One document matched: draft-dnadt-dna-discussion-00.txt
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]
| PAFTECH AB 2003-2026 | 2026-04-21 20:37:36 |