8.2.3.1 Discovery

The discovery function can be divided into three different subfunctions:

1. Neighbor discovery

2. Resource discovery

3. Service discovery

The neighbor discovery is responsible for determining the state of local links connecting to all neighbors. This kind of discovery is used to detect and maintain node adjacencies; without it, it would be necessary to manually configure the interconnection information in management systems or network elements.

The neighbor discovery usually requires some manual initial configuration and automated procedures running between adjacent nodes when the nodes are in operation.

Three instances of neighbor discovery are defined in ASON, that is

• Physical media adjacency discovery

• Data plane layer entities adjacency discovery

• Control entities logical adjacency discovery

Physical media discovery has to be done first to verify the physical connectivity between two ports. Generally this verification is carried out through an exchange of messages between adjacent network entities that verify both the network entities and the connecting link functionality.

The layer adjacency discovery is used for building the layer specific network topology (see Figure 8.3) that has to be stored into the local CC to support routing.

As a matter of fact, logical adjacencies between both data and control entities are created by layer adjacency discovery. Moreover, layer adjacency discovery, fixing the topology of the layer, also identifies link connection endpoints that are needed to describe connections through the cascade of links composing them, to manage such connections in correspondence to client request changes and to assure proper network working when a failure happens.

Discovery processes involve exchange of messages containing identity attributes. Relevant protocols may operate in either an acknowledged or unacknowledged mode. In the first case, the discovery messages can contain the near-end attributes and the acknowledgment can contain the farend identity attributes. The service capability information can be also contained in the acknowledgment message.

In the unacknowledged mode both ends send their identity attributes. Recommendation G.7714 discusses the following two discovery methods:

• Trace identifier method

• Test signal method

In the trace identifier method, the discovery is carried out by using the trail identifiers that are included in all the overheads of the transport ITU-T standards (both in SONET/SDH and in OTN, see Chapter 2).

In particular, the trail termination points are first identified and then links connections are inferred. Just to give an example, let us imagine to have an ASON-managed next generation SONET network and to consider path layer discovery. A trace identifier discovery protocol will reside into the CC and will detect in all the network entities if the J0 field of the SONET path layer header is terminated and regenerated (the J0 field is the trail identifier in this case).

Once all the points in which the J0 is terminated and recreated are detected, the path layer logical topology is inferred by connecting the point where a value of J0 is created with the point where such a value is terminated with a virtual link (that is, links at the path layer).

It is to be observed that, under a layering point of view, the trail reports an information that is typical of the service layer, thus the trace identifier method performs discovery in layer one by exploiting also information relative to the client layer.

In the test signal method, test signals are used to directly find associations between subnetwork termination points (see network layering, Chapter 3) without discovering any service layer trails. While the use of overhead elements identifying a trail allows discovery to be carried out during normal network working, the use of data field to send test messages implies that the client data transmission is suspended. Thus the first discov-ery method is a type of in-service discovery, while the second is a type of outof-service discovery.

The resource discovery has a wider scope than the neighbor discovery. It allows every node to discover network topology and resources. This kind of discovery determines what resources are available, what are the capabilities of various network elements, and how the resources are protected. It improves inventory management as well as detects configuration mismatches.

It has to be considered that, if an OXC has five DWDM output ports, this means that it switches probably more than 600 optical channels and that more than 1200 fiber patch-cords (every channel comes in and goes out) physically comes out from some OXC card to be plugged on some other card or on an external equipment. Since physical connections of fiber patchcords have to be done manually, the probability that some error occurs when a new equipment is installed or when an upgrade is done is not negligible.

Many errors can be detected via the equipment self-test, but not all, and there is a prob-ability that an error manifests its presence much later with respect to the equipment installation, since without any specific test, it will become evident only when a certain card is really used (let us think, e.g., about redundancy cards). Thus, having an automatic procedure that through the discovery of network links at each network layer points out errors in connecting different equipments is very important to simplify the network operation.

The service discovery is responsible for verifying and exchanging information about service capabilities of the network, for example, services supported over a trail or link. Such capabilities may include, as an example, the quality of service (QoS) a certain network link is capable of providing in terms for example of error probability, connectivity restoration time in case of failure or packets average delay.

8.2.3.2 Routing

Routing is used to select paths for establishment of connections through the network. Although some of the well-known routing protocols developed for the IP networks can be adopted, it has to be noted that optical technology is essentially an analog rather than digital technology, thus routing is strongly influenced by the transparency degree of the network. To be specific, several types of transparency can be defined at different network layers. Examples are as follows:

• Service transparency: the layer ability to work ignoring the services managed by the client layer

• Protocol transparency: the ability to transport any client layer protocol

• Bit Rate transparency: the ability to work at any bit rate within a given maximum

• Optical transparency: the absence of network elements where the signal is electronically regenerated

On the ground of the aforementioned definitions, any OTN network is service and protocol transparent, while it is not bit rate transparent. The transparency that is relevant discussing about routing is the optical transparency. The optical layer of a network can be divided into optically transparent isles, which are network areas where the optical signal is never electronically regenerated.

The optical transparency areas can be so small as a single DWDM link connecting two electrical core OXCs or so big as an entire routing zone where optical interconnected rings are deployed. While the optical signal traverse a single optical transparent area, transmission impairments accumulated along the optical paths and this has to be taken into account while calculating the route (see Chapter 10 for details). Under the point of view of the routing strategies, ASON supports hierarchical, source-based, and step-by-step routing.

In the first case, CCs are related to one another in a hierarchical manner as we have seen defining administrative domains and routing areas. Source routing is based on a federation of distributed connection and routing controllers. The path is selected by the first connection controller in the routing area. This component is supported by a routing controller that provides routes within the domain of its responsibility. Step-by-step routing requires less routing information in the nodes than the previous methods. In such a case path selection is invoked at each node to obtain the next link on a path to a destination.

8.2.3.3 Signaling

Signaling protocols are used to create, maintain, restore, and release connections. Such protocols are essential to enable fast provisioning or fast recovery after failures. Signaling network in ASTN should be based on common channel signaling, which involves separa-tion of the signaling network from the transport network. Such a solution supports scalability, a high degree of resilience, efficiency in using signaling links, as well as flexibility in extending message sets.

A variety of different protocols can interoperate within a multidomain network and the interdomain signaling protocols shall be agnostic to their intradomain counterparts. As a matter of fact, interdomain signaling is managed by the domain interface protocols related to E-NNI interface, which are completely independent of the internal protocols of the domain.

8.2.3.4 Call and Connection Control

Call and connection control are separated in the ASON architecture. A call is an association between endpoints that supports an instance of service, while a connection is a concatenation of link connections and subnetwork connections (connections crossing the border between nearby administrative domains or routing areas) that allows transport of user information.

A call may embody any number of underlying connections, including zero. The call and connection control separation makes also sense for restoration after faults. In such a case, the call can be maintained (i.e., it is not released) while restoration procedures are underway. The call control must support coordination of connections in a multiconnection call and the coordination of parties in a multiparty call. It is responsible for negotiation of endtoend sessions, call admission control, and maintenance of the call state. The connection control is responsible for the overall control of individual connections, including setup and release procedures and the maintenance of the state of the connections.

8.2.3.5 Survivability

As detailed in Chapter 2, survivability can be attained by either protection or restoration mechanisms, or both in some cases, where protection is based on the replacement of a failed resource with a preassigned standby resource, while restoration, is based on rerouting using available but not preprovisioned spare capacity.

Since the ASON architecture is intrinsically a multilayer architecture, protection or restoration may be applied at different layers allowing very high availability levels to be achieved, but also requiring appropriate layers coordination. In the ASON architecture, protection management is in general terms a responsibility of the management plane.

The management plane performs protection configuration and failure identification and reporting after that the protection mechanism has assured service continuity. However, the control plane is not out from the protection management activity. First, the management plane should inform the control plane about all failures of transport resources as well as their additions or removals. Unsuccessful transport plane protection actions may trigger restoration supported by the control plane.

Moreover, the control plane supports the protection switching by suitable control plane protocols that are used in any case to advertise all the network entities in the data plane of the performed protection and, in some cases, necessary to coordinate protection switching itself.

Just to do an example, let us image to have an optical channel shared protection ring (OCh-SPRing detailed in Chapter 3). The OCH-SPRing mechanism is shown in Figure 8.7; the wavelengths on each fiber is divided into two groups: a working group and a protection group, where the working wavelengths on the outer fiber are devoted to protection in the inner fiber and vice versa. Working channels, as shown in the figure, are routed bidirectionally using both the fibers on working wavelengths.

When a failure occurs, switching happens at the OCh end and the channels affected by the failures are rerouted in the opposite ring direction by using the other fiber and the set of protection wavelengths. As it is also evident from Figure 8.7, if several optical paths are routed in the ring on the same wavelengths, the corresponding protection wavelengths have to be shared among all those paths (from where comes the name shared protection).

Moreover, also where a unidirectional failure occurs, that is a failure affecting only one direction, both the optical channels ends have to switch to change the ring configuration from working to protection. This means that, when a node detects a failure via a signal power off or a signal quality major alarm (e.g., an estimated BER greater than 10⁻¹⁰), it has to inform the other node at the end of the affected channel of the failure. Moreover also all the other nodes in the ring have to be advertised that protection switching occurred, since the protection wavelengths are no more available.

