Routing vs forwarding, weighted-graph model & shortest paths

1. What are the three RFC 1918 private IPv4 address blocks?
   Stuck? Peek at 3.3 Network Address Translation (NAT): private ranges, NAPT & trade-offs

   • Private IPv4 ranges: 10.0.0.0/8, 172.16.0.0/12 (172.16..31.x.y), 192.168.0.0/16.
   • NAPT table: maps (Private IP, Private Port) ↔ (Public IP, NAT Port).
   • Rewrites: Outgoing → Source IP + Source Port; Incoming → Destination IP + Destination Port (+ checksums).

   Read lesson 3.3

2. When a destination IP matches both a /16 row and a /22 row in a router’s forwarding table, which row wins?
   Stuck? Peek at 3.1.5 Forwarding tables & Longest Prefix Match (LPM)

   • Match condition: Row N/n (mask M) matches destination D iff (D AND M) == N (i.e. D falls in [N .. N + 2³²⁻ⁿ − 1]).
   • Longest Prefix Match (LPM): Among all matching rows, pick the one with the largest prefix length n.
   • Default route 0.0.0.0/0: matches every address with n = 0 (used only if nothing else matches).

   Read lesson 3.1.5

3. In datagram packet switching, do all packets of a message have to follow the same path?
   Stuck? Peek at 1.2.2 Packet switching: store-and-forward, datagrams, statistical multiplexing

   • Packet switching: packets with headers; no reservation; full link rate while sending.
   • Store-and-forward: receive whole packet → buffer/queue → forward; full buffer → loss.
   • Datagram: each packet routed independently; may reorder; robust to failures.
   • Statistical multiplexing: share capacity on demand; P(exactly k of n) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.

   Read lesson 1.2.2

In Lesson 3.1.5 we saw how a router looks up a packet's destination IP in its forwarding table using Longest Prefix Match. Where did the rows inside that table come from?

No human sits at every router on the Internet typing millions of routes by hand! Routers run distributed routing algorithms that model the network as a weighted graph and continually compute the lowest-cost path to every destination.

In the network below, direct link A–C has cost 6, while links A–B (cost 2) and B–C (cost 3) take two hops. If router A wants to send a packet to C along the minimum-cost path, which neighbour should A hand the packet to?

Router A should hand the packet to B! Even though A → B → C is 2 hops instead of 1, its total cost is 2 + 3 = 5 < 6. Routing minimises total path cost, not necessarily hop count.

Forwarding (Data Plane) vs Routing (Control Plane)

Textbooks and GATE distinguish two jobs inside every router:

Weighted-Graph Primer & Shortest Paths

To design routing algorithms, we abstract a network as a weighted graph G = (V, E):

• Vertices (nodes) V = routers (or networks).
• Edges E = physical links joining neighbouring routers.
• Edge weight c(u, v) > 0 = the cost of link (u, v) (e.g., propagation delay, congestion level, monetary cost, or inverse bandwidth 1/B; if all links have weight 1, shortest path = minimum hop count).
• Path cost = sum of edge weights along the path; a shortest path from x to y is a path with minimum total cost.

Static vs Dynamic, and Intra- vs Inter-Domain Routing

Routing algorithms are classified along two axes:

• Static (non-adaptive) vs Dynamic (adaptive): Static routes are entered manually and do not react to link failures; dynamic algorithms automatically recompute routes when topologies or link costs change.
• Decentralised (Distance Vector, 3.4.2) vs Global (Link State, 3.4.4): Either each router knows only its neighbours' distances, or every router learns the full graph.

Putting it together

• Forwarding moves individual packets using the local forwarding table; routing runs network-wide algorithms to build those tables.
• Networks are modelled as weighted graphs where routers are nodes and links have positive costs.
• Each router stores only the total shortest-path cost and the first hop (next-hop neighbour) toward each destination.

• Shortest path ≠ fewest hops! Unless all link weights are equal, a 3-hop path of low-cost links beats a 1-hop high-cost link.
• A router does NOT store the entire path in a standard IP routing table — it stores only the next hop (and total cost); each subsequent router makes its own independent next-hop decision.

Routing draws the map (slow, network-wide); Forwarding turns the steering wheel at one junction (fast, local).

When you can see the whole graph on paper, finding the shortest path is easy. Next question (3.4.2): How can Router A find that A → B → C → D has cost 7 when Router A cannot see the whole network and can only talk to its immediate neighbours B and C?

1. MCQ

   Which statement correctly distinguishes forwarding from routing?

   1. Forwarding is a network-wide calculation of shortest paths; routing is a local table lookup.
   2. Forwarding moves a packet from an input interface to an output interface using a local table; routing is the distributed process that computes the tables.
   3. Forwarding happens only at Layer 2 switches; routing happens only at Layer 3 routers.
   4. Forwarding runs every 30 seconds; routing runs on every arriving bit.
2. NAT

   In a network with routers P, Q, R, and S, the link costs are: (P,Q)=4, (P,R)=1, (R,Q)=2, (Q,S)=3, (R,S)=6. What is the shortest-path cost from P to S?

   Write your answer before opening the key.

3. MCQ

   In the same network ((P,Q)=4, (P,R)=1, (R,Q)=2, (Q,S)=3, (R,S)=6), what is Router P’s next-hop neighbour for packets destined to S?

   1. Q
   2. R
   3. S
   4. P
4. MSQ

   Which of the following statements about routing metrics and classifications are TRUE?

   1. If every link is assigned a weight of 1, a shortest-path routing algorithm finds minimum-hop paths.
   2. Dynamic routing algorithms automatically recompute routes when link costs or topologies change.
   3. In a standard IP routing table, a router stores the complete sequence of all intermediate routers to each destination.
   4. Intra-domain routing operates within a single Autonomous System (AS).

• Forwarding = local per-packet lookup (data plane); Routing = network-wide shortest-path computation (control plane).
• Graph model: routers = vertices V, links = edges E with positive cost c(u, v).
• Routing table entry at u for d: stores (Destination d, Cost D_u(d), Next Hop = first neighbour along shortest path).

• routing vs forwarding
• routing algorithm
• routing table
• weighted graph
• edge cost
• path cost
• shortest path
• static vs dynamic routing
• intra- vs inter-domain routing (AS, RIP, OSPF, BGP — Foundation)

1. Difference between forwarding and routing?
   Reveal answer

   Forwarding is the local per-packet action of moving a packet to an output interface; routing is the network-wide algorithm that computes the routing/forwarding tables.
2. If all link costs equal 1, what does shortest-path routing minimise?
   Reveal answer

   Hop count (number of links traversed).
3. If the shortest path from A to D is A → B → C → D, what next hop does A store for D?
   Reveal answer

   B (the immediate neighbour along the shortest path).

• Next-Hop Extraction Rule: If the shortest path from S to D is S → X → Y → D, then S's routing table entry for D has Next Hop = X (the immediate neighbour) and Cost = total path cost. — converting a shortest-path tree into a router's table.
• Triangle Inequality Check: Direct edge (u, v) is NOT the shortest path whenever some third node w satisfies c(u, w) + c(w, v) < c(u, v). — spotting bypassed direct links in weighted graph questions.