CS331 · Chapter 8 · Annotated SlidesNetwork Layer: Routing of Packets
Original
Overview

Network Layer: Routing of Packets

How routers fill their tables: the internet as a weighted graph, static vs. dynamic routing, host-specific, network-specific and default routes, forwarding with masks (longest mask first), distance-vector (Bellman-Ford) vs. link-state (Dijkstra) routing, and autonomous systems with interior (RIP, OSPF, EIGRP) and exterior (BGP) protocols. Rebuilt from the highlighted copy of the deck until a clean one is uploaded, so a few figures show light highlighting.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 36 slides
  1. 1 Network Layer: Routing of Packets
  2. 2 Chapter 8: Outline
  3. 3 Routing (IP routing)
  4. 4 8-1 INTRODUCTION
  5. 5 8.1.1 General Idea
  6. 6 An Internet as a Graph
  7. 7 An internet and its graphical representation (Figure 8.1)
  8. 8 Graph representation of a network
  9. 9 Routing Algorithms Classifications
  10. 10 Routing algorithm: dynamic route operation
  11. 11 How to reduce number of entries in the routing table?
  12. 12 Host-specific versus network-specific method
  13. 13 Default Route
  14. 14 Forwarding of IP packets
  15. 15 Destination Address Forwarding
  16. 16 Classful addressing routing table
  17. 17 Example
  18. 18 Example
  19. 19 Example
  20. 20 Example: router R1’s networks
  21. 21 Forwarding table for router R1
  22. 22 Show the forwarding process if a packet arrives at R1 with the destination address 180.70.65.130.
  23. 23 Show the forwarding process if a packet arrives at R1 with the destination address 25.8.2.10.
  24. 24 Shortest Path Routing
  25. 25 Distance Vector (DV) Routing
  26. 26 The first-round distance vectors
  27. 27 Updating distance vectors (node B)
  28. 28 The distance vector corresponding to a tree
  29. 29 Least-cost trees for nodes for the previous network
  30. 30 Link State Routing
  31. 31 Link-state packets (LSPs) build the LSDB
  32. 32 Example of a link-state database (LSDB)
  33. 33 Comparison between distance vector and link state
  34. 34 Autonomous systems (AS)
  35. 35 A sample internet with four ASs
  36. 36 Popular routing protocols
Slide 1 / 36

Network Layer: Routing of Packets

Slide 1: Network Layer: Routing of Packets

Notes

  1. Routing vs. forwarding → graph model → static vs. dynamic → table tricks (network-specific, host-specific, default) → forwarding with masks → DV vs. LS → AS, IGP and BGP.

Slide 2 / 36

Chapter 8: Outline

Slide 2: Chapter 8: Outline
Slide 3 / 36

Routing (IP routing)

Slide 3: Routing (IP routing)

Notes

  1. Routing protocol = software that FILLS the routing table (routing) and uses it to pick the output interface (forwarding).

  2. Seen again Ch 7, slide 5: Routing vs. forwarding

Exam angle

PredictionQ1

Filling and updating routing tables by finding best paths is called:

Slide 4 / 36

8-1 INTRODUCTION

Slide 4: 8-1 INTRODUCTION

Notes

  1. The Internet is too big for one algorithm, so routing is hierarchical (inside each AS, then between ASs: slide 34).

Slide 5 / 36

8.1.1 General Idea

Slide 5: 8.1.1 General Idea

Notes

  1. Hosts just send to their default router; only routers need real forwarding tables.

Slide 6 / 36

An Internet as a Graph

Slide 6: An Internet as a Graph
Slide 7 / 36

An internet and its graphical representation (Figure 8.1)

Slide 7: An internet and its graphical representation (Figure 8.1)

Notes

  1. This A–G graph is reused in every DV and LS example below.

Slide 8 / 36

Graph representation of a network

Slide 8: Graph representation of a network

Notes

  1. Best path = minimum TOTAL cost from source to destination.

Exam angle

PredictionQ1

Which is NOT listed as a possible link cost metric?