This means that a control plane protocol has to be started from the CC supervisioning the node that detected the failure with the primary role to make handshaking with the note at the other end of the affected link. The messages are first sent on the other direction of the path: if the failure is unidirectional, they will be detected and the other node will answer on the protection path, if the failure is bidirectional also the other node has detected the failure and after some time the handshake will start on the protection path in both directions.

Before engaging the protection path for the first protection handshake, another protocol can be used to advertise all the nodes of the ring that the protection wavelengths has been reserved by the nodes involved in the failure so that no other node will try to use them. After the successful handshake of the nodes at the two ends of the affected path, which also has the scope of verifying that the protection path works correctly, the affected optical channel is switched on the protection wavelengths in both the directions.

It is clear that there is a complex activity to perform if the protection mechanism involves shared resources to coordinate protection switching in a network. Under a functional point of view, this operation of advertising and handshaking could also be forced by the management plane that can naturally reach all the nodes of the data plane. However, protection has to be carried out generally within 50 ms, or a similar short time, thus an intervention of a SW manager running on a centralized workstation is not feasible and real-time protocols are needed.

However, all the protection mechanisms are controlled and managed by the management plane. Just for an example, if protection switching does not work, it is the management plane to detect and to manage the result, invoking if is the case protection on an upper layer or resorting to restoration coordinated by the control plane.

A particular circumstance is created in the case of control plane protection in consequence of a failure either of a CC or of a control plane connection. In this case, only the source and destination connection controllers are involved in managing protection and it is suggested to avoid shared protection techniques not to be obliged to create protocols of a sort of meta-control plane.

Differently from protection, the restoration is completely managed by the control plane. During restoration, the control plane uses specific protocols to build new routes for the connections that have been disrupted from a failure starting from the spare capacity available in the network. In the ASON standard, such a rerouting service is performed on a per-routing domain basis, i.e., the rerouting operation takes place between the edges of the routing domain and is entirely contained within it. This assumption does not exclude requests for an end-to-end rerouting service.

Naturally, if restoration mechanism is foreseen to increase the network availability, the spare capacity has to be suitably distributed in the network so to permit restoration after the desired class of failures. Hard and soft rerouting services can be distinguished. The first one is a failure recovery mechanism and is always triggered by a failure event. Soft rerouting is associated with such operations as path optimization, network maintenance, or planned engineering works, and is usually activated by the management plane.

In soft rerouting the original connection is removed after creation of the rerouting connection, while in hard rerouting, the original connection segment is released prior to creation of a new alternative segment.

8.3.2.1 Open Shortest Path First with Traffic Engineering

To enable automated configuration of the controlled network, GMPLS defines an intradomain routing process. Via this routing process, the network topology and its TE attributes are disseminated within the TE domain. This routing process is implemented using routing protocols specified for the MLCP. However, this routing process is not used for routing user traffic, but only for distributing information in the MLCP. To understand this point, we have to remember that, taking as an example the optical domain, user signals are organized in optical channels that are routed like circuits in that layer. Extensions to existing protocols necessary for this routing process were therefore created in the relevant IETF and OIF standards.

Essentially, with OSPF-TE, participating generalized label switched routers (GLSRs) first establish routing adjacencies by exchanging hello messages. After routing adjacencies have been established, the GLSRs then synchronize their link state databases. This is done by exchanging database description packets.

The database description packets contain at least one database structure referred to as a link state advertisement (LSA). Different LSA types exist but all share a common 20-byte header whose structure is shown in Figure 8.11.

The primary OSPF-TE operation is to flood LSAs throughout the MLCP domain by appending them to “link state update” messages periodically sent between adjacent GLSRs. To avoid interference with any ordinary routing processes, a TE LSA is made opaque. Such an opaque LSA is a special type of LSA only processed by specific applications (e.g., the GMPLS routing process). By extending the link state database with TE information, a traffic engineering database (TED) is produced. From this TED, a network graph with traffic engineering content can be computed. Constructing a TE network graph is necessary to provide input for the constraint-based algorithms subsequently used to compute network paths.

When flooding LSAs, each OSPF-TE routing message contains a common 24-byte header, which is used to forward it. This routing message header includes information about message type, addressing, and integrity. Within this header, LSAs are then encapsulated and specific payloads appended to each LSA. In order to enable advertisement of TE attributes in opaque LSAs, the LSA payload consists of type-lengthvalue (TLV) records. These are information records composed by three fields: two 2-byte fields, the “Type” and “Length” fields, and a variable length field, the “Value” field. Using TLVs, router addresses and TE links can be expressed.

In GMPLS, if an advertising router is reachable, a “router address”-TLV can be used to describe a network address at which this router (i.e., GLSR) can always be reached. In turn, the “link”-TLV can be used to abstract advertised TE links. Multiple TE attributes can be represented on each link using fields that are related to the “link”-TLV address, which are called sub-TLV. Thus, in the case of a link address, the TLV appears as the first field and pointer of a bigger record containing all the information that are needed to the MLCP about the link in order to perform routing operations.

The structure of this bigger record is reported in Table 8.1. Two links attributes of Table 8.1 are worth a comment. The first is the last attribute of the record, advertising that the link is part of a shared risk link group (SRLG). An SRLG is a group of links that will fail contemporary when a certain type of failure happens.

As an example, we can look at Figure 8.12, where typical situations are represented. Physical fiber connections are routed through multifiber cables and links having different destinations are built over a cable structure that generally has been deployed without any knowledge of the overlay network.

Thus, also links that have completely different source and destinations can share in a part of their path the same fiber cable. If the cable is cut, for example, due to civil works, all those links goes down, thus they have to be put together in the same SRLG.

The definition of SRLGs is fundamental when defining protection or restoration strategies. As a matter of fact, when the protection capacity is preprovisioned, it is fundamental to avoid that a link is protected by another link in the same SRLG, otherwise a single failure could hit both working and protection link, making the protection useless. In the case of restoration, when routing of the restoration path is performed, also links in the same SRLG has to be avoided. This is why the SRLG is indicated among the information related to the routing protocol.

The second field that is worth a comment is the interface switching capable description. It is clear that a link will terminate on the same type of interfaces and this field let the routing protocol know what kind of interfaces there are at the link extremes. During GLSPs, this information can be very useful to balance sparing of higher layer interface use achieved by transparent pass-through of the traffic not destined to the node with transmission resources sparing achieved by grooming (see Section 8.4: Design and Optimization of ASON/GMPLS Networks).

Once the OSPF-TE has flooded the network and created all the nodes capable of routing GLSPs, a database of the routing area topology, the OSPF-TE routing engine can start every time there is a GLSP to route either if it is a new path or it is needed to carry out restoration of a failed path.

The OSPF-TE routing engine is based on the so called Dijkstra algorithm (from the name of the inventor), which is an algorithm that is able to find in a graph with tagged links the shortest path between two given nodes. In GMPLS, what should be the tagging of the links of the network is not prescribed in a mandatory way; generally every link is associated to its length and the GLSP are routed along the shortest path in term of kilometers. This is a reasonable solution since the cost of a DWDM system is roughly proportional to its length due to the presence of EDFA sites. Thus, since if I occupy preferably the shortest links I will have to upgrade them sooner, this strategy tends to minimize the cost of network upgrades.

However, in specific situations, it is possible to tag the network links with other numbers. For example, a competitive carrier leasing fibers from another company could tag the link with the leasing price so to use always the cheaper links. This direct routing through the topology of the network with the Dijkstra algorithm becomes increasingly complex while the network dimension increases, so that the routing process has to be simplified in some way if OSPF-TE has to scale up to the dimension of an incumbent carrier network. The solution to this problem is the division of the network in routing areas and the execution of the routing in a hierarchical manner.

In particular, OSPF-TE individuates in the network a set of routing entities (GLSR) that are suitably distributed to constitute the so-called network backbone. All the other GLSRs are divided in routing areas constituted by nearby nodes. Each distinct routing area has to be in contact with the backbone at least in two points to assure effective network survivability. An example of this hierarchical organization of the network is reported in Figure 8.13.

Staring from this structure, a new higher level topology (the area topology) is constructed substituting all the routing areas with virtual nodes; this new topology has for sure at least interconnection degree equal to 2 due to the presence of the backbone and to the way in which the areas have been constructed.

The routing between nodes in different areas is performed in two steps: first the route is individuated in the area topology, then, knowing for each traversed areas the incoming and the outcoming nodes, the path route is specified also within areas.

8.3.2.2 IS–IS Routing Protocol

IS–IS is designed and optimized to provide routing within a single network domain, while passage through a domain interface for multidomain GLSPs have to be realized with a different protocol (e.g., the BGP, see Chapter 3, Table 3.1 IP protocol suite). IS–IS is based on the concept of routing domains. An IS–IS routing domain is a network in which all the equipments that perform GLSP routing run the integrated IS–IS routing protocol to support intradomain exchange of routing information.

The underlying goal is to achieve consistent routing information within a domain by having identical link-state databases on all routing entities in that area. Hence, all routing entities in an area are required to be configured in the same way.

