6. Routing Approaches I¶

This note is all about the kings of routing and the kings of routers: IGPs, EGPs, Least-cost routing, trial and static routes, distance-vector

Kinds of Routing, Kinds of Routers¶

The Internet does not work by having a single giant routing protocol. The Internet is a network of networks. The best way to route on one may not be the best way on another (why not?)

• Networks differ: Physical size, number of hosts, number of routers, bandwidth, latency, failure rate, topology (densely vs. sparsely connected), support staff size, when built.

So, let's have all individual networks choose how to route insider their network (intradomain), and all networks agree on how to route between themselves and other networks (interdomain)

Interdomain and Intradomain Routing¶

Intradomain routing: means routing within a single network (technically an "autonomous system"). Protocols used are often called IGPs or Interior Gateway Protocols

Interdomain routing: routing between networks (ASes). The routing glue which binds many networks into the Internet! Protocols used are the EGPs or Exterior Gateway Protocols

• Only one is ever used at a time! All ASes agree

• Internet has used BGP since the mid 1900s

Least-Cost Routing¶

We wanted good routes: 1. Routes that work! State must not have any loops. Must not have any dead ends. Both of these 2. Routes that are in some way "good". Commonly this is done by minimizing some "bad" quantity which we might call cost -- hence least-cost routing 3. What else we might minimize: price, propagation delay, distance, unreliability, others.

Let's have a topology where we associate a cost with each edge. Our goal is to find the path with the smallest sum.

Where do the costs come from? 1. Generally, local to router: routers know the costs of their attached links 2. May be configured by an operator 3. May be determined automatically: OSPF (intradomain routing protocol) uses the link bandwidth. Higher bandwidth = smaller cost (gets highest-average-bandwidth paths)

Other notes: 1. Least cost routes are an easy way to avoid loops: no sensible cost metric is minimized by traversing a loop 2. Least cost routes are destination-based: only depends on the destination 3. They form a spanning tree: no loops 4. Shortest path really means least cost path 5. When weights are 1, these are the same thing -- the hop count

Trivial and Static Routes¶

Trivial Routes¶

There are a couple types of routes which are uninteresting, you probably get for free, We will often ignore. These are trivial routes 1. Route to yourself: with a cost of zero 2. If you have only one neighbor, a default route. Cost doesn't matter; it is the only way. Hosts with multiple neighbors usually have one anyway

Static Routes¶

Static routes are manually by an operator 1. Sometimes operator just knows what they want! 2. Hosts don't generally participate in routing protocols, so how do the routers know where the hosts are? Operator adds static route on router next to host

Distance-Vector Routing Protocols¶

Long history on the Internet. The prototypical DV protocol is RIP (Routing Information Protocol). There is also a strong relationship to Bellman-Ford shortest path algorithm.

Aside Routing vs. Forwarding¶

Routing 1. Communicate with other routers to determine how to populate tables for forwarding 2. Figuring out best friends by sharing magic numbers with neighbors

Forwarding 1. Looks up packet's destination in table and sends packet to given neighbor 2. Passing envelopes to our best friends

Bellman-Ford¶

Here is the serial Bellman-Ford algorithm

def bellman_ford(dst, routers, links):
    distance = {}
    nexthop = {}

    for r in routers:
        distance[r] = INFINITY
        nexthop[r] = None
    distance[dst] = 0

    for _ in range(len(routers) - 1):
        for (r1, r2, dist) in links:
            if distance[r1] + dist < distance[r2]:
                distance[r2] = distance[r1] + dist
                nexthop[r2] = r1

    return distance, nexthop

We can see things we recognize: 1. Magic number and best friend 2. Start with infinity (except destination) 3. Compare offer to current 4. Accept offer 5. Remember best friend

But we did it in parallel! and asynchronously! Also what is up with the for _ in range(len(routers) - 1)? Also, nobody new the whole topology!

Is Dijkstra's algorithm better? It is \(O(|E| + |V|\log |V|)\), and Bellman-Ford is \(O(|E||V|)\). It is not a fair comparison because Dijkstra's assumes you know everything about the topology.

Putting Together Distance-Vector¶

Keep processing updates/ advertisements from neighbors...

However, what if the router that gave you the magic number sends you another advertisement of a more terrible one?

Just update the one from the previous router? That's fine because if the R11 router gives you the 9 again, you'd update it.

Split Horizon¶

Router timers aren't synchonized with each other! Between offset timers, packet drops, triggered updates, advertisements can come in many orders

In following examples, let's show things that can happen, but doesn't mean they always will happen.

Lets begin with the A, R1, R2, R3 topology. R1 has its static connection to A, then sends the advertisement to R2, which sends it to R3. Now let' something terrible happen to the R1-R2 router. Since R3 will start sending back to R2. This is split horizon.

Why would you advertise a path back to the person who advertised it to you? Telling them about your entry going through them: doesn't tell them anything new, and can mislead them into thinking you have independent path.

Solution: if you are using a next-hop's path for some destination: don't advertise that destination to them!

Counting to Infinity¶

There is a scenario where R2-R3 will keep on advertising to each other with costs that they will accept. The tables will not converge in this case.

Solving split horizon also solves this scenario

Dealing with New Links¶

Have periodic updates when adding new links, so that it just works out

Failed Links¶

Solution: Each route only has a finite Time to Live. Gets recharged by the periodic advertisements. If you don't get a periodic update, expire and remove route