Slide 9 / 36

Routing Algorithms Classifications

Slide 9: Routing Algorithms Classifications

Notes

  1. Trap Static routes do NOT update automatically after a failure.

Exam angle

PredictionQ1

Static routing updates automatically when a link fails.

PredictionQ2

Compare static and dynamic routing.

Compare with the model answer

Static: shortest paths are computed offline and entered manually by the administrator; they change slowly, can’t adapt to failures, and suit small networks. Dynamic: each router learns the network state by talking to its neighbours and fills its own table automatically, adapting to changes, at the cost of more router complexity.

Slide 10 / 36

Routing algorithm: dynamic route operation

Slide 10: Routing algorithm: dynamic route operation

Notes

  1. Routing protocols on neighbouring routers swap updates to keep tables current.

Slide 11 / 36

How to reduce number of entries in the routing table?

Slide 11: How to reduce number of entries in the routing table?

Notes

  1. Three ways to keep the table short or specific: network-specific, host-specific and default routes.

Slide 12 / 36

Host-specific versus network-specific method

Slide 12: Host-specific versus network-specific method

Notes

  1. Host-specific: one row per HOST (A, B, C, D via R1). Network-specific: one row for the whole network N2 → much smaller.

Exam angle

PredictionQ1

Listing one entry for a whole destination network instead of each host is:

Slide 13 / 36

Default Route

Slide 13: Default Route

Notes

  1. Default route 0.0.0.0/0 = “everything else”: here, go to R2 (towards the Internet).

Exam angle

PredictionQ1

The default route is written as:

Slide 14 / 36

Forwarding of IP packets

Slide 14: Forwarding of IP packets
Slide 15 / 36

Destination Address Forwarding

Slide 15: Destination Address Forwarding
Slide 16 / 36

Classful addressing routing table

Slide 16: Classful addressing routing table

Notes

  1. Try each mask on the destination; the first row that matches wins. /32 = a host-specific row, /0 = default.

Slide 17 / 36

Example

Slide 17: Example

Exam angle

PredictionQ1

Using the table, a packet for 14.5.6.7 leaves through:

Slide 18 / 36

Example

Slide 18: Example
Slide 19 / 36

Example

Slide 19: Example

Exam angle

PredictionQ1

A /32 row in a routing table is a:

Slide 20 / 36

Example: router R1’s networks

Slide 20: Example: router R1’s networks

Notes

  1. Four attached networks plus a path to the rest of the Internet through 180.70.65.200.

Slide 21 / 36

Forwarding table for router R1

Slide 21: Forwarding table for router R1

Notes

  1. Rows are sorted from the LONGEST mask (/26) to the shortest (/22), with the default (/0) last. Longest match wins.

  2. Memory trick Longest prefix first, default last.

Slide 22 / 36

Show the forwarding process if a packet arrives at R1 with the destination address 180.70.65.130.

Slide 22: Show the forwarding process if a packet arrives at R1 with the destination address 180.70.65.130.

Notes

  1. /26 gives .128 (the row wants .192) → no. /25 gives .128 → match → m0.

Exam angle

PredictionQ1

Using R1’s table, a packet for 201.4.22.35 leaves through:

PredictionQ2

Using R1’s table, a packet for 201.4.18.7 leaves through:

Slide 23 / 36

Show the forwarding process if a packet arrives at R1 with the destination address 25.8.2.10.

Slide 23: Show the forwarding process if a packet arrives at R1 with the destination address 25.8.2.10.

Exam angle

PredictionQ1

R1 receives a packet for 25.8.2.10. Walk through the forwarding steps.

Compare with the model answer

Apply /26 → 25.8.2.0 (no match), /25 → 25.8.2.0 (no), /24 → 25.8.2.0 (no), /22 → 25.8.0.0 (no). Nothing matches, so the default row 0.0.0.0/0 is used: send to next hop 180.70.65.200 through interface m2.

Slide 24 / 36

Shortest Path Routing

Slide 24: Shortest Path Routing

Exam angle

