Transcript ppt
ECE453 – Introduction to
Computer Networks
Lecture 9 - The Network Layer (I)
- Routing
1
Recap
Framing
Error detection and correction
Reliable or unreliable data transfer
Channel allocation protocol
2
Network Core and Network Edge
application
transport
network
data link
physical
network
data link
physical
Network
core
network
data link
physical
Network
edge
application
transport
network
data link
physical
3
Network Core – Information
Transmission
Circuit switching
Telephone system
Message switching
Mail delivery
The message travels as a complete unit. At any
one time, it completely exists in one place.
Packet switching
The Internet
4
Design Issues
Store-and-forward packet switching
Services to the transport layer
Connection-oriented vs. Connectionless
Quality of service (QoS)
5
Network Layer Services
Connectionless
Best-effort
No guarantee
The Internet
No advance setup is
needed
Datagram subnet
Connection-oriented
Guaranteed delivery
ATM
A path from the
source router to the
destination router is
established before
any data packets can
be sent
Virtual circuit
6
The Internet Network Layer
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
routing
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
7
Routing - In the Middle of
Intersection …
8
Different Strategies
Nonadaptive
algorithms (or static
routing)
Adaptive algorithms
(or dynamic routing)
Global algorithm
(have a global
knowledge – a map)
Decentralized
algorithm (get
information only
from neighbor)
9
Graph Abstraction for Routing
Algorithms
Graph nodes Routers
Graph edge Physical links
Edge weight Link cost
Link cost
Delay, power consumption, congestion level,
$cost, etc.
5
Good path or optimal path
Minimum link cost
2
A
B
2
1
D
3
C
3
1
5
F
1
E
10
2
Two Fundamental Routing
Algorithms
Link state routing
A global algorithm
Distance vector routing (or BellmanFord routing, Ford-Fulkerson routing)
A decentralized algorithm
The original ARPANET routing algorithm,
replaced by LS routing in 1979
11
A Link State Routing Algorithm
Dijkstra’s algorithm
Net topology, link costs known to all
nodes
accomplished via “link state broadcast”
all nodes have the same info
computes least cost paths from the
source to all other nodes
Iterative algorithm
12
Dijkstra’s Algorithm: An
Example
Step
0
1
2
3
4
5
start N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
2,A
1,A
5,A
infinity
infinity
2,A
4,D
2,D
infinity
2,A
3,E
4,E
3,E
4,E
4,E
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
13
Dijkstra’s Algorithm: Discussion
Algorithm complexity: n nodes
each iteration: need to check all nodes, not in N
n*(n+1)/2 comparisons: O(n**2)
more efficient implementations possible: O(nlogn)
Oscillations possible:
e.g., link cost = amount of carried traffic
D
1
1
0
A
0 0
C
e
1+e
e
initially
B
1
2+e
A
0
D 1+e 1 B
0
0
C
… recompute
routing
0
D
1
A
0 0
C
2+e
B
1+e
… recompute
2+e
A
0
D 1+e 1 B
e
0
C
… recompute
14
E
DV Routing
Each router maintains a
distance table
Initialization
0 for itself
Infinity for non-neighbor
Link cost for neighbor
Message exchange between
neighbors
When a neighbor first comes
up
When information changes
(e.g. change in link cost)
Distance vector calculation
Minimize cost to each
destination
X
D (Y,Z)
cost to destination via
D ()
A
B
D
A
1
14
5
B
7
8
5
C
6
9
4
D
4
11
2
distance from X to
= Y, via Z as next hop
Z
= c(X,Z) + minw{D (Y,w)}
Iterative routing
Distributed routing
15
DV: Example
Y
X
X
2
Y
7
1
Z
Z
16
DV: Link Cost Changes
“good news travels fast”
Y
1
X
X
4
Y
50
1
Z
Z
algorithm
terminates
17
DV: Link Cost Changes
“bad news travels slow”
60
Count to infinity problem
X
4
Y
50
1
Z
algorithm
continues
on!
18
Distance Table: An Example
7
A
B
1
E
cost to destination via
D ()
A
B
D
A
1
14
5
B
7
8
5
C
6
9
4
D
4
11
2
2
8
1
C
E
2
D
E
D
D (C,D) = c(E,D) + minw {D (C,w)}
= 2+2 = 4
E
D
c(E,D)
+
min
{D
(A,w)}
D (A,D) =
w
= 2+3 = 5 loop!
E
B
D (A,B) = c(E,B) + minw{D (A,w)}
= 8+6 = 14
loop!
19