Transcript Network Layer

Network Layer: Routing
Goals:
 understand principles
behind network layer
services:



routing (path selection)
dealing with scale
how a router works
• Previous two lectures
 instantiation and
implementation in the
Internet
Overview:
 network layer services
 routing principle:
 path selection
 hierarchical routing
 IP
 Internet routing
protocols:


intra-domain
inter-domain
Lecture 6: Network Layer
#1
Network Layer
 Transport packet from source to
dest.
 Network layer in every host,
router
Basic functions:
 Data plane: forwarding

move packets from
router’s input port to
router output port
 Control plane: path
determination and call setup

determine route taken by
packets from source to
destination
Lecture 6: Network Layer
#2
Forwarding: Illustration
routing and call
setup
3
Lecture 6: Network Layer
#3
Network service model
Q: What service model
for “channel”
transporting packets
from sender to
receiver?
 guaranteed bandwidth?
 preservation of inter-packet
timing (no jitter)?
 loss-free delivery?
 in-order delivery?
 congestion feedback to
sender?
The most important
abstraction provided
by network layer:
? ?
?
virtual circuit
or
datagram?
Lecture 6: Network Layer
#5
Virtual circuits: signaling protocols
 used to setup, maintain teardown VC
 used in ATM, frame-relay, X.25
 not used in today’s Internet
 Cisco’s MPLS
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
6. Receive data application
3. Accept call
2. incoming call
transport
network
data link
physical
Lecture 6: Network Layer
#6
Virtual Circuit: call setup
 Resource allocation:
The call setup msg from source to destination.
 Path determination:

• Source based or network based.
 Msgs
includes the required resoutces:
• BW, latency, buffer, etc.

A router can either:
• accept (and commit) or reject
 Path
accepted if all routers accept.
Lecture 6: Network Layer
#7
Virtual Circuit: Identifiers
 Forward call-setup pass:

Each router allocate an id for the VC
 Backward call-setup pass:
 Each router informs its predecessor its id
 Runtime:

When receiving a packet with an id:
• Looks up the output port
• Looks up the new id
• Send on the required port with new id.
Lecture 6: Network Layer
#8
Virtual Circuit: identifiers
 Example setup
BW=1Mb
2
1
BW=1Mb
1
2
BW=1Mb
In
In
port
port
VC
VC id
id
in
in
Out
Out
port
port
VC
VC id
id
out
out
In
In
port
port
VC id
in
Out
port
VC id
out
11
38
2
22
11
22
2
xx
Lecture 6: Network Layer
#9
Virtual Circuit: identifiers
 Example runtime
VCid=38
2
1
VCid=22
2
1
VCid=xx
In
In
port
port
VC
VC id
id
in
in
Out
Out
port
port
VC
VC id
id
out
out
In
In
port
port
VC id
in
Out
port
VC id
out
11
38
2
22
11
22
2
xx
Lecture 6: Network Layer
#10
Datagram networks:
the Internet model
 no call setup at network layer
 routers: no state about end-to-end connections
 no network-level concept of “connection”
 packets typically routed using destination host ID
 packets between same source-dest pair may take
different paths
application
transport
network
data link 1. Send data
physical
application
transport
network
2. Receive data
data link
physical
Lecture 6: Network Layer
#14
Forwarding table
Destination Address Range
4 billion
possible entries
Link Interface
11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111
0
11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111
1
11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111
2
otherwise
3
Lecture 6: Network Layer
#15
Longest prefix matching
Prefix Match
Link Interface
11001000 00010111 00010
0
11001000 00010111 00011000
1
11001000 00010111 00011
2
otherwise
3
VC implementation
Examples
DA: 11001000 00010111 00010110 10100001
Which interface?
DA: 11001000 00010111 00011000 10101010
Which interface?
Lecture 6: Network Layer
#16
ATM: overview
 Asynchronous Transfer Mode
 Fixed packets size: called cells
 53 bytes = 5 header + 48 data
 All virtual circuit-based
 Types of virtual circuits
 Virtual circuits and virtual paths
 Permanent and switched
 Architecture is a QoS-based approach
Lecture 6: Network Layer
#17
Network Layer Quality of Service
Network
Architecture
Internet
Service
Model
Guarantees ?
Congestion
Bandwidth Loss Order Timing feedback
best effort none
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
constant
rate
guaranteed
rate
guaranteed
minimum
none
no
no
no
yes
yes
yes
yes
yes
yes
no
yes
no
no (inferred
via loss/delay)
no
congestion
no
congestion
yes
no
yes
no
no
 Internet model being extended: Intserv, Diffserv

