Method and system for providing a protection path for connectionless signals in a telecommunications network

A method is provided for providing protection for connectionless signals in a telecommunications network comprising a plurality of nodes. A first protection path is generated from each of the nodes to a destination node. A second protection path is generated from each of the nodes to the destination node. The second protection path is distinct from the first protection path. Protection traffic is routed along one of the protection paths to the destination node.

TECHNICAL FIELD OF THE INVENTION

This invention relates generally to the field of telecommunications and more particularly to a method and system for providing a protection path for connectionless signals in a telecommunications network.

BACKGROUND OF THE INVENTION

Telecommunications systems generally operate in either a connection-oriented mode or a connectionless mode. In a connectionless mode of operation, signals are communicated with less regard for the particular path traversed between source and destination and network elements than in a connection-oriented mode. Connectionless signaling typically focuses on the destination address, or other identification, rather than any particular path between source and destination network elements. Internet Protocol (IP), IPx, and SNA packet switching are examples of connectionless signal transport.

When a failure occurs along the working path being traversed by signals in connectionless communication, the signals must be re-routed to the destination network element along another available path. In conventional telecommunications systems, this re-routing is done by each individual network element with no pre-defined protection paths existing for the connectionless signals. Thus, these systems are inefficient. In addition, bandwidth is wasted by these systems due to inefficient bandwidth reservation schemes.

SUMMARY OF THE INVENTION

In accordance with the present invention, a method and system for providing a protection path for connectionless signals in a telecommunications network are provided that substantially eliminate or reduce disadvantages and problems associated with previously developed systems and methods. In particular, protection paths are pre-defined for connectionless signals, thereby increasing network efficiency.

In one embodiment of the present invention, a method is provided for providing protection for connectionless signals in a telecommunications network comprising a plurality of nodes. A first protection path is generated from each of the nodes to a destination node. A second protection path is generated from each of the nodes to the destination node. The second protection path is distinct from the first protection path. Protection traffic is routed along one of the protection paths to the destination node.

In another embodiment of the present invention, a node is provided in a telecommunications network. The node includes at least two ports and a protection egress port identifier. Each of the ports is operable to receive and transmit traffic for the node. The protection egress port identifier is operable to identify one of the ports as a protection egress port for a specified ingress port and a specified destination node. The protection egress port is operable to transmit protection traffic received at the specified ingress port for the specified destination node.

Technical advantages of the present invention include providing a method for providing a protection path for connectionless signals in a telecommunications network. In particular, two protection paths are provided from each node to each destination node. Accordingly, each node may communicate with each other node along two distinct protection paths. As a result, the network is protected against a single failure. In addition, network efficiency is improved through the use of the pre-defined protection paths.

Other technical advantages will be readily apparent to one skilled in the art from the following figures, description, and claims.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1is a block diagram illustrating a communication system10operable to facilitate communication of connectionless signals in accordance with one embodiment of the present invention. The telecommunications network is a network that transmits voice, audio, video or other suitable types of information, and/or a combination of different types of information between source and destination points. As used herein, the term “connectionless signal” refers to a signal that is not necessarily associated with any particular path from a source network element to a destination network element. In connectionless signaling, routing determinations, such as a determination of the next network element in the path, are generally made at each node in the path. Thus, each node independently identifies the next node in the forwarding chain. Connectionless signals include, for example, Internet Protocol (IP), IPx, SNA and other packet-switched transport signals.

The system10is operable to provide either connectionless communication or a hybrid of connectionless and connection-oriented communication, as described in the co-owned U.S. patent application entitled, “System and Method for Connectionless/Connection Oriented Signal Transport,” filed on Jun. 6, 2000. The system10comprises a core cloud12that comprises one or more core network elements14, or nodes14. The nodes14may communicate with each other via communication links16and with one or more peripheral network elements20via communication links30. The communication links16and30may comprise any wireless, wireline, fiber or other communication medium or combinations of media. A signal communicated via communication links16and/or30may comprise an electrical signal, an optical signal, or any other suitable type of signal or combination of signals.

The peripheral network elements20facilitate communication between the core cloud12and other network elements coupled to other networks, such as networks36. According to the illustrated embodiment, the peripheral network elements20comprise routers20. Each router20couples the core cloud12to a network36via a communication link50. As used herein, “each” means every one of at least a subset of the identified items.

The routers20facilitate routing functions for signals originated or forwarded by interface equipment40and communicated over the networks36. The interface units40comprise personal computers, servers, switches, routers or any other suitable network equipment operable to originate or forward communication signals.

