Link State Protocol: In-Band Hop-by-Hop Disseminations

3.4 Link State Routing Protocol

3.4.1 Link State Protocol: In-Band Hop-by-Hop Disseminations

First and foremost, in-band hop-by-hop basis is possible for link state information exchange since packets can be marked either as user data packets or routing packets to communicate link state information. How this is specifically done will be covered in detail for protocols such as OSPF in later chapters. For now, our discussion will be limited to the basic idea of link state protocol when in-band communication on a hop-by-hop basis is used for exchanging link state routing information.

We start with two important points:

• The link state information about a particular link in one part of a network to another part can traverse on a hop-by-hop communication basis to eventually spread it throughout the network; this is often referred to as flooding.

• On receiving link state information that is forwarded through the hop-by-hop basis, a node can do its own route computation in a distributed manner.

The second component is really related to performing route computation and can be de- coupled from the protocol itself. The first part is an essential part of the link state routing protocol.

F I G U R E 3.10 Six-node, eight-link network example.

LINKSTATEADVERTISEMENT ANDFLOODING

A link state message, often referred to as a link state advertisement (LSA), is generated by a node for each of its outgoing links, and each LSA needs to contain at least

Source node, Link ID, Link Cost (3.4.1)

which is then forwarded throughout the network. Certainly, we need to ask the question:

is the flooding reliable or unreliable? That is, is the information flooded received intact by each node in the network, or is it corrupted? From the discussion about a distance vector protocol, we know that routing information exchange using unreliable delivery mechanisms causes additional problems. Thus, since the early days of a distance vector protocol, we have learned one important thing: reliable delivery of routing information is important. We already saw its use in the loop-free distance vector protocol. You will find out that in fact almost all routing protocols since the early days of the basic distance vector protocol use reliable delivery of routing information. Henceforth, we will assume reliable flooding with the link state protocol.

We first examine the LSA format as given in protocol message (3.4.1). Consider the link that connects from node 1 to node 2 in Figure 3.10: this LSA will be generated by node 1;

however, the reverse direction, LSA for the same link from node 2 to node 1, will be generated by node 2. In other words, links in a link state protocol are directional (while directionality is not an issue for a distance vector protocol). To avoid any confusion between a bidirectional and a unidirectional link, we will use 1-2 to denote the bidirectional link that connects node 1 and node 2 while1→2 to denote the directional link from node 1 to node 2. In addition to the directional aspect, there is a critical issue we need to understand in regard to hop-by- hop traversal. Consider Figure 3.10, and the link costd12=1from node 1 to node 2, which needs to be disseminated. Thus, the link state information about the link that originates at node 1 and ends at node 2, that is for 1→2, would be generated at node 1 as the message

i=1, Link=1→2,d12=1, which can be written as 1,1→2, 1 in short; this message is forwarded to both nodes 2 and 4. These nodes can, in turn, forward (“flood”) on their outgoing links; for example, from node 2 to both node 4 and node 3. We can immediately see that node 4 would receive the same information in two different ways!

If the cost value of both the LSAs for the same link is the same, then it is not difficult to resolve. However, if the value is different, then a receiving node needs to worry about which LSA for a particular link was generated more recently. Consider the following illustration in terms of times event:

timet0: LSA 1,1→2, 1 is generated at node 1 and is sent to node 2 and node 4.

timet1: LSA 1,1→2, 1 is forwarded by node 2 to node 4.

timet2: 1→2fails; node 1 generates the new LSA 1,1→2,∞ to node 4.

timet3: LSA 1,1→2, 1 is received at node 4 from node 2.

From the above illustration, node 4 would receive LSA for the same link with two differ- ent cost values:∞first and then 1 next; however, the failure occurred afterward! We can see that the LSA needs to carry at least another piece of information that helps to identify LSA at a receiving node based on when it was generated. Thus, some way to time-stamp an LSA would then avoid any ambiguity. Thus, instead of using (3.4.1), LSA should contain a time stamp resulting in the format:

