Chapter 4

Network Layer

A note on the use of these ppt slides: Computer

We’re making these slides freely available to all (faculty, students, readers).
They’re in PowerPoint form so you see the animations; and can add, modify, Networking: A
and delete slides (including this one) and slide content to suit your needs.
They obviously represent a lot of work on our part. In return for use, we only Top Down
ask the following:
 If you use these slides (e.g., in a class) that you mention their source Approach
(after all, we’d like people to use our book!)
 If you post any slides on a www site, that you note that they are adapted
6th edition
from (or perhaps identical to) our slides, and note our copyright of this Jim Kurose, Keith Ross
material. Addison-Wesley
Thanks and enjoy! JFK/KWR March 2012
All material copyright 1996-2013
J.F Kurose and K.W. Ross, All Rights Reserved

Network Layer 4-1

Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
  RIP
datagram format
  OSPF
IPv4 addressing
  BGP
ICMP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-2

Network layer
application
 transport segment from transport
network

sending to receiving host data link

physical
network network

 on sending side network

data link
data link
physical
data link
physical

encapsulates segments physical network

data link
network
data link

into datagrams or physical physical

Packets network
data link
network
data link
physical
on receiving side, delivers
physical
 network
data link

segments to transport layer

physical
application
network transport
 network layer protocols in network
data link
physical
network
data link
network
data link

every host, router data link

physical
physical physical

Network Layer 4-3

Two key network-layer functions
 forwarding: move analogy:
packets from router’s
input to appropriate  routing: process of
router output(involves one planning trip from source
Router only) to dest
 routing: determine entire  forwarding: process of
route taken by packets getting through single
from source to dest. interchange
(involves all the routers
in network)
 routing algorithms
calculate these paths
Network Layer 4-4
 Interplay between routing and forwarding

routing algorithm routing algorithm determines

end-end-path through network

local forwarding table forwarding table determines

header output link local forwarding at this router
value0100 3
0101 2
0111 2
1001 1

value in arriving
packet’s header
0111 1

3 2

Network Layer 4-5

Connection, connection-less service
 datagram network provides network-layer
connectionless service
 virtual-circuit network provides network-layer
connection service
 analogous to TCP/UDP connecton-oriented /
connectionless transport-layer services, but:
 service: host-to-host(vs Process to process)
 implementation: in network core(vs in hosts)

Network Layer 4-6

Virtual circuits
“source-to-dest path behaves much like telephone
circuit”

 call setup, teardown for each call before data can flow
 each packet carries VC identifier (not destination host
address)
 every router on source-dest path maintains “state” for
each passing connection

Network Layer 4-7

VC implementation
a VC consists of:
1. path from source to destination
2. VC numbers, one number for each link along path
3. entries in forwarding tables in routers along path
 packet belonging to VC carries VC number
(rather than dest address)
 VC number will be changed :
 Each router in the path must replace the VC number
of each packet with a new VC number.
 new VC number comes from forwarding table

Network Layer 4-8

VC forwarding table
R1 R2
12 22 32

1 3 1 2
2 42 3
VC number
interface
forwarding table in number
R1 router:
Incoming interface Incoming VC # Outgoing interface Outgoing VC #
1 12 3 22
2 63 1 18
3 7 2 17
1 97 3 87
… … … …

VC routers maintain connection state

information!
Network Layer 4-9
Virtual circuits: signaling protocols
 used to setup, maintain teardown VC
 used in ATM, frame-relay, X.25
 not used in today’s Internet

application application
5. data flow begins 6. receive data
transport transport
network 4. call connected 3. accept call
1. initiate call network
data link 2. incoming call
data link
physical physical

Network Layer 4-10

Datagram networks
 no call setup at network layer
 routers: no state about end-to-end connections
 no network-level concept of “connection”
 packets forwarded using destination host address

application application
transport transport
network 1. send datagrams 2. receive datagrams network
data link data link
physical physical

Network Layer 4-11

Datagram forwarding table
4 billion IP addresses, so
routing algorithm rather than list individual
destination address
local forwarding table
list range of addresses
dest address output (aggregate table entries)
address-range 1 3 link
address-range 2 2
address-range 3 2
address-range 4 1

IP destination address in
arriving packet’s header
1
3 2

Network Layer 4-12

Datagram forwarding table
Destination Address Range Link Interface

11001000 00010111 00010000 00000000

through 0
11001000 00010111 00010111 11111111

11001000 00010111 00011000 00000000

through 1
11001000 00010111 00011000 11111111

11001000 00010111 00011000 00000000

through 2
11001000 00010111 00011111 11111111