multimedia networking
ATM: Asynchronous Transfer Mode; CBR: Constant Bit Rate; V: Variable; A: available; U: Unspecified
Lecture 6: Network Layer
#18
Datagram or VC network: why?
Internet (Datagram)
 data exchange among
computers
 “elastic” service, no strict
timing req.
 “smart” end systems
(computers)
 can adapt, perform
control, error recovery
 simple inside network,
complexity at “edge”
 many link types
 different characteristics
 uniform service difficult
ATM (VC)
 evolved from telephony
 human conversation:
strict timing, reliability
requirements
 need for guaranteed
service
 “dumb” end systems
 telephones
 complexity inside
network

 VC Benefits:
 Fast forwarding
 Traffic Engineering.
Lecture 6: Network Layer
#19
Network Layer: Protocols
Network layer functions:
Transport layer
Routing protocols
•path selection
•e.g., RIP, OSPF, BGP
Control protocols
- router “signaling”
e.g. RSVP
Control protocols
•error reporting
e.g. ICMP
Network
layer
forwarding
Network layer protocol (e.g., IP)
•addressing conventions
•packet format
•packet handling conventions
Link layer
physical layer
Lecture 6: Network Layer
#20
Control: ROUTING algorithms
Lecture 6: Network Layer
#21
Control Plane: Routing
Routing
Goal: determine “good” paths
(sequences of routers) thru
network from sources to dest.
Graph abstraction for the
routing problem:
5
 graph nodes are routers
 graph edges are physical
links

links have properties: delay,
capacity, $ cost, policy
A
2
1
B
2
D
3
3
1
C
1
E
5
F
2
Lecture 6: Network Layer
#22
Key Desired Properties of a Routing
Algorithm
 Robustness
 Optimality
 find
good path
(for user/provider)
 Simplicity
Lecture 6: Network Layer
#23
- Robustness
- Optimality
- Simplicity
Routing Design Space
 Routing has a large design space
 who decides routing?
• source routing: end hosts make decision
• network routing: networks make decision

how many paths from source s to destination d?
• multi-path routing
• single path routing

will routing adapt to network traffic demand?
• adaptive routing
• static routing

…
Lecture 6: Network Layer
#24
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
Static or dynamic?
Static:
 routes change slowly over
time
Dynamic:
 routes change more quickly
 periodic update
 in response to link cost
changes
Lecture 6: Network Layer
#25
A Link-State Routing Algorithm
Dijkstra’s algorithm
 net topology, link costs
known to all nodes
 accomplished via “link
state broadcast”
 all nodes have same info
 computes least cost paths
from one node (“source”) to
all other nodes
 gives routing table for
that node
 iterative: after k
iterations, know least cost
path to k dest.’s
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
Lecture 6: Network Layer
#26
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) = 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
Lecture 6: Network Layer
#27
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
B
2
1
D
3
C
3
1
5
F
1
E
2
Lecture 6: Network Layer
#28
Dijkstra’s algorithm, discussion
Algorithm complexity: n nodes
 each iteration: need to check all nodes, w, not in N
 n(n+1)/2 comparisons: O(n2)
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
B
e
initially
2+e
D
0
1
A
1+e 1
C
0
B
0
… recompute
routing
0
D
1
A
0 0
2+e
B
C 1+e
… recompute
2+e
D
0
A
1+e 1
C
0
B
0
… recompute
Lecture 6: Network Layer
#29
Distance Vector Routing Algorithm
iterative:
 continues until no
nodes exchange info.
 self-terminating: no
“signal” to stop
asynchronous:
 nodes need not
exchange info/iterate
in lock step!
distributed:
 each node
communicates only with
directly-attached
neighbors
Distance Table data structure
 each node has its own
 row for each possible destination
 column for each directly-
attached neighbor to node
 example: in node X, for dest. Y
via neighbor Z:
X
D (Y,Z)
distance from X to
= Y, via Z as next hop
= c(X,Z) + min {DZ(Y,w)}
w
Lecture 6: Network Layer
#30
Distance Vector Routing
 Basis of RIP, IGRP, EIGRP routing
protocols
 Based on the Bellman-Ford
algorithm (BFA)
 Conceptually, runs for each
destination separately
Lecture 6: Network Layer
#31
Distance Vector Routing: Basic Idea
 At node i, the basic update rule
d i  min
jN ( i )
(d ij  d j )
where
- di denotes the distance
estimation from i to the
destination,
- N(i) is set of neighbors of
node i, and
- dij is the distance of
the direct link from i to j;
assume positive
destination
j
di
d ij
i
dj
Lecture 6: Network Layer
#32
Distance Table: Example
A
7
Below is just one step! The algorithm repeats forever! 10
distance tables
dE ()
computation
from neighbors
A
B
D
A
B
D
A
0
7