Source Node, Link ID, Link Cost, Time stamp (3.4.2)

The question is how to indicate a time stamp that works in a distributed networked envi- ronment. There are two possibilities: either all nodes are clock-synchronized through some geosynchronous timing system, or a clock-independent mechanism is used. While a geo- synchronous timing system is a good idea, until recently this was not feasible; furthermore, a separate mechanism independent of the protocol would be required. Most link state routing protocols use a clock-independent mechanism called sequence number to indicate the notion of a time stamp that can be defined within the context of the protocol. That is, a node, when it generates an LSA for an outgoing link, stamps it with a sequence number and the LSA then has the following modified format:

Source Node, Link ID, Link Cost, Sequence Number (3.4.3)

When the same node needs to generate a new LSA for the same outgoing link, it increments the sequence number counter, inserts this new value in the LSA message, and sends out the LSA packet. Going back to the previous example, if the sequence number for link1→2is 1 before failure, then the first LSA announcement would be 1,1→2, 1, 1. After failure at time t2, the sequence number counter would be incremented to 2, and the new LSA would be

1,1→2,∞, 2. Thus, when at timet3, node 4 receives LSAs for the same link from two different directions, it can check the sequence number and discard the one with the older sequence number, in this case, the one received from node 2 with sequence number 1.

It is important that each node maintains a different sequence number counter for each outgoing link, and that other nodes maintain their own sequence number counters for their outgoing links; in other words, there is no dependency among nodes, which is an advantage of using the concept of a source-initiated, link-based sequence number. There is, however, a key issue to consider: the size of the sequence number space. In any data network environ- ment, usually a fixed length field is used for the sequence number space. Suppose that the sequence number space is only 3 bits long; this would mean that it can take values 1 to 8,

and after it reaches 7, it would need to wrap around and start at 1 again. Here is the first problem we encounter due to wrapping of the sequence number. When a node receives two LSAs for the same link ID from two different neighbors, one with sequence number 7 and the other with sequence number 2, the receiving node has no way of knowing if the sequence number 2 is after the number is wrapped or before; in other words, the receiving node has no way of knowing which is more recent. This tells us that the size of the sequence number space should not be small. Typically, the sequence number space is a 32-bit field; in most cases, this would solve the problem. However, there is still some ambiguity, for example, when a node goes down and then comes back up with the sequence number set to one, or when a network is isolated into two separate networks. Essentially, what this means is that some additional safeguard is required to ensure that a receiving node is not confused. A possible way to pro- vide this safeguard is to use an additional field in LSA that tells the age of the LSA. Taking this information into account, the LSA takes the form:

Source Node, Link ID, Link Cost, Sequence Number, Age (3.4.4)

Now we describe how to handle the age field at different nodes. The originating node sets the starting age field at a maximum value; the receiving node decrements this counter periodi- cally while storing the link state information in its memory. When the age field reaches zero for a particular link, the link state information for this link is considered to be too old or stale.

The following is a classical example of what can happen if sequence number and age are not addressed properly.

Example 3.3 ARPANET operational problem due to sequence number and age.

From an operational environment, we can learn a lot about what does or does not work in practice. A case in point is the sequence and age field, as used and as observed through its early use in ARPANET. This example is very nicely described in [559], and is reproduced here.

ARPANET at that time used a 3-bit-long age field with 8 sec as the time unit. This means that the starting maximum age was 56sec(=7×8), which was decremented every 8 sec.

To avoid the age becoming stale by the time an LSA reaches a downstream node, each node needed to generate a new LSA for an outgoing link within 60 sec. When a node starts up (either initial activation, or if rebooted), it needed to wait for 90 sec before generating the first LSA. The idea was that this would allow any old LSA in the memory of the node to decrement the age counter to 0; at the same time, it can receive new LSAs from neighboring nodes.