IS–IS protocol supports a two-level hierarchy for managing and scaling routing in large networks. A network domain can be divided into small segments known as areas. The topology resulting from the substitution of each area with a virtual node and each connection between nodes in different areas with a connection between the corresponding virtual nodes is called area topology. This construction allows hierarchical routing to be carried out within the domain.

This means that the routing between nodes in different areas is performed in two steps: first the route is individuated in the area topology, then, knowing for each traversed areas the incoming and the outcoming nodes, the path route is specified also within areas. Following the same network representation, IS–IS routing entities are hierarchically ordered depending on their ability to route GLSPs only within their area or also toward other routing areas. In particular routing entities that are only able to route paths within their area are called Level 1 routers (not to confound with Layer 1 entities; this is a specific IS–IS hierarchy completely different from the network layering).

Following the same criterion, routing entities that can route GLSPs only between virtual nodes that represents routing areas are called Level 2 routers (or inter area routers) and finally routing entities that are able to route GLSPs both inside the area and between different areas are considered logically as a superposition of communicating Level 1 and Level 2 routers and are called Level 1–2 routers.

Level 2 routers are interarea routers that can only form relationships with other Level 2 routers; in other words, they can route through the area topology constituted by virtual nodes representing the routing areas. Similarly Level 1 routers can exchange information only with other Level 1 routers. Level 1–2 routers exchange information with both levels and are used to connect the interarea routers with the intraarea routers.

Integrated IS–IS uses the legacy CLNP node-based addresses [35–37] to identify routers even in pure IP environments. The CLNP addresses, which are known as network service access points (NSAPs), are made up of three components: an area identifier (area ID) prefix, followed by a system identifier (SysID), and an N-selector. The N-selector refers to the network service user, such as a transport protocol or the routing layer.

A group of routing entities belongs to the same area if they share a common area ID. Note that all routing entities in an IS–IS domain must be associated with a single physical area, which is determined by the area ID in the router address. IS–IS packets can be divided into three categories:

1. Hello packets are used to establish and maintain adjacencies between IS–IS neighbors.

2. Link-state packets are used to distribute routing information between IS–IS nodes.

3. Sequence number packets are used to control distribution of linkstate packets, essentially providing mechanisms for synchronization of the distributed link-state databases on the routers in an IS-IS routing area.

Each type of IS–IS packet is made up of a header and a number of optional variable-length fields organized in records and containing specific routing-related information. The variable length fields are called TLV as in the case of the OSPF-TE from the form of the record that is organized into three fields: type, length, and value.

Each variable-length field has a 1-byte type label (the Type field) that describes the information it contains. The second field is a length information that contains the length of the third field whose content is the specific information that is carried by the TLV (see Table 8.1 for examples). The different types of IS–IS packets have a slightly different composition of the header, but the first 8 bytes are repeated in all packets. Each type of packet then has its own set of additional header fields, which are followed by TLVs.

Table 8.2 lists TLVs specified in ISO 10589 while Table 8.3 lists the TLVs introduced by IETF in RFC 1195.

Enhancements to the original IS–IS protocol are normally achieved through the introduction of new TLV fields. Note that a key strength of the IS–IS protocol design lies in the ease of extension through the introduction of new TLVs rather than new packet types.

The routing layer functions provided by the IS–IS protocol can be grouped into two main categories: subnetwork-dependent functions and subnetwork-independent functions.

Table 8.2 List of TLVs Specified in ISO 10589

Table 8.3 List of the TLVs Introduced by IETF in RFC 1195

The subnetwork-dependent functions involve operations for detecting, forming, and maintaining routing adjacencies with neighboring routing entities over various types of interconnecting network links. The subnetwork-independent functions provide the capabilities for exchange and processing of routing information and related control information between adjacent routers as validated by the subnetwork-dependent functions.

The routing information base is composed of two databases that are central to the operation of IS–IS: the link-state database and the forwarding database. The link-state database is fed with routing information by the update process. The update process generates local link-state information, based on the adjacency database built by the subnetwork-­ dependent functions, which the router advertises to all its neighbors in link-state packets.

A routing entity also receive similar link-state information from every adjacent neighbor, keeps copies of GLSPs received, and readvertises them to other neighbors. Routing entities in an area maintain identical link-state databases, which are synchronized using SNPs. This means that routing entities in an area will have identical views of the area topology, which is necessary for routing consistency within the area. The decision process creates the forwarding database by running the Dijkstra algorithm on the link-state database so selecting for each GLSP and for the forward of each control packet the shortest path in terms of whatever weight is associated to each network link in the topology database.

The IS–IS forwarding database, which is made up of only best IS–IS routes, is fed into the routing information base.

8.3.2.3 Brief Comparison between OSPF-TE and IS–IS

IS–IS and OSPF-TE are link-state protocols, that is routing protocols that perform routing on the ground of information on the state of the links of the network that is derived from a map of the network topology that each routing network element stores and updates using the protocol flooding functionality. Moreover, OSPF-TE and IS–IS have several other common characteristics:

• They use the Dijkstra algorithm for computing the best path through the network.

• They allow any link tag as weight for the Dijkstra calculation.

• They exchange via protocol packets records composed by sets of TVL fields that describe the characteristics of the link they are advertising.

• They use the concept of subnetwork and virtual node to leverage on hierarchical routing to simplify routing tables and routing computation.

• They can use multicast to discover neighboring routing equipment using hello packets.

• They can support authentication of routing updates.

As a result, OSPF-TE and IS–IS are conceptually similar.

While OSPF-TE is natively built to route IP and is itself a Layer 3 protocol that runs on top of IP, so that OSPF-TE packets are a particular type of IP packets, IS–IS is natively an OSI network layer protocol (it is at the same layer as CLNS [35–37]), a fact that may have allowed OSPF to be more widely used. IS–IS does not use IP to carry routing information messages and its packets are not IP packets.

In line of principle IS–IS does not need IP addressing, even if, since some form of addressing is needed to route GLSPs through the network, in practical applications IP addressing is almost always used in conjunction with IS–IS.

Routing entities of a network implementing IS–IS build a topological representation of the network. This map indicates the subnetworks that each IS–IS enabled equipment can reach, and the lowest cost (shortest) path to any subnetwork is used to forward IS–IS packets and to route GLSPs.

Due to its structure, IS–IS is also more scalable that OSPF-TE: given the same set of resources, IS–IS can support more routing entities in an area with respect to OSPF-TE. IS–IS differs from OSPF-TE also in the way that “routing areas” are defined and interarea routing is performed. No hierarchy similar to that present in IS–IS is present in OSPF-TE, whose routing entities are all on the same ground, capable of interarea or intraarea routing when it is needed.

In OSPF, areas are delineated on the interface such that an area border router (ABR) is actually in two or more areas at once, effectively creating the borders between areas inside the ABR, whereas in IS–IS area borders are in between routers, designated as Level 2 or Level 1–2. The result is that an IS–IS router is only ever a part of a single area. IS–IS also does not require the backbone (or Area Zero as it is sometimes called) through which all interarea traffic must pass, while OSPF-TE needs this definition to manage multiarea ­routing domains.

The logical view is that OSPF creates something of a spider web or star topology of many areas all attached directly to area zero and IS–IS by contrast creates a logical topology of a backbone of Level 2 routers with branches of Level 1–2 and Level 1 routers forming the individual areas.

8.3.2.4 Resource Reservation Protocol with Traffic Engineering Extensions

Because RSVP-TE inherits its design from the RSVP protocol, it is based on distributing various signaling objects. These signaling objects have been grouped. These groups contain mandatory and optional signaling objects; encapsulating the groups with a common header, distinct signaling messages are created.

When a GLSR receives a signaling message, the resident objects are examined and interpreted based upon the message type indicated by the common header. Extending the RSVP-TE protocol for GMPLS was thus a matter of generalizing existing signaling objects, including some new objects that are reported in Table 8.4, and adding some minor signaling enhancements.

Considering the RSVP-TE protocol with GMPLS extensions for signaling, each signaling message contains a common 8-byte header. The common header defines the message type followed by the encapsulated objects. Encapsulated objects are of variable length and contain a 4-byte header defining the object length, class, and type within class.

Table 8.4 New Objects Introduced in the Adaptation of RSVP-TE for the GMPLS

The first signaling activity of RSVP-TE is to distribute the labels that are used in the GLSPs. The mechanism used by RSVP-TE is downstream-on-demand label distribution: this means that upstream GLSRs request downstream GLSRs to select labels for the links connecting them. In this way, each GLSR acknowledges a request to install an GLSP, forward the request to the next downstream hop, and awaits the response.

As a response is returned upstream, the GLSR can install a cross-connection (i.e., state describing ingoing and outgoing labeltointerface mappings and associated network resources) for this GLSP. Here, downstream is defined as the direction from GLSP ingress to GLSP egress for a unidirectional GLSP. In the case a bidirectional GLSP is to be set up, this is done by contemporary setup of two unidirectional GLSPs.

Once all the labels are assigned, the GLSP can be set up. As a matter of fact, GLSR can route the signal incoming from an input port toward the output port with the same label and the GLSP is identified in the path topology through the vectors whose elements are the labels of the links traversed by the path in the correct order.

As for all signaling protocols, RSVP-TE operation is composed of three main functions:

1. GLSP setup that is carried out via labels distribution.

2. GLSP management, a function composed by various elements among which error management is probably the most important.

3. GLSP tear down that is carried out by labels removal.