10 15 
B
7
0

17 8
C

1
2

D


0

10 8
2
E’s
distance
table
B
1
C
2
8
E
D
2
distance
table E sends
to its neighbors
A: 10
A: 10

B: 8
B: 8
9
4
D: 4
C: 4

2
D: 2
D: 2
E: 0
Lecture 6: Network Layer
#33
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
w
(why not 15?)
Lecture 6: Network Layer
#34
Distance table gives 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,2
Distance table
to use, cost
Routing table
Lecture 6: Network Layer
#35
Distance Vector Routing: overview
Iterative, asynchronous:
each local iteration caused
by:
 local link cost change
 message from neighbor: its
least cost path change
from neighbor
Distributed:
 each node notifies
neighbors only when its
least cost path to any
destination changes

neighbors then notify
their neighbors if
necessary
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
Lecture 6: Network Layer
#36
Distance Vector Algorithm:
At all nodes, X:
1 Initialization:
2 for all adjacent nodes v:
3
DX(*,v) = infty
/* the * operator means "for all rows" */
4
DX(v,v) = c(X,v)
5 for all destinations, y
6
send minw DX(y,w) to each neighbor /* w over all X's neighbors */
Lecture 6: Network Layer
#37
Distance Vector Algorithm (cont.):
8 loop
9 wait (until a link cost change to neighbor V
10
or until 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) = DX(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 minw DV(Y,w) */
20 /* call this received new value is "newval" */
21 for the single destination y: D X(Y,V) = c(X,V) + newval
22
23 if a new minw DX(Y,w) for any destination Y
24
send new value of minw DX(Y,w) to all neighbors
25
Lecture 6: Network Layer
26 forever
#38
Distance Vector Algorithm: 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
Lecture 6: Network Layer
#39
Distance Vector Algorithm: example
X
2
Y
7
1
Z
Lecture 6: Network Layer
#40
Distance Vector: link cost changes
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”
1
X
4
Y
50
1
Z
algorithm
terminates
Lecture 6: Network Layer
#41
Distance Vector: link cost changes
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!
Lecture 6: Network Layer
#42
Distance Vector: 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?
60
X
4
Y
50
1
Z
algorithm
terminates
Lecture 6: Network Layer
#43
Comparison of LS and DV algorithms
Message complexity
 LS: with n nodes, E links,
O(nE) msgs sent
 DV: exchange between
neighbors only
 larger msgs
 convergence time varies
Speed of Convergence
 LS: requires O(nE) msgs
may have oscillations
 DV: convergence time varies
 may be routing loops
 count-to-infinity problem
Robustness: what happens
if router malfunctions?
LS:


node can advertise
incorrect link cost
each node computes only
its own table
DV:



DV node can advertise
incorrect path cost
each node’s table used by
others
• error propagate thru
network
Lecture 6: Network Layer
#44
Hierarchical Routing
Our routing study thus far - idealization
 all routers identical
 network “flat”
… not true in practice
scale: with 200 million
destinations:
 can’t store all dest’s in
routing tables!
 routing table exchange
would swamp links!
administrative autonomy
 internet = network of
networks
 each network admin may
want to control routing in its
own network
Lecture 6: Network Layer
#45
Hierarchical Routing
 aggregate routers into
regions, “autonomous
systems” (AS)
 routers in same AS run
same routing protocol


Gateway router
 Direct link to router in
another AS
“intra-AS” routing
protocol
routers in different AS
can run different intraAS routing protocol
Lecture 6: Network Layer
#46
Interconnected ASes
3c
3a
3b
AS3
1a
2a
1c
1d
1b
Intra-AS
Routing
algorithm
2c
AS2
AS1
Inter-AS
Routing
algorithm
Forwarding
table
2b
 Forwarding table is
configured by both
intra- and inter-AS
routing algorithm


Intra-AS sets entries
for internal dests
Inter-AS & Intra-As
sets entries for
external dests
Lecture 6: Network Layer
#47
Inter-AS tasks
AS1 needs:
1. to learn which dests
are reachable through
AS2 and which
through AS3
2. to propagate this
reachability info to all
routers in AS1
Job of inter-AS routing!
 Suppose router in AS1
receives datagram for
which dest is outside
of AS1

Router should forward
packet towards on of
the gateway routers,
but which one?
3c
3b
3a
AS3
1a
2a
1c
1d
1b
2c
AS2
2b
AS1
Lecture 6: Network Layer
#48
Example: Setting forwarding table
in router 1d
 Suppose AS1 learns from the inter-AS
protocol that subnet x is reachable from
AS3 (gateway 1c) but not from AS2.
 Inter-AS protocol propagates reachability
info to all internal routers.
 Router 1d determines from intra-AS
routing info that its interface I is on the
least cost path to 1c.
 Puts in forwarding table entry (x,I).
Lecture 6: Network Layer
#49
Example: Choosing among multiple ASes
 Now suppose AS1 learns from the inter-AS protocol
that subnet x is reachable from AS3 and from AS2.
 To configure forwarding table, router 1d must
determine towards which gateway it should forward
packets for dest x.
 This is also the job on inter-AS routing protocol!
 Hot potato routing: send packet towards closest of
two routers.
Learn from inter-AS
protocol that subnet
x is reachable via
multiple gateways
Use routing info
from intra-AS
protocol to determine
costs of least-cost
paths to each
of the gateways
Hot potato routing:
Choose the gateway
that has the
smallest least cost
Determine from
forwarding table the
interface I that leads
to least-cost gateway.
Enter (x,I) in
forwarding table
Lecture 6: Network Layer
#50
Broadcast and Multicast Routing
Lecture 6: Network Layer
#51
Broadcast Routing
 Deliver packets from source to all other nodes
 Source duplication is inefficient:
duplicate
duplicate
creation/transmission
R1
R1
duplicate
R2
R2
R3
R4
source
duplication
R3
R4
in-network
duplication
 Source duplication: how does source
determine recipient addresses
Lecture 6: Network Layer
#52
In-network duplication
 Flooding: when node receives brdcst pckt,
sends copy to all neighbors

Problems: cycles & broadcast storm
 Controlled flooding: node only brdcsts pkt
if it hasn’t brdcst same packet before
Node keeps track of pckt ids already brdcsted
 Or reverse path forwarding (RPF): only forward
pckt if it arrived on shortest path between
node and source

 Spanning tree
 No redundant packets received by any node
Lecture 6: Network Layer
#53
Spanning Tree
 First construct a spanning tree
 Nodes forward copies only along spanning
tree
A
B
c
F
A
E
B
c
D
F
G
(a) Broadcast initiated at A
E
D
G
(b) Broadcast initiated at D
Lecture 6: Network Layer
#54
Spanning Tree: Creation
 Center node
 Each node sends unicast join message to center
node

Message forwarded until it arrives at a node already
belonging to spanning tree
A
A
3
B
c
4
E
F
1
2
B
c
D
F
5
E
D
G
G
(a) Stepwise construction
of spanning tree
(b) Constructed spanning
tree
Lecture 6: Network Layer
#55
Multicast Routing: Problem Statement
 Goal: find a tree (or trees) connecting
routers having local mcast group members



tree: not all paths between routers used
source-based: different tree from each sender to rcvrs
shared-tree: same tree used by all group members
Shared tree
Source-based trees
Lecture 6: Network Layer
#56
Approaches for building mcast trees
Approaches:
 source-based tree: one tree per source
shortest path trees
 reverse path forwarding

 group-shared tree: group uses one tree
 minimal spanning (Steiner)
 center-based trees
…we first look at the basic approaches
Lecture 6: Network Layer
#57
Shortest Path Tree
 mcast forwarding tree: tree of shortest
path routes from source to all receivers

Dijkstra’s algorithm
S: source
LEGEND
R1
1
2
R4
R2
3
R3
router with attached
group member
5
4
R6
router with no attached
group member
R5
6
R7
i
link used for forwarding,
i indicates order link
added by algorithm
Lecture 6: Network Layer
#58
Reverse Path Forwarding
 rely on router’s knowledge of unicast
shortest path from it to sender
 each router has simple forwarding behavior:
if (mcast datagram received on incoming link
on shortest path back to center)
then flood datagram onto all outgoing links
else ignore datagram
Lecture 6: Network Layer
#59
Reverse Path Forwarding: example
S: source
LEGEND
R1
R4
router with attached
group member
R2
R5
R3
R6
R7
router with no attached
group member
datagram will be
forwarded
datagram will not be
forwarded
• result is a source-specific reverse SPT
– may be a bad choice with asymmetric links
Lecture 6: Network Layer
#60
Reverse Path Forwarding: pruning
 forwarding tree contains subtrees with no mcast
group members
 no need to forward datagrams down subtree
 “prune” msgs sent upstream by router with no
downstream group members
LEGEND
S: source
R1
router with attached
group member
R4
R2
P
R5
R3
R6
P
R7
P
router with no attached
group member
prune message
links with multicast
forwarding
Lecture 6: Network Layer
#61
Shared-Tree: Steiner Tree
 Steiner Tree: minimum cost tree
connecting all routers with attached group
members
 problem is NP-complete
 excellent heuristics exists
 not used in practice:
computational complexity
 information about entire network needed
 monolithic: rerun whenever a router needs to
join/leave

Lecture 6: Network Layer
#62
Center-based trees
 single delivery tree shared by all
 one router identified as “center” of tree
 to join:
edge router sends unicast join-msg addressed
to center router
 join-msg “processed” by intermediate routers
and forwarded towards center
 join-msg either hits existing tree branch for
this center, or arrives at center
 path taken by join-msg becomes new branch of
tree for this router

Lecture 6: Network Layer
#63
Center-based trees: an example
Suppose R6 chosen as center:
LEGEND
R1
3
R2
router with attached
group member
R4
2
R5
R3
1
R6
1
router with no attached
group member
path order in which join
messages generated
R7
Lecture 6: Network Layer
#64
End Part 1
Lecture 6: Network Layer
#65
Hierarchical Routing
Our routing study thus far - idealization
 all routers identical
 network “flat”
… not true in practice
scale: with 50 million
destinations:
 can’t store all dest’s in
routing tables!
 routing table exchange
would swamp links!
administrative autonomy
 internet = network of
networks
 each network admin may
want to control routing in its
own network
Lecture 6: Network Layer
#66
Hierarchical Routing
 aggregate routers into
regions, “autonomous
systems” (AS)
 routers in same AS run
same routing protocol


“intra-AS” routing
protocol
routers in different AS
can run different intraAS routing protocol
gateway routers
 special routers in AS
 run intra-AS routing
protocol with all other
routers in AS
 also responsible for
routing to destinations
outside AS
 run inter-AS routing
protocol with other
gateway routers
Lecture 6: Network Layer
#67
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
link layer
physical layer
Lecture 6: Network Layer
#68
Intra-AS and Inter-AS routing
C.b
a
Host
h1
C
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 intra-AS
Internet routing protocols shortly
Lecture 6: Network Layer
#69
AS D
Routing: Example
E
d
AS A
(OSPF)
a2
F
No Export
to F
a1
i
AS C
AS B
i2
(OSPF intra
routing)
b
AS I
Lecture 6: Network Layer
#71
AS D
Routing: Example
E
d1
d
d2
AS A
(OSPF)
a2
F
i
AS C
a1
How to specify?
AS B
(OSPF intra
routing)
b
AS I
Lecture 6: Network Layer
#72
IP Addressing Scheme
 We need an address to uniquely identify
each destination
 Routing scalability needs flexibility in
aggregation of destination addresses
 we
should be able to aggregate a set of
destinations as a single routing unit
 Preview: the unit of routing in the Internet
is a network---the destinations in the routing
protocols are networks
Lecture 6: Network Layer
#73
IP Addressing: introduction
 IP address: 32-bit
identifier for host,
router interface
 interface: connection
between host, router
and physical link



router’s typically have
multiple interfaces
host may have multiple
interfaces
IP addresses
associated with
interface, not host, or
router
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
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
Lecture 6: Network Layer
1
#74
IP Addressing: introduction
 IP address: 32-bit
identifier for host,
router interface
 interface: connection
between host, router
and physical link



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
router’s typically have
223.1.3.2
223.1.3.1
multiple interfaces
host may have multiple
interfaces
IP addresses
associated with 132.67.192.133 = 10000100 01000011 11000000 10000101
interface, not host, or
223
67
192
133
router
Lecture 6: Network Layer
#75
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
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)
Lecture 6: Network Layer
#76
IP Addressing
How to find the
networks?
 Detach each
