[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
P2PSIP                                                      M. Zangrilli
Internet-Draft                                                  D. Bryan
Intended status: Standards Track                  SIPeerior Technologies
Expires: August 29, 2007                               February 25, 2007


            A Bamboo-based DHT for Resource Lookup in P2PSIP
                draft-zangrilli-p2psip-dsip-dhtbamboo-00

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   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
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on August 29, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Abstract

   This document describes how a structured peer-to-peer algorithm is
   used for resource lookup by a P2PSIP Peer Protocol.  Specifically,
   this work describes how to integrate a DHT based on Bamboo with dSIP,
   a proposed P2PSIP Peer Protocol.  This document extends the dSIP
   draft to provide one possible implementation of a pluggable DHT
   algorithm.

   This is early work to demonstrate how alternative DHT algorithms can



Zangrilli & Bryan        Expires August 29, 2007                [Page 1]


Internet-Draft                   P2PSIP                    February 2007


   be plugged into the dSIP protocol.  Where appropriate, we compare the
   Bamboo DHT implementation to the Chord DHT implementation.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
     2.1.  Definitions  . . . . . . . . . . . . . . . . . . . . . . .  3
   3.  Background . . . . . . . . . . . . . . . . . . . . . . . . . .  4
     3.1.  Bamboo . . . . . . . . . . . . . . . . . . . . . . . . . .  4
   4.  Routing Table and Connection Table . . . . . . . . . . . . . .  4
     4.1.  Leaf Set . . . . . . . . . . . . . . . . . . . . . . . . .  5
     4.2.  Bamboo Routing Table . . . . . . . . . . . . . . . . . . .  5
     4.3.  Message Routing  . . . . . . . . . . . . . . . . . . . . .  5
   5.  Message Syntax . . . . . . . . . . . . . . . . . . . . . . . .  6
     5.1.  The DHT-PeerID Header  . . . . . . . . . . . . . . . . . .  6
       5.1.1.  Hash Algorithms  . . . . . . . . . . . . . . . . . . .  6
       5.1.2.  DHT Name Parameter . . . . . . . . . . . . . . . . . .  6
     5.2.  The DHT-Link Header  . . . . . . . . . . . . . . . . . . .  6
       5.2.1.  The linktype and depth values  . . . . . . . . . . . .  7
   6.  Bamboo Overlay Algorithm . . . . . . . . . . . . . . . . . . .  7
     6.1.  Bamboo Routing Table and Leaf set  . . . . . . . . . . . .  7
     6.2.  Starting a New Overlay . . . . . . . . . . . . . . . . . .  8
     6.3.  Peer Admission . . . . . . . . . . . . . . . . . . . . . .  8
       6.3.1.  Constructing a Peer Registration . . . . . . . . . . .  9
       6.3.2.  Processing and Routing the Peer Registration . . . . .  9
       6.3.3.  Admitting the Joining Peer . . . . . . . . . . . . . .  9
     6.4.  Bamboo Query Processing  . . . . . . . . . . . . . . . . . 10
     6.5.  Graceful Leaving . . . . . . . . . . . . . . . . . . . . . 11
     6.6.  DHT Maintenance  . . . . . . . . . . . . . . . . . . . . . 11
       6.6.1.  leaf set maintenance . . . . . . . . . . . . . . . . . 11
       6.6.2.  Bamboo routing table maintenance . . . . . . . . . . . 11
     6.7.  Peer Failure . . . . . . . . . . . . . . . . . . . . . . . 12
     6.8.  Resource Replicas  . . . . . . . . . . . . . . . . . . . . 12
   7.  Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 12
   9.  Open Issues  . . . . . . . . . . . . . . . . . . . . . . . . . 12
   10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 13
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 13
     11.2. Informative References . . . . . . . . . . . . . . . . . . 14
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14
   Intellectual Property and Copyright Statements . . . . . . . . . . 15







Zangrilli & Bryan        Expires August 29, 2007                [Page 2]


Internet-Draft                   P2PSIP                    February 2007


1.  Introduction


2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].

   Terminology defined in RFC 3261 [RFC3261] is used without definition.

   We use the terminology and definitions from the dSIP: A P2P Approach
   to SIP Registration and Resource Location [I-D.bryan-p2psip-dsip] and
   the Concepts and Terminology for Peer to Peer SIP
   [I-D.willis-p2psip-concepts] drafts extensively in this document.
   Other terms relating to P2P or new to this document are defined when
   used and are also defined in Definitions (Section 2.1).  We suggest
   reviewing these drafts and the Definitions (Section 2.1) section
   before reading the remainder of this document..

   In many places in this document, 10 hexadecimal digit values are used
   in examples as SHA-1 hashes.  In reality, these hashes are 40 digit.
   They are shortened in this document for clarity only.

