Subject: [Fwd: LDP protocol problem?]

From: Eric Gray <[email-masked]>
Date: Fri, 18 Jan 2002 13:54:11 -0500

oops, meant to send to the list...

--
Eric Gray (mailto:[email-masked])
http://www.mindspring.com/~ewgray

Subject: Re: LDP protocol problem?
From: Eric Gray <[email-masked]>
To: [email-masked]
Date: Fri, 18 Jan 2002 13:53:18 -0500

[email-masked] wrote:

> Vijay wrote:
> >I faced a similar problem some time back
> >
> >I think the problem comes because of the configuration of the LDP label
> >distribution mode, control mode and Request mode.
> >
> >Particularly here the request node is REQUEST_NEVER though the distribution
> >mode is DuS. If router B were 'Request When Needed' then it would have
> >requested A for a label when A becomes its next Hop then the problem would
> >have been overcome by A sending the mapping again after receiving the
> >request. I wonder if DuS Ind control with 'Request Never' is not a good
> >configuration choice
> >
> >Please correct me if I am wrong.
>
> The problem also manifests itself if the session is
> "Request-when-Needed" and "Downstream-on-Demand."  Example:
>
>   Router A                          Router B
>   --------                          --------
>
>                                     Router A becomes the next hop
>                                     Sends Label Request
>   Receives Label Request
>   Sends Label Mapping (Label 1)
>                                     Router A becomes NOT the next hop
>                                     Sends Label Abort Request
>   Receives Label Abort Request
>    (which is ignored)
>                                     Receives Label Mapping (Label 1)
>                                     Sends Label Release (Label 1)
>                                      (because Router A is not the next hop)
>   Sends Label Mapping (Label 1)
>    (because the hop count changed)
>                                     Router A becomes the next hop
>                                     Sends Label Request
>   Receives Label Release (Label 1)
>                                     Receives Label Mapping (Label 1)
>   Receives Label Request
>   Sends Label Mapping (Label 2)
>                                     Receives Label Mapping (Label 2)
>                                     Sends Label Release (Label 2)

No.  Router B has done a BAD THING.

Label Requests are used as transaction IDs.  In this case,  Router B has abused the
transaction ID concept by using Label 1 (which was received in a Label Mapping
that was not a response to an earlier Label Request - it contains no label request
message ID) as a response to a label request.  It is theoretically possible to do
this, but the router that decides to do this MUST be smart enough to figure out
how to recover from this and other scenarios.  In this scenario, for example, it
is possible for Router B to simply start using Label 2 when it receives it and
release Label 1 at that time.  For Router B to decide to use an unsolicited Label
Mapping as a response for a Label Request is a MYBAD that it has to know
how to fix.

Also, it is most often the case that downstream on demand is used only with
ordered control.  This is because labels received with an unknown hop count
may not be useful since using them may mean that packets are dropped at the
point where the LSP setup is not yet complete.  With ordered control mode,
this scenario is simply not going to come up all that often.

There is always a 'robustness' behavior that is well understood, if not exactly
specified.  If Router A is getting labels it does not know how to handle (it
has no corresponding ILM for these labels), it is a simple matter of software
to realize that it should send a Label Release for those labels to the LSR that
is sending them.

>
>   Receives Label Release (Label 2)
>
> The final outcome is the same.  Router B believes that a
> Label Mapping exists; Router A believes that no Label Mapping exists.
>
> The problem seems independent of distribution, control, or retention
> modes.  The crux of the problem is that when Router A sends a
> Label Mapping message which is an "update" message (the same FEC
> and Label as a previous message, usually sent to change the
> hop count and/or path vector) and then subsequently receives a
> Label Release message for that FEC and Label, one of two
> situations can exist:
>
>   * If Router B sent the Label Release after receiving the
>     "update" message, then Router B is not keeping the label
>
>   * If Router B sent the Label Release before receiving the
>     "update" message, then Router B may in fact keep the
>     label if his situation changed between sending the
>     Label Release and receiving the "update" message.
>     (The most likely reason for the situation to change
>     would be Router A becoming the next hop for the FEC.)
>
> Router A simply cannot reliably determine which of these
> two situations exists on Router B.