interface from
router, host
 create “islands of
isolated networks
223.1.1.2
223.1.1.1
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
Interconnected
system consisting
of six networks
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
Lecture 6: Network Layer
#77
IP Addresses
given notion of “network”, let’s re-examine IP addresses:
“class-full” addressing:
class
A
0 network
B
10
C
110
D
1110
1.0.0.0 to
127.255.255.255
host
network
128.0.0.0 to
191.255.255.255
host
network
multicast address
host
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
32 bits
Lecture 6: Network Layer
#78
IP addressing: CIDR
 classful addressing:


inefficient use of address space, address space exhaustion
e.g., class B net allocated enough addresses for 65K hosts,
even if only 2K hosts in that network
 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
Lecture 6: Network Layer
#79
CIDR Address Aggregation
AS D
d
d1
AS A
(OSPF)
130.132.1/24
i
i->a1: I can reach
130.132/16; my
path: I
a2
a1
130.132.2/24
AS I
intradomain
routing uses /24
130.132.3/24
Lecture 6: Network Layer
#80
CIDR Address Aggregation
B
x00/24: B
A
x01/24: C
C
x10/24: E
G
E
x11/24: F
F
Lecture 6: Network Layer
#81
IP addresses: how to get one?
Hosts (host portion):
 hard-coded by system admin in a file
 DHCP: Dynamic Host Configuration Protocol:
