Link State Routing

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 determine correct routes to any destination.

 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 link. This process continues until the information has reached all the nodes in the network. 

Link State Packet(LSP) contains the following information:

1.The ID of the node that created the LSP;

2. A list of directly connected neighbors of that node, with the cost of the link to each one;

3. A sequence number;

4. A time to live(TTL) for this packet.

Flooding works in the following way. When a node X receives a copy of an LSP that originated at some other node Y, it 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. The new LSP is then forwarded on to all neighbors of X except the neighbor from which the LSP was just received.

Each switch computes its routing table directly from the LSPs it has collected using a realization of Dijkstra's algorithm.

Every 10 S the average delay of all packets is computed.

( A longer measurement period = less adaptive routing if conditions actually change. A shorter measurement period = less optimal routing because of inaccurate measurement.) The delay is considered to have changed "by a significant amount" whenever the absolute value of the change exceeds a certain thershold. Threshold is a decreasing function of time. Threshold is decreased by 12.8 ms.

When the delay changes by only a small amount, it is not important routing changes. However, whenever a change in delay is long lasting, it is important that it should be reported eventually, even if it is small; otherwise, additive effects can introduce large inaccuracies into routing. A threshold value which is initially high but which decreases to zero over a period time has this effect. In this paper, the initial threshold is 64 ms. After each measurement period, the newly measured average delay is compared with the previously reported delay. If the difference does not exceed the threshold, the threshold is decreased by 12.8 ms. 

Whenever a change in average delay equals or exceeds the threshold, an update is generated, and the threshold is reset to 64 ms. Since the threshold will eventually decay to zero, an update will always be sent after a minute, even if there is no change in delay. 

Link state routing

A link-state routing protocol is one of the two main classes of routing protocols used in packet switching networks for computer communications (the other is the distance-vector routing protocol). Examples of link-state routing protocols include open shortest path first (OSPF) and intermediate system to intermediate system (IS-IS).

 The link-state protocol is performed by every switching node in the network (i.e. nodes that are prepared to forward packets; in the Internet, these are called routers). The basic concept of link-state routing is that every node constructs a map of the connectivity to the network, in the form of a graph, showing which nodes are connected to which other nodes. Each node then independently calculates the next best logical path from it to every possible destination in the network. The collection of best paths will then form the node'srouting table. 

This contrasts with distance-vector routing protocols, which work by having each node share its routing table with its neighbors. In a link-state protocol the only information passed between nodes is connectivity related. Link-state algorithms are sometimes characterized informally as each router 'telling the world about its neighbors

Determining the neighbors of each node[edit source | editbeta] First, each node needs to determine what other ports it is connected to, over fully working links; it does this using a reachability protocol which it runs periodically and separately with each of its directly connected neighbors. 

Distributing the information for the map[edit source | editbeta] Next, each node periodically and in case of connectivity changes makes up a short message, the link-state advertisement, which: Identifies the node which is producing it. Identifies all the other nodes (either routers or networks) to which it is directly connected. Includes a sequence number, which increases every time the source node makes up a new version of the message.

This message is then flooded throughout the network. As a necessary precursor, each node in the network remembers, for every other node in the network, the sequence number of the last link-state message which it received from that node. Starting with the node which originally produced the message, it sends a copy to all of its neighbors. 

When a link-state advertisement is received at a node, the node looks up the sequence number it has stored for the source of that link-state message. If this message is newer (i.e. has a higher sequence number), it is saved, and a copy is sent in turn to each of that node's neighbors. 

This procedure rapidly gets a copy of the latest version of each node's link-state advertisement to every node in the network. Networks running link state algorithms can also be segmented into hierarchies which limit the scope of route changes. These features mean that link state algorithms scale better to larger networks.