--
Eric Gray (mailto:[email-masked])
http://www.mindspring.com/~ewgray

---

From: Jack Brennen <[email-masked]>
Date: Fri, 18 Jan 2002 14:35:33 -0500

> No.  Router B has done a BAD THING.

I won't argue this point, merely because it's not fundamental to my finding
of a possible protocol instability.  The fundamental problem is that an "update"
Label Mapping message can "cross on the wire" with a Label Release message for
the same FEC/Label combination.  It is possible, in several ways, for Router B
to accept the "update" Label Mapping message as if it were a normal unsolicited
Label Mapping, even though it just recently released a Label Mapping for the
same FEC.  Reasons why Router B might do this:

   (1)  The original Label Mapping caused a "loop detection" failure,
        but the "update" Label Mapping did not.
   (2)  Router A was not the next hop when the original Label Mapping
        was processed, but is the next hop when the "update" Label Mapping
        is processed.
   (3)  Router B had no available memory to keep the original Label Mapping,
        but memory became available by the time the "update" Label Mapping
        was processed.

If "update" Label Mapping messages were syntactically different than normal
unsolicited Label Mapping messages, the whole problem could be avoided.  That
is how I would fix the specification if it were my decision.

> to realize that it should send a Label Release for those labels to the LSR that

In my examples, Router A thinks that the label has been released by Router B,
so it is free to reassign it to a different FEC -- there may be a corresponding
ILM for the label (on Router A) when Router B actually puts traffic onto it,
in which case Router A won't see anything amiss.

Also, I think you mean that Router A should send a Label Withdraw.  I don't
necessarily agree, but I wouldn't argue too hard against it.

    Jack

---

From: Eric Gray <[email-masked]>
Date: Fri, 18 Jan 2002 15:40:29 -0500

Jack,

    Yes, I meant Label Withdraw.

    The case where Router A re-issues Label 1, is problematic only for the
time it takes Router B to receive the corresponding Label Mapping.  Once
Router B receives a Label Mapping for a label it already has and a different
FEC, Router B will know that it is screwed up.  It is reasonably well
known that you should not re-use a label you have just removed from service
for some period of time as this is likely to result in miss-routed packets in
any case.  This would be forced in the case where Router A withdraws a label
mapping because Router A cannot then re-use the label until it receives a
Label Release for that label.

    Having a syntactically different messages for the initial and subsequent
update Label Mappings would fix the problem you're describing, but it may
not be necessary.  One simple way to avoid this problem is to treat any label
received unsolicited (when operating in DoD mode) as an update.  If this is
what you do, then you would not end up using any label you did not get as
a result of a Label Request - at least originally.

    I tend to think of DU and Liberal Retention as being a bundled package
and the same for DoD and Conservative Retention.  I told Bob Thomas a
long time ago that - while I think it reasonable for an implementation  to
send Label Requests in DU mode - I do not think it is reasonable for an
implementation to send unsolicited Label Mappings when operating in
the DoD mode.  If it were up to me, in DoD mode, the only Label Mappings
I would not immediately Release would be the ones I asked for and updates
for the ones I asked for.

---

From: Jack Brennen <[email-masked]>
Date: Fri, 18 Jan 2002 16:16:38 -0500

Eric Gray wrote:
> time it takes Router B to receive the corresponding Label Mapping.

Yes, I agree.

> Once
> FEC, Router B will know that it is screwed up.

Now you have imposed a requirement on Router B to look up a label in its
Label Information Base every time it receives a Label Mapping.  This is expensive
and is not called for in RFC 3036.

Furthermore, LDP explicitly allows a single label to be associated with multiple
FECs.  From 3.5.11.1 (Label Release Message Procedures):

   The FEC TLV may contain the Wildcard FEC Element; if so, it may
   contain no other FEC Elements.  In this case, if the Label Release
   message contains an optional Label TLV, then the label is to be
   released for all FECs to which it is bound.