dynamically get address: “plug-and-play”
 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
 The common practice in LAN and home access
(why?)
Lecture 6: Network Layer
#82
IP addresses: how to get one?
Network (network portion):
 get allocated portion of ISP’s address space:
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
11001000 00010111 00010000 00000000
200.23.16.0/23
Organization 1
11001000 00010111 00010010 00000000
200.23.18.0/23
Organization 2
...
11001000 00010111 00010100 00000000
…..
….
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
Lecture 6: Network Layer
#83
Hierarchical addressing: 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
“Send me anything
with addresses
beginning
199.31.0.0/16”
Lecture 6: Network Layer
#84
Hierarchical addressing: more specific
routes
ISPs-R-Us has a more specific route to Organization 1
Organization 0
200.23.16.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
Organization 1
200.23.18.0/23
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
Lecture 6: Network Layer
#85
Network Address Translation: Motivation
 A local network uses just one public IP address as far as outside
world is concerned
 Each device on the local network is assigned a private IP address
rest of
Internet
local network
(e.g., home network)
192.168.1.0/24
192.168.1.1
192.168.1.2
192.168.1.3
138.76.29.7
192.168.1.4
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
Datagrams with source or
destination in this network
have 192.168.1/24 address for
source, destination (as usual)
Lecture 6: Network Layer
#86
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
Lecture 6: Network Layer
#87
NAT: Network Address Translation
NAT translation table
WAN side addr
LAN side addr
1: host 192.168.1.2
2: NAT router
sends datagram to
changes datagram
138.76.29.7, 5001 192.168.1.2, 3345
128.119.40.186, 80
source addr from
……
……
192.168.1.2, 3345 to
138.76.29.7, 5001,
S: 192.168.1.2, 3345
updates table
D: 128.119.40.186, 80
2
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
3
192.168.1.2
1
192.168.1.1
192.168.1.3
S: 128.119.40.186, 80
D: 192.168.1.2, 3345
4
192.168.1.4
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 192.168.1.2, 3345
Lecture 6: Network Layer
#88
Network Address Translation: Advantages
 No need to be allocated range of addresses
