Transcript foils-4.1-to-4.4-1199

Part IV
Network Layer Protocols
Routing
IP Protocol
Router Architectures
Network Layer Functions
• Determine the routes to be taken by
datagrams using routing algorithms such as
Link State, Distance Vector, Hierarchical
Routing, multicast routing
• Switch packets arriving on an input port to
the output port specified by the routing
algorithms
• In case of connection oriented services
(ATM), implement Call Setup and Virtual
Circuit mechanisms and maintain
information related to set-up VCs
Network Layer Functions
Virtual Circuit (VC) Service
common route followed by all packets of a connection, thus
providing in-order packet delivery to a destination
VC phases:
VC Set-up: source to destination route is selected, tables
entries are inserted indicating the VC numbers and
incoming/outgoing ports; resources may be reserved for
this connection (eg buffer space)
Data Transfer: data packets flow over the selected route,
headers indicate the VC numbers
VC tear-down: either side can request tear-down, other
side is informed, and resources are released
Signaling Messages and Signaling Protocol: used to set-up
and tear-down VCs
Datagram Service
• No connection set-up and tear-down, thus
routers do not have to maintain any
connection state information
• Packets carry source and destination
addresses and are switched in a router based
on the destination address
• packets may follow different end-to-end
routes, and thus may arrive out of order
Virtual Circuit Vs. Datagram
Internet Service Model
• Internet uses datagram, while ATM uses VC
service
• Internet provides only one type of datagram
service, sometimes called best effort; ie no
guarantees regarding in-order delivery,
throughput, end to end average delay, jitter,
or just plain delivery!
• Researchers are currently working to add
differentiated services
ATM Service Models
• 4 service classes for a user connection:
– Constant Bit Rate (CBR): connection looks like a
dedicated wire; guarantees bdw and upper bounds on
loss rate, delay, jitter; suitable for real-time
applications (digitized voice)
– Unspecified Bit Rate (UBR): guarantees only in-order
delivery; suited for interactive traffic (email,
newsgroups)
– Available Bit Rate (ABR): guarantees a minimum
transmission rate, but if bandwidth is available, user
may exceed that rate up to some peak cell rate (suitable
for Web browsing)
– Variable Bit Rate (VBR): provides guarantees as in
CBR, but user can vary cell rate; suitable for
compressed video applications
Routing Principles
• Routing: delivering a packet to its destination on
the best possible path
• Routing steps:
(a) determine node network address
(b) compute/construct the path
(c) forward the packet to destination
Here, we will focus on (b) - routing alg. for
path computation
Routing Alg Requirements
• Find path with min delay, cost or other metric
• dynamic reconfiguration after failures/changes
• adaptive load balancing
Routing Alg Classification
• Global routing (eg, Link State): each node knows
complete topology (connectivity, link costs etc); it
individually computes all routes (“centralized”
computation)
• Distributed (decentralized) routing (eg, Distance Vector):
no node has global topology knowledge. Totally
distributed route computation. Gradual computation of
routes via exchange of route tables among neighbors
• Also static routing (manually edited routing tables) vs
dynamic routing (automatically updated tables)
Link State Routing
• Each router measures the “costs” (eg, delay, bdw, pkt loss
etc.) of its attached links
• Periodically (or upon link change/failure) it packs the link
costs in a Link State (LS) pkt, and broadcasts the LS pkt
to its neighbors
• The neighbors will in turn broadcast the LS pkt to their
neighbors and so on until all nodes have heard the pkt
(propagation via flooding)
• Duplicate pkts are detected and dropped based on source
ID and unique sequence number
Link State Routing (cont)
• At steady state, each router has received the LS updates
from all other routers
• It can build a complete network topology and link cost
map (identical for all routers)
• Next, it computes routes from itself to all other nodes in
the network (using, for example, Dijkstra’s Alg). It creates
a routing table with such routes
• Routing tables at different nodes are all consistent since
they are based on the same topology/cost data base
• LS routing protocol used in OSPF intradomain routing
Dijkstra Shortest Path Alg
Notation:
• c(i,j) be cost of link (i,j);
• D(v) cost of path from source A to v;
• p(v) previous node on shortest path from A to v
Dijkstra’s Alg (cont)
1 Initialization:
2
N = {A}
3
for all nodes v
4
if v adjacent to A
5
then D(v) = c(A,v)
6
else D(v) = infty
7
8
Loop
9
find w not in N such that D(w) is a minimum
10
add w to N
11
update D(v) for all v adjacent to w and not in N:
12
D(v) = min( D(v), D(w) + c(w,v) )
13
/* new cost to v is either old cost to v or known
14
shortest path cost to w plus cost from w to v */
15 until all nodes in N
step
N
D(B),p(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),p(F)
0
A
2,A
5,A
1
AD
2,A
4,D
2
ADE
2,A
3,E
4,E
3
ADEB
3E
4E
4
ADEBC
5
ADEBCF
1,A
infty
infty
2,D
infty
4E
Dijkstra’s Alg Complexity
• Assume the set of nodes is stored as a linear array
• To find the node not in N, with min distance from A, it
requires O(n) operations
• The above step is repeated n times, thus total complexity
is O(n)
• Using sorted heap instead of linear array, the complexity is
reduced to O(n lgn)
Link State oscillatory behavior
• Route oscillations may occur if link cost depends on flow
and thus on routes.
Distance Vector routing alg
• Distance Vector (DV): vector of distances to all
destinations
• Periodically, each nodes receives from neighbors their
respective DVs
• It adds to each DV entry the link cost to neighbor
• It updates own DV using the min distance (via any of the
neighbors) to each destination
• It creates Routing Vector: vector of next hops to each
destination following min distance path.
DV code
Initialization:
2
for all adjacent nodes v:
3
DX(*,v) = infty
/* the * operator means "for
4
DX(v,v) = c(X,v)
5
for all destinations, y
6
send minwD(y,w) to each neighbor /* w over all
7
8 loop
9
wait (until I see a link cost change to neighbor
10
or until I receive update from neighbor V)
11
12
if (c(X,V) changes by d)
13
/* change cost to all dest's via neighbor v by
all rows" */
X's neighbors */
V
d */
DV code (cont’d)
14
15
16
17
18
19
20
21
22
23
24
25
26
/* note: d could be positive or negative */
for all destinations y: DX(y,V) = DX(y,V) + d
else if (update received from V wrt destination Y)
/* shortest path from V to some Y has changed */
/* V has sent a new value for its minw DV(Y,w) */
/* call this received new value is "newval"
*/
for the single destination y: DX(Y,V) = c(X,V) + newval
if we have a new minw DX(Y,w)for any destination Y
send new value of minw DX(Y,w) to all neighbors
forever
Bellman Ford Alg
• The algorithm used to compute DVs is the Bellman Ford
(B-F) Algorithm
• For DV computation, we have used a “decentralized”
version of the B-F algorithm
• The B-F based DV routing algorithm is used in many
network routing protocols: BGP, ISO IDRP, RIP, Novell
IPX, original ARPANET, Packet Radio net, etc.
DV table example
DV convergence example
Link cost change: good news
Count-to-infinity problem
Poison Reverse
• If node Z uses next node Y to get to X, Z will advertises
D(X) = 00 to Y
Poison Reverse (cont)
• Note: loops with 3 or more nodes (instead of pingpong) not detected by Poison Reverse
• Solution? Path Vector: advertise not only the
distance to destination, but the entire path to
destination
• Path vector used in internet BGP (interdomain
routing)
Link State vs Distance Vector
• Message complexity:
For each cycle, O(nE) for both LS and DV, where
E = # of links
However, LS propagates change to ALL nodes; DV only to
nodes affected by change
• Speed of Convergence:
LS updates propagate much faster than DV updates; this is
one of the reasons why ARPANET dumped DV for LS in
1979
Link State vs Distance Vector (cont)
• Robustness:
both LS and DV tolerant of changes/failure; LS better
protected against router mulfunctions (wrong path
computation); the error remains local in LS; it affects the
entire network in DV
• QoS support:
in LS, complete topology map allows router to compute
paths with QoS constraints (Q-OSPF)
• Implementation cost:
LS requires more memory and more processing
Hierarchical Routing
• Routing hierarchy needed for:
• Scaling: “flat” routing tables (DV) and topology maps (LS)
grow too large. Message and computation O/H excessive
• Local autonomy: different organizations (eg, Campus,
company, ISP) wish to operate own network and to “hide”
internal organization structure
Hierarchical Routing (cont)
• Solution: Autonomous Systems (AS)
interconnected by gateway routers
• Intra-AS routing: varies from AS to AS
• Inter-AS routing: same for the entire Internet; it is
run by Border Gateways
Intra and inter-AS routing
Gateway router
Intra and inter-AS path
Internet Protocol (IP)
• Connectionless datagram service (like US
Post Service)
• No performance guarantees, not even
delivery guarantee
• No guarantee of in-order delivery of
datagrams
• Components of network layer:
– IP Protocol
Addressing In IP
• A host is typically connected via one
link/interface to the network
• A router is typically connected by more than
one link to the network
• Machines on the network will have as many
addresses as there are links that connect
them to the network, thus routers have more
than one IP address, while hosts typically
have one IP address
• IP Address is 32 bit long, expressed (for
Hosts And Router Addresses
223.1.1.4
223.1.3.27
223.1.2.9
• Router has three IP addresses
• Hosts/router interface on a network (LAN
in the example above) share the first three
bytes in the address; e.g. 223.1.3 for the
Addresses In Interconnected
Networks
This example has
three LANs with IP
addresses: 223.1.1,
223.1.2, 223.1.3;
and three other
networks (or
subnets) with
addresses: 223.1.7,
223.1.8, 223.1.9
Address Classes
Or Host/Router Interface
IP Datagram Forwarding
• Every IP datagram has an IP header
including source and destination IP
223.1.1.4
223.1.3.27
addresses; Hosts/Routers
have routing
223.1.2.9
tables; for example:
Routing Table In Host A
Next
Dest
#Hops
Router
Net
223.1.1
-1
223.1.2
223.1.1.4 2
223.1.3
223.1.1.4 2
Routing Table In Router
Dest
Next #Hops Interface
Net
Router
1
1
223.1.1 -1
2
223.1.2 -3
223.1.3 223.1.1.4 1
IP Datagram Format
• Version Number: allows coexistence of
more than one version; router forwards the
arriving datagram for processing to the
appropriate version of IP
• Header Length: to accommodate a variable
number of Option fields
• TOS: type of service, various interpretations
• Length: header + data in bytes, 16 bits
• Identifier, Flags, Fragmentation Offset:
used in Fragmentation, TBD
IP Datagram Format (Cont.)
IP Datagram Fragmentation
• Links along a route may use different link
layer protocols, possibly with differing
maximum frame size (called Maximum
Transfer Unit, or MTU)
• A router which receives a datagram on one
link, and has to forward on another link
with smaller MTU ‘fragments’ the datagram
• Each fragment travel to the destination
separately, and the original datagram is
reassembled as the destination, and its
payload passed to the transport layer
Fragmentation Example
1st fragment
1480 bytes in the data field of
the IP datagram.
identification = 777
offset = 0 (meaning the data
should be inserted beginning at
byte 0)
flag = 1 (meaning there is
more)
2nd fragment
1480 byte information field
identification = 777
offset = 1,480 (meaning the
data should be inserted beginning
at byte 1,480
Internet Control Message
Protocol (ICMP)
• Use by network nodes to exchange control
information such as error messages, and for
simple testing operations (eg, ping)
• ICMP messages are carried in IP datagrams
• Example messages:
–
–
–
–
–
–
echo request (ping)
echo reply (response to ping)
destination host unreachable
destination network unreachable
source quench (congestion control)
TTL expired (sent to source of datagram which was