2.1.  Definitions

   Please also see the dSIP: A P2P Approach to SIP Registration and
   Resource Location [I-D.bryan-p2psip-dsip] draft and the P2PSIP
   concepts and terminology [I-D.willis-p2psip-concepts] draft for
   additional terminology.  We do not redefine terms from that draft
   here.
   Bamboo:  A particular algorithm/approach to implementing a DHT that
      is described by Rhea et al.  [Bamboo] Bamboo uses a circular
      arrangement for the namespace and stores resources with
      Resource-ID k at the peer with Peer-ID that is numerically closest
      to k.
   Bamboo routing table:  Tree-based structure containing peer
      information (Peer-ID and location).  Each row of the table, l,
      contains peers whose Peer-IDs match its own Peer-ID in exactly l
      digits.  The columns in the row represent the values for the (l+1)
      digit.  A peer that has the same digit prefix (l) as its own
      Peer-ID and whose (l+1) digit is i, will be stored at row l,
      column i in its routing table.
   Chord:  A particular algorithm/approach to implementing a DHT,
      described by Stoica et al.  [Chord].  Uses a circular arrangement
      for the namespace.





Zangrilli & Bryan        Expires August 29, 2007                [Page 3]


Internet-Draft                   P2PSIP                    February 2007


   leaf set:  A set of peers immediately preceding and following the
      peer in the circular namespace.
   Predecessor Peer:  Refers to a peer directly before a particular peer
      in the address space.  This does not mean that the predecessor's
      Peer-ID is one less than the peer, it simply means that there are
      no other peers in the namespace between the peer and the
      predecessor peer.
   Successor Peer:  Refers to a peer directly after a particular peer in
      the address space.  This does not mean that the successor peer's
      Peer-ID is one more that that peer, rather there are no other
      peers in the namespace between that peer and the successor peer.
      Note that the first peer in a finger table is typically also the
      first successor peer.


3.  Background

3.1.  Bamboo

   Bamboo [Bamboo] is one particular DHT algorithm that, like the Chord
   DHT [Chord], conceptualizes the namespace as a circle, meaning the
   peer with Peer-ID is located next to the peer with largest possible
   Peer-ID in the namespace.  Unlike Chord, Bamboo uses prefix routing
   to converge on the peer responsible for the search key.  In Bamboo
   resources are stored by the peer with the closest numerical Peer-ID
   to their Resource-ID.  Note this differs from the Chord [Chord]
   approach where resources are stored by the first peer with Peer-ID
   equal or greater than the the Resource-ID.  Each Resource-ID is the
   responsibility of some peer in the overlay, though the responsible
   peer may change as peers enter and leave the overlay.


4.  Routing Table and Connection Table

   Each peer keeps information about how to contact some number of other
   peers in the overlay.  In terms of the overlay network, these are the
   neighbors of the peer, since they are reachable in one hop.  In
   Bamboo, the peer keep tracks of a leaf set containing one or more of
   its immediate predecessor peers, as well as one or more successor
   peers.  The peer also keeps a table of information about other
   neighbors called a Bamboo routing table.

   Note we use routing table as defined in the dSIP draft and Bamboo
   routing table as the specific structure of peers stored for routing
   use in the Bamboo DHT.  The routing table, as defined by dSIP, is a
   union of the leaf set and the Bamboo routing table.





Zangrilli & Bryan        Expires August 29, 2007                [Page 4]


Internet-Draft                   P2PSIP                    February 2007


