Bellman Ford and Dijkstra

Recap

Last time: flooding, source routing and distributed algorithms

All three are used in certain parts of the internet nowadays

Flooding: when we don’t know the topology – router failure, or before the routing table is decided (used as part of distributed algorithms)

Source routing: when the source host wants to control the whole path

Distributed algorithms: Bellman-ford and Dijkstra

• Bellman-ford: fully distributed, and each router does a small amount of computation as a part of the large computation. However, it is hard to stabilize and reason about the incorrectness (and how incorrectness is propagated in the algorithm) if the topology changes.
• Dijkstra: determine topology (hard part) and then do a BFS (easy part).

How often to rerun the algorithm? This is a configurable parameter (every 30, 60 or 90 seconds), and a link failure would trigger an update.

Distributed Bellman-Ford Algorithm

• Assume routers know cost of link to each neighbor
• Each router has a distance vector c = (c1, c2, …). Each router sends its distance vectors to its neighbors. If the router knows a lower cost path, it updates the vector. Repeat.
• Hard to stabilize.

How routing works in the Internet

Autonomous Systems (AS’s)

(Stanford is an AS).

Each AS has “border routers” that are connected to the border routers of other AS’s. Border routers are only aware of other border routers, and communicate following Border Gateway Protocol (BGP).

Within each AS, it decides its own routing protocol and this is opaque from outside the AS.

Stub AS (a leaf point of the Internet) and Transit AS (would transit traffic from one border router to another border router)

traceroute

AS numbers: AS’s use an address space different from IP addresses, and each AS is responsible for a certain range of IP addresses. (whois takes an IP address and return the AS number)

Internet exchange points (IXP): many routers for interconnecting between border routers of ISPs and ASs. How ISPs are connected within the IXP is decided by the IXP. IXP uses Ethernet switches to connect different ISPS (and therefore communication happens on the hardware address level)