draft-ietf-mpls-te-feed-01.txt   draft-ietf-mpls-te-feed-02.txt 
MPLS Working Group Peter Ashwood-Smith MPLS Working Group Peter Ashwood-Smith
Internet Draft Bilel Jamoussi Internet Draft Bilel Jamoussi
Expiration Date: December 2000 Don Fedyk Expiration Date: December 2001 Don Fedyk
Darek Skalecki Darek Skalecki
Nortel Networks Nortel Networks
July 2000 July 2001
Improving Topology Data Base Accuracy with LSP Feedback Improving Topology Data Base Accuracy with LSP Feedback
draft-ietf-mpls-te-feed-01.txt draft-ietf-mpls-te-feed-02.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 43 skipping to change at page 1, line 43
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
One key component of traffic engineering is a concept known as One key component of traffic engineering is a concept known as
constraint based routing. In constraint based routing a topology constraint based routing. In constraint based routing a topology
database is maintained on all participating nodes. This database database is maintained on all participating nodes. This database
contains a complete list of all the links in the network that contains a complete list of all the links in the network that
participate in traffic engineering and for each of these links a set participate in traffic engineering and for each of these links a set
of constraints which those links can meet. Bandwidth, for example, of constraints, which those links can meet. Bandwidth, for example,
is one essential constraint. Since the bandwidth available changes is one essential constraint. Since the bandwidth available changes
as new LSPs are established and terminated the topology database as new LSPs are established and terminated the topology database
will develop inconsistencies with respect to the real network. It is will develop inconsistencies with respect to the real network. It is
not possible to increase the flooding rates arbitrarily to keep the not possible to increase the flooding rates arbitrarily to keep the
database discrepancies from growing. We propose a new mechanism database discrepancies from growing. We propose a new mechanism
whereby a source node can learn about the successes or failures of whereby a source node can learn about the successes or failures of
its path selections by receiving feedback from the paths it is its path selections by receiving feedback from the paths it is
attempting. This fed-back information can be incorporated into attempting. This fed-back information can be incorporated into
subsequent route computations, which greatly improves the accuracy subsequent route computations, which greatly improves the accuracy
of the overall routing solution by significantly reducing the of the overall routing solution by significantly reducing the
skipping to change at page 2, line 16 skipping to change at page 2, line 8
1. Introduction 1. Introduction
Because the network is a distributed system, it is necessary to have Because the network is a distributed system, it is necessary to have
a mechanism to advertise information about links to all nodes in the a mechanism to advertise information about links to all nodes in the
network [IS-IS], [OSPF]. A node can then build a topology map of network [IS-IS], [OSPF]. A node can then build a topology map of
the network. This information is required to be as up-to-date as the network. This information is required to be as up-to-date as
possible for accurate traffic engineered paths. Information about possible for accurate traffic engineered paths. Information about
link or node failures must be rapidly propagated through the network link or node failures must be rapidly propagated through the network
so that recovery can be initiated. Other information about links so that recovery can be initiated. Other information about links
that may be useful for reasons of quality of service include that may be useful for reasons of quality of service includes
parameters such as available bandwidth, and delay. The information parameters such as available bandwidth, and delay. The information
in this topology database is often out of date with respect to the in this topology database is often out of date with respect to the
real network. Available bandwidth is the most critical of these real network. Available bandwidth is the most critical of these
attributes and it can drift substantially with respect to reality attributes and it can drift substantially with respect to reality
due to the low frequency of link state updates that can be sustained due to the low frequency of link state updates that can be sustained
in a very large topology. We refer to the deviation in the topology in a very large topology. We refer to the deviation in the topology
database available bandwidth as being optimistic if the database database available bandwidth as being optimistic if the database
shows more available bandwidth than there really is, or pessimistic shows more available bandwidth than there really is, or pessimistic
if the topology database shows less bandwidth than there really is. if the topology database shows less bandwidth than there really is.
This distinction is important because we shall propose an efficient This distinction is important because we shall propose an efficient
skipping to change at page 5, line 19 skipping to change at page 4, line 47
periodically snap the error back to 0 at flooding intervals. The periodically snap the error back to 0 at flooding intervals. The
effect of the feedback algorithm is to bring an optimistic error effect of the feedback algorithm is to bring an optimistic error
back to zero without having to wait for the flood interval. On back to zero without having to wait for the flood interval. On
average then, the feedback algorithm tends to halve the absolute average then, the feedback algorithm tends to halve the absolute
error, keeping it mostly negative or pessimistic. This makes sense error, keeping it mostly negative or pessimistic. This makes sense
since a routing system will never give paths to links that it thinks since a routing system will never give paths to links that it thinks
do not have resources and as a result its pessimistic view of the do not have resources and as a result its pessimistic view of the
world stays that way until it gets a flood. This relieves the IGP world stays that way until it gets a flood. This relieves the IGP
updates of the most urgent requirement of flooding when bandwidth is updates of the most urgent requirement of flooding when bandwidth is
consumed. Availability of new bandwidth occurs when paths are consumed. Availability of new bandwidth occurs when paths are
released or new links become available. New links are accompanied released or new links become available. New links are already
by floods. Significant releases of bandwidth can be broadcast at accompanied by floods. Significant releases of bandwidth can be
relatively low frequencies in the order of several minutes with broadcast at relatively low frequencies in the order of several
little operational impact. minutes with little operational impact.
Extensive operational experience with this feedback protocol in Extensive operational experience with this feedback protocol in
proprietary Nortel Networks (pre-standard CR-LDP) products has shown proprietary Nortel Networks (pre-standard CR-LDP) products has shown
it to work very well for networks up to 1000 nodes with significant it to work very well for networks up to 1000 nodes with significant
flooding intervals damped to several minutes. Without this protocol, flooding intervals damped to several minutes. Without this protocol,
these networks would block setups for up to several minutes. With these networks would block setups for up to several minutes. With
this protocol, the blocking in most cases is reduced to a small this protocol, the blocking in most cases is reduced to a small
number of retry attempts which is usually sub-second depending number of retry attempts which is usually sub-second depending
mostly on the propagation delays in the network. mostly on the propagation delays in the network.
skipping to change at page 8, line 37 skipping to change at page 7, line 37
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|U|F| 0x831 | Length | |U|F| 0x831 | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| BANDWIDTH UNRESERVED AT HOLDING PRIORITY 0 (IEEE float) | | BANDWIDTH UNRESERVED AT HOLDING PRIORITY 0 (IEEE float) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . . . . . . . . . . . . . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| BANDWIDTH UNRESERVED AT HOLDING PRIORITY 7 (IEEE float) | | BANDWIDTH UNRESERVED AT HOLDING PRIORITY 7 (IEEE float) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPV6 address of interface (near end) | | IPV6 address of interface (near end) |
| _____ | | ........ |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPV6 address of interface (far end) | | IPV6 address of interface (far end) |
| _____ | | ........ |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
5. Detailed Procedures 5. Detailed Procedures
On receipt of a withdraw, notification, query-reply, or mapping On receipt of a withdraw, notification, query-reply, or mapping
message pertaining to a request made by CR-LDP (as opposed to LDP), message pertaining to a request made by CR-LDP (as opposed to LDP),
a feedback TLV of the appropriate format for the interface over a feedback TLV of the appropriate format for the interface over
which the message was received is inserted into the message before which the message was received is inserted into the message before
forwarding it back to the source of the request. The 8 bandwidth forwarding it back to the source of the request. The eight bandwidth
values are filled in with the outgoing bandwidth available on this values are filled in with the outgoing bandwidth available on this
interface for each of the 8 holding priorities in bytes per second. interface for each of the 8 holding priorities in bytes per second.
Finally the interface's address and far end address are placed in Finally the interface's address and far end address are placed in
the TLV. the TLV.
On receipt of a CR-LDP request message which cannot be satisfied. A On receipt of a CR-LDP request message which cannot be satisfied. A
notification message is formatted normally. The 8-bandwidth values notification message is formatted normally. The 8-bandwidth values
are filled in with the outgoing bandwidth available on this are filled in with the outgoing bandwidth available on this
interface for each of the 8 holding priorities in bytes per second. interface for each of the 8 holding priorities in bytes per second.
Finally, the interface's address and far end address are placed in Finally, the interface's address and far end address are placed in
skipping to change at page 10, line 4 skipping to change at page 8, line 47
Implementations MUST NOT permit bandwidth information learned by Implementations MUST NOT permit bandwidth information learned by
this feedback mechanism to be re-flooded via IS-IS, OSPF or any this feedback mechanism to be re-flooded via IS-IS, OSPF or any
other IGP. The bandwidth information learned via these feedback other IGP. The bandwidth information learned via these feedback
mechanisms is to be used ONLY for source route computations on the mechanisms is to be used ONLY for source route computations on the
nodes that are directly on the path that fed back the bandwidth. nodes that are directly on the path that fed back the bandwidth.
Normally only the source node of the LSP, or perhaps intermediate Normally only the source node of the LSP, or perhaps intermediate
gateway nodes will use this information. It is however permitted for gateway nodes will use this information. It is however permitted for
intermediate nodes that are forwarding this feedback information to intermediate nodes that are forwarding this feedback information to
store it for their own local source route computations. store it for their own local source route computations.
There is a possibility of a race condition between the bandwidth There is a possibility of a race condition between the bandwidth
information that is received via feedback and that which is received information that is received via feedback and that, which is
via a normal IGP flood. While there may be a discrepancy between the received via a normal IGP flood. While there may be a discrepancy
two, both are within a few 100 milliseconds of being correct. between the two, both are within a few 100 milliseconds of being
Solutions to allow us to determine which information is most up to correct. Solutions to allow us to determine which information is
date (say by adding a sequence number) do not add any significant most up to date (say by adding a sequence number) do not add any
benefit. Constraint based, source routed systems will always have significant benefit. Constraint based, source routed systems will
errors in the local topology database with respect to the real always have errors in the local topology database with respect to
network. We can reduce these errors through reduced flooding the real network. We can reduce these errors through reduced
intervals, path following feedback and selective flooding but we flooding intervals, path following feedback and selective flooding
cannot realistically reduce the errors below the second or so range. but we cannot realistically reduce the errors below the second or so
As a result propagation delay order race conditions are noise with range. As a result propagation delay order race conditions are noise
respect to the average expected errors. An implementation SHOULD with respect to the average expected errors. An implementation
therefore consider the most recently received update (IGP or SHOULD therefore consider the most recently received update (IGP or
feedback) as being the most up to date. feedback) as being the most up to date.
7. Future considerations 7. Future considerations
Constraint based routing systems such as CR-LDP will in the future Constraint based routing systems such as CR-LDP will in the future
offer other forms of constraint than simply reserved bandwidth. offer other forms of constraint than simply reserved bandwidth.
Actual utilization levels, current congestion levels, number of Actual utilization levels, current congestion levels, number of
discrete channels/wavelengths available etc. are all possible discrete channels/wavelengths available etc. are all possible
constraints that change rapidly and which must be taken into constraints that change rapidly and which must be taken into
consideration when computing a route. It is expected that this consideration when computing a route. It is expected that this
mechanism will be used to feedback these and other new forms of link mechanism will be used to feedback these and other new forms of link
constraining data. constraining data.
8. RSVP consideration 8. RSVP consideration
skipping to change at page 10, line 36 skipping to change at page 9, line 17
discrete channels/wavelengths available etc. are all possible discrete channels/wavelengths available etc. are all possible
constraints that change rapidly and which must be taken into constraints that change rapidly and which must be taken into
consideration when computing a route. It is expected that this consideration when computing a route. It is expected that this
mechanism will be used to feedback these and other new forms of link mechanism will be used to feedback these and other new forms of link
constraining data. constraining data.
8. RSVP consideration 8. RSVP consideration
Nothing precludes the use of such feedback mechanisms with a similar Nothing precludes the use of such feedback mechanisms with a similar
TLV structure in the RSVP Resv and other reverse flowing messages TLV structure in the RSVP Resv and other reverse flowing messages
although repeatedly applying a fed-back should be avoided since it although repeatedly applying unchanged feedback should be avoided
increases the race condition window with flooded LSPs. This could be since it increases the race condition window with flooded LSPs. This
accomplished by a simple rule that only permits fed-back information could be accomplished by a simple rule that only permits feedback
on the original RESV, not on subsequent refreshes. information on the original RESV, not on subsequent refreshes.
9. Intellectual Property Consideration 9. Intellectual Property Consideration
The IETF has been notified of intellectual property rights claimed The IETF has been notified of intellectual property rights claimed
in regard to some or all of the specification contained in this in regard to some or all of the specification contained in this
document. For more information consult the online list of claimed document. For more information consult the online list of claimed
rights. rights.
10. Security Considerations 10. Security Considerations
skipping to change at page 11, line 4 skipping to change at page 9, line 35
in regard to some or all of the specification contained in this in regard to some or all of the specification contained in this
document. For more information consult the online list of claimed document. For more information consult the online list of claimed
rights. rights.
10. Security Considerations 10. Security Considerations
This document raises no new security considerations for CR-LDP, RSVP This document raises no new security considerations for CR-LDP, RSVP
or MPLS in general. or MPLS in general.
11. Acknowledgments 11. Acknowledgments
The authors would like to thank Keith Dysart for his guidance, and The authors would like to thank Keith Dysart for his guidance, and
Jerzy Miernik for helping implement these concepts and bringing them Jerzy Miernik for helping implement these concepts and bringing them
to life. to life.
12. References 12. References
[CR-LDP] Constraint-Based LSP Setup using LDP, draft-ietf-mpls-cr- [CR-LDP] Jamoussi, B. et al., _Constraint-Based LSP Setup using
ldp-04.txt LDP_, Internet Draft, draft-ietf-mpls-cr-ldp-05.txt, February 2001.
[LDP] LDP Specification, draft-ietf-mpls-ldp-05.txt [LDP] Andersson, L. et al., _LDP Specification_, RFC 3032, January
2001.
[IS-IS] Extensions to IS-IS for traffic engineering, draft-ietf- [IS-IS] Li, T., Smit, H., _Extensions to IS-IS for traffic
isis-traffic-01.txt engineering_, Internet Draft, draft-ietf-isis-traffic-03.txt, June
2001.
[QUERY] MPLS LDP Query Message Description, draft-paraschiv-mpls- [QUERY] Ashwood-Smith, P., Paraschiv, A., _MPLS LDP Query Message
lsp-query-00.txt. Description_, Internet Draft, draft-anto-ldp-query-02.txt, May 2001
13. Author's Addresses 13. Author's Addresses
Peter Ashwood-Smith Bilel Jamoussi Peter Ashwood-Smith Bilel Jamoussi
Nortel Networks Corp. Nortel Networks Corp. Nortel Networks Corp. Nortel Networks Corp.
P.O. Box 3511 Station C, 600 Technology Park Drive P.O. Box 3511 Station C, 600 Technology Park Drive
Ottawa, ON K1Y 4H7 Billerica, MA 01821 Ottawa, ON K1Y 4H7 Billerica, MA 01821
Canada USA Canada USA
Phone: +1 613-763-4534 phone: +1 978-288-4506 Phone: +1 613-763-4534 phone: +1 978-288-4506
petera@nortelnetworks.com jamoussi@nortelnetworks.com petera@nortelnetworks.com jamoussi@nortelnetworks.com
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/