Request for Comments: 3215 P. Cheval
Category: Informational Alcatel
L. Wu
Cisco
E. Gray
Sandburst
January 2002
LDP State Machine
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2002). All Rights Reserved.
Abstract
This document provides state machine tables for ATM (Asynchronous
Transfer Mode) switch LSRs. In the current LDP specification, there
is no state machine specified for processing LDP messages. We think
that defining a common state machine is very important for
interoperability between different LDP and CR-LDP implementations.
We begin in section 1 by defining a list of terminologies. Then in
section 2, we propose two sets of state machine tables for ATM switch
LSRs that use downstream-on-demand mode, one method can be used for
non-vc merge capable ATM LSRs, while the other one can be used for
the vc-merge capable ATM LSRs. In section 3, we provides a state
machine for downstream unsolicited mode ATM LSRs.
We focus on the LDP state machines and the associated control blocks
used for establishing and maintaining LSPs. We do not describe state
machines for the "LDP controller" that is in charge of LDP session
initialization, address mapping messages management, routing
interface, etc. that is defined in the LDP specification.
Even though the state machines in this document are specific for
ATM-LSR, they can be easily adapted for other types of LSRs.
Table Of Contents
1. Terminology ................................................... 4
2. State Machine for Downstream-on-Demand Mode ................... 4
2.1 An LSR's Behavior in the Case of a Next Hop Change ........... 4
2.2. ATM Switch LSR with No VC-merge Capability .................. 5
2.2.1 LSP Control Block .......................................... 5
2.2.2 States ..................................................... 7
2.2.3 Events ..................................................... 8
2.2.4 State Transitions .......................................... 9
2.2.5 State Machine .............................................. 10
2.2.5.1 State -- "IDLE" .......................................... 10
2.2.5.2 State -- "RESPONSE_AWAITED" .............................. 13
2.2.5.3 State -- "ESTABLISHED" ................................... 16
2.2.5.4 State -- "RELEASE_AWAITED" ............................... 21
2.2.6 Handling the Next Hop Change ............................... 23
2.2.6.1 Next Hop Trigger Control Block ........................... 24
2.2.6.2 States ................................................... 24
2.2.6.3 Events ................................................... 24
2.2.6.4 State Transition for next hop change ..................... 25
2.2.6.5 State Machine ............................................ 25
2.2.6.5.1 State -- "IDLE" ........................................ 25
2.2.6.5.2 State -- "NEW_NH_RETRY" ................................ 27
2.2.6.5.3 State -- "NEW_NH_RESPONSE_AWAITED" ..................... 28
2.2.7 LDP Related Message Handling ............................... 29
2.3. ATM Switch LSR with VC-merge ................................ 31
2.3.1 VC-merge ................................................... 31
2.3.2 Control Block .............................................. 31
2.3.3 State Machines for Downstream-on-demand Mode ............. 34
2.3.3.1 State of the Upstream LSP Control Block's State Machine
for Downstream-on-demand Mode ............................ 34
2.3.3.2 Events of the Upstream LSP Control Block's State Machine
for Downstream-on-demand Mode ............................ 35
2.3.3.3 State Transitions of the Upstream LSP Control Block's State
Machine for Downstream-on-demand Mode .................... 36
2.3.3.4 Upstream LSP Control Block's State Machine
for Downstream-on-demand Mode ............................ 37
2.3.3.4.1 State -- "IDLE" ........................................ 37
2.3.3.4.2 State -- "RESPONSE_AWAITED" ............................ 39
2.3.3.4.3 State -- "ESTABLISHED" ................................. 42
2.3.3.4.4 State -- "RELEASE_AWAITED" ............................. 45
2.3.3.5 State of the Downstream LSP Control Block's State Machine
for Downstream-on-demand Mode ............................ 47
2.3.3.6 Events of the Downstream LSP Control Block's State Machine
for Downstream-on-demand Mode ............................ 47
2.3.3.7 State Transitions of the Downstream LSP Control Block's
State Machine for Downstream-on-demand mode .............. 48
2.3.3.8 Downstream LSP Control Block's State Machine for
Downstream-on-demand Mode ................................ 49
2.3.3.8.1 State -- "IDLE" ........................................ 48
2.3.3.8.2 State -- "RESPONSE_AWAITED" ............................ 50
2.3.3.8.3 State -- "ESTABLISHED" ................................. 52
2.3.3.9 State of the Next_Hop_Trigger_Control_Block's State
Machine for Downstream-on-demand Mode .................... 53
2.3.3.10 Events of the Next_Hop_Trigger_Control_Block's State
Machine for Downstream-on-demand Mode ................... 53
2.3.3.11 State Transitions of the Next_Hop_Trigger_Control_Block's
State Machine for Downstream-on-demand Mode ............. 55
2.3.3.12 State Machine ........................................... 55
2.3.3.12.1 State -- "IDLE" ....................................... 55
2.3.3.12.2 State -- "NEW_NH_RETRY" ............................... 57
2.3.3.12.3 State -- "NEW_NH_RESPONSE_AWAITED" .................... 58
2.3.4 LDP Related Message Processing ............................. 59
3. State Machine for Downstream Unsolicited ...................... 61
3.1 Control Block ................................................ 61
3.2 States of the Upstream LSP Control Block's State Machine
for Downstream Mode .......................................... 62
3.3 Events of the Upstream LSP Control Block's State Machine
for Downstream Mode .......................................... 62
3.4 State Transitions of Upstream LSP Control Block's State
Machine for Downstream Mode .................................. 64
3.5 Upstream LSP Control Block's State Machine for
Downstream Mode .............................................. 65
3.5.1 : State -- "IDLE" .......................................... 65
3.5.2 : State -- "ESTABLISHED" ................................... 66
3.5.3 : State -- "RELEASE_AWAITED" ............................... 67
3.5.4 : State -- "RESOURCE_AWAITED" .............................. 69
3.6 State of the Downstream LSP Control Block's State Machine
for Downstream Mode .......................................... 70
3.7 Events of the Downstream LSP Control Block's State Machine
for Downstream Mode .......................................... 70
3.8 State Transitions of Downstream LSP Control Block's State
Machine for Downstream Mode .................................. 71
3.9 Downstream LSP Control Block's State Machine
for Downstream Mode .......................................... 71
3.9.1 : State -- "IDLE" .......................................... 71
3.9.2 : State -- "ESTABLISHED" ................................... 73
3.10 LDP Related Message Processing for downstream mode .......... 74
4. Security Considerations ....................................... 75
5. Acknowledgements .............................................. 76
6. References .................................................... 76
7. Authors' Address .............................................. 77
8. Full Copyright Statement ...................................... 78
1. Terminology
- LDP-REQUEST: LDP Label Request message
- LDP-MAPPING: LDP Label Mapping message
- LDP-WITHDRAW: LDP Label Withdraw message
- LDP-RELEASE: LDP Label Release message
- LDP-ABORT: LDP Abort message used to abort a LSP setup.
- LDP-NAK: LDP Notification message used to reject an LDP message.
2. State Machine for Downstream-on-Demand Mode
In this document, we provide two sets of state machines: one for the
ATM LSR that does not have VC-merge capability, and the other for the
ATM LSR that does have VC-merge capability.
State machine descriptions are given in terms of control blocks,
states, events, response actions and state transitions. Control
blocks contain the information that is required to support handling
of events. A control block may also contain any additional
information that is required either of any specific implementation or
in support of other required functions. In every case, additional
information required to support the procedures defined in the LDP
specification [4] or management objects defined in the LDP MIB [3]
would be stored in a specific LDP implementation - either as part of
the control block structure or in some other way.
The state machines cover both independent LSP control and ordered LSP
control.
Loop detection and loop prevention messages will be processed as
specified in [4]. The impact of loop detection and loop prevention
messages on state transitions is left for further study.
2.1 An LSR's Behavior in the Case of a Next Hop Change
When there is a topology change and an LSR detects a new better next
hop for an LSP, it may behave in 2 different ways:
1) It tries to do a "local repair". This means that it extends the
LSP through the new next hop, releases the old path from this LSR
forward and then splices into this newly extended LSP.
2) If the LSP is created with the "pinned" option (CR-LDP[5]), the
LSR ignores the new next hop change, and the LSP stays unchanged.
The LSR may decide to send an LDP-MAPPING containing attributes
for this New Next Hop (NH) that have changed.
2.2. ATM Switch LSR with No VC-merge Capability
In an MPLS domain where some ATM LSRs do not have VC-merge
capability, downstream-on-demand mode is required for these ATM LSRs
[1]. Also, "conservative label retention mode" is required in this
case [1].
For each LSP, there are 2 kinds of state machines involved:
1) the LSP Control Block and its state machine that can be used to
handle normal LSP setup. It is created when the LSR receives a
new LDP Request and it is deleted when the LSP of this request is
torn down.
2) the Next Hop Trigger Control Block and its state machine that is
used to handle switching over to a better LSP through a different
next hop. It is created when the LSR decides to switch over to a
better next hop and it is deleted when the LSR finishes switching
over to the better next hop. This state machine uses a timer (and
has corresponding states) to ensure that switch over occurs in a
timely fashion after a routing transient has had time to
stabilize.
2.2.1 LSP Control Block
For each LSP, an LSP Control Block is defined that may contain the
following information:
- Upstream Label Request ID (assigned by the upstream LSR), that
is the 'Message Id' in the Label Request Message received from
the upstream LSR.
- Downstream Label Request ID (assigned by this LSR itself), that
is 'Message Id' in the Label Request Message sent to the
downstream LSR.
- Upstream LDP Identifier
- Downstream LDP Identifier
- State
- FEC
- Upstream Label (assigned by this LSR)
- Downstream Label (assigned by the downstream LSR)
- Trigger Control Block Pointer, (Only used at the ingress LSR of
a LSP) that points to the control block that triggers setting
up this LSP or tearing down this LSP.
- Next Hop Control Block Pointer, that points to the control
block that is used for switching over to a better LSP.
The following index combinations can be used to locate a unique LSP
Control Block:
- Downstream Label and Downstream LDP Identifier, or
- Upstream Label and Upstream LDP Identifier, or
- Downstream Label Request ID and Downstream LDP Identifier
- Upstream Label Request ID and Upstream LDP Identifier
Here is the relationship between different control blocks, the detail
definition of Next Hop Trigger Control Block is described in section
2.2.6.
For example, an LSP that transits through (LSR-A, LSR-B, LSR-C, LSR-
D):
LSR-A ----> LSR-B ---> LSR-C ---> LSR-D
The control blocks in LSR-A are:
+-----------------------+
| Trigger Control Block |
| (e.g, by config) |
+-----------------------+
^
|(Trigger Control block pointer)
|
|
+-----------------------+
| LSP Control Block |
+-----------------------+
When LSR-B detects a better next hop to LSR-D through LSR-E, and it
decides to switch over to it, so control blocks in LSR-B are:
+-----------------------+
| LSP Control Block |
| (original LSP) |
+-----------------------+
(LSP ^ |
Control | | (Next Hop Trigger Control Block Pointer)
Block | |
Pointer) | v
+--------------------------------+
| Next Hop Trigger Control Block |
+--------------------------------+
^ |
(Trigger | | (New Next Hop LSP
Control | | Control Block Pointer)
Block | |
Pointer)| |
| v
+------------------------+
| LSP Control Block |
| (for LSP: LSR-B, LSR-E,|
| LSR-D) |
+------------------------+
2.2.2 States
This section describes the various states that are used in the state
machine for the ATM non VC-merge LSR.
-- IDLE
This is the initial LSP state, when the LSP Control Block is created.
-- RESPONSE_AWAITED
This state means that the LSR has received and processed an LDP-
REQUEST from an upstream LSR, or it has received an internal set up
request. It has sent a new LDP-REQUEST towards a downstream LSR.
The LSR is waiting for the LDP-MAPPING from the downstream LSR.
-- ESTABLISHED
This state means that the LSR has received the LDP-MAPPING from the
downstream LSR and the LSP is up and operational.
-- RELEASE_AWAITED
This state means that the LSR has sent a LDP-WITHDRAW upstream and is
waiting for the LDP-RELEASE before freeing up the label resource.
2.2.3 Events
-- LDP Request
The LSR receives an LDP-REQUEST from an upstream LSR.
-- LDP Mapping
The LSR receives an LDP-MAPPING from a downstream LSR.
-- LDP Release
The LSR receives an LDP-RELEASE from an upstream LSR.
-- LDP Withdraw
The LSR receives an LDP-WITHDRAW from a downstream LSR.
-- LDP Upstream Abort
The LSR receives an LDP-ABORT from an upstream LSR.
-- LDP Downstream NAK The LSR receives an LDP-NAK (notification) from
an downstream LSR.
-- Upstream Lost
The LSR loses its LDP session with an upstream LDP peer.
-- Downstream Lost
The LSR loses its LDP session with a downstream LDP peer.
-- Internal SetUp
For some reason, e.g. a configuration request of a traffic
engineering tunnel, or recognizing a new FEC could trigger an
Internal SetUp event to set up a new LSP from this node.
-- Internal Destroy
The LSR send an Internal Destroy event to tear down an LSP.
-- Internal Cross-Connect
The LSR send an Internal Cross-Connect to splice two LSPs into one
LSP. This happens when a LSR switches over to a better next hop.
-- Internal New NH
The LSR decides to switch over the better next hop.
2.2.4 State Transitions
The following diagram describes briefly the state transitions.
+-------------------+
| |<-------------------+
+-------->| IDLE | |
| | |----------+ |
| +-------------------+ | |
|(LDP Release) | | |
|(LDP Upstream |(LDP Request 1) | | (LDP Release)
| Abort |(Internal SetUp) | | (Upstream Lost)
|(Internal Destroy) | | |
|(Upstream Lost) v | |
| +-------------------+ | |
+---------| | | |
| RESPONSE_AWAITED | | |
+---------| | | |
| +-------------------+ | |
| | | |
|(Downstream Lost) |(LDP Mapping) | |
|(LDP Downstream | | |
| NAK) | +---------------+ |
| | | (LDP Request 2) |
| | | |
| v v |
| +-------------------+ (LDP Withdraw 1) |
| | | (Internal Destroy) |
| | ESTABLISHED |------------>-------+
| | | |
| +-------------------+ |
| | |
| | |
| |(LDP Withdraw 2) | (LDP Upstream
| |(Downstream Lost) | Abort)
| | |
| v |
| +-------------------+ |
| | | |
+-------->| RELEASE_AWAITED |------------>-------+
| |
+-------------------+
2.2.5 State Machine
2.2.5.1 State -- "IDLE"
State: IDLE
Event: LDP Request
New State: Depends upon the action routine.
Actions:
If this LSR is the LSP Egress or Proxy Egress [2]
Then:
Choose an upstream label, connect this upstream label to the local
IP forwarding module, allocate the resources, send the LDP-MAPPING
upstream with the upstream label, and go to the new state
`ESTABLISHED'.
else
Obtain a next hop (or interface) with the FEC specified in the
LDP-REQUEST, propagate the LDP-REQUEST, with newly assigned
Message ID by this LSR, towards the obtained next hop, and go to
the new state `RESPONSE_AWAITED'.
If the LSR uses the independent control mode [2], choose an
upstream label, connect this upstream label to the local IP
forwarding module, go to the ESTABLISHED state and send an LDP-
MAPPING upstream with the upstream label.
If unable to process the request for any reason, issue an LDP-NAK to
the sender with the appropriate error code, go to IDLE and delete the
LSP Control Block.
State: IDLE
Event: LDP Mapping
New State: IDLE
Actions:
Ignore the event. It is an internal implementation error.
State: IDLE
Event: LDP Release
New State: IDLE
Actions:
Ignore the event. It is an internal implementation error.
State: IDLE
Event: LDP Withdraw
New State: IDLE
Actions:
Ignore the event. It is an internal implementation error.
State: IDLE
Event: LDP Upstream Abort
New State: IDLE
Actions:
Ignore the event. It is an internal implementation error.
State: IDLE
Event: LDP Downstream NAK
New State: IDLE
Actions:
Ignore the event. It is an internal implementation error.
State: IDLE
Event: Upstream Lost
New State: IDLE
Actions:
Ignore the event. It is an internal implementation error.
State: IDLE
Event: Downstream Lost
New State: IDLE
Actions:
Ignore the event. It is an internal implementation error.
State: IDLE
Event: Internal SetUp
New State: RESPONSE_AWAITED
Actions:
Set up the Trigger Control Block pointer,
Obtain a next hop (or interface) with the FEC specified in the
Internal SetUp message, send a LDP-REQUEST towards the obtained
next hop, and go to the new state `RESPONSE_AWAITED'.
State: IDLE
Event: Internal Destroy
New State: IDLE
Actions:
Ignore. It is an internal implementation error.
State: IDLE
Event: Internal Cross-Connect
New State: IDLE
Actions:
Ignore. It is an internal implementation error.
State: IDLE
Event: Internal New NH
New State: IDLE
Actions:
Ignore. It is an internal implementation error.
2.2.5.2 State -- "RESPONSE_AWAITED"
State: RESPONSE_AWAITED
Event: LDP Request
New State: RESPONSE_AWAITED
Actions:
Ignore the event. It is an internal implementation error. A non
VC merge ATM LSR must create a new LSP control block for a new LDP
request.
State: RESPONSE_AWAITED
Event: LDP Mapping
New State: ESTABLISHED
Actions:
1) If the LSP is triggered by the local router (Trigger Control
Block Pointer is not zero), send event `Internal LSP UP' to the
Trigger control block.
2) Else If the LSR uses the ordered control mode, choose an
upstream label.
3) Connect the upstream label to the downstream label. Allocate
the resources. Propagate the LDP-MAPPING upstream with the
upstream label.
If unable to process the message, disconnect the upstream label
from the downstream label, free the upstream label, release the
resources, send an LDP-RELEASE downstream and an LDP-NAK upstream
with status (No Label Resources [4]), go to IDLE and delete the
LSP Control Block.
State: RESPONSE_AWAITED
Event: LDP Release
New State: IDLE
Actions:
If the LSR uses the independent control mode, free the upstream
label.
Send an LDP-ABORT downstream, go to IDLE and delete the LSP
Control Block.
Note: This should only occur if the LSR uses the independent
control mode. In the ordered control mode, no upstream label
mapping will have been sent corresponding to this LSP while
waiting for a label mapping from downstream.
State: RESPONSE_AWAITED
Event: LDP Withdraw
New State: RESPONSE_AWAITED
Actions:
Ignore the event. It's a protocol error from the downstream LSR.
State: RESPONSE_AWAITED
Event: LDP Upstream Abort
New State: IDLE
Actions:
If the LSR uses the independent control mode, free the upstream
label.
Send an LDP-ABORT downstream.
Delete the LSP Control Block.
State: RESPONSE_AWAITED
Event: LDP Downstream NAK
New State: Depends on the action routine.
Actions:
1. If the LSP is triggered by the local router (Trigger Control
Block Pointer is not zero), send event `Internal LSP DOWN' to
the Trigger control block, go to IDLE and delete the LSP
Control Block.
2. Else If the LSR uses the independent control mode, send an LDP-
WITHDRAW upstream and go to state `RELEASE_AWAITED'.
If the LSR uses the ordered control mode, send an LDP-NAK
upstream, go to IDLE and delete the LSP Control Block.
State: RESPONSE_AWAITED
Event: Upstream Lost
New State: IDLE
Actions:
If the LSR uses the independent control mode, free the upstream
label.
Send an LDP-ABORT downstream, go to IDLE and delete the LSP
Control Block.
State: RESPONSE_AWAITED
Event: Downstream Lost
New State: Depends on the action routine.
Actions:
1. If the LSP is triggered by the local router (Trigger Control
Block Pointer is not zero), send event `Internal LSP DOWN' to
the trigger control block, go to IDLE and delete the LSP
Control Block.
2. Else, If the LSR uses the independent control mode, free the
upstream label and send an LDP-WITHDRAW upstream and go to
state `RELEASE_AWAITED'.
If the LSR uses the ordered control mode, send an LDP-NAK upstream
(with a status `No Route' [4]), go to IDLE and delete the LSP
Control Block.
State: RESPONSE_AWAITED
Event: Internal SetUp
New State: RESPONSE_AWAITED
Actions:
Ignore, it is an internal implementation error.
State: RESPONSE_AWAITED
Event: Internal Destroy
New State: IDLE
Actions:
Send an LDP-ABORT downstream, go to IDLE and delete the LSP
Control Block.
State: RESPONSE_AWAITED
Event: Internal Cross-Connect
New State: RESPONSE_AWAITED
Actions:
Ignore the event. It is an internal implementation error.
State: RESPONSE_AWAITED
Event: Internal New NH
New State: RESPONSE_AWAITED
Actions:
Send LDP-ABORT to the old downstream, and send LDP-REQUEST to the
new next hop.
2.2.5.3 State -- "ESTABLISHED"
State: ESTABLISHED
Event: LDP Request
New State: ESTABLISHED
Actions:
Ignore the event. It's an internal implementation error. For non
VC-merge ATM LSR, a new LSP control block is always created for
each LDP request.
State: ESTABLISHED
Event: LDP Mapping
New State: ESTABLISHED
Actions:
Process the LDP-MAPPING, that may contain the new attributes of
the label mapping and then propagate the LDP-MAPPING upstream.
State: ESTABLISHED
Event: LDP Release
New State: IDLE
Actions:
Disconnect the upstream label from the downstream label.
Free the upstream label.
Free the resources.
Send event `Internal Destroy' to the Next Hop Trigger Control
Block if it was in the middle of switching over to the better next
hop.
Propagate the LDP-RELEASE downstream if the LSR is not the egress
for the LSP, go to IDLE and delete the LSP Control Block.
State: ESTABLISHED
Event: LDP Withdraw
New State: Depends on the action routine.
Actions:
1) Free the resources and send LDP-RELEASE downstream.
2) If it is independent control mode, set the state to `IDLE',
create a internal LDP Request with the information in the LSP
Control Block, and pass event `LDP Request' to its own state
machine.
3) Else for the ordered control mode
3.1) If the LSP is triggered to be setup by itself (e.g it is
the ingress LSR of this LSP), send event `Internal LSP
Down' to the trigger control block, go to IDLE and delete
the LSP Control Block.
3.2) Else, if it is triggered by the incoming LDP Request,
Disconnect the upstream label from the downstream label.
Propagate the LDP-WITHDRAW upstream and go to state
`RELEASE_AWAITED'.
3.3) If the LSP is in the middle of switching over to a better
LSP, send event `Internal Destroy' to the state machine of
its New Next Hop LSP Control Block, go to IDLE and delete
the LSP Control Block.
State: ESTABLISHED
Event: LDP Upstream Abort
New State: ESTABLISHED
Actions:
Ignore the event.
Note: This scenario can occur if the upstream LSR sends a LDP-
ABORT at about the same time as the local LSR sends a LDP-MAPPING.
In this situation, it should be up to exactly one of the two LSRs
as to whether or not the label that was sent remains valid. The
LDP specification [4] procedures leave the choice to the upstream
LSR that must send an LDP-RELEASE if it will not use the label
provided.
State: ESTABLISHED
Event: LDP Downstream NAK
New State: ESTABLISHED
Actions:
Ignore the event. It is a protocol error from the downstream LSR.
The downstream LSR should always LSP-WITHDRAW to tear down the LSP
when the LSP is established.
State: ESTABLISHED
Event: Upstream Lost
New State: IDLE
Actions:
Disconnect the upstream label from the downstream label.
Free the upstream label.
Send event `Internal Destroy' to the Next Hop Trigger Control
Block if it was in the middle of switching over to the better next
hop.
Free the resources.
Propagate an LDP-RELEASE downstream, go to IDLE and delete the LSP
Control Block.
State: ESTABLISHED
Event: Downstream Lost
New State: Depends on the action routine.
Actions:
1) If the LSP is triggered by the local router (Trigger Control
Block Pointer is not zero), send event `Internal LSP NAK' to
the Trigger control block, go to IDLE and delete the LSP
Control Block.
2) Else, disconnect the upstream label from the downstream label.
Propagate an LDP-WITHDRAW upstream and go to `RELEASE_AWAITED'
state.
3) Send event `Internal Destroy' to the Next Hop Trigger Control
Block if it was in the middle of switching over to the better
next hop.
State: ESTABLISHED
Event: Internal Setup
New State: ESTABLISHED
Actions:
Ignore, it is an internal implementation error.
State: ESTABLISHED
Event: Internal Destroy
New State: IDLE
Actions:
Disconnect the upstream label from the downstream label if it is
not the ingress of the LSP.
Free the resources.
Send an LDP-RELEASE downstream, go to IDLE and delete the LSP
Control Block.
State: ESTABLISHED
Event: Internal Cross-Connect
New State: ESTABLISHED
Actions:
Connect the upstream label to the downstream label
May need to send a new LDP-MAPPING upstream with the attributes
from the new next hop.
Reset Trigger Control Block Pointer to zero.
State: ESTABLISHED
Event: Internal New NH
New State: ESTABLISHED
Actions:
1) If the LSR was in the middle of switching over to a better next
hop (Next Hop Trigger Control Block Pointer is not zero), it
send `Internal New NH' to that control block.
2) Else, create a new Next Hop Trigger Control Block, set Next Hop
Trigger Control Block pointer to point to this control block,
and pass 'Internal New NH' to this control block.
2.2.5.4 State -- "RELEASE_AWAITED"
State: RELEASE_AWAITED
Event: LDP Request
New State: RELEASE_AWAITED
Actions:
Ignore the event. It is an internal implementation error.
State: RELEASE_AWAITED
Event: LDP Mapping
New State: RELEASE_AWAITED
Actions:
It is a protocol error from the downstream LDP peer, but anyway
send a LDP-RELEASE downstream.
State: RELEASE_AWAITED
Event: LDP Release
New State: IDLE
Actions:
1) Free the upstream label
2) Delete the control block.
State: RELEASE_AWAITED
Event: LDP Withdraw
New State: RELEASE_AWAITED
Actions:
It is a protocol error from the downstream LDP peer, but send a
LDP- RELEASE anyway.
State: RELEASE_AWAITED
Event: LDP Upstream Abort
New State: IDLE
Actions:
1) Free the upstream label
2) Delete the control block.
State: RELEASE_AWAITED
Event: LDP Downstream NAK
New State: RELEASE_AWAITED
Actions:
Ignore the event. Continue waiting for the LDP-RELEASE from
upstream.
State: RELEASE_AWAITED
Event: Upstream Lost
New State: IDLE
Actions:
1) Free the upstream label
2) Delete the control block.
State: RELEASE_AWAITED
Event: Downstream Lost
New State: RELEASE_AWAITED
Actions:
Ignore the event. Continue waiting for the LDP-RELEASE from
upstream.
State: RELEASE_AWAITED
Event: Internal SetUp
New State: RELEASE_AWAITED
Actions:
Ignore the event. It is an internal implementation error.
State: RELEASE_AWAITED
Event: Internal Destroy
New State: RELEASE_AWAITED
Actions:
Ignore the event. It is an internal implementation error.
State: RELEASE_AWAITED
Event: Internal Cross-Connect
New State: RELEASE_AWAITED
Actions:
Ignore the event. It is an internal implementation error.
2.2.6 Handling the Next Hop Change
When an LSR detects a better next hop, it may decides to establish a
new LSP through this next hop. For example, an LSR is configured as
"local repair", or the LSR is configured as "global repair" and it is
the ingress end of a LSP. It can then create a Next Hop Trigger
Control Block and use the state machine of Next Hop Trigger Control
Block to establish a new LSP through the better next hop.
2.2.6.1 Next Hop Trigger Control Block
-- State
-- LSP Control Block Pointer, that points to the original LSP control
block.
-- New Next Hop LSP Control Block Pointer, that points to the LSP
Control Block that is setting up an LSP through the new next hop.
2.2.6.2 States
-- IDLE
This is the initial LSP state, when the Trigger_Control_Block is
created.
-- NEW_NH_RETRY
This is the state where an LSR waits for a retry timer to expire and
then tries to establish an LSP through a new next hop.
-- NEW_NH_RESPONSE_AWAITED
This is the state where an LSR is in the middle of establishing a new
LSP through a new next hop. It has triggered a LSP control block to
send an LDP-REQUEST towards the new next hop and is waiting for the
LDP-MAPPING.
2.2.6.3 Events
-- Internal New NH
The LSR detects there is a new next hop for a FEC.
-- Internal Retry Timeout
The LSP retry timer expires.
-- Internal LSP UP
The LSP to the new Next Hop is UP
-- Internal LSP NAK
The LSP through the new next hop could not get set up
-- Internal Destroy
This event is triggered when the LSR lost the LDP session with its
upstream neighbor.
2.2.6.4 State Transition for next hop change
+---------------------+
| |
| IDLE |<------------+
| | |
+---------------------+ |
| |
| |
| (Internal New NH) |
| |
v |
+---------------------+ |
| | |
| NEW_NH_RETRY |----------->-+
| | (Internal |
+---------------------+ Destroy) |
| |
| |
| (Internal retry timeout) |
| |
v |
+---------------------+ |
| | (Internal |
| NEW_NH_RESPONSE | Destroy) |
| _AWAITED |----------->-+
| | |
+---------------------+ |
| |
| (Internal LSP UP) |
| (Internal LSP NAK) |
+------------------------>-+
2.2.6.5 State Machine
2.2.6.5.1 State -- "IDLE"
State: IDLE
Event: Internal New NH
New State: NEW_NH_RETRY
Actions:
Start the LSP retry timer and go to the `NEW_NH_RETRY' state.
State: IDLE
Event: Internal retry timeout
New State: IDLE
Actions:
Ignore. It is an internal implementation error.
State: IDLE
Event: Internal LSP UP
New State: IDLE
Actions:
Ignore. It is an internal implementation error.
State: IDLE
Event: Internal LSP NAK
New State: IDLE
Actions:
Ignore. It is an internal implementation error.
State: IDLE
Event: Internal destroy
New State: IDLE
Actions:
Ignore. It is an internal implementation error.
2.2.6.5.2 State -- "NEW_NH_RETRY"
State: NEW_NH_RETRY
Event: Internal New NH
New State: NEW_NH_RETRY
Actions:
Restart the LSP retry timer.
State: NEW_NH_RETRY
Event: Internal retry timeout
New State: Depends on action routine.
Actions:
If the new next hop is the same one as the old next hop, go to
IDLE and delete the control block.
Otherwise, create an LSP control block that will try to establish
a new LSP through the new next hop, send event `Internal Setup' to
its state machine and go to NEW_NH_RESPONSE_AWAITED.
State: NEW_NH_RETRY
Event: Internal LSP UP
New State: NEW_NH_RETRY
Actions:
Ignore. It is an internal implementation error.
State: NEW_NH_RETRY
Event: Internal LSP NAK
New State: NEW_NH_RETRY
Actions:
Ignore. It is an internal implementation error.
State: NEW_NH_RETRY
Event: Internal destroy
New State: IDLE
Actions:
Stop the timer, go to IDLE and delete the control block.
2.2.6.5.3 State -- "NEW_NH_RESPONSE_AWAITED"
State: NEW_NH_RESPONSE_AWAITED
Event: Internal New NH
New State: NEW_NH_RETRY
Actions:
Restart the LSP retry timer, send `Internal destroy' to the
control block of the LSP for the new next hop and go to the
`NEW_NH_RETRY' state.
State: NEW_NH_RESPONSE_AWAITED
Event: Internal retry timeout
New State: NEW_NH_RESPONSE_AWAITED
Actions:
Ignore. It is an internal implementation error.
State: NEW_NH_RESPONSE_AWAITED
Event: Internal LSP UP
New State: IDLE
Actions:
Send event `Internal cross-connect' event to the LSP control block
of the new next hop.
Send event `Internal destroy' event to the original LSP control
block.
Then go to IDLE and delete the control block.
State: NEW_NH_RESPONSE_AWAITED
Event: Internal LSP NAK
New State: IDLE
Actions:
Delete the control block.
State: NEW_NH_RESPONSE_AWAITED
Event: Internal destroy
New State: IDLE
Actions:
Send event `Internal destroy' the control block for the new LSP
through the new next hop.
2.2.7 LDP Related Message Handling
- If an LSR receives an LDP-REQUEST from an upstream LSR:
a) If this is a duplicate request, discard the message. A
duplicate request means that there is a LSP Control Block that
has the same FEC, Upstream Label Request ID and Upstream Label
Request ID and same Upstream LDP Session Identifier.
b) Otherwise, create a new LSP Control Block, store the relevant
information from the message into the control block, then pass
the event `LDP Request' to its state machine.
- If an LSR receives an LDP-MAPPING from a downstream LSR:
a) Extract the 'Label Request Message ID' field and from the LDP-
MAPPING.
b) Find an LSP Control Block that has the same Downstream Label
Request ID and the same Downstream LDP Session Identifier.
c) If an LSP Control Block is found, pass the event `LDP Mapping'
to its state machine.
d) If there is no matching LSP Control Block found, then try to
find an LSP Control Block that has the same Downstream Label
and the same Downstream LDP Session Identifier.
e) If an LSP Control Block is found, pass the event `LDP Mapping'
to its state machine.
f) Otherwise, ignore the LDP-MAPPING and send a LDP-RELEASE
downstream.
- If an LSR receives an LDP-RELEASE from an upstream LSR:
a) Find an LSP Control Block that has the same Upstream Label and
the same Upstream LDP Session Identifier.
b) If an LSP Control Block is found, pass the event `LDP Release'
to its state machine.
c) Otherwise, ignore the message.
- If an LSR receives an LDP-WITHDRAW from a downstream LSR:
a) Find an LSP Control Block that has the same Downstream Label
and the same Downstream LDP Session Identifier.
b) If an LSP Control Block is found, pass the event `LDP Withdraw'
to its state machine.
c) Otherwise, ignore the LDP-WITHDRAW and send a LDP-RELEASE
downstream.
- If an upstream LDP peer is lost:
a) Find all the LSP Control Blocks whose upstream LDP peer is that
LSR.
b) Then pass the event `Upstream Lost' to their state machines.
- If a downstream LDP peer is lost:
a) Find all the LSP Control Blocks whose downstream LDP peer is
that LSR.
b) Then pass the event `Downstream Lost' to their state machines.
- If the LSR detects a new next hop for an FEC:
For each LSP that needs "local repair", or it needs "global
repair" and it is the ingress of the LSP, pass event "Internal New
NH" to its state machine.
- If an LSR receives an LDP-Abort from an upstream LSR:
a) Extract the LDP Request ID value from the LDP-Abort message.
b) Find an LSP Control Block that has the same Upstream Label
Request ID and the same Upstream LDP Session Identifier.
c) If an LSP Control Block is found, pass the event `LDP Upstream
Abort' to its state machine.
d) Otherwise, ignore the message.
- If the LSR receives an LDP-NAK from a downstream LSR:
a) Extract the LDP Request ID value from the LDP-NAK.
b) Find an LSP Control Block that has the same Downstream Label
Request ID and the same Downstream LDP Session Identifier.
c) If an LSP Control Block is found, pass the event `LDP
Downstream NAK' to its state machine.
d) Otherwise, ignore the message.
2.3. ATM Switch LSR with VC-merge
2.3.1 VC-merge
A VC-merge capable LSR can map multiple incoming labels (VPI/VCI)
into one outgoing label. It is possible that this LSR can only merge
a limited number of incoming labels into a single outgoing label. As
described in [2], suppose, for example, that due to some hardware
limitation a node is capable of merging four incoming labels into a
single outgoing label. Suppose however, that this particular node
has six incoming labels arriving at it for a particular FEC. In this
case, this node may merge these into two outgoing labels.
When an upstream LSR has a limited merging capability, it is
difficult for a downstream LSR to know how many labels should be
assigned to each FEC. In this case, downstream-on-demand is
recommended.
2.3.2 Control Block
There are 3 types of control blocks involved: Upstream LSP Control
Block, Downstream LSP Control Block, and Next Hop Trigger Control
Block.
There is one Upstream LSP Control Block for each LDP-REQUEST
received.
There is one Downstream LSP Control Block for each unique LDP-REQUEST
sent to a downstream LSR. There can be multiple Downstream LSP
Control Blocks per FEC in an LSR. This can be the result of an
upstream LSR asking for a label for an FEC. This LSR must assign a
unique upstream label and it can not merge this upstream label into
an existing downstream label for this FEC.
There is one Next Hop Trigger Control Block for each FEC for which a
better next hop has been detected and the LSR has decided to switch
to this better next hop. It could be the result of "local repair" or
"global repair" if the LSR is the ingress LSR of the LSP.
A Downstream LSP Control Block contains a list of pointers to
Upstream LSP Control Blocks or the Next Hop Trigger Control Block.
This means that this LSR has decided to map the multiple labels
listed in the Upstream LSP Control Blocks and the Next Hop Trigger
Control Block into a single label listed in the Downstream LSP
Control Block.
An Upstream LSP Control Block may contain the following information:
- Upstream LDP Session Identifier
- State
- Upstream Label (assigned by this LSR)
- Downstream LSP Control Block pointer
- Upstream LDP Request ID (assigned by the upstream LSR in
downstream-on-demand mode)
- Next_Hop_Trigger_Block pointer
Upstream Label and Upstream LDP Session Identifier can be used to
locate a unique Upstream LSP Control Block.
If an LSR is using downstream-on-demand mode, it can use the Upstream
LDP Request ID and the Upstream LDP Session Identifier to locate a
unique Upstream LSP Control Block.
An Next_Hop_Trigger LSP Control Block may contain the following
information:
- Upstream LSP Control Block pointer, that points to the one that
is needed to switch over to the better next hop
- State
- Downstream LSP Control Block pointer
A Downstream LSP Control Block may contain the following information:
- FEC
- State
- Downstream LDP Session Identifier
- list of pointers to the Upstream LSP Control Blocks or the
Trigger_Control_Blocks that are merged at this LSR for this FEC
- Downstream Label (assigned by the downstream LSR)
- Downstream Label Request ID (assigned by the LSR itself if it
is using downstream-on-demand mode)
Downstream Label, Downstream LDP Session Identifier can be used to
locate a unique Downstream LSP Control Block.
If an LSR is using downstream-on-demand mode, it can also use the
Downstream Label Request ID and the Downstream LDP Session Identifier
to locate a unique Downstream LSP Control Block.
The following diagram details the relationship between these 2 types
of control blocks:
For example, the LSR has decided to merge 3 LDP-REQUESTs of a FEC
from upstream LSR1, LSR2, LSR3 into one LDP-REQUEST and sent it to a
downstream LSR4.
+---------------------+
| |
| Upstream_LSP_Control|
| _Block for Upstream|------+
| LSR1 | |
+---------------------+ |
|
+---------------------+ |
| | |
| Upstream_LSP_Control| | (merged into)
| _Block for Upstream |------+
| LSR2 | |
+---------------------+ | +------------------------------+
| | |
+---------------------+ +--->| Downstream LSP Control Block |
| Next_Hop_Trigger_ | | | for Downstream LSR4 |
| LSP Control Block |------+ | |
| | +------------------------------+
+---------------------+
2.3.3 State Machines for Downstream-on-demand Mode
The following sections describe the state machines used in
downstream-on-demand mode.
2.3.3.1 State of the Upstream LSP Control Block's State Machine for
Downstream-on-demand Mode
-- IDLE
This is the initial LSP state.
-- RESPONSE_AWAITED
This state means that the LSR has received and processed an LDP-
REQUEST from an upstream LSR, and has sent a new LDP-REQUEST towards
a downstream LSR. The LSR is waiting for the LDP-MAPPING from the
downstream LSR.
-- ESTABLISHED
This state means that the LSR has received the LDP-MAPPING from the
downstream LSR and the LSP is up and operational.
-- RELEASE_AWAITED
This state means that the LSR has sent a LDP-WITHDRAW upstream and is
waiting for the LDP-RELEASE before freeing up the label resource.
2.3.3.2 Events of the Upstream LSP Control Block's State Machine for
Downstream-on-demand Mode
-- LDP Request
The LSR receives an LDP-REQUEST from an upstream LSR.
-- Internal Downstream Mapping
This event is sent by one Downstream LSP Control Block's state
machine. This Downstream LSP Control Block is the merged Downstream
LSP Control Block of this Upstream LSP Control Block. The event is
the result of receiving an LDP-MAPPING by the Downstream LSP Control
Block's state machine.
-- LDP Release
The LSR receives an LDP-RELEASE from an upstream LSR.
-- Internal Downstream Withdraw
This event is sent by one Downstream LSP Control Block's state
machine. This Downstream LSP Control Block is the merged Downstream
LSP Control Block of this Upstream LSP Control Block. The event is
the result of receiving an LDP-WITHDRAW by the Downstream LSP Control
Block's state machine.
-- LDP Upstream Abort
The LSR receives an LDP-ABORT from an upstream LSR.
-- Internal Downstream NAK
This event is sent by one Downstream LSP Control Block's state
machine. This Downstream LSP Control Block is the merged Downstream
LSP Control Block of this Upstream LSP Control Block. The event is
the result of receiving an LDP-NAK by the Downstream LSP Control
Block's state machine, or it detects an error.
-- Upstream Lost
The LSR loses the LDP session with its upstream LDP peer.
-- Internal New NH
The LSR detects there is better next hop and decides to establish the
lsp through this better next hop.
-- Internal Re-Cross-Connect
This event is used to trigger splicing into a different downstream
LSP. This can happens when it is switched over to a better LSP
through the new next hop.
2.3.3.3 State Transitions of the Upstream LSP Control Block's State
Machine for Downstream-on-demand Mode
+-------------------+
| |
+-------->| IDLE |<-------------------+
| | | |
| +-------------------+ |
|(LDP Abort) | |
|(Internal |(LDP Request) |
| Downstream NAK) | |
|(Upstream Lost) | (Upstream Lost) |
| v (LDP Release) |
| +-------------------+ |
| | | |
+---------| RESPONSE_AWAITED | |
| | |
+-------------------+ |
| |
|(Internal Downstream |
| mapping) |
| |
v |
+-------------------+ |
| | |
| ESTABLISHED |------->------------+
| | |
+-------------------+ |
| |
| |
|(Internal Downstream Withdraw) |
|(Internal Downstream NAK) |
v |
+-------------------+ (LDP Upstream |
| | Abort) |
|RELEASE_AWAITED |------->------------+
| |
+-------------------+
2.3.3.4 Upstream LSP Control Block's State Machine for Downstream-on-
demand Mode
2.3.3.4.1 State -- "IDLE"
State: IDLE
Event: LDP Request
New State: Depends upon the action routine.
Actions:
If this LSR is the LSP Egress or Proxy Egress [2],
Then:
choose an upstream label, allocate the resources, connect this
upstream label to the local IP forwarding module, send an LDP-
MAPPING upstream with the upstream label and go to the state
`ESTABLISHED'.
else
Obtain a next hop (or interface). Find a Downstream LSP
Control Block that has the same FEC and the same next hop and
also is able to merge more input labels. If not found, create
a new Downstream LSP Control Block with the state `IDLE'.
If the state of the Downstream LSP Control Block is
`ESTABLISHED', choose an upstream label, connect the upstream
label with the downstream label and send an LDP-MAPPING
upstream with the upstream label, and go to the state
`ESTABLISHED'.
If the state of Downstream LSP Control Block is not