During this ospf state, routers have converged link-state databases.

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

First and foremost, an 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 and PNNI 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 decoupled from the protocol itself. The first part is an essential part of the link state routing protocol.

Link State Advertisement and Flooding

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

(3.4.1)

that 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 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.11: this LSA will be generated by node 1; however, in 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 bi-directional and a uni-directional link, we will use 1-2 to denote the bi-directional link that connects node 1 and node 2 while 1→2 denotes 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.11, and the link cost d12=1 from 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

that can be written as

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!

Figure 3.11. Six-node, eight-link network example.

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 the event time:

time t0:	LSA is generated at node 1 and is sent to node 2 and node 4.
time t1:	LSA is forwarded by node 2 to node 4.
time t2:	1→2 fails; node 1 generates the new LSA to node 4.
time t3:	LSA is received at node 4 from node 2.

From the above illustration, node 4 would receive LSA for the same link with two different cost values: ∞ first and then 1 next; however, the failure occurred afterward! We can see that the link state advertisement 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:

(3.4.2)

The question is how to indicate a time stamp that works in a distributed networked environment. There are two possibilities: either all nodes are clock-synchronized through some geosynchronous timing system, or a clock-independent mechanism is used. While geosynchronous 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 the 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:

(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 link 1→2 is 1 before failure, then the first LSA announcement would be

. After failure at time t2, the sequence number counter would be incremented to 2, and the new LSA would be

. Thus, when at time t3, 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 environment, 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 provide 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:

(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 periodically 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 [662] and is reproduced here.

In the early days, ARPANET used a 3-bit-long age field with 8 sec as the time unit. This means that the starting maximum age was 56 sec (=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 when initially activated or if rebooted), it needs 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 numbers a1,a2,a3 with a1 and then wrap around to a1. Now, consider a router that has a stored LSA from Z with sequence number a 1, 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 their databases accordingly. This pattern of updating the sequence number was repeated.

It was found that the 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 problems; 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 varied from the negative number −231+1 to the positive number 231−2 while the ends −231 and 231−1 are 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 cycles 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+1 to 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 sequence number before the failure. On hearing this sequence number, R1 now increments the counter and starts from the next sequence number in the next link state advertisement. 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 the link state advertisement are used when the maximum positive value is reached.

LSA and LSU

Along with LSA, there is another terminology commonly used that is called the 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.

Consider Figure 3.11. Here, node 1 generates the link state for 1→4 as

using the originating age counter as 60, and sends to node 4. Similarly, node 2 generates the link state for 2→4:

and sends to node 4. Node 4 can combine these two LSAs along with the link state for link 4→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

. •

Special Cases

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 recovered 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 example, there are several aspects to address here: 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 example, 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 determine any anomaly. Thus, typically a link state routing protocol consists of three sub-protocol mechanisms:

•

Hello protocol

•

Re-synchronization 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 neighbors to which it is connected and to learn about the rest of the network from its neighbors 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 protocol 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 several 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 the link state advertisement 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 link state advertisement by an originating node is information push. The entire logic control for a link state protocol is shown in Figure 3.12.

Figure 3.12. Link state protocol from the point of view of node i (with in-band hop-by-hop dissemination for flooding).

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.11. We will start by assuming 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 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 the failure of link 2-3, in Figure 3.13.

Figure 3.13. Six-node network: before and after failure of link 2-3 (assuming link 4-5 has already failed).

Note that when 4-5 fails, both its end nodes (node 4 and node 5) will increment the sequence number count to 2 and generate the directional LSAs with the 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 link 2-3 fails, 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 link 2→3 with cost set to ∞; this will be disseminated, and therefore 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 the LSA for the directional link 3→2 with the cost set to ∞; this will be disseminated and can only reach nodes 5 and 6. Thus, in the network on the left side consisting of the nodes 1, 2, and 4, the link state database will become as shown in Table 3.3(b), while for the network on the right side consisting of nodes 3, 5, and 6, the link state database will become as shown in Table 3.3(c). Notice the subtle difference in regard to the entry for directional links 2→3 and 3→2 since either side would not find out about the directional entry after the failure.

Table 3.3. Link state database as viewed before and after failure of link 2-3.

(a) Before Failure of Link 2-3 (as Seen by Every Node) Link-ID Cost Seq # 1→2 1 1 2→1 1 1 1→4 1 1 4→1 1 1 2→4 1 1 4→2 1 1 2→3 2 1 3→2 2 1 4→5 ∞ 2 5→4 ∞ 2 3→6 1 1 6→3 1 1 3→5 1 1 5→3 1 1 5→6 1 1 6→5 1 1	(b) After Failure of Link 2-3 (as Seen by Nodes 1, 2, 4) Link-ID Cost Seq # 1→2 1 1 2→1 1 1 1→4 1 1 4→1 1 1 2→4 1 1 4→2 1 1 2→3 ∞ 2 3→2 2 1 4→5 ∞ 2 5→4 ∞ 2 3→6 1 1 6→3 1 1 3→5 1 1 5→3 1 1 5→6 1 1 6→5 1 1	(c) After Failure of Link 2-3 (as Seen by 3, 5, 6) Link-ID Cost Seq # 1→2 1 1 2→1 1 1 1→4 1 1 4→1 1 1 2→4 1 1 4→2 1 1 2→3 2 1 3→2 ∞ 2 4→5 ∞ 2 5→4 ∞ 2 3→6 1 1 6→3 1 1 3→5 1 1 5→3 1 1 5→6 1 1 6→5 1 1

So far we have not discussed the issue of age of the LSA. In fact, for now, we will ignore it and will come back to it soon. Due to possible changes in the cost values of the links, each part of the network will evolve over time, which means an increase in the sequence number counter value for other links in the network, cost change, and so on. Now consider that the link 4-5 has recovered. On recognizing that the link has recovered, node 4 will generate the LSA for 4→5 and node 5 will generate one for 5→4 and flood the rest of the network. However, with normal flooding, node 4 or node 5 would not do anything in regard to link 2-3, although both have different views! This is partly why resynchronization is important. When a failed link or a node is recovered, the best thing to do is to exchange the entire list of link numbers along with the current sequence number between the neighbor nodes through a database description message. This allows the node on each side to determine where they differ, and then requests the cost information for the ones where they differ in terms of the sequence number. It may seem odd to request the database description first and then followed by the link cost update. There are two reasons why this approach is beneficial: 1) usually a link state message contains much more than just the link cost (especially if multiple metrics are allowed); thus, the message size stays smaller if only the database description is exchanged; and 2) a different message type for the database description exchange avoids needing to invoke a full link state update between these two neighbors. Certainly, once the end nodes (nodes 4 and 5 in this case) have done resynchronization, each will generate a standard/normal link state update message to let the rest of the nodes know about the changed entries.

