[CN notes] Intradomain Routing

CN notes 前情提要：傳送門

目錄：
• What is the difference between forwarding and routing?
• What is the main idea behind a link-state routing algorithm?
• What is an example of a link-state routing algorithm?
• Walk through an example of the link-state routing algorithm.
• What is the computational complexity of the link-state routing algorithm?
• What is the main idea behind the distance vector routing algorithm?
• Walk through an example of the distance vector algorithm.
• When does the count-to-infinity problem occur in the distance vector algorithm?
• How does poison reverse solve the count-to-infinity problem?
• What is the Routing Information Protocol (RIP)?
• What is the Open Shortest Path First (OSPF) protocol?
• How does a router process advertisements?
• What is hot potato routing?

What is the difference between forwarding and routing?

• 轉發 (forwarding): refers to transferring a packet from an incoming link to an outgoing link within a single router.
• 路由 (routing): refers to how routers work together using routing protocols to determine the good paths (or good routes as we call them) over which the packets travel from the source to the destination node.

What is the main idea behind a link-state routing algorithm?

• 在 link state routing algorithm / protocol 中，所有節點都知道鏈路成本和網絡拓撲（例如通過廣播這些值）。
• Based upon Djikstra’s algorithm.
• Start with N’ just containing the source node. Initialize all paths to infinity except directly attached nodes. Perform iterations and update whenever we find lower costs until every node is examined and added to N’.

What is an example of a link-state routing algorithm?

Open Shortest Path First (OSPF)

Walk through an example of the link-state routing algorithm.

At each iteration, look among nodes not yet in N’, select the node with least cost from the previous iteration. Update distance for all immediate neighbors of this node using the lowest cost paths.

What is the computational complexity of the link-state routing algorithm?

O(n²)

What is the main idea behind the distance vector routing algorithm?

• Based upon the Bellman-Ford algorithm.
• Iterative (continues until no more updates)
• Asynchronous (nodes do not have to be synchronized with each other)
• Distributed (no need to know network topology or have some central point of calculation)

Walk through an example of the distance vector algorithm.

The DV routing algorithm 基於 Bellman Ford 算法。每個節點都維護自己的距離向量，以及到達網絡中每個其他節點的成本。然後每個節點不時地將自己的距離向量發送到其相鄰節點。鄰居節點依次接收該距離向量，並使用它來更新自己的距離向量。換句話說，相鄰節點交換它們的距離向量來更新它們自己的網絡視圖。

When does the count-to-infinity problem occur in the distance vector algorithm?

When a large change occurs across a link, causing an infinite number of updates to be propagated across nodes. This can continue to happen until the nodes’ tables eventually converge. This can happen if nodes have large positive or negative numbers.

How does poison reverse solve the count-to-infinity problem?

When one node knows there is a path through another node, it will poison the opposite path so it is never taken. When bad news comes, it will take the opposite path and pass on this information so the new path is quickly used and the previous path becomes poisoned.

• This solves the problem with 2 nodes but is not guaranteed to work for 3 or more nodes that are not directly connected.

What is the Routing Information Protocol (RIP)?

The Routing Information Protocol (RIP) is based on the Distance Vector protocol. It uses hop count as the metric (each link = 1 cost). Uses RIP response message instead of distance vectors. Each node maintains a RIP Table (Routing Table), which will have one row for each subnet in the AS.

What is the Open Shortest Path First (OSPF) protocol?

OSPF 是一種路由協議，它使用 link-state routing algorithm 來尋找源路由器和目標路由器之間的最佳路徑。

• OSPF 是作為 RIP 協議的改進而引入的，在上層 ISP 中運行。
• It is a link-state protocol that uses flooding of link-state information and a Dijkstra least-cost path algorithm.
• Advances include authentication of messages exchanged between routers, the option to use multiple same cost paths, and support for hierarchy within a single routing domain.

How does a router process advertisements?

The router checks if advertisement is new or duplicate by referring to the link-state database. If its new, it updates this database and runs OSPF based on current topology. It floods the LS update and updates FIB.

What is hot potato routing?

hot potato routing is a technique/practice of choosing a path within the network, by choosing the closest egress point based on intradomain path cost (Interior Gateway Protocol/IGP cost).