One document matched: draft-kini-restoration-shared-backup-00.txt
Internet Draft Sriganesh Kini
Expires : April, 2001 Murali Kodialam
<draft-kini-restoration-shared-backup-00.txt> T.V.Lakshman
- Bell Labs
Curtis Villamizar
- Avici Systems
Shared backup Label Switched Path restoration
draft-kini-restoration-shared-backup-00.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
Traffic engineering using MPLS involves the setting up of label
switched paths (LSP) possibly with explicit routing and with
bandwidth guarantees (for label switched paths). The reliability of
these LSPs can be increased by providing a backup LSP onto which
traffic can be switched upon failure of an element in the path of the
active LSP. Backup LSPs can be routed in a way that bandwidth can be
shared between backup links of more than one active path while still
guaranteeing recoverability for a set of failures. This sharing greatly
increases the network efficiency, thereby increasing the number of LSPs
that can be carried while maintaining guarantees. Algorithms which can
route such recoverable LSPs while using only aggregate network usage
information are being developed.
This informational draft illustrates the concept of sharing links along
backup paths and examines the requirements from link state
information and the signaling functions.
S. Kini, et al Expires April, 2001 [Page 1]
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000
1. Introduction
The Multi Protocol Label Switching (MPLS) working group has developed a
framework and standards which enable traffic engineering of networks.
The framework is described in [8] and the architecture is described in
[7]. The MPLS framework is becoming increasing popular to traffic
engineer IP networks.
MPLS uses the label swapping paradigm to switch data over an LSP. The
functional capabilities required for operations in an MPLS domain are
described in [9]. The network layer routing determines the route of an
LSP from the topology of the network and the current demands of the
applications utilizing the network. Link state routing protocols like
OSPF (as described in [1]) and IS-IS (as described in [2]) can provide
the topology information to network layer routing that engineers
traffic. Signaling protocols like RSVP (as described in [9] and [10])
and LDP (as described in [11] and [12]) are then used to setup the LSP.
Since a LSP traverses a fixed path in the network, its reliability
depends on the links and nodes along the path. Traditionally IP
networks have carried only best-effort traffic. However new applications
are using the IP network infrastructure in ways that make it highly
desirable to incorporate faster repair.
MPLS based recovery provides a faster restoration mechanism
than layer 3 routing. Several methods have been proposed for MPLS
based recovery. A framework and terminology for MPLS based recovery
is described in [3].
Setting up a backup LSP for an active LSP (e.g. [6]) is one way to
achieve reliability. A straightforward solution to this problem is to
find two disjoint paths. However this requires at least twice the amount
of network resources. For a restoration objective like single link
failure recovery, links on the backup path can be shared between
different active paths in a way that single link failure restoration
is guaranteed. This must be done without requiring per-LSP routing
information for all LSPs currently carried by the network, since keeping
track of per-LSP routing information for the whole network is not
feasible. It is more desirable to efficiently route recoverable LSPs
with shared backups using only aggregate network usage information.
Aggregate information useful for setting up shared backup paths is
obtainable by adding a few new information elements to the link state
advertisement of a link state routing protocol like OSPF or ISIS.
Algorithms which can operate using aggregate information are being
developed. An example of one such algorithm is described later.
Other examples of such algorithms are in [4],[5]. These algorithms
achieve a very high degree of sharing by using aggregate information
that can be conveyed by a link state routing protocol.
The key concept of sharing backup paths is described in section 2.
The requirements from link state protocols and signaling protocols
is briefly examined in section 3.
S. Kini, et al Expires April, 2001 [Page 2]
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000
2. Concept of sharing backup paths
A brief description of the concept of sharing is described in this
section.
The model under which these principle of sharing is expected to be
deployed is very general. Requests for LSPs should be routed as they
arrive (online). A new type of LSP can be computed where given
a source and destination, an active path and a backup path (possibly
shared) is calculated. Links on the backup path are possibly shared
between backup paths of other active paths in a way that single
link/node failure restoration is guaranteed. As requests for setup and
teardown of such LSPs arrive and link failures occur the total link
bandwidth allocated for active paths and backup paths vary accordingly.
Section 2.1 through 2.3 illustrate the sharing concept through some
examples and section 2.4 outlines one simple algorithm that achieves
sharing and guarantees single link failure recovery. This algorithm
needs only aggregate information. [4] and [5] are other instances of
similar algorithms. They achieve a very high degree of sharing using
only aggregate information.
2.1 Sharing backup : single link failure recovery
Figure 1 illustrates a simple case of sharing of backup paths in a way
that single link failure can be recovered. A and B are label switch
routers. Say each link is of unit bandwidth and each LSP request
is also of unit bandwidth. L1 and L2 are two active paths. L1b is the
backup for L1 and L2b is the backup for L2. L1b and L2b can be
accomodated on the same link by sharing the bandwidth. Clearly, if
either one of L1 or L2 fail the system can recover.
L1
____________________
/ \
| |
---- L1b L2b ----
| A |----------------| B |
---- ----
| |
\____________________/
L2
Figure 1 : Sharing backup links with link failure recovery
2.2 Sharing backup : single node failure recovery
Figure 2 illustrates a simple case of sharing of backup paths in a way
that single node failure can be recovered.
S. Kini, et al Expires April, 2001 [Page 3]
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000
---- L2 ----
| A |--------------------------| B |
---- ----
| |
|L2b |L2b
| |
| |
---- L1b L2b ----
| C |--------------------------| D |
---- ----
| |
|L1b |L1b
| |
| |
---- L1 ---- L1 ----
| E |---------| F |-----------| G |
---- ---- ----
Figure 2 : Sharing backup links with node failure recovery
A,B, ... G are label switch routers. L1 is an active path along E-F-G.
The corresponding backup L1b is along the path E-C-D-G. Similarly
L2 is an active path along A-B. L2b is the corresponding backup path
along A-C-D-B. Clearly, if max-bandwidth(L1,L2) is allocated on link
C-D for L1b and L2b together, the system can ensure single node failure
recovery.
2.3 Local restoration : single link/node recovery
Local restoration (SONET like recovery constraints), can be achieved
by providing intermediate nodes with a backup path. The intermediate
nodes can switchover to the backup path immediately on getting a failure
indication.
Figure 3 illustrates an example of local restoration for single link
failure recovery.
---- ----
____| D |____ _____| E |____
L1b/ ---- \L1b /L1b ---- \L1b
/ \ / \
---- L1 ---- L1 ----
| A |--------------| B |---------------| C |
---- ---- ----
Figure 3 : Local restoration of link failure
Clearly from section 2.1 sharing of backup paths can be done in this
case to achieve single link/node failure recovery. In fact a further
degree of sharing can be achieved by sharing of links between segments
of the backup paths A-D-B and B-E-C (intra demand sharing).
S. Kini, et al Expires April, 2001 [Page 4]
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000
Similarly Figure 4 illustrates an example of local restoration for single
node failure recovery.
---- ----
________________| E |_____________ _____| F |____
L1b/ ---- \L1b /L1b ---- \L1b
/ \ / \
---- L1 ---- L1 ---- L1 ----
| A |--------------| B |---------------| C |--------------| D |
---- ---- ---- ----
\ /
\L1b ---- /L1b
\_______________| G |_____________/
----
Figure 4 : Local restoration of single node/link failure
Clearly from section 2.1 and 2.2, Figure 3, and Figure 4 backup sharing
(intra and inter demand sharing) can be done in this case as well.
2.4 A simple algorithm for calculated shared backup path
Terminology : Say for link (i,j)
i) the cumulative bandwidth allocated for active paths is F(i,j)
ii) the cumulative bandwidth allocated for backup paths is G(i,j)
iii) the residual bandwidth free for allocation is R(i,j)
For a request of bandwidth b the active path is calculated as the
shortest path on the topology of links that have R(i,j) > b.
Let M be the max of the F values along the active path. The backup
path is calculated as follows. The cost of a link (u,v) is now taken as
i) 0 if { M+b < G(u,v) } else
ii) b if { G(u,v) <= M and b <= R(u,v) } else
iii) M+b - G(u,v) if { M <= G(u,v) and M+b <= G(u,v)+R(u,v) } else
iv) infinity in all other cases
The backup path is calculated as the shortest path on the topology with
the cost of links calculated as above.
The lack of an active path or a backup path with finite cost represent
failure conditions.
3. Requirements for shared backup lsp restoration
Requirements from link state routing protocols and signaling protocols
is briefly described in this section.
Aggregate information about a link that has to be conveyed by a link
state routing protocol should consist of
S. Kini, et al Expires April, 2001 [Page 5]
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000
i) The total bandwidth used on the link for active LSPs
ii) Total bandwidth used on the link for backup LSPs
iii) Total available bandwidth on the link
The signaling protocol information elements should consist of
i) The setup information and procedures for a backup LSP
ii) The association between the active and backup LSP
4. Security Considerations
This document raises no new security issues.
5. Acknowledgements
The authors would like to thank Vishal Sharma and Roch Guerin for their
comments on this work.
6. References
[1] Moy, J,, "OSPF Version 2" RFC 2328, April 1998.
[2] "Intermediate System to Intermediate System Intra-Domain Routeing
Exchange Protocol for use in Conjunction with the Protocol for
Providing the Connectionless mode Network Service (ISO 8473)", ISO
DP 10589, February 1990.
[3] Makam, V., Sharma, V., Huang, C., Owens, K., Mack-Crane, B., et
al, "A Framework for MPLS-based Recovery," Work in Progress,
Internet Draft <draft-makam-mpls-recovery-frmwrk-00.txt>,
February 2000.
[4] Lakshman, T.V., Kodialam, M., "Dynamic Routing of Bandwidth
Guaranteed Tunnels with Restoration", Proceedings of INFOCOM 2000,
April 2000.
[5] Lakshman, T.V., Kodialam, M., "Dynamic Routing of Bandwidth
Guaranteed Tunnels Using Aggregated Link Usage Information",
To be published in Proceedings of INFOCOM 2001.
[6] Haskin, D., Krishnan, R., "A Method for Setting an Alternative Label
Switched Paths to Handle Fast Reroute", Work in Progress, Internet Draft
<draft-haskin-mpls-fast-reroute-04.txt>, May 2000.
[7] Rosen, E., Viswanathan, A., and Callon, R., "Multiprotocol Label
Switching Architecture", Work in Progress, Internet Draft <draft-ietf-
mpls-arch-06.txt>, August 1999.
[8] Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G.,
Viswanathan, A., "A Framework for Multiprotocol Label Switching",
Work in Progress, Internet Draft <draft-ietf-mpls-framework-05.txt>,
September 1999.
[9] Braden, R., Zhang, L., Berson, S., Herzog, S., "Resource
S. Kini, et al Expires April, 2001 [Page 6]
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000
ReSerVation Protocol (RSVP) -- Version 1 Functional
Specification", RFC 2205, September 1997.
[10] Awduche, D. et al "RSVP-TE: Extensions to RSVP for LSP Tunnels", Work in
Progress, Internet Draft <draft-ietf-mpls-rsvp-lsp-tunnel-07.txt,
August 1999.
[11] Andersson, L., Doolan, P., Feldman, N., Fredette, A., Thomas,
B., "LDP Specification", Work in Progress, Internet Draft <draft-
ietf-mpls-ldp-06.txt>, September 1999.
[12] Jamoussi, B. "Constraint-Based LSP Setup using LDP", Work in
Progress, Internet Draft <draft-ietf-mpls-cr-ldp-03.txt>,
September 1999.
7. Author's Addresses
Sriganesh Kini
Lucent Technologies, Bell Labs
Room 4C-526, 101 Crawfords Corner Road
Holmdel, NJ 07733-3030
Phone : 732 949 6418
Email : kini@dnrc.bell-labs.com
Murali Kodialam
Lucent Technologies, Bell Labs
Room 4D-525, 101 Crawfords Corner Road
Holmdel, NJ 07733-3030
Phone : 732 949 6296
Email : muralik@dnrc.bell-labs.com
T.V.Lakshman
Lucent Technologies, Bell Labs
Room 4D-531, 101 Crawfords Corner Road
Holmdel, NJ 07733-3030
Phone : 732 949 4778
Email : lakshman@dnrc.bell-labs.com
Curtis Villamizar
Avici Systems
Email : curtis@avici.com
S. Kini, et al Expires April, 2001 [Page 7]
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000
Full Copyright Statement
Copyright (C) The Internet Society (2000). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph
are included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
S. Kini, et al Expires April, 2001 [Page 8]
| PAFTECH AB 2003-2026 | 2026-04-23 22:17:22 |