The networks36may comprise any suitable wireline or wireless systems that support communication between network elements using ground-based and/or space-based components. For example, the networks36may comprise public switched telephone networks, integrated services digital networks, local area networks, wide area networks, or any other suitable communication system or combination of communication systems at one or more locations. Each of the networks36may comprise a single network or multiple networks.

In operation, the core cloud12receives connectionless signals from the routers20and routes those signals through the core cloud12to another appropriate router20according to routing rules associated with the received signal. In a particular embodiment, an ingress node14receives an incoming signal from a router20and appends a transport label to the incoming signal which contains instructions or an index to instructions to other nodes14on how to process the signal.

The ingress node14identifies an egress node14associated with a destination router20and communicates the signal toward the egress node14. Nodes14residing between the ingress node and the egress node14receive the signal with the appended transport label and process the signal in accordance with the transport label.

FIG. 2is a block diagram illustrating a system80for providing protection for connectionless signals communicated between the nodes14in accordance with one embodiment of the present invention. Protection is provided by two protection paths100and102. According to one embodiment, a protection path100or102comprises reserved bandwidth that is available for protection traffic.

In the illustrated embodiment, a plurality of nodes14are operable to communicate connectionless signals to and from each other over a working path104which provides a shortest distance path between source and destination nodes14. In order to provide protection for these connectionless signals, a blue protection path100, indicated by a dashed line, and a red protection path102, indicated by a dotted line, are generated such that each node14may communicate with each other node14along two distinct protection paths100and102. Thus, each node14comprises at least two ports: a blue port for transmitting traffic along the blue protection path100and a red port for transmitting traffic along the red protection path102. As illustrated inFIG. 2, a destination node108may be reached by any other node14by following either the blue protection path100or the red protection path102from the other node14.

In order to provide protection with these protection paths100and102, a network must be protectable. The following notation will be used in determining whether or not a network is protectable. A graph G with n vertices, or nodes, and m edges, or links, has a vertex set V(G) and an edge set E(G). The count of the set V(G) is expressed as C(V(G)), which is equivalent to the number of nodes14inside the network. A network is protectable against a single fault if for all x,y in the set G there are two distinct paths inside G. This is the case for any network for which an ear decomposition, as described below, is possible.

A path addition to graph G is the addition to G of a path of length l≧1 between two vertices of G, introducing l−1 new vertices. This added path is referred to as an ear. An ear decomposition is a partition of the graph G into sets P0, . . . , Pksuch that C=P0is a cycle and Pifor i−1 is an ear, or path addition, to the graph G formed by P0∪ . . . ∪Pi−1.

Thus, for each node14in a protectable network, there are two distinct paths100and102to reach any other node14in the network. The paths100and102are distinct in that they share no common nodes14or links. Using the ear decomposition previously described, the protectable network may be decomposed into a ring120and a set of ears130. In accordance with one embodiment, each node14in the network performs the ear decomposition in the same manner to arrive at the same result. It will be understood, however, that any suitable decomposition of the network may be performed by the nodes to arrive at a same result without departing from the scope of the present invention.

The ring120forms the initial part of the protectable network and is denoted by P0. The first ear130acomprises a set of nodes14coupled in a linear fashion with two links coupled to two different nodes14in the ring120. The first ear130ais denoted as P1. The second ear130bis a set of nodes14coupled to two different nodes14in either P0or P1. Although the illustrated embodiment comprises three ears130a, bandc, it will be understood that an ear decomposition of a protectable network may result in any suitable number of ears130.

FIG. 3is a block diagram illustrating a system140for generating the protection paths100and102for connectionless signals communicated between the nodes14in accordance with one embodiment of the present invention. After a protectable network has been decomposed through an ear decomposition, the protection paths100and102are generated as described in connection withFIG. 3.

The ring120is split open at the destination node108and charted horizontally, beginning and ending with the same destination node108. Beginning with the leftmost destination node108, the first ear130dis identified based on a minimum hop count to the destination node108. This ear130dis denoted as P1and is charted horizontally above the ring120.

Any other ears130, such as ears130e, fandg, are identified in a similar manner and charted horizontally above the previous ear130. After charting the ring120and the ears130, the blue protection path100is generated from right to left on the chart and the red protection path102is generated from left to right on the chart. Thus, from any node14, the protection paths100and102to the destination node108do not intersect, resulting in a network which is protected from any single failure.

