Pip Working Group                                             P. Francis
INTERNET-DRAFT                                    (formerly P. Tsuchiya)
                                                                Bellcore
                                                               June 1993


                        Pip Address Conventions


Status of this Memo

   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."

   Please check the I-D abstract listing contained in each Internet
   Draft directory to learn the current status of this or any other
   Internet Draft.


Abstract

   Pip is an internet protocol intended as the replacement for IP
   version 4.  Pip is a general purpose internet protocol, designed to
   handle all forseeable internet protocol requirements.  This
   specification is one of a number of documents that specify the
   operation of Pip.  This specification describes the conventions for
   using the various Pip addresses--the hierarchical unicast address,
   the class-D style multicast address, the CBT multicast address, and
   the nearcast address.  This specification does not describe how Pip
   addresses are assigned.


Conventions

   All functions in this specification are mandatory.





Pip WG, Expires December 1993                                   [Page 1]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


1.  Introduction

   Addressing is the core of any internet architecture.  Pip Addresses
   are carried in the Routing Directive (RD) of the Pip header (except
   for the Pip ID, which in certain circumstances functions as part of
   the Pip Address).  Pip Addresses are used only for routing packets.
   They do not identify the source and destination of a Pip packet.  The
   Pip ID does this.  This memo describes the various Pip addressing
   types.

   There are four Pip Address types [2].  The hierarchical Pip Address
   (referred to simply as the Pip Address) is used for scalable unicast
   and for the unicast part of a CBT-style multicast and nearcast.  The
   multicast part of a CBT-style multicast is the second Pip address
   type.  The third Pip address type is class-D style multicast.  The
   fourth type of Pip address is the so-called "nearcast" address.  This
   address causes the packet to be forwarded to one of a class of desti-
   nations (such as, to the nearest DNS server).

   Bits 0 and 1 of the RC for the near-term Pip architecture indicate
   which of four address families the FTIFs and Dest ID apply to.  The
   values are:

      Value      Address Family
      -----      --------------
       00        Hierarchical Unicast Pip Address
       01        Class D Style Multicast Address
       10        CBT Style Multicast Address
       11        Nearcast Pip Address

   The remaining bits are defined differently for different address fam-
   ilies, and are defined in the following sections.  The RC Contents
   value associated with this RC definition is 1.



2.  Hierarchical Unicast Pip Addresses




2.1.  General

   Pip Addresses are hierarchical addresses.  Pip Addresses are assigned
   such that a number at any level of the hierarchy is unique only with



Pip WG, Expires December 1993                                   [Page 2]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   respect to the levels above it.  Because of this, all Pip Address are
   unique.

   While the sole purpose of the Pip Address is to encode topologically
   significant addresses, the Pip Address does also represent a hierar-
   chy of Pip Address Assignment Authorities (PAAA).  At the top of the
   PAAA hierarchy is the root PAAA.  This PAAA assigns top-level Pip
   Address numbers.  These numbers appear at the top of any fully-
   enumerated Pip Address.  (By fully-enumerated, we mean a Pip Address
   where all levels of the address are given.)

   Pip Addresses signify either the location of a Pip system (host or
   router), or a subnetwork.  In the latter case, the Pip ID is used to
   route a Pip packet to a Pip system across the subnetwork.  Thus, a
   Pip Address or a Pip Address+ID causes a Pip packet to be routed to
   the Pip processing module of a given Pip system, after which the Pro-
   tocol field of the Pip header is used for further demultiplexing.
   (This having been said, the extension of a Pip Address on the least
   significant end to signify sub-system entities, such as processors
   within a multi-process host, or peripherals such as a screen or disk,
   is possible.  Such use is a local matter--it does not effect Pip
   routing outside the host.  Such use is outside the scope of this
   specification.)



2.2.  Routing Context (RC) Structure

   When the RC Contents field is 1, bits 0 and 1 of the Routing Context
   (RC) indicate the address family.  If the address family is Pip
   Hierarchical Unicast Address, then bits 0 and 1 are value 00.  When
   this RC indicates Pip Hierarchical Unicast Address (called simply the
   Pip Address in this document), the RC is structured as follows:

      bits       meaning
      ----       -------
      0,1        address family (= 00)
      2,3        level
      4,5        metalevel
      6          exit routing type

   This document discusses the conventions for handling Pip Addresses
   and their related Routing Context.





Pip WG, Expires December 1993                                   [Page 3]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


