RIP (Routing Information Protocol)

rip (routing information protocol)
the routing information protocol (rip) is an intradomain routing protocol used inside an autonomous system. it is a very simple protocol based on distance vector routing. rip implements distance vector routing directly with some considerations:
1. in an autonomous system, we are dealing with routers and networks (links). the routers have routing tables networks do not.
2. the destination in a routing table is a network, which means the first column defines a network address.
3. the metric used by rip is very simple the distance is defined as the number of links (networks) to reach the destination. for this reason, the metric in rip is called a hop count.
4. infinity is defined as 16, which means that any route in an autonomous system using rip cannot have more than 15 hops.
5. the next-node column defines the address of the router to which the packet is to be sent to reach its destination.
figure below shows an autonomous system with seven networks and four routers. the table of each router is also shown. let us look at the routing table for rl. the table has seven entries to show how to reach each network in the autonomous system. router rl is directly connected to networks 130.10.0.0 and 130.11.0.0, which means that there are no next-hop entries for these two networks. to send a packet to one of the three networks at the far left, router rl needs to deliver the packet to r2. the next-node entry for these three networks is the interface of router r2 with ip address 130.10.0.1. to send a packet to the two networks at the far right, router rl needs to send the packet to the interface of router r4 with ip address 130.11.0.1. the other tables can be explained similarly.

link state routing
link state routing has a different philosophy from that of distance vector routing. in link state routing, if each node in the domain has the entire topology of the domain the list of nodes and links, how they are connected including the type, cost (metric), and condition of the links (up or down)-the node can use dijkstra s algorithm to build a routing table. figure below shows the concept.

the figure shows a simple domain with five nodes. each node uses the same topology to create a routing table, but the routing table for each node is unique because the calculations are based on different interpretations of the topology. this is analogous to a city map. while each person may have the same map, each needs to take a different route to reach her specific destination.
the topology must be dynamic, representing the latest state of each node and each link. if there are changes in any point in the network (a link is down, for example), the topology must be updatingd for each node. how can a common topology be dynamic and stored in each node? no node can know the topology at the beginning or after a change somewhere in the network. link state routing is based on the assumption that, although the global knowledge about the topology is not clear, each node has partial knowledge: it knows the state (type, condition, and cost) of its links. in other words, the whole topology can be compiled from the partial knowledge of each node. figure below shows the same domain as in figure above, indicating the part of the knowledge belonging to each node.

node a knows that it is connected to node b with metric 5, to node c with metric 2, and to node d with metric 3. node c knows that it is connected to node a with metric 2, to node b with metric 4, and to node e with metric 4. node d knows that it is connected only to node a with metric 3. and so on. although there is an overlap in the knowledge, the overlap guarantees the creation of a common topology-a picture of the whole domain for each node.

building routing tables
in link state routing, four sets of actions are required to ensure that each node has the routing table showing the least-cost node to every other node.
1. creation of the states of the links by each node, called the link state packet (lsp).
2. dissemination of lsps to every other router, called flooding, in an efficient and reliable way.
3. formation of a shortest path tree for each node.
4. calculation of a routing table based on the shortest path tree.

creation of link state packet (lsp) a link state packet can carry a large amount of information. for the moment, however, we assume that it carries a minimum amount of data: the node identity, the list of links, a sequence number, and age. the first two, node identity and the list of links, are needed to make the topology. the third, sequence number, facilitates flooding and distinguishes new lsps from old ones. the fourth, age, prevents old lsps from remaining in the domain for a long time. lsps are generated on two occasions:
1. when there is a change in the topology of the domain. triggering of lsp dissemination is the main way of quickly informing any node in the domain to updating its topology.
2. on a periodic basis. the period in this case is much longer compared to distance vector routing. as a matter of fact, there is no actual need for this type of lsp dissemination. it is done to ensure that old information is removed from the domain.
the timer set for periodic dissemination is normally in the range of 60 min or 2 h based on the implementation. a longer period ensures that flooding does not create too much traffic on the network.
flooding of lsps after a node has prepared an lsp, it must be disseminated to all other nodes, not only to its neighbors. the process is called flooding and based on the following:
1. the creating node sends a copy of the lsp out of each interface.
2. a node that receives an lsp compares it with the copy it may already have. if the newly arrived lsp is older than the one it has (found by checking the sequence number), it discards the lsp. if it is newer, the node does the following:
a. it discards the old lsp and keeps the new one.
b. it sends a copy of it out of each interface except the one from which the packet arrived. this guarantees that flooding stops somewhere in the domain (where a node has only one interface).
3-formation of shortest path tree: dijkstra algorithm after receiving all lsps, each node will have a copy of the whole topology. however, the topology is not sufficient to find the shortest path to every other node a shortest path tree is needed.
a tree is a graph of nodes and links one node is called the root. all other nodes can be reached from the root through only one single route. a shortest path tree is a tree in which the path between the root and every other node is the shortest. what we need for each node is a shortest path tree with that node as the root.
the dijkstra algorithm creates a shortest path tree from a graph. the algorithm divides the nodes into two sets: tentative and permanent. it finds the neighbors of a current node, makes them tentative, examines them, and if they pass the criteria, makes them permanent. we can informally define the algorithm by using the flowchart in figure 22.22.

let us apply the algorithm to node a of our sample graph in figure below. to find the shortest path in each step, we need the cumulative cost from the root to each node, which is shown next to the node. the following shows the steps. at the end of each step, we show the permanent (filled circles) and the tentative (open circles) nodes and lists with the cumulative costs.

1. we make node a the root of the tree and move it to the tentative list. our two lists are permanent list: empty tentative list: a(0)
2. node a has the shortest cumulative cost from all nodes in the tentative list. we move a to the pennanent list and add all neighbors of a to the tentative list. our new lists are permanent list: a(0) tentative list: b(5), c(2), d(3)
3. node c has the shortest cumulative cost from all nodes in the tentative list. we move c to the permanent list. node c has three neighbors, but node a is already processed, which makes the unprocessed neighbors just b and e. however, b is already in the tentative list with a cumulative cost of 5. node a could also reach node b through c with a cumulative cost of 6. since 5 is less than 6, we keep node b with a cumulative cost of 5 in the tentative list and do not replace it. our new lists are permanent list: a(0), c(2) tentative list: b(5), d(3), e(6)
4. node d has the shortest cumulative cost of all the nodes in the tentative list. we move d to the permanent list. node d has no unprocessed neighbor to be added to the tentative list. our new lists are
permanent list: a(0), c(2), d(3) tentative list: b(5), e(6)
5. node b has the shortest cumulative cost of all the nodes in the tentative list. we move b to the permanent list. we need to add all unprocessed neighbors of b to the tentative list (this is just node e). however, e(6) is already in the list with a smaller cumulative cost. the cumulative cost to node e, as the neighbor of b, is 8. we keep node e(6) in the tentative list. our new lists are
permanent list: a(0), b(5), c(2), 0(3) tentative list: e(6)
6. node e has the shortest cumulative cost from all nodes in the tentative list. we move e to the permanent list. node e has no neighbor. now the tentative list is empty. we stop our shortest path tree is ready. the final lists are
permanent list: a(0), b(5), c(2), d(3), e(6) tentative list: empty
calculation of routing table from shortest path tree each node uses the shortest path tree protocol to construct its routing table. the routing table shows the cost of reaching each node from the root. table 22.2 shows the routing table for node a. compare table 22.2 with the one in figure 22.14. both distance vector routing and link state routing end up with the same routing table for node a.