DNA Working Group G. Daley
Internet-Draft B. Pentland
Expires: April 25, 2005 Monash University CTIE
E. Nordmark
Sun Microsystems
October 25, 2004
Deterministic Fast Router Advertisement Configuration
draft-daley-dna-det-fastra-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 April 25, 2005.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract
Neighbour Discovery forces routers responding to Router Solicitations
to delay a random interval of 0-500 ms in order to prevent contention
and bandwidth utilization by multiple responding routers. Routers
receiving solicitations may need to quickly send responding Router
Advertisements faster than allowed in IPv6 Neighbour Discovery.
In order to provide fast router response, Fast Router Advertisements
Daley, et al. Expires April 25, 2005 [Page 1]
Internet-Draft Deterministic FastRA October 2004
have been proposed, which do not randomly delay. This document
describes an automatic arbitration and configuration mechanism to
allow hosts to securely agree on the relative ordering and delay of
their Fast Router Advertisements.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 6
3.1 Deterministic Fast Router Advertisement Concepts . . . . . 6
3.2 Router-to-Router Status Communication . . . . . . . . . . 7
3.3 Deterministic Fast Router Advertisement Options . . . . . 7
4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 8
4.1 Router to Router ICMPv6 message . . . . . . . . . . . . . 8
4.2 Deterministic Fast Router Advertisement Option Format . . 10
4.2.1 Rank . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.2 Fixed Delay . . . . . . . . . . . . . . . . . . . . . 12
4.2.3 Separation . . . . . . . . . . . . . . . . . . . . . . 12
4.2.4 Relative Preference . . . . . . . . . . . . . . . . . 12
5. Sending Router-to-Router messages . . . . . . . . . . . . . . 12
5.1 Sending Router-to-Router Status-Requests . . . . . . . . . 12
5.2 Sending Router-to-Router Status . . . . . . . . . . . . . 13
6. Ranking Calculation . . . . . . . . . . . . . . . . . . . . . 13
6.1 Ranking Score Calculation Reasoning . . . . . . . . . . . 14
7. Becoming a Fast Router . . . . . . . . . . . . . . . . . . . . 15
8. Receiving DetFRAO in ICMPv6 Router-to-Router . . . . . . . . . 15
8.1 Receiving Bootstrap Deterministic FastRA Options . . . . . 16
8.2 Cleaning up old entries . . . . . . . . . . . . . . . . . 16
8.3 Responding to Status-Requests with DetFRAO . . . . . . . . 16
9. Sending DetFRAOs in ICMPv6 Router-to-Router . . . . . . . . . 16
9.1 Sending RAs on Rank or Delay Change . . . . . . . . . . . 17
9.2 Sending Advertisement Intervals . . . . . . . . . . . . . 17
10. Sending Fast Router Advertisements . . . . . . . . . . . . . 17
10.1 Sending Unicast Fast RAs . . . . . . . . . . . . . . . . . 18
10.2 Sending Multicast Fast RAs . . . . . . . . . . . . . . . . 18
11. Interaction with Other Routers . . . . . . . . . . . . . . . 18
11.1 Presence of Legacy Routers . . . . . . . . . . . . . . . . 18
11.2 Ceasing to be a Fast Router . . . . . . . . . . . . . . . 19
11.3 Presence of Non Fast Routers . . . . . . . . . . . . . . . 19
11.4 Presence of Incompatible Fast Routers . . . . . . . . . . 19
12. Configuration Parameters . . . . . . . . . . . . . . . . . . 20
13. Protocol Constants . . . . . . . . . . . . . . . . . . . . . 20
14. IANA Considerations . . . . . . . . . . . . . . . . . . . . 21
15. Security Considerations . . . . . . . . . . . . . . . . . . 21
16. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 22
17. Changes Since Last Revision . . . . . . . . . . . . . . . . 22
17.1 draft-daley-dna-det-fastra-00 to -01 . . . . . . . . . . . 22
Daley, et al. Expires April 25, 2005 [Page 2]
Internet-Draft Deterministic FastRA October 2004
18. References . . . . . . . . . . . . . . . . . . . . . . . . . 22
18.1 Normative References . . . . . . . . . . . . . . . . . . . . 22
18.2 Informative References . . . . . . . . . . . . . . . . . . . 23
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 23
A. State Diagram . . . . . . . . . . . . . . . . . . . . . . . . 24
Intellectual Property and Copyright Statements . . . . . . . . 26
Daley, et al. Expires April 25, 2005 [Page 3]
Internet-Draft Deterministic FastRA October 2004
1. Introduction
Existing standards require that hosts which respond to Router
Solicitations introduce a random delay of 0-500ms before sending a
Router Advertisement [2].
The Fast RA draft [6] introduces the concept of a Fast Router
Advertisement. Fast Router advertisements provide the capability for
a router to avoid performing the random delay before transmission,
and send responses without the mean 250ms delay.
Additionally, routers may wish to allow a small number of multicast
Router Advertisements to configuring devices with similar delays.
Extensions to FastRA which support multicast Router Advertisement are
considered in this document (possibly to move elsewhere later).
Fast Router Advertisement, as specified, only allows one host on a
link to be a FastRA router. Unless FastRA specified this limit,
responses from more than one FastRA router would result in the same
MAC contention which RFC 2461 sought to avoid.
Unfortunately, while Fast RA is an effective way of providing fast
response, it has no defined automated configuration mechanism to
determine which router is the fastest, nor any method to provide
router reselection in case a router is no longer able to provide fast
responses. This lack of a router reselection mechanism is seen a a
clear stumbling block to FastRA's deployment.
This document defines a secured mechanism relying on new
Router-to-Router ICMPv6 messages to allow routers to make decisions
about which router responds fastest, and additionally allows other
routers to avoid random delays[5][2]. The new mechanism relies upon
SEND-like security to determine trust-relationships between on-link
routers, and test the reachability of existing routers.
It allows automated reconfiguration in the case that routers join or
leave the Fast Router set, and ensures that Fast Routers do not
collide with each other by providing negotiated fixed delays between
responding advertisements.
2. Terminology
The following terms are used throughout the document
Bootstrapping Router: A router which has not yet determined its rank
and delay for Fast Router Advertisement.
Daley, et al. Expires April 25, 2005 [Page 4]
Internet-Draft Deterministic FastRA October 2004
Deterministic Fast Router Advertisement Option (DetFRAO): An ICMPv6
option indicating the Fast Router's participation in this
protocol, as well as its rank and delay. This option may appear
in Router-to-Router Status-Requests and Status messages. The
option's format is defined in Section 4.2.
Fast Router: A router participating in this protocol and exchanging
Deterministic Fast Router Advertisement Options in
Router-to-Router messages.
Fast Router Advertisement: A response to a Router Solicitation which
is not randomly delayed. Please note that at a particular time, a
Fast Advertising Router may advertise with a delay whose mean is
slower than that defined by [2]. Even in this case, the response
is still called a Fast Router Advertisement (or FastRA).
Fast Advertising Router List: A conceptual list where FastRA routers
are sorted by a Ranking Score, and delays for various routers
calculated.
Fastest Advertising Router: The router with Rank=1, which is able to
transmit without delay.
Fixed Delay: The minimum amount of time which a Fast Advertising
Router may delay before sending a Router Advertisement in response
to a Router Solicitation. Typically this is the delay used for
Router Advertisement transmission.
Legacy Router: A router which responds to router solicitations using
the algorithm defined in section 6.2.6 of the IPv6 Neighbour
Discovery RFC[2].
Multicast Fast Router Advertisement A Fast Router Advertisement sent
to the all-nodes multicast address. These advertisements have
different parameters for their Token Bucket than a Unicast Fast
Router Advertisement.
Rank: The position of the router in the advertising order. A router
with a better (lower numbered) rank will always send responding
advertisements faster than one with a worse rank.
Ranking Identifier: An value derived from the identity of the
advertising router, used in ranking calculations.
Ranking Score: A score calculated from the router's preference and
Ranking Identifier. This score is used to order the routers on
the link and determine their Rank.
Daley, et al. Expires April 25, 2005 [Page 5]
Internet-Draft Deterministic FastRA October 2004
Router-to-Router message: A new ICMPv6 message which uses the same
options format as IPv6 Neighbour Discovery, but is only used for
communication between routers on a local link. It provides a
means by which routers can advertise their configuration status
and request that other routers do the same.
Separation: A period after the transmission of a previous RA that the
router must wait. The separation time is defined by the preceding
router.
Token Bucket A finite sized non-negative resource counter which
increases at a set rate while the number of resource tokens in the
bucket is not at maximum. When a resource is to be allocated,
there must be a non-zero number of resource tokens in the bucket.
As the token is allocated the resource counter decrements.
Unicast Fast Router Advertisement A Fast Router Advertisement sent to
the unicast source address of a Router Solicitation. Unicast Fast
RAs can be sent while there are tokens in the Unicast FastRA token
bucket as defined in [6].
3. Protocol Operation
Routers wishing to provide Fast Router Advertisement need to check if
other routers on the link are providing Fast RAs and agree on a
relative ordering and delay before response. This negotiation takes
place prior to Fast RA operation, when routers are first configured,
start or change their preferences.
This allows all Fast Routers to send responses to Router
Solicitations at the agreed delay, without introducing additional
variable delays. Delays and ordering are therefore deterministic,
and one responding Fast Advertising Router (the Fastest) will be able
to transmit Router Advertisements in response to solicitation with no
delay at all.
During transition periods where router ordering changes, router
advertise their changed configuration to peer routers using ICMPv6
Router-to-Router messages, defined in this document.
3.1 Deterministic Fast Router Advertisement Concepts
To agree on when to send responses, Fast RA routers need to know
which routers are Fast Routers, and must agree on their relative
order for RS response. In this document, the ordinal position agreed
to by a router is its Rank.
Daley, et al. Expires April 25, 2005 [Page 6]
Internet-Draft Deterministic FastRA October 2004
The lowest number provides the best Rank, and the fastest responding
router has a Rank of 1. The ranking algorithm seeks to avoid ties,
although from time to time, multiple routers will be seen to have the
same Rank. Handling of this condition is specified in Section 6.
Upon determining the advertisement order, each router needs to choose
a delay exceeding that advertised by its better Ranked routers. To
do this it inspects the Separation value advertised by the fastest
router, and advertises its own Fixed Delay value based on the number
of routers preceding it and the fastest router's Separation. The
Fixed Delay is the lowest value used by the router as delay for
responding to Router Solicitations.
3.2 Router-to-Router Status Communication
In order to accomplish Ranking and delay agreement between routers on
a link, messages need to be exchanged between FastRA routers. These
messages contain information about the router's current configuration
status, and indicate that FastRA is in use. This document specifies
the Router-to-Router(RtR) ICMPv6 message which allows configuration
status to be requested from other routers while advertising the
router's own status.
In negotiating with other routers on a link, trust of a router's
identity and authorization needs to be established, and mechanisms to
check these must be devised. The Router-to-Router message is able to
use the existing message formats for Secure Neighbour Discovery, and
uses the same signatures and keys which are used in Router
Solicitations and Advertisements.
Existing protocol messages such as Router Solicitation and Router
Advertisement were explicitly designed for communication between
routers and autoconfiguring hosts. While the options deployed in
this document may have worked interoperably in existing Neighbour
Discovery messages, existing assumptions about the roles of
particular message senders (particularly as defined in Appendix D of
[2]) would be violated in doing so.
The newly defined Router-to-Router message aims to be compatible with
future protocols requiring router negotiation and agreement, and
defines an extensible option format in the same manner as IPv6
Neighbour Discovery.
3.3 Deterministic Fast Router Advertisement Options
Deterministic Fast Router Advertisement Options provide the means by
which a router's interest in being a Fast Advertising Router is
advertised, as well as providing an indication of the router's Rank,
Daley, et al. Expires April 25, 2005 [Page 7]
Internet-Draft Deterministic FastRA October 2004
Fixed Delay and Separation.
These options are sent in Router-to-Router Status-Request messages
from routers which wish to learn other routers' Fast RA parameters,
and sent in Router-to-Router Status messages responding to these
requests. The option may also appear in Router Solicitations and
Advertisements when communicating between a router and a host.
This draft principally concerns the use and operation of routers
configuring FastRA with Deterministic Fast Router Advertisement
Options.
4. Message Formats
This document introduces one new ICMPv6 Message, the Router-to-Router
message (RtR). It also defines a new option for this message, The
Deterministic FastRA Option (DetFRAO).
4.1 Router to Router ICMPv6 message
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Code | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options ...
+-+-+-+-+-+-+-+-+-+-+-+-
Source Address
MUST be the link-local address assigned to the
interface from which this message is sent.
Destination Address
Typically the router-to-routers multicast
group (TBD Suggest: FF02::12).
Hop Limit 255
ICMP Fields:
Type TBD (Suggest 191)
Code 0 - Status Request
1 - Status
Daley, et al. Expires April 25, 2005 [Page 8]
Internet-Draft Deterministic FastRA October 2004
Checksum The ICMPv6 checksum.
Reserved This field is unused. It MUST be initialized to
zero by the sender and MUST be ignored by the
receiver.
Valid Options:
Advertisement Interval
The maximum delay between unsolicited Router
Advertisement messages. This option and its use
are defined in Mobile IPv6.
Deterministic Fast Router Advertisement
The configuration status for FastRA, as defined in
Section 4.2
of this document.
CGA An option providing information about the router's
cryptographically generated address, as defined in
SEND.
Nonce This option is provided in Status-Request messages,
and copied into Status messages when responding to
a particular Status-Request. It is defined in SEND.
Timestamp An indication of the time of a Status-Request or
Status message, as perceived at the transmitter.
This option is aims to reduce the chance of
messages being replayed, and is defined in SEND.
Signature A digital signature over the message (including the
CGA Type Tag, IPv6 Source and Destination addresses
and the entire ICMPv6 message without Signature
option). This option MUST be the last option in
the message, if present, and is defined in SEND.
Future versions of this protocol may define new option types.
Receivers MUST silently ignore any options they do not recognize
and continue processing the message.
Mobile IPv6 is defined in [4], SEND is defined in [5].
The Router-to-Router message comes with two different codes. A
Status-Request message asks peer routers which understand the message
to report back with their configuration for the options contained in
the message. A Status message either responds to a Status-Request or
Daley, et al. Expires April 25, 2005 [Page 9]
Internet-Draft Deterministic FastRA October 2004
periodically updates its peers of the configuration.
Sending of Status-Request messages is defined in Section 5.1.
Processing of Status-Request messages is performed as described for
each received option type (unknown options being ignored). A router
MUST respond to a Status-Request message with a Status message, even
if it contains no configuration status information.
Transmission of Status messages is defined in Section 5.2.
SEND options are ignored as regards requests for status by receiving
routers.
SEND option processing is as detailed in [5] and particularly, all
secured Router-to-Router messages MUST contain the Signature and
Timestamp options. Status-Request messages act as if they are
solicitations for the inclusion of CGA options and Nonce Options.
CGA and Nonce Options MUST also be present in Status messages which
respond to a Status-Request. Where the Status messages are sent
otherwise they SHOULD include the CGA Option regularly to ensure that
routers newly arrived on the link are able to verify their message.
4.2 Deterministic Fast Router Advertisement Option Format
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 | Rank | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Fixed Delay | Separation | Rel Pref |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Daley, et al. Expires April 25, 2005 [Page 10]
Internet-Draft Deterministic FastRA October 2004
Fields:
Type TBD (Suggest 13)
Length The length of the option (including the type and
length fields) in units of 8 octets. Routers
compliant with this document MUST set the
length to 1. If the option is received in a
Router-to-Router message with a length greater
than one the router MUST NOT read the option's
contents, and MUST set the IncompatibleFastRouters
flag on the interface until the advertising router
disappears or begins advertising with an option
length of 1.
Rank An integer in the range 0-255 indicating the the
ordinal position of the Fast Router.
Reserved This field MUST be set to zero and be MUST be
ignored by receivers.
Fixed Delay The minimum delay used by this router to send
Router Advertisements in response to Router
Solicitation.
(Units: milliseconds)
Separation A delay after the current router's Fixed Delay
that worse ranked routers wait before transmitting.
This is used by other routers when the subject
router is fastest.
(Units: milliseconds)
Rel Pref The Relative Preference of the router seeking to
perform Fast Router Advertisement. This is set
to the variable FastRARelPref.
This option may appear in Router-to-Router, Router Solicitation and
Router Advertisement messages. Nodes receiving this option in other
messages MUST ignore it, acting as if they didn't understand the
option.
4.2.1 Rank
The Router ranked 1 will be the fastest router, and MUST configure a
Fixed Delay of 0. No router may adopt a rank (other than
BOOTSTRAP_RANK) until it has undertaken router querying as defined in
Section 7.
Daley, et al. Expires April 25, 2005 [Page 11]
Internet-Draft Deterministic FastRA October 2004
4.2.2 Fixed Delay
The router determines its Fixed Delay by counting the number of
preceding routers (Rank - 1) and multiplying this by the fastest
router's Separation value.
The Fastest Router MUST set its Fixed Delay to 0.
4.2.3 Separation
This value for the Fast Router's Separation from subsequent Fast
Routers exceeds the maximum additional delay over Fixed Delay
required to transmit a Fast Router Advertisement.
This delay MUST allow for computation delays in forming the RA (such
as incurred with SEND) [5].
4.2.4 Relative Preference
This is an integer number providing the relative preference of the
fast router for Rank determination. It is controlled by the variable
FastRARelPref which MUST be configurable by the router's
administrator. This value is prepended to the 24 bit Rank Identifier
in order to provide a Ranking Score, as described in Section 6.
A lower value will increase the preference of the router, and will
outrank routers configured with the default preference value of
DEF_REL_PREF.
Changes in a router's FastRA preference MAY be advertised immediately
based on its newly calculated Rank, since routers should be checking
if the Ranking Identifier associated with a particular router already
exists in the Fast Router List, and will move the existing entry to
its new location in the Fast Router List.
5. Sending Router-to-Router messages
Router-to-Router messages indicate the router's current configuration
and may request a response from a peer router, with its own
configuration status.
5.1 Sending Router-to-Router Status-Requests
When seeking to learn about other routers' status, a router may send
Router-to-Router status Requests to its peers.
In doing so the router delays randomly for between 0 and
MAX_RTR_STATUS_REQ_DELAY, and then sends up to MAX_RTR_STATUS_REQS
Daley, et al. Expires April 25, 2005 [Page 12]
Internet-Draft Deterministic FastRA October 2004
requests separated by at least RTR_STATUS_REQ_INTERVAL seconds.
These messages are sent to the router-to-routers multicast group, and
contain the Nonce, Signature, CGA and Timestamp options (at least) if
CGA is used.
5.2 Sending Router-to-Router Status
Router-to-Router Status messages MAY be sent periodically to other
routers to update the peers although the router's own reachability is
readily confirmed by periodic unsolicited RA reception.
When changes in configuration occur, the router SHOULD send up to
MAX_RTR_STATUS_REQS separated by MIN_DELAY_BETWEEN_RTR_STATUS after
an initial random delay of between 0 and MAX_RTR_STATUS_DELAY.
Responses to Status-Request messages MUST be sent.
This responding Status MUST be sent after a random delay of 0 to
MAX_RTR_STATUS_DELAY. Additionally, multicast Status Messages MUST
NOT be sent more regularly than once every
MIN_DELAY_BETWEEN_RTR_STATUS on average.
Responding Status messages MAY be sent to the unicast source address
of the Status-Request. If MIN_DELAY_BETWEEN_RTR_STATUS has elapsed
since the last multicast Status message, the response SHOULD be
multicast to the router-to-routers group.
When a router's configuration the steady state, it adopts a periodic
Router-to-Router Status advertisement interval as specificed by
R2RStatusInt. The Advertisements are randomly distributed by their
random delay upon advertisement of configuration changes. However,
routers SHOULD periodically pause an additional random delay between
0 and MAX_RTR_STATUS_DELAY, in order to re-spread Status messages.
6. Ranking Calculation
When receiving Router-to-Router messages containing the DetFRAO, a
router may maintain a list of Fast Routers and determines a relative
order amongst them. Changes in the relative order trigger changes in
Router Advertisement delays, so calculations for Rank need to be done
simply, and reliably on information available in each
Router-to-Router message with a Deterministic FastRA option.
Every Router-to-Router message is sent from a unicast link-local
address uniquely owned (on the link) by the router. Additionally,
every DetFRA Option contains a Rel Pref variable, which indicates the
configured preference of this router over others.
Daley, et al. Expires April 25, 2005 [Page 13]
Internet-Draft Deterministic FastRA October 2004
When receiving an Router-to-Router message containing a DetFRAO, the
Ranking Score is calculated by appending the Rank Identifier to the
Rel Pref value received in the DetFRAO.
The Rank Identifier is created by taking the final 24 bits of the
router's advertising link-local address and XOR'ing this value with
0xffffff.
As an example, using 32 bit unsigned integers, Ranking Score
computation is as follows:
RankID = ((ntohl(ll.s6_addr32[3]) & 0x00ffffff) ^ 0x00ffffff);
RScore = RankID | (relpref << 24);
A discussion of the reasoning behind this algorithm is provided in
Section 6.1.
The router with the lowest Ranking Score assumes the Rank: 1, and the
next lowest Rank: 2, etc.
In the situation where routers share the same Ranking Score and
Identifier, comparison of the routers' complete IPv6 link-local
address is made, in order to break ties.
The Ranking Identifier SHOULD be used to determine if a received
router's preference has changed, by checking if the Ranking
Identifier (as a lookup for the Source Address of the received
message) is already present in the list, and has a different Ranking
Score. In this case, the old entry is overridden by a more recent
advertisement, and list entries consequently are re-Ranked.
Note that during ranking calculation the advertised option's Rank
field is not consulted, although it may be checked subsequently.
6.1 Ranking Score Calculation Reasoning
Selecting the low-order 24 bits of the IPv6 address allows selection
of fastest router in the case of interface identifier creation from
MAC-48 addresses, without reference to manufacturer's
Organizationally Unique Identifier (OUI). Use of the XOR reverses
the order of the IPv6 address suffix so that EUI-64 based addresses
favour newer routers rather than older ones (unlike in [8] for the
case where OUIs are the same), and the relative preference overrides
all[7].
Maintaining this structure (RelPref,Suffix) allows routers to check
not only the relative ordering of a router in the list on DetFRAO
Daley, et al. Expires April 25, 2005 [Page 14]
Internet-Draft Deterministic FastRA October 2004
reception, but allows even Router-to-Router messages which do not
contain DetFRAOs to update the validity of the Fast Router's existing
list entry by matching Rank Identifiers created from the RA's source
address (if this is a unique match).
7. Becoming a Fast Router
When a router wishes to be a Fast Router, it needs to check if anyone
else is acting as a Fast Router on this link. The router begins this
bootstrap process sending Status-Request messages containing a
DetFRAO, as defined in Section 5.1.
The Deterministic FastRA option in this case MUST contain the values:
Rank = BOOTSTRAP_RANK
Fixed Delay= BOOTSTRAP_DELAY
Separation = FastRASep
Rel Pref = FastRARelPref
Receivers will see this option and recognise that the requester is a
bootstrapping router. As defined in Section 8.3, the routers MUST
send a Status message responding to the request containing the DetFRA
option. This informs the requester of their own identity, Rank and
delays.
While collecting information about other routers, the bootstrapping
router MUST send Router-to-Router messages with the DetFRA option.
It MUST delay when sending responses to Router Solicitations by 0 to
MAX_RA_DELAY_TIME, and ensure that MIN_DELAY_BETWEEN_RAS separates
multicast advertisements.
After collecting this information, the new Fast Router calculates its
Rank and begins advertising as described in Section 9.1.
8. Receiving DetFRAO in ICMPv6 Router-to-Router
When receiving Router-to-Router messages with the DetFRAO option, the
router determines whether the transmitting router has been seen
before, and whether the transmitted Rank, Fixed Delay or Separation
have changed. If either the router is previously unseen or the
ranking or delay parameters have changed, the entry is inserted into
the list at the position indicated by the router's Ranking Scores.
If the delay or rank of the receiving router have changed, it
advertises its changed configuration as indicated in Section 9.1.
Daley, et al. Expires April 25, 2005 [Page 15]
Internet-Draft Deterministic FastRA October 2004
8.1 Receiving Bootstrap Deterministic FastRA Options
Deterministic FastRA routers or bootstrapping routers may receive
Router-to-Router messages containing a DetFRAO from a bootstrapping
router.
Routers SHOULD add such routers into their Fast Router List, in
anticipation of the router's arrival as a fully functioning Fast
Router.
Calculations for the Rank and Fixed delay of the bootstrapping Router
MUST NOT be made based on the values in the received Option, but on
the Ranking Score generated as described in Section 6. The Fixed
Delay calculated for the bootstrap router should be based on the best
ranked router's Separation, and the number of preceding routers.
Where the best ranked router is the bootstrapping router, this
router's Separation is used in Fixed Delay calculations.
8.2 Cleaning up old entries
If a Fast Router fails to receive multiple expected Router
Advertisement packets from a peer router, it SHOULD check if the peer
router is dead using either router or neighbour discovery . Such
mechanisms may be invoked upon non-reception of advertisements in
multiple retransmission intervals as advertised by the peer router,
or non-response to previous Router-to-Router Status-Request [4].
If the peer is dead, the local router removes its entry from the
list, and re-advertises its own preference and distance as defined in
Section 9.1, if any change has occurred.
If one of a router's preceding routers reduces their Rank, so that it
conflicts with another router in the list, a router MAY send a
Router-to-Router Status-Request message containing DetFRAO after a
random delay between 0 and MAX_RTR_STATUS_REQ_DELAY, to establish
whether routers are still reachable.
8.3 Responding to Status-Requests with DetFRAO
A router MUST send a Deterministic FastRA option to a router which
sends a Router-to-Router Status-Request to it, if the router is
trusted. Delays to Status message are described in Section 5.2.
9. Sending DetFRAOs in ICMPv6 Router-to-Router
Daley, et al. Expires April 25, 2005 [Page 16]
Internet-Draft Deterministic FastRA October 2004
9.1 Sending RAs on Rank or Delay Change
In the case that a router's Rank, Fixed Delay or Separation change,
it MUST transmit a Router-to-Router Status message after a delay of
between 0 and MAX_RTR_STATUS_DELAY seconds and then
MAX_INITIAL_RTR_STATUS-1 messages each separated by
MIN_DELAY_BETWEEN_RTR_STATUS seconds (as described in Section 5.2.
If subsequent changes occur within this interval, it extends such
that three multicast Router-to-Router Status messages are sent with
the new configuration. This allows all peer routers to be updated in
a configuration interval of less than 12.5 seconds, if one set of
changes occurs.
9.2 Sending Advertisement Intervals
When a router advertises Deterministic Fast RA Options in
Router-to-Router messages, it MAY also indicate the frequency of its
periodic Router-to-Router Status messages using Advertisement
Interval Options in the message if there is room.
This option allows receiving routers to know how often to expect
these Router Advertisements, so that they can check that the
advertising router is active if expected packets are not received (as
in Section 8.2).
Routers MAY send DetFRAOs occasionally in their periodic unsolicited
Router Advertisements, in order to show hosts their FastRA
configuration.
10. Sending Fast Router Advertisements
Fast Router Advertisements are sent in response to Router
Solicitations. Where Deterministic Fast Router Advertisement Options
have been exchanged, and the routers know their fixed delays, Router
Advertisements are transmitted to the solicitor after delaying for
the Fixed Delay.
The number of FastRAs which may be sent at any time are determined by
trading off the reasonable arrival rate of Router Solicitations, and
the bandwidth and delay consumption caused by having all of these
packets transmitted successively[6].
Determining good values for these outstanding FastRA bucket sizes is
not well described and may require further work. The values defined
in this document are approximations thought to be relatively harmless
based on other protocol defaults, at the time of writing.
Daley, et al. Expires April 25, 2005 [Page 17]
Internet-Draft Deterministic FastRA October 2004
10.1 Sending Unicast Fast RAs
The same resource DoS protection mechanisms for unicast FastRAs used
in the FastRA Draft are used in this document. Particularly, the
maximum token bucket size is limited to MaxFastRAs, which defaults to
MAXFASTRAS (10) [6].
The FastRA draft places up to MaxFastRAs tokens into the bucket each
multicast Router Advertisement interval.
In order to provide more flexible replenishment of FastRA resources,
a router MAY place unicast FastRA tokens into the bucket at a rate of
one every FastRARefreshIval ms, where this defaults to
FASTRAREFRESHIVAL.
10.2 Sending Multicast Fast RAs
Multicast Fast RAs are not supported in the original FastRA draft
[6]. It does make sense for routers to provide fast multicast
responses to Router Solicitations, where such solicitations do not
create sufficient neighbour cache state to allow immediate unicast
response.
Also, if a router has multiple Unicast FastRAs delayed before
transmission, it may be possible to send a multicast FastRA instead
at the earliest of the delay times, in order to reduce the number of
responses required.
Multicast Fast RA transmission is managed separately to unicast
transmission, and has a token bucket with a size of MaxMCFastRAs
which defaults to MAXMCFASTRAS.
Tokens are placed into this bucket at a rate of one every
MIN_DELAY_BETWEEN_RAS.
11. Interaction with Other Routers
Not all routers will understand Deterministic FastRA options or want
to be in a Fast Router List. This section describes interactions
between Fast Routers and other routers.
11.1 Presence of Legacy Routers
Deterministic Fast Routers ignore the presence of Legacy Routers when
building their Fast Router List. Fast Routers rely upon these
routers undertaking random delays according to IPv6 Neighbour
Discovery[2].
Daley, et al. Expires April 25, 2005 [Page 18]
Internet-Draft Deterministic FastRA October 2004
11.2 Ceasing to be a Fast Router
A router which no longer wishes to undertake FastRA may stop making
fast responses at any time, but SHOULD delay by a random value
between 0 and MAX_RTR_STATUS_DELAY, before sending
MAX_INITIAL_RTR_STATUS successive multicast Router-to-Router Status
messages. These messages MUST contain the DetFRA option with Rank
set to NOT_FAST_RTR_RANK and an advertised Fixed Delay of
NOT_FAST_RTR_DELAY. These multicast Router Advertisements SHOULD be
sent once every MIN_DELAY_BETWEEN_RTR_STATUS to the router-to-routers
group.
While a router advertises its Fixed Delay as NOT_FAST_RTR_DELAY, it
in fact reverts to the procedures defined in IPv6 Neighbour Discovery
[2].
Routers receiving this option in a Router-to-Router message SHOULD
remove the router from the Fast Routers List, and recalculate
subsequent Ranks and delays of routers remaining in the list.
This may lead to peer routers' re-advertisement of new Ranks and
delays as described in Section 9.1.
11.3 Presence of Non Fast Routers
While a router may be able to understand and process DetFRAOs, it may
not wish to be a Fast Router. Routers which have completed
advertising their leaving of the Fast Routers List fall into this
category.
These routers SHOULD act like legacy routers, and ignore
Deterministic FastRA options as if they didn't understand them.
11.4 Presence of Incompatible Fast Routers
When routers wishing to undertake FastRA exist on the link but are
not trusted for inclusion in the Fast Routers List, two distinct sets
of routers may appear.
Each set may not trust another, and may instead have its own router
at each Rank. In this case, the IncompatibleFastRouters flag SHOULD
be set on the interface until the untrusted routers become trusted,
or cease being Fast Routers.
Each Fast Router which has the IncompatibleFastRouters flag MUST
attempt to inform its administrator about the misconfiguration.
Daley, et al. Expires April 25, 2005 [Page 19]
Internet-Draft Deterministic FastRA October 2004
12. Configuration Parameters
The following parameters are defined in this document:
FastRARelPref A parameter which controls the
ranking of Fast Routers. It sets
the advertised Rel Pref field in
the DetFRAO. Setting this value lower
betters the preference of the router.
Minimum: 0
Maximum: 255
Default: DEF_REL_PREF
FastRASep A parameter controlling the delay between
scheduling of Fast Router Advertisements
on adjacent routers in the Fast Routers
List.
(Units: milliseconds)
Minimum: 1
Maximum: 255
Default: DEF_SEP
MaxFastRAs The maximum bucket size for Unicast
FastRAs.
Minimum: 0 (not Fast RA)
Default: MAXFASTRAS
MaxMCFastRAs The maximum bucket size for Multicast
FastRAs.
Minimum: 0 (no Multicast Fast RA)
Default: MAXMCFASTRAS
R2RStatusInt The interval between Router-to-Router
Status messages while in steady state.
Minimum: MIN_DELAY_BETWEEN_RTR_STATUS
Default: DEF_DELAY_BETWEEN_RTR_STATUS
13. Protocol Constants
Daley, et al. Expires April 25, 2005 [Page 20]
Internet-Draft Deterministic FastRA October 2004
BOOTSTRAP_DELAY 500ms
BOOTSTRAP_RANK 254
DEF_SEP 50ms
DEF_REL_PREF 127
MAXMCFASTRAS 5
MAX_INITIAL_RTR_STATUS 3
MAX_RTR_STATUS_REQ_DELAY 1000ms
MAX_RTR_STATUS_REQS 3
MAX_RTR_STATUS_DELAY 500ms
MIN_DELAY_BETWEEN_RTR_STATUS 3 seconds
DEF_DELAY_BETWEEN_RTR_STATUS 15 seconds
NOT_FAST_RTR_DELAY 500ms
NOT_FAST_RTR_RANK 255
RTR_STATUS_REQ_INTERVAL 4 seconds
UCASTFASTRAREFRESHIVAL 400ms
14. IANA Considerations
The new ICMPv6 message type - Router to Router (with two codes) and a
new ICMPv6 'Deterministic Fast Router Advertisement Option' are
defined in this document.
The Router-to-Router message is suggested to be an Informational
ICMPv6 message and is defined in Section 4.1.
In order to provide a unique multicast address for routers wishing to
participate in router-to-rotuer configuration, it is suggested the
IANA supply the following Link-Local Scope multicast address:
FF02:0:0:0:0:0:0:12 Router-to-Routers Configuration
(DetFRAO) is defined in Section 4.2 of this document. It is
suggested that the option number 13 is used for the Type of this
option.
15. Security Considerations
The Router-to-Router message's use of the Neighbour Discovery option
format allows SEND options to be used to check the authenticity of
the messages sent from the peer router.
The authorization of a node to be a router is described by a
delegation chain advertised in a succession of Delegation Chain
Advertisement messages. When using SEND, routers MUST check that the
router from which they receive a DetFRAO is an authorized router from
that link, and that the router trusts the delegation service used to
sign this authorization [5].
Daley, et al. Expires April 25, 2005 [Page 21]
Internet-Draft Deterministic FastRA October 2004
Where the Router-to-Router message is not trusted, but contains a
Deterministic FastRA Option, the router MUST NOT include the router
in its Fast Router List, but SHOULD set the IncompatibleFastRouters
flag on that interface. This will turn attempt to inform the
administrator of the configuration problem.
Where disjoint sets of routers each undertake FastRA (but don't trust
each other), they can choose the same delay timers for sending
FastRA. In the worst case this means that every FastRA sent will
collide with another RA. Administrative action is currently required
to fix this issue, but further work may establish if automated
robustness to this issue is desirable.
16. Acknowledgments
This work is based on and expands the FastRA internet-draft [6].
17. Changes Since Last Revision
17.1 draft-daley-dna-det-fastra-00 to -01
Force Fastest Router to respond with no delay MUST instead of SHOULD.
Allow calculation based on advertised Separation in fastest router
Removed section about duplicate list entries. Working from
calculated rank only now.
Cleaned up references to Router Advertisement and Router-to-Router.
Removed Misleading SHOULD from Status-Request response
Removed capability to use Advertisement Interval in RA for R2R.
Removed entire section about hosts using DETFRAO.
Added configuration option for Router-to-Router Status Interval (15s
Def).
18. References
18.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.
Daley, et al. Expires April 25, 2005 [Page 22]
Internet-Draft Deterministic FastRA October 2004
[3] Conta, A. and S. Deering, "Internet Control Message Protocol
(ICMPv6) for the Internet Protocol Version 6 (IPv6)
Specification", RFC 2463, December 1998.
[4] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in
IPv6", RFC 3775, June 2004.
[5] Arkko, J., Kempf, J., Sommerfeld, B., Zill, B. and P. Nikander,
"SEcure Neighbor Discovery (SEND)", draft-ietf-send-ndopt-05
(work in progress), April 2004.
[6] Kempf, J., Khalil, M. and B. Pentland, "IPv6 Fast Router
Advertisement", draft-mkhalil-ipv6-fastra-02 (work in progress),
October 2002.
18.2 Informative References
[7] Hinden, R. and S. Deering, "Internet Protocol Version 6 (IPv6)
Addressing Architecture", RFC 3513, April 2003.
[8] "IEEE standard for local and metropolitan area networks -
commmon specifications - Media access control (MAC) Bridges",
ISO/IEC IEEE Std 802.1d, 1998.
Authors' Addresses
Greg Daley
Centre for Telecommunications and Information Engineering
Department of Electrical and Computer Systems Engineering
Monash University
Clayton, Victoria 3800
Australia
Phone: +61 3 9905 4655
EMail: greg.daley@eng.monash.edu.au
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
Daley, et al. Expires April 25, 2005 [Page 23]
Internet-Draft Deterministic FastRA October 2004
Erik Nordmark
Sun Microsystems, Inc.
17 Network Circle
Mountain View, CA
USA
Phone: +1 650 786 2921
EMail: erik.nordmark@sun.com
Appendix A. State Diagram
Below is a state diagram for Fast Router Advertisement.
Legend:
-------
FD : Fixed Delay
TmrSet : Set Timer value(milliseconds)
DetFRAO: Deterministic Fast RA Option
RSResp : Response to Router Solicitation
S : Router-to-Router Status
SR: : Router-to-Router Status-Request
TmrExp : A timer expiry
TmrExp4: Fourth Timer Expiry(resets counter)
Daley, et al. Expires April 25, 2005 [Page 24]
Internet-Draft Deterministic FastRA October 2004
TmrExp,SR /-\ /-\ Recv: TmrExp,S /-\
TmrSet:4K | | | | DetFRAO TmrSet:3K| |
* \V \V \V
/----\ /-----\TmrExp4 /---------\ /-------\
|Not |-------------->|Boot |------->| Changed |-------->|Adv |
|Fast|TmrSet: |Strap| | RtrSet |Sort List|Change |
\----/[0,1000] \-----/ 7\---------/Calc:FD \-------/
^ RSResp ^\ / ^ ^ TmrSet: ^\ \
| Delay: | | / | | [0,500] | | \
| [0,500] \-/ / Option| | \-/ \
| | Change| | RSResp \
| Pref \ or Add| | Delay: FD |
| TmrExp,RA /-\ Change\ | |List /
\ TmrSet:3K | | \ | |Entry /
Stop \ \V \ | |Timeout /
FastRA\ /------\ /-------------\ /
\------|Adv | | Steady |<------------/
|Leave |<-------------| State | TmrExp4
\------/Leave List \-------------/
RSResp ^\ TmrSet:[0,500] ^\ RSResp
Delay: | | | | Delay: FD
[0,500] \-/ \-/
Daley, et al. Expires April 25, 2005 [Page 25]
Internet-Draft Deterministic FastRA October 2004
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 (2004). 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.
Daley, et al. Expires April 25, 2005 [Page 26]