8.3.2.5 Constrained Routing Label Distribution Protocol

In the GMPLS network, GLSR must agree on the meaning of the labels used to for-ward traffic between and through them. This signaling operation can be performed by RSVP-TE, but a group of equipment vendors has pushed another protocol. The CR-LDP is an extension of the protocol used for the same scope in MPLS: the Label Distribution Protocol (LDP).

CR-LDP is a new protocol that defines a set of procedures and messages by which one GLSR informs another of the label bindings it has made. This implicitly advertises the GLSP setup since it is performed by assigning label bindings across GLSRs. The idea below the introduction in the GMPLS protocol suite of this extended protocol is to incorporate traffic engineering capabilities into a well-known protocol widely used in MPLS networks. The traffic engineering requirements are met by extending LDP for support of constraint-based routed label switched paths (also sometimes called CR-GLSPs).

Like any other GLSP, CR-GLSP is a path through a GMPLS network. The difference is that while other paths are setup based on information in routing tables or from a direct intervention of the management system, the CR-LDP constraint-based route is calculated at one point at the edge of network based on criteria including but not limited to explicit route constraints or QoS constraints.

The GLSR uses CR-LDP to establish LSPs through a network by mapping network layer routing information directly to data-link layer switched paths. A Forwarding Equivalence Class (FEC) is associated with each GLSP created. This FEC specifies which type of information is mapped to that GLSP and can be used for assuring the needed QoS during the GLSP setup.

Two GLSR which use CRT-LDP to exchange label mapping information are known as CR-LDP peers and they have a CR-LDP session between them. In a single session, each peer is able to learn about the other label mappings, that is, the protocol is bi-directional.

There are four types of CR-LDP messages:

1. Session messages

2. Discovery messages

3. Advertisement messages

4. Notification messages

Session messages are used to manage the CR-LDP section through the standard section management steps:

• Section setup through handshaking between the GLSR at the section ends

• Section monitoring

• Section teardown through another specific handshaking

Using discovery messages, the GLSRs announce their presence in the network by sending Hello messages periodically. This Hello message is transmitted as a UDP packet allocated into a GLSP that always exists when a physical capacity is deployed along a link in order to convey at least control plane messages.

When a new session must be established, the Hello message is sent over TCP to have a better control of the session opening procedure. Apart from the Discovery messages all other messages are sent over TCP. Advertisement messages are used to disseminate across the network the discovery of new network entities or other modifications in the network topology that influences the labels distribution. For example, if a link fails, this has to be eliminated from the topology map that each GLSR has in the routing engine. This is discovered by processing the absence of response to all the Hello messages that are directed toward that link and is advertised to all the network routing entities via advertisement messages. The notification messages signal errors and other events of interest. There are two kinds of notification messages:

1. Error notifications: these signal fatal errors and cause termination of the session

2. Advisory notifications: these are used to pass on GLSR information about the CR-LDP session or the status of some previous message received from the peer

All CR-LDP messages have a common structure that uses a TLV encoding scheme. This TLV encoding is used to encode much of the information carried in CR-LDP messages. The Value part of a TLV-encoded object may itself contain one or more TLVs. Messages are sent as CR-LDP PDUs. Each PDU can contain more than one CR-LDP message. Each CR-LDP PDU is an CR-LDP header followed by one or more CR-LDP message.

8.3.2.6 Comparison between RSVP-TE and CR-LDP

From the brief description we have done, it is quite evident that RSVP-TE and CD-LDP have almost all the same functionalities, even if they are constructed using different criteria. Thus a comparison between the two protocols, which are obviously alternative in a particular implementation of GMPLS, can be useful.

The summary of this comparison is mainly derived from Ref. [3].

• Transport Protocol: The first difference between CR-LDP and RSVP is the choice of transport protocol used to distribute the label requests. RSVP uses connectionless raw IP or UDP encapsulation for message exchange, whereas CR-LDP uses UDP only to discover GMPLS peers and uses connection-oriented TCP sessions to distribute label requests.

• Security: Once the path has been established and the data is being forwarded, the frame is no longer visible to the management or control plane software at the upper layers of the network. There is minimal chance that unauthorized individuals will be able to sniff or ruin the data or even redirect them toward an unintended destination.

Data is only allowed to enter and exit the GLSP at locations authorized and configured by the control plane. Both CR-LDP and RSVP-TE have the support of MD5 signature password and authentication. CR-LDP uses TCP/IP services, which is vulnerable to denial of service attacks; therefore, any in-between errors are reported immediately.

RSVP-TE uses UDP services and the IETF standard to specify an authentication and policy control. This allows the originator of the messages to be verified (e.g., using MD5) and makes it possible to police unauthorized or malicious reservation of resources. Similar features could be defined for CR-LDP but the connection-oriented nature of the TCP session makes this less important.

8.3.2.7 Line Management Protocol

The last key protocol of the GMPLS suite is the line management protocol; it is a pointto-point protocol that has the role of managing the link between adjacent nodes. As a matter of fact, traditional IP and MPLS protocol suite leverages on the physical layer to manage physical links. On the contrary, GMPLS cannot do that, since it is in charge of the entire network layering, thus a new protocol has been invented for this role. In particular, referring to an optical link, for generality with several WDM channels, LMP is aimed at the following tasks:

• Control-channel management

• Link connectivity verification

• Link property correlation

• Fault management

8.4.1.1 Basic Examples of Network Design

In this section, we will start to introduce a few basic elements of ASON/GMPLS network design neglecting two key elements: The uncertainty on the traffic forecast and the need of designing the network so as to allow some survivability strategy.

Even if these elements are key points in a real network design, at the first moment, they would mask more fundamental issues like transparent pass-through versus groomingbased design, mesh versus hub design, and finally the importance of linear cost models. In the next section, we will reconsider the design example of this section adding design for survivability and design in uncertain traffic conditions. Section 8.4.1 is intended as a preparation to the more formal discussion about ASON/GMPLS network design that we will carry out from Sections 8.4.2 through 8.4.4.

8.4.1.2 Design for Survivability

In the previous section, we have carried out a basic example of network design without taking into account any survivability strategy. In reality, survivability has to be taken into account. In the case of ASON/GMPLS networks, both protection and restoration can be implemented and each of them can be carried out both at layers 1 and 2. Depending on what solution is chosen for survivability, the impact on the network design changes and network availability has a different value.

Since we are dealing with a simple example to underline the main points of network design, in considering survivability, we will assume to face only fiber cables cuts or DWDM line sites failure.

We will assume that the probability of a cable cut in a given time interval t is constant (does not depends on the absolute time period but only on the interval duration) and for a sufficiently small t can be written as

(8.4)

In our case, Δt is sufficiently small as far as the failure probability will remain much smaller than one and in this case it can be as long as a few months, since the probability that a single link will be broken in a transport network is generally low.

Naturally, if the number of links in the network is very high, the overall probability that one link breaks in the period can be not negligible. In particular, we can assume as a measure of the network reliability the probability that no service disruption occurs in a fixed time if the service was working at the start of the period. We will call this measure network survivability degree D. In Section 8.5, we will give a more precise definition of the standard parameter used for this kind of evaluations: the network availability.

The survivability degree of a network with N_L links without any protection and/or restoration mechanism is

(8.5)

where P(failure, t₀) is the probability of a failure in the considered time interval when the network was working at the interval start (instant t₀) and it is assumed that the single link failure events are independent and their probabilities p_f equal and much smaller than 1.

It is important to note, just for an example, that if the network has 100 links and the probability p_f in the network repair time is 2 × 10⁻⁴, the result of (8.5) is D ≈ 0.98, that is clearly unacceptable in front of a normal request of 1 − D = 10⁻⁵.

This clarifies the need for a survivability strategy.

8.4.1.2.1 Link 1 + 1 Dedicated Protection

This is the most effective but also the most resource-hungry survivability strategy. Every single link is doubled with another identical link running physically on a different path. This is done by deploying, for example, two identical cables on different sides of a highway or of a railways so that if one is broken, the other is sufficiently far not to be involved in the accident. Every node has a protection switch in front of the receiver and the transmitted signal is doubled and sent both on the working and on the protection path (see Figure 8.22).

Figure 8.22 Block scheme of 1 + 1 link dedicated protection.

If this protection strategy is chosen, the base cost of all the fiber infrastructure is more than doubled (since for each link we have twice the number of amplifiers, DCFs, and so on and moreover we have to add the protection switch card with all the related monitoring), but the network design remains the same. The failure probability of such a protection mechanism adopted is such that within the repair time both the working and the protection links fail.

The probability of two failures on two specific links is, in a first approximation,

pf2≈pf2(1−pf)(2NL−2)

Thus the survivability degree can be approximately expressed as

D=1−P(fail)⁢(8.6)

(8.6)

where P(fail) is given by

P(fail)≈NLpf2(1−pf2)(NL−1)⁢(8.7)

(8.7)

If the network has 100 links and p_f in the network, repair time is 2 × 10⁻⁴; the result of is D ≈ 0.999996, a value compliant with values required for D in real networks.

8.4.2.1 Optimized Design Hypotheses

The first step to do to develop a general design procedure that can be applied to every topology and traffic request is to define the design problem data. We will assume a few very general hypotheses to restrict the problem and make it solvable.