otherwise 3

Network Layer 4-13

Longest prefix matching
longest prefix matching
when looking for forwarding table entry for given
destination address, use longest address prefix that
matches destination address.

Destination Address Range Link interface

11001000 00010111 00010*** ********* 0
11001000 00010111 00011000 ********* 1
11001000 00010111 00011*** ********* 2
otherwise / default route 3

examples:
DA: 11001000 00010111 00010110 10100001 which interface?
DA: 11001000 00010111 00011000 10101010 which interface?
Network Layer 4-14
Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
  RIP
datagram format
  OSPF
IPv4 addressing
  BGP
ICMP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-15

 IPV4 datagram format
IP protocol version 32 bits
number total datagram
header length length (bytes)
ver head. type of length
(bytes) len service
“type” of data fragment for
16-bit identifier flag fragmentation/
offset
max number time to upper header reassembly
remaining hops live layer P checksum
(decremented at
32 bit source IP address
each router)
32 bit destination IP address
upper layer protocol
to deliver payload to options (if any) e.g. timestamp,
record route
how much overhead? data taken, specify
 20 bytes of TCP
(variable length, list of routers
 20 bytes of IP
typically a TCP to visit.
 = 40 bytes + app
or UDP segment)
layer overhead

Network Layer 4-16

 IP fragmentation, reassembly
 The maximum amount of
data a link-layer frame can
carry is MTU fragmentation:

…
 different link types, in: one large datagram
different MTUs out: 3 smaller datagrams

 large IP datagram divided

(“fragmented”) within net
 one datagram becomes reassembly
several datagrams
 “reassembled” only at
final destination …
 IP header bits used to
identify, order related
fragments
Network Layer 4-17
 IP fragmentation, reassembly
length ID fragflag offset
example: =4000 =x =0 =0
 4000 byte datagram
one large datagram becomes
 MTU = 1500 bytes several smaller datagrams

1480 bytes in length ID fragflag offset

data field =1500 =x =1 =0

offset = length ID fragflag offset

1480/8 =1500 =x =1 =185

length ID fragflag offset

=1040 =x =0 =370

Network Layer 4-18

IP fragmentation, reassembly Rules
• Use ID, flag and fragmentation offset in packet
header
• Same fragments will contain same ID
• Last fragment has flag = 0, all other fragment has
flag = 1
• To understand if any segment is missing and also
to fit the correct segment in correct position we
need fragmentation offset(F.O.)
• F.O. should be specified as 8 byte chunk
• All the fragments except the last one will have
original payload equal to multiple of 8 bytes.

Network Layer 4-19

Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
  RIP
datagram format
  OSPF
IPv4 addressing
  BGP
ICMP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-20

IP addressing: introduction
223.1.1.1
 IP address: 32-bit 223.1.2.1
identifier for host, router
interface 223.1.1.2
223.1.1.4 223.1.2.9
 interface: connection
between host/router and 223.1.3.27
physical link 223.1.1.3
223.1.2.2
 router’s typically have
multiple interfaces
 host typically has one or
223.1.3.1 223.1.3.2
two interfaces (e.g., wired
Ethernet, wireless 802.11)
 IP addresses associated
with each interface 223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 1 1

Network Layer 4-21

IP addressing: introduction
223.1.1.1
Q: how are interfaces 223.1.2.1
actually connected?
A: we’ll learn about 223.1.1.2
223.1.1.4 223.1.2.9

that in chapter 5, 6.
223.1.3.27
223.1.1.3
223.1.2.2

A: wired Ethernet interfaces

connected by Ethernet switches
223.1.3.1 223.1.3.2

For now: don’t need to worry

about how one interface is
connected to another (with no
A: wireless WiFi interfaces
intervening router)
connected by WiFi base station

Network Layer 4-22

IP addresses: how to get one?
Q: How does a host get IP address?

 hard-coded by system admin in a file

 Windows: control-panel->network->configuration-
>tcp/ip->properties
 UNIX: /etc/rc.config
 DHCP: Dynamic Host Configuration Protocol:
dynamically get address from as server
 “plug-and-play”

Network Layer 4-23

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/“on”)
 support for mobile users who want to join network (more
shortly)
DHCP overview:
 host broadcasts “DHCP discover” msg [optional]
 DHCP server responds with “DHCP offer” msg [optional]
 host requests IP address: “DHCP request” msg
 DHCP server sends address: “DHCP ack” msg

Network Layer 4-24

DHCP client-server scenario

DHCP
223.1.1.0/24
server
223.1.1.1 223.1.2.1

223.1.1.2 arriving DHCP