2.3.  Pip Addresses in the Pip Header

   The Pip header carries Pip Addresses as a sequence of FTIFs (Forward-
   ing Table Index Fields).  Each FTIF is 16 bits in length.  Usually,
   each FTIF represents one layer of the hierarchy, although it is pos-
   sible for a single hierarchy layer to span multiple 16-bit FTIFs.
   The sequence of FTIFs is called the FTIF Chain.

   Both the source and destination Pip Addresses are carried in the same
   FTIF Chain.  The source Pip Address comes first, and is written in
   order of lowest hierarchy level first.  The destination Pip Address
   follows, and is written in order of highest hierarchy level first.
   Note that, depending on the locations of source and destination rela-
   tive to each other, it is not always necessary to include the top
   levels of the Pip Address in the FTIF Chain.

   The least significant bits of each FTIF is the relator.  The three
   relator types are:

       value                     type
       -----                     ----
       last bit = 0              horizontal
       last 5 bits = 11111       extension
       all others                vertical

   The relator indicates what the relationship between the current and
   subsequent FTIF is.  Horizontal indicates that the subsequent FTIF is
   a separate Pip Address number, but that the number is neither
   hierarchically above nor below the current one.  Vertical indicates
   that the subsequent FTIF is a separate Pip Address number, and that
   number is hierarchically above or below the current one.  Extension
   indicates that the subsequent FTIF is part of the same Pip Address
   number.

   When a Pip Address number is greater than 15 bits in length, then the
   extension must be used to encode the number.  When an extension is
   used, the Pip Address number is right-justified.  For instance, if
   the Pip address number (without the relator) is hex 89ab, and the
   subsequent number is below it, then it is written as 3f,1357 The last
   bit of "1357" is neither "0" nor "11111", which means vertical.  The
   last five bits of "3f" are "11111", which means extension.  The
   extension is needed because the vertical relator caused the number to
   be 17 bits long, thus forcing the extension.

   The reason for using five bits to encode extension and one bit to



Pip WG, Expires December 1993                                   [Page 4]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   encode horizontal and vertical is to 1) maximize the code space
   available for horizontal and vertical use (each type gets roughly 1/2
   the code space), and 2) maximize the use of forwarding table memory
   for the common case of direct index into the forwarding table.  If we
   used 2 bits to encode all three relators, then vertical and horizon-
   tal would each get only 1/4 of the available code space.  The reason
   we five bits rather than, say, 4 or 6, is that a 5 bit relator allows
   48 bit numbers to be encoded in 4 16-bit FTIFs (rather than 5 FTIFs
   as would be the case with a 6 bit relator), while still allowing 64
   bit numbers to be encoded in 6 FTIFs (as would also be the case with
   a 4 bit relator).

   Any Pip Address number is limited in size to 64 bits.  This allows a
   Pip ID to be used as a Pip Address number if desired.  When a single
   64-bit Pip Address number is notated, it consists of 6 FTIFs.  The
   first five have 5-bit extension relators.  The sixth has the "true"
   relator, which may be vertical or horizontal, depending on the con-
   text of the number.



2.4.  Assignment of Pip Addresses


   The root PAAA assigns top-level Pip Address numbers to two types of
   entities--providers and private networks.  (Note that in this paper,
   a "private network" is often referred to as a "subscriber network" to
   indicate its role as a subscriber of network services from a pro-
   vider.) Pip Addresses with a provider at the top-level are called
   provider-rooted Pip Addresses.  Pip Addresses with a private network
   at the top-level are called private-rooted Pip Addresses.

   The purpose of assigning numbers to providers is to allow good scal-
   ing characteristics at the top level of routing (because only routes
   to top level providers need be calculated), and to allow for policy
   routing, particularly provider selection.

   The purpose of assigning numbers to private networks is to give the
   systems in the private network globally unique Pip Addresses that are
   not dependent on the private network's service provider.  The top-
   level private network numbers are not advertised outside of the
   private network, and except for intra-private network communications,
   and even then only rarely, never appear in Pip headers.  Top-level
   private network numbers are primarily used to allow hosts to deter-
   mine when another host is in the same private network [9].



Pip WG, Expires December 1993                                   [Page 5]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   A Pip Address consists of zero or more Pip Address numbers with hor-
   izontal relators, followed by one or more Pip Address numbers with
   vertical relators, and ending with zero or one Pip Address numbers
   with a horizontal relator.

   The zero or more initial horizontal numbers represent a "route frag-
   ment".  Horizontal numbers are used when 1) the "top" of a Pip
   Address (the first vertical number, representing a provider) is not
   advertised globally, and so another provider that is must be
   prepended to the Pip Address, or 2) the top of the Pip Address is
   advertised globally, but an adjacent provider represents a meaningful
   policy choice.  (The top-level number of a private-rooted Pip Address
   always has a vertical relator.)

   For example, consider the following topology:

           other                  other
             big---BP1------BP2---big
       providers    \       /     providers
                     \     /
                      \   /
                       LAP     (local access provider)
                        |
                        |
                   +---------------------+
                   |    |                |  Sub1
                   |   Area1----Area2    |  (subscriber network)
                   |                     |
                   +---------------------+

   Here we have a subscriber network (Sub1) connected to a local access
   provider (LAP), which is in turn connected to two Big Providers (BP1
   and BP2).  Because LAP is a provider, it has a top-level number.
   But, because LAP is only a local access provider, let's assume that
   it is not advertised outside of BP1 or BP2.  Thus, the Pip Addresses
   of a subscriber host in Area1 are:

         BP1(hor),LAP(ver),Sub1(ver),Area1(hor)
         BP2(hor),LAP(ver),Sub1(ver),Area1(hor)

   Note that Pip Addresses are rooted at providers.  Issues concerning
   provider-rooted addresses are discussed in [2] and [3].  These
   addresses would be advertised by DNS and carried in the FTIF Chain.
   Because BP1 or BP2 is advertised globally, packets from anywhere
   would reach BP1 or BP2.  BP1 and BP2 know how to route to LAP, which



