Transcript Routing

CSS432 Routing
Textbook Ch3.3
Professor: Munehiro Fukuda
CSS 432: Routing
1
What Is Routing?

Forwarding vs Routing
 forwarding:




To map a network # to an outgoing interface and some MAC
information in a forwarding table.
To send a packet to an interface as consulting a local and static
forwarding table
OSI Layer 2: data link level
Implemented in specialized hardware (switch)
 routing:




To build a dynamic routing table
To update table contents in a dynamic and distributed fashion
OSI Layer 3: network level (internet)
Using complex distributed algorithms
CSS 432: Routing
2
Overview
At Node A

Network as a Graph
A
6
1
3
4
C

9
E
1
Next Hop
B
2
E
C
6
E
D
2
E
E
1
E
F
3
E
D
Find lowest cost path between two nodes
Static approach has shortcomings:




B
F
Cost
Goal


2
1
Destination
Hardware failures
Static network topology
Static band width
Distributed, dynamic routing algorithms


Distance vector routing (RIP)
Link state routing (OSPF)
CSS 432: Routing
3
Distance Vector

Each node maintains a set of triples
 (Destination, Cost, NextHop)
B
An initial distance vector at node A
Destination
Cost
Next hop
B
1
B
C
1
C
D
∞
-
E
1
E
F
1
F
G
∞
-
C
A
D
E
F
CSS 432: Routing
G
4
Distance Vector


Exchange updates directly connected neighbors
 periodically (on the order of several seconds)
 whenever table changes (called triggered update)
Each update is a list of pairs:
 (Destination, Cost)







(C, 1, C) < (C, 2, B)
(D, ∞, - ) > (D, 2, C)
From F: (G, 1)

D
G
F
From C: (D, 1)

C
A
E
Update local table if receive a “better” route
 From B: (C,1)


From B: (A, 1), (C, 1)
From C: (A, 1), (B, 1), (D, 1)
From E: (A, 1)
From F: (A, 1), (G, 1)
B
(G, ∞, - ) > (G, 2, F)
Refresh existing routes; delete if they are expired
CSS 432: Routing
Destination
Cost
Next hop
B
1
B
C
1
C
D
2
C
E
1
E
F
1
F
G
2
F
5
Routing Loop


Failure-recovering scenario
 F detects the link to G has failed
B
C To G in 2
 F sets distance to G to ∞ and sends an update to A
To G in 3
A
D
 A sets distance to G to ∞
 A receives periodic update from C with a 2-hop path To G in 4
E
To G in 1
to G
G
F
∞
 A sets distance to G to 3 and sends update to F
 F sets distance to G in 4 hops via A
B
Count-to-infinity problem
(5) To E in 4
 The link from A to E fails
(3) To E in 3
(2) To E in ∞
 A advertises distance of infinity to E
 C advertise a distance of 2 to E
(4) To E in ∞ (1) To E in 2
A
C
 B decides it can reach E in 3 hops
(6) To E in 5
 B advertises this to A
∞
 A decides it can read E in 4 hops
 A advertises this to C
E
 C decides that it can reach E in 5 hops…
CSS 432: Routing
6
Loop-Breaking Heuristics


Set infinity to 16

Scheme: Stop an infinity loop in 16.

Problem: No more 16 hops
Split horizon

Scheme: Don’t send a neighbor the routing information learned from
this neighbor.


Ex. B includes (E, 2, A) and thus doesn’t send (E, 3).
Split horizon with poison reverse

Scheme: Send the routing information learned from this neighbor as
setting hop count to ∞.


Ex. B includes (E, 2, A) and thus sends (E, ∞, A)
Problem: Its slow convergence speed
CSS 432: Routing
7
Routing Information Protocol (RIP)
frame header




1: request
2: reply
Used by routed
Advertisement: 30secs
Table entry timeout: 3 mins.


Routing domain
Addr family (net addr)
Route tag
Address of net 1
Cmd
Port: 520

RIP Message
UDP header
Cmd: 1-6


datagram heaader
Deleted in 60secs
Subnet mask
Next hop address (1-16)
Distance to net 1
Addr family (net addr)
Route tag
Address of net 2
Unix commands



Ripquery (BSD)
Tcpdump (available in Linux, too)
Snoop (Solaris)
25 entries
CSS 432: Routing
Ver
Subnet mask
Next hop address
Distance to net 2 (1-16)
8
Link State

Strategy
 Reliable dissemination of link-state information to
all nodes over a system.
 Calculation of routes from the sum of all the
accumulated link-state knowledge.

Link State Packet (LSP)
 ID of the node that created the LSP
 A cost of link to each directly connected neighbor
 A sequence number (SEQNO)
 A time-to-live (TTL) for this packet
CSS 432: Routing
9
Link State (cont)

Reliable flooding
 Store most recent LSP from
each node
 Forward LSP to all nodes but
one that sent it
 Generate new LSP
periodically

Increment SEQNO
 Start SEQNO at 0 when
reboot
 Decrement TTL of each
stored LSP

Discard when TTL=0
CSS 432: Routing
X
C
A
B
D
10
Dijkstra’s Shortest-Path Algorithm




