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 <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.
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.
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 <sort-key-list> 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 "<attr-name>=" or "<attr-
name>=<ref-value>", then the specified attribute is sorted as
integer, otherwise the specified attribute is sorted as string.
Furthermore, the form of "<attr-name>=" indicates a regular integer
sort, whereas the form of "<attr-name>=<ref-value>" indicates a
reference-based integer sort.
For example, if a <sort-key-list> 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 <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).
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]