Now we will bring age into the picture. If two parts have been isolated for a long time, the age field of the LSAs received from the other side will decrement all the way to zero. This will then trigger exception advertisements on both sides for the appropriate set of links. Through this process, links will be deleted from the local copy at the nodes. For example, nodes 1, 2, and 4 from the left side will not have any information about links on the right side. In this case, when link 4-5 recovers, nodes 4 and 5 would do the database description exchange and find out about the existence of new links that will be synchronized and then flooded to the rest of the network through a normal link state update. •

Inter-Area Routing Computation

It is important to note that the Dijkstra-based shortest path computation using link state information is applied only within an area. For routing updates between areas, information from one area is summarized using Summary LSAs without providing detailed link information; thus, inter-area routing computation in OSPF is similar to the distance vector flavor. Since OSPF employs only a two-level hierarchy, a looping problem typically known to occur with a distance vector approach is not conceptually possible. Yet, due to aggregation and hierarchy, in certain situations, it is possible to create a scenario where looping can occur [699].

6.3.5 Multiple routes into Exchange 2003

As long as you only have a single routing group connector between Exchange 2003 and Exchange 2007, you do not have to worry about link state information. Exchange 2003 will continue to send link state updates between its routing groups but Exchange 2007 will simply drop the updates and ignore them. The two sides will operate independently of each other and maintain separate routing topologies. Operating a single connector will be sufficient for small to medium organizations but things often become more complex with larger organizations because of the need to handle bigger volumes of traffic and to route messages efficiently within geographical network segments. In this situation, you probably need to configure additional routing group connectors between appropriate Exchange 2003 servers and Exchange 2007 hub transport servers.

