Dynamic routing and its risks - NicMcPhee/Models-of-Computing-Systems-in-class-projects GitHub Wiki

This is based on the material in Chap 7.4.1-7.4.3: "Routing and addressing" (p. 50) from Volume 2 of Saltzer & Kaashoek.

In-class exercise

Everyone will need a writing utensil and one or sheets of paper for their routing tables. I provided index cards for people to use as "network messages" indicating things like routing table updates.

  • Give everyone a random name.
  • This is optional, but I thought it would be useful. Since people don't know at the start who has what name, it helps keep them more "honest" about following the algorithm and not trying to employ "common sense" about how the routing should work.
  • That said, it did make it a little more difficult to talk about, so it might have been easier to have everyone just use their own name.
  • I used a random name generation site like http://listofrandomnames.com/ and then put the names on index cards when I passed out in class.
  • Have them identify who they're directly connected to.
  • I just had them use NSEW (north-south-east-west) to identify connections to the their immediate neighbors.
  • Note that some people will have fewer neighbors than others, which can usefully represent end points on the network.
  • Everyone should initialize their path vector table and their forwarding table.

Then everyone should repeat the following until the system reaches a stable state:

  • Use sheets of paper to send out their path vectors to their immediate neighbors.
  • Update their path vectors and forwarding table based on the info their receive from their neighbors.
  • Return the received sheets to the neighbor that sent them.
  • Managing all this paper turned out to be a pain.
  • It would have helped to have had them put their (real) names on their sheets so people would know who to return them to. When a student received sheets from four directions they didn't always know who to return them to, especially since the names on them weren't the students' real names.
  • If their path vector table was actually changed in the previous step, return to the first step and repeat.

Once the system has stabilized, demonstrate the ability to route messages through the network.

  • This took longer than I expected. We had 14 students and in well over half an hour we still hadn't stabilized. We were able to demonstrate some routing through significant parts of the "network", but not the whole network.
  • We also didn't have time to do any of the extra things that I would have liked to have done. Figuring out how to speed up the initial phase would be nice.

If there's time add/remove people from the network and/or add/remove links between people and see how long it takes to re-stabilize.

If there's time show how you can "hack" the algorithm by introducing "bogus" paths that route lots of traffic through a specific node (which can presumably then monitor/read that traffic – see below for examples of this happening in "real life").

Risks and problems

One key use of these routing algorithms is the Border-Gateway Protocol (BGP), and because BGP doesn't have any security mechanisms in place it can be manipulated to nefarious ends, e.g., Mystery traffic redirection attack pulls net traffic through Belarus, Iceland. Graduate students of UMM alum and UMTC CSci faculty Nick Hopper have identified ways to use problems with certain routers to "crash" parts of the Internet routing infrastructure: see "Taking Routers Off Their Meds: Why Assumptions Of Router Stability Are Dangerous" (1 pg abstract or full paper) if you want to learn more.