10.8. Routing across Multiple Areas
The OSPF extensions discussed earlier apply to a single OSPF area. For reasons of scalability, an OSPF routing domain may consist of multiple areas. In this section, we discuss how optical routing extensions to OSPF can be extended to multiple OSPF areas.
10.8.1. Packet Forwarding in IP Networks
Let us first consider how basic packet routing works in a two-level OSPF hierarchy. This hierarchy was described in the last chapter, where the notion of OSPF areas was discussed. Specifically, the OSPF protocol requires that each of the areas (including the backbone area) be internally connected. Following this rule, there are two general OSPF topology configurations possible. The first is the strictly hierarchical configuration, shown in Figure 10-4. Here, there are three areas, numbered in the usual OSPF fashion, 0.0.0.1 to 0.0.0.3. In addition, there is a backbone area, numbered 0.0.0.0. The path from a node in one area to a node in another area crosses no intermediate area other than the backbone. The second is a more general configuration, shown in Figure 10-5. Here, some of the backbone links are actually virtual links (shown as dotted lines between nodes B2–B6, C1–C4, and D2–D3). A path in the backbone area might consist of paths through intermediate areas. Thus, an end-to-end path may traverse one or more intermediate areas. The selection of a particular topological organization has implications on the manner in which areas are managed and end-to-end connections are provisioned in the case of an optical network.
Figure 10-4. OSPF Areas with an Explicit Backbone
Figure 10-5. Working and Protection Path Routing in an OSPF Network with Virtual Backbone Links
Under the OSPF protocol, each node generates LSAs that are flooded to all nodes in its area. This happens in each area independently, including the backbone area. The area border nodes[2] (ABNs) are responsible for creating summary information regarding the areas they serve (other than the backbone area). In IP networks, the summary information consists of IP address prefixes, and associated cost information. Each ABN floods the summary information into the backbone area. Each ABN also floods the summary information regarding external areas into the area it serves. These procedures allow an internal node in an area to maintain the complete link state information pertaining to its area and summary information pertaining to external areas. This type of information abstraction is adequate for packet forwarding in IP networks. Specifically, for a destination in an external area, an internal node merely computes a path to one of the ABNs advertising the destination. Similarly, an ABN computes a path to an external destination by computing a path to another ABN in the destination area. Finally, the ABN in the destination area computes a direct path to the destination node.
[2] Under OSPF, the term area border router (ABR) is used. We use the term ABN to generalize this concept to optical networks.
Thus, packet forwarding from node A2 to node B5 in the network shown in Figure 10-4 works as follows:
A2 routes the packet toward ABN A5, which had advertised a path to an IP prefix that includes the address of B5 (it is assumed that each intermediate node in Area 0.0.0.1 has selected ABN A5 as the egress towards node B5 using the standard OSPF forwarding table computation procedure, see Chapter 9).
ABN A5 routes the packet to ABN B4 in Area 0.0.0.2.
ABN B4 routes the packet to B5 (it is assumed that each intermediate node in Area 0.0.0.2 has computed a consistent forwarding table using the standard OSPF procedure).
Packet forwarding from node A4 to node D4 in the network shown in Figure 10-5 works as follows:
A4 routes the packet toward ABN A3, which had advertised a path to an IP prefix that includes the address of D4 (it is assumed that each intermediate node in Area 0.0.0.1 has selected ABN A3 as the egress toward node D4 using the standard OSPF forwarding table computation procedure).
ABN A3 routes the packet to ABN D2 in Area 0.0.0.4. The forwarding table at each ABN is computed based on the (virtual) backbone topology maintained by each ABN. The next node selected is ABN B2.
ABN B2 determines that the next node in the backbone area toward ABN D2 is ABN B6. Since link B2-B6 in the backbone is virtual, B2 utilizes the forwarding table computed for Area 0.0.0.2 to forward the packet to ABN B6. Each intermediate node in Area 0.0.0.2 is assumed to have selected ABN B6 to reach node D4 (therefore, the packet need not be tunneled from B2 to B6, i.e., carried within another packet originating at B2 and terminating at B6).
ABN B6 forwards the packet to ABN D2 in Area 0.0.0.4.
ABN D2 routes the packet to D4 (it is assumed that each intermediate node in Area 0.0.0.4 has computed a consistent forwarding table using the standard OSPF procedure).
10.8.2. Summarizing Resource Information
The summary reachability information advertised via the backbone into each area is adequate to forward IP packets. To establish optical connections, however, path computation procedures must take into account resource availability information. But summarization of resource availability information is rather awkward. The main problem is that the resource availability information advertised into an area must be sufficiently detailed to result in successful path computation most of the time, while not affecting the scalability of the routing scheme. This problem has been dealt with in the PNNI routing protocol that advertises (succinct) abstract topologies of external peer groups. Using this method, for instance, the topology of the backbone network may be summarized by an abstract topology where the ABNs are nodes and the links represent the resource availability in the paths between ABNs.
In general, topology summarization using the available OSPF mechanisms may be complex. Additionally, it may not be really necessary to do this. An approach for resource summarization may be as follows:
Each link is characterized by a hop count (h) and a bandwidth (b) parameter.[3] h and b for a virtual link are computed by the ABNs at the two ends using a shortest path algorithm that finds the minimum-hop path with the maximum available bandwidth (shortest-widest path, see Chapter 11). This algorithm is run on the internal topology of the area that contains the virtual link.
[3] In fact, the “bandwidth” parameter could characterize minimum and maximum bandwidths, etc., as described in section 10.7. To simplify the discussion of multiarea routing, we assume that the parameter merely describes an estimate of available bandwidth on a link. The hop count is assumed to be 1 for direct links.
Each IP prefix advertised into an area by an ABN is characterized by h and b parameters. These parameters are computed by combining the information advertised in step (2) and step (1).
It is assumed that virtual backbone area links are configured by the operator (i.e., the ABNs at the ends of the links are configured with the virtual adjacency information). The b and h parameters for virtual links may be determined dynamically by the ABNs at both ends (using a consistent procedure) or they may be configured. Considering the network shown in Figure 10-5, the reachability of D4 is advertised into Area 0.0.0.1 in the following manner:
ABN D2 computes h = 1 and b = 10 for the IP prefix that includes D4 (the b values in this example are arbitrary, for illustration purposes). Similarly, ABN D3 computes h = 2 and b = 10 for the same prefix. Both of these ABNs advertise the same prefix with the computed h and b parameters into the backbone area.
Virtual links C4-C1 and B2-B6 are assigned h = 2, b = 15, and h = 2, b = 5, respectively, by the ABNs at their end points. The OSPF LSAs for these links, flooded in the backbone, carry these parameters.
ABN A3 advertises the IP prefix that includes D4 into Area 0.0.0.1, with h = 5 (addition of all h values to reach D4 along the minimum hop path, A3-B2-B6-D2-D4) and b = 5 (the minimum of all b values along the path to D4).
ABN A5 advertises the IP prefix that includes D4 into Area 0.0.0.1, with h = 6 (A5-C1-C4-D3-D6-D4) and b = 10.
10.8.3. Provisioning in a Multiarea Network
The provisioning model is based on dividing an end-to-end provisioning event into a sequence of provisioning events in each area. Because the complete topology of the network is unavailable to any node, the provisioning proceeds from the source node to an ABN in the source area, from this ABN to an ABN in the destination area, and, finally, from the last ABN to the destination node. In the backbone area, provisioning may be carried out inside other areas where virtual links were configured. As an example, consider provisioning a connection from A4 to D4 in the network shown in Figure 10-5. Suppose that as described earlier ABNs A3 and A5 have advertised h = 5, b = 5, and h = 6, b = 10, respectively, for an IP prefix containing D4 into Area 0.0.0.1.
Node A4 computes h = 2, b = 8 for destination A3, and h = 2, b = 10 for destination A5 within Area 0.0.0.1. Combining the h and b values advertised for D4 by these ABNs, A4 determines that the path via A3 to D4 will lead to h = 7 and b = 5. Similarly, the path to D4 via A5 is found to be h = 8 and b = 10. A4 decides to use A3 as the egress ABN in Area 0.0.0.1 to reach D4.
A4 signals a connection establishment request to A3, with D4 as the ultimate destination. Let us assume that this is a RSVP-TE Path message with Label Request, Upstream Label and other objects (see Chapter 7). This message contains the strict explicit route from A4 to A3, and a loose route from A3 to D4 (the loose route need not list any nodes between A3 and D4). The Upstream Label indicates the label allocated for the reverse direction of the connection.
ABN A3 determines that it has to reach ABN D2 to reach D4, based on the backbone topology database. It then expands the loose route A3-D4 as A3-B2-B6-D2-D4 and forwards the Path message to the next node, B2, with Label Request, Upstream Label and other objects.
From the explicit route information in the Path message, ABN B2 determines that the next hop toward D4 is B6. The link B2-B6, however, is a virtual link. B2 therefore computes a (bidirectional) path to B6, which satisfies the required bandwidth. This explicit route turns out to be B2-B4-B6. Thus, B2 expands the received explicit route as B2-B4-B6-D2-D4, places it in the Path message, and forwards the message to B4. This explicit route is strict from B2 to D2, and loose from D2 to D4.
ABN D2 receives the Path message with the indication that D4 is the ultimate destination. It computes a path to D4 with the requested bandwidth. The explicit route found is D2-D4. This route is placed in the Path message and forwarded to D4.
D4 receives the Path message and generates a Resv message back toward A4.
The Resv message is forwarded in the reverse path to the source. Each node en route allocates a label for the forward direction of the connection and sends it in the Label object. The connection setup is completed when A4 receives the Resv message, as described in Chapter 7.
The resulting path, <A4-A1-A3-B2-B4-B6-D2-D4>, is shown in Figure 10-5 (solid line).
10.8.4. Shared Mesh Protection in a Multiarea Network
End-to-end shared mesh protection requires that a protection path be established a priori for each (protected) working path (see Chapter 8). Recall that a protection path should be physically (SRLG-wise) diverse from the working path. Thus, the computation of protection paths requires both the information about the SRLGs associated with the network links and the information on the actual routes of the working paths. It was illustrated in section 10.7.2 how the SRLG information is propagated under single-area OSPF. Although the topology database information depicted in Table 10-3 does not show it, each node is assumed to keep track of the entire route of working paths originating from that node, along with the SRLGs associated with that path. Thus, a node under single-area OSPF can compute the protection path based on available information.[4]
[4] A related problem, which we will not consider here in detail, is that of optimizing the sharing of protection capacity in the network. This requires that a node computing the protection path be aware of the routes of all the active working paths. To realize this requirement, the working path information must be flooded throughout the network, which will adversely affect the scalability of routing. Heuristic methods, however, have been proposed to avoid this need [Kodialam+00]. Briefly, these methods rely on additional link parameters to indicate the presence of shared protection bandwidth, and the usage of this information during protection path computation.
With multiple areas, a node has neither detailed topology (and SRLG) information nor working path information outside of its own area. How then to establish a protection path? In the following, we describe various procedures for doing this. First, in section 10.8.4.1, an approach based on using “route servers” is described. Next, in section 10.8.4.2, an incremental protection path establishment procedure is described. Finally, in section 10.8.4.3, area-wise protection is described.
10.8.4.1. PROTECTION PATH COMPUTATION USING ROUTE SERVERS
Under this model, it is assumed that a “route server” participates in OSPF routing in all the areas. That is, the route server maintains the topology and resource information pertaining to the entire network. The route server may thus treat the multiarea network as a single large OSPF area and use the same protection path computation methods developed for single-area networks.
Clearly, since the route server has complete information, it can compute both working and protection paths. But for reasons of robustness and scalability, working path computation and establishment may be decentralized, using the procedures described in sections 10.8.2 and 10.8.3. Suppose this is the case. Then, each node is responsible for establishing the working path. Once the working path is established, it is assumed that the originating node has detailed knowledge about the route taken by the working path, along with the SRLGs traversed. Note that this information will not be propagated by OSPF itself, but has to be obtained during signaling (e.g., this information may be collected using RSVP-TE RRO, see Chapter 7). The orginating node can then supply the detailed working path information to the route server, which can then compute a full protection path. The establishment of the protection path would be similar to the procedure described in section 10.8.3, except that a strict explicit route will be used (i.e., no need for ABNs to expand loose hops).
The route-server-based based protection path computation approach does not require SRLG information to be summarized along with other resource information (as described in section 10.8.2). On the other hand, this approach is at best an interim step toward the final solution that takes into account only area-level information to compute protection paths.
10.8.4.2. INCREMENTAL PROTECTION PATH ESTABLISHMENT
Under this approach, the working path is established using multiarea OSPF and signaling as described in section 10.8.3. After the working path is established, it is assumed that the source node has detailed knowledge about its route and the SRLGs traversed, as described earlier. This information is used to compute the end-to-end (shared) protection path in each area incrementally as follows.
Consider the working path between nodes A4 and D4 established under the example in section 10.8.3. This path, <A4-A1-A3-B2-B4-B6-D2-D4>, is shown in Figure 10-5. The following steps are used to compute a node-disjoint protection path (which can be considered in terms of SRLG-disjointedness, as described in section 10.3):
1. | Utilizing the resource availability information and the SRLG information pertaining to the working path in Area 0.0.0.1, node A4 determines that the protection path segment in that area should exit through ABN A5. It thus computes a protection path segment, <A4-A6-A5> that is (node) SRLG-disjoint from the working path segment within Area 0.0.0.1. |
2. | A4 signals a connection establishment request to A5, with D4 as the ultimate destination. Let us assume that this is a RSVP-TE Path message with Label Request and other objects (see Chapter 7). This message contains the strict explicit route from A4 to A5, and a loose route from A5 to D4, that is, <A4-A6-A5-D4>. The Path message also carries the SRLGs associated with the working route (this feature requires extensions to RSVP-TE). |
3. | Using the SRLG information contained in the Path message, ABN A5 expands the loose hop <A5-D4> as the (SRLG-disjoint) explicit route, <A5-C1-C4-D3-D4>, and forwards the Path message to the next node, C1. |
4. | From the explicit route information in the Path message, ABN C1 determines that the next hop toward D4 is C4. The link C1-C4, however, is a virtual link. C1 therefore computes an SRLG-disjoint path to C4, which satisfies the required bandwidth. This explicit route turns out to be C1-C2-C4. Thus, C1 expands the received explicit route as C1-C2-C4-D3-D4, places it in the Path message, and forwards the message to C2. This explicit route is strict from C1 to D3, and loose from D3 to D4. |
5. | ABN D3 receives the Path message with the indication that D4 is the ultimate destination. Using the working path SRLG information, it computes a (SRLG) disjoint path to D4 with the requested bandwidth. The explicit route found is D3-D5-D6-D4. This route is placed in the Path message and forwarded to D4. |
6. | D4 receives the Path message and generates a Resv message back toward A4. |
7. | The Resv message is forwarded in the reverse path to the source. The protection path establishment is completed when A4 receives the Resv message, as described in Chapter 7.[5]
|
The protection path thus established is shown in Figure 10-5 (dotted line). It should be noted that because this is an incremental procedure, it is possible that some intermediate node may fail to find a suitable route. In this case, an alternate path has to be found, for instance, using a crank-back procedure [Farrel+03].
10.8.4.3. AREA-WISE PROTECTION
Area-wise protection refers to the approach where protection signaling is limited to the area in which the primary path segment failed (see Chapter 8). To do area-wise protection, it is required that the working and the protection path segments within an area originate and terminate at the same nodes. In this regard, the ABNs become the junction nodes for working and primary paths, as shown in Figure 10-6. Here, the working and protection path segments are shown as solid and dotted lines, respectively. For instance, within Area 0.0.0.1, the working path segment is <A4-A1-A3>, and the protection path segment is <A4-A6-A3>. The failure of the working path within Area 0.0.01 will be handled by activating the protection path segment within Area 0.0.01 while keeping the working path segments in other areas in place. Under this arrangement, when the backbone area has virtual links, the protection path segments within certain areas may be established twice: one to protect the working path segment within the area and the other to protect the working path segment in the backbone area.
Figure 10-6. Area-Wise Protection Path Routing
Protection path routing for area-wise protection can be described with reference to Figure 10-6. Suppose that A4 has established the working path, <A4-A1-A3-B2-B4-B6-D2-D4>, as shown in the figure. The protection path is established as follows:
Node A4 first determines that the exit ABN in Area 0.0.0.1 for the working path is A3. Utilizing the resource availability information and the SRLG information pertaining to the working path segment in Area 0.0.0.1, node A4 then computes the protection path segment, <A4-A6-A3> that is (node) SRLG-disjoint from the working path segment.
A4 signals a connection establishment request to A3, with D4 as the ultimate destination. Suppose that this is a RSVP-TE Path message with Label Request and other objects. This message contains the strict explicit route from A4 to A3, and a loose route from A3 to D4, that is, <A4-A6-A3-D4>. The Path message also carries the entire working route information and the SRLGs associated with the working route.
Using the working route information, ABN A3 determines that the egress ABN is D2. Using the SRLG information contained in the Path message, ABN A3 expands the loose hop <A3-D4> as the (SRLG-disjoint) explicit route, <A3-A5-C1-C4-D3-D2-D4>, and forwards the Path message to the next node, A5.
ABN D3 receives the Path message and expands the loose hop <D3-D2> into <D3-D1-D2> and forwards the message to D2.
ABN D2 finally receives the Path message with the indication that D4 is the ultimate destination. Using the working path SRLG information, it computes a (SRLG) disjoint path to D4 with the requested bandwidth. The explicit route found is D2-D1-D4. This route is placed in the Path message and forwarded to D1.
D4 receives the Path message and generates a Resv message back toward A4. The Resv message is forwarded in the reverse path to the source. Ingress and egress nodes in each area perform the appropriate actions to associate the working and protection path segments. The protection path establishment is completed when A4 receives the Resv message.
It is clear that the procedure described above may result in some inefficiency. This was seen in (4) above, where the protection segment had to go from D3 to D2. Instead, an SRLG-disjoint protection segment could have been established directly from D3 to D4, which is the final destination. As before, because this is an incremental procedure, it is possible that some intermediate node may fail to find a suitable protection route. In this case, the procedure has to be retried.
10.8.5. Multiarea Traffic Engineering Based on OSPF
The above discussion illustrated proprietary, heuristic approaches for routing and connection provisioning using multiarea OSPF. Standards-based multiarea OSPF-TE is still at its infancy. A number of proposals have been made in the IETF for traffic engineering across multiple areas [Cheng03, Kompella+02c, Srisuresh+03]. Based on the flooding scope of TE LSA, these proposals can be categorized as follows:
TE LSAs restricted to area local flooding scope: In this case, the TE LSAs are broadcast only in the local area and do not cross area boundaries. The advantage of this approach is that it is almost as scalable as the original OSPF. The obvious disadvantage is that the nodes do not have access to the TE information outside their local area except for the ABNs. These have access to the TE information in the areas they border with.
TE LSAs are broadcast across area boundaries: Under this approach, the TE LSAs are broadcast beyond the local area. The obvious advantage is that nodes outside the local area also have TE information available to them. The price paid is the scalability. One possible compromise is to broadcast the TE LSAs within the local area and broadcast only summary TE LSAs across area boundaries. Another possible alternative is to limit the broadcast, for example, from backbone area to other areas, but not vice versa.
When TE LSAs are broadcast only within the local area, there are different approaches to compute end-to-end paths.
Per-area path computation: Under this approach, the source node computes a strict explicit route from itself to the ABN within its own area. It then initiates path establishment. Once the path setup request reaches the ABN in the source area, the ABN uses the topology and TE information of the backbone area to compute a strict explicit route to an ABN in the destination area. The destination ABN uses the topology and TE information of the destination area to compute a strict explicit route to the destination node. This procedure was illustrated in section 10.8.3.
The choice of the ABN in the source area is determined only by the information in that area. Thus, the inability to find a route via a given ABN does not imply that no other routes exist. Specifically, it would be necessary to try other ABNs to find an alternate route [Farrel+03]. This procedure, therefore, is inherently iterative.
Path computation by a route server: Under this approach, a route server participates in topology discovery using OSPF-TE along with the NEs. It is assumed that the route server has the complete topology and TE information of the entire autonomous system (all OSPF areas). The source node then requests the route server to compute the entire path from the source to the destination. Once the route is obtained, the source node initiates the path set-up process. This procedure was described in section 10.8.4.1.
A variation in the above method is to use multiple, redundant route servers for fault tolerance. Thus, every node participates in the hierarchical topology distribution phase, but a few specialized nodes get the complete topology information.
Various proposals for extending the scope of TE LSA broadcast are under consideration. One such proposal recommends broadcasting TE LSAs from the backbone area into nonbackbone areas [Cheng03]. There are other proposals recommending creation of summary TE LSAs to be broadcast across the entire AS [Srisuresh+03]. In the following, we discuss end-to-end path computation under both approaches.
Backbone TE LSAs broadcast across area boundaries: Under this approach, the source node obtains the TE information from the backbone area, and uses it to compute the path all the way from itself to the ABN in the destination area. That ABN computes the rest of the path to the destination node. In certain cases, it may be desirable to “preengineer” the backbone area by constructing a set of paths that would be used as traverse the backbone area. With a preengineered backbone area, it is possible to restrict the backbone TE LSAs leaked to nonbackbone areas to contain only the information associated with the preengineered paths.
Summary TE LSA broadcast across area boundaries: Under this approach, TE information from within an area is summarized and then broadcast to other areas. Specifically, the ABNs perform the TE attribute summarization, for example, summarization of bandwidth, delay, and so on. The summarized metric advertised by an ABN represents the best possible value considering all the paths from the ABN to the destination in question. This procedure was illustrated in section 10.8.2. Since these summaries provide a clearer picture of the resources available in external areas, the probability of encountering a node (in another area) where resources cannot be allocated to a connection is minimized. The summarized TE resource availability information also helps in determining the ABN that is “closest” to the destination in terms of the resources required for the connection. This determination is similar to the route calculation based on summarized routes across areas under regular OSPF [Moy98].