16.3.2.2 OLSR

The Optimized Link State Routing Protocol (OLSR) [7] is a proactive link-state routing protocol, which uses hello and topology control (TC) messages to discover and then disseminate link-state information throughout the ad hoc network. Individual nodes use this topology information to compute next-hop destinations for all nodes in the network, using the shortest hop-forwarding paths.

The OLSR protocol uses a link-state algorithm to proactively determine the most efficient path between nodes. The key point of OLSR lies in the dynamic Multi-Point Relay (MPR) technique, which selects only a subset of neighboring nodes to relay data instead of every node acting as a relay. MPRs are elected in such a way that every node can communicate with an MPR within one hop. The localized network information is shared among MPRs to maintain network-wide routing paths. This allows every MPR to have a complete routing table while simultaneously minimizing the number of topology-control messages.

Routing Update Impact

The RIP protocol is more suited to smaller networks because of the large amount of broadcasts used to update routers about paths to remote networks. The OSPF protocol is well-suited to larger, dynamic, more complicated networks. RIP updates occur every 30 seconds, whereas OSPF updates occur every 30 minutes. RIP routers send the entire routing table to neighboring routers, whereas OSPF sends very small update flies to routers whenever they detect a change in the network, such as a failed link or new link. When routers exchange information, it is called convergence, where the routers “converge” on the new representation of the network very quickly.

A network of OSPF and RIP routers can possibly coexist. OSPF is slowly replacing RIP as the interior gateway routing protocol of choice. These OSPF routers can simultaneously RIP for router-to-end station communications, and OSPF for router-to-router communications. For example, you can configure a Windows NT computer to participate as a RIP router in a RIP-routing environment, but you cannot configure this same Windows NT computer to participate as an OSPF router in an OSPF-routing environment. This coexistance between RIP and OSPF makes gradual migrations from RIP to OSPF feasible. In fact, RIP and OSPF routers cannot only coexist in the same network, they can actually share routing information. Figure 6.8 shows the enabling of RIP routing on Windows NT.

To configure your Windows NT computer to participate in sharing routing updates with other computers on the network, you need to enable IP forwarding. This is done in the Network applet of the Control Panel, by selecting the TCP/IP protocol and viewing the properties. The Routing tab is illustrated in Figure 6.8. You also need to enable RIP in the Services applet in the Control Panel.

In OSPF, a neighbor is another router running OSPF that has an interface on the same network. When discovering and configuring OSPF neighbors, the router will use the Hello protocol to discover their neighbors and maintain this relationship. On two of the types of OSPF networks, point-to-point and broadcast, the Hello protocol will dynamically discover the neighbors. On a nonbroadcast network, you will have to configure the neighbors manually, because OSPF will not have a means of contacting and establishing relationships with its neighbors.

This Hello protocol ensures that the relationships between the routers are bidirectional. This will guarantee that every OSPF router will send as well as receive updated route information to and from each of its neighbors. The communication is bidirectional when the router sees itself in the Hello packet from another router. Included in the Hello protocol packet is the following:

The router's priority

The router's Hello timer and Dead timer value

A list of routers that has sent the router Hello packets on this interface

This router's choice of designated router and backup designated router.