223.1.1.4 223.1.2.9
client needs
address in this
223.1.3.27
223.1.2.2 network
223.1.1.3

223.1.2.0/24

223.1.3.1 223.1.3.2

223.1.3.0/24

Network Layer 4-25

DHCP client-server scenario
DHCP server: 223.1.2.5 DHCP discover arriving
client
src : 0.0.0.0, 68
Broadcast: is there a
dest.: 255.255.255.255,67
DHCPyiaddr:
server0.0.0.0
out there?
transaction ID: 654

DHCP offer
src: 223.1.2.5, 67
Broadcast: I’m a DHCP
dest: 255.255.255.255, 68
server! Here’s an IP
yiaddrr: 223.1.2.4
transaction
address youID:can
654use
lifetime: 3600 secs
DHCP request
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
Broadcast: OK. I’ll take
yiaddrr: 223.1.2.4
that IP address!
transaction ID: 655
lifetime: 3600 secs

DHCP ACK
src: 223.1.2.5, 67
Broadcast: OK. You’ve
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
got that IPID:
transaction address!
655
lifetime: 3600 secs
Network Layer 4-26
DHCP: more than IP addresses
DHCP can return more than just allocated IP address
on subnet:
 address of first-hop router for client
 name and IP address of DNS sever
 network mask (indicating network versus host portion
of address)

Network Layer 4-27

 NAT: network address translation
rest of local network
Internet (e.g., home network)
10.0.0/24 10.0.0.1

10.0.0.4
10.0.0.2
138.76.29.7

10.0.0.3

all datagrams leaving local

network have same single datagrams with source or
source NAT IP address: destination in this network
138.76.29.7,different source have 10.0.0/24 address for
port numbers source, destination (as usual)

Network Layer 4-28

NAT: network address translation
motivation: local network uses just one IP address as
far as outside world is concerned:
 range of addresses not needed from ISP: just one IP
address for all devices
 can change addresses of devices in local network
without notifying outside world
 can change ISP without changing addresses of
devices in local network
 devices inside local net not explicitly addressable,
visible by outside world (a security plus)

Network Layer 4-29

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

Network Layer 4-30

 NAT: network address translation
NAT translation table 1: host 10.0.0.1
2: NAT router WAN side addr LAN side addr
changes datagram sends datagram to
source addr from 138.76.29.7, 5001 10.0.0.1, 3345 128.119.40.186, 80
10.0.0.1, 3345 to …… ……
138.76.29.7, 5001,
updates table S: 10.0.0.1, 3345
D: 128.119.40.186, 80
10.0.0.1
1
S: 138.76.29.7, 5001
2 D: 128.119.40.186, 80 10.0.0.4
10.0.0.2
138.76.29.7 S: 128.119.40.186, 80
D: 10.0.0.1, 3345
4
S: 128.119.40.186, 80
D: 138.76.29.7, 5001 3 10.0.0.3
4: NAT router
3: reply arrives changes datagram
dest. address: dest addr from
138.76.29.7, 5001 138.76.29.7, 5001 to 10.0.0.1, 3345

Network Layer 4-31

NAT: network address translation
 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
 Port numbers should only differentiate
processes not hosts
 violates end-to-end argument
• e.g., P2P applications
 address shortage should instead be solved by
IPv6
Network Layer 4-32
NAT traversal problem
 client wants to connect to
private server with address
10.0.0.1 client
10.0.0.1
 server address 10.0.0.1 local to
LAN (client can’t use it as ?
destination addr) 10.0.0.4
 only one externally visible NATed
address: 138.76.29.7 138.76.29.7 NAT
 solution1: statically configure router
the Router’s NAT table to
forward incoming connection
requests at given port to server
 e.g., (138.76.29.7, port 2500)
always forwarded to 10.0.0.1 port
80

Network Layer 4-33

 NAT traversal problem
 solution 2 : relaying (used in Skype)
 NATed client establishes connection to relay Skype’s
relay server
 external client connects to relay server
 relay bridges packets between two connections

2. connection to
relay initiated 1. connection to 10.0.0.1
by client relay initiated
by NATed host
3. relaying
client established
138.76.29.7 NAT
router

Network Layer 4-34

Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
  RIP
datagram format
  OSPF
IPv4 addressing
  BGP
ICMP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-35

Graph abstraction
5
3
v w 5
2
u 2 1 z
3
1 2
x 1
y
graph: G = (N,E)

N = set of routers = { u, v, w, x, y, z }

E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

aside: graph abstraction is useful in other network contexts, e.g.,

