Link State Routing (OSPF)

Link-state routing is the second major class of intradomain routing protocol. The basic idea behind link-state protocols is very simple: Every node knows how to reach its directly connected neighbors, and if we make sure that the totality of this knowledge is disseminated to every node, then every node will have enough knowledge of the network to build a complete map of the network. This is clearly a sufficient condition (although not a necessary one) for finding the shortest path to any point in the network.

link-state routing protocols rely on two mechanisms: reliable dissemination of link-state information, and the calculation of routes from the sum of all the accumulated link-state knowledge.

Reliable Flooding

Reliable flooding is the process of making sure that all the nodes participating in the routing protocol get a copy of the link-state information from all the other nodes. As the term “flooding” suggests, the basic idea is for a node to send its link-state information out on all of its directly connected links, with each node that receives this information forwarding it out on all of its links. This process continues until the information has reached all the nodes in the network.

each node creates an update packet, also called a link-state packet (LSP), that contains the following information:

• the ID of the node that created the LSP
• a list of directly connected neighbors of that node, with the cost of the link to each one
• a sequence number
• a time to live for this packet

Consider a node X that receives a copy of an LSP that originated at some other node Y. Note that Y may be any other router in the same routing domain as X. X checks to see if it has already stored a copy of an LSP from Y. If not, it stores the LSP. If it already has a copy, it compares the sequence numbers; if the new LSP has a larger sequence number, it is assumed to be the more recent, and that LSP is stored, replacing the old one. A smaller (or equal) sequence number would imply an LSP older (or not newer) than the one stored, so it would be discarded and no further action would be needed. If the received LSP was the newer one, X then sends a copy of that LSP to all of its neighbors except the neighbor from which the LSP was just received. The fact that the LSP is not sent back to the node from which it was received helps to bring an end to the flooding of an LSP. Since X passes the LSP on to all its neighbors, who then turn around and do the same thing, the most recent copy of the LSP eventually reaches all nodes.

Each node generates LSPs under two circumstances. Either the expiry of a periodic timer or a change in topology can cause a node to generate a new LSP. However, the only topology-based reason for a node to generate an LSP is if one of its directly connected links or immediate neighbors has gone down. The failure of a link can be detected in some cases by the link-layer protocol. The demise of a neighbor or loss of connectivity to that neighbor can be detected using periodic “hello” packets. Each node sends these to its immediate neighbors at defined intervals. If a sufficiently long time passes without receipt of a “hello” from a neighbor, the link to that neighbor will be declared down, and a new LSP will be generated to reflect this fact. One of the important design goals of a link-state protocol’s flooding mechanism is that the newest information must be flooded to all nodes as quickly as possible, while old information must be removed from the network and not allowed to circulate.

Route Calculation

Once a given node has a copy of the LSP from every other node, it is able to compute a complete map for the topology of the network, and from this map it is able to decide the best route to each destination. The question, then, is exactly how it calculates routes from this information. The solution is based on a well-known algorithm from graph theory—Dijkstra’s shortest-path algorithm.

The algorithm is defined as follows:

M = {s}
for each n in N− {s}
C(n) = l(s, n)
while (N = M)
M = M ∪ {w} such that 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))

Each switch computes its routing table directly from the LSPs it has collected using a realization of Dijkstra’s algorithm called the forward search algorithm. Specifically, each switch maintains two lists, known as Tentative and Confirmed. Each of these lists contains a set of entries of the form (Destination, Cost, NextHop).

The algorithm works as follows:

1. Initialize the Confirmed list with an entry for myself; this entry has a cost of 0.
2. For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP.
3. For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach this Neighbor as the sum of the cost from myself to Next and from Next to Neighbor. 
• If Neighbor is currently on neither the Confirmed nor the Tentative list, then add (Neighbor, Cost, NextHop) to the Tentative list, where NextHop is the direction I go to reach Next. 
• If Neighbor is currently on the Tentative list, and the Cost is less than the currently listed cost for Neighbor, then replace the current entry with (Neighbor, Cost, NextHop), where NextHop is the direction I go to reach Next.
4. If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to step 2.

The link-state routing algorithm has many nice properties: It has been proven to stabilize quickly, it does not generate much traffic, and it responds rapidly to topology changes or node failures. On the downside, the amount of information stored at each node (one LSP for every other node in the network) can be quite large.

The Open Shortest Path First Protocol (OSPF)

One of the most widely used link-state routing protocols is OSPF. The first word, “Open,” refers to the fact that it is an open, nonproprietary standard, created under the auspices of the IETF. The “SPF” part comes from an alternative name for linkstate routing.

 

LS age - The time, in seconds, since the LSA was generated. 
LSID (Link State ID) - The ID of the router that generated the LSA. 
Advertising Router - ID of the router that originated the LSA.
LS Seq (Link State Sequence) - The sequence number of the advertisement. Used to detect old or duplicate link state advertisements.  
Flags - Possible values:

• V - Router is the endpoint of an active virtual link that is using the area as a transit area. 
• ASBR - Router is an autonomous system boundary router (ASBR). 
• ABR - Router is an area border router (ABR).

 Link ID - Identifies the object to which this router link connects for each Link Type. Possible values:

•     If Link Type is PTP, then this is the neighboring router's router ID.
•     If Link Type is Transit, then this is the address of the designated router.
•     If Link Type is Stub, then this is the IP network or subnetwork number.
•     If Link Type is Virtual Link, then this is the neighboring router's router ID.

Link Data - Provides additional link information. Possible values:

•     If Link Type is PTP, then this is the MIB II index value for an unnumbered point-to-point interface.
•     If Link Type is Transit, then this is the IP address of the advertising router's interface.
•     If Link Type is Stub, then this is the network's IP address mask.
•     If Link Type is Virtual Link, then this is the IP address mask of the neighboring router.

Link Type - A description of the router link. Possible values:

•    PTP - Connection is point-to-point to another router.
•    Transit - Connection is to a transit network.
•    Stub - Connection to a stub network.
•    Virtual link - Connection is to a far-end router that is the endpoint of a virtual link.

Metric - Cost of using this outbound router link. With the exception of stub networks, this value must be other than 0. 

 

NUM_TOS :TOS information is present to allow OSPF to choose different routes for IP packets based on the value in their TOS field.