However, this does not mean OSPF is a perfect routing protocol as far as routing updates are concerned. In really large network configurations, OSPF can produce a large number of router updates that flow between routers. If a network consists of hundreds of routers in a network topology that is designed to be fault tolerant, the number of link-state messages that traverse the network can be in the thousands. These thousands of link-state messages can be propagated from router to router across the network, consuming valuable bandwidth, especially on slower WAN links. The routers then have to recalculate their routing tables, which can consume valuable RAM and CPU cycles if these routing tables are a significant size. Fortunately for OSPF, no routing protocol available today is capable of minimizing routing updates in a very large network with many routers. OSPF is, however, much more capable than RIP at minimizing these bandwidth intensive routing updates. By the way, by “link-state” we mean the state, or condition of a link that is a description of the router's relationship to its neighboring routers. We think of the link as being an interface on the router. An interface, for example, would be the IP address of the physical interface, the subnet mask, the type of network to which it is connected, or the routers connected to the network. The collection of all these link-states would comprise a link-state database.

The link-state algorithm states (in much more complex terms than described here) a few steps of building and calculating these paths:

Upon initialization or upon a change in routing information, a router will generate a link-state advertisement that will represent the collection of all the link-states currently on the router.

In an event called flooding, all routers will exchange this link-state information. This flood of routing information will be propagated to all routers in the area.

After each router has finished compiling the link-state information, they will begin to calculate a Shortest Path Tree to all destinations. This is very CPU-intensive, as there can be hundreds of paths that need to be processed. These paths will include the associated cost and next hop information to reach those destinations.

If there are no changes in the network topology, OSPF will not be very active. OSPF will not need to exchange link-state information, and the routers will therefore not need to calculate Shortest Path Trees, because they will already have the information processed.

There are also different types of link-state packets, as follows:

Router links. Describe the state and cost of the router's links to the area. These router links are the indication of the interfaces on a router belonging to a certain area.

Network links. Describe all routers that are attached to a specific segment. These are generated by the Designated Router (DR).

Summary links. Describe networks in the autonomous system (AS), but outside of an area. These summary links also describe the location of the ABSR. They are also generated by the ABRs.

External links. Describe destinations that are external to the AS, or a default route from outside the AS. The ASBR is responsible for injecting the external link information into the autonomous system.

Another feature of OSPF is that routing updates are not passed across areas. Remember that areas are separated by the types of routers that we listed before, such as area border routers. If a network link were to fail, only the routers inside that area would exchange routing update information. Area border routers filter the routing updates from separate areas and the backbone. Area border routers can communicate with each other and exchange routing update information, but they use special link-state messages that are a brief summarization of the LAN or WAN topology for their areas.

Figure 6.9 illustrates the use of dividing areas that represent physical regions with area border routers attached to the backbone.

Each city does not want to receive the routing updates from the other cities; therefore, these areas are separated by area border routers, which can and do exchange information between each other, but in a smaller link-state update.

You can also fine-tune OSPF routers to minimize the amount of updates that are unleashed on the network, and therefore minimize the reduction in network bandwidth. You can also fine-tune the rate of convergence, which is the time between the routers receiving the new routing information and the time the network routers have made the necessary adjustments in their routing tables.

Table 6.4 illustrates an example of the OSPF database. This output is from the following command:

Table 6.4. The Complete OSPF Database Taken from an Area Border Router (ABR)

OSPF Router with ID (211.231.15.67) (Process ID 10)

We can begin analyzing the results, first starting with the Router Link States section of Area 1, shown in Table 6.5.

Table 6.5. The Router Link States Section of Area 1 in the OSPF Database

The two entries represent two routers in this area. Both routers have two links to Area 1, as represented by the Link Count column.

We continue, skipping past the Summary Net Link States section, and on to the next Router Link States section, which is for Area 0, shown in Table 6.6.

Table 6.6. he Router Link States Section of Area 0 in the OSPF Database

Once again, there are two routers in this area. The first router has three links to Area 0, and the second router has one link to Area 0.