Pip WG, Expires December 1993                                   [Page 6]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   knows how to route to Sub1, and so on.



2.5.  Hierarchy Levels in Pip Addresses

   One reason that forwarding is fast with Pip is that the entire Pip
   Address does not have to be processed upon reception of a Pip packet.
   Rather, a router can just look at the relevant FTIF and forward the
   packet.  To understand the appropriate context in which to interpret
   the FTIF, however, the Routing Context (RC) must be examined.  The
   RC, among other things, contains information about the hierarchy
   level of the FTIF.  This is necessary because it is possible for a
   given FTIF value to exist at any level of the hierarchy, and it is
   possible for a router to be operating at multiple levels of the
   hierarchy.

   Generally speaking, the level sub-field in the Routing Context (RC)
   is 0 for the highest level, and counts up one for each level deeper
   in the hierarchy.  So, the top level of the hierarchy is level 0, the
   next level below that level 1, and so on.  However, level alone is
   not enough to always determine the context of an FTIF.  The following
   paragraphs explain why this is so.

   One of the goals of Pip is to isolate intra-domain (subscriber net-
   work) addressing from inter-domain (provider network) addressing con-
   ventions.  The better we can isolate these two parts of the address,
   the better we can deal with address prefix changes, such as those
   that result from changing providers.  (Note that, in the above exam-
   ple, BP1.LAP.Sub1 and BP2.LAP.Sub1 constitute the provider part of
   the addresses, and Area1 constitutes the subscriber part.)

   One of the techniques used to isolate subscriber and provider address
   parts is to allow the source and destination addresses of intra-
   domain packets (that is, packets between two hosts in the same sub-
   scriber network) to not encode the provider parts at all.  In the
   context of the above example, this means that the FTIF Chain would
   not contain BP1.LAP.Sub1.  Instead, it would contain only the Area1
   part.  By not requiring the provider part of the address to be in
   intra-domain packets, we allow network administrators to assign
   addresses internally without regard to the provider part.  For
   instance, in the subscriber network the administrator should be able
   to assign numbers to Area1 and Area2 without concern for what pro-
   vider prefixes it has or may have in the future.




Pip WG, Expires December 1993                                   [Page 7]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   In order to do this, the administrator must not only be isolated from
   the value of the provider prefix, but also from the number of levels
   in the provider prefix.  But, the level is needed by subscriber
   routers to know how to forward based on examination of a single FTIF.
   Therefore, level alone is not enough to determine the context of an
   FTIF.  To see why this is so, consider the following example:

                ----BP1--------BP2----
                     |          |
                     |          |
                +---------------------+
                |    |          |     |  Sub1
                |   Area1--R1--Area2  |  (subscriber network)
                |           |   |     |
                |          subArea2   |
                |                     |
                +---------------------+

   Here we have a subscriber network (Sub1) attached to two providers
   (BP1 and BP2) at two internal areas (Area1 and Area2 respectively).
   Area2 has a another layer of hierarchy below it (subArea2).  Attached
   to Area1, Area2, and subArea2 is a router R1.  Assume that the prefix
   given to Sub1 from BP1 is 1-2-3, and the prefix given to Sub2 from
   BP2 is 2-3.  In other words, the top-level number of BP1 is 1 and the
   top-level number given to BP2 is 2.  Both BP1 and BP2 have assigned
   the number 3 to Sub1.  However, BP1 has an internal level of hierar-
   chy whereas BP2 does not.  Thus, BP1's prefix has three numbers while
   BP2's prefix has only two.

   Assume further that Area1 is assigned the number 2, Area2 is assigned
   the number 3, and subArea2 is assigned the number 2.  Thus, the Pip
   Addresses for hosts in Area1 are:
      1-2-3-2
      2-3-2
   and the Pip Addresses for hosts in subArea2 are:
      1-2-3-3-2
      2-3-3-2

   (Note that these Pip Addresses are not notated properly.  For the
   sake of simplicity, the relator bits are not shown in this example.)

   Now, assume that we try to use level alone to indicate the appropri-
   ate hierarchy level in the RC field.  Assume that router R1 receives
   a packet with level=3 and FTIF=2 (where level=0 is the top level).
   Router R1 cannot determine if this packet is for something in Area1