• The infrastructure is completely given; that means that geographical position of Points of Presence of the carrier and of fiber cables are given. Equipment can be installed only in the points of presence, but for in-line amplifier sites of DWDM systems.

• We will assume that no OADM branching point exists in DWDM systems.

• We will work in terms of nodes topology: the topology in which the physical network nodes are represented by the nodes of the topology graph. A completely equivalent model can be carried out in the so called links topology, where the topology graph has nodes representing the physical network links. An example of corresponding links and node topologies are given in Figure 8.24.

  

  Figure 8.24 Example of (a) node topology and (b) corresponding link topology.

• We will image that all the fiber cables are owned by the carrier that is designing the network so that the bare use of a free fiber does not entail a cost and a fiber is always available on each route where a cable is present. However, the model can be generalized without changing the base definitions if the fibers are leased and using a fiber is a cost for itself. Also a possible limitation of fiber availability can be easily introduced without substantially changing the model.

• The topology will be meshed at every network layer; design of multiring networks is an important subject, based on different algorithms, and we encourage the interested reader to start the study on multiring networks design from Refs. [10–12].

• The layering is also fixed: physical layer is composed by a WDM transport network based on OXCs. We will assume that the OXCs are opaque and that every link between adjacent OXCs has been correctly designed under a transmission point of view so that we need not deal with transmission systems design when designing the network.

• The client layer is assumed to be an MPLS layer that interfaces the optical layer via the GMPLS overlay model interface. This means that a node comprising an LSR only cannot exist in the network since in the overlay model, the LRS cannot interface DWDM systems and OXCs directly in other nodes.

The design of optically transparent networks is an important subject that we will consider in Chapter 10. The opaque hypothesis also implies that wavelength continuity is not required in crossing an OXC, since the opaque switching machine also performs wavelength conversion.

• In principle, not always an LSR is superimposed on an OXC, and only when it is true, it is possible to communicate between layer 2 and layer 1. Since in practical networks it almost never happens that a node has no local traffic, we will assume that an LSR is always superimposed on an OXC at every node.

• Equipment type is already selected when doing network dimensioning at every network layer, thus all the cost parameters are given. In particular, the DWDM layer is composed only of one type of wavelength channel with a given capacity (let us say 10 Gbit/s).

• As far as QoS is concerned, we will simplify the situation with respect to a real-istic case and we will assume that all the GLSPs are on the same level as far as the survivability is concerned. Also in this case introducing high priority (that is, protected or restored) and best effort GLSPs simply complicate a bit the model, but does not introduce any new element. Introducing realistic QoS classes on the contrary has quite an impact on the optimization model. Several studies have been done in this direction, see, for example, Refs. [13,14].

• We will also assume that a maximum number of GLSPs requests can be done between the same couple of nodes. This is a reasonable limitation, aimed at limiting the number of ports of the network nodes. All the MPLS LSPs will have the same capacity (e.g. 1.2 Gbit/s) that is assumed the unit of capacity of the network. Also this condition can be removed with a slight modification of the optimization algorithm if it is needed.

• In principle, an ideal optimization should be carried out by contemporarily assigning both working and survivability resources. We will see that the ILP problem deriving from the multilayer optimization is very complex (precisely NP-hard). Thus, to simplify the solution under a computational point of view, we will design the network in two steps: first assigning the working resources and in a second phase the survivability ones.

The decision of performing a two-step dimensioning, first working capacity and then protection or restoration, deserves some comments. Several studies in literature demonstrate that final network cost is quite near the optimum when proceeding in this way [6], while the computational complexity is sensibly reduced. Besides in terms of computation complexity, this approach has the practical advantage to allow simulation of different survivability mechanisms by designing the working part of the network only once.

We will exploit this feature in the last part of the chapter, when we will compare different survivability strategies maintaining the same traffic and network. These hypotheses are a sufficient base to lay the foundation for a general network design method based on ILP. In order to do that we have to built a general description of the network that is suitable for the scope.

8.4.2.2 Network Model for ILP

In a multilayer network model, a set of topology and traffic variables can be defined at the same way at infrastructure layer (layer 0 in our model), at the optical layer (layer 1) and at the MPLS layer (layer 2). We will call them with the same symbol with a suitable prefix. The layer prefix will be written on the left of the symbol, so that it is not confused with indices representing elements of a matrix.

For example, the number of nodes will be indicated with ⁰N if we are considering the infrastructure layer, with ¹N if we are considering the optical layer, and ²N if we are dealing­ with the MPLS layer. Naturally variables at different layers are related, in this case ⁰N ≥ ¹N = ²N.

The topology will be described by two matrixes: the adjacency matrix [^sA], whose dimensions are ^sN × ^sN (s = 0, 1, 2), and the link matrix [L], which exists only at the physical layer. The element ^sα_ij of the adjacency matrix is 1 if at the s th layer the nodes i and j are connected via a layer direct connection, otherwise it is zero. The element ℓ_ij of the link matrix contains the length of the physical cable connecting nodes i and j at layer 0 if this cable exists, otherwise it is zero.

The traffic is defined through a traffic matrix [T] of dimension ²N × ²N that contains the request of traffic in terms of LSPs to route in the MPLS layer, its element τ_ij represents in particular the number of LSPs to route between node i and node j of the MPLS layer (layer 2).

If the traffic forecast is not sufficiently reliable, the matrix [T] has to be derived from the traffic statistics with a statistical model. For the moment we will assume that [T] is given, we will analyze in the next section a draft method to manage traffic uncertainly.

We will call

The maximum number T_M of LSPs to be routed between a couple of nodes is given by

However, in the network we have chosen as an example and in general in any network, it is possible to set a maximum number of hops per LSP and it is quite small (generally much smaller than N). For example, optimizing with random traffic the network of Figure 8.25 the maximum number of hops results to be 3 at optical layer and 2 at the MPLS layer. As a matter of fact, more hops generally means longer transmission and more costly DWDM.

Let us assume that H is the maximum number of elements different from zero in one slice of [^sR] obtained by ^sr_ijkdv varying k and d and maintaining constant the other indices. Let us also assume that it is the same for all the layers. Due to the meaning of the elements of [^sR], H results to be the maximum number of hops of a GLSP on layer s.

The matrixes [^sR] have a maximum number of ^sN²H² elements different from zero, which in the previous example is 900 for s = 1 and 400 for s = 2.

Moreover, as we will see in detail, the property that all GLSP are bidirectional can be used to further reduce the number of variables, arriving to 450 for s = 1 and 200 for s = 2 out of a total of 30,000. Thus, if it is needed to compact the representation of the matrixes [^sR], it is possible to adopt a sparse matrix representation. This can be also beneficial to speed up searches in the matrix and thus calculation.

One way to do that is to represent [^sR] through a ²N × ²N × M pointers matrix and to append to each pointer a list of the only nonzero elements with the first two and the last indexes equal to the indexes of the pointer. The records of the list will be H² and each of them will contain the third and the fourth indexes of the nonzero element of [^sR].

This representation has also an important physical meaning that helps in implementing the algorithm. The first two indices are the two ends of an LSP while the last index is the order number of that LSP among all those with the same ends. Thus every pointer represents an LSP and it points to records representing the links traversed at layer s by that LSP.

The computation complexity of the final algorithm is a different issue, which is also triggered by the great number of design variables and we will discuss it at the end of the section. Returning to the definition of the routing matrixes, it is relevant to underline that if an LSP of the MPLS layer is routed through the hth node of the optical layer while it is merged in an optical channel, but it is not sent to the local LSR, we will have ¹r_ijkhv = 1, but ²r_ijkhv = 0 since it does not travel through the node in the MPLS layer, but only in the optical layer. This shows as in the multilayer representation of routing the grooming is automatically comprised.

The matrix [Λ] is a ¹N × ¹N matrix and λ_ij represents the number of wavelength connecting node i with node j to route the LSPs. The wavelength channels connecting OXCs and transporting LSPs that travel only at the optical layer without being extracted by the wavelength up to their destination can be considered GLSPs in the optical layer.

The elements of the matrixes [^sR], [Λ] are the design parameters and the solution of any optimized design has to provide values for these elements. However, this determines also the number of variables of our ILP problem and from this point of view, this is clearly quite a big number. Thus frequently simplifications are introduced to decrease the number of variables. We will discuss a few ways to simplify the problem when we will have a complete algorithm formulation.

Considering the cost model, we will use a generalization of what we have assumed in our example in the last section. Every equipment has a cost constituted by two terms: a platform and an interfaces term.

• DWDM systems cost is given by

  (χw0l(1+⌈w/Mw⌉)+χw1w) where l is the system length and w is the number of wavelengths, while χ_w0 and χ_w1 are constants typical of the system. M_w is the number of wavelengths supported by a single system and ⌈x⌉ indicates the smaller integer greater than x. We will also call W the normalized capacity of one wavelength in term of LSPs (maintaining for definition equal to one the capacity of each LSP).

• The cost of OXC is given by

  [χx0(1+⌈qMq⌉)+χx1q] where q is the number of bidirectional­ line ports of the OXC, M_q is the number of bidirectional line ports supported by a single platform unit (e.g., a single rack), and ⌈x⌉ indicates the smaller integer greater than x. The parameters χ_x0 and χ_x1 are normalized cost constants typical of the OXC.

• The cost of LSR is given by

  [χL0(1+⌈u/Mu⌉)+χL1u] where u is the number of bidirectional line ports of the LSR and M_u is the number of bidirectional line ports supported by a single platform unit (e.g., a single rack). The parameters χ_L0 and χ_L1 are constants typical of the LSR.

The number u_j of bidirectional ports of the jth LSR can be calculated as the sum of the locally generated LSPs plus the number of transit LSPs that are sent to the LSR to perform grooming optimization.

Thus

(8.14)

Similarly, the number q_j of bidirectional ports of the jth OXC is given by

(8.15)

Finally, neglecting the ⌈x⌉ operator to maintain the linearity of the cost function, the ILP target function writes

(8.16)

The target function is linear in the design variables as desired. In this condition the resulting problem is an ILP problem if suitable constraints are set. Arriving at an ILP requires elimination from the cost function the lower integer part to the addenda representing the platform cost of the equipment. This is not a small approximation and it is worth a comment.

Generally, deploying a new DWDM system or a new OXC is an expensive operation with respect to adding a new wavelength to an existing DWDM or a new card to an existing OXC. This is exactly due to the integer part operation that we have neglected in the cost function: that operator represents the fact that the whole platform cost is paid when the first equipment card is installed.

Thus, while in practice the deployment of a new system is always avoided if possible, in our problem, this would not be true, since the first card will have the same cost of all the others. This approximation is important mainly in the case of DWDM systems whose platform has a high cost due to amplifiers and other line equipment.

In specific cases, this approximation can cause the solution to be far from optimum. This situation is detected when there are a lot of DWDM systems or OXCs and LSRs with a very low number of wavelengths or interfaces, only one in the limit case.

In this case, it can be beneficial to create a postprocessing routine that tries to eliminate these systems by rerouting the wavelengths on already existing equipment and verifies if the cost of the network can be lowered in this way. We do not detail how such post-processing can be implemented, technical literature on such heuristics is very rich, and the interested reader can start to approach the problem from [15]. To obtain the results presented in this chapter, no postprocessing is used since looking at the obtained solutions shows that the platform approximation is never so important to change the results significantly.

Considering the constraints, we have to maintain them linear if we want to formulate an ILP problem. The first set of conditions is the flow continuity across the nodes at every layer. This means that at every layer the traffic entering the node from client and line ports has to balance the traffic exiting from client and line port. Looking at the LSR, the continuity, coinciding with the bidirectional nature of the LSR, can be written as

(8.17)

(8.18)

It is important to note that even if (8.17) and (8.18) are constraints, they can be imposed directly on the routing matrix with the effect of reducing the independent variables and decreasing the overall complexity. This is particularly easy if the sparse representation is used for the routing matrix, where LSPs appear explicitly. In this case, only the variables representing an LSP in one direction have to be considered, so halving number of elements of the pointers matrix.

While looking at the OXC we have two continuities, one in terms of wavelengths and one in terms of LSPs. In terms of wavelengths we can write

(8.19)

which means that the wavelength matrix is symmetric.

In terms of LSPs, the bidirectional condition is written as

(8.20)

(8.21)

Last but not least the continuity at the layers’ boundary has to be set. Remembering that an LSR is always present where there is an OXC, we can say that the LSPs traversing the LSR (that is, passed from layer 1 to layer 2 in the nodes) will be in general a subset of the LSR traversing the OXC. This subset has to coincide with the set of LSPs carried by a certain number of wavelengths.

Mathematically this condition is expressed as

(8.22)

Moreover, the number of LSPs terminated in a node has to coincide with the corresponding entry of the traffic matrix, thus

(8.23)

(8.24)

After the bidirectionality, it is needed to assure that the number of wavelengths deployed on each link is sufficient to support the traffic routed along that link and to assign the LSPs to the wavelengths so that passing a set of LSPs between the layers at a certain node coincides with the termination of a certain number of wavelengths in that node. This con-straint requires to introduce the number of wavelengths terminated in a node and the number of wavelengths that bypass the node without termination.

We will call [Ω] ≡ {ω _kh} the ¹N × ¹N matrix containing the wavelengths bypassing node k when arriving from link h-k. The requirement of a certain wavelength number is written as

(8.25)

while the condition on the wavelength termination, utilizing the fact that the locally dropped LSPs are the same both on layer 1 and on layer 2, can be written as

(8.26)

and finally

(8.27)

where W is the maximum number of MPLS LSPs that can be multiplexed into a wavelength.

After the constraints on bidirectionality and capacity, we have to impose the GLSPs continuity through the network. This means two things:

1. If the routing matrix tells that a certain GLSPs travels at layer s from node h to node k with one hop, these nodes have to be contiguous in their own layer, which means that ^sα_hk have to be equal to 1.

2. Successive hops have also to be contiguous, that is, the GLSP can go from node h to node k and then from node k to node j, but not from node j to node v, since after the previous step it was in node k.

First, let us introduce the maximum number of hops ^sD allowed to the GLSP in the network at layer s (it can be ^sN in the extreme case).

The first condition involves obviously the adjacency matrix at the given level, and is written as

(8.28)

which says that if ¹r_ijkhv = 1, implying that the vth path routed through the nodes j and i passes through the link h-k, thus the link h-k has to exist.

In order to express the second condition we can notice that a matrix [^sr_ijkhv] where k and h are the running indexes while the other are fixed represents the path of a GLSP that, by definition, has no loops. Thus only one element per line and one element per column can be different from zero, which is the same as saying that the path enters into the h^th node of the topology only one time and exits from it only one time.

The previous conditions can be written in term of constrain compatible with ILP as

(8.29)

If the condition (8.29) is a constrain of the problem, we are sure that only one element is different from zero among the elements of a column and of a row.

The last step is to express the fact that the path of an GLSP has to be made by adjacent links, that is, the set of nonzero elements ^sr_ijkhv. with i, j, v fixed has to be constituted by concatenated elements like (^sr_ijihv, ^sr_ijhkv, ^sr_ijkjv).

This condition can be expressed by the use of the adjacency matrix. From the nodes adjacency matrix, a links adjacency matrix [^sB] can be easily derived, whose elements ^sβ_ijk are equal to one only if the two adjacent links i, j, and j, k both exist. In particular, it is immediately seen that ^sβ_ijk = ^sα_i,j ^sα_j,k.

Thus the condition we are searching is written as

(8.30)

The meaning of this constraint is the following. Starting from ^sr_ijikv, which are the unique nonzero elements with the first and third index equal to i, the second equal to j and the fifth equal to v, a chain of elements of [^sR] can be constructed by adding to each element the following element having the same first, second, and fifth index and the fourth index moved at the third place.

These last conditions also define a unique nonzero element, so that, if a valid path has been found between i and j, it can be constructed in this way. This also implies that both ^sr_ijhkv, and ^sr _ijkxv,, representing adjacent links of the path, are equal to 1. From this property derives the fact that Equation 8.26 is satisfied.

A similar continuity constraint has to be written across a node for the wavelengths that are not passed to the upper layer by the OXC. In particular, the number of passing through wavelengths entering the OXC has to be equal to the number of passing through wavelengths exiting the OXC.

This condition however is automatically satisfied by the coexistence of the constrain (8.18) and by the property ω_kh = ω_hk deriving from the bidirectional nature of the GMPLS GLSPs. The equations we have derived up to now are sufficient to dimension the network with optimized resources to sustain the traffic, but without any survivability strategy.

In order to add survivability resources a further dimensioning step has to be done. This step is sensibly different if protection or restoration is used. We will limit ourselves to describe the algorithms that can be used in this second step, leaving to the reader the construction of the optimization equations.

8.4.2.3 ILP Design Complexity

The ILP optimization model we have presented in the last section is very explicit in representing the capacity routed on every link, which is useful in those cases in which DWDM links have to be designed after the network general optimization.

Other model exists that are a bit less complex from a computational point of view [16–18], however, whatever model is defined, the optimization of a multilayer mesh network is an NP hard problem, which means that the problem nature implies an exponential complexity increase with the key scale variable, which in our case is the number of nodes. Thus it is important to understand how the computation time can be shortened and what does it mean in terms of accuracy of the found solution. A very good analysis on this point is reported in Ref. [6] and we encourage the reader interested to detailed results on specific examples to start from this reference. Here we will cite and justify intuitively a few techniques for ILP complexity reduction without reporting a detailed quantitative analysis.

The first observation is that ILP goes uniformly toward the optimum solution, thus there is a relevant part of the time used by the algorithm to refine an already good solution. There is a measure of how much the configuration found in an intermediate state is far from the final optimization, which is the so-called solution optimality gap to be evaluated comparing the fully optimized solution with the intermediate one and measuring the cost difference in percentage with respect to the optimum cost.

It has been demonstrated in Ref. [6] a quite general result regarding algorithms like this: if an optimality gap of the order of 3% is accepted the computation time can be significantly shortened and even quite large networks can be analyzed.

In our case, trying to find a full optimal solution in the case of the network with 15 nodes and 25 links with a dense traffic matrix requires a vector computer or a very long time. However, in few hours of working on a well-equipped workstation a solution with a cost within 3% from the optimum can be obtained.

