Subject: Re: (ML)PPP State Machine Issues

From: Henrik Kristensen <[email-masked]>
Date: Thu, 24 Feb 2000 18:25:10 -0800 (PST)

No, I'm sorry I didn't keep the log; we don't have a PPP analyzer 
that can run on our interfaces and in cases with crossed signaling 
it's hard to exactly reconcile packet dumps from the two ends.

One case of crossed signaling was provoked by the non-restarting 
end receiving RCA in state OPENED. Another was caused by receiving 
a left-over RCR+ in stat OPENED.

I might be able to run the tests with the original code again in a 
couple of weeks.

--Henrik

> From [email-masked] Thu Feb 24 17:31 PST 2000
> From: Archie Cobbs <[email-masked]>
> Subject: Re: (ML)PPP State Machine Issues
> To: [email-masked] (Henrik Kristensen)
> Date: Thu, 24 Feb 2000 17:30:35 -0800 (PST)
> Cc: [email-masked]
> MIME-Version: 1.0
> Content-Transfer-Encoding: 7bit
> 
> Henrik Kristensen writes:
> > Thanks for the sugegstion. Increasing timeout value didn't help in 
> > this case (and latency was low; I was only running a few feet of 
> > fiber in a lab).
> > 
> > (What happened was that one end restarted without the other end
> >  noticing, which can happen if there are switches or cross-connects 
> >  in the telecom path and, one end doesn't get the chance to send 
> >  TERM_ACK before it is disconnected. 
> >  This causes the "innocent end" to jump back from OPENED to REQSENT 
> >  or ACKSENT when it gets the CONF_REQ and in this situation there's
> >  a chance the two ends will end up cycling between OPENED and 
> >  REQSENT/ACKSENT.)
> 
> Hmm... do you have a log trace of this? I still don't see how
> that would happen (though I believe you that it does)..
> 
> -Archie
> 
> ___________________________________________________________________________
> Archie Cobbs   *   Whistle Communications, Inc.  *   http://www.whistle.com
>

---

From: Henrik Kristensen <[email-masked]>
Date: Fri, 25 Feb 2000 09:19:52 -0800 (PST)

I made two changes, both with the purpose of avoiding getting kicked 
out of OPENED state when unnecessary, and a third change which is 
already valid according to RFC1661. The changes were:

1) Ignore Duplicate CONFACK received in state OPENED.

Described in RFC 1661 [1], sect.4.1 as a "crossed connection", in
some cases duplicate Configure-Ack's may be received in state OPENED,
causing the generation of a new Configure-Request and a move back to
state REQSENT. Depending on the actual scenario (delays and state to
the other end), this can cause either delayed link establishment or, 
start configuration loops (e.g. involving further timeouts).

Although it could be argued that the transition from OPENED to
REQSENT and the generation of the new Configure-Request might by
themselves be harmless, causing delays and not loops, ignoring
duplicate Configure- Ack's in state OPENED appears to be safe and
backwards compatible. (RFC 1661 [1] sect.5.2 already requires that
the Identifier and options must match those sent in the Configure-
Request, which protects against Configure-Ack's from a diffenrent
(mis)configured link!).

2) Ignore "Truly Duplicate" CONFREQ received in state OPENED.

In one scenario, link establishment can fail if one end of the link,
after having reached state OPENED receives a duplicate Configure-
Request (RCR+) which would cause it to go back to state ACKSENT and
generate what is effectively another duplicate Configure-Request
(RCR+) towards the other end. The other end might in the meantime
have received a Configure-Ack (RCA) and reached state OPENED but,
upon receipt of this new Configure-Request (RCR+) go back to state
ACKSENT, and the cycle would repeat indefinitely.

The solution to this is to ignore duplicate Configure-Requests which
may have been caused by timeouts or delays on the link. But, since a 
received Configure-Request could also be the result of the other end 
either requesting a change in configuration options (in which case 
the Identifier must be changed according to [1]) or restarting, only
"truly duplicate" Configure-Requests can be ignored. Relying only on
the Identifier is insufficient since this value may be "repeated" in
the case of the other end restarting and, since it is only an 8 bit
value.  To ensure uniqueness, an identical Magic number is required
as well.
   
