Transcript Network Layer

CMPT 371
Data Communications
and Networking
Chapter 4
Network Layer
Network Layer
4-1
Chapter 4: Network Layer
Chapter goals:
 understand principles
behind network layer
services:




routing (path selection)
dealing with scale
how a router works
advanced topics: IPv6,
mobility
 instantiation and
implementation in the
Internet
Overview:
 network layer services
 routing principles: path
selection
 IP overview
 Internet routing
protocols


intra-domain
inter-domain
 what’s inside a router?
 IPv6
 mobility
Network Layer
4-2
Chapter 4 roadmap
4.1 Introduction and Network Service Models
4.2 Routing Principles
4.3 The Internet (IP) Protocol
4.4 Routing in the Internet
4.5 IPv6
4.6 Mobility (Section 6.5/6.6 in textbook)
Network Layer
4-3
Network layer functions
 deliver packets from sending
to receiving hosts
 network layer protocols in
every host, router
Two important functions:
 path determination: route
taken by packets from source
to dest. Routing algorithms
 forwarding: move packets
from router’s input to
appropriate router output
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
Network Layer
4-4
Routing and Forwarding
 routing: determine
route taken by
packets from source
to dest.

routing algorithms
 forwarding: move
packets from
router’s input to
appropriate router
output
analogy:


routing: process of
planning trip from source
to dest
forwarding: process of
getting through single
interchange
Network Layer
4-5
Interplay between routing and forwarding
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
Network Layer
4-6
Chapter 4 roadmap
4.1 Introduction and Network Service Models
4.2 Routing Principles
Link state routing
 Distance vector routing

4.3
4.4
4.5
4.6
The Internet (IP) Protocol
Routing in the Internet
IPv6
Mobility (Section 6.5/6.6 in textbook)
Network Layer
4-7
Routing
Routing protocol
5
Goal: determine a “good” path
(sequence of routers) thru
network from source to dest.
Graph abstraction for
routing algorithms:
 graph nodes are
routers
 graph edges are
physical links

link cost: delay, $ cost,
or congestion level
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
 “good” path:
 typically means minimum
cost path
 other def’s possible
Network Layer
4-8
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
Network Layer
4-9
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 forwarding table
for that node
 iterative: after k
iterations, know least cost
path to k dest.’s
Notation:
 c(x,y): link cost from node
x to y; = ∞ 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
 N': set of nodes whose
least cost path definitively
known
Network Layer 4-10
Dijsktra’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 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-11
Dijkstra’s algorithm: example
Step
0
1
2
3
4
5
N'
u
ux
uxy
uxyv
uxyvw
uxyvwz
D(v),p(v) D(w),p(w)
2,u
5,u
2,u
4,x
2,u
3,y
3,y
D(x),p(x)
1,u
D(y),p(y)
∞
2,x
D(z),p(z)
∞
∞
4,y
4,y
4,y
5
2
u
v
2
1
x
3
w
3
1
5
z
1
y
2
Network Layer 4-12
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
x
(u,v)
(u,x)
y
(u,x)
w
(u,x)
z
(u,x)
Network Layer 4-13
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)
Network Layer 4-14
Dijkstra’s algorithm, more discussion
 Why the algorithm is correct ?
 Is this algorithm always correct ?
 Shortest – definition ?
1
B
-3
A
1
C
Network Layer 4-15
Distance Vector Algorithm
Bellman-Ford Equation (dynamic programming)
Define
dx(y) := cost of least-cost path from x to y
Then cost to neighbor v
cost from neighbor v to destination y
dx(y) = min
{c(x,v) + dv(y) }
v
where min is taken over all neighbors v of x
Network Layer 4-16
Bellman-Ford example
5
2
u
v
2
1
x
3
w
3
1
5
z
1
y
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
2
B-F equation says:
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
Node that achieves minimum is next
hop in shortest path ➜ forwarding table
Network Layer 4-17
Distance Vector Algorithm
 Dx(y) = estimate of least cost from x to y
 Node x knows cost to each neighbor v:
c(x,v)
 Node x maintains distance vector Dx =
[Dx(y): y є N ]
 Node x also maintains its neighbors’
distance vectors
 For
each neighbor v, x maintains
Dv = [Dv(y): y є N ]
Network Layer 4-18
Distance vector algorithm (4)
Basic idea:
 Each node periodically 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
 Under minor, natural conditions, the estimate
Dx(y) converge to the actual least cost dx(y)
Network Layer 4-19
Distance Vector Algorithm (5)
Iterative, asynchronous:
each local iteration caused
by:
 local link cost change
 DV update message from
neighbor
Distributed:
 each node notifies
neighbors only when its DV
changes

neighbors then notify
their neighbors if
necessary
Each node:
wait for (change in local link
cost or msg from neighbor)
recompute estimates
if DV to any dest has
changed, notify neighbors
Network Layer 4-20
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 7 1 0
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
from
from
x
x ∞∞ ∞
y ∞∞ ∞
z 71 0
time
2
y
7
1
z
Network Layer 4-21
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
x ∞∞ ∞
y ∞∞ ∞
z 71 0
from
from
from
from
x 0 2 7
y 2 0 1
z 7 1 0
cost to
x y z
x 0 2 7
y 2 0 1
z 3 1 0
x 0 2 3
y 2 0 1
z 3 1 0
cost to
x y z
x 0 2 3
y 2 0 1
z 3 1 0
x
2
y
7
1
z
cost to
x y z
from
from
from
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
x 0 2 3
y 2 0 1
z 7 1 0
cost to
x y z
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 3 1 0
time
Network Layer 4-22
Distance Vector: link cost changes
Link cost changes:
 node detects local link cost change
 updates routing info, recalculates
distance vector
 if DV changes, notify neighbors
“good
news
travels
fast”
1
x
4
y
50
1
z
At time t0, y detects the link-cost change, updates its DV,
and informs its neighbors.
At time t1, z receives the update from y and updates its table.
It computes a new least cost to x and sends its neighbors its DV.
At time t2, y receives z’s update and updates its distance table.
y’s least costs do not change and hence y does not send any
message to z.
Network Layer 4-23
Distance Vector: link cost changes
Link cost changes:
 good news travels fast
 bad news travels slow -
“count to infinity” problem!
3
A
1
1
B
1
C
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?
Network Layer 4-24
Chapter 4 roadmap
4.1 Introduction and Network Service Models
4.2 Routing Algorithms
4.3 The Internet (IP) Protocol






4.4.1 IPv4 addressing
4.4.2 Moving a datagram from source to destination
4.4.3 Datagram format
4.4.4 DHCP: Dynamic Host Configuration Protocol
4.4.5 ICMP: Internet Control Message Protocol
4.4.6 NAT: Network Address Translation
4.4 Routing in the Internet
4.5 IPv6
4.6 Mobility (Section 6.5/6.6 in textbook)
Network Layer 4-25
The Internet Network layer
Host, router network layer functions:
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
Network Layer 4-26
IP Addressing: introduction
 IP (v4) 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 each
interface
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
1
Network Layer 4-27
IP Addr: Client Settings
Network Layer 4-28
Internet: Network of networks
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
A: wired Ethernet interfaces
connected by Ethernet switches
223.1.3.1
For now: don’t need to worry
about how one interface is
connected to another (with no
intervening router)
223.1.3.2
A: wireless WiFi interfaces
connected by WiFi base station
Network Layer 4-29
Subnets
 IP address:
 subnet part (high
order bits)
 host part (low order
bits)
 What’s a subnet ?
 device interfaces with
same subnet 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
subnet
223.1.3.1
223.1.3.2
network consisting of 3 subnets
Network Layer 4-30
Subnets
Recipe
 To determine the