4.1.  Leaf Set

   Each peer maintains a leaf set, or set of peers immediately preceding
   and following the peer in the circular namespace.  Half of the leaf
   set contains the peers with numerically closest Peer-ID that are
   smaller than this peer's own Peer-ID.  The other half of the leaf set
   contains the peers with numerically closest Peer-IDs that are larger
   than this peer-s own Peer-ID.

   The leaf set is a similar concept to Chord's predecessor and
   successor peers.  See Section Definitions (Section 2.1).  The peers
   in the leaf set may be called successors or predecessor in the
   remainder of this document.

4.2.  Bamboo Routing Table

   Each peer also maintains a Bamboo routing table.  Bamboo routing
   tables treat each identifier as a sequence of digits of base 2^b.
   Each row l of the Bamboo routing table stores peers with Peer-IDs
   that share the first l digits with its own peer-ID.  The columns in
   each row represent the different values possible for the l+1st digit.

   More than one peer may be an appropriate fit for each Bamboo routing
   table entry, and entries may be chosen based on network proximity or
   other factors.  The choice of which peer to use for each entry is
   left up to each implementation.  As an example, the peer with the
   smallest latency will fill the routing table spot whenever possible.

4.3.  Message Routing

   Bamboo uses prefix routing.  Messages are routed such that each hop
   will results in a peer that either shares a larger prefix with the ID
   being searched for or shares the same length prefix as the previous
   hop's Peer-ID, but the new peer's Peer-ID is numerically closer to
   the ID than the previous hop's Peer-ID.

   To route a message to a particular ID, the peer first looks to see
   any of the peers in its leaf set are responsible for the ID.  If the
   ID lies within the leaf set, the message is routed to the appropriate
   leaf set peer.  If the ID is not within the leaf set, the searching
   peer computes the length l of the longest matching prefix between the
   search ID and it's own peer-ID.  The peer then looks in its Bamboo
   routing table at row l.  If there is an entry in that row
   corresponding to the l length prefix of the ID being searched for,
   then the message is forwarded on to that peer.  If that Bamboo
   routing table entry is empty, the message is routed to the peer in
   its leaf set with the peer-ID that is numerically closest to the ID
   being searched for.



Zangrilli & Bryan        Expires August 29, 2007                [Page 5]


Internet-Draft                   P2PSIP                    February 2007


5.  Message Syntax

5.1.  The DHT-PeerID Header

   The routing algorithms used to implement the overlay is specified in
   the dht-param parameter in the DHT-PeerID header.  The format of the
   DHT-PeerID header is defined in the dSIP [I-D.bryan-p2psip-dsip]
   draft.

5.1.1.  Hash Algorithms

   Implementations MUST support the SHA-1 [RFC3174] algorithm, which
   produces a 160 bit hash value.  An implementation MAY rely on a
   secret initialization vector, key, or other shared secret to use the
   identifier as an HMAC, from from RFC 2104 [RFC2104] such that no peer
   may join the overlay without knowledge of the shared secret, however
   this technique by itself does not protect the overlay against replay
   attacks.  Security Extensions to dSIP
   [I-D.lowekamp-p2psip-dsip-security] provides information on how to
   protect against replay attacks and hash algorithms defined in that
   draft MAY be used in Chord implementations.

5.1.2.  DHT Name Parameter

   For this protocol, the dht-param token MUST be set to "Bamboo1.0".

   A peer receiving a message with a dht-param other than "Bamboo1.0"
   SHOULD reject the message and return a 488 Not Acceptable Here
   response message.

   Examples:
   A peer with an SHA-1 hashed Peer-ID of a04d371e24 on IP 192.0.2.1.
   We include the required algorithm, and overlay as well as the
   optional expires header parameter.


   DHT-PeerID: <sip:peer@192.0.2.1;peer-ID=a04d371e24>;algorithm=sha1;
   dht=Bamboo1.0;overlay=chat;expires=600

5.2.  The DHT-Link Header

   The DHT-Link header is used to transfer information about where in
   the DHT other peers are located.  In particular, it is used by peers
   to pass information about the leaf set peers and Bamboo routing table
   information stored by a peer.

   The linktype and depth values are dependent on the DHT routing
   algorithm employed by the peer.  We define a linktype-token and



