Subject: An MP alternative

From: James Carlson <[email-masked]>
Date: Fri, 27 Mar 1998 09:08:18 -0500

I'd like to propose the following as an alternative to full-blown MP
for very high speed (ie, SONET/SDH) systems using PPP.  I think the
rest of the text stands on its own.  Please post any comments to the
list.  Thanks!

PPP Working Group                                             J. Carlson
Internet Draft                                       IronBridge Networks
expires in six months                                         April 1998

                   PPP Link Balancing Detection (LBD)
                     <draft-ietf-pppext-lbd-00.txt>

Status of this Memo

   This document is the product of the Point-to-Point Protocol
   Extensions Working Group of the Internet Engineering Task Force
   (IETF).  Comments should be submitted to the [email-masked]
   mailing list.

   Distribution of this memo is unlimited.

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months.  Internet-Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet-
   Drafts as reference material or to cite them other than as a
   ``working draft'' or ``work in progress.''

   To learn the current status of any Internet-Draft, please check the
   1id-abstracts.txt listing contained in the Internet-Drafts Shadow
   Directories on ds.internic.net, nic.nordu.net, ftp.nisc.sri.com, or
   munnari.oz.au.

Abstract

   The Point-to-Point Protocol (PPP) [1] provides a standard method for
   transporting multi-protocol datagrams over point-to-point links.

   PPP also defines an extensible Link Control Protocol, which allows
   the detection of optional link handling procedures, as well as a
   Multilink procedure (MP) [2] which allows operation over multiple
   physical links.  This document defines an extension to MP called Link
   Balancing Detection (LBD).

Carlson                   expires October 1998                  [Page 1]

INTERNET DRAFT        PPP Link Balancing Detection            April 1998

Table of Contents

   1.      Introduction ...........................................    2
   1.1.    Conventions ............................................    3
   2.      MRRU Configuration Option Modification .................    3
   3.      Bundle Establishment ...................................    3
   4.      Bundle Tear-Down .......................................    4
   5.      Message Distribution ...................................    4
   6.      Security Issues ........................................    5
   7.      References .............................................    5
   8.      Authors' Addresses .....................................    5

1.  Introduction

   Standard PPP negotiation allows for two types of links with regard to
   multiple link layer entities.  The standard type of PPP link is nego-
   tiated without the Maximum-Receive-Reconstructed-Unit (MRRU) option
   and appears as a separate network interface to the network layer and
   to routing protocols.  The Multilink PPP (MP) [2] type of link uses
   the MRRU option and allows multiple PPP links to be bundled into one
   network interface.  An MP link appears as a single network interface
   to the network layer and to routing protocols.

   There are many advantages having multiple links between two nodes
   appear at the network layer to be a single link.  One is that less
   stress is placed on scarce routing system resources, and another is
   that routing system stability in the face of errors is usually
   higher.

   The main disadvantage to the current MP technique is that it does not
   constrain the fragmentation which may be done by the peer.  For sys-
   tems employing general purpose CPUs in the data path and with
   scatter-gather direct memory access (DMA) capability, this is often
   not a problem.  For systems with very high bandwidth capabilities,
   these features are often infeasible, and this problem makes MP unus-
   able.

   This draft describes a method similar to (and compatible with) MP for
   detecting multiple links to the same node, but without the fragmenta-
   tion or reordering protection of MP.  Instead, datagrams are distri-
   buted intact among the links in any convenient manner, including
   based on an IP [3] address hash or simple round-robbin service.

Carlson                   expires October 1998                  [Page 2]

INTERNET DRAFT        PPP Link Balancing Detection            April 1998

1.1.  Conventions

   The following language conventions are used in the items of specifi-
   cation in this document:

      o  MUST, SHALL, or MANDATORY -- This item is an absolute require-
         ment of the specification.

      o  SHOULD or RECOMMEND -- This item should generally be followed
         for all but exceptional circumstances.

      o  MAY or OPTIONAL -- This item is truly optional and may be fol-
         lowed or ignored according to the needs of the implementor.

2.  MRRU Configuration Option Modification

   The MRRU option from MP is modified to allow a new distinguished
   value.  This value is zero, and indicates that the Configure-Request
   sender wishes to bundle multiple links but refuses to reconstruct
   received fragmented datagrams or to use the header as defined in MP.

   The receiver of Configure-Request with MRRU set to zero MAY
   Configure-Reject it to disable all MP support, including LBD, or MAY
   send Configure-Nak with a hint set non-zero to request standard MP
   support, or MAY send Configure-Ack to indicate its willingness to run
   LBD.

   Both peers MUST agree that MRRU is not in effect, or that it is zero,
   or that it has a non-zero value.  If MRRU has a non-zero value, how-
   ever, it need not be identical in each direction.  If LCP goes to
   Open state with the MRRUs set to an illegal set of values (id est,
   one zero and the other non-zero), then an implementation SHOULD ter-
   minate the link or MAY choose to renegotiate LCP.

