DNA Working Group B. Pentland Internet-Draft Monash University CTIE Expires: August 15, 2005 February 14, 2005 An Overview of Approaches to Detecting Network Attachment in IPv6 draft-dnadt-dna-discussion-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 15, 2005. Copyright Notice Copyright (C) The Internet Society (2005). All Rights Reserved. Abstract This document is a discussion of potential solutions to the problem of rapidly and reliably detecting attachment to a network and determining when host configuration change is required. Pentland Expires August 15, 2005 [Page 1] Internet-Draft DNA Solution Overview February 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Objectives for a Solution to the Problem of DNA . . . . . . . 4 4. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 4 5. The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 4 6. Determining Whether Link Change Has Occurred . . . . . . . . . 4 6.1 Techniques that add information to the RA. . . . . . . . . 5 6.1.1 Explicit Link Identifier. . . . . . . . . . . . . . . 5 6.1.2 Complete Router Advertisement. . . . . . . . . . . . . 6 6.2 Techniques That Ask a Question in the RS. . . . . . . . . 6 6.2.1 Requested Landmark. . . . . . . . . . . . . . . . . . 6 6.2.2 Priority Landmark. . . . . . . . . . . . . . . . . . . 7 6.2.3 Hybrid Landmark. . . . . . . . . . . . . . . . . . . . 7 7. Fast Responses to Solicitation . . . . . . . . . . . . . . . . 8 7.1 Fast Router Discovery. . . . . . . . . . . . . . . . . . . 8 7.2 Simple Fast RA. . . . . . . . . . . . . . . . . . . . . . 8 7.3 Deterministic Fast RA. . . . . . . . . . . . . . . . . . . 8 7.4 Negotiation-free Deterministic Fast RA. . . . . . . . . . 9 7.5 Probabilistic Fast RA. . . . . . . . . . . . . . . . . . . 9 8. Dealing with Legacy Routers . . . . . . . . . . . . . . . . . 10 9. Putting Things Together . . . . . . . . . . . . . . . . . . . 10 9.1 Requested Landmark with Negotiation-free Deterministic Fast RA . . . . . . . . . . . . . . . . . . . . . . . . . 11 9.1.1 How the goals are met . . . . . . . . . . . . . . . . 13 9.2 CompleteRA with Probabilistic Fast RA . . . . . . . . . . 14 9.2.1 How the goals are met . . . . . . . . . . . . . . . . 15 9.3 Prefix-based LinkID with Fast Router Discovery . . . . . . 16 9.3.1 How the goals are met . . . . . . . . . . . . . . . . 17 10. On the Wire Costs . . . . . . . . . . . . . . . . . . . . . 18 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . 20 12. Security Considerations . . . . . . . . . . . . . . . . . . 21 12.1 General Threats . . . . . . . . . . . . . . . . . . . . . 21 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 22 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 14.1 Normative References . . . . . . . . . . . . . . . . . . . . 22 14.2 Informative References . . . . . . . . . . . . . . . . . . . 22 Author's Address . . . . . . . . . . . . . . . . . . . . . . . 23 Intellectual Property and Copyright Statements . . . . . . . . 24 Pentland Expires August 15, 2005 [Page 2] Internet-Draft DNA Solution Overview February 2005 1. Introduction This document represents, an overview of the discussion of the DNA design team on potential solutions to the problem of rapid and reliable network attachment detection. The design team was comprised of JinHyeock Choi, Tero Kauppinen, James Kempf, Sathya Narayanan, Erik Nordmark, and Brett Pentland. While we were unable to settle on a single solution, a number of different techniques were discussed at length, and this document provides a summary of them, including their advantages and disadvantages. In general, it was felt that fast attachment detection will require some kind of hint from layer two. The link layer event notifications draft [13], provides a discussion of layer two information available from a number of link types. Though it talks about "link-up" and "link-down", only link-up is considered here, for its utility in triggering a router solicitation from a host. In considering DNA, we have discussed how to get to the point where a host knows whether or not its IP configuration is likely to be valid, and has enough information to be able to start reconfiguration if necessary. At the end of "DNA" it either knows that it is connected to the same link as its current configuration implies, or it knows that it's connected to a new link, its IP configuration is invalid, as it has at least one prefix that it can use for Stateless Address Auto-configuration, if appropriate. It might also just use this as a trigger to start DHCP and/or any higher layer authorization/ authentication as required. 2. Terminology The following terms are used throughout the document Link - As defined in RFC 2461 [2]. Landmark - Some attribute that may be associated with a specific link such as a prefix or global router address. Link Identifier - A consistent identifier used in some way by all routers on a link to allow hosts to distinguish the link from other links. Pentland Expires August 15, 2005 [Page 3] Internet-Draft DNA Solution Overview February 2005 3. Objectives for a Solution to the Problem of DNA Because detecting network attachment will frequently happen on a network that a host has not seen before, information about that network will be required in order to configure addresses, etc. for future communication. The usual mechanism for obtaining this information is the Router Advertisement. A solicitation will be required in order to take advantage of hints from lower layers and speed up the detection process. It was felt that by crafting the information in the solicitation and advertisement, a single RS/RA exchange should be sufficient for DNA. In order to detect attachment rapidly, RA response should be as fast as possible. To this end, a DNA protocol ideally should not include any timer-induced delays for the first RA in response to an RS, though if a technique is sufficiently superior in other areas, some delay may be acceptable. 4. Assumptions - All of the routers on a link can be expected to receive packets sent to the "all-routers" multicast address (ff02::2) with some packet-loss probability < 1. - Hosts with interfaces that can connect to more than one link concurrently are able to distinguish packets from the separate links and thus abstract the link connections as separate virtual interfaces. 5. The Problem Given the above objectives, the problem to be solved can then be broken into two parts: 1. Crafting the information in the RS/RA exchange to allow accurate determination of whether a link change has occurred, necessitating a change to existing configuration, and including the necessary prefixes, etc. to allow those configuration changes to be made if needed. 2. Ensuring that an RA is received as rapidly as possible in response to solicitation. 6. Determining Whether Link Change Has Occurred There are a number of ways that the RFC 2461 RS/RA exchange could be modified to allow unambiguous determination of whether configuration Pentland Expires August 15, 2005 [Page 4] Internet-Draft DNA Solution Overview February 2005 change is required with a single exchange. These may be broadly divided into two classes: 1. Techniques that add information to the RA to allow hosts to make a correct decision. 2. Techniques that add information to the RS to ask a question of routers on the link, getting back an answer in the RA. 6.1 Techniques that add information to the RA. 6.1.1 Explicit Link Identifier. The routers on a link, by some mechanism, agree on a single identifier for the link that is different from any corresponding identifier used on another link that a host is likely to transition to directly. The identifier would then be included in router advertisements to allow hosts to immediately recognise whether this link is the same as the one they believe themselves to be connected to. Link Identifier techniques have an associated cost of needing a (secure) mechanism for the routers to come to agreement on the value of the link ID and also a means to change it if necessary without confusing the hosts on the link. 6.1.1.1 Random Link Identifiers. There are a number of options for the identifier. It could be simply a random number carried in a new advertisement option. This is quite simple, independent of changes to prefixes or routers on a link, but takes some extra bytes per RA and has a non-zero probability of there being multiple links using the same identifier. 6.1.1.2 Prefix Based Link Identifiers. A global prefix is another possible candidate for use as a Link Identifier. This would have the advantage of being unique, requires no additional RA bytes if a router is already advertising the prefix and just needs to add a flag to indicate that it is also a link identifier. If it is not possible to find a global prefix that all of the routers on the link are announcing, then some routers will need to include a prefix that is only a link identifier, thus increasing the size of the RA. There also needs to be a mechanism to change the Link Identifier if the chosen prefix ceases to be used on the link. Pentland Expires August 15, 2005 [Page 5] Internet-Draft DNA Solution Overview February 2005 Another way to generate an identifier from prefixes is to collect all of the prefixes active on the link and take some kind of hash over the ordered list of them, or alternatively, just one of them. This would generate an identifier like in Section 6.1.1.1, but with a guarantee of uniqueness. As with other prefix based link identifiers, the prefixes need to be monitored to ensure that they are current. A mechanism is needed to be able to change the identifier in response to changes in the prefixes. Using a hash based on a single prefix would be less vulnerable to changes than one based on all of the prefixes. 6.1.2 Complete Router Advertisement. Routers on a link listen for other routers' advertisements and include a complete list of all prefixes in use on the link in RAs they send. The RA would carry a flag to indicate that the RA did indeed include a complete list. Care should be taken to differentiate prefixes that are learnt from those that were originally configured on a router. The prefixes that are only learnt would need to be included in special PIOs so that hosts only use them for identification purposes and not as regular PIOs. The special PIOs could have their own code so that they are unrecognised by hosts that don't implement a new DNA specification. Another alternative would be to use conventional PIOs but with the L, A and R flags not set, and with a new D-flag (DNA) to indicate that the prefix is reflected for DNA purposes. PIOs with the L, A and R flags all cleared have no effect on non-DNA hosts. This technique has the advantages of forming an implicit identifier, is quite simple, requires no changes to solicitations, and makes it easy for a host to generate a complete prefix list for a link, allowing it to deal easily with an RA from a non-DNA router. The main cost is the size of the RAs. If routers on a link have matching sets of prefixes, then this is no cost but if there are differences then some of the RAs will be larger. If the sets are disjoint, then all of the solicited RAs will be larger and there is no implicit upper bound on the increase. 6.2 Techniques That Ask a Question in the RS. 6.2.1 Requested Landmark. Routers on a link listen for other routers' advertisements and collect the prefixes so that they know all of the active prefixes on the link. Hosts, when soliciting, select a prefix that they have seen previously and include it in the solicitation. Routers responding to the solicitation can then included a yes or no flag (as Pentland Expires August 15, 2005 [Page 6] Internet-Draft DNA Solution Overview February 2005 distinct from no flag at all) that says whether or not the prefix is in use on this link. This technique is again quite simple. The cost is an increase in the size of the RS (with no corresponding increase in the RA) but the increase is known, fairly modest, and fixed. There is, in general, a 1:N ratio of RSs to RAs, where N is the number of routers on the link. The result of this is that increases to the RS size are less costly than increases to the RA size. In certain other techniques it is possible to reduce the number of RAs by using multicast to answer multiple solicitations at once. This can only be achieved if delays are added which is something to be avoided if possible for the first response to an RS. Thus the number of RAs is always >= the number of RSs and hence increases to the RA size are still more costly than increases to the RS size. 6.2.2 Priority Landmark. Hosts include the address of their default router in solicitations. A fast RA mechanism is used that guarantees that if that router is on the link then it will respond first. If the first response is not from the default router then the host can assume that it has moved to a new link, possibly after checking that the included PIOs support this. This technique has the advantage of confirming bi-directional reachability with the default router when movement has not taken place. The cost is an increase in the RS size and a dependence on a mechanism to ensure that the requested router is always the first to respond. 6.2.3 Hybrid Landmark. Routers on a link include at least one PIO in unsolicited advertisements that includes an R-bit, and monitor the R-bit PIOs of other routers on the link. This gives out addresses that can be used as landmarks for the link. Hosts pick a landmark that they have seen most recently and include it in solicitations. Routers responding to this solicitation include flags to indicate whether or not this landmark has been seen on the link. The fast RA mechanism can be designed to allow the router with the requested landmark to respond first. This again has the advantage of confirming bi-directional reachability with the default router when movement has not taken place. It also allows any router to respond and give a definitive answer to the link-change question. The main cost is the increased Pentland Expires August 15, 2005 [Page 7] Internet-Draft DNA Solution Overview February 2005 RS size. This, the two preceding landmark schemes, and Complete RA all require routers to place timers on the gathered prefixes to be sure that old information can be discarded if prefixes are moved to different links. 7. Fast Responses to Solicitation Again there are a number of ways that standard procedures could be modified to allow a router advertisement to be received quickly following solicitation. 7.1 Fast Router Discovery. draft-jinchoi-dna-frd-00.txt Access Points cache the most recent RA(s) and forward it(them) to a host upon detection of its association. This is very simple and potentially very fast and places no requirements on hosts or routers but is link-specific and raises some security concerns since it is, by definition, a "man in the middle". Where there are multiple routers on a link it needs to be determined which RA(s) will be forwarded, and how to time out old cache entries. 7.2 Simple Fast RA. draft-mkhalil-ipv6-fastra-05.txt Select one router on each link to be allowed to respond immediately to solicitations. Again very simple, but requires a mechanism to select the fast router, introduces a single point of failure, and may result unbalanced loading of routers. 7.3 Deterministic Fast RA. draft-daley-dna-det-fastra-01.txt Routers on a link negotiate amongst themselves an ordering for responding to solicitations. Responses are made in order at fixed intervals starting from zero delay for the first router. This removes the single point of failure problem and means that losing an RA doesn't slow down the RS/RA exchange much (unless there Pentland Expires August 15, 2005 [Page 8] Internet-Draft DNA Solution Overview February 2005 is only one router). The costs include the necessity for the routers to engage in negotiation to select the ordering and fact that that ordering may result in unbalanced loading of the routers. It would be fairly simple to alter the behaviour to reorder the responses based on some function of the source of the RS to spread load evenly. 7.4 Negotiation-free Deterministic Fast RA. Routers on a link listen for advertisements from other routers and form tokens for them from the source addresses. Hosts include a tentative source link layer address option (TSLLAO) [11] in solicitations. When an RS is received by a router, some function of the TSLLAO is XORed with each of the router tokens to create a ranking. One or more of the routers then respond in order with fixed delays starting from zero. The advantage here is that routers just need to listen to RAs to determine an ordering that will vary from solicitation to solicitation, it doesn't have a single point of failure and will result in multiple (if there are multiple routers) RAs quickly. The main cost is the need for the RSs from hosts to include a TSLLAO, but this will be necessary for any technique where sending unicast RAs is required, unless a separate NS/NA exchange is done between the RS and RA. If multicast RAs are to be used, then TSLLAOs are not necessary for the transmission of the RA to the host without an NS/NA exchange. The cost of including a TSLLAO might be removed by determining a base ordering for the routers based on the tokens, and then perturbing that ordering using a function of the time that the RS is received (for example, shifting the ordering by the minute of the reception time, modulo the number of routers). The cost of this is the necessity to synchronize the router's clocks and a small period of ambiguity around the time when the part of the timestamp used changes (e.g. when the clock ticks over from one minute to the next). 7.5 Probabilistic Fast RA. Routers on a link listen for advertisements from other probabilistic fast RA routers (as defined by a flag) and count the number of them. Responses to solicitations are scheduled into one of count+1 slots spaced, say, 20 ms apart starting from zero. A slight bias towards the zero slot can be done to improve average response. Maximum and minimum values for the number of slots can be set to limit the effects of unknown or spurious routers. Details of this technique can be found in [10] including claimed intellectual property rights. Pentland Expires August 15, 2005 [Page 9] Internet-Draft DNA Solution Overview February 2005 Again, routers just have to listen to other routers on the link to get the information they need to determine the sending delay. The trust requirements are even lower, having no need for security associations between routers. This is because they are just counting routers, storing minimal information about them, and abnormally high counts are easily ignored. An upper bound is placed on introduced delay, and average delays are quite low, albeit non-zero. Hosts will often, but not always receive an immediate response. 8. Dealing with Legacy Routers It is likely that hosts will encounter links that have routers that don't have any enhancements to support DNA. It is important that they are still able make correct decisions quickly about whether link change has occurred. By maintaining a list of all of the prefixes in use on a link, they can then use any prefix in an RA to make a decision. One way to maintain such a list is described in [8]. An unsolicited RA might indicate an added prefix or router, rather than movement, but can be used as a trigger to send an RS to test the link. There is a small chance of an erroneous decision, even after an RS, if a prefix or router is added to a link. An implementation may choose to delay making configuration changes until further confirmation if the cost of an incorrect decision is high. It may wait for further RAs or even re-solicit to achieve that confirmation. The Complete Router Advertisement technique described in Section 6.1.2 integrates well with this because a single RA can provide all of the prefixes in use on a link, simplifying the process of gathering them. 9. Putting Things Together For a complete solution, a fast RA technique needs to be mated up with a technique for using the RS/RA exchange for identification. The two parts are largely but not completely independent. For example, deterministic fast RA defines a "router to router" message that can be reused to negotiate a link identifier. To evaluate solutions, the way they meet the goals laid out in the DNA goals document [9] should be considered. Quoting from the goals document: G1 DNA schemes should detect the identity of the currently attached link to ascertain the validity of the existing IP configuration. They should recognize and determine whether a link change has Pentland Expires August 15, 2005 [Page 10] Internet-Draft DNA Solution Overview February 2005 occurred and initiate the process of acquiring a new configuration if necessary. G2 DNA schemes should detect the identity of an attached link with minimal latency lest there should be service disruption. G3 In the case where a host has not changed a link, DNA schemes should not falsely assume a link change and an IP configuration change should not occur. G4 DNA schemes should not cause undue signaling on a link. G5 DNA schemes should make use of existing signaling mechanisms where available. G6 DNA schemes should make use of signaling within the link (particularly link-local scope messages), since communication off-link may not be achievable in the case of a link change. G7 DNA schemes should be compatible with security schemes such as Secure Neighbour Discovery [3]. G8 DNA schemes should not introduce new security vulnerabilities. The node supporting DNA schemes should not expose itself or others on a link to additional man-in-the-middle, identity revealing, or denial of service attacks. G9 The nodes, such as routers or hosts, supporting DNA schemes should work appropriately with unmodified nodes, such as routers or hosts, which do not support DNA schemes. G10 Hosts, especially in wireless environments, may perceive routers reachable on different links. DNA schemes should take into consideration the case where a host is attached to more than one link at the same time. 9.1 Requested Landmark with Negotiation-free Deterministic Fast RA (How routers collect the information needed to determine RS response order) - Routers send periodic advertisements including a flag that indicates that they are DNA routers. - An interval option (rfc3775) should be included in multicast RAs to facilitate detection of lost routers - If more than one SA is in use then a PIO with the R-bit (rfc3775) should be included. - Routers listen to other routers' advertisements and use them to Pentland Expires August 15, 2005 [Page 11] Internet-Draft DNA Solution Overview February 2005 maintain a list of all active prefixes on the link. - Upper bound needed on list length to prevent memory overflow. - routers collect the source addresses of routers they have received RAs from. - a token equal to a hash of the IID (could be the full SA, but presumably the IID is where the variation is) of the collected addresses is stored for each router, associated with a timer related to the interval option in the received RA. - the IIDs are also stored - R-bit PIOs should be monitored to detect the use of multiple SAs by a single router - only the lowest IID and its token should be stored. - an upper bound is needed on the number of tokens that will be stored (to prevent overflow). - a fallback position is needed in the case of a full list. (How hosts request information from the link) - Hosts solicit including a TSLLAO (for unicast responses), an 8 bit counter that is incremented for each RS sent, and an option including the most recently received prefix. (How routers respond to solicitation) - Unicast is used by routers for responding to solicitations, subject to rate control by a token bucket scheme. - Exhaustion of the token bucket results in the use of multicast, subject to the controls of rfc2461. - Routers examine the TSLLAO of incoming RSs, XOR the IID contained with each of the stored tokens (including its own) and compare them to calculate a ranking for themselves. - The top ranked router responds immediately. - Some number of the others follow at fixed intervals. (How hosts interpret RAs received) - The response RAs contain one of two flags indicating whether or not the requested prefix is active on this link, and a copy of the counter in the received RS. - Hosts look at the flags in the received RA to decide on a course of action. - Yes flag set: no action required - maybe NS/NA exchange with current default router at leisure. - No flag set: clear NC, and use one of the prefixes in the RA to form a new address - test with optiDAD, etc. - Both set: not allowed - treat as though none set - None set: invoke CPL logic - CPL logic: (going from memory, may need correcting - more aggressive approach to new prefixes) - hosts try to form a complete list of all prefixes available Pentland Expires August 15, 2005 [Page 12] Internet-Draft DNA Solution Overview February 2005 on a link. - send (possibly multiple) RSs at suitable intervals - RAs received in this time considered to be part of prefix list building - RAs with all prefixes disjoint from current prefix list assumed to be from a new link (maybe test with NS/NA to current default router with short timeout) - Clear NC, form new address, etc., restart CPL building. 9.1.1 How the goals are met G1 The answer to the landmark question gives a positive indication of whether link change has occurred, and the RA will contain the information required to reconfigure if necessary. G2 Under normal circumstances, a host that sends an RS should get an RA back from a router in one round trip time plus a small processing delay. If that RA is lost another should arrive after a small delay if there is more than on router on the link. G3 Non-movement situations are correctly detected. G4 A single RS/RA exchange is initiated in response to a hint that a link change may have occurred. Routers build the state they need to respond to RSs simply by listening to the unsolicited RAs of other routers. G5 The RS/RA mechanism is all that is required. A new option is defined for the RS and a pair of new flags is required in RAs. G6 Only link-scope signalling is used. G7 SeND can be used to protect RSs with a specified source address and will protect the new option against tampering. It will also protect the new flags in the RA against tampering. G8 If SeND is not deployed, then a rogue device could cause a host to think its configuration is invalid by sending an RA that answers the RS question incorrectly. A similar effect is already possible, however, by a rogue device sending an RA with valid prefixes with zero lifetimes. G9 The CPL logic allows a graceful fallback position for dealing with non-DNA hosts and routers. Pentland Expires August 15, 2005 [Page 13] Internet-Draft DNA Solution Overview February 2005 G10 This technique is carried out on an interface by interface basis. A host with multiple interfaces can get information about changes to configuration on each interface, but would need a higher level process to decide how the information from the various interfaces relates to each other. 9.2 CompleteRA with Probabilistic Fast RA (How routers gather all the routers and prefixes on a link.) - Routers include a "D" flag (DNA) in RAs to indicate that they will participate in probabilistic fast RA. - Routers listen to other routers' advertisements and use them to maintain a list of all active prefixes on the link. - They also keep a count of the number of DNA routers on the link. - An upper bound needed on list lengths to prevent memory overflow. (How routers decide when to respond to an RS) - Upon reception of an RS, an RA is scheduled into one of count+1 time slots starting from zero with, say, 20 ms spacing. - count is set to the number of probabilistic routers heard with configurable upper and lower bounds - multicast RAs may be used (subject to the rate limiting restrictions of RFC 2461) and if they are, solicitations that would result in the scheduling of an RA after an already scheduled RA may be ignored (How routers advertise CompleteRA) - CompleteRA is the RA that contains the complete set of all prefixes on the link, including a flag to indicate that the list is indeed complete. - PIOs seen on the link but not originating from the sending router could use a new type code (as distinct from a flag which would be ignored by non-dna hosts). - Routers advertise the CompleteRA upon receiving an RS as indicated above. - If too many prefixes are in use to fit in an RA then the complete flag cannot be set and CPL may be relied on with conventional logic. (How hosts check for link change with CompleteRA.) - A host receiving an RA compares the prefixes in the RA to their own list of current prefixes. - if there is overlap between the prefix lists (they should match exactly) then nothing needs to be done - maybe NS/NA exchange with current default router at leisure. Pentland Expires August 15, 2005 [Page 14] Internet-Draft DNA Solution Overview February 2005 - if they are disjoint, then it is a new link and the NC can be cleared and new addresses formed, etc. (How hosts generate the Complete Prefix List with a single CompleteRA) - Upon receiving a CompleteRA, hosts can generate the Complete Prefix List without further action. (How to interoperate with non-supporting links) - The Complete Prefix List logic is simpler: - similar to above - when building the CPL, if an RA is received with the complete flag set, then those prefixes constitute the CPL and the host can go straight to the state where list is considered built. - In the built state, if a new prefix is received that has a disjoint prefix set, then a new link is implied. - reconfiguration should be commenced, possibly after an attempted NS/NA exchange with default router with a short timeout if the cost for an incorrect decision is high (could just be a new router and prefix on the link). 9.2.1 How the goals are met G1 The complete set of prefixes in the RA gives a positive indication of whether link change has occurred, and contains the information required to reconfigure if necessary. G2 The router advertisement is usually transmitted to the host in one round trip time plus a processing delay. Sometimes there will be a slot delay if no routers schedule for slot zero, adding 20 ms to the delay. G3 Non-movement situations are correctly detected. G4 A single RS/RA exchange is initiated in response to a hint that a link change may have occurred. Routers build the state they need to respond to RSs simply by listening to the unsolicited RAs of other routers. If a complete RA is received without solicitation, then no solicitation is required; the RA contains enough information. G5 The RS/RA mechanism is all that is required. A new option is defined for the RA to carry learned (but unused) prefixes and new flags are required to indicate completeness and participation in probabilistic fast RA. Pentland Expires August 15, 2005 [Page 15] Internet-Draft DNA Solution Overview February 2005 G6 Only link-scope signalling is used. G7 SeND can be used to protect the RAs. The new option can be protected against tampering but not necessarily that they are authorized to be included in the RA. Since they are only used for link identification, this is no different to the flag protection in the previous section. It will also protect the new flags in the RA against tampering. G8 If SeND is not deployed, then a rogue device could cause a host to think its configuration is invalid by sending an RA with bogus prefixes. A similar effect is already possible, however, by a rogue device sending an RA with valid prefixes with zero lifetimes. G9 The CPL logic allows a graceful fallback position for dealing with non-DNA hosts and routers. G10 This technique is carried out on an interface by interface basis. A host with multiple interfaces can get information about changes to configuration on each interface, but would need a higher level process to decide how the information from the various interfaces relates to each other. 9.3 Prefix-based LinkID with Fast Router Discovery -(How to choose a common Prefix LinkID on a link) - Routers listen to other routers' advertisements and use them to maintain a list of all active prefixes on the link. - Upper bound needed on list length to prevent memory overflow. - The routers choose the smallest prefix as the Link Identifier, i.e. Prefix LinkID. (How to advertise the Prefix LinkID in an RA) - The routers advertise the prefix in every RA with PIO including a new "I" (identification) bit to indicate that the prefix is the Link Identifier, i.e. Prefix LinkID. - If the prefix is not explicitly configured on the sending router, the L, A and R flags should be set off, so that the PIO would have no effect on hosts other than link identification. (How hosts use Prefix LinkID) - Hosts keep the Prefix LinkID of the currently attached link. (How to quickly forward Prefix LinkID to hosts with FRD) - Access Points on the network cache an RA with the Prefix LinkID. Pentland Expires August 15, 2005 [Page 16] Internet-Draft DNA Solution Overview February 2005 - When an Access Point detects (through layer two means) that a host has arrived on the link, it immediately forward it a copy of the cached RA. (How a host checks for link change with Prefix LinkID) - The host receiving the RA compares the Prefix LinkID in the RA to its currently stored one. - If they are the same, the host remains at the same link and no further DNA action is required. - If they differ, the host assumes a link change and immediately initiates a new IP configuration. (How to interoperate with non-supporting links) - Prefix LinkID scheme allows a host to detect a link change properly when it moves FROM and TO the link supporting the scheme. Backup mechanism such as CPL is needed only when a host moves between non-supporting links. 9.3.1 How the goals are met G1 The reception of the LinkID gives a host a positive indication of whether link change has occurred, and the RA will contain the information required to reconfigure if necessary. G2 The router advertisement is transmitted to the host as soon as the AP detects that it has associated and is able to receive packets on the link. G3 Non-movement situations are correctly detected. G4 Only a single RA is required. G5 Only RAs are required. A new flag is added to PIOs to indicate that a prefix is in fact the Link ID as well. G6 Only link-scope signalling is used. G7 SeND can be used to protect RAs and show authorization for a set of prefixes. For routers with the prefix used as the LinkID explicitly configured, SeND may not show authorization. In this case there will be no evidence that the LinkID is valid. Hosts should only accept RAs that contain another authorized prefix. It will also protect the new flag in the RA against tampering. G8 If SeND is not deployed, then a rogue device could cause a host to think its configuration is invalid by sending an RA with a bogus Link ID. A similar effect is already possible, however, by Pentland Expires August 15, 2005 [Page 17] Internet-Draft DNA Solution Overview February 2005 a rogue device sending an RA with valid prefixes with zero lifetimes. G9 The CPL logic allows a graceful fallback position for dealing with non-DNA hosts and routers. G10 This technique is carried out on an interface by interface basis. A host with multiple interfaces can get information about changes to configuration on each interface, but would need a higher level process to decide how the information from the various interfaces relates to each other. 10. On the Wire Costs The number of bytes sent onto the wire (air) is highly dependent on the number of routers on a link and the way in which prefixes are distributed across them. In the very simplest case where there is only one router and it only has a single prefix to advertise, the variation in costs is quite small. Considering only unicast RA examples, the RS/RA would take 160 octets for CompleteRA, or for LinkID where the link identifier is the prefix being advertised. Using the hybrid landmark scheme would take 184 octets. As the topology gets more complex and there are more routers and/or prefixes the number of octets in the exchange increases dramatically. In general, however, the growth is fairly consistent across the combinations of techniques. The exception is combinations including CompleteRA. The re-advertising of prefixes makes the size of its exchanges grow much more quickly if there are non-matching sets of prefixes on routers. For example, a medium case where there are two routers each with one prefix (but not the same one), the prefix-based requested landmark scheme takes 280 octets for the exchange. Complete RA takes 328 octets. In a much worse case of four routers, each with two prefixes and none matching, the two exchanges are 616 and 1240 octets respectively. The worst case performance of Complete RA can be improved substantially by defining a new RA option to carry all of the re-advertised 64-bit prefixes at once. This reduces the above case exchange to 824 octets, but it is still unbounded. It needs to be considered how likely such topologies are. The actual sizes of RAs will depend on which options are needed but an example of the sizes is shown in the following table. In this case "typical" options counted are Maximum Transmission Unit (MTU) and Link Layer Address Option (LLAO). Pentland Expires August 15, 2005 [Page 18] Internet-Draft DNA Solution Overview February 2005 +--------------------+--------------------+-----------------------+ | Technique | RS size | RA size | +====================+====================+=======================+ | Random LinkID | 56 octets (basic + | 40 + 48 + p*32 octets | | | 8 for TSLLAO) | (basic + 8 (LLAO) + | | | | 8 (MTU) + 16 (LinkID) | | | | + PIOs) | +--------------------+--------------------+-----------------------+ | Prefix LinkID | 56 octets (basic + | 40 + 48 + p*32 octets | | | 8 for TSLLAO) | as above _OR_ | | | | 40 + 32 + p*32 octets | | | | if one of the prefixes| | | | is the link ID | +--------------------+--------------------+-----------------------+ | CompleteRA | 56 octets (basic + | 40 + 32 + P*32 octets | | | 8 for TSLLAO) | (basic + 8 (LLAO) + 8 | | | | (MTU) + all PIOs) | +--------------------+--------------------+-----------------------+ | CompleteRA with | 56 octets (basic + | 40 + 32 + p*32 + 8 + | | re-advertised | 8 for TSLLAO) | p2*32 (basic + 8 | | prefix option | | (LLAO) + 8 (MTU) + | | | | own PIOs + opt header | | | | learned prefixes | +--------------------+--------------------+-----------------------+ | Requested Landmark | 72 octets (basic + | 40 + 32 + p*32 octets | | | TSLLAO + 16 octet | (basic + 8 (LLAO) + | | | landmark option) | 8 (MTU) + PIOs | +--------------------+--------------------+-----------------------+ | Priority Landmark | 80 octets (basic + | 40 + 32 + p*32 octets | | | TSLLAO + 24 octet | as above | | | landmark option) | | +--------------------+--------------------+-----------------------+ | Hybrid Landmark | 80 octets (basic + | 40 + 32 + p*32 octets | | | TSLLAO + 24 octet | as above | | | landmark option) | | +--------------------+--------------------+-----------------------+ p = number of prefixes router advertises P = total number of prefixes on link p2 = number of prefixes re-advertised in case of CompleteRA Note that unicast RAs have been assumed here necessitating the TSLLAO in the RS if an immediate RA is desired. Note that RA size assumes that flags can be placed in existing RA flag fields - if an option is required the RA will be 8 octets larger. Pentland Expires August 15, 2005 [Page 19] Internet-Draft DNA Solution Overview February 2005 Note also that the CompleteRA and LinkID techniques could have value even without an RS at all. As mentioned above, the number of routers on a link and the distribution of prefixes has a large effect on the number and size of packets sent onto the link. Some examples are shown below. +--------------------+--------------------------------------------+ | Technique |1 Router|2 Router|2 Router|2 Router|4 Router| | |1 prefix|1 prefix|1 prefix|2 prefix|2 prefix| | | | |each |disjoint|disjoint| +====================+========+========+========+========+========+ | Random LinkID |56+120 |56+2*120|56+2*120|56+2*152|56+4*152| | |=176 |=296 |=296 |=360 |=664 | +--------------------+--------+--------+--------+--------+--------+ | Prefix LinkID |56+104 |56+2*104|56+104+ |56+136+ |56+136+ | | |=160 |=264 |120=280 |152=344 |3*152 | | | | | | |=648 | +--------------------+--------+--------+--------+--------+--------+ | CompleteRA |56+104 |56+2*104|56+2*136|56+2*200|56+4*296| | |=160 |=264 |=328 |=456 |=1240 | +--------------------+--------+--------+--------+--------+--------+ | CompleteRA with |56+104 |56+2*104|56+2*120|56+2*160|56+4*192| | re-advertised |=160 |=264 |=296 |=376 |=824 | | prefix option | | | | | | +--------------------+--------+--------+--------+--------+--------+ | Requested Landmark |72+104 |72+2*104|72+2*104|72+2*136|72+4*136| | |=176 |=280 |=280 |=344 |=616 | +--------------------+--------+--------+--------+--------+--------+ | Priority Landmark |80+104 |80+2*104|80+2*104|80+2*136|80+4*136| | |=184 |=288 |=288 |=352 |=624 | +--------------------+--------+--------+--------+--------+--------+ | Hybrid Landmark |80+104 |80+2*104|80+2*104|80+2*136|80+4*136| | |=184 |=288 |=288 |=352 |=624 | +--------------------+--------+--------+--------+--------+--------+ Note this table assumes that for each RS there will be N RAs, where N is the number of routers on the link. It may be possible to multicast any delayed RAs and if a group of RSs arrive very close together, to have one RA answer multiple RSs. If the first RA is not delayed, then #RAs is always >= #RSs and in general, #RAs = N * #RSs. 11. IANA Considerations No new options or messages are defined in this document. Pentland Expires August 15, 2005 [Page 20] Internet-Draft DNA Solution Overview February 2005 12. Security Considerations All of the techniques described in this document are modifications to router discovery. SeND [12] has be design for the express purpose of securing neighbour and router discovery exchanges. It follows then that there are two cases to consider: networks with and without SeND. SeND can be used to show that a router is authorised to advertise particular prefixes. This can be used equally well by routers checking the prefixes of other routers as it can by hosts checking the same. In the case of link identifiers SeND may not be able to show that a linkid is correct for a given router but it can protect the packet against tampering. There may be some performance issues introduced by SeND. The first time a host comes to a link there may need to be a packet exchange to get certificates chains. This may be mitigated by allowing certificates to cover larger prefixes, e.g. for a site/organization. Where SeND is not deployed there are many attacks against neighbour/ router discovery already possible and it is just necessary to investigate whether proposed DNA techniques make the network or hosts any more vulnerable than they already are. The main difference between the threat to RFC2461 devices and the threat to devices implementing techniques discussed in this document comes from the desire to speed things up. The goal is to have a single RA able to give enough information to decide if a link change has occurred, and if so, reconfigure addressing, etc., to allow packet exchanges to begin on the new link. A result of this is that if a single carefully crafted packet can cause a host to make the decision that it has changed links, it can then cause that host enter a state where logically all of its existing configuration is invalid. If a host has in fact moved to a new link, then that configuration is invalid. It be prudent, however, to move the configuration to a placeholder in case it is possible to recognise to false advertisement and restore the old configuration. 12.1 General Threats 1 A bogus router advertises a landmark or identifier that convinces a host that it has moved when it in fact not. 2 A bogus router advertises a landmark or identifier that convinces a host that it has not moved when it in fact has. Pentland Expires August 15, 2005 [Page 21] Internet-Draft DNA Solution Overview February 2005 3 A mischievous host may, depending on the mechanisms available in the fast RA scheme employed, be able to cause a flood of RAs to be sent onto the link. Even unicast RAs can cause disruption to all nodes on certain link types, such as those employing CSMA/CA like 802.11b. It is probably worth designing in mechanisms to limit the effect of this even when SeND is not employed because of the potential for a multiplicative effect where there are more than one router on the link: 1 RS -> N RAs. 13. Acknowledgments Thanks to all members of the design team - JinHyeock Choi, Tero Kauppinen, James Kempf, Sathya Narayanan, and Erik Nordmark - upon whose discussion the text of this document is based, and for their help in shaping the content. Thanks also to Greg Daley for some very useful insight. 14. References 14.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. 14.2 Informative References [3] Thomson, S. and T. Narten, "IPv6 Stateless Address Autoconfiguration", RFC 2462, December 1998. [4] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in IPv6", RFC 3775, June 2004. [5] Choi, J., "Fast Router Discovery with RA Caching", draft-jinchoi-dna-frd-00 (work in progress), July 2004. [6] Kempf, J., Khalil, M. and B. Pentland, "IPv6 Fast Router Advertisement", draft-mkhalil-ipv6-fastra-05 (work in progress), July 2004. [7] Daley, G., "Deterministic Fast Router Advertisement Configuration", draft-daley-dna-det-fastra-01 (work in progress), October 2004. Pentland Expires August 15, 2005 [Page 22] Internet-Draft DNA Solution Overview February 2005 [8] Choi, J., "DNA with unmodified routers: Prefix list based approach", draft-jinchoi-dna-cpl-01 (work in progress), October 2004. [9] Choi, J., "Detecting Network Attachment in IPv6 Goals", draft-ietf-dna-goals-04 (work in progress), December 2004. [10] Daley, G., Narayanan, S. and G. Perkins, "A probabilistic scheme for fast Router Advertisement responses in IPv6", draft-daley-dna-prob-fastra-00 (work in progress), February 2005. [11] Daley, G., "Tentative Source Link-Layer Address Options for IPv6 Neighbour Discovery", draft-daley-ipv6-tsllao-00 (work in progress), June 2004. [12] 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] Yegin, A., "Link-layer Event Notifications for Detecting Network Attachments", draft-ietf-dna-link-information-00 (work in progress), September 2004. Author's Address Brett Pentland Centre for Telecommunications and Information Engineering Department of Electrical and Computer Systems Engineering Monash University Clayton, Victoria 3800 Australia Phone: +61 3 9905 5245 EMail: brett.pentland@eng.monash.edu.au Pentland Expires August 15, 2005 [Page 23] Internet-Draft DNA Solution Overview 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. 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. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Pentland Expires August 15, 2005 [Page 24]