P2P, where N is set of peers and E is set of TCP connections

Network Layer 4-36

Graph abstraction: costs
5
c(x,x’) = cost of link (x,x’)
3 e.g., c(w,z) = 5
v w 5
2
u cost could always be 1, or
2
3
1 z inversely related to bandwidth,
1 2 or directly related to
x 1
y
congestion

cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

key question: what is the least-cost path between u and z ?

Goal of routing algorithm: Try to find that least cost
path
Network Layer 4-37
Routing algorithm classification
Q: global or decentralized Q: static or dynamic?
information?
static:
Global(Centralized):  routes change slowly over
 all routers have complete time
topology, link cost info of dynamic:
entire network  routes change more
 “link state” algorithms
quickly
decentralized:  periodic update
 router knows only the costs
 in response to link cost
of its own links changes
 iterative process of
computation, exchange of
info with neighbors
 “distance vector” algorithms

Network Layer 4-38

Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
  RIP
datagram format
  OSPF
IPv4 addressing
  BGP
ICMP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-39

A Link-State Routing Algorithm
Dijkstra’s algorithm notation:
 net topology, link costs  c(x,y): link cost from
known to all nodes node x to y; = ∞ if not
 accomplished via “link state direct neighbors
broadcast”  D(v): current value of
 all nodes have same info cost of path from source
 computes least cost paths to dest. v
from one node (‘source”)  p(v): predecessor node
to all other nodes along path from source
 gives forwarding table for to v
that node  N': set of nodes whose
 iterative: after k least cost path definitively
iterations, know least known
cost path to k dest.’s
Network Layer 4-40
Dijkstra’s Algorithm
1 Initialization:
2 N' = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find any node 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'

Network Layer 4-41

Dijkstra’s algorithm: example
D(v) D(w) D(x) D(y) D(z)
Step N' p(v) p(w) p(x) p(y) p(z)
0 u 7,u 3,u 5,u ∞ ∞
1 uw 6,w 5,u 11,w ∞
2 uwx 6,w 11,w 14,x
3 uwxv 10,v 14,x
4 uwxvy 12,y
5 uwxvyz x
9

notes: 5 7
4
 construct shortest path tree by
tracing predecessor nodes 8
 ties can exist (can be broken u
3 w y z
arbitrarily) 2
3
7 4
v
Network Layer 4-42
 Dijkstra’s algorithm: another example
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz

v 3 w
2 5
u 2 1 z
3
1 2
x 1
y

Network Layer 4-43

Dijkstra’s algorithm: example (2)
resulting shortest-path tree from u:

v w
u z
x y

resulting forwarding table in u:

destination link
v (u,v)
x (u,x)
y (u,x)
w (u,x)
z (u,x)
Network Layer 4-44
Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
  RIP
datagram format
  OSPF
IPv4 addressing
  BGP
ICMP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-45

Distance vector algorithm
Bellman-Ford equation (dynamic programming)

let
dx(y) := cost of least-cost path from x to y
then
dx(y) = min v{c(x,v) + dv(y) }
cost from neighbor v to destination
cost to neighbor v

min taken over all neighbors v of x