3.  Bundle Establishment

   As with MP, bundle establishment is based on a combination of the
   peer's supplied endpoint discriminator (ED) and the peer's identity
   as determined via link authentication.  The algorithm used for LBD is
   identical to the MP algorithm, and is documented here only for con-
   venience.

   When authentication (if any was negotiated via LCP) is complete, a
   check is made before attempting to negotiate any Network Control Pro-
   tocols (NCPs).  If an MRRU (either zero or non-zero) is agreed to by

Carlson                   expires October 1998                  [Page 3]

INTERNET DRAFT        PPP Link Balancing Detection            April 1998

   both peers and if there is an existing LBD bundle where the ED (or
   lack thereof) matches the new link's ED (or lack), and the authenti-
   cated peer name (or lack thereof) match the new link's peer name (or
   lack), then this new link should be made part of the bundle and no
   new NCPs are created.  Otherwise, this is a separate link, and NCPs
   should be started.

   If the local and remote MRRU values do not agree with the bundle,
   then the link SHOULD be terminated.  An implementation MAY choose
   instead to renegotiate LCP to repair the error.  If the MRRU values
   are zero, then the MRU values MUST also be checked in the same
   manner.

   When LBD is in effect, in contrast with standard MP, the value adver-
   tised to the network layer as the MTU MUST be the peer's requested
   MRU (or any smaller value), rather than the negotiated MRRU.

4.  Bundle Tear-Down

   Tear-down is identical to standard MP and is thus not covered here.

5.  Message Distribution

   To distribute messages among the links, a few simple rules must be
   followed.

   First, since PPP negotiation does not withstand reordering, all PPP
   negotiation messages MUST be sent over a single link to avoid possi-
   ble reordering.  The first link in a bundle MUST be used to transmit
   PPP messages until this link is terminated.  If the first link is
   terminated, then one remaining link in the bundle MUST be chosen for
   subsequent messages.  Once that link is chosen, an implementation
   MUST continue sending all PPP negotiation messages over that single
   link.  Any remaining link in the bundle MAY be chosen, and it is
   entirely possible that each peer may choose a different link without
   harm to the PPP protocol.

   Second, PPP negotiation messages MUST be handled when received on any
   link.  An implementation MAY choose to terminate the last link over
   which negotiation was received if negotiation is received over a dif-
   ferent link, since this transition implies that the peer has already
   terminated the prior link.

   Third, network datagrams SHOULD be distributed over all links as

Carlson                   expires October 1998                  [Page 4]

INTERNET DRAFT        PPP Link Balancing Detection            April 1998

   evenly as possible.  There are no requirements that any particular
   distribution algorithm be used.  Note, however, that some network
   protocols behave poorly when subjected to message reordering, so
   techniques which prevent reordering (such as deterministic hashes of
   network layer addresses) are encouraged.

   Fourth, the common but technically non-standard practice of using LCP
   Terminate-Request to gracefully terminate a link without data loss is
   encouraged in LBD implementations.  To do this, an implementation
   leaves Open state on sending LCP Terminate-Request, but, contrary to
   RFC 1661 [1], continues processing received datagrams until the peer
   replies with LCP Terminate-Ack.

6.  Security Issues

   The authentication and bundling techniques are identical to standard
   MP and the security issues are the same as with RFC 1990.

7.  References

   [1] W. Simpson, "The Point-to-Point Protocol (PPP)", RFC 1661,
      07/21/1994

   [2] K. Sklower, et al, "The PPP Multilink Protocol (MP)", RFC 1990,
      08/1996

   [3] J. Postel, "Internet Protocol", RFC 791, 09/01/1981

8.  Author's Address

   James Carlson
   IronBridge Networks
   55 Hayden Avenue
   Lexington MA  02173-7999

   Phone:  +1 781 402 8032
   Fax:    +1 781 402 8092
   Email:  [email-masked]

Carlson                   expires October 1998                  [Page 5]


-- 
James Carlson, Consulting S/W Engineer  <[email-masked]>
IronBridge Networks / 55 Hayden Avenue  71.246W    Vox:  +1 781 402 8032
Lexington MA  02173-7999 / USA          42.423N    Fax:  +1 781 402 8092
"PPP Design and Debugging" ------- http://id.wing.net/People/carlson/ppp

---

From: Gerry Meyer <[email-masked]>
Date: Tue, 7 Apr 1998 16:07:37 +0100 (BST)

Since the only rational given for your proposal is that
fragmentation is undesirable on high speed links, would it not
be more appropriate to include a sentence to that effect in the
next multilink RFC (which must be ready to advance by now).
 
    Gerry

---

From: James Carlson <[email-masked]>
Date: Tue, 7 Apr 1998 11:59:50 -0400

