Network Working Group G. Daley Internet-Draft Monash University CTIE Expires: August 11, 2005 S. Narayanan G. Perkins Panasonic February 10, 2005 A probabilistic scheme for fast Router Advertisement responses in IPv6 draft-daley-dna-prob-fastra-00.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 11, 2005. Copyright Notice Copyright (C) The Internet Society (2005). All Rights Reserved. Abstract The IPv6 Neighbour Discovery RFC provides for random delays of between 0 to 500 milliseconds, in order to spread responses to solicitations when multiple routers exist on a link. This document describes an alternative scheme for responding to Router Solicitations which estimates the number of routers on the link, and aims to reduce the delay spread for responding Router Advertisements. Daley, et al. Expires August 11, 2005 [Page 1] Internet-Draft Probabilistic FastRA February 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Probabilistic Fast Router Advertisement . . . . . . . . . . 3 3. Router estimation . . . . . . . . . . . . . . . . . . . . . 3 4. Delay calculation . . . . . . . . . . . . . . . . . . . . . 4 5. Discussion of heuristic . . . . . . . . . . . . . . . . . . 5 6. Rate limiting responses . . . . . . . . . . . . . . . . . . 5 7. Message Format . . . . . . . . . . . . . . . . . . . . . . . 5 8. Configuration . . . . . . . . . . . . . . . . . . . . . . . 6 9. Protocol constants . . . . . . . . . . . . . . . . . . . . . 6 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . 7 11. Security Considerations . . . . . . . . . . . . . . . . . . 7 12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 8 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 13.1 Normative References . . . . . . . . . . . . . . . . . . . 8 13.2 Informative References . . . . . . . . . . . . . . . . . . 8 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 8 A. Implementation status . . . . . . . . . . . . . . . . . . . 9 Intellectual Property and Copyright Statements . . . . . . . 10 Daley, et al. Expires August 11, 2005 [Page 2] Internet-Draft Probabilistic FastRA February 2005 1. Introduction Responding to Router Solicitations quickly allows a router to advertise up-to-date configuration information to hosts which are either discovering routers or checking their current configuration. The IPv6 Neighbour Discovery RFC [2] requires a random delay of between 0 and 500ms before responding to a Router Solicitation (RS) with a Router Advertisement (RA). Simultaneous transmissions of Router Advertisements by multiple routers may cause MAC congestion, or even packet loss in some environments. The random delay described in RFC 2461 prevents routers from continually sending RAs at the same time, and therefore causing congestion. While some delay is needed to prevent continual collision by responding routers, the delays caused by the existing scheme induce a mean 250ms delay before responses are received. An alternative scheme described in this document allows for a more constrained spread of delays by estimating the number of routers on the link, and randomly choosing a transmission delay within a small range of values. 2. Probabilistic Fast Router Advertisement Probabilistic Fast Router Advertisement attempts to provide sufficiently fast Router Solicitation responses based only on a rough estimate of the number of routers on a link. Routers do not coordinate their responses, nor know anything about peers, other than that another (purported) router is advertising. This allows routers which do not know or trust each other to make choices about the router occupancy on the list with bounded worst case performance, and good usualcase performance. 3. Router estimation On each link a router is likely to receive periodic Router Advertisements from most or all of the other routers on a link. While routers do not use RAs for configuration, they may be used to provide an indication of the number of routers occupying a link. This router estimate is used by Probabilistic FastRA in order to calculate RS response delays when scheduling Router Advertisement transmission. Daley, et al. Expires August 11, 2005 [Page 3] Internet-Draft Probabilistic FastRA February 2005 In order to provide an accurate estimate, Fast Routers MUST set the Probabilistic Fast Routers Flag in the Router Advertisement header as described in Section 7. Probabilistic Fast Routers SHOULD only count routers advertising this flag in their estimate of fast routers. Routers inspecting Router Advertisements SHOULD store the link-local source address, advertisement intervals and last transmission time of a (bounded) number of routers on the link. The number of routers so stored provides the basis of the estimate used in scheduling responses, with routers including themselves in the estimate. Routers always consider themselves to be present, even if they do not receive their own advertisements. In order to provide robustness against unknown routers and spurious router entries, the router bounds its estimate between MIN_PROB_ROUTERS and MAX_PROB_ROUTERS. The delay so calculated is stored in the variable RouterEst. This ensures that a Probabilistic FastRA router always acts as if there was at least one other router on the link, even if it has seen no other routers. Also, in order to facilitate estimation by other routers, a fast router SHOULD advertise periodically, and MAY include an Advertisement Interval Option in its multicast advertisement [3]. 4. Delay calculation When a router receives an RS it processes it in the way described in section 6.2.6 of the Neighbour Discovery RFC [3]. Instead of randomly delaying for 0 to MAX_RA_DELAY_TIME, though, the router may use the algorithm described in this section. As described above RouterEst is the estimate of the number of routers on a link. RouterEst is in the range: [MIN_PROB_ROUTERS,MAX_PROB_ROUTERS]. Probabilistic FastRA requires routers to delay by choosing one of RouterEst + 1 slots, in the range from [0, RouterEst], where the delay duration is: slotNumber * ProbFastRASlotTime Slot choices are based on probabilities, which depend on RouterEst. The first slot (slot 0) is given greater weight, and all other slots equal weight from the remaining probability: Daley, et al. Expires August 11, 2005 [Page 4] Internet-Draft Probabilistic FastRA February 2005 P(slot_0) = 1/RouterEst P(slot_i) = (RouterEst - 1)/(RouterEst^2), for all i [1,RouterEst] 5. Discussion of heuristic The algorithm presented above provides some random delay, which is tied to the link's current router occupancy. This limits the effect of collisions, while providing bounded response scheduling delays. Selection of zero delay is preferred, particularly with low estimates of routers (50% if only one or two routers). This is deliberate, since it allows a fast mean response time, but allows re-ordering upon retransmission if slot collisions and consequent MAC collision or contention occur. When only one router operates, the response time maximum is 2 slot times (default 40ms) with 25% probability, the expected delay is 0.75 slot times ( 15ms ). Where two routers operate, the expected delay reduces to 0.3125 slot times ( 6.25ms ) . With two routers though, there is a 37.5% chance of a slot collision, where both routers choose the same slot. For larger numbers of routers, there is the likelihood of at least one slot collision. Particularly for odd-numbered estimates of routers, there is a high likelihood that (at least) one of the routers will pick a slot which is not chosen by other routers. These singleton responses may be successfully transmitted in some environments even if slot collisions from other routers' transmissions produce garbled, lost or delayed RA reception on other computers. The estimates provided for router numbers are bounded for this algorithm. This may make it inappropriate on links with many advertising routers. 6. Rate limiting responses It is necessary to limit the number of fast Router Advertisements sent by a router within an interval. It is therefore RECOMMENDED that hosts use a token bucket scheme to allow not allow more than ProbFastRABucket Router advertisements to be outstanding, with transmission tokens being replenished once every ProbFastRATokInterval. 7. Message Format This document specifies a new flag to be sent in Router Daley, et al. Expires August 11, 2005 [Page 5] Internet-Draft Probabilistic FastRA February 2005 Advertisements in order to identify members of the Fast Router set. This is described below: 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 | Code | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cur Hop Limit |M|O|H|Prf|F| | Router Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reachable Time | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Retrans Timer | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Options ... +-+-+-+-+-+-+-+-+-+-+-+- The new field "F" describes the Probabilistic Fast Router Flag. This flag is set by routers participating in Probabilistic FastRA. 8. Configuration Probabilistic FastRA runs per-interface, and its use SHOULD be configurable on a per-interface basis. All configuration variables listed below SHOULD be configurable on a per-interface basis. The configuration parameter ProbFastRASlotTime is described in this document. It provides the delay between adjacent scheduling slots for responding router advertisements. This parameter SHOULD default to PROB_FASTRA_SLOT_TIME. The default for this parameter MAY vary based on the class of interface, and the transmission medium. ProbFastRABucket provides the maximum number of fast Router Advertisements which may be transmitted at any time. It should be a positive integer, if Probabilistic FastRA is in use. It defaults to PROB_FASTRA_BUCKET. ProbFastRATokInterval number of milliseconds defining the time it takes to increase the number of tokens by one. It defaults to PROB_FASTRA_TOKEN_INTERVAL. For intervals under a second, a router MAY group intervals together and add multiple tokens to the bucket each time the longer interval's timer fires. 9. Protocol constants MIN_PROB_ROUTERS: 2 Daley, et al. Expires August 11, 2005 [Page 6] Internet-Draft Probabilistic FastRA February 2005 MAX_PROB_ROUTERS: 5 PROB_FASTRA_SLOT_TIME: 20 (milliseconds) PROB_FASTRA_BUCKET: 10 PROB_FASTRA_TOKEN_INTERVAL: 500 (milliseconds) 10. IANA Considerations A protocol flag (1 bit - suggest 0x04) in the Router Advertisement's "reserved and flags" octet is required to be allocated to support Probabilistic FastRA identification. 11. Security Considerations Probabilistic FastRA does not vouch for the validity of Router Advertisements it receives, nor does it check their security. Each router up to the fourth (fifth including itself) has an impact on the advertising state of the other routers on the link, but cannot force advertisements at a particular time, nor can they predict which of the slots will be used by another router. The state required to store router information is thus bounded, and only four other routers need to be stored (information from other routers may be discarded). Router information received may be spoofed, and recipient routers SHOULD be careful in handling Advertisement Intervals and lifetimes for routers. They SHOULD consider timing out routers based on the default advertised lifetime if no other measures are available (9000 seconds) [2]. Where Advertisement Interval options are used, robustness to packet loss is desirable, and the router should remain in the list for at least two intervals. This may extend the duration of an attack by spurious routers, but cannot cause a more severe delays without transmitting Router Advertisements itself. The maximum expected duration before an RA is scheduled in this case is bounded at 2.4 slots (around 48ms), even when every other router is bogus. Where this is an acceptable delay, no other action needs to be taken. Where two real Probabilistic FastRA routers exist on the link, the expected delay comes to around 1.4 slots (about 28 ms), even if all other routers are bogus. Daley, et al. Expires August 11, 2005 [Page 7] Internet-Draft Probabilistic FastRA February 2005 12. Acknowledgments 13. References 13.1 Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for IP Version 6 (IPv6)", RFC 2461, December 1998. [3] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in IPv6", RFC 3775, June 2004. [4] Arkko, J., Kempf, J., Sommerfeld, B., Zill, B. and P. Nikander, "SEcure Neighbor Discovery (SEND)", draft-ietf-send-ndopt-06 (work in progress), July 2004. 13.2 Informative References Authors' Addresses Greg Daley Centre for Telecommunications and Information Engineering Department of Electrical and Computer Systems Engineering Monash University Clayton, Victoria 3800 Australia Phone: +61 3 9905 4655 EMail: greg.daley@eng.monash.edu.au Sathya Narayanan Panasonic Digital Networking Lab Two Research Way, 3rd Floor Princeton, NJ 08536 USA Phone: +1 609 734 7599 EMail: sathya@Research.Panasonic.COM URI: Daley, et al. Expires August 11, 2005 [Page 8] Internet-Draft Probabilistic FastRA February 2005 Greg Perkins Panasonic Digital Networking Lab Two Research Way, 3rd Floor Princeton, NJ 08536 USA EMail: gmp@Research.Panasonic.COM URI: Appendix A. Implementation status This has been implemented under RADVD. Daley, et al. Expires August 11, 2005 [Page 9] Internet-Draft Probabilistic FastRA 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. Daley, et al. Expires August 11, 2005 [Page 10] Internet-Draft Probabilistic FastRA February 2005 Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Daley, et al. Expires August 11, 2005 [Page 11]