from ISP: - just one public IP address is
used for all devices
16-bit port-number field allows 60,000
simultaneous connections with a single LAN-side
address !
 can change ISP without changing addresses of
devices in local network
 can change addresses of devices in local network
without notifying outside world

 Devices inside local net not explicitly
addressable, visible by outside world (a
security plus)
Lecture 6: Network Layer
#89
NAT: Network Address Translation
 If both hosts are behind NAT, they will
have difficulty establishing connection
 NAT is controversial:
 routers
should process up to only 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
having more addresses --- IPv6 !
Lecture 6: Network Layer
#90
IP addressing: the last word...
Q: How does an ISP get block of addresses?
A: ICANN: Internet Corporation for Assigned
Names and Numbers
 allocates addresses
 manages DNS
 assigns domain names, resolves disputes
Lecture 6: Network Layer
#91
Getting a datagram from source to dest.
routing table in A
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
IP datagram:
misc source dest
fields IP addr IP addr
data
A
 datagram remains
unchanged, as it travels
source to destination
 addr fields of interest
here
 mainly dest. IP addr
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.9
223.1.3.27
223.1.1.3
223.1.3.1
223.1.2.2
E
223.1.3.2
Lecture 6: Network Layer
#92
Getting a datagram from source to dest.
misc
data
fields 223.1.1.1 223.1.1.3
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
Starting at A, given IP
datagram addressed to B:
 look up net. address of B
 find B is on same net. as A
A
223.1.1.1
223.1.2.1
 link layer will send datagram
directly to B inside link-layer
frame
 B and A are directly
connected
223.1.1.4
223.1.1.4
1
2
2
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.3
223.1.3.1
223.1.2.2
E
223.1.3.2
Lecture 6: Network Layer
#93
Getting a datagram from source to dest.
misc
data
fields 223.1.1.1 223.1.2.2
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
Starting at A, dest. E:
 look up network address of E
 E on different network
