INTERNET DRAFT Weibin Zhao draft-zhao-slp-customization-03.txt Henning Schulzrinne March 25, 2002 Columbia University Expires: September 25, 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: September 25, 2002 [Page 1] Internet Draft SLP Customization March 25, 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. 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. By not needing 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 | 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: September 25, 2002 [Page 2] Internet Draft SLP Customization March 25, 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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 . This MUST have at least one key, and MAY have up to eight keys; extra keys (beyond eight) are ignored. For each key in the , 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. Although SLP has five different 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 has no value, it never needs to be sorted; (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]. As different types of attributes have different sort rules, the type of an attribute must be determined before it can be properly sorted. In SLP, attributes are defined in service templates [4]. But retrieving the attribute type information from service templates is practically difficult due to the existence of incomplete deployment of service templates and inconsistent template versions. Therefore, we adopt a simple approach: all sort types are indicated in the Sort Extension so that service templates are no longer needed in the sort type resolution process. Zhao, et al. Expires: September 25, 2002 [Page 3] Internet Draft SLP Customization March 25, 2002 The is defined using ABNF [5] as follows: sort-key-list = sort-key / sort-key "," sort-key-list sort-key = attr-name / attr-name "=" / attr-name "=" ref-value attr-name = attr-tag from section 5 of RFC 2608 ref-value = intval from section 5 of RFC 2608 The sort type for each sort-key is determined using the following rule: if a sort-key is in the form of "=" or "=", then the specified attribute is sorted as integer, otherwise the specified attribute is sorted as string. Furthermore, the form of "=" indicates a regular integer sort, whereas the form of "=" indicates a reference-based integer sort. For example, if a is encoded as "A,B=,C=12", then attribute A is sorted as string, attribute B is sorted as integer, and attribute C is sorted as integer based on the distance to the reference value 12. A reference-based integer sort "C=12" requires the following two steps: Step 1. for each matched service, if its attribute C has a value of x, then use |x-12| as its metric. Step 2. use the metrics obtained in Step 1 to sort attribute C 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 best effort, no sort error will be returned from a DA/SA to a UA. (1) The is in order of highest to lowest sort key precedence (section 1.1 of RFC 2891). (2) Each attribute SHOULD only occur in the once (section 1.1 of RFC 2891). If an attribute is included in the 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). Zhao, et al. Expires: September 25, 2002 [Page 4] Internet Draft SLP Customization March 25, 2002 (6) As the attribute type in SLP is un-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 as follows: (1) OPTION_NOT_UNDERSTOOD [1] if the DA/SA does not support the Sort Extension, (2) 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 Integer sort on speed (reverse order). Sort(0x80, "speed=") [Note] The "=" following the attribute name "speed" indicates that the values are considered as integers, and only values with integer syntax will be sorted. o Integer sort on load (default order) and speed (reverse order). Sort(0x40, "load=,speed=") o String sort on model (default order). Sort(0x00, "model") [Note] Since the attribute name "model" is not followed by an "=", the values are considered as strings, and sorted as such. o Integer sort on speed (default order), based on a reference value 12. Sort(0x00, "speed=12") [Note] The "=" following the attribute name "speed" indicates that the values are considered as integers. Further, a reference value "12" following the "=" indicates that the values are sorted based on the distance to the reference value 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|). Zhao, et al. Expires: September 25, 2002 [Page 5] Internet Draft SLP Customization March 25, 2002 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) 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) 6. Security Considerations The security considerations for RFC 2891 apply to this document. 7. Acknowledgments The need for best match in SLP was initially proposed by Erik Guttman. He reviewed the whole document in detail and gave many valuable comments. Ira McDonald also provided good suggestions. Zhao, et al. Expires: September 25, 2002 [Page 6] Internet Draft SLP Customization March 25, 2002 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 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 Zhao, et al. Expires: September 25, 2002 [Page 7] Internet Draft SLP Customization March 25, 2002 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: September 25, 2002 [Page 8]