PredictionQ1

Link-state routing uses which algorithm?

PredictionQ2

Distance-vector routing is based on:

Slide 25 / 36

Distance Vector (DV) Routing

Slide 25: Distance Vector (DV) Routing

Notes

  1. Each router keeps distances to ALL destinations and sends that whole vector to its NEIGHBOURS, periodically or on change.

  2. Memory trick DV = “tell your NEIGHBOURS about the WHOLE world”. LS = “tell the WHOLE world about your NEIGHBOURS”.

Exam angle

PredictionQ1

Which is a distance-vector protocol?

Slide 26 / 36

The first-round distance vectors

Slide 26: The first-round distance vectors

Notes

  1. Round 1: only neighbour costs, everything else ∞.

Slide 27 / 36

Updating distance vectors (node B)

Slide 27: Updating distance vectors (node B)

Notes

  1. Bellman-Ford: new cost to X = min(old cost, cost to neighbour + neighbour’s cost to X).

Exam angle

PredictionQ1

B–A costs 2 and A’s cost to D is 3. B currently has D at ∞. After A’s update, B’s cost to D is:

PredictionQ2

State the Bellman-Ford update rule used in distance-vector routing.

Compare with the model answer

Dx(y) = min over neighbours v of [c(x, v) + Dv(y)]: the cost from x to y is the cheapest of “cost to a neighbour plus that neighbour’s advertised cost to y”, compared with the current value.

Slide 28 / 36

The distance vector corresponding to a tree

Slide 28: The distance vector corresponding to a tree

Notes

  1. A’s final vector: B 2, C 7, D 3, E 6, F 8, G 9.

Exam angle

PredictionQ1

In the slide’s graph, the least cost from A to G is:

Slide 29 / 36

Least-cost trees for nodes for the previous network

Slide 29: Least-cost trees for nodes for the previous network

Notes

  1. Every node ends up with its own least-cost tree.

Slide 30 / 36

Link State Routing

Slide 30: Link State Routing

Notes

  1. Every router builds the same map (LSDB) and runs Dijkstra itself. OSPF is link state.

Exam angle

PredictionQ1

Which is a link-state protocol?

PredictionQ2

In link-state routing, each router sends its link costs to its neighbours only.

Slide 31 / 36

Link-state packets (LSPs) build the LSDB

Slide 31: Link-state packets (LSPs) build the LSDB

Notes

  1. An LSP = “my neighbours and their costs”.

Slide 32 / 36

Example of a link-state database (LSDB)

Slide 32: Example of a link-state database (LSDB)

Notes

  1. All routers share the same LSDB (the whole map) but each computes its own tree.

Slide 33 / 36

Comparison between distance vector and link state

Slide 33: Comparison between distance vector and link state

Notes

  1. DV: to neighbours, estimates of everything, periodic, slow to react. LS: to all, exact neighbour costs, on change, fast.

Exam angle

PredictionQ1

Compare distance-vector and link-state routing (who receives updates, what is sent, when, and reaction to failure).

Compare with the model answer

Distance vector: sends to neighbours only; sends its estimated cost to every known destination; periodically (e.g. every 30 s); reacts to failures slowly. Link state: floods to all routers in the area; sends the exact cost of its own links to its neighbours; only when something changes; reacts to failures quickly.

PredictionQ2

Which reacts faster to a link failure?

Slide 34 / 36

Autonomous systems (AS)

Slide 34: Autonomous systems (AS)

Exam angle

PredictionQ1

Routing between autonomous systems is called:

Slide 35 / 36

A sample internet with four ASs

Slide 35: A sample internet with four ASs
Slide 36 / 36

Popular routing protocols

Slide 36: Popular routing protocols

Notes

  1. Interior: RIP, EIGRP (distance vector), OSPF (link state). Exterior: BGP (path vector).

  2. Memory trick Only one exterior protocol to know: BGP, the B is for Border.

Exam angle

PredictionQ1

Which protocol routes between autonomous systems?

PredictionQ2

EIGRP is a: