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.
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
Periodic or event driven
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).
Each node creates an update msg called LSP(Link state packet) and flood the network with it
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
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.