CS 164 : Slide Set 9 : Internetworking — Routing.

CS 164 : Slide Set 9 : Internetworking -- Routing.

In this set . Distance Vector Routing -- Distrubuted Bellman Ford – Routing Information Protocol or RIP Link State Routing -- Dijkstra’s – Open Shortest Path First or OSPF

Distance Vector Routing Completely decentralized No node has complete information about the costs of all network links Gradual calculation of path by exchanging information with neighbors – Remember -- network as a graph ?

Specifics Each node constructs a one-dimensional array containing the “distances” or “costs” to all other nodes (as it relates to its knowledge) and distributes it to its immediate neighbors. Key thing -- each node knows the cost of links to its neighbors. If no link exists between two nodes, the cost of a direct link between the nodes is “infinity”.

Representation The cost from X to Y via Z is the cost from X to Z plus the “minimum” cost from Z to Y. Dx (Y,Z) C(X, Z) minW{Dz(Y,W)} LHS -- Cost from X to Y via Z RHS -- first term -- cost to go to Z -- second term -- minimum cost to go from Z to Y. Minimum cost from Z to Y computed by taking all possible paths into consideration.

An Example A B C D E F G B C A D A 0 1 1 1 1 E F G B 1 0 1 C 1 1 0 1 Internal Information at each node ----- D 1 0 1 E 1 0 F 1 0 1 G 1 1 0

Routing Tables B A Next Hop B 1 B C 1 C D - E 1 E F 1 F G - D E F Cost C G With this information, routing table at A is --

Evolution of the table. Each node sends a message to neighbors with a list of distances. F -- A with G is at a distance 1 C -- A with D at distance 1. B C A D E F G Cost Next Hop B 1 B C 1 C D 2 C E 1 E F 1 F G 2 F

Final Distance Matrix A B C D E F G B C A D A 0 1 1 2 1 1 2 E F G B 1 0 1 2 2 2 3 C 1 1 0 1 2 2 2 D 2 2 1 0 3 2 1 E 1 2 2 3 0 2 3 F 1 2 2 2 2 0 1 G 2 3 2 1 3 1 0

Convergence In the absence of topological changes -- few exchanges between neighbors before complete routing table is formed. This table is consistent. Convergence is achieved. Notice -- no centralized authority

Routing updates When are routing updates sent ? 1. Periodic updates – Even if nothing has changed, send periodically. Main reason is to let other nodes know that the sender is alive. – Refresh information that might be needed if some of the routes were to become unavailable. 2. Triggered updates – o When a node receives an update from one of its neighbors which may lead to a change in its routing tables (could be due to change in link cost). Note: typically order of periodicity is seconds to several minutes.

Link/Node Failures Nodes that first notice send new lists of distances to neighbors. How do they detect failures ? – Route updates don’t arrive – Probing with test packets.

Example Revisited Let link from F to G fail. F sets new distance to G to ; sends update to A. A was initially routing to G via F. So it now sets link cost to G to . Next update from C; A learns that C has 2 hop path to G. A now can reach G in 3 hops via C. A sends an update to F. Thus, F now, can reach G via A in 4 hops. B C A D E F G

Count to Infinity A discovers that link to E is lost. If before A’s message (saying that link cost to E is ) is received, if B or C advertise that they can reach E in two hops, then A can be confused. Another possibility, B gets A’s update followed by C’s update which says that E is reachable in 2 hops. So B tells A this, and A thinks it can now reach E via B in 3 hops. This information reaches C who now thinks that it can reach E in 4 hops via A. The process continues and thus, the system does not stabilize. This is the count to infinity problem. B C A D E F G

Split Horizon One solution would be to approximate to say 16 hops. With Split Horizon, when a node sends a routing table update to its neighbors, it “does not” send those routes it learned from “a particular” neighbor, back to that neighbor. – For example, B had E, 2, A. When it sends a route update to A, it does not include this. With split horizon with poison reverse, this update is reported but the link weight is set to . – For example B sends (E, ) to A.

Does this work ? Works only if there is a loop with only 2 nodes. Typically, in static networks where link failures/node failures are rare, this may be enough. Speed of convergence is why, link state routing may be preferable -- it takes a while before routes converge.

