CCN Activity Session for Section 2.1 (Including Solutions) – Routing Within an Autonomous System
As you’ve heard in the lectures, connectionless packet switched networks must be able to pass datagrams from the source to the destination host by a series of hops between network elements such as switches. Local networks are often structurally volatile, so the mechanism for routing packets must be sufficiently flexible to cope with changes to the network topology. Two of the most common general approaches to routing packets in local networks are distance vector and link state routing, the main difference between them being whether the routers exchange information on shortest routes between neighbours (algorithms such as the distributed Bellman-Ford), or the shortest paths are calculated from a complete topology map if the network (algorithms such as Dijkstra).
Activity
Apply Bellman-Ford to the graph shown below. Extract the path from node H to node C.
C
2F
2 A71
D
1
G
4
B
4
3
H
2
6
E
Activity
Apply Dijkstra’s algorithm to the graph shown below, starting from node E and enumerating all paths.
C
2F
2 A71
D
1
G
4
B
4
3
H
2
6
E
Discuss
Suppose a routing algorithm identifies paths that are “best” in the following sense: (1) minimum number of hops, (2) minimum delay, (3) maximum available bandwidth. What conditions in the network would lead to the paths produced by these approaches being the same? Which would lead to them being different?
The routes would be identical if the network was uniform (i.e. if all links were the of the same type, and the routing hardware was identical) and the network was free of congestion. Congestion in the network, non-identical queuing / delay behaviour due to differences in the routing hardware, or varying bandwidth on the links would lead to different routing choices.
Further reading
In today’s lecture we’ll talk about RIP, which is one example of an Interior Gateway Protocol for routing within an autonomous system. RIP is a distance vector based routing protocol, but other interior protocols use link state routing, two common examples being Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). Find out about these protocols, and compare with what you know about RIP – what are the strengths and weaknesses of the two approaches?