A, E not directly attached
routing table: next hop
router to E is 223.1.1.4
link layer sends datagram to
router 223.1.1.4 inside linklayer frame
datagram arrives at 223.1.1.4
continued…..
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.9
223.1.3.27
223.1.1.3
223.1.3.1
223.1.2.2
E
223.1.3.2
Lecture 6: Network Layer
#94
Getting a datagram from source to dest.
misc
data
fields 223.1.1.1 223.1.2.2
Arriving at 223.1.4,
destined for 223.1.2.2
 look up network address of E
 E on same network as router’s
interface 223.1.2.9
 router, E directly attached
 link layer sends datagram to
223.1.2.2 inside link-layer
frame via interface 223.1.2.9
 datagram arrives at
223.1.2.2!!! (hooray!)
Dest.
next
network router Nhops interface
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.9
223.1.3.27
223.1.1.3
223.1.3.1
223.1.2.2
E
223.1.3.2
Lecture 6: Network Layer
#95
IP datagram format
IP protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
upper layer protocol
to deliver payload to
32 bits
head. type of
length
len service
fragment
16-bit identifier flgs
offset
time to upper
Internet
layer
live
checksum
ver
total datagram
length (bytes)
for
fragmentation/
reassembly
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
Lecture 6: Network Layer
#96
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
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
Network Layer
4-97
IP Fragmentation and Reassembly
Example
 4000 byte
datagram
 MTU = 1500 bytes
1480 bytes in
data field
offset =
1480/8
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
=185
length ID fragflag offset
=1040 =x
=0
=370
Network Layer
4-98
Routing in the Internet
 The Global Internet consists of Autonomous Systems
(AS) interconnected with each other:



Stub AS: small corporation
Multihomed AS: large corporation (no transit)
Transit AS: provider
 Two-level routing:
 Intra-AS: administrator is responsible for choice
 Inter-AS: unique standard
Lecture 6: Network Layer
#99
Internet AS Hierarchy
Inter-AS border (exterior gateway) routers
Intra-AS interior (gateway) routers
Lecture 6: Network Layer #100
Intra-AS Routing
 Also known as Interior Gateway Protocols (IGP)
 Most common IGPs:

RIP: Routing Information Protocol

OSPF: Open Shortest Path First

IGRP: Interior Gateway Routing Protocol (Cisco
propr.)
Lecture 6: Network Layer #101
RIP ( Routing Information Protocol)
 Distance vector algorithm
 Included in BSD-UNIX Distribution in 1982
 Distance metric: # of hops (max = 15 hops)
 why?
 Distance vectors: exchanged every 30 sec via
Response Message (also called advertisement)
 Each advertisement: route to up to 25 destination
nets
Lecture 6: Network Layer #102
RIP (Routing Information Protocol)
z
w
A
x
D
y
B
C
Destination Network
w
y
z
x
….
Next Router
Num. of hops to dest.
….
....
A
B
B
--
2
2
7
1
Routing table in D
Lecture 6: Network Layer #103
RIP: Link Failure and Recovery
If no advertisement heard after 180 sec -->
neighbor/link declared dead
 routes via neighbor invalidated
 new advertisements sent to neighbors
 neighbors in turn send out new advertisements (if
tables changed)
 link failure info quickly propagates to entire net
 poison reverse used to prevent ping-pong loops
(infinite distance = 16 hops)
Lecture 6: Network Layer #104
OSPF (Open Shortest Path First)
 “open”: publicly available
 Uses Link State algorithm
 LS packet dissemination
 Topology map at each node
 Route computation using Dijkstra’s algorithm
 OSPF advertisement carries one entry per neighbor
router
 Advertisements disseminated to entire AS (via
flooding)
Lecture 6: Network Layer #105
OSPF “advanced” features (not in RIP)
 Security: all OSPF messages authenticated (to
prevent malicious intrusion); TCP connections used
 Multiple same-cost paths allowed

only one path in RIP
 For each link, multiple cost metrics for different
ToS (eg, satellite link cost set “low” for best effort;
high for real time)
 Integrated uni- and multicast support:

Multicast OSPF (MOSPF) uses same topology data base as
OSPF
 Hierarchical OSPF in large domains.
Lecture 6: Network Layer #106
Hierarchical OSPF
Lecture 6: Network Layer #107
Hierarchical OSPF
 Two-level hierarchy: local area, backbone.
Link-state advertisements only in area
 each nodes has detailed area topology; only know
direction (shortest path) to nets in other areas.
 Area border routers: “summarize” distances to nets
