Chapter 5: The Network Layer II Flashcards
What are the three classifications of routing algorithms?
Centralised: All routers have complete topology.
Decentralised: Least-cost path is carried out iteratively, distributed among the routers.
Static routing algorithms are where routes change very slowly.
Dynamic routing algorithms change the routing paths as the network traffic changes.
Load-sensitive algorithms consider that link costs vary dynamically to reflect the current level of congestion in the underlying link.
Load-insensitive algorithms are where a link’s cost doesn’t represent it’s congestion.
What is Dijkstra’s algorithm?
Initialisation:
- The subset of finished nodes is the starting node.
- The cost of all neighbours is the path cost.
Loop:
- Find the unfinished node with the lowest cost and add it to the finished nodes.
- For each neighbour, update it if the path from this node is shorter.
Terminate:
- When all nodes are finished.
What is the time-complexity of Dijsktra’s algorithm?
O(V^2) standardly, but with heap implementation O(V + ElogV)
How can we mitigate oscillating results of the LS algorithm?
Routers each randomise the time it sends out a link advertisement.
Explain the Bellman-Ford equation:
d_x(y) = min_v{c(x, v) + d_v(y)}
If x goes to some v, before going to y, it will be the cost of the (x,v) link plus the least-cost of the (v,y) path.
Thus, the minimum over all neighbours is the least cost.
What is the Distance-Vector Algorithm? Explain for some node x.
Initialisation:
- For all destinations, set D_x(y) to be the cost of (x,y) link. [This can be infinite.]
- For all neighbours, set D_w(y) to an unknown variable.
- For all neighbours, send distance vector Dx = [D_1(y), D_2(y), …, D_N(y)].
Loop (on link_cost change to any neighbour || on distance vector received) :
- for all destinations ‘y’, D_x(y) = min_v{c(x, v) + d_v(y)}
- if D_x(y) changed, send the distance vector to all neighbours.
Termination: None
What is the count-to-infinity problem?
Bad news spreads very slowly through a DV algorithm. If a link cost suddenly increases a lot, two nodes will be incrementally increasing their length times, taking a long time to reach a high value.
Does poisoned reverse fix the count-to-infinity problem?
No. If z routes through y to get to x, every time it sends its vector, it sends Dz(x) as infinity, meaning y will not route through z to get to x.
This works for neighbouring nodes, but not loops of more then two nodes.
Compare the LS and DV routing algorithms.
LS requires more messages, O(N * E), to be sent.
LS converges much faster then DV, which can hit routing loops or count to infinity.
LS is much more robust than DV.
What is an intra-autonomous system routing protocol?
In a group of routers/links owned by one administrator, the routing algorithm running within them is an Intra-AS protocol.
What is OSPF?
It uses flooding of link-state information and Dijkstra’s algorithm. Each router builds a complete topological map of the AS.
It then computes minimum path trees to each subnet with itself as the root.
Every time something changes, or periodically every 30 minutes, the link’s state is broadcast.
All OSPF messages are authenticated.
What are the two main roles of BGP (Border Gateway Protocol)?
It allows each subnet to be known about by the rest of the Internet.
It determines the best route for a router to send a packet to a specific prefix.
What is the route selection algorithm for BGP?
If there are multiple routes to the same prefix, then the following ordering is chosen:
1. Local preference (additional attribute set by the router or administrator)
2. Shortest AS-PATH
3. Closed NEXT-HOP router
4. BGP identifiers
Theoretically, how might CDN servers use BGP? Why do they not?
They set the same IP address for each of its servers, and use standard BGP to advertise this IP address from each of the servers.
Each router chooses the best route to a server.
They don’t because BGP routing changes will cause different packets to reach different instances of the Web server.
How does DNS use BGP?
When a DNS query is sent to one of the root server IP addresses, BGP finds the closest root DNS server for that IP address.