Network Layer 4-46
Bellman-Ford example
5
3
clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
v w 5
2
u 2 1 z B-F equation says:
3
1 2 du(z) = min { c(u,v) + dv(z),
x 1
y
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
Node(in this case x) achieving minimum is next
hop in shortest path, used in forwarding table
Network Layer 4-47
Distance vector algorithm
key idea:
 from time-to-time, each node sends its own
distance vector estimate to neighbors
 when a node x receives new DV estimate from
neighbor, it updates its own DV using B-F
equation:
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N

Network Layer 4-48

Distance vector algorithm
iterative each node:
asynchronous: each local
iteration caused by: wait for (change in local link
 local link cost change cost or msg from neighbor)
distributed:
 each node notifies
neighbors only when its recompute estimates
DV changes
 neighbors then notify
their neighbors if if DV to any dest has
necessary changed, notify neighbors

Network Layer 4-49

 Dx(z) = min{c(x,y) +
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to cost to
table x y z x y z
x 0 2 7 x 0 2 3

from
from

y ∞∞ ∞ y 2 0 1
z ∞∞ ∞ z 7 1 0

node y cost to
table x y z y
2 1
x ∞ ∞ ∞
x z
from

y 2 0 1 7
z ∞∞ ∞

node z cost to
table x y z
x ∞∞ ∞
from

y ∞∞ ∞
z 7 1 0
time
Network Layer 4-50
 Dx(z) = min{c(x,y) +
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to cost to cost to
table x y z x y z x y z
x 0 2 7 x 0 2 3 x 0 2 3

from
from

y ∞∞ ∞ y 2 0 1 y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0
node y cost to cost to cost to
table x y z x y z x y z y
2 1
x ∞ ∞ ∞ x 0 2 7 x 0 2 3 x z
from

y 2 0 1 y 2 0 1 7
from

y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0

node z cost to cost to cost to

table x y z x y z x y z

x ∞∞ ∞ x 0 2 7 x 0 2 3
from

from

y 2 0 1 y 2 0 1
from

y ∞∞ ∞
z 7 1 0 z 3 1 0 z 3 1 0
time
Network Layer 4-51
Comparison of LS and DV algorithms
message complexity robustness:
 LS: with n nodes, E links, O(nE) LS:
msgs sent  node can advertise incorrect
 DV: exchange between neighbors link cost
only  each node computes its own
table
speed of convergence
DV:
 LS: O(n2) algorithm requires
O(nE) msgs  DV node can advertise
incorrect path cost
 DV: convergence time varies
 each node’s table used by
 may be routing loops others
 count-to-infinity problem
• error propagate through
network

Network Layer 4-52

Hierarchical routing
our routing study thus far - idealization
 all routers identical
 network “ flat”

… not true in practice

scale: with 600 million administrative autonomy

destinations:  internet = network of
 can’t store all dest’s in networks
routing tables!  each network admin may
 routing table exchange want to control routing in its
would swamp links! own network

Network Layer 4-53

Hierarchical routing
 aggregate routers into gateway router:
regions, “ autonomous  at “ edge” of its own AS
systems” (AS)  has link to router in another
 routers in same AS run AS
same routing protocol
 “ intra-AS” routing
protocol
 routers in different AS
can run different intra-
AS routing protocol

Network Layer 4-54

Interconnected ASes

3c
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b AS1
1d  forwarding table
configured by both intra-
and inter-AS routing
Intra-AS Inter-AS algorithm
Routing Routing
algorithm algorithm  intra-AS sets entries
Forwarding
for internal dests
table  inter-AS & intra-AS
sets entries for external
dests
Network Layer 4-55
Intra-AS Routing
 also known as interior gateway protocols (IGP)
 most common intra-AS routing protocols:
 RIP: Routing Information Protocol
 OSPF: Open Shortest Path First

Network Layer 4-56

 RIP ( Routing Information Protocol)

 Uses distance vector algorithm

 distance metric: # hops (max = 15 hops), each link has cost 1
 DVs exchanged with neighbors every 30 sec in response message (aka advertisement)
 each advertisement: list of up to 25 destination subnets (in IP addressing sense)

from router A to destination subnets:

u v subnet hops
w u 1
A B
v 2
w 2
x x 3
z C D y 3
y z 2
Network Layer 4-57
RIP: example

z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
z B 7
x -- 1
…. …. ....
Network Layer 4-58
RIP: example
A-to-D advertisement
dest next hops
w - 1
x - 1
z C 4
…. … ... z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
A 5
z B 7
x -- 1
…. …. ....
Network Layer 4-59
 Inter-AS tasks
 suppose router in AS1 AS1 must:
receives datagram 1. learn which dests are
destined outside of AS1: reachable through AS2,
 router should forward which through AS3
packet to gateway 2. propagate this
router, but which one? reachability info to all
routers in AS1
job of inter-AS routing!

3c
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer 4-60

Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol): the de facto
inter-domain routing protocol
 “ glue that holds the Internet together”

 BGP provides each AS a means to:

 eBGP: obtain subnet reachability information from
neighboring ASs.
 iBGP: propagate reachability information to all AS-
internal routers.
 determine “ good” routes to other networks based on
reachability information and policy.

Network Layer 4-61

 BGP basics
 BGP session: two BGP routers (“ peers” ) exchange BGP
messages:
 advertising paths to different destination network prefixes (“ path vector”
protocol)
 exchanged over semi-permanent TCP connections

 when AS3 advertises a prefix to AS1:

 AS3 promises it will forward datagrams towards that prefix
 AS3 can aggregate prefixes in its advertisement

3c
BGP
3a message
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer 4-62

BGP basics: distributing path information
 using eBGP session between 3a and 1c, AS3 sends prefix
reachability info to AS1.
 1c can then use iBGP do distribute new prefix info to all routers in AS1
 1b can then re-advertise new reachability info to AS2 over 1b-to-2a
eBGP session
 when router learns of new prefix, it creates entry for prefix in
its forwarding table.

eBGP session
3a iBGP session
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer 4-63