FIG. 4is a block diagram illustrating one of the nodes14operable to provide protection for connectionless signals in accordance with one embodiment of the present invention. The node14comprises a plurality of ports200, each of which is operable to receive traffic from and transmit traffic to other nodes14in the network. Although the illustrated embodiment comprises seven ports200, it will be understood that any suitable number of ports200greater than one may be implemented in the node14without departing from the scope of the present invention.

The node14also comprises a traffic classifier206for classifying traffic received through ports200as either working traffic or protection traffic, a working traffic egress port identifier210for identifying an egress port200for working traffic, a protection egress port identifier214for identifying an egress port200for protection traffic, a secondary protection egress port identifier218for identifying an egress port200for protection traffic, an egress port evaluator224for evaluating the status of an egress port200, and an egress port selector228for selecting an appropriate egress port200and, in certain situations, discarding traffic.

The traffic classifier206is operable to classify traffic received through the ports200as either working traffic or protection traffic. According to one embodiment, the traffic comprises a traffic identifier identifying itself as either working traffic or protection traffic. For example, the traffic identifier may comprise a specified bit in the traffic, with one value for the bit indicating working traffic and another value for the bit indicating protection traffic. The traffic classifier206is then operable to classify the received traffic based on the traffic identifier for the traffic. It will be understood that the traffic classifier206may classify the traffic as working or protection traffic in any other suitable manner without departing from the scope of the present invention.

The working traffic egress port identifier210identifies an egress port200for working traffic received at any one of the ports200for the node14based on the corresponding destination node for the traffic. Thus, the working traffic egress port identifier210may comprise a database, table or other suitable data store for identifying a particular port200as an egress port for working traffic received at the node14based on the destination node for the working traffic. For example, for working traffic received at the node14having a particular destination node, the working traffic egress port identifier210may identify port F200as the egress port200for that traffic. For another destination node, the working traffic egress port identifier210may identify port C200as the egress port200.

The protection egress port identifier214is operable to identify an egress port200for protection traffic received at any other port200in the node14bound for a particular destination node. Thus, the protection egress port identifier214may comprise a database, table or other suitable data store for identifying a particular port200as an egress port for protection traffic received at the node14based on a particular ingress port200in conjunction with the destination node for the protection traffic. For example, for protection traffic received at port B200having a particular destination node, the protection traffic egress port identifier214may identify port D200as the egress port200for that traffic. For protection traffic received at port B200having a different destination node, the protection traffic egress port identifier214may identify port E200as the egress port200for that traffic.

The secondary protection egress port identifier218is operable to identify an egress port200for transmitting traffic received at another port200in the node14for a particular destination node. Thus, the secondary protection egress port identifier218may comprise a database, table or other suitable data store for identifying a particular port200as an egress port for transmitting protection traffic based on working traffic received at the node14having a particular destination node. For example, for working traffic received at the node14having a particular destination node and for which the working traffic egress port200identified by the working traffic egress port identifier210is unavailable, the secondary protection egress port identifier218may identify port G200as the egress port200for that traffic. Thus, for a particular destination node, the secondary protection egress port identifier218identifies one egress port200.

The egress port evaluator224is operable to evaluate the status of an egress port200in order to determine whether the port200is available or unavailable. The status for a port200is available when the port200is functioning properly, while the status is unavailable when the port200is not functioning properly. According to one embodiment, each port200for the node14provides a status to the egress port evaluator224. Alternatively, the egress port evaluator224may test the ports200to determine status or may request a status from the ports200. It will be understood that the egress port evaluator224may obtain the status of the egress ports200in any suitable manner without departing from the scope of the present invention.

The egress port selector228is operable to select an appropriate egress port200and to discard traffic for which no appropriate egress port200is available. Thus, the egress port selector228may retrieve information from the traffic classifier206, the egress port evaluator224, and one or more of the working traffic egress port identifier210, protection egress port identifier214, and secondary protection egress port identifier218in order to select the appropriate egress port200for a given situation.

In operation, the traffic classifier206, the working traffic egress port identifier210, the protection egress port identifier214, the secondary protection egress port identifier218, the egress port evaluator224and the egress port selector228operate together to route traffic from a particular ingress port200to the appropriate egress port200for the node14. The working traffic egress port200identified by the working traffic egress port identifier210is selected by the egress port selector228for received working traffic that is being forwarded along the working path104. The protection egress port200identified by the protection egress port identifier214is selected by the egress port selector228for received protection traffic that is being forwarded along a protection path100or102. The secondary protection egress port200identified by the secondary protection egress port identifier218is selected by the egress port selector228for traffic received on the working path104, but that is being transmitted onto a protection path100or102.

