12.3. Domain Hierarchies

We have seen that (topological) hierarchies are used with various routing protocols (OSPF, IS-IS, and ATM's PNNI routing) to enhance scalability. In transport networks and other types of circuit switched networks (e.g., the telephone network), hierarchies are also used to demarcate specific boundaries of networks (from the policy perspective). This is particularly the case when networks cross geopolitical boundaries. For example, a transport network may be composed of metropolitan networks interconnected by a state (or province)-wide core network. These state-wide core networks may be interconnected by a regional core network. These regional networks might then be interconnected by a country or continent-wide core network. Finally, international core networks may tie together various levels of international networks. Due to different regulatory, operational, or business influences, these networks may be administered somewhat autonomously, and hence a hierarchical assemblage of control domains is highly desirable, independent of scalability concerns.

Let us consider the use of hierarchy for structuring a carrier's network strictly for scalability. Suppose that a routing protocol can deal with 200 nodes at any given layer in a hierarchy. How many physical nodes (lowest level nodes) can be accommodated in total by (a) two, (b) three, or (c) four levels of hierarchy? Given that N nodes can be accommodated per hierarchical level, a two-level network would have N second level logical nodes each representing N physical nodes, resulting in a total of N² physical nodes. Repeating this process we get the following results: (a) N²= 40,000 nodes; (b) N³= 8,000,000 nodes; (c) N⁴= 1,600,000,000 nodes. From this, we see why those who need hierarchy for scalability alone question the need for more than three levels of hierarchy, while those who require hierarchical structuring of networks based on geopolitical boundaries cannot get by with just three levels of hierarchy.

12.3.1. Relationship to Signaling

As seen in Chapter 7, signaling protocols already contain provisions for “loose explicit routes” or “abstract nodes” which allow them to accommodate hierarchical domains. Thus, our focus later is on modifications and extensions to routing protocols for interdomain use.

Routing in optical networks involves calculating the entire route of the connection (albeit a loose route in some cases) at the source. As a connection set-up request crosses different domains, the signaling entity in each domain can take the loose routing information, and, based on detailed information about the internal topology of the domain, compute a specific intradomain path. This process can be repeated within each domain, with the routing entity in each domain using a potentially different algorithm to calculate the portion of the path passing through its domain.

For example, in the network of Figure 12-1, a route between NE4 in domain C and NE2 in domain B could be specified simply as a sequence of domains {C, A, B} to be traversed by the set-up request for the connection to be established between these nodes. This route could then be locally expanded in domains A and B, either by a border node or by an appropriate entity in the domain responsible for resolving the route, to the exact sequence of hops through that domain. For instance, within domain C, the route may be resolved as NE4→NE1. The border node NE1 in domain A may resolve the local route to be NE1→NE2→NE3. Finally, border node NE3 in domain B may resolve the route (due to its local constraints) to be NE3→NE2→NE1. Once the connection is established and the source node receives the corresponding acknowledgment, the connection is deemed available to carry data (possibly after the completion of other end-to-end connectivity tests conducted by the carrier).

12.3.2. Routing Hierarchies

To aid our discussion of domain hierarchies, we introduce below a subset of the definitions used in the ITU-T optical routing architecture and requirements document [ITU-T02b]. These pertain to Routing Controllers, Routing Areas, Routing Control Domains, and Link Resource Manager.

Routing Controller (RC)

This is an entity that computes routes across a routing area. There could be multiple, cooperating RCs within a routing area. For example, when a routing protocol like OSPF is used, every node running OSPF would be an RC. On the other hand, with centralized routing of the sort typically used in legacy transport networks, there would be a single RC, perhaps implemented in the Element Management System (EMS). In general, there could be one or more RCs in a routing area, either implemented directly on NEs or on separate equipment. The RCs implement interdomain routing.

Routing Area (RA)

Abstractly, an RA is a collection of nodes and links that define the topology over which RCs compute paths. At the lowest level of the domain hierarchy, an RA represents a control domain, that is, the nodes represent physical NEs and the links represent the interconnections between the NEs. The nodes and links in an RA can also be “abstract,” that is, each node itself representing an RA and the links representing the interconnections between these RAs. This will be the case at the higher levels of the domain hierarchy. RCs work with each other within a single RA (and within that RA only). For example, Figure 12-5 depicts three distinct RAs, identified as 2112, 505, and 417, in the first level of a domain hierarchy. Each of these RAs could be a control domain, for instance, a vendor “cloud” with its own internal control and management mechanisms. The RCs within the scope of RA 2112, that is, RC 3 and RC 7, interact with each other, but not with RC 11 in RA 505. This notion of an RA is somewhat different from the OSPF [Moy98] notion of a routing area in that it does not imply anything about how entities in different RAs interact (unlike OSPF's requirement on communications via the backbone area).

Routing Control Domain (RCD)

Each RC represents a routing control domain, that is, a logical region whose properties are characterized by the RC. When a domain hierarchy is created, an RA in level N-1 is represented as an RCD in level N by a level N-1 RC. Thus, an RCD is what appears as the abstract node in higher-level RAs, as described earlier. For example, Figure 12-5 depicts level 1 routing areas 2112, 505, and 417 being represented as RCDs by RCs 3, 12, and 7, respectively, within the level 2 routing area (identifier 1313). To summarize, a routing area defines the scope of a set of cooperating routing controllers while a routing control domain is associated with a single routing controller.

Link Resource Manager (LRM)

A link resource manager is a logical entity responsible for allocating and deallocating link resources, that is, time slots, wavelengths, and so on. In addition, it is responsible for providing link status information to the appropriate RC. Figure 12-5 shows several links (e.g., optical fibers) interconnecting the level 1 routing areas. Since these links are between level 1 routing areas, they do not fall under the management of any level 1 RC. Hence, the LRM associated with each of these links will need to communicate link status information to the appropriate level 2 RC.

Thus, the RCs within an RA represent either a single control domain or a hierarchy of such domains. Abstractly, these RCs are “nodes” within an RA, and they execute a link state routing protocol within the RA. This is similar to the manner in which routers in an OSPF area implement intraarea OSPF routing. Now, consider a collection of interconnected RAs at level 1 of the hierarchy. Each of these RAs is treated as a separate routing control domain and represented by a single RC (“node”) in a level 2 RA. This RC is thus a member of both the level 1 and the level 2 RAs. This is similar to an OSPF ABR being a member of both its own area and the backbone area. The interconnection between the RAs in level 1 is captured by “links” between the corresponding RCs (“nodes”) in level 2. These links could be links directly connecting the RCs in the physical topology, or (logical) adjacencies established between the RCs (similar to OSPF virtual links, see Chapter 10). This defines the topology of the level 2 RA. The RCs within the level 2 RA then execute the link state routing protocol. Further hierarchical levels are constructed in the same manner.

Now, the link state information pertaining to level N+1 is required to route a connection between RAs in level N. This means that the RC representing a level 1 RA in a level 2 RA must abstract and inject its level 1 RA information into the level 2 RA, and summarize the level 2 (topology and resource) information into its level 1 area. This is similar to interarea OSPF routing, where an ABR injects information pertaining to its area into the backbone area and propagates reachability information received in the backbone area (from other ABRs) into its area.

12.3.3. Identification of Components within a Hierarchy

To implement hierarchical routing as described, RCs and RAs need to be identified in the interdomain routing protocol. An RC identifier (RC-ID) uniquely identifies an RC within a given routing area. There is no separate RCD identifier, since each RCD is uniquely associated with an RC. Thus, the RC-ID is synonymous with the corresponding RCD identifier.

Before two RCs communicate with each other, they should verify that they are in the same routing area. Hence, it is useful to have an identifier for RAs, that is, RA identifiers (RA-IDs). Another way of thinking about this is that an RA-ID identifies the scope or context within which one or more RCs interact. An RC-ID must be unique only within its containing RA. Such a situation is shown in Figure 12-6, where the RC-IDs used in level 2 are the same as those used within some of the level 1 RAs. RC-IDs, however, can be globally unique.

12.3.3.1. OSPF EXAMPLE

The format of the OSPF packet header is shown in Figure 12-7 [Moy98]. This header contains an Area ID and a Router ID. These correspond to the RA-ID and the RC-ID, respectively. The concepts discussed earlier can be used to model OSPF's hierarchical interactions. In particular, OSPF maintains separate routing interactions in each of its areas, and the Area ID is used to tell these apart when a router participates in multiple areas.

12.3.3.2. BGP EXAMPLE

BGP-4 [Rekhter+95] runs over TCP. Once a TCP session is established between two BGP speakers (i.e., the equivalent of RCs), each speaker sends an Open message. The format of this message, containing the AS number, is shown in Figure 12-8.

BGP essentially defines the second level RA in IP networks. That is, each AS running E-BGP with another AS (see Figure 12-3) can be considered as a first level RA, and hence represented as an RCD in the second level RA. Thus, the AS number is the equivalent of the RCD identifier in the domain hierarchy.

12.3.3.3. OPERATIONAL ISSUES ARISING FROM RA IDENTIFIERS

The containment relationship between routing areas may need to change from time to time in an optical transport network. Such changes may come about due to incremental network growth, mergers, acquisitions and/or divestitures. The following capabilities are needed to support these changes:

• Splitting an area into two

• Merging two areas into one

• Adding a new area between two levels in the hierarchy

• Adding a new area to the top of the hierarchy

These changes should have minimal impact on the operation of the network. The following efficient methods for dealing with these changes are described in [ITU-T02b].

Splitting/Merging Areas

The splitting and merging of RAs can be best handled by allowing an RA to have multiple synonymous RA-IDs at the same time. The process of splitting can then be accomplished by the following sequence of actions:

1.	Add the second identifier to all the RCs in the new area.
2.	Ensure that at least one adjacency exists between RCs in the two RAs being formed.
3.	At a specified time, drop the original RA identifier from the RCs being placed in the new RA.

A similar sequence can be used to merge two areas into one:

1.	The RA-ID of the merged area is selected to be the ID of one of the RAs being merged.
2.	The selected RA-ID is added to the RCs in the other area.
3.	The original RA-ID is removed from the RCs modified in Step (2).

Inserting New Areas at the Top or in the Middle of the Hierarchy

Adding a new area at the top of the hierarchy or between two existing areas in the hierarchy can be accomplished by using methods similar to splitting and merging areas. The extent of reconfiguration needed, however, is dependent on how an RA is identified. Two different approaches exist for defining an RA-ID:

Because an RC has to use the RA-ID to identify if adjacent RCs are located in the same RA, the RA-ID has to be provisioned in each RC prior to forming adjacencies. If the first method is used, then insertion of a new area changes the IDs of all the RAs below the point of insertion. This will require the new RA-ID to be provisioned in all the RCs in all the areas below the point of insertion, and the old RA-ID to be removed. As the point of insertion is moved up in the hierarchy, the number of nodes to be reconfigured can grow exponentially.

If RA-IDs are absolute, then the amount of reconfiguration is greatly reduced. Instead of the RCs in all the areas below the point of insertion being reconfigured, only the RCs affected by the insertion need to be reconfigured.

12.3.4. Diversity Services and Domain Representation

Although it is not necessary and frequently not desired, there are certain situations in which revealing something about the internal topology and resources of a domain can be advantageous. This may be done, for instance,

Figure 12-9 depicts the network of Figure 12-1, with each domain represented by an abstract node. To realize better traffic engineering across an abstract node (domain), the propagation of abstract (i.e., approximate) internal link connectivity information is necessary. Such internal abstract links are shown for domain A (abstract node A) in Figure 12-9. Note that these abstract links do not necessarily correspond to internal physical links within the domain. In addition to helping in traffic engineering, the abstract link representation is also useful if a domain provides diverse transit service. An example of this service is also shown in Figure 12-9. In this case, the internal abstract links of domain A are advertised, along with their SRLGs, to the rest of the network so that diverse paths can be computed. Two connections that originate at location A in domain B and terminate at location Z in domain C can be routed over diverse paths across domain A.