Zangrilli & Bryan        Expires August 29, 2007                [Page 6]


Internet-Draft                   P2PSIP                    February 2007


   depth-token in the DHT-Link Header to be used by peers implementing
   the Bamboo1.0 DHT algorithm.

   link-value      = linktype-token depth-token
   linktype-token  = "P" / "S" / "R" / other-token
   depth-token     = 1*DIGIT

   and an example, the header might look like (using a shortened digit
   Peer-ID for clarity):

   DHT-Link: <sip:peer@192.0.2.1;peer-ID=671a65bf22>;link=R1;expires=600

5.2.1.  The linktype and depth values

   The linktype MUST be one of three single characters, "S", "P" or "R".
   "S" MUST be used to indicate that the information provided describes
   a successor, a peer in the leaf set that immediately follows the
   sending peer in the circular namespace.  "P" MUST be used to indicate
   that the information provided describes a peer in the leaf set that
   immediately precedes the sending peer in the circular namespace.  "R"
   MUST indicate that the information describes a peer in the sending
   peer's routing table.

   The depth MUST be a non-negative integer representing which leaf set
   peer or routing table entry is being described.  For leaf set peers,
   this depth value MUST indicate numeric depth.  In other words, "S1"
   indicates the first succeeding peer in the circular namespace, while
   "P3" would indicate the third preceding peer in the circular
   namespace.  "S0" or "P0" would indicate the sending peer itself.  In
   the case of the routing table entries, the depth MUST indicate the
   level/row of the routing table.  The routing table level is designed
   so that the level represents the number of digits (digit prefix) the
   routing table entry has in common with the sending peer.  For
   example, "R1" would correspond to a routing table entry that shares a
   one-digit prefix with the sending peer, while "R3" would indicate a
   routing table entry that shares a three-digits prefix with the
   sending peer.


6.  Bamboo Overlay Algorithm

6.1.  Bamboo Routing Table and Leaf set

   Bamboo routing tables treat each identifier as a sequence of digits
   of base 2^b.  For a namespace of N, there are log_(2^b)(N) rows in a
   Bamboo routing table and each row should contain 2^b-1 entries.  We
   use "l" to indicate the number of rows.  The row number corresponds
   to the number of digits that match its own identifier ( row 0 would



Zangrilli & Bryan        Expires August 29, 2007                [Page 7]


Internet-Draft                   P2PSIP                    February 2007


   have no matching prefix, row 1 would have peers that have the same
   first digit...).

   In order to be compatible with our hashing and security schemes, we
   use 160 bit identifiers, meaning our namespace N is of size 2^160.
   Additionally, we choose to use hexadecimal values, meaning our b is
   4, since 2^b or 2^4=16.  Solving for the number rows in the Bamboo
   routing table, " l", we have the following.  Note that in our
   notation, log_n means log base n, and lg is assumed to be log base 2,
   or log_2:


   l = log_(2^b) (N)

   Using the property that log_n x = lg n / lg x we have:

   l = [lg N] / [lg 2^b]

   Plugging in and solving we have:

   l = [lg (2^160)] / [lg 16]
   l = 160 / 4
   l = 40

   Leaf sets in Bamboo store peers that immediately precede or follow
   the current peer in the circular namespace.  The leaf set MUST
   contain at least one peer that immediately precedes the current peer
   and one peer that follows the current peer, but it SHOULD contain 2^b
   total peers in the leaf set (half for peers preceding and half for
   peers following the current peer in the namespace).

6.2.  Starting a New Overlay

   A peer starting an overlay for the first time need not do anything
   special in order to construct the overlay.  The peer MUST initialize
   its leaf set and routing table such that all entries are NULL.

6.3.  Peer Admission

   A peer that wishes to join an overlay (called the joining peer),
   constructs a Peer Registration message and sends it to the bootstrap
   peer.  The Peer Registration is routed to the admitting peer, which
   is the peer that is currently responsible for the joining peer's
   portion of the overlay.







Zangrilli & Bryan        Expires August 29, 2007                [Page 8]


Internet-Draft                   P2PSIP                    February 2007


