7. Routing Approaches II¶

This note is the final lecture on routing, which will finish up distance-vector protocols, talk about Link-State protocols, switches, and spanning tree protocol.

Review¶

If you have valid routing state, does that mean the network will never drop any packets? Answer: No

• Routing does not ensure reliable delivery of packets between end hosts. Routing may be necessary, but is not sufficient

Does "no loops, no dead ends" theorem only hold true for destination-based forwarding? Answer: No

• Same basic no loops or dead ends conditions generalizes to at least any othe rsystem that does deterministic forwarding based on fix packet headers (that is, it's not limited to destination-based routing)

Routing occurs when a data packet arrives at a router and is sent out another port. Answer: False

• When a packet arrives, router forwards it to one of its neighbors. Forwarding occurs when a data packet arrives at a router and is sent out another port

Finishing up Distance-Vector¶

From BF to DV¶

We refined our update rule, we resolved some wacky problems with split horizon, we ensured that we eventually converge instead of counting to infinity, we made it robust to packet drops/ordering by advertising periodically, we saw that we can adapt to new links easily, we can identify failed links and dead routes by missing advertisements.

Solution to Failed Links: Poison¶

Failed links become a big problem because you have to wait a long time for the TTL to expire all the way through.

• Key idea: instead of not advertising a route, actively advertise that you don't have a route. Do this by advertising an impossibly high cost (a poison route)

The poison route will propagate like other routes, poisoning the entry on any other router that was using it. It can be much faster than waiting for timeouts.

And this doesn't just work for timed advertisements. If you get a poison advertisement and it changes your table, it will trigger you to send poison so it propagates dead routes as fast as they can reach and be processed by neighbor.

• Can be much, much faster than waiting for timeouts

Besides expired routers, we also did not advertise when split horizon happens. In split horizon, we had a route but chose not to advertise.

• Don't want to advertise a route back to router that advertised it to us! Can lead to sending things bacwards (or even looping)

Instead of not advertising in this case, advertise infinite cost. We call this poison reverse.

In both cases (poisoning and poison reverse), without poisoning, you would not have sent a route. Instead, send an explicitly terrible route (any other route will be bettter), and never forward using these terrible infinite-length routes.

More Triggers¶

We know that our table changing should trigger us to send an update. Can be useful to handle other events too

1. Sometimes we can detect when a link becomes available. Immediately send new neighbor advertisements, no need to wait for timer
2. Sometimes we can detect when a link fails. Immediately poison all table entries using that link. If there are any, advertise the newly poisoned ones

Summing Up Distance-Vector¶

We now add to our list at the beginning: we can converge faster by explicitly signaling the absence of a route, we can adapte more quickly by advertising when "triggered" by events. This is now a pretty good routing protocol!

Link-State Routing¶

Another major class of routing protocols: Link-State routing. It is newer than Distance-Vector. It is also very common to use as an Interior Gateway Protocol.

Two major Examples: 1. IS-IS (Intermediate System to Intermediate System) 2. OSPF (Open Shortest Path First): used at Berkeley

DV vs. LS¶

DV:

• Uses Global computation (it's distributed across all nodes) using local data (from just itself and its neighbors)

LS:

• Uses local computation using global data (from all parts of the network)

Global Data¶

Global data is the state of every link in the network. It is up? What is the cost?

It contains information about: the state of links and the destinations. We use this info to build a complete map (global view) of topology.

If a router had global view, could easily comput paths

Every router:

• Gets the state of all links and location of all destinations

• Uses that global information to build full graph

• Finds paths from itself to every destination on graph

• Uses the second hop in those paths to populate its forwarding table

How to Find Paths?¶

Each router has the complete tpology; can basically do it however it wants! For least-cost routes, this is called Single Source Shortest Path (SSSP)

Some obvious algorithm choices:

• Bellman-Ford algorithm -- serial version -- \(O(|E||V|)\)

• Dijkstra's algorithm -- \(O(|E| + |V|\log |V|)\)

• Breadth First Search (hop count only) -- \(O(|E| + |V|)\)

• Dynamic shortest path algorithms -- time complexity varies

• Approximate shortest path algorithms -- various

• Parallel SSSP algorithms

But there is nothing that says you need to do least-cost routing!

Populating Tables¶

Important: Remember, each router can only influence its own next hop. Other routers must be coming up with paths which are "compatible".

It is pretty easy for least-cost routing if:

• Minimizing the same cost

• All costs are > 0

• All routers agree on topology

Given all those, don't even need to implement same exact algorithm (e.g., bread ties exactly the same)

How Do We Share Info Globally¶

All routers need info about all links between all routers, and all destinations.

Every router must:

• Find out who its neighbors are

• Tell everyone about its neighbors (i.e., its links to them)

• Tell everyone else about any adjacent destinations

Finding Your Neighbors¶

How do people do this? They introduce themselves.

Routers periodically send hello messages to neighbors. If a neighbor goes quiet, eventually assume they're gone

Telling Neighbors: Flooding¶

Exchanging hellos tells you who your neighbors are (local info), but we need to know who everyone's neighbors are!

The solution is called flooding.

Strawman solution:

• When local information changes, send to all neighbors.

• When you receive info packet from neighbor, send to all other neighbors

• Does this always work? What happens if there is a loop? It will go on forever... Two loops make exponential growth of information

Naive solution doesn't work when topology has loops. Solution?

• When local information changes, send to all neighbors.

• When you receive info packet from neighbor, send to all other neighbors (add on to the statement, unless you've already seen this info packet, in which case, drop it)

• How do you know if it is the first time you've seen it? Easy solution: routers put a sequence number in their updates.

Every router has its own sequence number

• When it sends a routing message, it puts it in the packet, and then increments it

• Every router tracks largest sequence number seen from every other router

• If it sees an update with a smaller/equal sequence number, the update is old -- drop it

• If it sees an update with a larger sequence number, the update is new, remember the sequence number and flood update to all other neighbors

If we used this protocol as an EGP? Scaling is not really that good

How do you make flooding reliable?

• Periodically resend it (same old trick)

• IS-IS and OSPF both do this

• But do more clever stuff too: delivers reliability faster without resending more often, but we won't explore this in detail in context of LS

Tell Everyone Else About Adjacent Destinations¶

By flooding iinfo about destinations too (e.g., static routes)

Flood info about destinations using same flooding mechanism you use to share information about router topology

Link State Convergence¶

Using plain non-parallel Dijkstra's algorithm. Dijkstra's will never find a looping path, so we never have loops in Link-State protocols... is this true? No!

• We only have control of our own next hop! If routers don't have same global view of topology, all bets are off!

Sources of convergence delay: 1. Time to detect failure 2. Time to flood link-state information (proportional to network diameter) 3. Time to re-compute paths/tables

Problems during convergence period: 1. Deadends 2. Looping packets 3. Out-of-order packets reaching the destination (should not cause semantic problems, but can create performance problems! We will see why later)

Timeline for Local Failure¶

1. Failure not detected: packets sent into dead link (dropped)
2. Detected, not recomputed: deadends
3. Detected, computed, not globally notified/computed: could be loops

As nodes become aware, routers may change. Continued loopings, and possible reorderings.

Link State Summary¶

Link state is super simple conceptually:

• Everyone floods link/destination information

• Everyone then has global map of network

• Everyone independently computes next hops

All the complexity is in the details

Learning Switches and Spanning Tree Protocol¶

Learning Switches¶

We've been looking at DV and LS protocols:

• Tables filled in by ongoing routing process

• Are seeded with static routes for destinations

• Very common for routing at the network layer (L3), like for IP addresses

Let's look at a very different approach to filling in our tables!

Learning switches:

• Tables filled in opportunistically using data packets (assume there is a path to B from A, so then flood it to the neighbors)

• No seeding with static entries required

• Very common for routing at the link layer (L2). many people would say it is not routing.

Rather than dropping the packet, it will opportunistically flood the packet to its neighbors, while updating a table saying it got it from the source.

Now, if B replies to A, then the table is filled in and we don't have to flood!

It breaks down if you have a loop...

• Major problem: floods when destination is unknown, floods have problems when topology has loops.

• The previous solution doesn't work in this case, but we will come back to it later.

The decision to flood is done on a switch-by-switch basis... packets are not purely flooded or purely point-to-point throughout their lifetimes. Instead at each switch, packets are sent out correct port if table entry exists, or flooded out all ports (except incoming) if not.