This leads to the following suggested change to the PPP State
Transition Table [1].

For RCR+ is received in state OPENED (9):
      IF  Identifier is unchanged
      AND Identifier is different from zero
      AND Magic number option is present
      AND Magic number value is unchanged
      THEN sca/9
      ELSE tld,scr,sca/8

That is, if Identifier and Magic number are present and equal to the
last received values, and Identifier is different from zero, send
Configure-Ack and remain in state OPENED. Otherwise, act as
originally specified in RFC 1661 [1].
(Many implementations default to starting with Identifier value zero,
hence the extra check against Identifier = zero.)

3) Reuse Identifier when REtransmitting CONFREQ.

In order for the second change to be effective, it is also necessary 
to reuse the same Identifier when retransmitting a CONFREQ (i.e. on 
TO+ event). This is already mentioned as allowed (though neither 
recommended for or against) in RFC1661.

--Henrik

> From [email-masked] Fri Feb 25 06:38 PST 2000
> From: Dan Flowers <[email-masked]>
> To: Henrik Kristensen <[email-masked]>
> Subject: RE: (ML)PPP State Machine Issues
> Date: Fri, 25 Feb 2000 09:29:09 -0500
> MIME-Version: 1.0
> 
> Hi Henrik,
> 
> I'm curious, what changes to the FSM solved your problem?
> 
> Thanks,
> Dan
> 
> > -----Original Message-----
> > From:	Henrik Kristensen [SMTP:[email-masked]]
> > Sent:	Thursday, February 24, 2000 7:38 PM
> > To:	[email-masked]
> > Cc:	[email-masked]
> > Subject:	(ML)PPP State Machine Issues
> > 
> > Hi,
> > 
> > Please forgive me if I'm missing what ought to be "common 
> > knowledge":
> > 
> > I've seen problems with (ML)PPP LCP/NCP negotiation sequences 
> > that didn't converge even when the two ends agreed on all 
> > options.
> > 
> > I have a couple of changes to the RFC1661 state machine that 
> > seem to solve the problem and be backwards compatible but, I 
> > was wondering whether any specified or de-facto standard 
> > solution already exists that I'm not aware of ?
> > 
> > (While useful for realigning two ends using different timer
> > algorithms/constants, exponential timeout doesn't always help
> > in the case where the two ends use the same algorithm.)
> > 
> > Thanks,
> >   Henrik Kristensen
> >   Mayan Networks
>

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 25 Feb 2000 11:14:48 -0700 (MST)

> From: Henrik Kristensen <[email-masked]>

> ...

It is impossible to receive a duplicate Configure-Ack unless you either
fail to check packet ID's, or if you send Configure-Requests with duplicate
ID's.  Otherwise, there is no such thing as the very idea a duplicate
Configure-Ack.  If you do bend the standard by re-using ID's on your
Configure-Requests, then you must do something about the consequences.

> may have been caused by timeouts or delays on the link.
> ...

That is a mistake.  PPP links are universally assumed to deliver
all packets (that they deliver) in the order in which they were
sent.  That implies that if you ignore a Configure-Request from a
peer that is compliant with RFC 1661, then you will break the link.
The peer will be waiting for your Configure-Ack.  You cannot ignore
the peer's Configure-Request, even if it has the same ID as its
previous Configure-Request.

Are you failing to change or check the LCP packet ID?

> ...

Some other implementations start with an intentionally random ID,
and will use an ID of zero after having used a non-zero ID.  Anything
that assumes anything special about ID 0 is a mistake.

> recommended for or against) in RFC1661.

I may have been the person who argued vigorously for re-using ID's when
retransmitting Configure-Requests and for changing the draft to allow
them.  I know that I eventually decided it was a bad idea for my own code.
Regardless, if you do re-use ID's, you "MUST NOT" assume that the peer
will know or understand that you are doing so.  You also "MUST NOT" assume
that the peer is or is not re-using ID's.  If you do re-use ID's, then
you "MUST" also warp your own implementation of the state table as
required, probably including introducing the non-standard idea of a
"duplicate Configure-Ack", although I do not know how you can define a
"duplicate Configure-Ack" and still interoperate with existing
implementations.  As I said, I eventually decided that re-using ID's is
a bad idea at least for my own code.