The Summary ASB Link States of Area 1 are listed in Table 6.7.

Table 6.7. The Summary ASB Link States of Area 1 in the OSPF Database

This gives you an indication of who the ASBR for the area is. The ASBR is a router with the address of 211.231.16.130.

The AS External Link States information contains information about destinations outside of our area, shown in Table 6.8.

Table 6.8. The AS External Link States in the OSPF Database

Both of the two external links that are listed have been injected into our area from the OSPF.

Link-State Routing Model

The link-state routing model is composed of physical entities (routers and communication links) and logical entities (the link-state routing protocol running in the routers). Within a link-state routing domain, each router generates the linkstate information for the link that has the direct connection with the router (the link-state information is directional) and floods1 this information to its neighbors. A receiving router will forward the routing information (unmodified) via flooding again. Therefore, each router will have the same view of a network. When a router joins the network, it needs to synchronize the link-state database with its neighbors. The routing information carried by a link-state routing protocol is typically the link-state of a router's interface. This information is called the link-state advertisement (LSA). During flooding, multiple LSAs can be encapsulated in a single link-state update (LSU) routing packet.

The security issues related to the link-state routing model can be broadly classified as security for the network device, operational security, and communication security. Security for the network devices concerns the physical access to the routers and communication links. Operational security includes the access control of the operating system of a router, privilege mode of a router, and so on. Communication security is related to the transmission, reception, and processing of routing data (LSAs and LSUs). Note that all data security-related issues discussed here are based on routing data but not on user data, and we focus on the communication security aspect of the link-state routing protocol.

7.7.8 Secure Link-State Routing for Mobile Ad Hoc Networks (SLSP)

Secure Link-State Protocol (SLSP) [42] is a proactive secure routing protocol for ad hoc networks. The protocol uses digital signatures and one-way hash chains to ensure the security of link-state updates. In SLSP, nodes disseminate their link-state updates (LSU) and maintain topological information for the subset of network nodes within R hops, which is termed as their zone [43]. Each node is equipped with a public/private key pair. Nodes' public key certificates are broadcasted within their zones using signed public key distribution (PKD) packets. SLSP can be used as the Intrazone Routing Protocol in the Zone Routing Protocol (ZRP). Link-state information is broadcasted periodically using the Neighbor Location Protocol (NLP). On receipt of LSU packets, nodes verify the attached signature using a public key they have previously cached in the pubic key distribution phase of the protocol and authenticate the hop count with the help of one-way hash chains. As a part of NLP, each node broadcasts a signed pairing between its IP address and its MAC address. A node's NLP can notify SLSP when one MAC address uses two IP addresses, when two MAC addresses claim the same IP address, and when another node uses the same MAC address as that of the detecting node. These protocols ensure some level of integrity of MAC and IP addresses within a two-hop radius.

SLSP link-state updates are signed and propagated a limited number of hops. In ZRP, SLSP link-state updates would have a maximum hop count equal to the zone radius. To ensure that an SLSP update does not travel too many hops, each update includes a hop count representing the number of hops traveled by the SLSP update. A hash chain is used to authenticate the hop count, and the hash chain values are authenticated using the hash chain's anchor, which is included in the signed portion of the LSU packet. SLSP uses the same lightweight flooding prevention mechanism as SRP, wherein nodes that relay or generate fewer link-state updates are given priority over any node that sends more link-state updates.

SLSP offers protection against individual malicious nodes. But SLSP is vulnerable to colluding attackers that fabricate nonexisting links between themselves and flood this information to their neighboring nodes.

Distributing Link-State Information with BGP

As we have seen, routers and other type of network nodes use an IGP to distribute routing information inside a routing domain or AS. IGP determines which routes are the best candidates to distribute using one of two methods:

Distance vector—This technique is used by older protocols such as the routing information protocol (RIP). These protocols advertise the entire routing table to their directly connected neighbors using a broadcast address (“Everybody, pay attention to this!”). The best path to a destination is simply the minimum number of hops (routers or network nodes) that the packet would take to the destination, regardless of link speed or node processing power.