In practice, of course, the optimum solution is not known and the optimality gap cannot be evaluated exactly. However, observing the solution evolution for different running times it is not difficult to estimate the order of magnitude of the solution refinement versus the running time.

Even accepting a certain optimality gap, networks with a number of nodes in the order of 11–13 depending on the traffic matrix and the number of links are the limit for a reasonable execution time. If greater networks have to be analyzed, some more important simplification has to be done.

We can divide the possible simplifications in two classes: physical simplifications related to the particular nature of the problem at hand and mathematical simplifications, which is the mathematical approximation of the original ILP problem that can be applied to all the networks.

8.4.2.4 Design in Unknown Traffic Conditions

The design method we have detailed up to now relies on the fact that a reliable prediction of the traffic to be routed in a considered period of time (e.g., between two major network upgrades) is well known and that this traffic is constituted by connections that will last up to the end of the considered period.

In this case, the network design does not depend on the order in which the connections are opened, since the traffic matrix is available from the beginning. This condition is called deterministic static traffic.

The traffic model can be altered essentially in two ways:

1. Substituting the absolute knowledge of the traffic to be routed in the network with a partial knowledge of the traffic matrix; for example, the element of the matrix can be known only with a great approximation (like 5 < τ_ij < 8) or they can be random variables with a known statistical description. In this case the design is performed in unknown traffic conditions.

2. Instead to be semipermanent, the connections are setup and tear-down several times in the considered observation period on the ground of some statistics. In this case the network is designed under dynamic traffic conditions.

GMPLS sets up semipermanent connections in the transport and MPLS layers, thus dimensioning in conditions of dynamic traffic does not occurs in the bottom layers of the network. On the contrary, if the dimensioning was performed for a TCP/IP network, since TCP set-up and tear down continuously connections design in dynamic conditions would be needed.

On the other hand, the consolidation of competition among carriers and in general the uncertainty on the penetration of new services renders the knowledge of the traffic matrix less and less precise so that dimensioning is often performed in conditions of unknown traffic.

In order to use a dimensioning algorithm in these conditions, it is needed to set up a method to manage the unknown traffic condition. The problem is widely studied in literature and in general we would like to evidence three possible methods [21]:

1. A priori adjustment

2. A posteriori adjustment

3. Probabilistic approach

In the first two methods, the idea is simply to use a safety margin to face possible fluctuations of the traffic matrix. This safety margin reflects at the end in an overdeployment of network resources with respect to the optimum solution dictated by the average traffic matrix. The difference between the two methods is that in the first the average traffic matrix is augmented by the safety margin and then the optimization is carried out as usual.

In the second method all the optimization is carried out on the ground of the average traffic and at the end more resources are deployed with respect to the optimization output. The key issue in both these methods is how to choose the safety margin to be sure to reduce suitably the network rejection probability (that is, the probability a connection request is rejected by the network) while containing the deployment cost.

A discussion based on statistical approach is reported in Ref. [21] where it is demonstrated that it is possible to select an optimum safety margin starting from hypothesis on the statistical distribution of the traffic both in a priori and in a posteriori adjustment. However, even when the margin is chosen in this way, in particular cases, its use leads to excessive overdeployment in some areas of the network where in other areas resource shortage could still happen for modest fluctuations of the traffic variables. Sometimes the problem is solved considering different safety margins in different zones of the network, but other times this gives no advantage.

In any case, after the design of the network using the safety margin–driven overdeployment, simulations have to be generally performed to verify the effectiveness of the design in reducing the rejection probability.

Better results are achieved via the probabilistic method, which uses directly the knowledge of the traffic statistic distribution.

The easier case is that of uniform traffic variation.

In this case the random traffic matrix [T] can be written as follows:

(8.31)

where

[T₀] is the average traffic matrix.

x is a random variable with average equal to one and known probability distribution

In this case, the problem can be formulated as follows: the network has to be designed so that the probability that a connection request is rejected is smaller than a certain limit, called P_R.

The solution is straightforward once the design tool is available. Calling p(x) the probability density of the variable x, it is possible to find a value x₀ so that

(8.32)

If the network is dimensioned for the traffic matrix [T] = x₀[T₀], the rejection probability is surely smaller or equal to P_R.

The situation gets more complex if the traffic matrix depends on more than one random variable, but in line of principle the solution method is the same. Let us assume that [X] is a random matrix, with ²N ≤ V ≤ ²N² nonzero elements, and whose average is the identity matrix [I]. Let also assume to know the joined probability density functions of the V random variables that are elements of [X], called p(x₁, x₂, …, x_V).

If the traffic matrix can be written as [T] = [X] [T₀], the method used for the single random variable can be directly generalized. Naturally it is not easy to derive the model of the traffic matrix and its distribution so that, in the absence of other information, a Gaussian model is often adopted. It is possible to imagine more complex models for the random nature of the traffic, for example, based on Markov chains [21]. In this case, the design gets more complex and we direct the reader to the relevant bibliography for a study of the problem.

8.4.3.1 OSPF Protocol

This is the simpler choice, suggested by the fact that is one of the most diffused routing protocols. Moreover, it is possible to shape the working of the protocol by tagging the network links with a suitable tag and, in case, tagging also the crossing through a node.

The algorithm corresponding to pure OSPF for the routing, as it is generally used in dimensioning tools, remembering that in this case infinite resources are assumed, can be described as follows:

• Evaluate the shortest path between source and destination with the given graph metrics.

• If on every link there is an incomplete DWDM system with available wavelengths, route the GLSP and go to END.

• If there is no wavelength available on one or more links, route the GLSP on the shortest path by opening new DWDM systems where needed.

• END

The operation of opening new DWDM systems is generally an expensive operation since it requires the deployment of new equipment in the central office and the deployment in the field of optical amplifier places.

Thus sometimes effort is paid to avoid the aperture of a new DWDM system by exploring the possibility of routing the new GLSP on a second shortest path. In this case the algorithm is the following (we will call it M-OSPF: Modified OSPF):

• Evaluate the shortest path between source and destination with the given graph metrics.

• If on every link there is an incomplete DWDM system with available wavelengths, route the GLSP and go to END.

• If there is no wavelength with sufficiently capacity available on one or more links, eliminate those links from the topology.

• Find the shortest path in the new topology.

• If on every link there is an incomplete DWDM system with available wavelengths, route the GLSP and go to END.

• Return to the original topology and to the original shortest path. • Add a new DWDM system when needed and route the GLSP.

• END

Naturally this is only one of the possible flavors that OSPF like algorithms can have when used in network design tools. For example, we have listed a version that opens a new DWDM if the second shortest path is also unavailable, but this is not needed. It would be possible to look for the third shortest path and so on. Finally, in this paragraph we have considered explicitly the cost of the links, but the cost of the nodes can be added using the same criterion.

8.4.3.2 Constrained Routing

A different type of routing can be applied when designing a network, more oriented to limit the overall network cost. This is the cost constrained routing whose algorithm can be described as follows:

• Set an order for the GLSP setup requests.

• For each GLSP, find all the paths connecting source and destination.

• With an opportune cost model compute the incremental cost related the possibility of routing the new GLSP on every possible route.

• Among the considered paths chose that with the minimum incremental cost.

• END

Several routing algorithms can be devised introducing different kind of constrains, for example, on the QoS, on the capacity and so on. A class of interesting constrains are the so called dynamic once. A routing constraint is called dynamic when the tags that are put on the links and drive the constrained routing are not constant but change while the situation of the network evolves.

Naturally also in this case an order in which the setup of the GLSP is request has to be fixed. A classical example is constituted by the CAPEX related to the routing of a new wavelength on a certain link. This is generally constant, but when the routing of the wave-length implies the deployment of a new DWDM system, then it becomes very high so limiting as much as possible the opening of new DWDM systems.

Another typical application of dynamic constrains is possible when the number of fibers connecting the network nodes are not unlimited, for example, since the carrier is leasing them, and the bare use of a fiber has its own cost. In this case the cost of using a link for a new wavelength depends on the link length, on the number of fibers available along the link and on the leasing price if applicable. In this condition a dynamic link cost tag is very effective in performing a correct network optimization.

The design methods based on routing strategies are only one of the classes of heuristic algorithms that has been devised to design GMPLS networks. A more complete analysis can be done starting from the following biographies [22–24].

8.4.3.3 Comparison among the Considered Algorithms

In comparing the different heuristics we have introduced, we will take as a reference the results obtained using the ILP optimization.

The comparison is based on sets of 10 random networks designed to cover an approxi-mately square area of the dimension of Italy for all the considered values of the number of nodes. All the considered networks have a connectivity (average number of disjoined path between couples of nodes) around 2.2 and the design does not include any survivability mechanism.

The traffic matrix is uniform and composed of three GLSPs between each couple of OXC. When the order of the connection request is required the dimensioning is repeated in 10 random orders and the lower cost is accepted. The comparison result is reported in Figure 8.26. All costs are normalized with respect to the optimized cost obtained with the ILP.

The first observation is that there is a good performance of the routing-based algorithms, the cost does not change more that 20% from the value obtained from ILP. The reason essentially has to be found in two characteristics of the considered networks:

connectivity and geographic extension. The connectivity is low, generally two paths between any couple of node with a few exceptions, thus a smart optimization algorithm cannot do much better than a simple OSPF having a little number of alternatives. Moreover the number of nodes is also low, so that any advantage achieved in node dimensioning has little impact.

