Distance routing protocols

    The aim of a distance routing protocol is for each router to have
    a list of accessible nets, the interface to use to reach each accessible
    net, and a distance to the net when using that interface.
    
    Each router exchanges with its neighbor router this table. The neighbor
    then updates its table depending whether what it learns provides for 
    a shorter route, and a route that uses a different interface.
    
    Each link between routers has a distance. We will call it 1 to 
    be simple. So the distance to a net is hop count. At first, a router 
    marks distance 0 that net it can deliver to locally, that is, for
    each interface, take that network port and put it in the table with
    distance zero. Any other net is distance infinity.
    
    It announces this table to its neighbors. If neighbor router R receives on
    interface I the annoucement that its' neighbor is distance from network
    N, then it has a candidate route to N of distance 1 via interface I.
    If there is no other and better route, it will enter (N,1) into its routing
    tables, and internally it will further note (N,I), that is, to get to
    N use interface I.
    
    R now announces, along with (N',0) for all N's that have directly matching
    networks as some interface of R, the distance (N,1). Routers which have no
    route to N will receives this and have an (N,2) that they can brag about
    to their neighbors. Again, internally the router notes which interface to
    use for each destination net, but this it doesn't need announce.
    
    Eventually this process converges.
    
    Routers are also configured with default routers. Since all networks
    in all the world can't be in the database, this is somehow for a family
    of local networks. For the rest, the router sends to a default router.
    But chain of defuatl routers, the packet reaches the edge of what is 
    considered local, the Autonomous Systems, and the packet is launched
    into the backbone, and a second level of routing.
    
    RIP is a distance routing protocol. What one saw was a router, running
    RIP would periodically dump its database of net, distance pairs to each
    neighbor.
    
Counting to infinity in distance vector protocols

    The problem with distance vector protocols is evidenced by this example
    network:
                  (a)-----(b)-----(c)
    At stability, b will be 1 away from all networks c delivers to, and a
    will be 2 away from those networks. assume c crashes. not receiving updates
    from c, b decides to recalculate the distance away from any network that
    was directly connected to c. 
    
    b receives a's advertisement of a distance 2 route and decides to get 
    to those networks, it will send packets to a, and it has distance 3 to
    those destinations. subsequently, a receives a new distance vector 
    from b, and now considers its distance to c to be 4. And so on.
    
    This is called counting to infinity. And it is why distance vector 
    protocols are often discouraged.
    
split horizon

    In the above situation, a technique called Split Horizon would speed
    convergence of the distance vector. A router using split horizon replaces
    the distance to some nets with infinity depending on which router receives
    the vector. If router R is on interface I, then all nets which use 
    interface I are replaced by distance infinity before the vector is sent
    to R.
    
    In the above example, even though b's distance vector would be {(c,1),
    (a,1)}, it would send to c the vector {(c,-),(a,1)} (where c stands
    for all networks zero distance from c, and a stands for all networks
    zero distance from a). Likewise, a would be sent the vector {(c,1),(a,-)}.
    a would send to b the vector {(b,-),(c,-)}. With these vectors, when
    c is lost, b would not be confused to route traffic for c through a, and
    it would immediately converge its distance to c as infinity.
    
    Split horizon is not a complete solution. This network still suffers from
    counting to infinity even with split horizon:
    
                       (a)
                        | \
                        | (d)----(c)
                        | /
                        (e)
    
poison reverse
    
    In the above scheme, the router either refrains from sending routing
    information back to the rounter, or explicitly marks those networks
    as unreachable. Our example used "-" to indicate infinity, and therefore
    the routing tables will quickly spread the news of the unreacability of
    the down net. This active use an infinite value, or some marker of the
    unreachability of the particular net, is called a poison reverse.


Link state protocols
    
    A link state protocol runs Djkstra's algorithm at each router to calculate
    shortest paths. Routers advertise the state of their links, the connections
    they have with neighboring routers, as well as the networks served by
    each router. The LSP's (link state packets) are flooded throughout the
    network. That is, a router receiving an LSP will broadcast it on all its
    other interfaces. Since this causes a muliplication of packets, the router
    must take care to do this only once for each LSP.