6.3.1.  Constructing a Peer Registration

   To initiate the joining process, the joining peer constructs a Peer
   Registration and sends it to the bootstrap peer.  The joining peer
   MUST construct the Peer Registration according the rules outlined in
   the dSIP [I-D.bryan-p2psip-dsip] draft.  The registering peer MUST
   provide a DHT-PeerID header field in the Peer Registration message.
   It MAY leave the overlay parameter set to "*" for its initial
   registration message, but MUST set this parameter to the name of the
   overlay it is joining as soon as it receives a response from the
   bootstrap peer.  The dht-param parameter in the DHT-PeerID header
   MUST be set to "*" or "Bamboo1.0", as specified in Section DHT Name
   Parameter (Section 5.1.2).

   Assume that a peer running on IP address 192.0.2.2 on port 5060
   attempts to join the network by contacting a bootstrap peer at
   address 192.0.2.129.  Further assume that 192.0.2.2:5060 hashes to
   463ac4b449 under SHA-1 (using a 10 digit hash for example
   simplicity), and that the overlay name is chat.  An example message
   would look like this (neglecting tags):

   REGISTER sip:192.0.2.129 SIP/2.0
   To: <sip:peer@192.0.2.2;peer-ID=463ac4b449>
   From: <sip:peer@192.0.2.2;peer-ID=463ac4b449>
   Contact: <sip:peer@192.0.2.2;peer-ID=463ac4b449>
   Expires: 600
   DHT-PeerID: <sip:peer@192.0.2.2;peer-ID=463ac4b449>;algorithm=sha1;
               dht=Bamboo1.0;overlay=chat;expires=600
   Require: dht
   Supported: dht

6.3.2.  Processing and Routing the Peer Registration

   The Peer Registration is processed and routed according the rules
   outlined in the dSIP [I-D.bryan-p2psip-dsip] draft.

6.3.3.  Admitting the Joining Peer

   The admitting peer recognizes that it is presently responsible for
   this region of the hash space -- that is, it is currently the peer
   storing the information that the joining peer will eventually be
   responsible for.  The admitting peer knows this because the joining
   peer's Peer-ID is numerically closest to its own Peer-ID; the
   admitting peer does not have a Bamboo routing table entry or leaf set
   peer with a longer shared prefix or with a numerically closer Peer-ID
   than its own Peer-ID.  The admitting peer is responsible for helping
   the joining peer become a member of the overlay.




Zangrilli & Bryan        Expires August 29, 2007                [Page 9]


Internet-Draft                   P2PSIP                    February 2007


   When handling a Peer Registration, the admitting peer MUST reply with
   a 200 response if the admitting peer's Peer-ID has the longest shared
   prefix and is numerically closest to the joining peer's peer-ID as
   compared to all the peers in its leaf set and Bamboo routing table.

   The admitting peer MUST verify that the joining peer's Peer-ID is
   valid.  If the joining peer's credentials are not valid, the message
   should be rejected with a response of 493 Undecipherable.  In
   addition to verifying that the joining peer's Peer-ID is valid, the
   admitting peer MAY require an authentication challenge to the
   REGISTER message.  Once any challenge has been met, the admitting
   will reply with a 200 OK message to the joining peer.  As in a
   traditional registration, the Contact in the 200 OK will be the same
   as in the request, and the expiry time MUST be provided.

   The 200 response that is constructed MUST provide information about
   the admitting peer's leaf set peers in the DHT-Link headers of the
   200 response.  This enables the joining peer to initialize its own
   leaf set and fill any appropriate entries in its Bamboo routing
   table.  These MUST be placed in DHT-Link headers, as described in the
   The DHT-Link Header (Section 5.2) section of this document.  If the
   immediate preceding peer is not NULL, it MUST be transmitted in a
   DHT-Link header using a type of "P" and a depth of 1.  It MUST be
   omitted if NULL.  If the immediate following peer is not NULL, it
   must be transmitted in a DHT-Link header using a type of "S" and
   depth of 1.  It MUST be omitted if NULL.  The 200 or 404 MUST contain
   the other leaf set peers, again only if they are not NULL.
   Additionally, the replying peer MUST include its DHT-PeerID header.

   The admitting peer MUST add the joining peer to its leaf set and the
   joining peer MUST add the admitting peer to its leaf set.  The
   joining peer MAY use the leaf set information to fill in entries in
   its Bamboo routing table.

   [To Do: Add example of 200 response to Peer Registration.]