The transmission systems are not so long, so that the platform cost (proportional to the system length) has less impact with respect to a continental network like the North American one. This also explains why the performance of the M-OSPF is so near to the simple OSPF.

It is interesting to note that the situation depicted in the figure is common to a significant part of the national networks in Europe and Asia, but for connectivity that is generally slightly higher, while a completely different problem is the design of a U.S. or a Chinese network due to the greater extension and number of nodes.

8.5.2.1 Bandwidth Usage

Dedicated protection uses exactly the same bandwidth for protection that for working GLSPs. Shared protection is a bit more efficient. In 1:1 protection, the spare bandwidth is used for low-priority traffic, generally best effort services. In this way also the protection bandwidth is used during the normal network working.

Restoration with presignaled GLSPs and reserved bandwidth is generally slight better than shared protection. On the contrary, restoration with complete reprovisioning exploits the bandwidth at best.

8.5.2.2 Recovery Time

All protection mechanisms, due to the preprovision of the protection path, are very fast. The SDH/SONET standard of 50 ms between the failure and the complete service resto-ration is the reference for these methods. Restoration with presignaling and bandwidth reservation has a speed similar to protection, while the other two forms of restoration in general are quite slow.

8.5.2.3 Specific Protocols

Optical path 1 + 1 protection requires no real-time protocol, even if obviously the protection setup has to be advertised at the network elements and at the network manager. However, these communications does not condition the speed of the protection mecha-nism that is completely hardware.

In case of shared protection, a dedicated specific protocol has to be realized in order to manage the protection resources sharing and coordinate the protection switch on and switch off. The SDH/SONET automatic protection switching protocol (APS) is an example of such a protection dedicated protocol. Restoration processes are completely managed by the control plane and uses control plane standard protocols.

8.5.2.4 QoS Issues

In the cases of shared protection and, mainly, of restoration with complete reprovisioning of the path, it is difficult to guarantee some elements of the QoS, i.e., the network traversing time. If services with a high-level QoS are concerned, other survivability methods should be used.

8.5.2.5 Quantitative Comparison

To perform a quantitative comparison, for each survivability strategy we will consider three merit parameters. First is the survivability cost efficiency C_E, which is the percentage of the overall cost expended for working equipment.

In other words,

(8.44)

This parameter represents somehow the results of the design. Besides C_E we will consider. the average GLSP availability, or better the so-called unavailability (U = 1 − A), and finally the parameter RF₂ to characterize the behavior in front of double failure events.

The simulation was carried out using the parameters summarized in Tables 8.7 and 8.9 and the main results, which are weakly dependent on traffic as far as the network is correctly dimensioned, are summarized in Table 8.10.

The first thing to be noticed is that dedicated protection absorbs about 64% of the network cost to deploy protection resources. This is due to the fact that the network connectivity is quite low so that protection paths are quite longer with respect to working paths. This causes DWDM systems used for protection to be much more costly than those used for working traffic. Moreover the protection routes also have an higher number of hops, forcing the nodes to devote a large amount of resources to process transit protection paths.

The situation is only a bit better for shared protection. Again, the poor network connec-tivity, which is frequently a characteristic of real geographical networks, forces protection paths to be frequently quite longer with respect of working path and sharing the protection capacity helps only partially. The result is that even when using shared protection a bit more that 50% of the network CAPEX is used to set up protection capacity.

Table 8.9 Design Parameters for the Design for Survivability of the North American Network

Table 8.10 Main Results of the Performance Evaluation of Different Survivability Strategies

The situation is completely different considering restoration at the MPLS layer. As a matter of fact, while optical channel protection is constrained to maintain the optical channel in its wholeness protecting it as a single entity, MPLS restoration does not have this constraint.

What happens is that when restoration is in place and a link fails, layers 1 and 2 communicate through the common control plane and the GLSPs are individually restored not only by opening other optical paths exploiting free resources in layer 1, but also filling free spaces in already created optical paths and exploiting grooming to better distribute the traffic to be restored.

This causes a negligible increase of the cost of layer 2 (less than 2%) but the effect is strong and the final efficiency of restoration is near 70% if only the optical layer is considered or about 65% if all the network is taken into account.

The first type of restoration, without any preassignment of resources is slightly better due to the stub reuse and stub release procedures, while in the case of the other two restoration techniques, under the point of view of efficiency they have the same performances.

The value of the asymptotic availability, which we will use as a parameter, depends not only on the protection or restoration scheme, but also on the characteristics of the link failure process, on the repair time and on average time passing from the failure discovery to a complete traffic restoration.

In case of protection the time needed to restore a connection is assumed deterministic, while in case of restoration the recovery time is assumed a Gaussian random variable due to the need of running signaling protocols for the last two models of restoration and both routing and signaling for the first case. The time this protocol takes to provision and reserve restoration resources depends on the number of nodes to be traversed by the restored path and on the number of GLSPs to be restored. As a matter of fact, in our model, restoration manages each GLSP as an independent connection to be routed using available layer 1 capacity. As expected, the best availability is reached using dedicated protection, networks using bare rerouting restoration have the lower availability. Last, but not least, Table 8.10 shows the value of the reliability coefficient related to double failures.

The only scheme that has a reasonable probability to survive to a double failure is the dedicated optical channel protection. As a matter of fact, if two links will fail within a link repair time so that a double failure situation occurs, the only case in which traffic is lost is the case in which one failure affects a working path and the other the corresponding protection.

The values of RF₂ are much smaller in the case of shared protection, due to the fact that in this case the traffic is lost either if both working and protection path fails and if two working paths sharing the same protection resources fails. In the considered case, the sharing degree (number of protection links shared by at least two working paths normalized to the number of protection links) is quite high.

A similar comment can be done regards restoration types 2 and 3, since in these cases restoration resources are reserved for restoration, even if not coupled with a particular working path. In this case the sharing is high so that RF₂ is small.

8.5.3.1 Multilayer Survivability

Let us image that shared protection is adopted at Layer 1 with a network design suitable to face all single link failures. In case a multiple failure occurs and some GLSPs cannot be restored by layer 1 protection, layer 2 LSRs manage a restoration process to exploit free transport resources to reroute the affected LSPs.

Naturally the two processes have to be coordinated in order to avoid those problems that can occur in a bad designed multilayer restore mechanism. The most important phenomenon to be avoided is protection instability: if a path is protected at layer 1 and then also restored at layer 2, restoration can cause switching off optical power on the layer 1 protec-tion path. Layer 1 protection mechanism could interpret the fact as a new failure and try to protect the considered and other paths against it, with service disruption and the possibility to start an oscillatory phenomenon between the two layers.

The simpler way to coordinate two reliability mechanism located at different layers is to introduce a sufficiently long hold-off time at the upper layer so to give to the lower layer sufficient time to stabilize. More sophisticated methods however exists to avoid the increment of recovery time due to the fact that the hold-off time is the same for any failure event. These methods are based on the use of signaling protocols to advertise all the rel-evant network entities of the started protection switch.

It is also interesting to compare, at last in a qualitative way, multilayer reliability with a multistrategy single layer reliability, where, for example, both dedicated protection and wavelength level restoration are carried out by OXCs directly at the optical layer.

The basic multilayer approach advantage is that, in case the optical reliability mecha-nism does not work or is compromised by a multiple failure, the successive step is to route MPLS LSPs individually, exploiting the small granularity to perform more efficient restoration.

This is a principle similar to that of grooming, where complexity at layer 2 is traded with more effective exploitation of transmission capacity at layer 1. We will analyze multilayer survivability with the same method used in the previous section: we will design first the network for the required traffic, so deriving information on the network cost.

We will use a three stage optimization, first optimizing the network for working traffic, then dimensioning the bottom layer survivability and at the end the upper layer survivability. The average availability is evaluated by simulation as in previous section. Two multilayer methods will be considered, assuming simple coordination through an hold-off time. The first method, which for simplicity we will call SP-R, is based on 1 + 1 optical GLSP at layer 1 and type 1 restoration at layer 2. This means that after a failure event, the MPLS LSR at layer 2 wait a certain time to let the optical layer to end its recovery attempt. After this time, all the LSR that has not been recovered by the optical layer has to be restored using already the available network resources to route them.

The second method, which briefly we will call R-R, comprises wavelength level type 3 restoration at layer 1 and LSR type 3 restoration at level 2. The survivability method efficiency and the average GLSP availability are reported in Table 8.11 in the conditions detailed in the previous section.

The two multilayer methods are both better with respect to single-layer methods, even if under different points of view. The R-R method attains almost the same availability of 1 + 1 optical protection, but at a much lower cost in terms of redundant equipment in the network. The SP-R method is quite expensive, but has the highest availability among the methods analyzed up to now.

Not only double failures can be efficiently faced, but also a few of triple and quadruple fail-ure events are recovered and a good recovery capability also exists in front of node failures. This property is shown in Table 8.12, where resilience factors of different degree are evaluated.

Besides the factor relative to multiple link failures, the resilience factor RF_n relative to node failure is also reported. This new factor is defined in line with the definition of RF_k as

(8.45)

where

N is the node number

lsp_n(j) is the total number of GLSPs processed in the absence of any failure by node j