ARPANET was found to be nonfunctional one night (these things always happen at night!) with the queue at a router filled with multiple LSAs from a specific router, say Z, where each of these LSAs had different sequence numbersa1,a2,a3 witha1<a2<a3and then wrap around toa1. Now, consider a router that has a stored LSA from Z with sequence number a1, and it receives an LSA with sequence number a2; it would overwrite the one in memory since a2>a1 and, in addition, it will flood this “new” LSA to its neighbors who in turn will update accordingly. This pattern of updating the sequence number was repeated.

It was found that LSAs did not age out. The problem was in the inherent assumption that the age counter will be decremented at a node every 8 sec. If a received LSA leaves a particular node within this 8 sec, its age field would not get decremented. However, it was originally envisioned that if a node receives an LSA and immediately sends it out, the age counter would get decremented. This simple logic problem caused the network to become

nonfunctioning.

In recent protocols, the sequence number space is large enough to avoid any such prob- lems; for example, a 32-bit signed sequence number space is used. Furthermore, in many protocol implementations, the sequence number space is considered as a lollypop sequence number space; in this scheme, from the entire range of possible numbers, two are not used.

For example, consider a 32-bit signed sequence number space. The sequence number is var- ied from the negative number−231+1 to the positive number231−2while the ends −231 and231−1are not used. The sequence number begins in the negative space and continues to increment; once it reaches the positive space, it continues to the maximum value, but cy- cles back to 0 instead of going back to negative; that is, it is linear in the negative space and circular in the positive space giving the shape of a lollypop and thus the name. The lollypop sequence number is helpful when a router, say R1, restarts after a failure. R1 announces the sequence number−231+1to its neighbor R2. The neighbor R2 immediately knows that R1 must have restarted and sends a message to R1 announcing where R1 left off as the last se- quence number before the failure. On hearing this sequence number, R1 now increments the counter and starts from the next sequence number in the next LSA. Note that not all protocols use lollypop sequence numbering—the complete linear sequence number space that starts at negative and continues to positive in a linear fashion is also used; if the maximum value is reached, other mechanisms such as flushing of LSA are used when the maximum positive value is reached.

LSAANDLSU

Along with LSA, there is another terminology commonly used: link state update (LSU). It is important to understand and distinguish LSA from LSU. An LSA is an announcement generated by a node for its outgoing links; a node receiving LSAs from multiple nodes may combine them in an LSU message to forward to other nodes.

Example 3.4 LSA and LSU.

Consider Figure 3.10. Here, node 1 generates the link state for1→4as 1,1→4, 1, 1, 60 using the originating age counter as 60 and sends to node 4. Similarly, node 2 generates the link state for2→4: 2,2→4, 1, 1, 60 and sends to node 4. Node 4 can combine these two LSAs along with the link state for link4→5, and assuming it takes one time unit to process, it decrements the age counter by one for the received LSAs and sends out the link state update to node 5 as

1,1→4, 1, 1, 59 2,2→4, 1, 1, 59 4,4→5, 2, 1, 60.

SPECIALCASES

How does a link state protocol handle special cases? There are two scenarios we consider here: a node going down and coming back up again, and a link going down and coming back up again. The node failure has an immediate impact on the sequence number and the age field since nodes are, after all, specialized computing devices. When a node is restarted, the sequence number space may be reinitialized to 1 again; this again leaves a receiving node wondering whether it has received a new or old LSA generated from the node that just recov- ered from a failure. While in some cases such an exception can be handled through additional attributes in an LSA, it is usually done through additional mini-protocol mechanisms along with the proper logic control within the framework of the link state routing protocol. For ex- ample, there are several aspects to address: (1) the clock rate for aging needs to be about the same at all nodes, (2) receiving, storing, and forwarding rules for an LSA need to take into account the age information, (3) the maximum-age field should be large enough (for exam- ple, an hour), and (4) if the sequence number is the same for a specific link that is received from two incoming links at a receiving node, then the age field should be checked to deter- mine any anomaly. Thus, typically a link state routing protocol consists of three subprotocol mechanisms:

• Hello protocol

• Resynchronization protocol

• Link state advertisement (normal).