6.4.  Bamboo Query Processing

   A reply that is constructed to a query by the responsible peer MUST
   provide information about the responding peer's Bamboo routing table
   entries.  These MUST be placed in in the DHT-Link headers of the 200
   or 404 message.  The admitting peer calculates the shared prefix, l,
   between it's Peer-ID and the joining peer's Peer-ID.  The admitting
   peer MUST place all non NULL Bamboo routing table entries in row l of
   its Bamboo routing table in DHT-Link headers of type R, as described
   in the The DHT-Link Header (Section 5.2) section.  Additionally, the
   replying peer MUST include its DHT-PeerID header.




Zangrilli & Bryan        Expires August 29, 2007               [Page 10]


Internet-Draft                   P2PSIP                    February 2007


6.5.  Graceful Leaving

   Peers MUST send their resource registrations to their successor or
   predecessor before leaving the overlay.  Additionally, peers MUST
   unregister themselves with their leaf set peers.  This unregister
   message is constructed exactly the same as the Peer Registration
   message used to join, with the following exceptions.  The expires
   parameter or header MUST be provided, and MUST be set to 0.

6.6.  DHT Maintenance

   In order to keep the overlay stable, peers must periodically perform
   book keeping operations to take into account peer failures.
   Periodically (we suggest 60-360 seconds), peers MUST perform leaf set
   and Bamboo routing table maintenance.

6.6.1.  leaf set maintenance

   Every maintenance period, a peer must exchange its leaf set
   information with a randomly chosen peer in the leaf set.  After
   choosing the peer from the leaf set, the peer MUST send a Peer
   Registration to the selected peer, structured as if the peer had just
   entered the system.  The message MUST include the sending peer's leaf
   set information transmitted in the DHT-Link headers using a type of
   "S" and "P", as described above in the The DHT-Link Header
   (Section 5.2) section.  Additionally, the sending peer MUST include
   its DHT-PeerID header.

   The response MUST include the responding peer's leaf set information
   transmitted in the DHT-Link headers using a type of "S" and "P", as
   described above.  The response MUST also include the DHT-PeerID of
   the responding peer.

   Both peers should examine the DHT-Link Headers in the response and
   verify that the leaf set information is consistent with each others
   leaf set.  If there are any inconsistencies, the peers SHOULD attempt
   to update their leaf sets by contacting the peers in question.

6.6.2.  Bamboo routing table maintenance

   Every maintenance period, a peer MUST perform an arbitrary query for
   to update one of its Bamboo routing entries.  Each routing table
   entry is specified by the l shared prefix with the peer and the
   unique l+1st digit.  During maintenance, the peer performs a peer
   query for a Peer-ID that contains the l prefix and l+1st digit of the
   chosen routing table entry with all other digits random.

   The responding peer MUST provide information about its Bamboo routing



Zangrilli & Bryan        Expires August 29, 2007               [Page 11]


Internet-Draft                   P2PSIP                    February 2007


   table entries in the 200 or 404 response.  The responding peer
   calculates the shared prefix, l, between it's Peer-ID and the sending
   peer's Peer-ID.  The responding peer MUST place all non NULL Bamboo
   routing table entries in row l of its Bamboo routing table in DHT-
   Link headers of type R, as described in the The DHT-Link Header
   (Section 5.2) section.  Additionally, the responding peer MUST
   include its DHT-PeerID header.

   The sending peer uses the information in the response to update its
   Bamboo routing table information.  If the peer in the DHT-PeerID is a
   closer peer than the existing entry in the Bamboo routing table, the
   existing entry MUST be replaced by the peer in the DHT-PeerID.  The
   peers listed in the DHT-Link Headers MAY be used to fill any empty
   Bamboo routing table holes, but these SHOULD be contacted directly
   before adding to the table.

6.7.  Peer Failure

   Peer failure is handled by the periodic DHT Maintenance and responses
   to failed requests discussed above.  Redundancy prevents against lost
   registrations.