Pip WG, Expires December 1993                                   [Page 8]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   (1-2-3-2), or subArea2 (2-3-3-2).  Both can have FTIF=2 at level=3,
   depending on which provider address is used.  Note that if the router
   parses the address from the top level down, it could resolve the
   ambiguity.  However, this both results in a slower lookup, and weak-
   ens the isolation between provider and subscriber addressing (even
   internal packets would have to carry full addresses).

   To fix this ambiguity, and still allow for provider and subscriber
   address isolation, we introduce a second subfield into the RC, the
   metalevel field.  Whereas there is a level boundary at every level of
   the hierarchy, there is a metalevel boundary only at those hierarchy
   boundaries where there is a reasonable probability that the hierarchy
   element will have multiple parents.  This will normally be the case
   at significant administrative boundaries.  (Note that horizontal
   administrative boundaries do not represent metalevel boundaries.
   Metalevel boundaries, like level boundaries, indicate different
   hierarchical levels.)

   The most significant metalevel boundary is that between provider and
   subscriber.  Every provider/subscriber boundary must also be a
   metalevel boundary.  There may be metalevel boundaries at lower lev-
   els in the hierarchy.  There may not be metalevel boundaries above
   the provider/subscriber metalevel boundary.

   Metalevel numbering in the RC is similar to level numbering it that
   the highest metalevel is metalevel=0, the next lower metalevel boun-
   dary is metalevel=1, and so on.  Level numbering starts over again at
   0 at each metalevel boundary.  Thus, the top-level of the hierarchy
   (the level at which the root PAAA assigns Pip numbers) is
   metalevel=0, level=0.  The next level down (if it is not at the
   provider/subscriber boundary) is metalevel=0, level=1.  This level
   could, for instance, be a hierarchy level within the provider to
   allow for better scaling in the provider network.  This numbering
   continues for all additional levels above the provider/subscriber
   boundary (that is, metalevel=0, level=2; metalevel=0, level=3, and so
   on).

   At the provider/subscriber boundary, the metalevel is incremented and
   the level reset to 0.  Thus, the level just below the
   provider/subscriber boundary is metalevel=1, level=0.  The next level
   down is metalevel=1, level=1, and so on.  Thus, a packet between two
   hosts in the same subscriber network is transmitted at metalevel=1,
   level=0, regardless of the provider prefixes owned by those two
   hosts.  This allows "hard-coded" configuration of Pip Addresses for
   intra-subscriber destinations.  (By hard-coded, I mean static



Pip WG, Expires December 1993                                   [Page 9]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   configuration of a Pip Address in a computer such that the Pip
   Address is not subject to auto-configuration protocols.  An example
   of this is to put a Pip Address in an ASCII configuration file used
   by an application.) It also allows a private network to operate
   without connecting to any providers at all.  When such a private net-
   work connects to a provider, it can then obtain one or more provider
   prefixes.

   Note that it is not a good idea to "hard-code" Pip Addresses with the
   private-rooted address prefix, because even these prefixes are sub-
   ject to change, for instance when two private networks merge.



2.6.  Pip Address Notation

   This section describes how to notate a Pip Address (for instance, in
   an ASCII file).  There is only one way to notate a Pip Address.  Pip
   Address notation closely resembles the encoding of a Pip Address in a
   Pip header.

   The Pip Address is notated as a series of hex numbers separated by
   commas (",") and dots (".").  Each hex number can be between one and
   four digits in length.  Up to four digits are needed to encode a 16-
   bit FTIF.  The relators, including the extension relator, are
   included in the hex number.

   When notating a Pip Address, a comma is used at address positions
   where a metalevel boundary exists.  A dot is used otherwise.

   When notating a Pip Address, the left-most (high-order, or higher-
   in-the-hierarchy) hex number must be at a metalevel boundary, and
   must be a level=0 Pip Address number.  Leading commas are used to
   indicate the metalevel boundary of the Pip Address.  A Pip Address
   notated from the root of the Pip Address hierarchy (metalevel=0) has
   no leading commas.  A Pip Address notated from the top of the private
   network portion of the Pip Address hierarchy (metalevel=1) has a sin-
   gle leading comma.  A Pip Address rooted at metalevel=2 has two lead-
   ing commas, and a Pip Address rooted at metalevel=3 has three leading
   commas.  The maximum number of metalevels is four (encoded as two
   bits in the RC).

   The following network is used to illustrate Pip Address notation.
   BP1 and BP2 are big providers that are advertised globally by the
   routing protocol.  LAP is a local access provider that is not