Purging routing entries Each routing entry has a time-to-live (or TTL) field. A counter -- initially set to MaxTTL. This is then decremented and if TTL 0, then, time to purge the entry.

RIP Stands for Routing Information Protocol Built based on distance vector routing. In the Internet, goal of routers is to learn how to forward packets to various networks.

An Example of RIP Routers advertise the cost of reaching networks. In this example, C’s update to A would indicate that C can reach Networks 2 and 3 with cost 0, Networks 5 and 6 with cost 1 and Network 4 with cost 2. 1 4 A B 2 5 C 3 D 6

RIP Packet 0 8 Command 16 Version Family of net 1 31 Must be zero Address of net 1 Address of net 1 Distance to net 1 Family of net 2 Address of net 2 Address of net 2 Distance to net 2 Essentially contains the networks that can be reached and the distances to each.

Other RIP Details Routing tables are exchanged every 30 seconds using the RIP advertisement. If a router does not hear from its neighbor once every 180 seconds, the neighbor is deemed unreachable. The router that detects this will modify its routing table and propagate the information.

RIP implementation RIP packets are sent using UDP. Typically, there is a routing daemon (routed) that is an application layer process that provides access to routing tables. Allows for the access of the tables. Use “netstat -rn” to view routing table at host.

Link State Routing Initial state : similar to distance vector i.e., state of link to neighbors known (up/down). goal: To find the path of least cost to destination. Basic Idea -- Every node knows how to reach its neighbors. If this info is dissemination to every node, every node ultimately has the info. to build the complete map of the network.

Mechanisms Two mechanisms: – Reliable dissemination of link state information -process is called reliable flooding. – calculation of routes using the collected information -the computation is based on Dijkstra’s algorithm.

Reliable Flooding Process of making sure that all the nodes participating in the link state routing protocol get a copy of the link-state info. from all other nodes. Each node sends out link-state info. on its directly connected links. Each node that receives this, forwards it.

Link State Information Each node creates a link-state packet (LSP) that contains: – ID of the node that created LSP – a list of directly connected nodes and the cost to each node. – sequence number – TTL } for reliability

An Example X receives LSP from some node Y. X checks to see if it already has an update from Y. If it does, it compares the sequence number in the new LSP to the one stored. If New seq no Old sequence number, then, discard LSP. Else -- store LSP and send the LSP to all neighbors except the one that sent the LSP. If no update from Y, keep it. X A C B D X A C B (a) X A C B (c) D (b) D X A C B (d) D

Dissemination of LSPs LSPs are sent periodically (upon the expiry of a timer) or may be triggered due to a change in topology (as in RIP). The only topology change that triggers the creation of a new LSP is a change to one of the directly connected links. – Failures detected by link layer protocol by using what are known as “HELLO” packets -probes to determine if neighbor is alive. To minimize overhead, LPSs are not created unless needed --periodicity is of the order of hours. Sequence numbers help in identifying new info and TTL helps in ensuring that packets don’t stay in the network indefinitely.

Graph abstraction Used for computation of shortest path using Dijkstra’s. Let N denote the set of nodes in the graph. l(i,j) denotes the non-negative cost or weight associated with the edge between nodes i and j. l(i,j) if there is no edge between i and j. Remember -- each node has entire map of network.

The Dijkstra’s Algorithm Let “s” which belongs to the set N, denote the node that executes the algorithm. Algorithm maintains M -- set of nodes incorporated so far by the algorithm. C(n) -- cost of the path from s to n. M {s} for each node n in N- {s}, C(n) l(s,n); while (N M), M M U {w} where C(w) is the minimum for all w in (N -M) for each n in (N-M), C(n) min(c(n), C(w) l(w,n)

An Example B 5 A Let s A. 3 10 C 11 2 D At next step, look at neighbors of A and B (we have C and D). We add C (via B). Then, we consider D, (note that we consider the link via C as well -- finally that is added. Initially M A. Now, minimum cost node is B (note that only two nodes can be considered). So add B to M. Finally, the tree with links AB, BC and CD is created.

Next time . Dijkstra’s shortest path algo in practice. OSPF Global Internet