put (myself, 0, -) in the confirmed list
Next = myself;
while( true ) {
 for each edge (X, distance, Next) where X is N’s neighbor
 if neither confirmed or tentative list has (X, distance, Y) where
Y != Next, put (X, distance, Next) in the confirmed list
 if the tentative list has (X, distance, Y) where Y != Next, and (X,
distance, Y) > (X, distance, Next)
 Replace (X, distance, Y) with (X, distance, Next)
 If the tentative list is empty,
 exit
 else
 move the shortest edge (A, distance, B) from the tentative to the
confirmed list.
 Next = A
}
CSS 432: Routing
11
Dijkstra’s Shortest-Path Algorithm
(A, 0, -)
(A, 0, -)
(B, 5, B)
(C, 10, C)
(E, 2, E)
(F, 4, F)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(C, 10, C)
(F, 4, F)
(A, 0, -)
(E, 2, E)
(F, 4, F)
(C, 10, C)
(B, 5, B)
(A, 0, -)
(E, 2, E)
(F, 4, F)
(C, 10, C)
(B, 5, B)
(G, 15, F)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(F, 4, F)
(C, 8, B)
(G, 18, B)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(F, 4, F)
(C, 8, B)
(G, 15, F)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(F, 4, F)
(C, 8, B)
(G, 15, F)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(F, 4, F)
(C, 8, B)
(D, 14, C)
(G, 15, F)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(F, 4, F)
(C, 8, B)
(D, 14, C)
(G, 15, F)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(F, 4, F)
(C, 8, B)
(D, 14, C)
(G, 15, F)
(A, 0, -)
(E, 2, E)
(B, 5, B)
(F, 4, F)
(C, 8, B)
(D, 14, C)
(G, 15, F)
5
A
3
B
10
D
2
4
F
CSS 432: Routing
6
C
13
E
11
2
G
12
Open Shortest Path First Protocol (OSPF)
frame header
Version
Type(=4)
datagram header
OSPF header
Message Length
SourceAddr
AreaId
Checksum
Authentication type
Authentication 0-3
Authentication 4-7


OSPF Message
# of link status advertisements
Options
LS Age
Type=1
Link-state ID
Advertising router
LS sequence number
Link Checksum
Length
Header
0 Flag
0
# of links
1.
Hello (reachability)
2.
Database description (topology)
Link ID
3.
Link status request
Link data
4.
Link status update
5.
Link status acknowledgment
Metric
Link type Num TOS
Advertisement (header type=4)

LS Age: = TTL
Optional TOS information

Type=1: link cost b/w routers

Link-State ID = Advertising Router

Seq # from the same router

Link ID = the other end route ID of link

Link data = used if there are two or more links to the same router

Metric = link cost

Link type = P2P, ethernet, etc

TOS = delay-sensitive, etc
CSS 432: Routing
13
OSPF Con’td


Gated daemon: directly uses IP datagram.
Header Type2: Database description (topology)
message
 Used when the current
 Sent from an initialized
topology has changed.
router to another router which
has a topology information

LS Sequence number
 Used
to determine which message is the latest
 Send a message with a new sequence number and
metric= ∞ when a router or a link fails.
CSS 432: Routing
14
Metrics

Original ARPANET metric



New ARPANET metric






measures number of packets enqueued on each link
took neither latency or bandwidth into consideration
stamp each incoming packet with its arrival time (AT)
record departure time (DT)
when link-level ACK arrives, compute
Delay = (DT - AT) + Transmit + Latency
if timeout, reset DT to departure time for retransmission
link cost = average delay over some time period
Fine Tuning


compressed dynamic range
replaced Delay with link utilization
CSS 432: Routing
15
Virtual Private Networks and Tunnels
Application
Level
A
10.0.0.1
20.0.0.1
Router
Dest router
Source router
Router
Level
A
10.0.0.1
20.0.0.1
To: 20.0.0.1
To: 215.0.0.1
To: 10.0.0.2
215.0.0.1
Company
Branch
Company
Branch
To: 20.0.0.1
A
10.0.0.1
B
To: 20.0.0.1
C
Physical
Network Level
B
To: 215.0.0.1
To: 215.0.0.1
Internet
To: 215.0.0.1
CSS 432: Routing
To: 20.0.0.1
B
20.0.0.1
16
Why VPN?
1.
Security

2.
Routers

3.
Routers with special features such as multicasting
can form a virtual network.
No-IP packets

4.
The final destination/contents of packet cannot be
easily intercepted.
Packets may be non-IP compatible packets.
Mobile IPs

The final destination may be a mobile computer.
CSS 432: Routing
17
Mobile IP


Sending host
Invariant: Sending hosts want to use the same IP address
mapped to a mobile host regardless of its location.
Questions
 How does the home agent intercept a packet that is
destined for the mobile agent? --- Use ARP
 How does the home agent then deliver the packet to the
mobile host? – Use DHCP and VPN
10.0.0.3
Home
agent
Internet
DHCP
server
12.0.0.6
Mobile Host
10.0.0.9
(12.0.0.7)
Mobile Host
CSS 432: Routing
18
Mobile IP (Cont’d)
Sending host
1. ARP request: What’s the physical addr
corresponding to 10.0.0.9?
3. Packet request: sends a packet destined for 10.0.0.9
to the home agent’s MAC address
2. ARP response: sends back MAC of
10.0.0.3 instead of 10.0.0.9
1. DHCP: receives a new IP
in the foreign network.
10.0.0.3
Home
agent
Internet
DHCP
server
12.0.0.6
IP tunneling: wraps the packet inside an IP
header destined for the mobile host (12.0.0.7).
Mobile Host
10.0.0.9
(12.0.0.7)
Mobile Host
2. Care-of-address: a mobile host informs its
Home agent of its original and new IPs.
CSS 432: Routing
19

Reviews
 RIP:
distance vector, routing loop and breaking heurictics
 OSPF: link state, Dijkstra’s shortest path algorithm
 VPN and mobile IP

Exercises in Chapter 3
 Ex.
46 (RIP)
 Ex. 52 (RIP)
 Ex. 62 (OSPF)
 Ex. 64 (OSPF)
CSS 432: Routing
20