Pip WG, Expires December 1993                                  [Page 10]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   advertised globally.  Sub1 is the subscriber network.  Area1 and
   Area2 are areas inside the subscriber network.  subArea2 is an area
   within Area2.  There is a single metalevel boundary--between the sub-
   scriber network Sub1 and the providers, LAP and BP2.

          ---BP1----LAP--------BP2----
                     |          |
                     |          |
                +---------------------+
                |    |          |     |  Sub1
                |   Area1------Area2  |  (subscriber network)
                |               |     |
                |           subArea2  |
                |                     |
                +---------------------+

   Assume the following Pip Address number assignments:

      network            assignment
      component          # ( << 1)       notes
      ---------          ----------      -----
      BP1                23 (46)         top-level number
      BP2                9a (134)        top-level number
      LAP                1b9 (372)       top-level number
      Sub1               493aa (92754)   top-level number
      LAP/Sub1           43 (86)         assigned to Sub1 by LAP PAAA
      BP2/Sub1           11a (234)       assigned to Sub1 by BP2 PAAA
      Area1              b3 (166)        assigned by Sub1 PAAA
      Area2              71 (e2)         assigned by Sub1 PAAA
      Area2/subArea2     14 (28)         assigned by Area2 PAAA

   Note that none of the numbers shown above include the relator.  The
   number in parenthesis is the assigned number left shifted one.  This
   is shown to more clearly indicate the number with the relator
   appended.

   A host in Area1 may have the following four Pip Addresses:

           Pip Address      PAAA Hierarchy
           -----------      --------------
      1.   46.373.87,166    root.BP1.LAP.Sub1,Area1
      2.   135.235,166      root.BP2.Sub1,Area1
      3.   13f.2755,166     root.Sub1,Area1
      4.   ,166             private,Area1




Pip WG, Expires December 1993                                  [Page 11]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   The first two Pip Addresses are provider-rooted.  These would be used
   by hosts in other private networks to reach the host in Area1.  Note
   that the last bit of the first number of Pip Address 1 has a 0 as the
   least significant bit.  This indicates a relator of horizontal.
   Since LAP has a top-level Pip Address number, it is not "under" BP1
   in the address hierarchy.  Never-the-less, BP1 is in the Pip Address
   as part of a route fragment either because LAP isn't advertised glo-
   bally by routing, or because being able to route paths through BP1 is
   important to hosts in Sub1.

   The third Pip Address is private-rooted.  This address would not be
   used by hosts outside of Sub1 to address hosts inside Area1, because
   Sub1 is not advertised globally.  The third Pip Address would, how-
   ever, be advertised by DNS.  This would allow other hosts in Sub1 to
   determine that the Area1 host was in the same private network (and
   thus, no provider prefix is needed to address the packet).

   The fourth Pip Address is not globally unique, and can only be used
   locally.  The leading comma indicates that the top level of this
   address is at metalevel=1.  Thus, if a host creates a Pip header
   using the fourth Pip Address, it would know to set the metalevel sub-
   field in the RC field to 1.  The fourth Pip Address would not be
   advertised in DNS.



2.7.  Router Addressing Conventions

   A router plays several roles.  First, it can of course receive Pip
   packets to be forwarded to another router or a host.  Second, as the
   destination of Pip packets, it can itself be a host.  Third, it can
   be the "target" of a Pip packet that must then be translated into an
   IP packet and forwarded.  We use the term "target" rather than sink
   to indicate that, even though the FTIF Chain is structured to deliver
   the packet to the router, the router is not the ultimate destination
   of the packet.  Fourth, the router can be the end of a tunnel, in
   which case it is the target of a Pip packet that is untunneled and
   forwarded.

   Thus, routers can be the targets of three kinds of packets-- those
   meant for it, those that need to be translated, and those that need
   to be untunneled.  To distinguish between these three types, routers
   must have a different Pip Address for each type.  In its role as a
   host, the router uses the Pip Address of the attached LAN if there is
   one, or simply the destination Pip Address assigned to the router if



