INTERNET DRAFT                                            Weibin Zhao
draft-zhao-slp-customization-02.txt               Henning Schulzrinne
February 1, 2002                                  Columbia University
Expires: August 1, 2002                           Chatschik Bisdikian
                                                       William Jerome
                                                                  IBM


                  Selection and Sort Extension for SLP


Status of This Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   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.

Copyright Notice

   Copyright (C) The Internet Society (2002).  All Rights Reserved.

Abstract

   This document defines the Selection and Sort extension for the
   Service Location Protocol. These extensions allow a User Agent to
   request that the URL entries in a Service Reply be bounded to the
   specified maximum number, or be sorted according to the specified
   sort key list. Using these two extensions together can support best
   match.







Zhao, et al.            Expires: August 1, 2002                 [Page 1]


Internet Draft             SLP Customization            February 1, 2002


1. Introduction

   This document defines the Selection and Sort extension for the
   Service Location Protocol (SLP [1]). These extensions allow a User
   Agent (UA) to request that the URL entries in a Service Reply
   (SrvRply) be bounded to the specified maximum number, or be sorted
   according to the specified sort key list.

   Using the Selection Extension, a UA can opt for finding a few (not
   all) services, which is useful if the UA only has limited resources
   or uses a low-bandwidth channel. The Sort Extension enables server-
   side sorting of matched URL entries, which helps a UA to choose a
   service from multiple candidates, and is more efficient than client-
   side sorting since it can avoid passing attributes to the UA.
   Furthermore, using the Selection and Sort extension together can
   support best match, such as finding a service that has the maximum
   speed or the minimum load, or has a speed closest to the specified
   reference value (by using reference-based sort, see section 3).

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

2. Selection Extension

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Selection Extension ID = TBD  |  Next Extension Offset (NEO)  |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | NEO, cont'd   |  upper-bound  |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                      Figure 1. Selection Extension

   The format of the Selection Extension is shown in Figure 1. A UA uses
   this extension in a Service Request (SrvRqst) to request that the URL
   entries in the corresponding SrvRply be bounded to the specified
   maximum number. If the upper-bound is n, and the number of matched
   URL entries is m, then the corresponding SrvRply SHOULD include only
   the first n matched URL entries if m > n, or include all m matched
   URL entries if m <= n.

   When a DA/SA receives a SrvRqst with a Selection Extension, the DA/SA
   SHOULD set the error code in the corresponding SrvRply as follows:
   (1) OPTION_NOT_UNDERSTOOD [1] if the DA/SA does not support the
   Selection Extension, (2) zero if the DA/SA has successfully performed
   the requested selection.



Zhao, et al.            Expires: August 1, 2002                 [Page 2]


Internet Draft             SLP Customization            February 1, 2002


   We denote a Selection Extension as Select(upper-bound). Thus,
   Select(3) means that the corresponding SrvRply SHOULD include at most
   three URL entries.

3. Sort Extension

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |    Sort Extension ID = TBD    |  Next Extension Offset (NEO)  |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | NEO, cont'd   | reverse-order |   length of <sort-key-list>   |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                      <sort-key-list> string                   \
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Figure 2. Sort Extension

   The format of the Sort Extension is shown in Figure 2. A UA uses this
   extension in a SrvRqst to request the URL entries in the
   corresponding SrvRply be sorted according to the <sort-key-list>.
   This <sort-key-list> MUST have at least one key, and MAY have up to
   eight keys; extra keys (beyond eight) are ignored. All keys in the
   <sort-key-list> MUST have been defined as service attributes in the
   corresponding service template [3].

   For each key in the <sort-key-list>, default ordering is assumed
   unless a corresponding bit is set in the reverse-order byte. For
   example, if the reverse-order byte is 0x80, then the first key is
   sorted in reverse order, all other keys are sorted in default order.

   Only string and integer attributes can be sorted (i.e., it is invalid
   to sort boolean, opaque and keyword attributes). Strings are compared
   using the rule defined in section 6.4 of RFC 2608 [1]. Integers are
   compared using the integerOrderingMatch rule defined in X.520 [4].
   The sort operation SHOULD conform to RFC 2891 [5].

   If a key in the <sort-key-list> has a type of integer, it MAY have a
   value, such as "speed=12". In this case, the sort operation on the
   speed attribute is reference-based, which requires the following two
   steps:

   Step 1. for each matched service, if its speed attribute value is
           x, then use |x-12| as its metric.

   Step 2. use the metrics obtained in Step 1 to sort the speed
           attribute for matched services.




