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