Introduction to Intra-Domain Routing
Stefano Vissicchio UCL Computer Science
COMP0023
Agenda
• We delve into network layer’s main functionality
1. Setting
• Context
• Routing players
2. Intra-domain routing problem definition
2
Let’s consider a network with several LANs
1.2.3.48
host host 1.2.2.0/23
1.2.3.156
DNS
1.2.3.19
router
host
5.6.7.11
host … DNS 5.6.7.0/24
router
router
3
Several LANs can belong to a single organization
1.2.3.48
host host 1.2.2.0/23
Domain (e.g., UCL)
5.6.7.11
1.2.3.156
DNS
1.2.3.19
router
host host
…
DNS
5.6.7.0/24
router
router
Internet
4
Collecting evidence from the real world
• Traceroute exposes real Internet paths – Unix: traceroute
• It displays all hops on the path between host where launched and
– it sends a sequence of carefully constructed packets that “expire” after 1 hop, 2 hops, …
– each of those packets elicits ICMP error from router that many hops from sender
5
A traceroute from UCL to Cambridge
traceroute to www.cl.cam.ac.uk (128.232.0.20), 64 hops max, 40 byte packets
1 cisco (128.16.64.1) 0.370 ms 0.322 ms 0.361 ms
2 128.40.255.29 (128.40.255.29) 0.483 ms 0.348 ms 0.487 ms
3 128.40.20.1 (128.40.20.1) 0.486 ms 0.342 ms 0.362 ms
4 128.40.20.62 (128.40.20.62) 0.486 ms 0.474 ms 0.363 ms
5 ulcc-gsr.lmn.net.uk (194.83.101.5) 0.485 ms 0.346 ms 0.362 ms
6 london-bar1.ja.net (146.97.40.33) 0.485 ms 0.470 ms 0.488 ms
7 po10-0.lond-scr.ja.net (146.97.35.5) 0.735 ms 0.722 ms 0.610 ms
8 po0-0.cambridge-bar.ja.net (146.97.35.10) 5.232 ms 4.964 ms 4.734 ms
9 route-enet-3.cam.ac.uk (146.97.40.50) 4.982 ms 4.841 ms 4.860 ms
10 route-cent-3.cam.ac.uk (192.153.213.194) 4.984 ms 4.964 ms 4.861 ms
6
A traceroute from UCL to Cambridge
traceroute to www.cl.cam.ac.uk (128.232.0.20), 64 hops max, 40 byte packets
1 cisco (128.16.64.1) 0.370 ms 0.322 ms 0.361 ms
2 128.40.255.29 (128.40.255.29) 0.483 ms 0.348 ms 0.487 ms 3 128.40.20.1 (128.40.20.1) 0.486 ms 0.342 ms 0.362 ms
4 128.40.20.62 (128.40.20.62) 0.486 ms 0.474 ms 0.363 ms
5 ulcc-gsr.lmn.net.uk (194.83.101.5) 0.485 ms 0.346 ms 0.362 ms
6 london-bar1.ja.net (146.97.40.33) 0.485 ms 0.470 ms 0.488 ms
7 po10-0.lond-scr.ja.net (146.97.35.5) 0.735 ms 0.722 ms 0.610 ms
8 po0-0.cambridge-bar.ja.net (146.97.35.10) 5.232 ms 4.964 ms 4.734 ms
9 route-enet-3.cam.ac.uk (146.97.40.50) 4.982 ms 4.841 ms 4.860 ms
10 route-cent-3.cam.ac.uk (192.153.213.194) 4.984 ms 4.964 ms 4.861 ms
7
The big picture emerging from the traceroute
Host
Interface 0
(IP address A)
Subnet 1 128.16.64.0/24
Interface 0 (IP address B)
Interface 1
(IP address C)
Interface 0
(IP address D)
Router
Subnet 2 128.40.255.29/24
Router
9
…
Routers keep routing tables
Three fields
• Destination: destination IP
• Outgoing interface: on which to forward packet for the given destination
• Metric: total cost to reach the destination
– depends on interfaces’ metrics (set by net admins)
Destination
Interface
Metric
A
0
0
B
1
0
11
Routers’ destinations are IP prefixes
• Each host (interface) has unique 32-bit IP address – E.g., 128.16.64.1
• Must every router in entire Internet know about every other router and host?
No; interfaces on same subnet share IP prefix • e.g., 128.16.64/24 for 128.16.64.1
• IP routing destination is subnet’s prefix – Not single IP addresses
12
Routers use routing table to forward packets
• Packet for destination D arrives
• Router searches D in destination field of routing table
– using longest-prefix match
• If more than one route match D, choose the route with
the longest prefix • Possible outcomes:
– if entry for D, forward on interface in the entry – if no entr y, no route known à drop packet
13
Routers use routing table to forward packets
• Packet for destination D arrives
• Router searches D in destination field of routing table
– using longest-prefix match
How to populate routing tables
– if entry for D, forward on interface in the entry – if no entr y, no route known à drop packet
• If more than one route match D, choose the route with for any router in a domain?
the longest prefix • Possible outcomes:
14
At startup, a router initializes its routing table for directly connected subnets
Destination
Interface
Metric
Interface 0
128.16.64/24
(IP address A)
128.40.255.0/24
0
0
1
0
Host
Subnet 1 128.16.64.0/24
Interface 0 (IP address B)
Interface 1
(IP address C)
Interface 0
(IP address D)
Router
Subnet 2 128.40.255.0/24
Router
15
…
At startup, a router initializes its routing table for directly connected subnets
Destination
Interface
Metric
Interface 0
128.16.64/24
(IP address A)
128.40.255.0/24
0
0
1
0
Host
Subnet 1 128.16.64.0/24
Interface 0 (IP address B)
Interface 1
(IP address C)
Interface 0
(IP address D)
Router
Subnet 2 128.40.255.0/24
Packets to other destinations would be dropped
Router
16
…
At startup, a router initializes its routing table for directly connected subnets
Host
Interface 0
128.16.64/24
(IP address A)
Subnet 1 128.16.64.0/24
128.40.255.0/24 1
Routing protocols are needed to add information on remote destinations
Interface 0 (IP address B)
Interface 1
(IP address C)
Interface 0
(IP address D)
Destination
Interface
0
Metric
0
0
Router
Subnet 2 128.40.255.0/24
Packets to other destinations would be dropped
Router
17
…
Agenda
• We delve into network layer’s main functionality
1. Setting
• Context
• Routing players
2. Intra-domain routing problem definition
18
Consider an arbitrary network
• Each router has an ID and several interfaces
– Linked to many other routers and subnets
• Each router must choose the next-hop for received packets
– Packets include info on destinations (IP addresses)
• But not on intermediate hops
D
?
?
?
S
19
Routing protocols build routing tables
• Routing protocols define information and messages exchanged by routers
– For routers to accumulate state (routing table entries) to forward packets
• Routing protocols also determine how to choose between alternative next-hops
D
S
20
Intra-domain routing goals
• Provide good performance
– Typically, choose “good” paths for any pair of routers
• Automated path computation
– Possibly, efficient in time and memory
• Deal with failures
– Routes must be coherent with topology
21
Typical solution: shortest path routing
• View network as weighted graph – Routers are vertices, links are edges – Link metrics are edge weights
10
5
20
10
5
5
22
Typical solution: shortest path routing
Shortest paths problem:
– What path between two vertices offers minimal sum of edge weights?
• Classic graph algorithms find single-source shortest paths when the entire graph is known centrally
– Dijkstra’s Algorithm, Bellman-Ford Algorithm • Typically, no central knowledge of entire graph
– Each router only knows its own interfaces’ addresses
23
Challenge: deal with changing networks
• Network components are not reliable
– Links may be cut, router or their interfaces may fail
• Changing networks induce hazards
– Need for (fast) re-convergence to new, correct paths
after a failure
– Potential for forwarding loops
• Amplify traffic à congest links
– TTL will eventually expire, but typically too late
– Possibility of temporary disconnections (i.e., blackholes) 24
Distance Vector Routing
Stefano Vissicchio UCL Computer Science
COMP0023
Agenda
• We are now ready to study Distance Vector routing 1. Algorithm
2. Pathologies 3. Optimizations
26
Basic Distance Vector Algorithm
• Distributed Bellman-Ford (DBF)
• Principle:“tell everything you know to your
neighbours”
– Periodically, send all your routing table entries (destination and metric fields) to all your neighbouring routers
27
Basic Distance Vector Algorithm: DBF
(Failures NotYet Considered)
Upon receipt of routing table entry for destination D with metric m on interface i:
m += configured metric for interface i rt = lookup(D) in rou0ng table
if (rt = “not found”) then
rt_new = new rou0ng table entry
rt_new.dst = D; rt_new.metric = m; rt_new.iface = i add rt_new to rou0ng table
else if (m < rt.metric) then rt.metric = m; rt.iface = i
28
Distance Vector: Example
• Consider simple network where all nodes are routers, addresses are simply single letters
• Initial routing tables when routers first start:
0C 1
Dst
I/f
Metric
A
local
0
Dst
I/f
Metric
B
local
0
02 A1 B
Dst
Metric
A
0
01
Dst
I/f
Metric
C
local
0
011 D 0E2
Dst
I/f
Metric
D
local
0
Dst
I/f
Metric
E
local
0
29
Distance Vector: Iteration 1
• Routers incorporate received announcements:
0C 1
Dst
I/f
Metric
B
local
0
A
0
1
C
2
1
E
1
1
Dst
I/f
Metric
A
local
0
B
1
1
D
0
1
02 A1 B
01
Dst
I/f
Metric
C
local
0
B
0
1
E
1
1
011 D 0E2
Dst
I/f
Metric
D
local
0
A
0
1
E
1
1
Dst
I/f
Metric
E
local
0
D
0
1
B
1
1
C
2
1
30
Distance Vector: Iteration 2
• Routers incorporate received announcements:
0C 1
Dst
I/f
Metric
B
local
0
A
0
1
C
2
1
E
1
1
D
1
2
Dst
I/f
Metric
A
local
0
B
1
1
D
0
1
E
0
2
C
1
2
02 A1 B
01
011 D 0E2
Dst
I/f
Metric
C
local
0
B
0
1
E
1
1
A
0
2
D
1
2
Dst
I/f
Metric
D
local
0
A
0
1
E
1
1
B
0
2
C
1
2
Dst
I/f
Metric
E
local
0
D
0
1
B
1
1
C
2
1
A
1
2
31
Distance Vector: Iteration 2
• Routers incorporate received announcements: Convergence:
routing tables no longer changing;
Dst I/f Metric
Dst I/f Metric
A local 0
B11
A01
B local 0
routes reflect up-to-date knowledge of topology
C
2
1
E
1
1
D
1
2
D
0
1
E
0
2
C
1
2
02 A1 B
01
011 D 0E2
0C 1
Dst
I/f
Metric
C
local
0
B
0
1
E
1
1
A
0
2
D
1
2
Dst
I/f
Metric
D
local
0
A
0
1
E
1
1
B
0
2
C
1
2
Dst
I/f
Metric
E
local
0
D
0
1
B
1
1
C
2
1
A
1
2
32
Link Failure (1)
Dst
I/f
Metric
B
local
0
A
0
1
C
2
1
E
1
1
D
1
2
Dst
A
B
D
E
C
I/f
local
1
0
0
1
Metric
0
1
1
2
2!
A1 B
02 0!1
0C 1
011 D 0E2
Dst
I/f
Metric
C
local
0
B
0
1
E
1
1
A
0
2
D
1
2
Dst
I/f
Metric
D
local
0
A
0
1
E
1
1
B
0
2
C
1
2
Dst
I/f
Metric
E
local
0
D
0
1
B
1
1
C
2
1
A
1
2
33
Link Failure (1)
Dst
I/f
Metric
B
local
0
A
0
Inf
C
2
1
E
1
1
D
1
2
Dst
I/f
Metric
A
local
0
B
1
Inf
D
0
1
E
0
2
C
1
Inf
02 A1 B
01
0C 1
011 D 0E2
Dst
I/f
Metric
C
local
0
B
0
1
E
1
1
A
0
2
D
1
2
Dst
I/f
Metric
D
local
0
A
0
1
E
1
1
B
0
2
C
1
2
Dst
I/f
Metric
E
local
0
D
0
1
B
1
1
C
2
1
A
1
2
34
Link Failure (2)
Dst
I/f
Metric
B
local
0
A
0
Inf
C
2
1
E
1
1
D
1
2
Dst
A
B
D
E
C
Metric C 0
Inf
1
2
Inf
Dst
A
B
D
E
I/f
local
1
0
0
1
Metric
0
Inf
1
2
Inf
02 A1 B
01
0C 1
011 D 0E2
Dst
I/f
Metric
C
local
0
B
0
1
E
1
1
A
0
2
D
1
2
Dst
I/f
Metric
D
local
0
A
0
1
E
1
1
B
0
2
C
1
2
Dst
I/f
Metric
E
local
0
D
0
1
B
1
1
C
2
1
A
1
2
35
Link Failure (2)
Problem:
D ignores the update for the route to
B because the metric is worse than
Dst I/f Metric
the one it already has.
B local 0
A
C
E
D
0
2
1
1
Inf
1
1
2
Dst
A
B
D
E
C
Metric C 0
Inf
1
2
Inf
Dst
A
B
D
E
I/f
local
1
0
0
1
Metric
0
Inf
1
2
Inf
02 A1 B
01
0C 1
011 D 0E2
Dst
I/f
Metric
C
local
0
B
0
1
E
1
1
A
0
2
D
1
2
Dst
I/f
Metric
D
local
0
A
0
1
E
1
1
B
0
2
C
1
2
Dst
I/f
Metric
E
local
0
D
0
1
B
1
1
C
2
1
A
1
2
36
DV Algorithm, Revised
• Upon receipt of routing table entry for destination D with metric m on interface i:
m += metric for interface i
rt = lookup(D) in rou