Forwarding & Routing

Question 1

Key network layer functions

Answer 1

• forwarding: move packets from router’s input to appropriate router output
• routing: determine route taken by packets from source to dest.
• forwarding: process of getting on the right flight at the airport
• routing: process of planning whole trip from source to destination

Question 2

Interplay between routing and forwarding

Answer 2

Question 3

Router architecture overview
High-level overview

Answer 3

Question 4

Input port functions

Answer 4

Question 5

Output port functions

Answer 5

• Buffering required when datagrams arrive from switch fabric faster than the outgoing transmission rate
• A scheduling discipline chooses among queued datagrams for next transmission

Question 6

Destination-based forwarding (CIDR)

Answer 6

• Question: address 128.42.222.198 matches four rows
  ¤ Which destination interface do we forward to?
• Answer: use longest prefix matching (so, dest. 1 in this case)
  ¤ Use the matching row with the longest string of 1’s in the mask
  ¤ This is the most specific match

Question 7

Longest prefix matching: an analogy

Answer 7

• I want to fly to Orange County, California
• I arrive at Manchester Airport (without a ticket, apparently!)
• I look at the departure board…
  – Flight to London, “gateway to the world”, departs gate 5
  
  • Destination is OK but very general – cf. 128.0.0.0/8
    – Flight to LA, California departs gate 6
  • Destination is more specific – cf. 128.42.128.0/16
    – Flight to Orange County, California departs gate 7
  • Destination is most specific – cf. 128.42.222.0/24
• These are ordered least specific to most specific – analogous to shortest to longest mask length
• I pick the most specific match (longest mask) => gate 7

Question 8

Longest prefix matching: a second example

Answer 8

Question 9

Per-router control plane

Answer 9

Routing algorithm components in each and every router interact with each other in control plane to build forwarding tables

Question 10

Logically centralised control plane

Answer 10

A distinct (typically remote) controller interacts with local control agents (CAs) in routers to compute forwarding tables

Question 11

Routing algorithms

Answer 11

• Goal: determine a “good” path through the network from source to destination
• What is “good”?
  ¤ Usually means shortest
  ¤ And/or Load balanced
  ¤ And/or lowest $$$ cost

Question 12

Problem setup

Answer 12

• Network is modeled as a graph
  ¤ Nodes are routers (can be subnets!)
  ¤ Edges are links
  ¤ Edge (link) cost:
  - delay, congestion level, etc.
• Initially, each node only knows
  ¤ Its local neighbors
  ¤ The cost to reach each neighbor
• How does each node learn the best path to every other node?

Question 13

Intra-domain routing protocols

Answer 13

• Distance vector
  ¤ Routing Information Protocol (RIP), based on Bellman-Ford algorithm
  ¤ Routers periodically exchange reachability information with neighbors
• Link state
  ¤ Open Shortest Path First (OSPF), based on Dijkstra’s algorithm
  ¤ Each network periodically floods its immediate reachability information to all other routers

¤ The Bellman-Ford and Dijkstra algorithms are alternative ways to find shortest paths between nodes in weighted digraphs

Question 14

Distance vector routing algorithm (BF)

Answer 14

Question 15

Distance vector initialization

Answer 15

Question 16

1st Iteration: B’s neighbors update their distance vectors

Answer 16

2nd Iteration: C’s neighbors update their distance vectors

Distance vector: end of 3rd Iteration
* Nothing changed, algorithm pauses…

Question 17

Distance vector summary

Answer 17

¤ Each router initially knows the cost of links to its direct neighbors
¤ As the algorithm proceeds, each router is learning new (provisional) “shortest paths” to every other router – this is embodied in its DV
¤ Routers send their DV to their neighbors periodically or when something changes
¤ On receipt of an incoming DV, routers look over the new set of options and update their DV if these options improve on the paths they currently know
¤ It’s an iterative process that converges to a set of shortest paths

Question 18

Q: How many “rounds” will it take for the DV algorithm to converge?

Answer 18

• Initial state: best one-hop paths
• One (simultaneous) round: best two hop paths
• Two (simultaneous) rounds: best three hop paths
• …
• k’th simultaneous round: best (k+1) hop paths
• Will eventually converge… when it reaches longest best paths

Question 19

Distance vector routing in practice

Answer 19

• Routing Information Protocol (RIP) (RFC 2453)
  ¤ Uses distance vector (Bellman-Ford algorithm)
  ¤ Updates sent every 30 seconds
  ¤ Originally in BSD UNIX, routed
  ¤ Widely-used for many years
  ¤ Used less now because of DV’s relatively weak adaptation to changes