DNA Working Group S. Narayanan Internet-Draft Panasonic Expires: August 21, 2005 February 20, 2005 Recommendations to achieve efficient Router Reachability Detection in IPv6 networks draft-narayanan-dna-rrd-01.txt Status of this Memo By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. 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. This Internet-Draft will expire on August 21, 2005. Copyright Notice Copyright (C) The Internet Society (2005). All Rights Reserved. Abstract Detecting Network Attachment (DNA) requires the rapid detection of link identity and validation of the current IP configuration [3]. Even though acquiring the configuration for a new link is outside the scope of DNA, mechanisms that can accomplish both DNA and collect possible configuration information about the current link will prove to be very useful in rapidly changing network environments. RFC 2461 defines a Router Discovery (RD) procedure [1] to learn about the available access routers on an L3 link. RFC 2461 [1] also defines Neighbor Discovery (ND) procedure to discover neighbors in the same Narayanan Expires August 21, 2005 [Page 1] Internet-Draft DNAv6 RRD February 2005 link. This draft recommends a few simple modifications to the Router Discovery (RD) procedure defined by RFC 2461 [1] that can lead to efficient Router Reachability Detection (RRD), while enabling the quick learning of other available routers if the current router is not available. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terms and Abbreviations . . . . . . . . . . . . . . . . . . . 4 3. Neighbor Discovery and Router Discovery . . . . . . . . . . . 4 4. Router Reachability Detection . . . . . . . . . . . . . . . . 4 4.1 Router Reachability Detection procedure . . . . . . . . . 5 4.2 Identify the Current Access Router in RS message . . . . . 5 4.3 Higher priority for current access router in responding to RS . . . . . . . . . . . . . . . . . . . . . 6 4.4 Identify received RS messages in RA . . . . . . . . . . . 6 4.5 Token bucket based rate limiting RA messages . . . . . . . 6 5. New optional headers for RS/RA messages . . . . . . . . . . . 7 5.1 Link local address option . . . . . . . . . . . . . . . . 7 5.2 Current Access Router option . . . . . . . . . . . . . . . 8 6. Security Considerations . . . . . . . . . . . . . . . . . . . 8 7. Constants . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9.1 Normative References . . . . . . . . . . . . . . . . . . . . 9 9.2 Informative References . . . . . . . . . . . . . . . . . . . 9 Author's Address . . . . . . . . . . . . . . . . . . . . . . . 10 A. Complete DNA solution with RRD & Probabilistic FastRA . . . . 10 B. Comparisons to ECS and LCS . . . . . . . . . . . . . . . . . . 11 Intellectual Property and Copyright Statements . . . . . . . . 13 Narayanan Expires August 21, 2005 [Page 2] Internet-Draft DNAv6 RRD February 2005 1. Introduction When operating in changing environments, IPv6 hosts may experience variations in reachability or configuration state over time. For hosts accessing the Internet over wireless media, such changes may be caused by changes in wireless propagation or host motion. In these and other cases, IP addressing and default routing configuration may be invalid, which prevents successful communication with IP nodes on the global Internet. Detecting Network Attachment (DNA) in IPv6 is the task of checking for changes in the validity of a host's IP configuration. Changes may occur on establishment or disconnection of a link-layer. For newly connected interfaces, need to confirm if their current configuration is valid. DNA focuses on determining whether the current configuration is valid, leaving the actual practice of re-configuration to other subsystems if the current configuration is invalid. This document identifies the requirements to achieve efficient router discovery and reachability detection and makes recommendations in terms of modifications to the Router Discovery procedure defined by [1]. The proposed solution in this draft is built upon the following design principles: The link identifier used by each IP node [3] in a link does not need to be the same as long as they can efficiently identify if the link is the same link (belonging to the identifier used by the IP node) or not after attachment . This link identifier, as suggested by this draft, is . Note that it is possible to modify the recommendations in this draft to use a different identifier that can be used to uniquely identify the current access router. The IP nodes are proactive in determining network attachment by sending a Router Solicitation message. This avoids reducing the Router Advertisement interval significantly to achieve efficient detection of network attachment if the IP nodes remain reactive by depending on unsolicited Router Advertisements. Narayanan Expires August 21, 2005 [Page 3] Internet-Draft DNAv6 RRD February 2005 A Link Up notification from layer-2 is available to initiate the proactive transmission of a Router Solicitation message for the IP node to be proactive in determining network attachment. 2. Terms and Abbreviations There is an existing DNA terminology draft [6]. This draft does not introduce any new terminology not already used by existing drafts. 3. Neighbor Discovery and Router Discovery The Neighbor Discovery procedure defined by RFC 2461 [1] involves the exchange of NS (Neighbor Solicitation) and NA (Neighbor Advertisement) messages between two IP nodes. The responding host is required to send the Neighbor Advertisement message using unicast addressing, thus the NA acts as a confirmation to the receipt of NS. Its widely accepted that such an exchange can also be used as a bi-directional reachability detection mechanism. On the other hand, the Router Discovery procedure [1] requires a RA (Router Advertisement) message sent to a multicast address in response to the RS (Router Solicitation) message. Unlike the Neighbor Discovery procedure when the RA message is received, the source of the RS message can not ascertain whether the RA message is in response to its RS message. Even though RFC 2461 [1] allows for the possibility of a unicast RA response, it does not mandate it. In order to avoid responses from multiple routers at the same time RFC 2461 [1] requires routers wait for a random delay between 0 and MAX_RA_DELAY_TIME while not sending more than one multicast RA in MIN_DELAY_BETWEEN_RAS time. (Note: The values for these timers are modified in RFC 3775 [2] to lower values.) Note that the response to a RS message can be sent by any/all of the routers on the link. If a router that is not the current access router responds first the IP node can not be sure whether to accept the reponse or to wait in order to provide a chance for it's current router to respond. 4. Router Reachability Detection In order to achieve rapid network attachment detection, this draft suggests the following requirements to be met by the Router Discovery (RD) procedure. Narayanan Expires August 21, 2005 [Page 4] Internet-Draft DNAv6 RRD February 2005 1) The initiator of the RD procedure MUST be able to verify that the response message was generated in response to its solicitation message to confirm bi-directional reachability with the router. 2) The current access router of the initiator MUST have a high likelihood of responding to the router solicitation message. 3) The rate limiting mechanism SHOULD be flexible to allow for the possibility of multiple consecutive RS messages arriving at the routers within MIN_DELAY_BETWEEN_RAS time. This document proposes the following modifications to the RD procedure and defines a new procedure called Router reachability Detection. 4.1 Router Reachability Detection procedure The Router Reachability Detection procedure works as follows: when an IP node wants to find out if its current access router is accessible, it generates a RS message and it MUST include a current access router option in the RS message containing the address of the current access router (Note: This address may be the link-local address of the router) and MUST included its current global prefix using the prefix option defined in RFC 2461 [1]. The IP node SHOULD also include its own link layer address using the tentative source link layer address option (SLLAO) in the RS message it sends. The routers respond to the RS message within the random delay generated as described in Section 4.3 and Section 4.5. If multiple RS messages are received during the random delay time, the router MUST note down the link layer addresses if present in the RS message SLLAO and the link local address of the source of the RS messages. The router MUST include the link-layer address of the source of RS messages using the target link layer option and link local address of the source of the RS message using the target link-local address option headers in the RA message. Using this procedure, an IP node can detect if its current router is still available and if not, the IP node will receive RA messages from other routers in the network. With the receipt of the RA message the IP node can also confirm bi-directional reachability to the router that sent the RA message based on the sources of RS messages identified in that particular RA message. 4.2 Identify the Current Access Router in RS message One new option header is defined by this draft in section Section 5.2 named Current Access Router. The RS message generated by an IP node Narayanan Expires August 21, 2005 [Page 5] Internet-Draft DNAv6 RRD February 2005 MUST include at least one newly defined current access router option and also the current prefix information using the prefix option defined in RFC 2461 [1] to provide the current access router and prefix information to the routers receiving the RS message. The usage of this options is discussed in Section 4.1. 4.3 Higher priority for current access router in responding to RS Two new variables named MaxDelayForCurrRouter and MinDelayForOtherRouters are defined for routers. The current access router identified in the RS message MUST generate a random delay between 0 and MaxDelayForCurrRouter, while all other routers MUST generate the random delay between MinDelayForOtherRouters and MAX_RA_DELAY_TIME. The MinDelayForOtherRouters <= MaxDelayForCurrRouter. These two variables can be controlled to increase the likelihood of the current router responding first. For example, if the MaxDelayForCurrRouter = MinDelayForOtherRouter = X milli-seconds < MAX_RA_DELAY_TIME, the probability of current router responding before other routers is 1, provided that the current router didn't transmit an RA within MIN_DELAY_BETWEEN_RAS time (This problem of delay introduced by the rate limiting variable MIN_DELAY_BETWEEN_RAS is addressed in Section 4.5). The RECOMMENDED value for the both MaxDelayForCurrRouter and MinDelayForOtherRouters is zero. 4.4 Identify received RS messages in RA The Target Link Layer address defined by RFC 2461 [1] will be used in the RA message for including all the link-layer addresses and/or the newly defined option header in section Section 5.1 to include the link-local addresses of the IP nodes from which RS messages were received. This information in the RA message will be useful for the IP nodes to verify bi-directional reachability to routers. The router learn the link layer address of the source of the RS message from the tentative source link layer address (SLLAO) option in the RS message. The usage of these options is discussed in Section 4.1. 4.5 Token bucket based rate limiting RA messages Instead of rate-limiting the number of multicast RA messages by restricting one message per MIN_DELAY_BETWEEN_RAS as describe by RFC 2461 [1], it is recommended that the router maintain a token bucket of size MAX_RA_TOKEN_BUCKET. This recommedation is made to avoid the MIN_DELAY_BETWEEN_RAS delay in responding to a RS message if the RS message was received immediately after a RA message was sent. Implementing the MIN_DELAY_BETWEEN_RAS limit will affect the network attachment delay when more than one IP node need to detect network Narayanan Expires August 21, 2005 [Page 6] Internet-Draft DNAv6 RRD February 2005 attachment around the same time. The token bucket mechanism is implemented as follows. A token is added to the bucket at the rate of RA_TOKEN_BUCKET_RATE. When the router has to send a RA message (after the random delay introduced by Section 4.3 has expired)it checks the bucket for a token, if the bucket is empty, the router waits until a token is added to the bucket. If a token is available, the router removes the token from the bucket and sends the RA message. Any token generated when the bucket is full MUST be discarded. 5. New optional headers for RS/RA messages 5.1 Link local address option 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + Target link local address + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type TBA Length 8 bit unsigned integer indicating the length in octests of the option excluding the type and length fields. Set to 8. Target Link Local address The link local address of the source of the RS message. Narayanan Expires August 21, 2005 [Page 7] Internet-Draft DNAv6 RRD February 2005 Description This option MUST be used only in the RA message. It provides the receiver with an acknowledgment to its RS message. 5.2 Current Access Router option 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + Current access router address + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type TBA Length 8 bit unsigned integer indicating the length in octests of the option excluding the type and length fields. Set to 8. Current access router address The IPv6 address of the current access router. Description This option MUST be used only in the RS message. 6. Security Considerations Since this document depends on the existing protocol mechanisms defined in RFC 2461 [1], all the security consideration mentioned in RFC 2461 are applicable to this draft. The token bucket based rate Narayanan Expires August 21, 2005 [Page 8] Internet-Draft DNAv6 RRD February 2005 limiting mechanism suggested here makes a DOS attack possible, but the constraints placed by the constant MAX_RA_TOKEN_BUCKET can control the impact of such DOS attacks because after producing consecutive messages based on the tokens left in the bucket, the responses will be limited to one every MIN_DELAY_BETWEEN_RAS time. Allowing for MAX_RA_TOKEN_BUCKET number of RA messages to be sent almost consecutively makes efficient network attachment detection possible when a series of upto MAX_RA_TOKEN_BUCKET IP nodes move into the area covered by particular access router. 7. Constants The following values are suggested for the constants defined in this document (these values need to be refined based on the implementation and simulation experience): MAX_RA_TOKEN_BUCKET: 20 MaxDelayForCurrRouter: 50 ms MinDelayForOtherRouters: 50 ms 8. Acknowledgments I would like to express my sincere appreciation to Dave Braun, Greg Daley, Greg Perkins and Eunsoo Shim for their valuable comments in improving this draft. 9. References 9.1 Normative References [1] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for IP Version 6 (IPv6)", RFC 2461, December 1998. [2] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in IPv6", RFC 3775, June 2004. [3] Choi, J. and G. Daley, "Detecting Network Attachment in IPv6 Goals", draft-ietf-dna-goals-02.txt (work in progress), September 2004. 9.2 Informative References [4] Narayanan, S., Daley, G. and N. Montavont, "Detecting Network Attachment in IPv6 - Best Current Practices for hosts", draft-narayanan-dna-hosts-bcp-00 (work in progress), February Narayanan Expires August 21, 2005 [Page 9] Internet-Draft DNAv6 RRD February 2005 2005. [5] Daley, G., Narayanan, S. and G. Perkins, "Detecting Network Attachment in IPv6 - Best Current Practices", draft-daley-dna-prob-fastra-00 (work in progress), February 2005. [6] Yamamoto, S., "Detecting Network Attachment Terminology", draft-yamamoto-dna-term-00 (work in progress), February 2004. [7] Manner, J. and M. Kojo, "Mobility Related Terminology", draft-ietf-seamoby-mobility-terminology-06 (work in progress), February 2004. Author's Address Sathya Narayanan Panasonic Digital Networking Lab Two Research Way, 3rd Floor Princeton, NJ 08536 USA Phone: 609 734 7599 EMail: sathya@Research.Panasonic.COM URI: Appendix A. Complete DNA solution with RRD & Probabilistic FastRA The mechanisms recommended by this internet-draft achieves efficient verification of the current configuration when the IP node has not moved away from its current link. It also confirms bi-directional reachability with the current access router in the same scenario. Intergrating this method with a fast router advertisement method will basically provide the required complete solution for the DNA problem [3]. In this appendix, a brief description on how such integration can be done with probabilistic fast router advertisement[5] is presented. The following simple modifications to probabilistic fastra are needed to combine with RRD: When a current access router is identified in the RS message, the current access router MUST set its probability of responding to 1. When a current access router is identified in the RS message, other routers that have knowledge of the presence of that access router in the link, SHOULD follow the delay constraints specified Narayanan Expires August 21, 2005 [Page 10] Internet-Draft DNAv6 RRD February 2005 by RFC2461 [1]. These other routers MAY elect to follow the probabilities for P(slot_i) as specified by the [5]. When a current access router is identified in the RS message, other router that do not have knowledge of the presence of that access router in the link, SHOULD follow the recommedation in [5] with the following modification to the delay calculation. If SlotNumber = 0; then delay = 10 ms; else delay = slotNumber * ProbFastRASlotTime. Appendix B. Comparisons to ECS and LCS This section presents a simple analysis based on the work done in [4] to compare the proposed Router Reachability Detection scheme with the well know eager configuration switching (ECS) and lazy configuration switching (LCS) schemes. The ECS mechanism accepts the first RA received (solicited or unsolicited) from the network and if the RA contains different configuration from the IP node's current configuration, the IP node changes its configuration based on the newly received RA. LCS mechanism attempts reachability testing using a NS-NA exchange with the current router before soliciting new router information or before accepting the new Router Advertisement. A brief analysis of the average cost introduced by the schemes LCS and ECS are given in [4]. Assuming the following costs for the operations: N - Reachability test success (with NS/NA) T - Reachability test failure (timeout) R - Router Advertisement reception (This will be the average random delay introduced for responding to the RS message) C - Host reconfiguration The probability that there is a L3 link change given that the L2 point of attachment has changed is p = (number of L3 links)/(number of L2 Point of attachment) If nr represents the number of routers in each L3 link and NR the total number of routers. The probability of the received RA being from a router different from the current access router is p1 = (sum of all (nr - 1)/ NR) Note that if there is a single router on a L3 link, then (nr - 1) Narayanan Expires August 21, 2005 [Page 11] Internet-Draft DNAv6 RRD February 2005 will be zero leading to p1 = 0 The mean cost of Eager Configuration switching is: Cost(ECS)= (R + C) * (p + p1) And the cost of Lazy switching is: Cost(LCS)= (T + R + C) * p + (1 - p) * N To extend this analysis to the Router Reachability Detection (RRD) procedure requires the definition of a new variable p2 which is the probability that the current access router will respond to the Router Solicitation message first. This probability is controlled by the choice of values for the variable MaxDelayForCurrRouter and MinDelayForOtherRouters. (MaxDelayForCurrRouter - MinDelayForOtherRouters) * (nr -1 ) p2 =1 - ------------------------------------------------------------ MAX_RA_DELAY_TIME * nr Note that, if MaxDelayForCurrRouter = MinDelayForOtherRouters, then p2=1, while if MinDelayForOtherRouters = 0 and MaxDelayForCurrRouter = MAX_RA_DELAY_TIME (which will be the values for the current Router Discovery scheme defined by RFC 2461 [1]), then p2 = 1 / nr. If the cost of receiving a Router Advertisement is R1 if the current router is available (This will be the average random delay (0, MaxDelayForCurrRouter)) and R2 if the current router is not available (This will be the average random delay (MinDelayForOtherRouter, MAX_RA_DELAY_TIME)), then Cost(RRD) = R2 * p + R1 * (1 - p) + p * C + p1 * (1-p2) * C It can be seen from this expression that when p1 = 0, (i.e. when you don't have multiple routers in the same L3 link), RRD has the same cost as ECS. When p1 is non-zero, and if p2 is maintained at 1, RRD performs better than ECS by avoiding the erroneous configuration changes. This improvement in cost is significant only if C is large compared to other costs. Narayanan Expires August 21, 2005 [Page 12] Internet-Draft DNAv6 RRD February 2005 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights 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; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat 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 implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Narayanan Expires August 21, 2005 [Page 13] Internet-Draft DNAv6 RRD February 2005 Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Narayanan Expires August 21, 2005 [Page 14]