Network Working Group                                         M. Bagnulo
Internet-Draft                                                      UC3M
Intended status: Informational                              July 8, 2007                         February 22, 2008
Expires: January 9, August 25, 2008

    Default Locator-pair selection algorithm for the SHIM6 protocol

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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on January 9, August 25, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2007). (2008).


   In this note, we present a locator-pair selection mechanism for the
   shim6 protocol.  The presented mechanism provides an ordered list of
   available locator-pairs that can be used for outgoing traffic.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Preliminary considerations . . . . . . . . . . . . . . . . . .  4
     2.1.  Candidate Locator-pair set . . . . . . . . . . . . . . . .  4
     2.2.  Locator-pair States  . . . . . . . . . . . . . . . . . . .  5
     2.3.  Locator preferences  . . . . . . . . . . . . . . . . . . .  5
       2.3.1.  Remote locator preferences . . . . . . . . . . . . . .  5
       2.3.2.  Source locator preferences . . . . . . . . . . . . . .  6
     2.4.  Locator-pair selection table . . . . . . . . . . . . . . .  6
   3.  Default Locator-Pair Selection Algorithm . . . . . . . . . . .  6
   4.  Security considerations  . . . . . . . . . . . . . . . . . . .  8
     4.1.  Privacy considerations . . . . . . . . . . . . . . . . . .  8
   5.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . .  9
   6.  References . . . . . . . . . . . . . . . . . . . . . . . . . .  9
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10
   Intellectual Property and Copyright Statements . . . . . . . . . . 11

1.  Introduction

   Once that a shim6 context is established between two peers, they are
   free to select the best locator pair to continue the communication.
   In particular, when an outage is detected, they will need to select a
   new locator pair to rehome the communication.  Besides, policy or
   other considerations may lead to change the locator pair used in the
   communication even if no outage has occurred.

   In this note, we present a locator-pair selection mechanism for the
   shim6 protocol.  The presented mechanism provides an ordered list of
   available locator-pairs that can be used for outgoing traffic (note
   that since unidirectional locator pairs are supported by the shim6
   protocol, the locator pair used in the outgoing direction may not
   affect the locator pair used by the peer to send incoming traffic).

   The motivation for having a locator selection mechanism different
   than RFC 3484 [3] is that RFC 3484 was designed to select addresses
   that were both identifiers and locators, so, in some cases the
   selection criteria differs from the one used when selecting addresses
   that will used only as locators.  In particular, when addresses are
   to be used as identifiers and as locators, stable addresses such as
   Home Addresses are preferred over more temporary addresses as Care-
   Off Addresses.  If an address is to be used only as a locator,
   probably the stability property is not as important as achieving a
   more direct path, making a Care-off Address more attractive than a
   Home Address.  Similar considerations can be made with respect to
   private and public addresses.  In addition, the locator pair
   selection mechanism described in this document incorporates into the
   selection mechanism shim-specific information, such as available
   reachability information and local and remote locator preferences
   obtained through the shim6 protocol.  Finally, the mechanism
   presented in this note is a locator pair selection mechanism as
   opposed to separate source address and destination address selection
   mechanisms as described in RFC 3484.  We think that such approach is
   more appropriate for the shim6 protocol, since reachability seems to
   be a property of an address pair rather than a property of a single

   The presented mechanism takes into account general properties of the
   available addresses, in particular the address family (v4 or v6),
   address scope [3], mobility consideration (Home-Addresses and Care-
   off Addresses) [4], status of the addresses (Preferred and Deprecated
   addresses) [5], privacy considerations (Public and Temporary
   addresses) [6].  In addition it also takes into account shim6
   specific information such as whether the addresses are known to be
   locally operational (as defined in [2]), if locator pairs are know to
   be unidirectionally operational [2], the local and remote preferences
   for the different locators available in the shim6 context.

   Multicast addresses are out of the scope of the document.

2.  Preliminary considerations

