Request for Comments: 3212 L. Andersson, Utfors AB
Category: Standards Track R. Callon, Juniper Networks
R. Dantu, Netrake Corporation
L. Wu, Cisco Systems
P. Doolan, OTB Consulting Corp.
T. Worster
N. Feldman, IBM Corp.
A. Fredette, ANF Consulting
M. Girish, Atoga Systems
E. Gray, Sandburst
J. Heinanen, Song Networks, Inc.
T. Kilty, Newbridge Networks, Inc.
A. Malis, Vivace Networks
January 2002
Constraint-Based LSP Setup using LDP
Status of this Memo
This document specifies an Internet standards track protocol for the
Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2002). All Rights Reserved.
Abstract
This document specifies mechanisms and TLVs (Type/Length/Value) for
support of CR-LSPs (constraint-based routed Label Switched Path)
using LDP (Label Distribution Protocol).
This specification proposes an end-to-end setup mechanism of a CR-LSP
initiated by the ingress LSR (Label Switching Router). We also
specify mechanisms to provide means for reservation of resources
using LDP.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [6].
Table of Contents
1. Introduction....................................................3
2. Constraint-based Routing Overview...............................4
2.1 Strict and Loose Explicit Routes...............................5
2.2 Traffic Characteristics........................................5
2.3 Preemption.....................................................5
2.4 Route Pinning..................................................6
2.5 Resource Class.................................................6
3. Solution Overview...............................................6
3.1 Required Messages and TLVs.....................................7
3.2 Label Request Message..........................................7
3.3 Label Mapping Message..........................................9
3.4 Notification Message..........................................10
3.5 Release , Withdraw, and Abort Messages........................11
4. Protocol Specification.........................................11
4.1 Explicit Route TLV (ER-TLV)...................................11
4.2 Explicit Route Hop TLV (ER-Hop TLV)...........................12
4.3 Traffic Parameters TLV........................................13
4.3.1 Semantics...................................................15
4.3.1.1 Frequency.................................................15
4.3.1.2 Peak Rate.................................................16
4.3.1.3 Committed Rate............................................16
4.3.1.4 Excess Burst Size.........................................16
4.3.1.5 Peak Rate Token Bucket....................................16
4.3.1.6 Committed Data Rate Token Bucket..........................17
4.3.1.7 Weight....................................................18
4.3.2 Procedures..................................................18
4.3.2.1 Label Request Message.....................................18
4.3.2.2 Label Mapping Message.....................................18
4.3.2.3 Notification Message......................................19
4.4 Preemption TLV................................................19
4.5 LSPID TLV.....................................................20
4.6 Resource Class (Color) TLV....................................21
4.7 ER-Hop semantics..............................................22
4.7.1. ER-Hop 1: The IPv4 prefix..................................22
4.7.2. ER-Hop 2: The IPv6 address.................................23
4.7.3. ER-Hop 3: The autonomous system number....................24
4.7.4. ER-Hop 4: LSPID............................................24
4.8. Processing of the Explicit Route TLV.........................26
4.8.1. Selection of the next hop..................................26
4.8.2. Adding ER-Hops to the explicit route TLV...................27
4.9 Route Pinning TLV.............................................28
4.10 CR-LSP FEC Element...........................................28
5. IANA Considerations............................................29
5.1 TLV Type Name Space...........................................29
5.2 FEC Type Name Space...........................................30
5.3 Status Code Space.............................................30
6. Security Considerations........................................31
7. Acknowledgments................................................31
8. Intellectual Property Consideration............................31
9. References.....................................................32
Appendix A: CR-LSP Establishment Examples.........................33
A.1 Strict Explicit Route Example.................................33
A.2 Node Groups and Specific Nodes Example........................34
Appendix B. QoS Service Examples..................................36
B.1 Service Examples..............................................36
B.2 Establishing CR-LSP Supporting Real-Time Applications.........38
B.3 Establishing CR-LSP Supporting Delay Insensitive Applications.38
Author's Addresses................................................39
Full Copyright Statement..........................................42
1. Introduction
Label Distribution Protocol (LDP) is defined in [1] for distribution
of labels inside one MPLS domain. One of the most important services
that may be offered using MPLS in general and LDP in particular is
support for constraint-based routing of traffic across the routed
network. Constraint-based routing offers the opportunity to extend
the information used to setup paths beyond what is available for the
routing protocol. For instance, an LSP can be setup based on
explicit route constraints, QoS constraints, and other constraints.
Constraint-based routing (CR) is a mechanism used to meet Traffic
Engineering requirements that have been proposed by, [2] and [3].
These requirements may be met by extending LDP for support of
constraint-based routed label switched paths (CR-LSPs). Other uses
for CR-LSPs include MPLS-based VPNs [4]. More information about the
applicability of CR-LDP can be found in [5].
The need for constraint-based routing (CR) in MPLS has been explored
elsewhere [2], and [3]. Explicit routing is a subset of the more
general constraint-based routing function. At the MPLS WG meeting
held during the Washington IETF (December 1997) there was consensus
that LDP should support explicit routing of LSPs with provision for
indication of associated (forwarding) priority. In the Chicago
meeting (August 1998), a decision was made that support for explicit
path setup in LDP will be moved to a separate document. This
document provides that support and it has been accepted as a working
document in the Orlando meeting (December 1998).
This specification proposes an end-to-end setup mechanism of a
constraint-based routed LSP (CR-LSP) initiated by the ingress LSR. We
also specify mechanisms to provide means for reservation of resources
using LDP.
This document introduce TLVs and procedures that provide support for:
- Strict and Loose Explicit Routing
- Specification of Traffic Parameters
- Route Pinning
- CR-LSP Preemption though setup/holding priorities
- Handling Failures
- LSPID
- Resource Class
Section 2 introduces the various constraints defined in this
specification. Section 3 outlines the CR-LDP solution. Section 4
defines the TLVs and procedures used to setup constraint-based routed
label switched paths. Appendix A provides several examples of CR-LSP
path setup. Appendix B provides Service Definition Examples.
2. Constraint-based Routing Overview
Constraint-based routing is a mechanism that supports the Traffic
Engineering requirements defined in [3]. Explicit Routing is a
subset of the more general constraint-based routing where the
constraint is the explicit route (ER). Other constraints are defined
to provide a network operator with control over the path taken by an
LSP. This section is an overview of the various constraints
supported by this specification.
Like any other LSP a CR-LSP is a path through an MPLS network. The
difference is that while other paths are setup solely based on
information in routing tables or from a management system, the
constraint-based route is calculated at one point at the edge of
network based on criteria, including but not limited to routing
information. The intention is that this functionality shall give
desired special characteristics to the LSP in order to better support
the traffic sent over the LSP. The reason for setting up CR-LSPs
might be that one wants to assign certain bandwidth or other Service
Class characteristics to the LSP, or that one wants to make sure that
alternative routes use physically separate paths through the network.
2.1 Strict and Loose Explicit Routes
An explicit route is represented in a Label Request Message as a list
of nodes or groups of nodes along the constraint-based route. When
the CR-LSP is established, all or a subset of the nodes in a group
may be traversed by the LSP. Certain operations to be performed
along the path can also be encoded in the constraint-based route.
The capability to specify, in addition to specified nodes, groups of
nodes, of which a subset will be traversed by the CR-LSP, allows the
system a significant amount of local flexibility in fulfilling a
request for a constraint-based route. This allows the generator of
the constraint-based route to have some degree of imperfect
information about the details of the path.
The constraint-based route is encoded as a series of ER-Hops
contained in a constraint-based route TLV. Each ER-Hop may identify
a group of nodes in the constraint-based route. A constraint-based
route is then a path including all of the identified groups of nodes
in the order in which they appear in the TLV.
To simplify the discussion, we call each group of nodes an "abstract
node". Thus, we can also say that a constraint-based route is a path
including all of the abstract nodes, with the specified operations
occurring along that path.
2.2 Traffic Characteristics
The traffic characteristics of a path are described in the Traffic
Parameters TLV in terms of a peak rate, committed rate, and service
granularity. The peak and committed rates describe the bandwidth
constraints of a path while the service granularity can be used to
specify a constraint on the delay variation that the CR-LDP MPLS
domain may introduce to a path's traffic.
2.3 Preemption
CR-LDP signals the resources required by a path on each hop of the
route. If a route with sufficient resources can not be found,
existing paths may be rerouted to reallocate resources to the new
path. This is the process of path preemption. Setup and holding
priorities are used to rank existing paths (holding priority) and the
new path (setup priority) to determine if the new path can preempt an
existing path.
The setupPriority of a new CR-LSP and the holdingPriority attributes
of the existing CR-LSP are used to specify priorities. Signaling a
higher holding priority express that the path, once it has been
established, should have a lower chance of being preempted. Signaling
a higher setup priority expresses the expectation that, in the case
that resource are unavailable, the path is more likely to preempt
other paths. The exact rules determining bumping are an aspect of
network policy.
The allocation of setup and holding priority values to paths is an
aspect of network policy.
The setup and holding priority values range from zero (0) to seven
(7). The value zero (0) is the priority assigned to the most
important path. It is referred to as the highest priority. Seven
(7) is the priority for the least important path. The use of default
priority values is an aspect of network policy. The recommended
default value is (4).
The setupPriority of a CR-LSP should not be higher (numerically less)
than its holdingPriority since it might bump an LSP and be bumped by
the next "equivalent" request.
2.4 Route Pinning
Route pinning is applicable to segments of an LSP that are loosely
routed - i.e. those segments which are specified with a next hop with
the "L" bit set or where the next hop is an abstract node. A CR-LSP
may be setup using route pinning if it is undesirable to change the
path used by an LSP even when a better next hop becomes available at
some LSR along the loosely routed portion of the LSP.
2.5 Resource Class
The network operator may classify network resources in various ways.
These classes are also known as "colors" or "administrative groups".
When a CR-LSP is being established, it's necessary to indicate which
resource classes the CR-LSP can draw from.
3. Solution Overview
CR-LSP over LDP Specification is designed with the following goals:
1. Meet the requirements outlined in [3] for performing traffic
engineering and provide a solid foundation for performing more
general constraint-based routing.
2. Build on already specified functionality that meets the
requirements whenever possible. Hence, this specification is
based on [1].
3. Keep the solution simple.
In this document, support for unidirectional point-to-point CR-LSPs
is specified. Support for point-to-multipoint, multipoint-to-point,
is for further study (FFS).
Support for constraint-based routed LSPs in this specification
depends on the following minimal LDP behaviors as specified in [1]:
- Use of Basic and/or Extended Discovery Mechanisms.
- Use of the Label Request Message defined in [1] in downstream
on demand label advertisement mode with ordered control.
- Use of the Label Mapping Message defined in [1] in downstream
on demand mode with ordered control.
- Use of the Notification Message defined in [1].
- Use of the Withdraw and Release Messages defined in [1].
- Use of the Loop Detection (in the case of loosely routed
segments of a CR-LSP) mechanisms defined in [1].
In addition, the following functionality is added to what's defined
in [1]:
- The Label Request Message used to setup a CR-LSP includes one
or more CR-TLVs defined in Section 4. For instance, the Label
Request Message may include the ER-TLV.
- An LSR implicitly infers ordered control from the existence of
one or more CR-TLVs in the Label Request Message. This means
that the LSR can still be configured for independent control
for LSPs established as a result of dynamic routing. However,
when a Label Request Message includes one or more of the CR-
TLVs, then ordered control is used to setup the CR-LSP. Note
that this is also true for the loosely routed parts of a CR-
LSP.
- New status codes are defined to handle error notification for
failure of established paths specified in the CR-TLVs. All of
the new status codes require that the F bit be set.
Optional TLVs MUST be implemented to be compliant with the protocol.
However, they are optionally carried in the CR-LDP messages to signal
certain characteristics of the CR-LSP being established or modified.
Examples of CR-LSP establishment are given in Appendix A to
illustrate how the mechanisms described in this document work.
3.1 Required Messages and TLVs
Any Messages, TLVs, and procedures not defined explicitly in this
document are defined in the LDP Specification [1]. The reader can
use [7] as an informational document about the state transitions,
which relate to CR-LDP messages.
The following subsections are meant as a cross-reference to the [1]
document and indication of additional functionality beyond what's
defined in [1] where necessary.
Note that use of the Status TLV is not limited to Notification
messages as specified in Section 3.4.6 of [1]. A message other than
a Notification message may carry a Status TLV as an Optional
Parameter. When a message other than a Notification carries a Status
TLV the U-bit of the Status TLV should be set to 1 to indicate that
the receiver should silently discard the TLV if unprepared to handle
it.
3.2 Label Request Message
The Label Request Message is as defined in 3.5.8 of [1] with the
following modifications (required only if any of the CR-TLVs is
included in the Label Request Message):
- The Label Request Message MUST include a single FEC-TLV
element. The CR-LSP FEC TLV element SHOULD be used. However,
the other FEC- TLVs defined in [1] MAY be used instead for
certain applications.
- The Optional Parameters TLV includes the definition of any of
the Constraint-based TLVs specified in Section 4.
- The Procedures to handle the Label Request Message are
augmented by the procedures for processing of the CR-TLVs as
defined in Section 4.
The encoding for the CR-LDP Label Request Message is as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0| Label Request (0x0401) | Message Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| FEC TLV |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LSPID TLV (CR-LDP, mandatory) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ER-TLV (CR-LDP, optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Traffic TLV (CR-LDP, optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pinning TLV (CR-LDP, optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Resource Class TLV (CR-LDP, optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Preemption TLV (CR-LDP, optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
3.3 Label Mapping Message
The Label Mapping Message is as defined in 3.5.7 of [1] with the
following modifications:
- The Label Mapping Message MUST include a single Label-TLV.
- The Label Mapping Message Procedures are limited to downstream
on demand ordered control mode.
A Mapping message is transmitted by a downstream LSR to an upstream
LSR under one of the following conditions:
1. The LSR is the egress end of the CR-LSP and an upstream mapping
has been requested.
2. The LSR received a mapping from its downstream next hop LSR for
an CR-LSP for which an upstream request is still pending.
The encoding for the CR-LDP Label Mapping Message is as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0| Label Mapping (0x0400) | Message Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| FEC TLV |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Label TLV |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Label Request Message ID TLV |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LSPID TLV (CR-LDP, optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Traffic TLV (CR-LDP, optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
3.4 Notification Message
The Notification Message is as defined in Section 3.5.1 of [1] and
the Status TLV encoding is as defined in Section 3.4.6 of [1].
Establishment of an CR-LSP may fail for a variety of reasons. All
such failures are considered advisory conditions and they are
signaled by the Notification Message.
Notification Messages carry Status TLVs to specify events being
signaled. New status codes are defined in Section 4.11 to signal
error notifications associated with the establishment of a CR-LSP and
the processing of the CR-TLV. All of the new status codes require
that the F bit be set.
The Notification Message MAY carry the LSPID TLV of the corresponding
CR-LSP.
Notification Messages MUST be forwarded toward the LSR originating
the Label Request at each hop and at any time that procedures in this
specification - or in [1] - specify sending of a Notification Message
in response to a Label Request Message.
The encoding of the notification message is as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0| Notification (0x0001) | Message Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Status (TLV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Optional Parameters |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
3.5 Release , Withdraw, and Abort Messages
The Label Release , Label Withdraw, and Label Abort Request Messages
are used as specified in [1]. These messages MAY also carry the
LSPID TLV.
4. Protocol Specification
The Label Request Message defined in [1] MUST carry the LSPID TLV and
MAY carry one or more of the optional Constraint-based Routing TLVs
(CR-TLVs) defined in this section. If needed, other constraints can
be supported later through the definition of new TLVs. In this
specification, the following TLVs are defined:
- Explicit Route TLV
- Explicit Route Hop TLV
- Traffic Parameters TLV
- Preemption TLV
- LSPID TLV
- Route Pinning TLV
- Resource Class TLV
- CR-LSP FEC TLV
4.1 Explicit Route TLV (ER-TLV)
The ER-TLV is an object that specifies the path to be taken by the
LSP being established. It is composed of one or more Explicit Route
Hop TLVs (ER-Hop TLVs) defined in Section 4.2.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| Type = 0x0800 | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ER-Hop TLV 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ER-Hop TLV 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ............ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ER-Hop TLV n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the ER-TLV
Type = 0x0800.
Length
Specifies the length of the value field in bytes.
ER-Hop TLVs
One or more ER-Hop TLVs defined in Section 4.2.
4.2 Explicit Route Hop TLV (ER-Hop TLV)
The contents of an ER-TLV are a series of variable length ER-Hop
TLVs.
A node receiving a label request message including an ER-Hop type
that is not supported MUST not progress the label request message to
the downstream LSR and MUST send back a "No Route" Notification
Message.
Each ER-Hop TLV has the form:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|L| Content // |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ER-Hop Type
A fourteen-bit field carrying the type of the ER-Hop contents.
Currently defined values are:
Value Type
------ ------------------------
0x0801 IPv4 prefix
0x0802 IPv6 prefix
0x0803 Autonomous system number
0x0804 LSPID
Length
Specifies the length of the value field in bytes.
L bit
The L bit in the ER-Hop is a one-bit attribute. If the L bit
is set, then the value of the attribute is "loose." Otherwise,
the value of the attribute is "strict." For brevity, we say
that if the value of the ER-Hop attribute is loose then it is a
"loose ER-Hop." Otherwise, it's a "strict ER-Hop." Further,
we say that the abstract node of a strict or loose ER-Hop is a
strict or a loose node, respectively. Loose and strict nodes
are always interpreted relative to their prior abstract nodes.
The path between a strict node and its prior node MUST include
only network nodes from the strict node and its prior abstract
node.
The path between a loose node and its prior node MAY include
other network nodes, which are not part of the strict node or
its prior abstract node.
Contents
A variable length field containing a node or abstract node
which is one of the consecutive nodes that make up the
explicitly routed LSP.
4.3 Traffic Parameters TLV
The following sections describe the CR-LSP Traffic Parameters. The
required characteristics of a CR-LSP are expressed by the Traffic
Parameter values.
A Traffic Parameters TLV, is used to signal the Traffic Parameter
values. The Traffic Parameters are defined in the subsequent
sections.
The Traffic Parameters TLV contains a Flags field, a Frequency, a
Weight, and the five Traffic Parameters PDR, PBS, CDR, CBS, EBS.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| Type = 0x0810 | Length = 24 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Flags | Frequency | Reserved | Weight |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Peak Data Rate (PDR) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Peak Burst Size (PBS) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Committed Data Rate (CDR) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Committed Burst Size (CBS) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Excess Burst Size (EBS) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the Traffic
Parameters TLV Type = 0x0810.
Length
Specifies the length of the value field in bytes = 24.
Flags
The Flags field is shown below:
+--+--+--+--+--+--+--+--+
| Res |F6|F5|F4|F3|F2|F1|
+--+--+--+--+--+--+--+--+
Res - These bits are reserved.
Zero on transmission.
Ignored on receipt.
F1 - Corresponds to the PDR.
F2 - Corresponds to the PBS.
F3 - Corresponds to the CDR.
F4 - Corresponds to the CBS.
F5 - Corresponds to the EBS.
F6 - Corresponds to the Weight.
Each flag Fi is a Negotiable Flag corresponding to a Traffic
Parameter. The Negotiable Flag value zero denotes
NotNegotiable and value one denotes Negotiable.
Frequency
The Frequency field is coded as an 8 bit unsigned integer with
the following code points defined:
0- Unspecified
1- Frequent
2- VeryFrequent
3-255 - Reserved
Reserved - Zero on transmission. Ignored on receipt.
Weight
An 8 bit unsigned integer indicating the weight of the CR-LSP.
Valid weight values are from 1 to 255. The value 0 means that
weight is not applicable for the CR-LSP.
Traffic Parameters
Each Traffic Parameter is encoded as a 32-bit IEEE single-
precision floating-point number. A value of positive infinity
is represented as an IEEE single-precision floating-point
number with an exponent of all ones (255) and a sign and
mantissa of all zeros. The values PDR and CDR are in units of
bytes per second. The values PBS, CBS and EBS are in units of
bytes.
The value of PDR MUST be greater than or equal to the value of
CDR in a correctly encoded Traffic Parameters TLV.
4.3.1 Semantics
4.3.1.1 Frequency
The Frequency specifies at what granularity the CDR allocated to the
CR-LSP is made available. The value VeryFrequent means that the
available rate should average at least the CDR when measured over any
time interval equal to or longer than the shortest packet time at the
CDR. The value Frequent means that the available rate should average
at least the CDR when measured over any time interval equal to or
longer than a small number of shortest packet times at the CDR.
The value Unspecified means that the CDR MAY be provided at any
granularity.
4.3.1.2 Peak Rate
The Peak Rate defines the maximum rate at which traffic SHOULD be
sent to the CR-LSP. The Peak Rate is useful for the purpose of
resource allocation. If resource allocation within the MPLS domain
depends on the Peak Rate value then it should be enforced at the
ingress to the MPLS domain.
The Peak Rate is defined in terms of the two Traffic Parameters PDR
and PBS, see section 4.3.1.5 below.
4.3.1.3 Committed Rate
The Committed Rate defines the rate that the MPLS domain commits to
be available to the CR-LSP.
The Committed Rate is defined in terms of the two Traffic Parameters
CDR and CBS, see section 4.3.1.6 below.
4.3.1.4 Excess Burst Size
The Excess Burst Size may be used at the edge of an MPLS domain for
the purpose of traffic conditioning. The EBS MAY be used to measure
the extent by which the traffic sent on a CR-LSP exceeds the
committed rate.
The possible traffic conditioning actions, such as passing, marking
or dropping, are specific to the MPLS domain.
The Excess Burst Size is defined together with the Committed Rate,
see section 4.3.1.6 below.
4.3.1.5 Peak Rate Token Bucket
The Peak Rate of a CR-LSP is specified in terms of a token bucket P
with token rate PDR and maximum token bucket size PBS.
The token bucket P is initially (at time 0) full, i.e., the token
count Tp(0) = PBS. Thereafter, the token count Tp, if less than PBS,
is incremented by one PDR times per second. When a packet of size B
bytes arrives at time t, the following happens:
- If Tp(t)-B >= 0, the packet is not in excess of the peak rate
and Tp is decremented by B down to the minimum value of 0, else
- the packet is in excess of the peak rate and Tp is not
decremented.
Note that according to the above definition, a positive infinite
value of either PDR or PBS implies that arriving packets are never in
excess of the peak rate.
The actual implementation of an LSR doesn't need to be modeled
according to the above formal token bucket specification.
4.3.1.6 Committed Data Rate Token Bucket
The committed rate of a CR-LSP is specified in terms of a token
bucket C with rate CDR. The extent by which the offered rate exceeds
the committed rate MAY be measured in terms of another token bucket
E, which also operates at rate CDR. The maximum size of the token
bucket C is CBS and the maximum size of the token bucket E is EBS.
The token buckets C and E are initially (at time 0) full, i.e., the
token count Tc(0) = CBS and the token count Te(0) = EBS.
Thereafter, the token counts Tc and Te are updated CDR times per
second as follows:
- If Tc is less than CBS, Tc is incremented by one, else
- if Te is less then EBS, Te is incremented by one, else neither
Tc nor Te is incremented.
When a packet of size B bytes arrives at time t, the following
happens:
- If Tc(t)-B >= 0, the packet is not in excess of the Committed
Rate and Tc is decremented by B down to the minimum value of 0,
else
- if Te(t)-B >= 0, the packet is in excess of the Committed rate
but is not in excess of the EBS and Te is decremented by B down
to the minimum value of 0, else
- the packet is in excess of both the Committed Rate and the EBS
and neither Tc nor Te is decremented.
Note that according to the above specification, a CDR value of
positive infinity implies that arriving packets are never in excess
of either the Committed Rate or EBS. A positive infinite value of
either CBS or EBS implies that the respective limit cannot be
exceeded.
The actual implementation of an LSR doesn't need to be modeled
according to the above formal specification.
4.3.1.7 Weight
The weight determines the CR-LSP's relative share of the possible
excess bandwidth above its committed rate. The definition of
"relative share" is MPLS domain specific.
4.3.2 Procedures
4.3.2.1 Label Request Message
If an LSR receives an incorrectly encoded Traffic Parameters TLV in
which the value of PDR is less than the value of CDR then it MUST
send a Notification Message including the Status code "Traffic
Parameters Unavailable" to the upstream LSR from which it received
the erroneous message.
If a Traffic Parameter is indicated as Negotiable in the Label
Request Message by the corresponding Negotiable Flag then an LSR MAY
replace the Traffic Parameter value with a smaller value.
If the Weight is indicated as Negotiable in the Label Request Message
by the corresponding Negotiable Flag then an LSR may replace the
Weight value with a lower value (down to 0).
If, after possible Traffic Parameter negotiation, an LSR can support
the CR-LSP Traffic Parameters then the LSR MUST reserve the
corresponding resources for the CR-LSP.
If, after possible Traffic Parameter negotiation, an LSR cannot
support the CR-LSP Traffic Parameters then the LSR MUST send a
Notification Message that contains the "Resource Unavailable" status
code.
4.3.2.2 Label Mapping Message
If an LSR receives an incorrectly encoded Traffic Parameters TLV in
which the value of PDR is less than the value of CDR then it MUST
send a Label Release message containing the Status code "Traffic
Parameters Unavailable" to the LSR from which it received the
erroneous message. In addition, the LSP should send a Notification
Message upstream with the status code 'Label Request Aborted'.
If the negotiation flag was set in the label request message, the
egress LSR MUST include the (possibly negotiated) Traffic Parameters
and Weight in the Label Mapping message.
The Traffic Parameters and the Weight in a Label Mapping message MUST
be forwarded unchanged.
An LSR SHOULD adjust the resources that it reserved for a CR-LSP when
it receives a Label Mapping Message if the Traffic Parameters differ
from those in the corresponding Label Request Message.
4.3.2.3 Notification Message
If an LSR receives a Notification Message for a CR-LSP, it SHOULD
release any resources that it possibly had reserved for the CR-LSP.
In addition, on receiving a Notification Message from a Downstream
LSR that is associated with a Label Request from an upstream LSR, the
local LSR MUST propagate the Notification message using the
procedures in [1]. Further the F bit MUST be set.
4.4 Preemption TLV
The default value of the setup and holding priorities should be in
the middle of the range (e.g., 4) so that this feature can be turned
on gradually in an operational network by increasing or decreasing
the priority starting at the middle of the range.
Since the Preemption TLV is an optional TLV, LSPs that are setup
without an explicitly signaled preemption TLV SHOULD be treated as
LSPs with the default setup and holding priorities (e.g., 4).
When an established LSP is preempted, the LSR that initiates the
preemption sends a Withdraw Message upstream and a Release Message
downstream.
When an LSP in the process of being established (outstanding Label
Request without getting a Label Mapping back) is preempted, the LSR
that initiates the preemption, sends a Notification Message upstream
and an Abort Message downstream.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| Type = 0x0820 | Length = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SetPrio | HoldPrio | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the Preemption-TLV
Type = 0x0820.
Length
Specifies the length of the value field in bytes = 4.
Reserved
Zero on transmission. Ignored on receipt.
SetPrio
A SetupPriority of value zero (0) is the priority assigned to
the most important path. It is referred to as the highest
priority. Seven (7) is the priority for the least important
path. The higher the setup priority, the more paths CR-LDP can
bump to set up the path. The default value should be 4.
HoldPrio
A HoldingPriority of value zero (0) is the priority assigned to
the most important path. It is referred to as the highest
priority. Seven (7) is the priority for the least important
path. The default value should be 4.
The higher the holding priority, the less likely it is for CR-
LDP to reallocate its bandwidth to a new path.
4.5 LSPID TLV
LSPID is a unique identifier of a CR-LSP within an MPLS network.
The LSPID is composed of the ingress LSR Router ID (or any of its
own Ipv4 addresses) and a Locally unique CR-LSP ID to that LSR.
The LSPID is useful in network management, in CR-LSP repair, and in
using an already established CR-LSP as a hop in an ER-TLV.
An "action indicator flag" is carried in the LSPID TLV. This "action
indicator flag" indicates explicitly the action that should be taken
if the LSP already exists on the LSR receiving the message.
After a CR-LSP is set up, its bandwidth reservation may need to be
changed by the network operator, due to the new requirements for the
traffic carried on that CR-LSP. The "action indicator flag" is used
indicate the need to modify the bandwidth and possibly other
parameters of an established CR-LSP without service interruption.
This feature has application in dynamic network resources management
where traffic of different priorities and service classes is
involved.
The procedure for the code point "modify" is defined in [8]. The
procedures for other flags are FFS.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| Type = 0x0821 | Length = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |ActFlg | Local CR-LSP ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Ingress LSR Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the LSPID-TLV
Type = 0x0821.
Length
Specifies the length of the value field in bytes = 4.
ActFlg
Action Indicator Flag: A 4-bit field that indicates explicitly
the action that should be taken if the LSP already exists on
the LSR receiving the message. A set of indicator code points
is proposed as follows:
0000: indicates initial LSP setup
0001: indicates modify LSP
Reserved
Zero on transmission. Ignored on receipt.
Local CR-LSP ID
The Local LSP ID is an identifier of the CR-LSP locally unique
within the Ingress LSR originating the CR-LSP.
Ingress LSR Router ID
An LSR may use any of its own IPv4 addresses in this field.
4.6 Resource Class (Color) TLV
The Resource Class as defined in [3] is used to specify which links
are acceptable by this CR-LSP. This information allows for the
network's topology to be pruned.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| Type = 0x0822 | Length = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RsCls |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the ResCls-TLV
Type = 0x0822.
Length
Specifies the length of the value field in bytes = 4.
RsCls
The Resource Class bit mask indicating which of the 32
"administrative groups" or "colors" of links the CR-LSP can
traverse.
4.7 ER-Hop semantics
4.7.1. ER-Hop 1: The IPv4 prefix
The abstract node represented by this ER-Hop is the set of nodes,
which have an IP address, which lies within this prefix. Note that a
prefix length of 32 indicates a single IPv4 node.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| Type = 0x0801 | Length = 8 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|L| Reserved | PreLen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPv4 Address (4 bytes) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the ER-Hop 1, IPv4
Address, Type = 0x0801
Length
Specifies the length of the value field in bytes = 8.
L Bit
Set to indicate Loose hop.
Cleared to indicate a strict hop.
Reserved
Zero on transmission. Ignored on receipt.
PreLen
Prefix Length 1-32
IP Address
A four-byte field indicating the IP Address.
4.7.2. ER-Hop 2: The IPv6 address
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| 0x0802 | Length = 20 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|L| Reserved | PreLen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPV6 address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPV6 address (continued) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPV6 address (continued) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPV6 address (continued) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the ER-Hop 2, IPv6
Address, Type = 0x0802
Length
Specifies the length of the value field in bytes = 20.
L Bit
Set to indicate Loose hop.
Cleared to indicate a strict hop.
Reserved
Zero on transmission. Ignored on receipt.
PreLen
Prefix Length 1-128
IPv6 address
A 128-bit unicast host address.
4.7.3. ER-Hop 3: The autonomous system number
The abstract node represented by this ER-Hop is the set of nodes
belonging to the autonomous system.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| 0x0803 | Length = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|L| Reserved | AS Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the ER-Hop 3, AS
Number, Type = 0x0803
Length
Specifies the length of the value field in bytes = 4.
L Bit
Set to indicate Loose hop.
Cleared to indicate a strict hop.
Reserved
Zero on transmission. Ignored on receipt.
AS Number
Autonomous System number
4.7.4. ER-Hop 4: LSPID
The LSPID is used to identify the tunnel ingress point as the next
hop in the ER. This ER-Hop allows for stacking new CR-LSPs within an
already established CR-LSP. It also allows for splicing the CR-LSP
being established with an existing CR-LSP.
If an LSPID Hop is the last ER-Hop in an ER-TLV, than the LSR may
splice the CR-LSP of the incoming Label Request to the CR-LSP that
currently exists with this LSPID. This is useful, for example, at
the point at which a Label Request used for local repair arrives at
the next ER-Hop after the loosely specified CR-LSP segment. Use of
the LSPID Hop in this scenario eliminates the need for ER-Hops to
keep the entire remaining ER-TLV at each LSR that is at either
(upstream or downstream) end of a loosely specified CR-LSP segment as
part of its state information. This is due to the fact that the
upstream LSR needs only to keep the next ER-Hop and the LSPID and the
downstream LSR needs only to keep the LSPID in order for each end to
be able to recognize that the same LSP is being identified.
If the LSPID Hop is not the last hop in an ER-TLV, the LSR must
remove the LSP-ID Hop and forward the remaining ER-TLV in a Label
Request message using an LDP session established with the LSR that is
the specified CR-LSP's egress. That LSR will continue processing of
the CR-LSP Label Request Message. The result is a tunneled, or
stacked, CR-LSP.
To support labels negotiated for tunneled CR-LSP segments, an LDP
session is required [1] between tunnel end points - possibly using
the existing CR-LSP. Use of the existence of the CR-LSP in lieu of a
session, or other possible session-less approaches, is FFS.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0| 0x0804 | Length = 8 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|L| Reserved | Local LSPID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Ingress LSR Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
A fourteen-bit field carrying the value of the ER-Hop 4, LSPID,
Type = 0x0804
Length
Specifies the length of the value field in bytes = 8.
L Bit
Set to indicate Loose hop.
Cleared to indicate a strict hop.
Reserved
Zero on transmission. Ignored on receipt.
Local LSPID
A 2 byte field indicating the LSPID which is unique with
reference to its Ingress LSR.
Ingress LSR Router ID
An LSR may use any of its own IPv4 addresses in this field.
4.8. Processing of the Explicit Route TLV
4.8.1. Selection of the next hop
A Label Request Message containing an explicit route TLV must
determine the next hop for this path. Selection of this next hop may
involve a selection from a set of possible alternatives. The
mechanism for making a selection from this set is implementation
dependent and is outside of the scope of this specification.
Selection of particular paths is also outside of the scope of this
specification, but it is assumed that each node will make a best
effort attempt to determine a loop-free path. Note that such best
efforts may be overridden by local policy.
To determine the next hop for the path, a node performs the following
steps:
1. The node receiving the Label Request Message must first
evaluate the first ER-Hop. If the L bit is not set in the
first ER-Hop and if the node is not part of the abstract node
described by the first ER-Hop, it has received the message in
error, and should return a "Bad Initial ER-Hop Error" status.
If the L bit is set and the local node is not part of the
abstract node described by the first ER-Hop, the node selects a
next hop that is along the path to the abstract node described
by the first ER-Hop. If there is no first ER-Hop, the message
is also in error and the system should return a "Bad Explicit
Routing TLV Error" status using a Notification Message sent
upstream.
2. If there is no second ER-Hop, this indicates the end of the
explicit route. The explicit route TLV should be removed from
the Label Request Message. This node may or may not be the end
of the LSP. Processing continues with section 4.8.2, where a
new explicit route TLV may be added to the Label Request
Message.
3. If the node is also a part of the abstract node described by
the second ER-Hop, then the node deletes the first ER-Hop and
continues processing with step 2, above. Note that this makes
the second ER-Hop into the first ER-Hop of the next iteration.
4. The node determines if it is topologically adjacent to the