> next multilink RFC (which must be ready to advance by now).

That's a perfectly acceptable solution to me provided that the next MP
RFC describes that this is an option, and how to properly negotiate
that both peers want to do this.  (It's not clear what the dividing
line between "low" and "high" speed links might be, and the line
probably moves over time, and the position of the line at any point in
time probably also depends on the architecture of the device itself.
This argues that it should be a negotiable item, rather than just a
convention for usage.)

I think this amounts to a little more than a single sentence (but only
a little more).  There's certainly more than one way to skin this cat,
and I'm not wedded to either solution (separate RFC or integrated).

Any comments from Mr. Sklower (et al)?

(It's been pointed out to me in private email that I didn't adequately
note that, for instance, OSPF can detect ECMP.  This is a more general
mechanism, since the equal cost paths might take arbitrary walks
through the topology, and it does have scaling problems which are
exacerbated by having multiple parallel links.  The good thing about
this approach is that with a given set of constraints on OSPF, a
network can scale further by using this simple mechanism.)

(It was also pointed out that a "minor" modification to OSPF could
allow it to detect that a set of links were all connected to a single
peer and then emit a single LSA for the group of links.  This does
require a modified OSPF at both ends [it just won't do to have one
side generate a single LSA and the other generate many] but it doesn't
seem as simple as this mechanism.)

---

From: John Bray <[email-masked]>
Date: Tue, 7 Apr 1998 09:24:52 -0700 (PDT)

> next multilink RFC (which must be ready to advance by now).

I agree, the issue is really whether you want fragmentation or not.
Removing multilink headers completely means you can only support
protocols that are insensitive to reordering unless you force such
packets over one link.  An option which disables fragmentation without
also removing MP headers would be more desireable.

John

---

From: James Carlson <[email-masked]>
Date: Tue, 7 Apr 1998 13:18:59 -0400

> also removing MP headers would be more desireable.

I disagree.  Removing the MP headers (or at least the normal affect of
the headers) is also required here.

There are two points here.  The first is that fragmentation by the
peer is harmful to an all-hardware implementation since it implies
aribrary-sized data block handling.  The second is that the reordering
implied by the MP sequence numbers is itself also harmful in hardware
implementations since it implies dedicated message-sorting input
queues which are problematic at high speed.

It is not the case that without MP sequence numbers that I am
necessarily reordering any messages where it would matter.  In section
5 of the draft I carefully delineate usage conventions and
implementation options which prevent harmful reordering.  For IPv4,
for instance, outgoing link determination based on a hash of source
and destination addresses prevents reordering within a TCP stream,
which is generally a goal of MP sequencing.  The choice of links for
PPP negotiation messages is also covered in that section.

The goal of this draft is to arrive at a variant of MP which has the
low overhead and simple hardware implementation of traditional load
balancing while retaining the valuable negotiation and single-NCP
model of MP.

---

From: John Bray <[email-masked]>
Date: Tue, 7 Apr 1998 10:48:41 -0700 (PDT)

> queues which are problematic at high speed.

OK.  In some cases it may be desirable to omit the headers.  I contend
that I might want to keep the headers but turn off fragmentation.  I
think this should be separately negotiable.

> PPP negotiation messages is also covered in that section.

I understand.  You're forcing packets that are sequence sensitive over
a given link (regardless of how you accomplish that).  So packets for
a given TCP connection (to use your example) always travel over one
link.  It seems to me that kind of limits the amount of adaptive link
balancing you can do.

Now what about stateful data compression?  You would have to support
multiple compression histories (at least one per link), or do per-link
compression, wouldn't you? 

John

---

From: James Carlson <[email-masked]>
Date: Tue, 7 Apr 1998 14:36:07 -0400

> think this should be separately negotiable.

Ok; at that point I think we might require a new mechanism.  I suppose
that you could use another distinguished MRRU value (say 1?) to
indicate the option of handling sequencing with the normal headers but
with no fragmentation or reassembly supported (all 'fragments' have B
and E bits set).

It's not entirely clear to me what the application for this mode might
be, but it doesn't sound unreasonable.

> link.  It seems to me that kind of limits the amount of adaptive link

Yes, that is the case whenever traditional load balancing is done.
The general mechanism is to include enough data in the hash such that
a given flow lands on an almost "random" link, but that it lands on at
most one link.

The happy accident that occurs here is that multiple parallel very
high speed links also tend to have aggregate traffic for which hashing
works nicely to do load balancing.

> compression, wouldn't you? 

Gee whiz!  If I could do data compression at these speeds, I'd
probably have no trouble with variable-sized blocks.  ;-}

Seriously, yes, I considered that.  Both ECP and CCP would need to be
done with the per-link (00FB and 0055) variants in this case, or at
least the mostly-unused "multiple histories" feature of some
compression algorithms would need to be used.