The egress port selector228is operable to select an egress port200based on traffic classification and on port status. If the traffic classifier206has classified the received traffic as protection traffic, the egress port selector228provides the protection egress port200identified by the protection egress port identifier214to the egress port evaluator224for status evaluation. If the protection egress port status is available, the egress port selector228selects the protection egress port200as the egress port200for the corresponding traffic. However, if the protection egress port status is unavailable, the egress port selector228discards the corresponding traffic.

If the traffic classifier206has classified the received traffic as working traffic, the egress port selector228provides the working traffic egress port200identified by the working traffic egress port identifier210to the egress port evaluator224for status evaluation. If the working traffic egress port status is available, the egress port selector228selects the working traffic egress port200as the egress port200for the corresponding traffic. However, if the working traffic egress port status is unavailable, the secondary protection egress port200identified by the secondary protection egress port identifier218is provided by the egress port selector228to the egress port evaluator224for status evaluation.

If the secondary protection egress port status is available, the egress port selector228selects the secondary protection egress port200as the egress port200for the corresponding traffic. However, if the secondary protection egress port status is unavailable, the egress port selector228discards the corresponding traffic.

Thus, for received working traffic with an available corresponding working traffic egress port200, the traffic is transmitted by the working traffic egress port200along the working path104. Similarly, for protection traffic with an available protection egress port200, the traffic is transmitted by the protection egress port200along the protection path100or102on which the traffic was received. For received working traffic with an unavailable working traffic egress port200, the traffic is transmitted onto a protection path100or102by the secondary protection egress port200, if available. Thus, this traffic is re-routed from the working path104to the protection path100or102having the shortest distance to the destination node. In addition, the traffic identifier for the traffic is changed to indicate that the traffic is now protection traffic as opposed to working traffic.

FIG. 5is a flow diagram illustrating a method for assigning a secondary protection egress port for a particular node14, referred to as node β, for each of a plurality of destination nodes64. The method begins at step500where a selection is made of a destination node64whose secondary protection egress port for node β has not been assigned. At step501, a cost is determined for the blue protection path100based on the distance from the blue port for node β to the destination node. At step502, a cost is determined for the red protection path102based on the distance from the red port for node β to the destination node. At step504the cost from the working traffic egress port200to the destination node is set to infinity. Thus, for the situation in which either the blue port or the red port comprises the working traffic egress port200, the cost for the corresponding protection path100or102is infinity.

At step506, the costs of the protection paths100and102are compared. At decisional step508, a determination is made regarding whether the cost of the blue protection path100is less than the cost of the red protection path102. If the cost of the blue protection path100is less than the cost of the red protection path102, the method follows the Yes branch from decisional step508to step510. At step510, the secondary protection egress port200for node β for the selected destination node is set to the blue port.

Returning to decisional step508, if the cost of the blue protection path100is not less than the cost of the red protection path102, the method follows the No branch from decisional step508to step512. At step512, the secondary protection egress port200for node β for the selected destination node is set to the red port.

From steps510and512, the method continues to decisional step514. At decisional step514, a determination is made regarding whether any destination nodes64remain whose secondary protection egress port for node β has not been assigned. If destination nodes64remain whose secondary protection egress port for node β has not been assigned, the method follows the Yes branch from decisional step514and returns to step500for the selection of another destination node64. However, if no destination node64remains whose secondary protection egress port for node β has not been assigned, the method follows No branch from decisional step514and comes to an end.

FIG. 6is a flow diagram illustrating a method for assigning a protection egress port for each port200for a particular node14, referred to as node β, for each of a plurality of destination nodes64. The method begins at step600where a selection is made of a destination node64whose protection egress ports for node β have not been assigned. This destination node64is denoted as d. At step602, the ring120of the ear decomposition, P0, is identified by determining which ring (i) has the largest nodal count, C(V(P0)), among all the possible decompositions and (ii) has the largest node ID for the nodes14in {d}∩V(P0). Each node14has a corresponding node ID. The largest node ID is used to select a single ring120from multiple possible rings which each have the same nodal count. The ring120starts and ends with the destination node d64.

At step604, the ring120is charted horizontally on a graph. Because the destination node d64is included twice, at the beginning and end of the ring120, the destination node d64has two coordinates on the graph. The left coordinate, which is expressed as X(dl) is zero, while the right coordinate, which is expressed as X(dr), is α (a value greater than zero).

