Routing

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 1
 Routing algorithm
D
A
source
router R2
B R1
R4
E
C R3
destination F
router
• How to find the best path from A to F?
• How does R1 chooses the best route to R4?
• “A part of the network software responsible for deciding which
output line an incoming packet should be transmitted on.”

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 2
 Routing - properties
1. correctness
2. simplicity
3. robustness
• updating possibility
• should cope with changes in the topology and traffic
4. stability
• must converge to equilibrium
5. fairness
6. optimality
– min mean packet delay
– max total network throughput
• Note: 5 & 6 often contradictory
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 3
 Routing algorithms
– DYNAMIC
• change routing decisions to reflect changes in the topology
• adapt for changes in the traffic (load change)
• ALGORITHMS: where the routers get the information from?
– locally
– from adjacent routers
– from all routers
• ALGORITHMS: when they change their routes?
– every ΔT sec
– when the load changes
– when topology changes
– STATIC
• routes computed in advance
– node failures, current load etc. not taken into account
• Note that both dynamic & static algorithms can be either load-sensitive or
load-insensitive.
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 4
 The optimality principle
How to find the optimal route without regard to the
network topology & traffic?
• If a router J is on the optimal path from I to K then the
optimal path from J to K falls along the same route
– I-J r1; J-K r2; if r2 not optimal than upper statement contradictory
– Sink Tree : set of optimal routes
from all sources to a
given destination form
a tree routed at the
destination

a subnet sink tree for router B

• The goal of routing alg.: discover & use the sink tree for all routers

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 5
 Static routing

• Dijkstra’s algorithm (Shortest Path Routing)

– computes the least-cost path (route) from one node to all the
other nodes
• Flooding
– Computes the shortest path (route) from one node to all the
other nodes (inverse tree)

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 6
 Dijkstra’s algorithm
• c(i,j) link cost from node i to j
• c(i,j)= if i & j not directly conn
• D(v) cost of the path from the
source node to destination v
• N set of nodes whose least-
cost path from the source is
definitely known

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 7
 Dijkstra’s algorithm - sketch

step N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F) D(G),p(G) D(H),p(H)

0 A 2,A     6,A 

1 AB 9,B  4,B  6,A 

2 ABE 9,B  6,E 5,E 

3 ABEG 9,B  6,E 9,G

4 ABEGF 9,B  8,F

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 8
 Dijkstra’s algorithm - sketch

step N D(B),p(B) D (C),p (C) D(D),p(D) D(E), p(E) D(F), p(F) D(G),p(G) D(H),p(H)
0 A 2,A     6,A 

1 AB 9,B  4,B  6,A 

2 ABE 9,B  6,E 5,E 

3 ABEG 9,B  6,E 9,G

4 ABEGF 9,B  8,F

5 ABEGFH 9,B 10,H

6 ABEGFHC 10,H

5 ABEGFHCD

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 9
 Flooding
• Another static algorithm
• Every incoming packet is sent out to every outgoing
line except the one that the packet arrived on
PROBLEM:
• A large # of duplicated packets
A E SOLUTION:
C
• counter decremented in hops
B H
D • put a sequence # in each packet
G ­ decrement seq. # at each hop
­ the packets received by D from
F both C & B are discarded since
they both have smaller sequence
numbers
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 10
 Flooding (cnt’d)
• Mostly applicable in
– Military applications
• A large number of routers may be blown at any instant
– Robustness required!
– Distributed database applications
• To update all the databases concurrently
– Wireless sensor networks
• Sensors can randomly come and go
– Benchmarking
• As a metric against which other routing algorithms can be
compared

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 11
 Two basic dynamic algorithms
• Distance Vector Routing
– used in the ARPANET until 1979
• Link State Routing
– used in the newer Internet Open Short Path First (OSPF)
protocol

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 12
 The Distance Vector Routing
• Dynamic algorithm
– takes current network load into account
• Distributed
– each node receives information from its directly attached
neighbours, performs a calculation, distribute the results back
to neighbours

This algorithm is sometimes also known as

- Distributed Bellman-Ford routing algorithm
- Ford-Fullkerson algorithm

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 13
 The Distance Vector Routing

(a) A subnet. (b) Input from A, I, H, K, and the new

routing table for J.
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 14
 The count-to-infinity problem
• DVR – good news spread rapidly, bad news slowly
• Suppose all distance vectors sent at once
• Suppose that A was down (link cost = ) and it just came up

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 15
 The distance vector routing
• Two problems
1. Link bandwidth not taken into account for metric, only the
queue length
– all the lines at that time 56 Kbps
2. Efficient only in small networks. Why?
– Too long time to converge
– QUESTION: when the algorithm converges?
– ANSWER: when every node knows about all other
nodes and networks and computes the shortest path to
them

– will the nodes know the exact network topology by then?

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 16
 Two basic algorithms
• Distance Vector Routing
• Link State Routing

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 17
 A Link state routing algorithm
• Link state broadcast – node learns about the path costs
from its neighbors
• Inform the neighbors whenever the link cost changes
– hence the name link state

• Advertisements on the link state are not repeated

periodically!
– Consequence (pros & cons)?

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 18
 Link state routing
Each router must do the following:
1. Discover its neighbors, learn their network
address.
2. Measure the delay or cost to each of its neighbors.
3. Construct a packet telling all it has just learned.
4. Send this packet to all other routers.
5. Compute the shortest path to every other router.

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 19
 Constructing link state packets