2.1.  Candidate Locator-pair set

   We define the local set of locally-operational locators (LOLs(local))
   as the local locators that are included in the local locator set
   (Ls(local) as defined in [1]) and that are locally operational as
   defined in [2].  Locally operational addresses are discovered through
   local means that are outside of the scope of this document.

   We define the set of the locally-operational locators of the peer
   (LOLs(peer)) as the remote locators that are included in the peer
   locator set (Ls(peer) as defined in [1]) and that are locally
   operational in the peer as defined in [2].  The peers' locally
   operational locators are discovered through the Locator List Option
   and the Locator Preferences Option (in particular the BROKEN flag)
   defined in the shim protocol [1].

   The candidate locator-pair set is the set of locator pairs that can
   be used to send packets in a shim context.

   The candidate locator-pair set contains in all the possible locator
   pairs formed with the first of them belonging to the local set of
   locally-operational locators (LOLs(local)) and the second locator
   belonging to the locally-operational locators of the peer

   This can be expressed as:

   Cand_Loc_Pair_Set ={(x,y)/[x in LOLs(local) and y in LOLs(peer)}

   Current shim6 protocol specification only supports IPv6 addresses as
   locators.  In case the shim6 protocol specification is updated and
   IPv4 addresses are accepted as locators, the creation of the
   Candidate Locator Pair Set must only accept locator pairs where both
   source and destiantion address are of the same family.  The result
   would be the following formula:.

   Cand_Loc_Pair_Set ={(x,y)/[family(x) = family(y)] AND [x in
   LOLs(local) and y in LOLs(peer)]}

   Question: should we allow locator pairs with all types of scope
   combinations or should we restrict the type of scope combinations for
   the inclusion in the cadidate set?  If we don't allow all the
   combinations, we can remove rule 1 aboput scopes

2.2.  Locator-pair States

   Locator pairs can be in the following state:

   o  Unidirectionally Operational state: As defined in [2], is when
      packets send with the first locator as the source address and the
      second locator as a destination address are known to reach the
      destination.  In the shim6 case, a locator pair is know to be
      unidirectionally operational when there is fresh information about
      packets reaching the peer, using the mechanisms defined in [2] or
      thanks to recent ULP feedback.  When the information about
      reachability expires, the locator pair moves to Unknown state.
   o  Non-Operational state: The locator pair is known to be non-
      operational i.e. that packets containing the first locator as
      source address and the second locator as destination address do
      not reach the destination.  In the shim6 case this can be known
      because recent attempts to exchange packets have failed.  When the
      information about unreachability expires, the locator pair moves
      to Unknown state.
   o  Unknown state: No recent reachability information is available for
      this locator-pair.

2.3.  Locator preferences

2.3.1.  Remote locator preferences

   Remote locator preferences can be obtained through the shim6 protocol
   using the Locator Preference option.  The preferences consist in a
   Flag octet, a Priority octet and an optional Weight octet.

   The weight field express the relative weight for locators with the
   same priority, and as defined in [7] larger weights should be given a
   proportionally higher probability of being selected.  In order to
   include this probability information in the locator-pair selection
   algorithm, a new weight* information is generated from the weight
   values as following:

   We order each set of destination addresses with the same priority and
   defined weight values using the following algorithm defined in [7]:

   Arrange all addresses (that have not been ordered yet) in any order,
   except that all those with weight 0 are placed at the beginning of
   the list.

   Compute the sum of the weights of those addresses, and with each
   address associate the running sum in the selected order.  Then choose
   a uniform (pseudo)random number between 0 and the sum computed
   (inclusive), and select the address whose running sum value is the
   first in the selected order which is greater than or equal to the
   (pseudo)random number selected.  This address is the next one to be
   included in the ordered list.  Remove this address from the set of
   the unordered addresses and apply the described algorithm to the
   unordered address set to select the next target address.  Continue
   the ordering process until there are no unordered addresses.

   The weight* (W*1, W*2,...,W*N) values for each of the addresses is
   their final position in the resulting ordered list.

   The procedure is repeated for each one of the sets containing
   destination addresses with equal priority.

   The Weight information is not used in the locator-pair selection
   mechanism, but the Weight* information is.

2.3.2.  Source locator preferences

   With respect to the local locator preferences, this document assumes
   that the host will have a mechanism to express Priority and Weight
   information for local locators similar to the one defined in [7].

   The same procedure is used to assign Weight* values to the source
   locators that have the same priority value.

   Note that destination and source addresses are never included in the
   same set, even if they have the same priority value.

   The Weight information is not used in the locator-pair s election
   mechanism, but the Weight* information is.

2.4.  Locator-pair selection table

   We define the Locator-pair selection table to express preferences
   about which source address prefix to use when communicating with a
   given destination address prefix.  The table contains entries having
   a source prefix and a destination prefix each.  Given a locator pair,
   it is then possible to find a match when both the source prefix is
   contained in the source address and the destination prefix is
   contained in the destination address.

3.  Default Locator-Pair Selection Algorithm

   The goal of the defualt locator-pair selection algorithm is to
   produce an ordered list of locator pairs to be tried for rehoming an
   ongoing communication.  The ordered list can be produced with any
   sorting algorithm.  The set of rules described next are the
   comparison criteria to be used in the locator-pair sorting algorithm.
   This rules act must be processed in order and if a given rule selects
   a locator pair over the other one, then the following rules don't
   need to be processed and the selected locator pair is prefered.

   We are comparing two locator pairs (src1,dst1) and (src2,dst2).  Note
   that in some cases the source or the destination addresses of the two
   pairs may be equal.
   Rule 1:  Prefer appropriate scope: If scope(src1) >= scope(dst1) and
            scope(src2) < scope(dst2), then prefer (src1,dst1).

   Rule 2:  Avoid Non-Operational pairs: If (src1,dst1) is in Non-
            Operational state and (src2,dst2) is in Unidirectionally
            Operational or in Unknown state, then prefer (src2,dst2).

   Rule 3:  Prefer Unidirectionally Operational state: If (src1,dst1) is
            in Unknown state and (src2,dst2) is in Unidirectionally
            Operational, then prefer (src2,dst2).

   Rule 4:  Prefer fresher reachability information: If (src1,dst1) and
            (src2,dst2) are both in Unidirectionally Operational state,
            then prefer the one with smallest age information i.e. the
            one for which newer reachability information is available.

   Rule 5:  Prefer ULID-Pair: If (src1,dst1) is the ULID-pair of the
            context, the prefer (src1,dst1)

   Rule 6:  Prefer matching scope: If scope(src1) = scope(dst1) and
            scope(src2) < scope(dst2), then prefer (src1,dst1)

   Rule 7:  Prefer Locator-pair table match: If (dst1,src1) has a match
            in the Locator-pair selection table and (src2,dst2) does not
            have a match in the locator-pair selection table, then
            prefer (dst1,src1).

   Rule 8:  Prefer Preferred addresses: If src1 address is a Preferred
            address in the RFC2462 sense and src2 is a deprecated
            address in the RFC2462 sense, then prefer (src1,dst1)

   Rule 9:  Prefer Local Priority: If src1 of (src1,dst1) has a lowest
            Priority than src2 of (src2,dst2) then prefer (src1,dst1)
   Rule 10: Prefer Local Weight*: If src1 of (src1,dst1) has a lowest
            Weight* than src2 of (src2,dst2) then prefer (src1,dst1)

   Rule 11: Prefer Local Care-off Addresses: If src1 is a Care-off
            address [4] and src2 is a Home Address, the prefer
            (src1,dst1).  This only applies to Mobile IP [4].

   Rule 12: Prefer Remote Priority: If dst1 of (src1,dst1) has a lowest
            Priority than dst2 of (src2,dst2) then prefer (src1,dst1)

   Rule 13: Prefer Remote Weight*: If dst1 of (src1,dst1) has a lowest
            Weight* than dst2 of (src2,dst2) then prefer (src1,dst1)

   Rule 14: Prefer Remote Care-off Addresses: If dst1 is a Care-off
            address (Temporary flag set in the Locator preferences
            options defined in [1]) and dst2 is not a Care-off address,
            the prefer (src1,dst1).  This only applies to Mobile IP [4].

   Other rules that may be worth taking into account are:
   o  Prefer native transport
   o  Prefer smaller scope
   o  Prefer most dissimilar locator pair to the currently used
   o  Prefer locator pair contained in incoming packet
   o  Longest prefix match
   o  Should we eliminate the site and link local addresses from the
      accpetable locator set?

4.  Security considerations

   Note that according to the shim6 protocol specification, locators are
   included in the Ls(peer) only after HBA/CGA verification has been
   successful.  This eliminates the possibility of using locators that
   do not belong to the peer.  Besides, it should be noted that before
   using a given locator pair to actually send data packets, a
   reachability test is performed in order to prevent flooding attacks.

4.1.  Privacy considerations

   Including or not RFC3041 [6] addresses in the Locator set available
   for a shim6 context may have privacy implications.  This is so
   because of two reaosns: First, the inclusion of RFC 3041 addresses in
   the locator set discloses the RFC3041 addresses of the host to the
   peer.  Second, the locator sets of both peers are exchanged in clear
   text during the shim6 context establishment and/or in the subsequent
   UPDATE messages.  This means that an attacker located along the path
   that can observe such packets can discover that all the addresses
   included in the locator set belong to the same host, beating the
   purpose of RFC3041 private addresses.  So, when forming the locator
   set of a shim6 context the host must take into account these privacy
   considerations in order to decide whether to include RFC3041
   addresses in the locator set of a shim6 context.

5.  Acknowledgements

   The idea of pre-assigning Weight* values for introducing the Weight
   probability in the locator-pair selection process was suggested by
   Albert Banchs.

   Marcelo Bagnulo worked on this document while visiting Ericsson
   Research laboratory Nomadiclab.

   Iljitsch van Beijnum provided a detailed review of this document.

6.  References

   [1]  Nordmark, E. and M. Bagnulo, "Level 3 multihoming shim
        protocol", draft-ietf-shim6-proto-04 (work in progress),
        March 2006.

   [2]  Arkko, J. and I. Beijnum, "Failure Detection and Locator Pair
        Exploration Protocol for IPv6  Multihoming",
        draft-ietf-shim6-failure-detection-03 (work in progress),
        December 2005.

   [3]  Hinden, R. and S. Deering, "IP Version 6 Addressing
        Architecture", RFC 4291, February 2006.

   [4]  Johnson, D., Perkins, C., and J. Arkko, "Mobility Support in
        IPv6", RFC 3775, June 2004.

   [5]  Thomson, S. and T. Narten, "IPv6 Stateless Address
        Autoconfiguration", RFC 2462, December 1998.

   [6]  Narten, T. and R. Draves, "Privacy Extensions for Stateless
        Address Autoconfiguration in IPv6", RFC 3041, January 2001.

   [7]  Gulbrandsen, A., Vixie, P., and L. Esibov, "A DNS RR for
        specifying the location of services (DNS SRV)", RFC 2782,
        February 2000.

   [8]  Draves, R., "Default Address Selection for Internet Protocol
        version 6 (IPv6)", RFC 3484, February 2003.

Author's Address

   Marcelo Bagnulo
   Universidad Carlos III de Madrid
   Av. Universidad 30
   Leganes, Madrid  28911

   Phone: 34 91 6248814

Full Copyright Statement

   Copyright (C) The IETF Trust (2007). (2008).

   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

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

   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


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