> It is reasonably well
> any case.

I disagree that this is true from the point of view of Router B; if the downstream
router has advertised a FEC/Label combination, said router is indicating that it is
ready to switch that label now, not at some point in the future.

Your statement is correct from the point of view of Router A; after the last release
for a label is received, Router A should avoid readvertising that label until all
packets in transit have had a chance to clear the network.  But that's not what
my example shows.  Router A is not readvertising a released label, it just looks
that way from Router B's perspective.

> This would be forced in the case where Router A withdraws a label

Correct.  A Label Withdraw message is semantically a request for a release message,
and the label is not actually freed until that Label Release is received.

> a result of a Label Request - at least originally.

But the problem has nothing to do with DoD mode.  It occurs in DU mode as well:

  Router A                          Router B
  --------                          --------

  Sends Label Mapping
   (Path Vector=<B,C,D,A>)
                                    Receives Label Mapping
  Router A gets a new next hop
   for the FEC
  Sends Label Mapping
   (Path Vector=<E,F,G,A>)
                                    Sends Label Release
                                     (loop detected)
  Receives Label Release
                                    Receives Label Mapping

At the end of this scenario, Router B holds a label which he believes was
validly advertised by Router A.  Router A believes that Router B released
the label.

> and the same for DoD and Conservative Retention.

Okay, but RFC 3031 (MPLS Architecture) specifically allows DU & Conservative
to be used together.  See section 5.2.1, scheme 3.

> I told Bob Thomas a

I agree; if a session is in DoD mode, unsolicited label mappings shouldn't
be sent, and should be released if received.

---

From: Eric Gray <[email-masked]>
Date: Fri, 18 Jan 2002 16:49:26 -0500

Jack,

    Please see below...

You wrote (in part):

> ...

It's hard to specify robustness sometimes.  I am sure there are
other ways to know if a label mapping you have received is one
you have previously received and retained then looking it up in
your LIB.  I also seem to recall this being a check in at least
some of the steps in the appendix under receive label mapping.

>    released for all FECs to which it is bound.

I am pretty sure that you cannot send unsolicited label mappings
for multiple FECs because of the ramifications on the LSPs going
upstream.  But I don't really have the time right at the moment
to put my finger on where it says that in the spec, so I may be
wrong.

> that way from Router B's perspective.

And Router A is the one making the commitment to deliver a set
of packets in a certain way.  So only Router A's perspective
counts.  If it waits some reasonable amount of time before it
re-issues a label, then it does not matter what Router B's
point of view is with respect to that label.

> ...

This is a smallish sort of window, which may be sorted by simply
having Router A send a Label Withdraw when it receives packets
that are labeled with the labels that Router B mistakenly thinks
are valid.  I think that a robust LSR implementation will do
that in any case.

I think it's time for Bob Thomas to take the torch on this one.
The specification is currently being revised for submission as
a draft standard.  If people can convince him that adding some
semantic/syntactic differentiator is a good idea, then it will
be in the next version.  It makes absolutely no difference to
me.

> to be used together.  See section 5.2.1, scheme 3.

Yeah, but this is a monkey trap.  The fact that it is allowed
does not change the fact that it is a very bad idea.  You have
to realize that DU and Conservative Retention means you will
have to release almost all of the labels you get in any real
world router with any interesting number of interfaces and
peers.  Why would you want to do that?

> ...

---

From: Jack Brennen <[email-masked]>
Date: Fri, 18 Jan 2002 18:03:29 -0500

> are valid.  I think that a robust LSR implementation will do

But Router A believes Router B to have released the label, so he may
reuse it for another purpose.  When Router B eventually puts traffic
onto the label (which may occur hours later), there is no reason to
believe that the label will still be unassigned.