in own area, advertise to other Area Border routers.
 Backbone routers: run OSPF routing limited to
backbone.
 Boundary routers: connect to other ASs.

Lecture 6: Network Layer #108
IGRP (Interior Gateway Routing Protocol)
 CISCO proprietary; successor of RIP (mid 80s)
 Distance Vector, like RIP
 several cost metrics (delay, bandwidth, reliability,
load etc)
 uses TCP to exchange routing updates
 Loop-free routing via Distributed Updating Alg.
(DUAL) based on diffused computation
Lecture 6: Network Layer #109
Inter-AS routing
Lecture 6: Network Layer
#110
Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol): the de facto
standard
 Path Vector protocol:
 similar to Distance Vector protocol
 each Border Gateway broadcast to neighbors
(peers) entire path (I.e, sequence of ASs) to
destination
 E.g., Gateway X may send its path to dest. Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
Lecture 6: Network Layer
#111
Internet inter-AS routing: BGP
Suppose: gateway X send its path to peer gateway W
 W may or may not select path offered by X
 cost, policy (don’t route via competitors AS), loop
prevention reasons.
 If W selects path advertised by X, then:
Path (W,Z) = W, Path (X,Z)
 Note: X can control incoming traffic by controlling its
route advertisements to peers:
 e.g., don’t want to route traffic to Z -> don’t
advertise any routes to Z
Lecture 6: Network Layer
#112
Internet inter-AS routing: BGP
 BGP messages exchanged using TCP.
 BGP messages:
OPEN: opens TCP connection to peer and
authenticates sender
 UPDATE: advertises new path (or withdraws old)
 KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
 NOTIFICATION: reports errors in previous msg;
also used to close connection

Lecture 6: Network Layer
#113
Why different Intra- and Inter-AS routing ?
Policy:
 Inter-AS: admin wants control over how its traffic
routed, who routes through its net.
 Intra-AS: single admin, so no policy decisions needed
Scale:
 hierarchical routing saves table size, reduced update
traffic
Performance:
 Intra-AS: can focus on performance
 Inter-AS: policy may dominate over performance
Lecture 6: Network Layer
#114
Extra
Lecture 6: Network Layer
#115
ICMP: Internet Control Message Protocol
 used by hosts & routers to
communicate 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
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
Network Layer 4-116
Traceroute and ICMP
 Source sends series of
UDP segments to dest



First has TTL =1
Second has TTL=2, etc.
Unlikely port number
 When nth datagram arrives
to nth router:



Router discards datagram
And sends to source an
ICMP message (type 11,
code 0)
Message includes name of
router& IP address
 When ICMP message
arrives, source calculates
RTT
 Traceroute does this 3
times
Stopping criterion
 UDP segment eventually
arrives at destination host
 Destination returns ICMP
“host unreachable” packet
(type 3, code 3)
 When source gets this
ICMP, stops.
Network Layer 4-117
IPv6
 Initial motivation: 32-bit address space soon
to be completely allocated.
 Additional motivation:
header format helps speed processing/forwarding
 header changes to facilitate QoS
IPv6 datagram format:
 fixed-length 40 byte header
 no fragmentation allowed

Network Layer 4-118
IPv6 Header (Cont)
Priority: identify priority among datagrams in flow
Flow Label: identify datagrams in same “flow.”
(concept of“flow” not well defined).
Next header: identify upper layer protocol for data
Network Layer 4-119
Other Changes from IPv4
 Checksum: removed entirely to reduce
processing time at each hop
 Options: allowed, but outside of header,
indicated by “Next Header” field
 ICMPv6: new version of ICMP
additional message types, e.g. “Packet Too Big”
 multicast group management functions

Network Layer 4-120
Transition From IPv4 To IPv6
 Not all routers can be upgraded simultaneous
no “flag days”
 How will the network operate with mixed IPv4 and
IPv6 routers?

 Tunneling: IPv6 carried as payload in IPv4
datagram among IPv4 routers
Network Layer 4-121
Tunneling
Logical view:
Physical view:
A
B
IPv6
IPv6
A
B
C
IPv6
IPv6
IPv4
Flow: X
Src: A
Dest: F
data
A-to-B:
IPv6
E
F
IPv6
IPv6
D
E
F
IPv4
IPv6
IPv6
tunnel
Src:B
Dest: E
Src:B
Dest: E
Flow: X
Src: A
Dest: F
Flow: X
Src: A
Dest: F
data
data
B-to-C:
IPv6 inside
IPv4
B-to-C:
IPv6 inside
IPv4
Flow: X
Src: A
Dest: F
data
E-to-F:
IPv6
Network Layer 4-122