Transcript 102803
Network Layer, Routing, IP
October 28-30, 2003
10/28/2003-10/30/2003
Assignments
• Homework 4
• Project 2
• Read Chapter 4 sections 4.1-4.4 for this
week
10/28/2003-10/30/2003
Network Layer
• Move packet from sender to
receiver
• Network layer protocols in
every host, router
• Three Functions:
– path determination: route
taken by packets from source
to dest. Routing algorithms
– forwarding: move packets
from router’s input to
appropriate router output
– call setup: some network
architectures require router
call setup along path before
data flows
10/28/2003-10/30/2003
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Service Model
• End-to-end transport of data between
sending and receiving systems
– How is this different than the transport
layer services?
• Datagram versus Virtual Circuit
10/28/2003-10/30/2003
Virtual Circuit
• Call setup, teardown for each call
• Each packet carries VC identifier (not destination
host ID)
• Every router on source-dest path maintains
“state” for each passing connection
– transport-layer connection only involved two end
systems
• Link, router resources (bandwidth, buffers) may
be allocated to VC
– to get circuit-like performance
10/28/2003-10/30/2003
Datagram Networks
• Routers: no state about end-to-end connections
• Packets forwarded using destination host address
• Best-effort service
– No guarantees with respect to delay, in-order delivery
application
transport
network
data link 1. Send data
physical
10/28/2003-10/30/2003
application
transport
network
2. Receive data
data link
physical
Datagram and the Internet
• Why is datagram service okay for the
Internet?
10/28/2003-10/30/2003
Routing
• Routing Protocol
– Find route from
default/first hop/source
router to destination
router
• Job of the algorithm –
find a “good path”
– Use graph abstraction
to represent the
network
– Where do the numbers
come from?
10/28/2003-10/30/2003
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
Routing Algorithm Classification
Global or decentralized
information?
• Global:
– all routers have complete
topology, link cost info
– “link state” algorithms
• Decentralized:
– router knows physicallyconnected neighbors, link
costs to neighbors
– iterative process of
computation, exchange of
info with neighbors
– “distance vector”
algorithms
10/28/2003-10/30/2003
Static or dynamic?
• Static:
– routes change slowly over
time
• Dynamic:
– routes change more quickly
• periodic update
• in response to link cost
changes
Load sensitive/insensitive
A Link-State Routing Algorithm
• Global – every router knows about all
others
• How does a node find out about all other
nodes?
• Once a node has the complete topology, it
runs Dijkstra’s algorithm to generate the
routing table
10/28/2003-10/30/2003
Notation
• c(i,j): link cost from node i to j. cost
infinite if not direct neighbors
• D(v): current value of cost of path
from source to dest. v
• p(v): predecessor node along path
from source to v, that is next v
• N: set of nodes whose least cost path
definitively known
10/28/2003-10/30/2003
Dijsktra’s Algorithm
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) = infinity
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
10/28/2003-10/30/2003
Dijkstra’s algorithm: 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
2
1
10/28/2003-10/30/2003
B
D
3
C
3
1
5
F
1
E
2
Discussion
• Algorithm complexity
–
–
–
–
n nodes
each iteration: need to check all nodes, w, not in N
n*(n+1)/2 comparisons: O(n**2)
more efficient implementations possible: O(nlogn)
• Oscillations possible:
D
1
– e.g., link cost = amount of carried traffic
– Solution?
A
A
A
1
0
1+e
0 0
C
e
B
e
initially
2+e
D
0
1
10/28/2003-10/30/2003
0
1+e 1
C
B
0
… recompute
routing
0
D
1
0 0
2+e
B
C 1+e
… recompute
2+e
D
0
A
1+e 1
C
0
B
e
… recompute
Distance Vector Routing
Algorithm
• Iterative, asynchronous, and distributed
• Distance table
– all nodes have one
– row for all destinations and a column for
neighbors
X
D (Y,Z)
distance from X to
= Y, via Z as next hop
= c(X,Z) + min {DZ(Y,w)}
w
10/28/2003-10/30/2003
Distance Table: Example
7
A
B
1
C
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
E
2
D
E
D (C,D) = c(E,D) + min {DD(C,w)}
= 2+2 = 4
w
E
D (A,D) = c(E,D) + min {DD(A,w)}
E
w
= 2+3 = 5
loop!
D (A,B) = c(E,B) + min {D B(A,w)}
= 8+6 = 14
10/28/2003-10/30/2003
w
loop!
Routing Table
E
cost to destination via
Outgoing link
D ()
A
B
D
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,4
Distance table
10/28/2003-10/30/2003
to use, cost
Routing table
DV Overview
Each node:
wait for (change in local link
cost of msg from neighbor)
recompute distance table
if least cost path to any dest
has changed, notify
neighbors
10/28/2003-10/30/2003
Distance Vector Algorithm
At all nodes, X:
1 Initialization:
2 for all adjacent nodes v:
3
D X(*,v) = infinity
/* the * operator means "for all rows" */
4
D X(v,v) = c(X,v)
5 for all destinations, y
6
send min D X(y,w) to each neighbor /* w over all X's neighbors */
w
10/28/2003-10/30/2003
Distance Vector Algorithm
8 loop
9 wait (until I see a link cost change to neighbor V
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 d */
14 /* note: d could be positive or negative */
15 for all destinations y: DX(y,V) = D X(y,V) + d
16
17 else if (update received from V wrt destination Y)
18 /* shortest path from V to some Y has changed */
19 /* V has sent a new value for its min DV(Y,w) */
20 /* call this received new value is "newval" w */
21 for the single destination y: DX(Y,V) = c(X,V) + newval
22
23 if we have a new min DX(Y,w)for any destination Y
w
24
send new value of minw DX(Y,w) to all neighbors
25
26 forever
10/28/2003-10/30/2003
Example
X
2
Y
7
1
Z
X
Z
X
Y
D (Y,Z) = c(X,Z) + minw{D (Y,w)}
= 7+1 = 8
D (Z,Y) = c(X,Y) + minw {D (Z,w)}
= 2+1 = 3
10/28/2003-10/30/2003
Example
X
2
Y
7
1
Z
10/28/2003-10/30/2003
Link Cost Changes
• node detects local link cost
change
• updates distance table (line 15)
• if cost change in least cost path,
notify neighbors (lines 23,24)
“good
news
travels
fast”
10/28/2003-10/30/2003
1
X
4
Y
50
1
Z
algorithm
terminates
Link Cost Changes
• good news travels fast
• bad news travels slow “count to infinity”
problem!
60
X
4
Y
50
1
Z
algorithm
continues
on!
10/28/2003-10/30/2003
Poisoned Reverse
If Z routes through Y to get to X
• Z tells Y its (Z’s) distance to X is infinite
(so Y won’t route to X via Z)
• will this completely solve count to infinity
problem?
10/28/2003-10/30/2003
60
X
4
Y
50
1
Z
algorithm
terminates
Comparison of LS and DV
• Message Complexity
• Speed of Convergence
• Robustness
10/28/2003-10/30/2003
Hierarchical Routing
• So far – all routers are equal, network is
flat
– Why is this view a problem?
10/28/2003-10/30/2003
Hierarchical Routing
• Aggregate routers into autonomous
systems ASs
• Intra-AS routing
• Each AS has a gateway
– responsible for inter-AS routing
10/28/2003-10/30/2003
Intra-AS and Inter-AS routing
C.b
a
C
Gateways:
B.a
A.a
b
A.c
d
A
a
b
c
a
c
B
b
•perform inter-AS
routing amongst
themselves
•perform intra-AS
routers with other
routers in their
AS
network layer
inter-AS, intra-AS
routing in
gateway A.c
10/28/2003-10/30/2003
link layer
physical layer
Intra-AS and Inter-AS routing
C.b
a
C
Host
h1
b
A.a
Inter-AS
routing
between
A and B
A.c
a
d
c
b
A
Intra-AS routing
within AS A
B.a
a
c
B
Host
h2
b
Intra-AS routing
within AS B
• We’ll examine specific inter-AS and intraAS Internet routing protocols shortly
10/28/2003-10/30/2003
Assignments
• Continue work on Project 2
• Finish reading chapter 4 for next week –
we will not talk about 4.6 in class
10/28/2003-10/30/2003
Network Layer
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
forwarding
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
10/28/2003-10/30/2003
IP Addressing
• IP address
223.1.1.1
– 32-bit identifier for host,
router interface
223.1.2.1
• interface – connection
between host/router and
physical link
– router’s typically have
multiple interfaces
– host may have multiple
interfaces
– IP addresses associated
with each interface
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
10/28/2003-10/30/2003
1
1
1
IP Addressing
• IP address:
– network part (high order
bits)
– host part (low order bits)
• What’s a network ? (from IP
address perspective)
– device interfaces with
same network part of IP
address
– can physically reach
each other without
intervening router
10/28/2003-10/30/2003
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
LAN
223.1.3.1
223.1.3.2
network consisting of 3 IP networks
(for IP addresses starting with 223,
first 24 bits are network address)
Classful Addressing
class
A
0 network
B
10
C
110
D
1110
network
128.0.0.0 to
191.255.255.255
host
network
multicast address
32 bits
10/28/2003-10/30/2003
1.0.0.0 to
127.255.255.255
host
host
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
CIDR
• Classful addressing
– inefficient use of address space, address space exhaustion
– example?
• CIDR: Classless InterDomain Routing
– network portion of address of arbitrary length
– address format: a.b.c.d/x, where x is # bits in network portion of
address
network
part
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
10/28/2003-10/30/2003
How do I get an IP address?
• Two options – what are they?
• Which is used when and why?
10/28/2003-10/30/2003
What about the network part?
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
Organization 1
Organization 2
...
11001000 00010111 00010000 00000000
11001000 00010111 00010010 00000000
11001000 00010111 00010100 00000000
…..
….
200.23.16.0/23
200.23.18.0/23
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
10/28/2003-10/30/2003
Route Aggregation
Hierarchical addressing allows efficient advertisement of routing
information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
10/28/2003-10/30/2003
“Send me anything
with addresses
beginning
199.31.0.0/16”
Constructing a Packet
misc source dest
fields IP addr IP addr
10/28/2003-10/30/2003
data
Determining the Next Hop
Dest. Net. next router Nhops
misc
data
fields 223.1.1.1 223.1.1.3
223.1.1
223.1.2
223.1.3
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.2
223.1.1.3
223.1.3.1
10/28/2003-10/30/2003
223.1.2.9
223.1.3.27
223.1.3.2
E
Determining the Next Hop
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
misc
data
fields 223.1.1.1 223.1.2.3
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.2
223.1.1.3
223.1.3.1
10/28/2003-10/30/2003
223.1.2.9
223.1.3.27
223.1.3.2
E
Router Forwarding Table
Dest. Net router Nhops interface
misc
data
fields 223.1.1.1 223.1.2.3
223.1.1
223.1.2
223.1.3
A
-
1
1
1
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.2
223.1.1.3
223.1.3.1
10/28/2003-10/30/2003
223.1.2.9
223.1.3.27
223.1.3.2
E
Datagram Format
32 bits
head. type of
length
ver
len service
fragment
flgs
16-bit identifier
offset
upper
time to
Internet
layer
live
checksum
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
10/28/2003-10/30/2003
IP Fragmentation & Reassembly
• network links have MTU
(max.transfer size) - largest
possible link-level frame
– different link types,
different MTUs
• large IP datagram divided
(“fragmented”) within net
– one datagram becomes
several datagrams
– “reassembled” only at
final destination
– IP header bits used to
identify, order related
fragments
10/28/2003-10/30/2003
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
IP Fragmentation and Reassembly
Example
• 4000 byte
datagram
• MTU = 1500
bytes
length ID fragflag offset
=4000 =x
=0
=0
One large datagram becomes
several smaller datagrams
length ID fragflag offset
=1500 =x
=1
=0
length ID fragflag offset
=1500 =x
=1
=1480
length ID fragflag offset
=1040 =x
=0
=2960
10/28/2003-10/30/2003
ICMP: Internet Control Message
Protocol
• used by hosts, routers,
gateways to communication
network-level information
– error reporting:
unreachable host, network,
port, protocol
– echo request/reply (used
by ping)
• network-layer “above” IP:
– ICMP msgs carried in IP
datagrams
• ICMP message: type, code
plus first 8 bytes of IP
datagram causing error
10/28/2003-10/30/2003
Type
0
3
3
3
3
3
3
4
Code
0
0
1
2
3
6
7
0
8
9
10
11
12
0
0
0
0
0
description
echo reply (ping)
dest. network unreachable
dest host unreachable
dest protocol unreachable
dest port unreachable
dest network unknown
dest host unknown
source quench (congestion
control - not used)
echo request (ping)
route advertisement
router discovery
TTL expired
bad IP header
DHCP: Dynamic Host
Configuration Protocol
• Goal: allow host to dynamically obtain its IP address
from network server when it joins network
– Can renew its lease on address in use
– Allows reuse of addresses (only hold address while connected
an “on”
– Support for mobile users who want to join network (more shortly)
• DHCP overview:
–
–
–
–
host broadcasts “DHCP discover” msg
DHCP server responds with “DHCP offer” msg
host requests IP address: “DHCP request” msg
DHCP server sends address: “DHCP ack” msg
10/28/2003-10/30/2003
DHCP client-server scenario
A
223.1.1.2
223.1.1.4
B
223.1.2.1
DHCP
server
223.1.1.1
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
10/28/2003-10/30/2003
223.1.3.27
223.1.3.2
E
arriving DHCP
client needs
address in this
network
DHCP client-server scenario
DHCP server: 223.1.2.5
DHCP discover
src : 0.0.0.0, 68
dest.: 255.255.255.255,67
yiaddr: 0.0.0.0
transaction ID: 654
DHCP offer
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 654
Lifetime: 3600 secs
DHCP request
time
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
DHCP ACK
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
10/28/2003-10/30/2003
arriving
client
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0/24
10.0.0.4
10.0.0.1
10.0.0.2
138.76.29.7
10.0.0.3
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
10/28/2003-10/30/2003
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
NAT: Network Address Translation
• Implementation: NAT router must:
– outgoing datagrams: replace (source IP address, port #) of every
outgoing datagram to (NAT IP address, new port #)
• . . . remote clients/servers will respond using (NAT IP address, new
port #) as destination addr.
– remember (in NAT translation table) every (source IP address,
port #) to (NAT IP address, new port #) translation pair
– incoming datagrams: replace (NAT IP address, new port #) in
dest fields of every incoming datagram with corresponding
(source IP address, port #) stored in NAT table
10/28/2003-10/30/2003
NAT
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
2
NAT translation table
WAN side addr
LAN side addr
1: host 10.0.0.1
sends datagram to
128.119.40, 80
138.76.29.7, 5001 10.0.0.1, 3345
……
……
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
138.76.29.7
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3: Reply arrives
dest. address:
138.76.29.7, 5001
10/28/2003-10/30/2003
3
1
10.0.0.4
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
10.0.0.1
10.0.0.2
4
10.0.0.3
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
NAT
• 16-bit port-number field:
– 60,000 simultaneous connections with a
single LAN-side address!
• NAT is controversial:
– routers should only process up to layer 3
– violates end-to-end argument
• NAT possibility must be taken into account by app
designers, e.g., P2P applications
– address shortage should instead be solved by
IPv6
10/28/2003-10/30/2003