At step606, each node14in the ring120is given a coordinate. Starting from the dlside, the jthnode in P0, denoted as nP0,jwill have a coordinate given by:

At decisional step608, a determination is made regarding whether node β is in the ring120. If node β is in the ring120, the method follows the Yes branch from decisional step608to step610. At step610, a blue port for node β is defined as the port200linked to node nP0,b∈V(P0) with coordinate X(nP0,b)<X(β). At step612, a red port for node β is defined as the port200linked to node nP0,r∈V(P0) with coordinate X(nP0,r)>X(β) At step614, the protection egress port for the red port is set to the blue port. At step616, the protection egress port for the blue port is set to the red port.

At decisional step618, a determination is made regarding whether each port200of node β has been assigned a corresponding protection egress port for the destination node d64. If each port200of node β has been assigned a corresponding protection egress port for the destination node d64, the method follows the Yes branch from decisional step618to decisional step620.

At decisional step620, a determination is made regarding whether any destination nodes d64remain whose protection egress ports for node β have not been assigned. If destination nodes d64remain whose protection egress ports for node β have not been assigned, the method follows the Yes branch from decisional step620and returns to step600for the selection of another destination node d64. However, if no destination nodes D64remain whose protection egress ports for node β have not been assigned, the method follows the No branch from decisional step620and comes to an end.

Returning to decisional step618, if each port of node β has not been assigned a corresponding protection egress port for the destination node d64, the method follows the No branch from decisional step618to step619. At step619, protection egress ports are assigned for the remaining ports200of node β.

Returning to decisional step608, if node β is not in the ring120, the method follows the No branch from decisional step608to step622. At step622, a counter, i, is set to zero. At step624, the counter, i, is incremented by one.

At step626, the ithear130of the ear decomposition, Pi, is identified by determining which ear (i) has the largest nodal count, C(V(Pi)), among all the possible decompositions and (ii) has the largest node ID, xmax, among the nodes14inV(P0∪ . . . ∪Pi−1). The largest node ID is used to select a single ear from multiple possible ears which each have the same nodal count.

At step628, a left border node, eil, is identified for the ear Pi130in the set V(Pi)∩V(P0∪ . . . ∪Pi−1). At step630, a right border node, eir, is identified for the ear Pi130in the set V(Pi)∩V(P0∪ . . . ∪Pi−1).

At decisional step632, a determination is made regarding whether d∈V(Pi). If d∈V(Pi), the method follows the Yes branch from decisional step632to step634. At step634, the ear130starts on the dlside, with X(eil)=X(dl)=0. The ear130may also end with the destination node d64on the drside. This is the case when eil=eir=d. The nodes eiland eirare selected so that X(eil)<X(eir).

Returning to decisional step632, if d∉V(Pi), the method follows the No branch from decisional step632to decisional step642. At step decisional step642, a determination is made regarding whether node β is in V(Pi). If node β is in V(Pi), the method follows the Yes branch from decisional step642to step644. If node β is not in V(Pi), the method follows the No branch from decisional step642and returns to step624where the counter is incremented and the method continues until node β is in V(Pi).

At step644, the blue port of node β is defined as the port200linked to node nPi,b∈V(Pi), with coordinate X(nPi,b)<X(β). At step646, the red port of node β is defined as the port200linked to node nPi,r∈V(Pi), with coordinate X(nPi,r)>X(β). At step648, the protection egress port for the red port is set to the blue port. At step650, the protection egress port for the blue port is set to the red port.

At decisional step652, a determination is made regarding whether node β is the left border node. If node β is the left border node, the method follows the Yes branch from decisional step652to step654. At step654, the protection egress port for the port200of node β leading to other nodes14in V(Pi) is set to the blue port.

Returning to decisional step652, if node β is not the left border node, the method follows the No branch from decisional step652to decisional step653. At decisional step653, a determination is made regarding whether node β is the right border node. If node β is the right border node, the method follows the Yes branch from decisional step653to step656. At step656, the protection egress port for the port200of node β leading to other nodes14in V(Pi) is set to the red port. Returning to decisional step653, if node β is not the right border node, the method follows the No branch from decisional step653and returns to decisional step618.

According to one embodiment, the coordinates for each V(Pi) are made unique. For this embodiment, the coordinates of the jthnode from eil, denoted as nPi,jwith j>0, are assigned to:

where Miis the smallest coordinate in V(P0∪ . . . ∪Pi−1) which is larger than X(eil).

FIG. 7is a flow diagram illustrating a method for reserving bandwidth for connectionless signals communicated between the nodes14in accordance with one embodiment of the present invention. The method begins at step700where a working bandwidth for a central node is reserved. A central node comprises any node14operable to receive traffic from a plurality of peripheral nodes.

At step702, working bandwidth is determined for the central node based on the amount of working traffic that may be received from a particular peripheral node, assuming that the corresponding working path104is available. At step704, protection bandwidth is determined for the central node based on the amount of protection traffic that may be received from the peripheral node, assuming that the corresponding working path104is unavailable.

At step706, the working bandwidth for the central node based on the working traffic from the peripheral node is compared to the protection bandwidth for the central node based on the protection traffic from the peripheral node. At decisional step708, a determination is made regarding whether the protection bandwidth is greater than the working bandwidth. If the protection bandwidth is greater than the working bandwidth, the method follows the Yes branch from decisional step708to step710. At step710, additional working bandwidth is reserved for the central node in accordance with the difference between the protection bandwidth and the working bandwidth associated with the peripheral node.

Returning to decisional step708, if the protection bandwidth is not greater than the working bandwidth, the method follows the No branch from decisional step708to step712. At step712, no additional working bandwidth is reserved for the central node based on the peripheral node.

From steps710and712, the method continues to decisional step714. At decisional step714, a determination is made regarding whether there are more peripheral nodes that may contribute to the bandwidth requirement for the central node. If there are more peripheral nodes, the method follows the Yes branch from decisional step714and returns to step702in order to determine whether or not to reserve additional bandwidth for another peripheral node. However, if there are no more peripheral nodes, the method follows the No branch from decisional step714and comes to an end. In this way, bandwidth is reserved for the central node in accordance with the bandwidth requirements contributed by each of the peripheral nodes from which the central node receives traffic.

According to one embodiment, bandwidth is reserved for the protection paths100and102to provide protection based on Quality of Service. The following notations are introduced to facilitate the discussion of this embodiment.

The set of all nodes14in the telecommunications network will be denoted as NT. Each node14can be expressed as Ixwhere x is the index of the set NT. The count of this set is C(NT).

The set of all unidirectional links in the telecommunications network will be denoted as LT. Each member of LTwill be represented as li, with i being the index of the set LT. The count of this set is C(LT).

Bandwidth reservation involves a determination of the required link bandwidth for protection purposes, expressed as Plxfor any link lxinside the network. In determining protection bandwidth reservation for a link lx, traffic from other links and nodes14onto link lxare considered, as discussed below.

For any working link lyinside the network that sends working traffic onto link lx, the bandwidth for this portion of the traffic on link lxis expressed as Bw(ly/lx) (bandwidth of the working traffic from lyto lx). If link lyis broken, such traffic disappears.

For any broken link lyinside the network, bandwidth for the protection traffic directed onto link lxdue to the broken status of link lyis expressed as Bp(ly/lx).

For any working node Iyinside the network that sends working traffic onto link lx, the bandwidth for this portion of the traffic on link lxis expressed as Bw(Iy/lx) (bandwidth of the working traffic from node Iyto lx). If node Iyis broken, such traffic disappears.

For any broken node Iyinside the network, bandwidth for the protection traffic directed onto link lxdue to the broken status of node Iyis expressed as Bp(Iy/lx).

Thus, for protecting against a failure on link ly, the protection bandwidth on link lx, expressed as Plx(ly), is given by:
Plx(ly)=max(0,Bp(ly/lx)−Bw(ly/lx))  (eqn. 1)

Similarly, for protecting against a failure on node Iy, the protection bandwidth on link lx, expressed as Plx(Iy), is given by:
Plx(Iy)=max(0,Bp(Iy/lx)−Bw(Iy/lx))  (eqn.2)

The array expressed in equation 3 can be numerically sorted and expressed as {p1,p2, . . . , pn} with p1≧p2≧ . . . ≧pnand n=C(LT)+C(NT). For a single failure inside the network, the amount of bandwidth required for protection purposes is:
Plx=p1(eqn. 4)

For M failures, the amount of the bandwidth required for protection purposes is:

Based on equation 3, it is also possible to specify a set of multiple failures for protection, depending on the protection policy (based on the importance of protecting certain links over others). Thus, this reservation mechanism minimizes the amount of bandwidth to be reserved for protection purposes.