subnets, detach each
interface from its
host or router,
creating islands of
isolated networks.
Each isolated network
is called a subnet.
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
Subnet mask: /24
Network Layer 4-31
Subnets
223.1.1.2
How many?
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
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
Network Layer 4-32
IP Addresses
given notion of “network”, let’s re-examine IP addresses:
“classful” addressing - Traditional:
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
Network Layer 4-33
IP addressing: CIDR
 Traditional: 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
 Current: CIDR: Classless InterDomain Routing


network portion of address of arbitrary length
address format (1): 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
Network Layer 4-34
IP addressing: CIDR
 CIDR: Classless InterDomain Routing
network portion of address of arbitrary length
 address format (2): address + mask

network
part
IP address
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
IP mask
network
part
host
part
11111111 11111111 11111110 00000000
255.255.254.0
Network Layer 4-35
Move a datagram from source to dest
forwarding 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
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.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
Network Layer 4-36
Move a datagram from source to dest
forwarding table in A
misc
data
fields 223.1.1.1 223.1.1.2
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
Starting at A, send IP
datagram addressed to B:
 look up net. address of B in
forwarding table
 find B is on same net. as A
 link layer will send datagram
directly to B inside link-layer
frame
 B and A are directly
connected
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.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
Network Layer 4-37
Move a datagram from source to dest
forwarding table in A
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





in forwarding table
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.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
Network Layer 4-38
Move 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
in router’s forwarding table
 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!)
forwarding table in router
Dest. Net 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.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
Network Layer 4-39
IP addresses: how to get one – host ?
Q: How does host get IP address?
 hard-coded by system admin in a file
Wintel: 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-40
DHCP: Dynamic Host Configuration Protocol
Goal: allow host to dynamically obtain its IP address
from network server when it joins network