Link-state protocols—This technique, used by protocols such as OSPF or IS-IS, advertise information about the network topology to all routers in a routing domain using multicast addresses (“If you are interested, pay attention to this”). This triggers other updates until all routers running the protocol have the same information about the network, a process known as convergence. Best paths can then be determined by different criteria: delay, bandwidth, or other parameters.

Whatever the method, the IGP provides routing connectivity information within the routing domain, the set of routers under common control of a single administration entity that controls the domain. A BGP AS can contain a single routing domain (the simplest case) or several, and these separate domains can even run different IGPs. Inside an AS, the IGP(s) learns reachable prefixes and the interfaces to reach them and advertised the “best” way to get to them to all IGP neighbors. When an AS consists of multiple routing domains, the IGPs can exchange information gathered from different routing protocols through a process known as route redistribution. This redistribution ties multiple routing domains together inside a single AS (so the routes are still intra-AS and not external routes).

Implementing BGP for Link-State Protocols

How should routers implement this new capability for BGP? The standards say that there should be a “protocol agnostic representation” of nodes and links for these purposes. This is a fancy way of saying that any implantation should be more abstract than the concrete link-state parameters used by the IGP for nodes and links.

Because the Illustrated Network is built out of Juniper Networks equipment, let’s look in a bit more detail at how Juniper Networks routers implement sharing link-state information across IGP boundaries using BGP. The “protocol agnostic” database for this information already exists in every Juniper Networks router (and other Layer 3 devices) as the Traffic Engineering Database (TED). All topology information is also in the TED. All that is missing is a way to “transcode” this link-state information into a format suitable for BGP NLRI updates.

To do this, we’ll put all relevant link-state information into a separate table called the “link-state distribution table,” or lsdist.0. All of the link and nodes entries in the TED are converted into routes before being placed into the TED table, a process called TED import, and users can examine these entries if they wish. In fact, a routing policy can be inserted here to control exactly which routes are “leaked” into the lsdist.0 table. Then we can export this collected information back into the TED (because it is a cumulative process) and out to BGP for export to peers. This overall process is shown in Figure 17.11.

Figure 17.11. Implementing BGP link-state distribution.

Another policy can be used to export (advertise) routes from the lsdist.0 table using BGP. To do this, BGP needs to be configured with the BGP-TE address family and an export policy to select these routes for BGP distribution.

BGP then sends these routes as it would any other NLRIs. BGP peers that have the BGP-TE address family enabled receive and process these BGP-TE NLRIs, storing them in the receiver’s lsdist.0 table.

All routes in the lsdist.0 table must be selected for export with a routing policy. By default, no entries are leaked from the lsdist.0 table unless directed by a policy.

One other aspect of Juniper Network’s link-state BGP distribution should be mentioned. That is the fact that the TED uses a protocol preference scheme based on the protocol used to provide the information to the table. Entries learned by BGP can be supplied by different protocols, and TED entries can correspond to more than one protocol. To make sense out of this multiplicity, a protocol with a higher “credibility” value is favored over a source with a lower value. The credibility values can be changed by configuration.

The default credibility values for BGP-TE are:

•

Unknown—80

•

OSPF—81

•

ISIS Level 1—82

•

ISIS Level 2—83

•

Static—84

•

Direct—85.

21.8 Summary

In this chapter, we discussed QoS routing. We started by discussing what QoS means, and the scope of QoS routing and its inherent relation to traffic engineering. Based on arrival and service frequency, we have also identified how different services may be classified into three types of classifications; this is summarized in Table 21.1. We have indicated that QoS routing falls under the Type-A classification.

We then presented a taxonomy for QoS routing and showed how QoS routing can be divided based on different types of networks, and whether one or more attributes are to be considered in the QoS routing decision, especially for packet switched networks.

