Description
Objective For this assignment, you will implement a shortest path routing algorithm. 2 Overview Like most link-state algorithms, OSPF uses a graph-theoretic model of network topology to compute shortest paths. Each router periodically broadcasts information about the status of its connections. OSPF floods each status message to all participating routers. A router uses arriving link state information to assemble a graph. Whenever a router receives information that changes its copy of the topology graph, it runs a conventional graph algorithm to compute shortest paths in the graph, and uses the results to build a new next-hop routing table. FIGURE 1: INTERN ET TOPOLOGY OSPF uses a directed graph to model an Internet. Each node in an OSPF topology graph either corresponds to a router or a network. If a physical connection exists between two objects in an Internet, the OSPF graph contains a pair of directed edges (one in each direction) between the two nodes that represent the objects. To enable routers to compute shortest paths, each edge in an OSPF graph is assigned a weight that corresponds to the cost of using the path. The identities of the links that are attached to a router together with their cost metrics are entered into a table (known as the circuit database).
2 Circuit Database for R1 Link Cost L1 2 L2 1 FIGURE 2: INIT IAL IZED CIRCU IT DATABASE Before a router can send any PDU to its neighbors it should first send a HELLO PDU to tell its neighbor that the router is ready to participate in the OSPF procedure. So at the beginning of the procedure each router sends a HELLO PDU to each of its neighbors. Each router sends to each of its neighbors a link state (LS) PDU containing the identifiers of the links to which the router is attached together with the cost values. In this way, a router receives some LS PDUs from each of its neighbors informing it of the links that are attached to it and their cost values. This information is stored in the link state database by the update process in the router. R1 From R2 – R2: L1,2/L3,4/L4,1/L6,4 R3 – R3: L2,1/L3,4/L5,3/L8,4 R2 From R1 – R1: L1,2/L2,1 R3 – R3: L2,1/L3,4/L5,3/L8,4 R4 – R4: L4,1/L5,3/L7,5 R5 – R5: L6,4/L9,2 | | | R7 From R4 – R4: L4,1/L5,3/L7,5 R5 – R5: L6,4/L9,2 R6 – R6: L8,4/L10,2 FIGURE 3: LIN K STAT E DAT ABA SE AFT ER FIRST SET OF LS PDUS When it has done this, the update process in each router sends a copy of the LS PDU to each of its neighbors (except the one that has sent the PDU and those from which it has not received a HELLO PDU yet; also the same message should be sent to a router only once to avoid loops). As a result, each router receives a further set of LS PDUs which have effectively originated from its neighbors’ neighbors. This procedure then continues. As can be deduced, over a period of time each router will receive a complete set of LS PDUs containing the identities of the links – and their path cost values – which are attached to all other routers in the Internet. Whenever a new set of LS PDUs is entered into the link state database, the router performs the Shortest Path First (SPF) algorithm on the link state database, and determines, from all the entries in