There are a bazillion PPP implementations in the field.  They work, do
not get stuck, and do not make unnecessary trips through the initial
states.  Anything you do that requires changes in the state table that
they implement is wrong, even if the changes result in a better protocol.
I suspect that re-using ID's is exactly such an idea, that the protocol
would have been better (e.g. quicker to converge on a lossy link) if it
allowed for in duplicate ID's, the original state table, but that duplicate
ID's cannot be retrofitted.

Vernon Schryver    [email-masked]

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 25 Feb 2000 12:33:51 -0700 (MST)

> I wasn't trying to start a big discussion. It appears RFC1661 is
> perfect by definition, in which case I must be wrong.

That depends on whether you care more about writing a PPP implementation
that interoperatoes than about the theoretically best possible
point-to-point protocol.  Before PPP was widely deployed, I think
you would have been right.

> Just let me add in closing:
>
>   Duplicates can happen (for example in what's described as "crossed 
>   connection" in RFC1661 sect.4.1's table or, if one end times out a 
>   number of times(TO+) before the other end's first CONFACK gets 
>   back.)

Unless you fail to change the ID in your Configure-Requests, there is no
such thing as a duplicate Configure-Ack.

>   I still think my changes would be backwards compatible with 1661-
>   conformant implementations.

Wasn't the basis of your complaint or proposal is that existing RFC 1661
conformant implementations that do not re-use ID"s do not work well with
your implementation?

>                               (However some of my changes would not 
>   have any effect when "talking to" a 1661-conformant version. For
>   example, if the other end doesn't reuse the Identifier, we don't
>   ignore CONFREQ.)

How do you know whether the peer reuses ID's?  The peer might have sent
you 257 Configure-Requests, starting and ending with ID #1, but with 255
lost.  (well, assuming it has very generous/persistent timers and counters)

>   The "zero check" was an extra protection AGAINST altering the 
>   standard behavior in the zero case..:

But once again, you cannot infer anything from a zero ID.
More than one implementation does not start with ID 0.
Besides, why would the magic number value ever change, assuming
there is no evidence of loop-back?
Thus, your test is necessarily reduced to only "if the ID is unchanged."

> (Obviously, I've extended my stay on this list by now. My apologies.)

I also disagree with that.  I think you have made a compelling case that
the words in RFC 1661 that allow duplicate ID's should be removed.

The idea of duplicate ID's was neat (even if I do say so myself), but
based on the assumption that losses of Configure-Requests packets are
common.  That assumption is wrong, at least today, with ISDN, DSL, v.42
modems, and the other media where PPP is used.  Thus, reusing ID's is not
valuable.

Without changes in RFC 1661 implementations that do not reuse ID's,
re-using ID's does not work.  A conformant RFC 1661 implementation will
always assume that the peer is starting over when it receives a
Configure-Request.  It is impossible in theory and in practice to change
all or even most of the literally 100's of 1,000,000's of deployed PPP
implementations (every Microsoft Windows installation has one).
Thus, re-using ID's is a bad idea today, and it should be officiall
deprecated.

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 25 Feb 2000 17:32:58 -0700 (MST)

> Here are four changes I had to make to the RFC 1661 state machine
> to resolve certain race conditions:
>
>    RCR+ in state STOPPED: add tls
> ...

> In my implementation this problem led to a modem redialing when it
> was supposed to stay on-hook, etc.

I've always found the inter-state machine interactions in RFC 1661,
confusing, wrong, simplistic, or all of those.  I'm willing to believe
that they are close someone's real code, but I've never seen any code
where they made sense.  I've also also figured they're outside the proper
scope of the protocol (that which can be seen on the wire), and so not
worth arguing about.

I guess their main problem is that they try to formalize simple, obvious
ideas that get more confusing as you make them more formal, such as "don't
redial when you've been told to shut down" and "1+1=2".   If you never
have, try to prove, in the sense a mathematician uses the word, that 1+1=2,
but without basically saying "because it is" by quoting a definition of 2.