Zhao, et al.            Expires: August 1, 2002                 [Page 3]


Internet Draft             SLP Customization            February 1, 2002


   When a DA/SA receives a SrvRqst with a Sort Extension, the DA/SA
   SHOULD set the error code in the corresponding SrvRply as follows:
   (1) OPTION_NOT_UNDERSTOOD [1] if the DA/SA does not support the Sort
   Extension, (2) SORT_ERROR (section 5) if the DA/SA encounters any
   sorting error, (3) zero if the DA/SA has successfully performed the
   requested sort.

   We denote a Sort Extension as Sort(reverse-order, "sort-key-list").
   The following examples illustrate how to use the Sort Extension.

   o Sort on speed (reverse order).

     Sort(0x80, "speed")

   o Sort on load (default order) and speed (reverse order).

     Sort(0x40, "load,speed")

   o Sort on speed (default order), based on a reference value 12.

     Sort(0x00, "speed=12")

     [Note] If there are four matched services, with speed attribute
     as 8 (URL1), 10 (URL2), 12 (URL3), and 15 (URL4), then the sorted
     URL list will be "URL3,URL2,URL4,URL1" (based on the metric order
     of |12-12| < |12-10| < |12-15| < |12-8|).

4. Using the Selection and Sort Extension Together

   In addition to being used individually, the Selection and Sort
   Extension can be used together to support best match, such as finding
   a service with the maximum speed. When these two extensions appear in
   the same SrvRqst message, they MUST be processed in the order of
   their presence. Let's look at some examples.

   o Find the minimum load

     Sort(0x00, "load")
     Select(1)

   o Find top three in terms of speed

     Sort(0x80, "speed")
     Select(3)







Zhao, et al.            Expires: August 1, 2002                 [Page 4]


Internet Draft             SLP Customization            February 1, 2002


   o Find the minimum load among the top three in terms of speed

     Sort(0x80, "speed")
     Select(3)
     Sort(0x00, "load")
     Select(1)

   o Find the service that has a speed closest to 12

     Sort(0x00, "speed=12")
     Select(1)

5. Constants

   Selection  Extension ID                 TBD    (section 2)
   Sort       Extension ID                 TBD    (section 3)
   SORT_ERROR error code                   TBD    (section 3)

6. Security Considerations

   The security considerations for RFC 2891 [5] are applied to this
   document.

7. Acknowledgments

   Erik Guttman and Ira McDonald provided valuable comments for this
   document.

8. References

   [1] E. Guttman, C. Perkins, J. Veizades and M. Day, "Service location
       protocol, version 2", RFC 2608, June 1999.

   [2] S. Bradner, "Key words for use in RFCs to indicate requirement
       levels", BCP 14, RFC 2119, March 1997.

   [3] E. Guttman, C. Perkins and J. Kempf, "Service Templates and
       Service: Schemes", RFC 2609, June 1999.

   [4] International Telephone Union, "The Directory: Selected
       Attribute Types", X.520, 1997.

   [5] T. Howes, M. Wahl and A. Anantha, "LDAP Control Extension for
       Server Side Sorting of Search Results", RFC 2891, August 2000.







Zhao, et al.            Expires: August 1, 2002                 [Page 5]


Internet Draft             SLP Customization            February 1, 2002


9. Authors' Addresses

   Weibin Zhao
   Henning Schulzrinne
   Department of Computer Science
   Columbia University
   1214 Amsterdam Avenue, MC 0401
   New York, NY 10027-7003
   Email: {zwb,hgs}@cs.columbia.edu

   Chatschik Bisdikian
   William F. Jerome
   IBM T. J. Watson Research Center
   P.O.Box 218
   Yorktown Heights, NY 10598-0218
   Email: {bisdik,wfj}@us.ibm.com

10. Full Copyright Statement

   Copyright (C) The Internet Society (2002).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS 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.







Zhao, et al.            Expires: August 1, 2002                 [Page 6]