The hello protocol is used for initialization when a node is first activated; this is somewhat similar to the hello protocol used in the loop-free distance vector protocol. In this case, the hello protocol is useful in letting neighbors know its presence as well as the links or neigh- bors to which it is connected and to learn about the rest of the network from its neighbor so that it can perform route computation and build a routing table. The hello protocol is also periodically invoked to see if the link is operational to a neighbor. Thus, the hello proto- col has both information push and information pull. The resynchronization protocol is used after recovery from a link or a node failure. Since the link state may have been updated sev- eral cycles during the failure, resynchronization is merely a robust mechanism to bring the network to the most up-to-date state at the nodes involved so that LSA can be triggered.

The resynchronization step includes a link state database exchange between neighboring nodes, and thus involves both information pull and push. The normal LSA by an originat- ing node is information push. The entire logic control for a link state protocol is shown in Figure 3.11.

We will illustrate the need for the resynchronization step in the following example. Note that this step is also called “bringing up adjacencies.”

Example 3.5 Need for resynchronization.

We will use the same network as the one shown in Figure 3.10. We will start by assum- ing that the network has converged with all links having sequence number 1. We will also consider that the failure of link 4-5 occurred resulting in a new sequence number for each

Initialization:

– Use hello protocol to establish neighbor relation and learn about links from neighbors Link State Advertisement (normal):

– Generate LSA periodically (before the expiration of the age counter), incrementing the sequence number from the last time, and set the age field to the maximum value for this LSA; start the timer on the age field

Receive (new):

– Receive LSA about a new linkl→mfrom neighboring nodek

– Update the link state database and send LSA for this link to all neighbors (exceptk) – Start the timer for decrementing the age counter

Receive (normal):

– Receive LSA about known linkl→mfrom neighboring nodek

– Compare the sequence number to check if I have the most recent LSA for this link – If yes, send LSA for this link back to neighboring nodek

– If not, decrement the age counter, store the recent LSA for linkl→min the link state database, and forward it on all other outgoing links to the rest of the neighbors (except fork)

– If it is the same sequence number and the age difference is small, do nothing; if the age difference is large, store the most recent record

– Start the timer for decrementing the age counter Compute:

– Perform route computation using the local copy of the link state database – Update the routing table

Special Cases:

– Link failure: set the link cost to∞and send LSA immediately to neighbors – Link recovery: perform link state database resynchronization

– Node recovery: perform link state database resynchronization; alternately, flush records and perform hello protocol

– (Action mode when the age counter reaches 0 for a link ID):

(1) Do not consider this link in route computation

(2) Inform neighbors through advertisement stating that the age field is zero (3) Delete this link entry from the database

– (Receive mode with age 0): accept this LSA. This would set the age to zero, and thus, perform ‘action mode when age counter reaches 0.’ If the record is already deleted, ignore this advertisement.

F I G U R E 3.11 Link state protocol from the point of view of nodei(with in-band hop-by-hop communication for flooding).

direction with link cost set to∞; this information has also converged. Our interest is in the second failure, i.e., the failure of the second link,2-3. We show the two network states, before and after failure of link2-3, in Figure 3.12.

Note that when4-5fails, both its end nodes (node 4 and node 5) will increment the se- quence number count to 2 and generate the directional LSAs with cost set to∞to advertise to their neighbors. This information will be flooded throughout the network, and all nodes will eventually converge to having the link state database as shown in Table 3.3(a). When the second link2-3fails, we can see that the network will be isolated into two separate smaller networks. Node 2, on recognizing this failure, will increment the sequence number counter to 2 and generate an LSA for the directional link2→3 with cost set to∞; this will be dis- seminated which can reach only nodes 1 and 4. Similarly, node 3, on recognizing the same failure, will increment the sequence number counter to 2 and generate LSA for the directional link3→2with cost set to∞; this will be disseminated, which can reach only nodes 5 and 6.

Thus, in the network on the left side consisting of the nodes 1, 2, and 4, the link state database