Routing

Forwarding and routing are different

Forwarding means taking a package, looking up its entry in forward table and sending it.
Routing is the process of building the forward table.

Routing table might look like this :
prefix | Next hop
18/8 | 171.1.1

And forward table might look like
prefix | Interface |MAC
18/8 | if0 |1:1:1:1:1:1:1:1

Forwarding table should use data structure that’s fast for look up and routing table should be fast for topology calculation.

The routing protocols described below are all Intradomain routing protocol or Interior gateway protocol (IGP). Domain here means An internetwork which all routers are under the same admin.

Distance-vector

Or Bellman-Ford algorithm O(VE)
Each node has a 1d vector of cost to reach all other nodes. Immediate links cost are known and all other are first set to + inf.
The process of getting this info for all nodes is called convergence. No nodes need global knowledge

Updates

Periodic or event driven

Problem with down link

If one link go down and update the cost to reach the node at other end to inf. It will try to learn a new way with lower cost to that node.
EG link between A and G goes down. cost of A -> G becomes inf.
Assume the networks look like B -> A -> G.
A might attempt to learn the route through B since B still has a cost of 2.
Then the cost of A-> G goes up to 3. B will update its cost to G to 4 and it goes on till the end of world…

Can use poison reverse to prevent route from sending routes learned from neighbour back to neighbour

Protocol using distance vector (RIP)

Routing information protocol. Routers will broadcast min distance to Network. Also a major constrain is the num of hops in RIP can be no more than 16.
Since 16 counts as infinity (because of the counting to inf problem mentioned abov).

Link state

Each node creates an update msg called LSP(Link state packet) and flood the network with it
It contains
1. ID of the node that created the LSP. 2. Node that’s directly link to the sending node. 3. A sequence number 4. TTL
The first 2 info is enough to calculate route. using Dijkstra

Comparison between Link state and Distance vector

Distance vector shares the distances to all nodes to each other | L-S shares knowledge of its neighbors with every other router in the network

Protocol using link state

OSPF Open Shortest path first protocol

Additional feature of OSPF

additional hierarchy allow use to partition domains into areas so routers within a network doesn’t need to know how to reach every networks in the same domain.
load balacing

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax