Routing Flashcards
Explain the dynamic alternative routing protocol, making reference to the concept of a sticky random tandem and trunk reservation.
Dynamic alternative routing assumes a fully connected network with stochastic traffic. When nodes i and j wish to communicate and the direct link between them is saturated, we use an alternative (tandem) node. This is either fixed apriori is is chosen randomly (sticky tandem) and replaced as soon as it fails. Trunk reservation means that a tandem agrees to forward a call iff it has a free capacity greater than R.
What is an automonous system? What is the difference between Intra-AS and Inter-AS routing and how do their requirements differ?
An AS is a collection of routing prefixes under the control of one or more network operators which presents a common routing policy to the internet.
Inter-AS must allow policy-based routing, where a policy refers to arbitary preference between several options. The routing protocol must be flexible to change in policy and scalalbe to the size of the internet.
Describe the Distance Vector Routing protocol. How many iterations are required until a steady state is reached?
Each node maintains a distance vector, which records the estimated distance to each other node in the network, in conjunction with the next hop to reach that node. Nodes periodically exchange distance vectors with their neighbours and recalculate if any of their distance estimates can be shortened by routing through a neighbour. This is essentially the Bellman-Ford algorithm and requires O(d) iterations, where d is the diameter of the network.
Describe the count to infinity problem and outline a possible solution.
The solution is to implement poisoned reverse; If B is the next hop to C for A, A advertises its C distance to B as infinity.
Describe the link state protocol.
With the link state approach, the state of the entire toplogy is disseminated to each node via controlled flooding. Each node creates a link state message identifying itself and all the nodes it is immediately connected to. After flooding, each node has a global view of the topology and indepedently calculates shortest paths.
One problem with the link state protocol is that sequence numbers wrap around. Describe two solutions to this problem.
The first solution is aging; the creator of the LSP puts a timeout value in the header. Other routers discard the LSP after the timeout peroid.
The second solution is a lollipop sequence space, which distinguishes start sequence numbers. Thus if other routers see an older sequence number, they know it is a router rebooting and notify it of the current sequence number.
What is the major disadvantage of link state routing which makes it unsuitable for inter-AS routing?
Each router must have an excessive amount of storage. Moreover, It is based on minimizing some notion of GLOBAL distance, which doesn’t allow each AS to have its own policy.
How can multicast routing be implemented and what are some optimisations?
The simplest implementation is to flood packets from the source to the entire network. But routers receieve duplicate packets and therefore must be stateful. A solution is reverse path forwarding, whereby a router only accepts a packet if it arrives on the shortest path from the source. Better still is for node X to only forward a packet from source S to node Y if X is along the shortest path to Y from S!