sender

subnet link state packets for this subnet

• When to build these packets?

– at regular time intervals,
– on occurrence of some significant event,
• link goes down (or comes back); cost change appreciably.
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 20
 Distributing the link state packets
• Typically, flooding
– routers recognize packets passed earlier
• sequence number incremented for each new packet sent
• routers keep track of the (source router, sequence) pair
• thus avoiding the exponential packet explosion
– first receivers start changes already while changes are being
reported
– sequence numbers wrap around or might be corrupted
• 32 bit sequence number
• To avoid corrupted sequences (or a router reboot) and therefore
prevent any update, the state at each router has an age field that
is decremented once a second
• but, need additional robustness in order to deal with errors on
router-to-router lines
– acknowledgements

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 21
Task: compare DV and LS algorithms
With respect to:
• Message complexity,
• Speed of convergence,
• Robustness,
• Bandwidth consumption (overhead),
• Simplicity,
• Fairness,
• Optimality.

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 22
 Routing in the Internet
• What would happen if hundreds of millions of routers
execute the same routing algorithm to compute routing
paths through the network?
• Scale
– large overhead
– enormous memory space in the routers
– no bandwidth left for data transmission
– would DV algorithm converge?
• Administrative autonomy
– an organization should run and administer its networks as it
wishes but must be able to connect it to the “outside” networks

Igor Radovanović, [Link]@[Link]

14/04/11 TU/e Computer Science, System Architecture and Networking 23
 Hierarchical routing
• The Internet uses hierarchical routing
– it is split into Autonomous Systems (AS)
• routers at the border: gateways
• gateways must run both intra & inter AS routing protocols
– routers within AS run the same routing algorithm
• the administrator can chose any Interior Gateway Protocol
– Routing Information Protocol (RIP(implementation of DVR Protocol))
– Open Shortest Path First (OSPF(implementation of LSR Protocol))
– between AS gateways use Exterior Gateway Protocol
• Border Gateway Protocol (BGP)

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 24
 Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 25
 Autonomous systems H2
gateway

network

router A BGP B

RIP & BGP

OSPF D
H1 BGP C

• gateways (R1, R2, R3, R4) use both interior & exterior routing
• other routers use only interior routing
• Note: AS routing protocols in A, B, C & D not need to be the same!
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 26
 Routing Information Protocol
• Based on Distance Vector Routing
• Distance metric = hop count
1. each router shares its knowledge about the entire AS
• it is unimportant how much it knows, it sends whatever it has
2. sharing only with neighbours
3. updates exchanged among neighbours every 30 sec
– RIP response message
• Send the distance to networks within AS

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 27
 RIP updating algorithm
Receive: a response RIP message
1. Add one hop to the hop count for each advertised destination.
2. Repeat the following steps for each advertised destination:
a. If (destination not in the routing table)
I. Add the advertised information to the table.
b. Else
I. If (next-hop field is the same)
i. Replace entry in the table with the advertised one.
II. Else
i. If (advertised hop count smaller than one in the table)
- Replace entry in the routing table.
3. Return.
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 28
 RIP – updating the table

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 29
 Open Shortest Path First
• “Open” - resources assumed to be freely usable
• Uses Link State algorithm
– Link state (LS) packet spreading
– Topology map at each node
– Route computation using Dijkstra algorithm
– link costs set up by the administrator
• Separates policy from mechanism

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 30
 OSPF – advances to RIP
• Security: all messages between routers (for example
link state updates) are authenticated

• Multiple same-cost path: allowed

• Support for hierarchy: AS is divided into areas to handle

routing efficiently

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 31
 Areas in AS

• intra area routing involves only routers within the same area
• area border router – routs the packet outside the area
• exactly 1 area configured to be backbone area
• backbone routers run OSPF within backbone area
• AS bound. router – exchanges routing info with routers in other AS’s

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 32
 Inter AS routing
Border Gateway Protocol
• it is de facto standard interdomain routing protocol in
today’s Internet H2
gateway

network

router A BGP B

RIP & BGP

OSPF D
H1 BGP C

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 33
 BGP
• Why are Distance Vector Routing & Link State Routing
not good candidates?
– route with the smallest hop count not the preferred one
• AS not secure
– DVR: only a number of hops known to a destination, not the
path to get there
– LSR: Internet too big for this routing method
• huge databases
• long time to run Dijsktra’s algorithm

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 34
 BGP- path vector messages

network next router path

1. router R1 sends a path vector advertising the detachability of N1

2. router R2 receives the message, updates its table, replaces the
router # with its own, adds its AS # and sends a message to R3
3. …
Igor Radovanović, [Link]@[Link]
14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 35
 BGP activities
1. receiving & filtering route advertisement from directly
attached neighbors

2. route selection
• distinguish between routing mechanism & routing policy
3. sending its route advertisement to neighbors
• only provides mechanism – not policy

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 36
 Types of BGP packets

• Open: create a neighbor relationship

– a router running BGP opens a connection and sends an open
message
– if a neighbour accepts the relationship its responds with a keep-alive
• Update: heart of BGP
– used to redraw destinations advertised previously
• Keep-alive: routers tell each other that they are active
• Notification: in case of error or when router wants to close the
connection

Igor Radovanović, [Link]@[Link]

14/04/11
10/20/24 TU/e Computer Science, System Architecture and Networking 37