INTERNET DRAFT Weibin Zhao draft-zhao-slp-customization-04.txt Henning Schulzrinne June 3, 2002 Columbia University Expires: December 3, 2002 Erik Guttman Sun Microsystems 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 number, or be sorted according to the specified sort key list. Using these two extensions together can support best match. Zhao, et al. Expires: December 3, 2002 [Page 1]
Internet Draft SLP Customization June 3, 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 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. Using the Sort Extension, a UA can ask the DA/SA to sort matched URL entries, which helps the UA to choose a service from multiple candidates. As it does not need to pass attributes to the UA, sort at the server side is more efficient than sort at the client side. 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 a reference value. 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 | Number of URL Entries | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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 limit the maximum number (say n) of URL entries to be returned. When a DA/SA receives a SrvRqst with a Selection Extension, it MUST use a Selection Extension in the corresponding SrvRply to indicate the total number (say m) of matched URL entries if the DA/SA supports this extension, otherwise the DA/SA MUST set the error code in the corresponding SrvRply to OPTION_NOT_UNDERSTOOD [1]. If n < m, then only the first n (not random n) matched URL entries are returned, else all m matched URL entries are returned. As a special case, a UA may set n to zero to obtain the number of matched URL entries without retrieving the entries themselves. Zhao, et al. Expires: December 3, 2002 [Page 2]
Internet Draft SLP Customization June 3, 2002 We denote a Selection Extension as Select(number). Thus, Select(3) means that the corresponding SrvRply can have 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 | length of <sort-key-list> |<sort-key-list>\ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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>. The <sort-key-list> is defined using ABNF [5] as follows: sort-key-list = sort-key / sort-key "," sort-key-list sort-key = attr-name ":" type ":" ordering [":" ref-value] attr-name = attr-tag from section 5 of RFC 2608 type = "s" / "i" ; "s" for string type ; "i" for integer type ordering = "0" / "1" ; "0" for default ordering ; "1" for reverse ordering ref-value = intval from section 5 of RFC 2608 The type of a key is explicitly specified since this information is practically difficult to be retrieved from service templates [4] due to incomplete deployments and inconsistent versions. Although SLP has five attribute types (integer, string, boolean, opaque and keyword), we only consider integer sort and string sort. This is based on the following observations: (1) a keyword attribute never needs to be sorted since it has no value; (2) boolean and opaque attributes can be sorted as string if needed. The integer sort uses the integerOrderingMatch rule defined in X.520 [3], whereas the string sort is performed based on lexical ordering. Strings are compared using the rules defined in section 6.4 of RFC 2608 [1]. When an optional ":<ref-value>" is present in a <sort-key>, it indicates a reference-based sort that is applicable only to integer type. For example, if a <sort-key-list> is "A:i:0:12", then attribute A is sorted as integer based on the distance to the reference value Zhao, et al. Expires: December 3, 2002 [Page 3]
Internet Draft SLP Customization June 3, 2002 12 (default ordering), which requires the following two steps: Step 1. for each matched service, if its attribute A has a value of x, then use |x-12| as its metric. Step 2. use the metrics obtained in Step 1 to sort attribute A for matched services. The SLP sort rules are adapted from the LDAP sort rules defined in RFC 2891 [6]. Note that sort in SLP is a best effort, no sort error will be returned from a DA/SA to a UA. (1) The <sort-key-list> is in order of highest to lowest sort key precedence (section 1.1 of RFC 2891). (2) Each attribute SHOULD only occur in the <sort-key-list> once (section 1.1 of RFC 2891). If an attribute is included in the <sort-key-list> multiple times, only its first occurrence is considered, all other occurrences are ignored. (3) For a multi-valued attribute, the least value in each entry SHOULD be used in sort (section 2.2 of RFC 2891). (4) An entry missing one or more of the sort keys is treated as having NULLs for those missed keys (section 2.2 of RFC 2891). (5) NULL is considered as a larger value than all other valid values (section 2.2 of RFC 2891). (6) As the attribute type in SLP is not enforced, an attribute may have inconsistent values. For the purpose of sort, inconsistent values may exist only when an attribute is sorted as integer. Inconsistent values SHOULD be treated as NULLs. When a DA/SA receives a SrvRqst with a Sort Extension, the DA/SA SHOULD set the error code in the corresponding SrvRply to OPTION_NOT_UNDERSTOOD [1] if the DA/SA does not support the Sort Extension, or to zero if the DA/SA has successfully performed the requested sort. We denote a Sort Extension as Sort(sort-key-list). The following examples illustrate how to use the Sort Extension. o Integer sort on speed (reverse ordering). Sort(speed:i:1) [Note] "i" means integer sort, and "1" means reverse ordering. Zhao, et al. Expires: December 3, 2002 [Page 4]
Internet Draft SLP Customization June 3, 2002 o Integer sort on load (default ordering) and speed (reverse ordering). Sort(load:i:0,speed:i:1) [Note] "0" means default ordering. o String sort on model (default ordering). Sort(model:s:0) [Note] "s" means string sort. o Integer sort on speed (default ordering), based on a reference value 12. Sort(speed:i:0:12) For example, if we have four matched services, with the "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 ordering 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(load:i:0) Select(1) o Find the top three speeds Sort(speed:i:1) Select(3) o Find the minimum load among the top three speed Sort(speed:i:1) Select(3) Sort(load:i:0) Select(1) Zhao, et al. Expires: December 3, 2002 [Page 5]
Internet Draft SLP Customization June 3, 2002 o Find the service that has a speed closest to 12 Sort(speed:i:0:12) Select(1) 5. Constants Selection Extension ID TBD (section 2) Sort Extension ID TBD (section 3) 6. Security Considerations The security considerations for RFC 2891 apply to this document. 7. Acknowledgments Ira McDonald provided good suggestions. 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] International Telephone Union, "The Directory: Selected Attribute Types", X.520, 1997. [4] E. Guttman, C. Perkins and J. Kempf, "Service Templates and Service: Schemes", RFC 2609, June, 1999. [5] D. Crocker and P. Overell, "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, November 1997. [6] T. Howes, M. Wahl and A. Anantha, "LDAP Control Extension for Server Side Sorting of Search Results", RFC 2891, August 2000. 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 Zhao, et al. Expires: December 3, 2002 [Page 6]
Internet Draft SLP Customization June 3, 2002 Erik Guttman Sun Microsystems Eichhoelzelstr. 7 74915 Waibstadt Germany Email: Erik.Guttman@sun.com 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: December 3, 2002 [Page 7]