We next discussed extendibility of widest and shortest path routing to QoS routing. An important issue to consider here is that periodic updating of information induces inaccuracy on link state information—thus, to properly address service performance, a path caching mechanism that allows alternate path routing can be helpful; this is presented as a three-phase framework. Performance results are presented to understand the interrelation in the presence of heterogeneous guaranteed services, update frequency, traffic dynamism, and so on.

The importance of QoS routing goes beyond the telephone networks. It is also applicable in MPLS, optical, and wavelength routing when service requests with guaranteed resource requirements are to be connected on demand and quickly. In subsequent chapters, the specific applicability of QoS routing will be discussed for each technology.

Before we conclude, we briefly comment on the QoS guarantee in a generic best-effort network such as the Internet. This QoS guarantee issue should not be confused with QoS routing. In an intradomain environment running a best-effort model, QoS guarantee for services are quite possible if the network is engineered to meet the QoS guarantee—this may require overprovisioning. A better environment is a differentiated services environment, where priority to certain packets can be given by using a router's scheduling algorithm (refer to Chapter 17) for services that require certain guarantees—in this case, the overprovisioning can be moderate since the routers have the mechanisms to discriminate packets that require a guarantee and those that do not. In an interdomain environment, it is much more difficult since each provider on a path for a request that require the QoS guarantee would need to have the proper mechanisms—this is difficult in practice since it might not be possible to enforce every provider to provide the same QoS guarantee. However, instead of a stringent QoS guarantee, it is possible to provide certain quality through broad service level agreements (SLAs) (see Section 18.1 for examples of SLAs). SLAs are possible among different providers through which traffic may flow. Thus, meeting SLA agreements can be thought of as meeting “soft” QoS guarantee.

Distributed Control

For the reasons given above, we are seeing a trend toward a more distributed form of control for connection management. Distributed control protocols have been used in IP/MPLS and Ethernet networks. They have a fair degree of success with respect to standardization and accomplishing interoperability across vendor boundaries. These protocols can be reused to control and manage optical networks. An example is the Generalized MPLS (GMPLS) protocols that support optical connections. The developers of GMPLS recognized that a label-switched path (LSP) is a virtual circuit-switched path. Much of the control and management of an LSP can be applied to an arbitrary circuit-switched connection, for example, a TDM connection, a wavelength-switched connection (i.e., a lightpath), or fiber-switched connection. Then an LSP rather than being a trail of labels will be a trail of generalized labels (e.g., time slots, wavelengths, or fibers).

The Automatic Switched Transport Network (ASTN) is an architecture for managing connections including optical connections. It has similar objectives with GMPLS, but while GMPLS development is on implementations to realize an optical network, ASTN development is on a framework. Thus, ASTN is considered a top-down approach, while GMPLS is a bottom-up approach.

Distributed connection control has several components:

Topology management. Each node in the network maintains a database of the network topology and the current set of resources available, as well as the resources used to support traffic. In the event of any changes in the network, for example, a link capacity change, the updated topology information needs to be propagated to all the network nodes. We can use the same techniques used in IP networks for this purpose. Nodes periodically, or in the event of changes, flood the updated information to all the network nodes. We can use an Internet routing and topology management protocol such as OSPF or IS-IS (see Section 6.5), with suitable modifications to represent optical layer topology information, and update it automatically. OSPF-Traffic Engineering (OSPF-TE) and IS-IS-Traffic Engineering (IS-IS-TE) are enhancements of OSPF and IS-IS that include attributes of the links such as available bandwidth.

As we mentioned earlier, nodes monitor their links by periodically sending “hello” or continuity check messages through their link ports. A node can conclude that a link is up as long as it receives such messages. Through these messages, nodes can discover their current neighbors. The messages may also carry attributes of the link such as the available bandwidth and delay. Nodes will share their link state information with other nodes by flooding the information through the network as we described above.