Pip WG, Expires December 1993                                  [Page 12]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   there isn't.

   If the router is a target system either as a tunnel endpoint or for
   translation, then it must have distinct Pip Addresses for each of
   these cases.  These Pip Addresses may or may not be interface
   specific, depending on the situation.  Normally these Pip Addresses
   will all be identical except for the lowest FTIF.  The exception to
   this rule is when the router is a border router.

   When a router is a Pip/IP translator, then it is a translator for a
   set of IP destinations.  When a DNS lookup for one of these IP desti-
   nations is made, the Pip Address representing the router's role as a
   translator is returned (along with the router's Pip ID).

   In the case where the router is a tunnel endpoint, the Pip Address
   assigned for the purpose must be advertised to the router's peer tun-
   nel endpoints.  When the router is the entry point of a tunnel, it
   puts this Pip Address in the source address location of the FTIF
   Chain of the Transit Part that it creates for the tunnel.

   When a Pip router inside a tunnel cannot deliver the packet to the
   tunnel exit router, it sends a PCMP error message back to either the
   source host or the tunnel entry router, depending on the cir-
   cumstances [5].  In the former case, the returned Pip packet is tar-
   geted to the original tunnel entry router, which becomes the tunnel
   exit router.  In this case, the router untunnels the packet and for-
   wards it on.  In the latter case, the tunnel entry router becomes the
   actual destination of the PCMP message.

   Because the tunnel endpoint router must be able to distinguish
   between being the tunnel exit system and being the recipient of the
   returned PCMP message, there must be a means by which the router that
   initiated the PCMP message can indicate the distinction.  To do this,
   we use the following convention.

   When a tunnel endpoint is to untunnel a packet and forward it on, the
   relator of the last FTIF indicates horizontal.  When a tunnel end-
   point is the recipient of a packet (that uses the router's tunnel Pip
   Address), the relator of the last FTIF indicates vertical.



2.8.  Host Addressing Conventions

   Host Pip Addresses may be either LAN-based or host-based.  In the



Pip WG, Expires December 1993                                  [Page 13]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   former case, the host uses as its Pip Address the Pip Address of its
   attached LAN.  (If there are multiple attached LANs, the host has
   multiple Pip Addresses.) The host's Pip ID is used to deliver the
   packet from a router (or another host) on the LAN to the host.  That
   is, the Pip ID in the Dest ID field of the Pip header is examined to
   determine the appropriate LAN address to forward the packet to.  If
   necessary, the Pip ID is also used to ARP for the destination host's
   LAN address.

   In the latter case (host-based), the FTIF Chain is sufficient to
   deliver the packet to the destination host.  If the host is using
   host-based addressing, but is also attached to a LAN, then the host
   could have a Pip Address prefix that matches the LAN Pip Address.
   This address prefix would be followed by one or more FTIFs.

   In order for a router to distinguish between LAN-based and host-based
   Pip Addresses for hosts on its attached LAN, we use the following
   convention.  If the host is using LAN-based addressing, then the FTIF
   representing the LAN (in this case, the last FTIF) has a horizontal
   relator.  If the host is using host-based addressing, then the FTIF
   representing the LAN (in this case, not the last FTIF) has a vertical
   relator.



2.9.  Reversing an FTIF Chain with Pip Addresses

   There are two cases where a Pip system may want to "reverse" an FTIF
   Chain with Pip Address.  Reversing an FTIF Chain is the process of
   creating a new FTIF Chain that allows the packet to get back to the
   source host.  The first case is that of a destination host returning
   a packet to the source host.  The second case is that of a router
   returning a PCMP message back to the source host or a tunnel entry
   system.

   In the following descriptions, we assume that an FTIF Chain of the
   following form is received:











Pip WG, Expires December 1993                                  [Page 14]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993



      V1 V2...Vi H1...Hj Hj+1...Hj+k Hj+k+1...Hj+k+m V1 V2... Vn
     |                  |           |                           |
     |                  |  policy   |                           |
     | source address   |  route    |      dest address         |

        i >= 0, j >= 1, k >= 0, m >= 0, n >= 1


   That is, the FTIF Chain starts with a source address that contains
   zero or more vertical FTIFs followed by at least one horizontal FTIF.
   This is followed by 0 or more horizontal FTIFs that make up the "pol-
   icy route".  This is in turn followed by the destination address,
   made up of 0 or more horizontal FTIFs followed by one or more verti-
   cal FTIFs.  (There is one exception to the dest address shown here,
   which is that in the case of returning a Pip packet to a tunnel entry
   point, the final FTIF may be horizontal.)



2.9.1.  Host FTIF Chain Reversal

   To reverse an FTIF Chain, the host first extracts the destination Pip
   Address from the received FTIF Chain.  The destination Pip Address
   can be determined by matching the trailing FTIFs against those of the
   host's own addresses.  That is, FTIF Vn is compared against the
   host's lowest level address component, Vn-1 against the host's next
   lowest level address component, and so on.

   Note that the destination Pip Address may be a partial address, com-
   ing under a metalevel boundary.  In this case, there would be no hor-
   izontal components in the destination address of the received FTIF
   Chain.  The destination Pip Address of the received FTIF Chain must
   be one of the Pip Addresses of the host.  This becomes the source Pip
   Address of the returned (reversed) Pip packet.

   The host then takes the remainder of the FTIF Chain and treats it as
   the destination Pip Address of the returned Pip packet.  Note that
   the remainder of the FTIF Chain may in fact be more than the received
   source Pip Address, for instance because of the inclusion of a policy
   route in the FTIF Chain.  From the perspective of the reversing host,
   however, this does not change things.

   At this point, the host has the source and "destination" Pip
   Addresses for the return Pip packet.  The host sets the Active FTIF



Pip WG, Expires December 1993                                  [Page 15]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   field, and the level, metalevel, and exit routing type subfields of
   the RC, according to the procedures described in [9].



2.9.2.  Router FTIF Chain Reversal

   To reverse an FTIF Chain, a router must first decide how much of the
   received source Pip Address is needed to return the packet.  For
   instance, if the packet is destined to an inter-domain location, but
   has not yet left the private network, then only the private network
   part of the address (metalevel=1 cluster) is needed.

   There are three cases to handle;

   1.   The packet is in the source's metalevel>0 cluster,

   2.   The packet is at metalevel=0,

   3.   The packet is in the destination's metalevel>0 cluster

   The first case exists when the prefix of the source address in the
   received FTIF Chain matches one of those of the router's.  Since the
   received FTIF Chain does not explicitly indicate which FTIFs consti-
   tute the source address, the router must compare prefixes by first
   finding the first horizontal FTIF of the FTIF Chain (H1).  If this
   matches the lowest horizontal FTIF in one or more of the router's Pip
   Addresses (that is, the FTIF in the router's Pip Address correspond-
   ing to H1), then the router compares the FTIFs in its Pip Address
   corresponding to H2 through Hj against H2 through Hj in the received
   FTIF Chain, and the FTIFs in its Pip Address corresponding to Vi,
   Vi-1, and so on down to the metalevel boundary, against those in the
   received FTIF Chain.

   If all of these FTIFs match, then the router is in the same
   metalevel>0 cluster as the source, and does not need to include the
   common prefix in the return packet.  That is, the series of FTIFs
   starting from the first FTIF and going up to the FTIF previous to the
   common prefix is considered to be the "source address" of the
   received FTIF Chain.

   If any of these FTIFs don't match, then the router considers the
   "potential source address" of the received FTIF Chain to be the
   series of FTIFs starting from the first FTIF and going up to the FTIF
   previous to the Active FTIF.  If one of the horizontal FTIFs of the



Pip WG, Expires December 1993                                  [Page 16]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   potential source address matches that of the router's provider net-
   work, then that FTIF and all subsequent FTIFs are stripped from the
   potential source address, and what remains is considered to be the
   "source address" of the received FTIF.  (Note that this may not be
   the complete source address of the source host, but it is sufficient
   to route the packet back to the source host.)

   The series of FTIFs that are considered to be the source address of
   the received FTIF Chain are reversed and used as the destination
   address of the FTIF Chain of the return packet.  The router then
   chooses one of its own Pip Addresses to be the source address in the
   return packet.  Then the router creates an FTIF Chain, Active FTIF
   field, and level, metalevel, and exit routing type subfields of the
   RC according to the algorithm for host creation of a Pip header
   described above.



2.9.3.  Reversal of Multiple FTIF Chains (Tunneling Case)

   If there are multiple FTIF Chains in the received Pip packet, then
   all of them must be reversed in the return Pip packet.  Each indivi-
   dual FTIF Chain is reversed according to the rules stated above.  The
   order of encapsulation in the returned packet is the same as the
   received packet.



3.  CBT Style Multicast Addresses


   When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 10,
   the FTIF and Dest ID indicate CBT (Core Based Tree) style multicast.
   The remainder of the bits are defined as follows:

      bits       meaning
      ----       -------
      0,1        CBT Multicast (= 10)
      2,3        level
      4,5        metalevel
      6          exit routing type
      7          on-tree bit
      8,9        scoping

   With CBT (Core-based Tree) multicast, there is a single multicast



Pip WG, Expires December 1993                                  [Page 17]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   tree connecting the members (recipients) of the multicast group (as
   opposed to Class-D style multicast, where there is a tree per
   source).  The tree emanates from a single "core" router.  To transmit
   to the group, a packet is routed towards the core using unicast rout-
   ing.  Once the packet reaches a router on the tree, it is multicast
   using a group ID.

   The FTIF Chain for CBT multicast contains the (unicast) Hierarchical
   Pip Address of the core router and the Pip Address of the source.
   The Dest ID field contains the group ID.

   A Pip CBT packet, then, has two phases of forwarding, a unicast phase
   and a multicast phase.  The "on-tree" bit of the RC indicates which
   phase the packet is in.  While in the unicast phase, the on-tree bit
   is set to 0, and the packet is forwarded as for Pip Addresses as
   described above.  During this phase, the scoping bits are ignored.
   If during this phase the packet cannot be delivered, the PCMP Packet
   Not Delivered (PND) message is sent as though the original packet
   were a Pip Address.

   Once the packet reaches the multicast tree, it switches to multicast
   routing by changing the on-tree bit to 1 and using the Dest ID group
   address for forwarding.  During this phase, bits 2-6 of the RC are
   ignored.  PCMP messages are not sent in response to a packet in the
   on-tree phase of CBT multicast.

   The CBT specification [7] describes the forwarding of CBT packets for
   IP.  For use with Pip, the CBT specification is used as is, with the
   following exceptions:

   1.   The source and destination Pip Addresses in the FTIF Chain take
        on the roles of the source and destination IP address, with the
        proviso that the packet is forwarded according to Pip Address
        forwarding rules.

   2.   The on-tree bit in the RC takes on the role of the on-tree bit
        in the CBT IP option.

   3.   The Dest ID of the Pip header takes on the role of the group ID
        in the CBT IP option.

   4.   The scoping bits in the RC take on the role of the scoping bits
        in the CBT IP option.





Pip WG, Expires December 1993                                  [Page 18]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


4.  Class D Style Multicast Addresses


   When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 01,
   the FTIF and Dest ID indicate Class D style multicast.  The remainder
   of the RC is defined as:

      bits       meaning
      ----       -------
      0,1        Class D Style Multicast (= 01)
      2,3        scoping

   By "class D" style multicast, we mean multicast using the algorithms
   developed for use with Class D addresses in IP (class D addresses are
   not used per se).  This style of routing uses both source and desti-
   nation information to route the packet (source host address and des-
   tination multicast group).

   For Pip, the FTIF Chain holds the source Pip Address, in order of
   most significant hierarchy level first.  The reason for putting the
   source Pip Address rather than the Source ID in the FTIF Chain is
   that use of the source Pip Address allows the multicast routing to
   take advantage of the hierarchical source address, as is being done
   with IP.

   The Dest ID field holds the multicast group.  All of the existing IP
   Class D multicast addresses are used with Pip by virtue of the "local
   IP" Pip ID address space [8].  These addresses are necessary when a
   multicast group is partly Pip and partly IP.  For a pure Pip multi-
   cast group, either an IP Class D multicast address can be used, or
   another (non-IP) Pip address.

   To forward a Class D multicast packet, a router first examines the
   FTIF Chain starting from the beginning (Active FTIF field = 1).
   FTIFs are examined in order until the source of the packet is unambi-
   guously determined.  Note that the FTIF Chain only identifies the
   source subnet, not the source host.  This is adequate to describe the
   multicast tree, since all trees coming from hosts on the same subnet
   will be identical.

   Bits 2 and 3 of the RC are the scoping bits.  The use of these bits
   are for further study.  As of this writing, there is no specification
   for a routing algorithm to create Class D style multicast trees with
   Pip.  It is expected that such a specification will be written in the
   future.



Pip WG, Expires December 1993                                  [Page 19]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


4.1.  Nearcast Addressing

   Nearcast addressing is a new form of addressing that, for now, is
   peculiar to Pip.  Nearcast addressing causes a packet to be routed to
   one (the "nearest") of a group of systems.  Thus, nearcast is similar
   to multicast in that a nearcast address identifies a group of sys-
   tems.  Nearcast is similar to unicast, however, in that it only
   delivers one packet.  To do nearcast addressing, the (other unicast)
   routing algorithm must maintain a route to the nearest member of each
   nearcast group.

   Nearcast is particularly useful for discovery applications.  It
   allows one of a class of systems to be found without prior knowledge
   of that system's unicast address.  Pip uses nearcast to help auto-
   configure Pip hosts.

   When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 11,
   the FTIF and Dest ID indicate Nearcast addressing.  The remainder of
   the RC is defined as:

      bits       meaning
      ----       -------
      0,1        Nearcast Address (= 11)
      2,3        level
      4,5        metalevel
      6          exit routing type
      7          nearcast active
      8,9        scoping

   With nearcast routing, the packet is unicast, but to the nearest of a
   group of destinations.  This type of routing is used by Pip for auto-
   configuration.  Other applications, such as discovery protocols, may
   also use nearcast routing.

   Like CBT, Pip nearcast has two phases of operation, in this case the
   unicast phase and the nearcast phase.  The unicast phase is for the
   purpose of getting the packet into a certain vicinity.  The nearcast
   phase is to forward the packet to the nearest of a group of destina-
   tions in that vicinity.

   Thus, the RC has both unicast and nearcast information in it.  During
   the unicast phase, the nearcast active bit is set to 0, and the
   packet is forwarded according to the rules of Pip Addressing.  The
   scoping bits are ignored.




Pip WG, Expires December 1993                                  [Page 20]


INTERNET-DRAFT            Pip Addr Conventions                 June 1993


   The switch from the unicast phase to the nearcast phase is triggered
   by the presence of an FTIF of value 1 in the FTIF Chain.  When this
   FTIF is reached, the nearcast active bit is set to 1, the scoping
   bits take effect, and bits 2 through 6 are ignored.  When in the
   nearcast phase, forwarding is based on the Dest ID field.




   References

   [1]   Francis, "Pip Header Processing", Internet-Draft
   [2]   Francis, "Pip Near-term Architecture", Internet-Draft
   [3]   Francis, "On the Assignment of Provider-rooted Addresses",
         Internet-Draft
   [4]   Thomson, Francis, "Use of DNS with Pip", Internet-Draft
   [5]   Francis, Govindan, "PCMP: Pip Control Message Protocol",
         Internet-Draft
   [6]   Pip ARP (to be completed)
   [7]   Ballardie, Francis, Crowcroft, "Core Based Trees (CBT), An
         Architecture for Scalable Inter-Domain Multicast Routing",
         Internet-draft.
   [8]   Francis, "Pip Identifiers", Internet-Draft
   [9]   Francis, "Pip Host Operation", Internet-Draft
























Pip WG, Expires December 1993                                  [Page 21]