SEAMOBY Working Group Arunesh Mishra INTERNET-DRAFT University of Maryland Expires: August 2003 24 February 2003 The use of Neighbor Graphs for Context Caching This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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 (2003). All Rights Reserved. Abstract The use of neighbor graphs as a method for dynamically caching the context of mobile stations in front of the station's mobility path can reduce the latency of handoff's between base stations or access points. Neighbor graphs capture the set of all potential mobility paths for a wireless network. Given any base station or access point, the set of all possible hand-offs can easily be determined by examining the neighbor graph in either a distributed fashion (at each base station) or centralized at the AAA server. This draft describes how the neighbor graph algorithm works at both the base station and the AAA server. Mishra et. al. [Page 1] INTERNET-DRAFT Context Caching 24 February 2003 Table of Contents 1. Introduction .......................................... 2 1.1 Terminology ..................................... 3 1.2 Requirements language ........................... 4 2. Neighbor Graph Creation and Maintenance................ 4 2.1 Authentication Server............................ 4 2.2 NAS.......... ................................... 5 3. Usages of Neighbor Graphs.............................. 5 3.1 Context Caching........... ...................... 5 3.2 Management Information........................... 5 4. Security considerations ............................... 6 4.1 IPsec usage guidelines .......................... 6 5. IANA considerations ................................... 6 6. Normative references .................................. 6 7. Informative references ................................ 7 ACKNOWLEDGMENTS .............................................. 8 AUTHORS' ADDRESSES ........................................... 8 Intellectual Property Statement .............................. 9 Full Copyright Statement ..................................... 9 Mishra et. al. [Page 2] INTERNET-DRAFT Context Caching 24 February 2003 1. Introduction In wireless networks such as IEEE 802.11, described in [IEEE80211], it may be desirable to improve the speed at which a handoff can be completed. A number of different approaches can be used to facilitate the handoff process using RADIUS extensions as described in [Arbaugh2003]. This draft describes the notion of neighbor graphs as one possible approach. The sequence of NASes contacted by clients as they move creates a graph representing the mobility paths of the clients. We call this graph a neighbor graph with NASes as the vertices and the mobility paths between the NASes as the edges. Thus, the number of neighbors for a given NAS is given by the degree function applied to the vertex representing the given NAS, e.g. for NAS_A the number of neighbors would be given by deg(v_A) where deg is the degree function- deg: V -> int. Through knowledge of the neighbor graph, it is possible for the basestation or RADIUS server to anticipate client movements and provide advance notice of a potential handoff to the NAS. This advance notice can be provided by the RADIUS extensions described in [Arbaugh2003]. This removes the latency of the RADIUS exchange from the critical path for processing a handoff, decreasing handoff latency substantially, as described in [IEEE-02-758, IEEE-03-084]. Assuming that the coverage area is over- lapping, this technique can support handoffs at vehicular velocities. The creation and maintenance of neighbor graphs at an AS and basestation is described in this document. By nature, client behavior is not completely predictable, so that the handoff advance notice is only advisory. The client identified in the advance notice may never contact the NAS, or may contact it long after the initial notice is received. As a result, the NAS will typically free reserved resources after a suitable waiting period, known as the Reservation-Lifetime. A client contacting the NAS after the Reservation- Lifetime has expired will be unable to complete a handoff, and will need to do a fast resume, such as is supported in EAP TLS [RFC2716]. The extension described in [Arbaugh2003] enables a RADIUS Server to send Notify-Requests to NASes, and to receive Notify-Responses. The Notify- Request identifies the session to be handed off. If the NAS has Mishra et. al. [Page 3] INTERNET-DRAFT Context Caching 24 February 2003 resources available to reserve, and if it is enabled to support this handoff extension, then it will respond with a Notify-Accept. If resources are not available (such as when previous resource commitments leave insufficient resources remaining), or if the NAS does not wish to support the handoff for any other reason, the NAS will respond with a Notify-Reject, specifying the reason why the requested handoff reservation could not be carried out. After the NAS responds with a Notify-Accept, it will typically issue an Access-Request to the RADIUS server. This allows the NAS to obtain the authorizations for the session before it is contacted by the client. The contents of the Access-Request sent by the NAS will depend on the form of access it is providing, so that it cannot be specified in detail here. However, for use with IEEE 802.11, it is expected that an Access- Request will be sent with a NAS-Port-Type=802.11 and a Service- Type=Handoff. For other access methods, a different NAS-Port-Type value might be sent, along with a different value for Service-Type. 1.1. Terminology This document uses the following terms: Authenticator An Authenticator is an entity that require authentication from the Supplicant. The Authenticator may be connected to the Supplicant at the other end of a point-to-point LAN segment or 802.11 wireless link. Authentication Server An Authentication Server is an entity that provides an Authentication Service to an Authenticator. This service verifies from the credentials provided by the Supplicant, the claim of identity made by the Supplicant. Network Access Server (NAS) The device providing access to the network. Service The NAS provides a service to the user, such as IEEE 802 or PPP. Port Access Entity (PAE) The protocol entity associated with a physical or virtual (802.11) Port. A given PAE may support the protocol functionality associated with the Authenticator, Supplicant or both. Mishra et. al. [Page 4] INTERNET-DRAFT Context Caching 24 February 2003 Session Each service provided by the NAS to a user constitutes a session, with the beginning of the session defined as the point where service is first provided and the end of the session defined as the point where service is ended. A user may have multiple sessions in parallel or series if the NAS supports that, with each session generating a separate start and stop accounting record. Where the client is mobile and is able to handoff between NASes, multiple related sessions may be uniquely identified by the Acct-Multi-Session-Id attribute. Supplicant A Supplicant is an entity that is being authenticated by an Authenticator. The Supplicant may be connected to the Authenticator at one end of a point-to-point LAN segment or 802.11 wireless link. 1.2. Requirements language In this document, several words are used to signify the requirements of the specification. These words are often capitalized. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 2. Neighbor Graph Creation and Maintenance 2.1. Authentication Server The creation of the neighbor graph is accomplished dynamically through the course of operation of the area serviced by the AS. The series of RADIUS messages, e.g. Accounting-Request(Start) and Access-Request messages from the NAS, induces a neighbor graph. Through analysis of these messages by the AS, the neighbor graph is easily created and maintained. When the attributes in a RADIUS message indicate that a session is continuing from a previous NAS, the AS MUST create an edge from the previous NAS to the new NAS in the neighbor graph. Each edge created SHOULD have some method for removal of the edge such as a timeout, or the use of a least recently used cache to ensure that 'outliers' (outliers are those edges that are NOT mobility paths through the network but are added due to discrete movements by the station) are removed from the graph in a timely fashion. Mishra et. al. [Page 5] INTERNET-DRAFT Context Caching 24 February 2003 2.2. NAS Neighbor graphs can also be computed locally at the NAS rather than globally at the AS. In this case, the creation and maintenance of the neighbor graph is similar to the process used at the AS, but is specific to the link layer technology being used. In the case of wireless networks such as those defined by the IEEE 802.11 specification [IEEE80211], the NAS examines the REASSOCIATION-REQUEST frame to determine the MAC address of the previous NAS. The NAS MUST now add an edge from the previous NAS to itself. Once again, the NAS SHOULD have some method for removal of the edge such as a timeout for reasons described earlier. 3. Usages of Neighbor Graphs 3.1. Context Caching Once one station has completed a high latency handoff, the mobility path of the station is added to the neighbor graph as an edge. There after, stations following that path can experience reduced latency. In the case that the neighbor graph is resident with the AS, the RADIUS extensions described in [Arbaugh2003] are used to notify the set of NASes to which the station may roam, i.e. the neighbors. In the case where the neighbor graph is resident with the NAS, context caching can be performed using a NAS specific method such as the inter access point protocol (IAPP) defined by the IEEE [IEEEIAPP]. 3.2. Management Information While neighbor graphs are primarily focused on providing fast roaming support via context caching, they can also provide insight into the mobility patterns of stations at the local (NAS) or global (AS) level. Because neighbor graphs are dynamic, they present a picture of the current network that can depict the mobility topology of the network. Mishra et. al. [Page 6] INTERNET-DRAFT Context Caching 24 February 2003 4. Security considerations Because context is being cached, the AS MUST ensure that a proper trust relation exists between the NAS before context information is cached. 5. IANA Considerations None 6. Normative references [Arbaugh2003] Arbaugh, W., "Experimental Handoff Extension to RADIUS", Work in Progress, draft-irtf-aaaarch-handoff-00.txt. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March, 1997. [RFC2865] Rigney, C., Rubens, A., Simpson, W., Willens, S., "Remote Authentication Dial In User Service (RADIUS)", RFC 2865, June 2000. [RFC2866] Rigney, C., "RADIUS Accounting", RFC 2866, June 2000. [RFC2869] Rigney, C., Willats, W., Calhoun, P., "RADIUS Extensions", RFC 2869, June 2000. [RFC3162] Aboba, B., Zorn, G., Mitton, D.,"RADIUS and IPv6", RFC 3162, August 2001. [IEEE8021X] IEEE Standards for Local and Metropolitan Area Networks: Port based Network Access Control, IEEE Std 802.1X-2001, June 2001. 7. Informative references [RFC2104] Krawczyk, H., Bellare, M., Canetti, R.,"HMAC: Keyed- Hashing for Message Authentication", RFC 2104, February 1997 [RFC2434] Alvestrand, H. and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998. Mishra et. al. [Page 7] INTERNET-DRAFT Context Caching 24 February 2003 [RFC2607] Aboba, B., Vollbrecht, J., "Proxy Chaining and Policy Implementation in Roaming", RFC 2607, June 1999. [RFC2716] Aboba, B., Simon, D., "PPP EAP TLS Authentication Protocol", RFC 2716, October 1999. [IEEEIAPP] Recommended Practice for Multi-Vendor Access Point Interoperability via an Inter-Access Point Protocol Across Distribution Systems Supporting IEEE 802.11 Operation, IEEE P802.11F/D5, January 2003. [IEEE802] IEEE Standards for Local and Metropolitan Area Networks: Overview and Architecture, ANSI/IEEE Std 802, 1990. [IEEE8021Q] IEEE Standards for Local and Metropolitan Area Networks: Draft Standard for Virtual Bridged Local Area Networks, P802.1Q, January 1998. [IEEE-02-758] Mishra, A., Shin, M., Arbaugh, W., Lee, I., Jang, K., "Proactive Caching Strategies for IAPP Latency Improvement during 802.11 Handoff", IEEE 802.11 Working Group, IEEE-02-758r1-F, November 2002. [IEEE-03-084] Mishra, A., Shin, M., Arbaugh, W., Lee, I., Jang, K., "Proactive Key Distribution to support fast and secure roaming", IEEE 802.11 Working Group, IEEE-03-084r1-I, http://www.ieee802.org/11/Documents/DocumentHolder/3-084.zip, January 2003. [8021XHandoff] Pack, S., Choi, Y., "Pre-Authenticated Fast Handoff in a Public Wireless LAN Based on IEEE 802.1X Model", School of Computer Science and Engineering, Seoul National University, Seoul, Korea, 2002. [IEEE8023] ISO/IEC 8802-3 Information technology - Telecommunications and information exchange between systems - Local and metropolitan area networks - Common specifications - Part 3: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications, (also ANSI/IEEE Std 802.3- 1996), 1996. [IEEE80211] Information technology - Telecommunications and information exchange between systems - Local and metropolitan area networks - Specific Requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Std. 802.11-1999, 1999. Mishra et. al. [Page 8] INTERNET-DRAFT Context Caching 24 February 2003 [MD5Attack] Dobbertin, H., "The Status of MD5 After a Recent Attack." CryptoBytes Vol.2 No.2, Summer 1996. [NTPAuth] Mills, D., "Public Key Cryptography for the Network Time Protocol", Internet draft (work in progress), draft-ietf- stime-ntpauth-05.txt, November 2002. Acknowledgments The authors would like to thank Bernard Aboba for many helpful conversations concerning this work. Authors' Addresses Arunesh Mishra Department of Computer Science University of Maryland, College Park A.V. Williams Building College Park, MD 20742 EMail: arunesh@cs.umd.edu Min-ho Shin Department of Computer Science University of Maryland, College Park A.V. Williams Building College Park, MD 20742 EMail: mshin@cs.umd.edu William A. Arbaugh Department of Computer Science University of Maryland, College Park A.V. Williams Building College Park, MD 20742 EMail: waa@cs.umd.edu Phone: 301.405.2774 Insun Lee Samsung Electronics P.O. Box 111 Suwon 440-600 South Korea Email: islee@sait.samsung.co.kr Phone: 82.31.280.8195 Mishra et. al. [Page 9] INTERNET-DRAFT Context Caching 24 February 2003 Kyunghun Jang Samsung Electronics P.O. Box 111 Suwon 440-600 South Korea Email: khjang@samsung.com Phone: 82.31.280.8195 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any intellectual property 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; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards- related documentation can be found in BCP-11. Copies of claims of rights made available for publication 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 implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. Full Copyright Statement Copyright (C) The Internet Society (2003). 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 Mishra et. al. [Page 10] INTERNET-DRAFT Context Caching 24 February 2003 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." Mishra et. al. [Page 11] INTERNET-DRAFT Context Caching 24 February 2003 Expiration Date This memo is filed as , and expires August 22, 2003. Mishra et. al. [Page 12]