Network administrators may need to know the status of an end-to-end connection traversing multiple links. Ping or loopback messages can be sent from one end of a connection and are returned by the other end. These messages are used to verify if a connection is still up and can be used in troubleshooting. Also, Traceroute or link trace messages can be sent from one end of the connection to discover the path of the connection. The path is a list of links or nodes of the connection. This is useful to a network administrator when paths are computed in a distributed fashion and unavailable in a centralized database. Even if the path information is stored, the traceroute or link trace can be used to verify the path.

Link management. As we described above, monitoring the status of the link can be accomplished with periodic “hello” or continuity check messages. In addition, the performance of the link can be monitored by keeping statistics on packet losses and bit error rates. If the performance grades below an acceptable threshold, a failure indication signal can be sent to the other end of the link. A failure indication signal can also be sent when the performance is degrading to indicate imminent failure. Then an early warning can allow a switchover to an alternate link before the link fails.

Networks may also allow link bundling, where multiple parallel channels between two nodes operate as a single logical link. This will reduce the amount of overhead in the routing protocol and keep track of the network topology. Then end nodes must be able manage the channels including set up and tear down the channels, map the data to the channels, and support routing and resource allocation. The Link Management Protocol (LMP) of GMPLS is an example of this.

Route computation. When a connection is requested from the network, the network needs to find a route and obtain resources along the route to support this connection. This can be done by applying a routing algorithm on the topology database of the network. The routing algorithm should take into account the various constraints imposed by the network, such as wavelength conversion ability and the capacity available on each link of the network. In the case of capacity availability, the minimum available capacity may be a constraint as well as the maximum available capacity. For example, a link may be a bundle of wavelengths. If we were to consider setting up a lightpath connection through the link then the wavelength capacity would be the link's minimum available capacity because the lightpath would use an entire wavelength in the link. In addition to computing routes for carrying the working traffic, the algorithm may also have to compute protection or back up routes for the connection, which are used in the event of failures. We discuss route computation in Section 10.2.2.

Signaling protocol. Once routes are computed, the connection needs to be set up. This process involves reserving the resources required for the connection and setting the actual switches inside the network to set up the connection. The process requires nodes to exchange messages with other nodes. Typically, the destination or source of the connection signals to each of the nodes along the connection path to perform this function. Protocols based on MPLS Internet signaling protocols such as RSVP and LDP (see Section 6.5) can be used for this purpose. They will set up paths for connections without considering link attributes, such as available capacity. In addition, they will set up connections along shortest paths. The extensions RSVP Traffic Engineering (RSVP-TE) and Constraint-based Routing LDP (CR-LDP) can take into account link attributes, and allow explicitly routed paths (see Section 6.6.3). Information sent by signaling protocols, such as the attributes of a link, are often in a type-length-value (TLV) format.

The same protocols can also be used to take down connections when they are no longer needed. In the case of IP/MPLS and GMPLS-based network architectures, connections have a “soft state.” This means that the connections have a lifetime, and while the connections are in use, their lifetimes are refreshed periodically with refresh messages. Discontinuing refresh messages will eventually discontinue the connection by time out.

The process of setting up or taking down a connection must be executed carefully. For example, if the connection is simply taken down by the source and destination, then the intermediate nodes may sense the loss of light on the connection as a failure condition and trigger unwanted alarms and protection switching. This can be avoided by suitable coordination among the nodes along the route of the lightpath.

GMPLS has enhancements of MPLS to support setting up lightpaths. Whereas MPLS is designed to set up unidirectional LSPs, GMPLS can set up bidirectional LSPs. This is important since most lightpaths are bidirectional. In addition, GMPLS allows an upstream node to impose restrictions on the type of labels or generalized labels that can be used in setting up an LSP over the next link or the entire path. This can be applied to set up lightpaths that have restrictions on wavelength conversion. Also, when setting up an LSP, a particular egress port can be specified.

Signaling network. Nodes need a signaling channel to exchange control information with other nodes. We described the many options available to realize this in Section 8.5.5.