And it is a smallish sort of window, but I'm not bringing this to the WG's
attention because of a theoretical concern.  This problem is being observed
in our lab under stress conditions.  It really happens in the real world.  :-(

Another way to look at this, which I hope *clearly* demonstrates the
intractable nature of this problem.  Consider these three protocol
conversations:

   Conversation 1                           Conversation 2
   --------------                           --------------

   Router A            Router B             Router A        Router B
   --------            --------             --------        --------
   Send LMap                                Send LMap
                       Recv LMap                            Recv LMap
                       Send LRel                            Send LRel
   NHOP Changes                             Recv LRel
   Send LMap                                NHOP Changes
   Recv LRel                                Send LMap
                       Recv LMap                            Recv LMap

   Conversation 3
   --------------

   Router A            Router B
   --------            --------
   Send LMap
                       Recv LMap
   NHOP Changes
   Send LMap
                       Recv LMap
                       Send LRel
   Recv LRel

These conversations are all legal according to the LDP spec,
and all are reasonably likely to happen.  Note that Router B can't
tell the difference between Conversations 1 & 2, and Router A can't
tell the difference between Conversations 1 & 3.

  Conversation 1:  A ends up with no label allocated, B has a label
  Conversation 2:  A and B both end up with a label allocated
  Conversation 3:  A and B both end up with no label allocated

Clearly, Conversation 1 leads to problems, but neither Router A nor
Router B can distinguish this from the valid Conversations 2 & 3.

This is a deficiency in the protocol, and we can brainstorm any number
of methods to work around the problem, but the problem is there,
and should be addressed.

   Jack

---

From: Abhijit Gadgil <[email-masked]>
Date: Sun, 20 Jan 2002 23:17:59 +0530 (IST)

Jack,

Yes I agree to you, a simple solution to this problem could be as follows

Label Release message will carry mesg-id (mandatory)to indicate exactly
this is an ack for which message, this can work for withdraw messages as
well. So there is no need to change the semantics of original mappings and
updates.

The LSR which receives this release, can check the message-id and take a
decision on to what can be done with it. If the mesg-id is older than the
most recently used message-id (to the peer, for that fec), it may ignore
the Release message, silently.

If the Release is as a result of some internal event at LSR, it may use
the message-id field of all zero's to indicate the internal event. (If the
release is being propagated, it can still be interpreted by downstream LSR
as internal event at upstream LSR). In such case, the downstream LSR
should not silently ignore this.

I tried working this scheme for two or three scenario's which you have
specified, it works correctly.

Also as Eric has pointed out on this thread a label release is an ack to
label withdraw message, its not quite unreasonable to send it as nack for
"a specific mapping" message. It doe not complicate the processing of
label mapping message and any LSR does not have to do extra work to check
whether a mapping received is updated mapping or not. An LSR when it needs
to do so, can simply release with proper mesg-id.

Does this sound alright?

-abhijit

-- 
-abhijit

Abhijit Gadgil
Graduate Student,
Dept. of Electrical Engineering,
IIT, Bombay.

---

From: Praveen Kumar <[email-masked]>
Date: Mon, 21 Jan 2002 17:19:38 +0530 (IST)

> is how I would fix the specification if it were my decision.

I agree with this.

Label Mapping message allows an optional mesg id field which can indicate
the mesg id of corresponding Label Request Message. Here either 
"update" or "unsolicited" mapping messages are not result of any label
request. So, how about carrying special mandatory (reserved) ids in these
fields, for these two cases. Thus this reserved id can logically/ 
syntactically differentiate these two cases.

For the cases mentioned by jack, LSR A can determine whether the received
release message is result of recently sent update mapping or previous
mapping by using the approach suggested by "gabhijit". 

The differentiation of mapping messages that are sent as a result of label
request, result of update or result of advertisement mode gives more
flexibility to an receiving LSR to take any further (may be 
future) decisions.

Correct me if am wrong.

-- 
S.Praveen Kumar
Graduate Student
KReSIT, IIT-Bombay
web: http://www.it.iitb.ac.in/~praveen