6.8.  Resource Replicas

   When a resource is registered, the registering peer SHOULD create at
   least 2 redundant replicas to ensure the registry information is
   secure in the DHT.  The registering peer is responsible for
   maintaining these replicas along with the primary entry.


7.  Examples

   [To Do: Add examples here]


8.  Security Considerations

   There are no new security considerations introduced in this draft
   beyond those already mentioned in the dSIP [I-D.bryan-p2psip-dsip]
   and Security for P2PSIP [I-D.lowekamp-p2psip-dsip-security] drafts.


9.  Open Issues

   As this is preliminary work on how to integrate the Bamboo DHT with
   dSIP, there are many issues that are yet to be resolved.

   The reliability of the system depends in part on keeping the leaf



Zangrilli & Bryan        Expires August 29, 2007               [Page 12]


Internet-Draft                   P2PSIP                    February 2007


   sets updated and exchanging leaf set information between peers.
   Peers should be skeptical of information about peer arrival or
   departures and should verify information by directly contacting
   peers.  However, should it be possible for one peer to trigger
   another peer to update their information?

   The number of bits in each Peer-ID is large (160 if using SHA-1) and
   messages include the Peer-IDs in DHT-PeerID and DHT-Link headers.  In
   Bamboo, each routing table row has the same prefix length (just
   different digits after the prefix are stored in each row).  When
   routing table information is sent in DHT-Link headers, can we
   eliminate the prefix of each Peer-ID?  This would certainly help
   reduce the message size, but needs to be explored more.


10.  IANA Considerations

   This document defines the valid "link-value" values, and defines the
   "dht-param" value to be "Bamboo1.0".


11.  References

11.1.  Normative References

   [I-D.bryan-p2psip-dsip]
              Bryan, D., Lowekamp, B., and C. Jennings, "dSIP: A P2P
              Approach to SIP Registration and Resource Location",
              Internet Draft draft-bryan-p2psip-dsip-00, February 2007.

   [I-D.lowekamp-p2psip-dsip-security]
              Lowekamp, B. and J. Deverick, "Authenticated Identity
              Extensions to dSIP", Internet
              Draft draft-lowekamp-p2psip-dsip-security-00,
              February 2007.

   [I-D.willis-p2psip-concepts]
              Willis, D., "Concepts and Terminology for Peer to Peer
              SIP", draft-willis-p2psip-concepts-03 (work in progress),
              October 2006.

   [RFC2104]  Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
              Hashing for Message Authentication", RFC 2104,
              February 1997.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.




Zangrilli & Bryan        Expires August 29, 2007               [Page 13]


Internet-Draft                   P2PSIP                    February 2007


   [RFC3174]  Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1
              (SHA1)", RFC 3174, September 2001.

   [RFC3261]  Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston,
              A., Peterson, J., Sparks, R., Handley, M., and E.
              Schooler, "SIP: Session Initiation Protocol", RFC 3261,
              June 2002.

11.2.  Informative References

   [Bamboo]   Rhea, R., Geels, D., Roscoe, T., and J. Kubiaatowicz,
              "Handling Churn in a DHT", University of California,
              Berkeley Technical Report UCB/CSD-03-1299 December 2003,
              Usenix Annual Technical Conference June 2004.

   [Chord]    Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.,
              Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A
              Scalable Peer-to-peer Lookup Service for Internet
              Applications", IEEE/ACM Transactions on Networking Volume
              11, Issue 1, 17-32, Feb 2003.


Authors' Addresses

   Marcia Zangrilli
   SIPeerior Technologies
   3000 Easter Circle
   Williamsburg, VA  23188
   USA

   Phone: +1 757 565 0101
   Email: marcia@sipeerior.com


   David A. Bryan
   SIPeerior Technologies
   3000 Easter Circle
   Williamsburg, VA  23188
   USA

   Phone: +1 757 565 0101
   Email: dbryan@sipeerior.com









Zangrilli & Bryan        Expires August 29, 2007               [Page 14]


Internet-Draft                   P2PSIP                    February 2007


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Zangrilli & Bryan        Expires August 29, 2007               [Page 15]