Allows reuse of addresses (only hold address while
connected an “on”
Support for mobile users who want to join network
Network Layer 4-41
DHCP client-server scenario
A
B
223.1.1.2
223.1.1.4
223.1.3.1



223.1.2.9
223.1.2.2
223.1.1.3

223.1.2.1
DHCP
server
223.1.1.1
223.1.3.27
223.1.3.2
E
arriving DHCP
client needs
address in this
network
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
Network Layer 4-42
DHCP client-server scenario
DHCP server: 223.1.2.5
DHCP discover
arriving
client
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
Network Layer 4-43
IP addresses: how to get one – network ?
Q: How does network (DHCP server) get network
part of IP addr?
A: gets allocated portion of its provider ISP’s
address space
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
Network Layer 4-44
IP addresses: how to get one – ISP ?
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
Network Layer 4-45
IP (v4) 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
how much overhead
with TCP?
 20 bytes of TCP
 20 bytes of IP
 = 40 bytes + app
layer overhead
32 bits
type of
ver head.
len service
length
fragment
16-bit identifier flgs
offset
upper
time to
Internet
layer
live
checksum
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.
Network Layer 4-46
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
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
Network Layer 4-47
NAT: Network Address Translation
 Motivation: local network uses just one IP address as
far as outside word is concerned:
 no need to be allocated range of addresses from ISP:
- just one IP address is used 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-48
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-49
NAT: Network Address Translation
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
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
Network Layer 4-50
NAT: Network Address Translation
 16-bit port-number field:
 60,000+ simultaneous connections with a single LAN-side
address!
 NAT is controversial:
 abuse of port number
• Problem with internal server using well-know ports
• Network layer vs transport layer


routers should only process up to layer 3 (network layer)
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
Network Layer 4-51
Chapter 4 roadmap
4.1 Introduction and Network Service Models
4.2 Routing Algorithms
4.3 The Internet (IP) Protocol
4.4 Routing in the Internet
 4.5.1 Intra-AS routing: RIP and OSPF
 4.5.2 Inter-AS routing: BGP
4.5 IPv6
4.6 Mobility (Section 6.5/6.6 in textbook)
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
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
Network Layer 4-53
Hierarchical Routing
 aggregate routers into
gateway routers
regions, “autonomous
systems” (AS)
 routers in same AS run
same routing protocol


 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
“intra-AS” routing
protocol
routers in different AS
can run different intraAS routing protocol
C.b
a
 special routers in AS
C
B.a
A.a
b
A.c
d
A
a
b
c
a
c
B
b
Network Layer 4-54
Routing in the Internet
 The Global Internet consists of Autonomous Systems
(AS) interconnected with each other:



Stub AS: small corporation: one connection to other AS’s
Multihomed AS: large corporation (no transit): multiple
connections to other AS’s
Transit AS: provider, hooking many AS’s together
 Two-level routing:
 Intra-AS: administrator responsible for choice of routing
algorithm within network
 Inter-AS: unique standard for inter-AS routing: BGP
(Boarder Gateway Protocol)
Network Layer 4-55
Internet AS Hierarchy
Inter-AS border (exterior gateway) routers
Intra-AS interior (gateway) routers
Network Layer 4-56
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
Network Layer 4-57
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
Network Layer 4-58
Why hierarchical?
 Network size: N
 Non-hierarchical: O(N2)
 Hierarchical (M clusters)
• Non-gateway: (N/M)2
• Gateway: (N/M)2+M2
Network Layer 4-59
Intra-AS Routing
 Also known as Interior Gateway Protocols (IGP)
 Most common Intra-AS routing protocols:

RIP: Routing Information Protocol
• Distance vector

OSPF: Open Shortest Path First
• Link state
Network Layer 4-60
Inter-AS routing in the Internet: BGP
R4
R5
R3
BGP
AS1
AS2
(RIP intra-AS
routing)
(OSPF
intra-AS
routing)
BGP
R1
R2
AS3
(OSPF intra-AS
routing)
Figure 4.5.2-new2: BGP use for inter-domain routing
Network Layer 4-61
Why different Intra-/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
Network Layer 4-62
Why different Intra-/Inter-AS routing ?
Telus
Shaw
Bell
Network Layer 4-63
Chapter 4 roadmap
4.1 Introduction and Network Service Models
4.2 Routing Algorithms
4.3 The Internet (IP) Protocol
4.4 Routing in the Internet
4.5 IPv6
Network Layer 4-64
IPv6
 Initial motivation: 32-bit address space
completely allocated by 2008 ! – not really
 Additional motivation:
header format helps speed processing/forwarding
 header changes to facilitate QoS
 new “anycast” address: route to “best” of several
replicated servers

 IPv6 datagram format:
 fixed-length 40 byte header
 no fragmentation allowed
Network Layer 4-65
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-66
IPv6 Header (Cont)
32 bits
type of
ver head.
len service
length
fragment
16-bit identifier flgs
offset
upper
time
Internet
layer
to
checksum
live
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
Network Layer 4-67
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-68
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?

 Two proposed approaches:
 Dual Stack: some routers with dual stack (v6, v4)
can “translate” between formats
 Tunneling: IPv6 carried as payload in IPv4
datagram among IPv4 routers
Network Layer 4-69
Dual Stack Approach
A
B
C
D
E
F
IPv6
IPv6
IPv4
IPv4
IPv6
IPv6
Flow: X
Src: A
Dest: F
Src:A
Dest: F
Src:A
Dest: F
Flow: ??
Src: A
Dest: F
data
data
data
data
B-to-C:
IPv4
B-to-C:
IPv4
B-to-C:
IPv6
A-to-B:
IPv6
Problems
• Complexity
• Lost information
Network Layer 4-70
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-71
IPv6 – State-of-the-art
 Give up or not ?
 What can we learn from it ?
Network Layer 4-72
Network Layer: summary
What we’ve covered:
 network layer services
 routing principles: link state and
distance vector
 hierarchical routing
 IP
 Internet routing protocols
what’s inside a router?
 IPv6
Next stop:
the Data
link layer!
Network Layer 4-73