Internet DRAFT - draft-goyal-roll-dv
draft-goyal-roll-dv
Internet Engineering Task Force M. Goyal
Internet-Draft University of Wisconsin Milwaukee
Intended status: Informational July 27, 2009
Expires: January 28, 2010
A Distance Vector Protocol for Routing Over Low Power and Lossy Networks
draft-goyal-roll-dv-01
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
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 January 28, 2010.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Abstract
This draft describes a distance vector protocol for routing over low
power and lossy networks (LLN).
Goyal Expires January 28, 2010 [Page 1]
Internet-Draft draft-goyal-roll-dv-01 July 2009
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. LLN Host Operation . . . . . . . . . . . . . . . . . . . . . . 4
4. LLN Router Operation . . . . . . . . . . . . . . . . . . . . . 5
5. Route Discovery and Maintenance . . . . . . . . . . . . . . . 6
6. Routing Loop Detection and Correction . . . . . . . . . . . . 9
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
8. Security Considerations . . . . . . . . . . . . . . . . . . . 11
9. Informative References . . . . . . . . . . . . . . . . . . . . 11
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12
Goyal Expires January 28, 2010 [Page 2]
Internet-Draft draft-goyal-roll-dv-01 July 2009
1. Introduction
This draft describes a distance vector protocol for routing over low
power and lossy networks (LLN) to meet the requirements of different
LLN applications [I-D.ietf-roll-building-routing-reqs]
[I-D.ietf-roll-home-routing-reqs] [I-D.ietf-roll-indus-routing-reqs]
[RFC5548]. This protocol supports optimal routing for both
multipoint-to-point and point-to-point traffic flows while requiring
the LLN routers to maintain minimal routing state.
This protocol presents an alternative to RPL [I-D.dt-roll-rpl]. RPL
is based on organizing LLN routers along directed acyclic graphs
(DAGs) with LLN Border Routers (LBR) as roots. In other words, RPL
allows LLN routers to advertize routing costs for LBRs only. Under
RPL, point-to-point routing between two arbitrary LLN nodes takes
place along one or more DAGs that connect the two nodes together.
RPL does not yet specify a mechanism to achieve more optimal point-
to-point routes "across" a DAG. In contrast, this protocol supports
on-demand discovery of optimal routes for any destination and
continuous maintenance of established routes. Thus, this protocol
allows optimal (or good quality) routes to be established for any
destination based on one or more routing metrics defined in
[I-D.ietf-roll-routing-metrics]. Such routes can be used by any
traffic flow irrespective of whether it is point-to-point, point-to-
multipoint or multipoint-to-point in nature.
This protocol categorizes LLN nodes as routers and hosts. An LLN
host has very simple operation, needs minimal configuration and does
not participate in routing of packets. An LLN router participates in
the routing operation and needs to maintain state about only those
destinations that the router itself, or the nearby routers, need to
reach.
2. Terminology
This draft follows the ROLL terminology as detailed in
[I-D.ietf-roll-terminology]. The following additional terms are used
in this document:
LLN Host: An LLN node that only sources or sinks packets. Also
referred to as host in this document.
LLN Router: An LLN node that is willing to forward packets between
arbitrary source-destination pairs. Also referred to as router in
this document.
LLN Node: An LLN host or router. Also referred to as node in this
Goyal Expires January 28, 2010 [Page 3]
Internet-Draft draft-goyal-roll-dv-01 July 2009
document.
Routing Domain: The LLN is divided into routing domains to limit the
scope of route discovery and maintenance. By default, the routes to
a destination are searched only within the routing domain. Thus, the
routing domain boundaries should be determined such that most source-
destination pairs lie in the same domain. The domain information
needs to be configured in LLN routers only. The LLN hosts are
assumed to belong to the same domain as their neighbor LLN routers.
Thus, an LLN host may belong to multiple domains.
In-domain Destination: A destination in the same domain as the LLN
router.
Universal Destination: A destination for which the route discovery
and maintenance operations do not observe domain boundaries.
3. LLN Host Operation
An LLN host can only originate or sink a packet. It can not forward
the packets originated by another LLN node. If an LLN host needs to
send a packet to an LLN node within its radio range, it can do so
without involving an LLN router. Otherwise, the LLN host needs to
send the packet to an LLN router that forwards the packet further
towards its final destination.
An LLN host maintains a Neighbor Table of other LLN nodes in its
radio range. The neighbor table is maintained by overhearing packets
originated by the LLN nodes in the radio range. The entries in the
neighbor table expire after a pre-configured time interval unless
refreshed. The entry for an LLN router also includes the routing
domain to which the LLN router belongs. When an LLN host needs to
send a packet to a destination not in the neighbor table, it forwards
the packet to an LLN router in the neighbor table. If the LLN host
knows about the routing domain of the destination, it forwards the
packet to an LLN router belonging to the same domain. The LLN host
may learn the routing domain of a remote destination from a packet
received from that destination.
An LLN host may periodically originate Host Advertisements (HA) via
1-hop broadcast. An HA serves two purposes:
o First, an HA lets the neighbor LLN routers know of the host's
existence so that the routers may send to the host any packets
addressed to it. An LLN router may perform a handshake (packet
exchange) with the LLN host to test for bidirectional
communication. The LLN host may set a flag in its HA to mark
Goyal Expires January 28, 2010 [Page 4]
Internet-Draft draft-goyal-roll-dv-01 July 2009
itself as a universal destination.
o Secondly, an HA may contain a Route Discovery List in which the
LLN host can specify the destinations to which it needs to send
packets to.
4. LLN Router Operation
An LLN router maintains the following conceptual data structures:
o Neighbor Table: List of LLN nodes in the radio range. The
neighbor table is maintained by overhearing packets, including HAs
and RAs, originated by the LLN nodes in the radio range. The
entries in the neighbor table expire after a pre-configured time
interval unless refreshed. For each LLN router in the neighbor
table, the LLN router maintains link-level routing cost to reach
the neighbor router.
o Route Discovery Table: List of remote destinations to which the
router needs to discover routes to. When the router receives an
HA or an RA listing a destination to which a route is desired, the
router enters the destination in this table and initiates the
route discovery. The route discovery table contains in-domain or
universal destinations only. If an entry is created in the route
discovery table in response to a received RA, the entry remembers
the router that originated this RA. Repeated listing of the
destination in the route discovery list of this router's RA acts
to refresh the entry's existence in the route discovery table.
Otherwise, the entry expires after a certain time.
o Route Maintenance Table: This table consists of destinations to
which the router, or the nearby routers, currently send, or need
to send, packets to. The characteristics of the route maintenance
table are as follows:
* Each entry in this table consists of the costs to reach the
destination via each router in the neighbor table that has
advertised reachability to this destination unless the
destination is also listed in the neighbor table, in which case
the costs to this destination advertised by neighbor routers
are ignored (in other words, a router never forwards a packet
to a neighbor router if the packet's destination is listed in
the neighbor table).
* In addition to the cost, each entry also keeps track of the
"routing interest" of each router in the neighbor table in
reaching the destination. The routing interest is a metric
Goyal Expires January 28, 2010 [Page 5]
Internet-Draft draft-goyal-roll-dv-01 July 2009
between 0 and 1 indicating a router's interest in maintaining
routing state for a destination. A router advertises this
metric for a destination in the route maintenance list of its
RA (described later in this section) along with the cost to
reach that destination. A router advertises the routing
interest value 1 for a destination if that destination exists
in its route discovery table. If a router currently routes
packets towards a destination, it advertises routing interest
value 1 for this destination. Otherwise, the routing interest
of a router towards a destination is the product of a pre-
configured constant (less than 1) and the maximum routing
interest any neighbor router has for this destination. A
router maintains an entry in its route maintenance table as
long as its routing interest in that destination is more than a
pre-configured threshold.
* All destinations in the route discovery table exist in the
route maintenance table as well.
* The route maintenance table consists of in-domain or universal
destinations only.
o Routing Table: The next hop routers for each destination to which
the router needs to send packets to.
The Router Advertisement (RA) generated by the router includes the
following information:
o a Route Discovery List consisting of a subset of entries in the
route discovery table; and
o a Route Maintenance List advertising the router's best cost, as
well as the routing interest, to reach a subset of entries in the
route maintenance table.
Each entry in the route discovery and maintenance tables includes an
"advertised" flag that indicates if this entry was recently included
in the route discovery or route maintenance list of the router's RA.
The "advertised" flags are periodically reset using a yet-unspecified
mechanism. The entries with "advertised" flag false receive
preference for inclusion in the route discovery/maintenance list when
the router generates its new RA.
5. Route Discovery and Maintenance
When an LLN router receives a route discovery list in an HA/RA, it
checks, using the information in its neighbor and route maintenance
Goyal Expires January 28, 2010 [Page 6]
Internet-Draft draft-goyal-roll-dv-01 July 2009
tables, whether it can reach the destinations listed in there.
If the received packet is an HA and the router can not yet reach some
of the destinations in the route discovery list, the router does the
following:
o It creates entries for all such unreachable destinations in its
route discovery and maintenance tables as long as they are in-
domain or universal; and
o It resets the Trickle [trickle] timer that governs its RA
generation to the minimum value.
If the received packet is an RA and the route discovery list in the
RA is not empty, the router does the following:
o It resets the trickle timer that governs its RA generation to the
minimum value;
o If any destination in the route discovery list of the RA is
present in the router's neighbor table but not in the route
maintenance table, an entry is created for this destination in the
route maintenance table as well;
o It resets the "advertised" flag of all entries in its route
maintenance table corresponding to reachable destinations listed
in the route discovery list of the received RA so that these
destinations can soon be included in the route maintenance list of
the RAs the router generates;
o It creates entries in its route discovery and maintenance tables
(with "advertised" flag false) for all unreachable destinations
listed in the route discovery list of the RA unless such entries
already exist and as long as these destinations are in-domain or
universal. These entries include the identity of the router whose
RA triggered their creation.
o An existing route discovery table entry is refreshed, i.e. allowed
to exist for a certain additional time duration, if it was created
in response to an RA from this router and the current RA includes
in its route discovery list the destination corresponding to this
entry.
Thus, when an LLN host needs to send packets to a destination, it
includes the destination in the route discovery list of its HA. On
receiving this HA, the LLN routers in the neighborhood, if they don't
already know of a route to this destination, soon include the
destination in the route discovery list of their RAs. Thus, the LLN
Goyal Expires January 28, 2010 [Page 7]
Internet-Draft draft-goyal-roll-dv-01 July 2009
routers in the domain quickly come to know of the need to find a
route to this destination. If a router can reach this destination,
it advertises its cost to reach the destination in the route
maintenance list of its RA. As mentioned before, a router advertises
a routing interest 1 in a destination as long as the destination is
in its route discovery table.
When a router receives an RA that advertises in its route maintenance
list reachability to a destination for which the router has an entry
in its route discovery table, the router does the following:
o It updates the corresponding entry in its route maintenance table
with new cost and routing interest information received in the RA;
o It creates an entry in the routing table for this destination or
updates the existing routing table entry based on new information;
o If the router created the route discovery table entry in response
to an HA by a neighbor host or in response to its own need to
reach that destination, the router may delete the entry from the
route discovery table or it may choose to retain the entry for
some more time to allow additional neighbor routers to advertise
routes to this destination.
o It resets the trickle timer that governs its RA generation to the
minimum value.
Thus, as router X, that had created an entry in its route discovery
table in response to an HA from a neighbor host, receives
reachability advertisements from neighbor routers for this
destination, it deletes the entry from its route discovery table and
hence stops including this destination in the route discovery list of
its RAs. This leads to removal of this destination from the route
discovery table of neighbor routers that had created the route
discovery table entry in response to an RA from router X. Ultimately,
this destination is removed from the route discovery tables of all
routers in the domain.
Once a router has removed a destination from its route discovery
table, further existence of this destination in the router's route
maintenance table depends on the router's routing interest in this
destination. Periodically, the router checks for each entry in its
route maintenance table whether it is currently routing packets to
that destination. If yes, the router associates routing interest 1
with that destination. Otherwise, if the destination previously had
a routing interest 1 associated with it, the route maintenance table
entry is placed in the "observation" mode for a certain time during
which the router collects the routing interest of the neighbor
Goyal Expires January 28, 2010 [Page 8]
Internet-Draft draft-goyal-roll-dv-01 July 2009
routers in this destination. When the entry comes out of the
"observation" mode and if the router still thinks that it does not
send any packets to this destination, it calculates its routing
interest in this destination as the product of a local pre-configured
constant (less than 1) and the best routing interest it could find
among its neighbor routers in this destination. If the calculated
routing interest is less than a pre-configured value, the router
deletes the entry from its route maintenance table. Otherwise, the
router stores the calculated routing interest value in the route
maintenance table entry for use in its future RAs.
Thus, during the route discovery phase for a destination, all routers
in the routing domain (or all routers in the LLN if the destination
is universal) may maintain state about the destination. However,
afterwards, only routers in the vicinity of the existing routes to
this destination maintain state about the destination. The
definition of "vicinity" depends on how a router degrades its routing
interest in a destination if it is not itself sending packets to this
destination and what threshold value is used to decide whether the
router's routing interest in the destination is too little.
6. Routing Loop Detection and Correction
When a router forwards a packet, it puts its current cost to reach
the packet's destination in the packet header. When a router
receives a packet, it compares the cost listed in the packet's header
with its own cost to reach the packet's destination. If the cost
listed in the received packet's header is less than the router's own
cost to reach the packet's destination, the router assumes the
existence of a routing loop and does the following:
o It reduces the trickle timer governing the generation of its RAs
to its minimum value;
o It originates a special "path accumulation" packet with same
destination as the packet that led to the loop detection.
When a router receives the "path accumulation" packet going towards
destination X, it does the following:
o The router checks the accumulated path and if it does not find
itself listed in there, the router adds its address to the
accumulated path in the packet and forwards the packet further
towards its destination;
o Otherwise, the router identifies all the routers involved in the
loop and discards the "path accumulation" packet. In order to
Goyal Expires January 28, 2010 [Page 9]
Internet-Draft draft-goyal-roll-dv-01 July 2009
correct the routing loop, the router enters the "loop correction"
state and performs the following actions:
* It modifies the route maintenance table entry for destination X
and lists infinity as each neighbor router's cost to reach
destination X. Note that the cost of all neighbor routers to
reach destination X is set to infinity irrespective of whether
they are identified to be in loop or not. This is done because
the currently advertized cost of all neighbor routers may be
tainted by the costs advertized by the routers in the loop.
* It immediately generate an RA listing an infinite cost to reach
destination X. This RA also includes the list of nodes
identified to be in the loop. While the router is in the "loop
correction" state, it periodically generates additional such
RAs irrespective of the trickle timer settings.
The sojourn in the "loop correction" state lasts for a certain pre-
configured time interval. While in the "loop correction" state, the
router can not add any new next hops for destination X. Thus, while a
router is in the "loop correction" state, it simply buffers or drops
packets going to destination X. A router in the "loop correction"
state updates the neighbor routers cost to reach X based on the
received RAs. But, as mentioned before, it can not choose a new next
hop and it continues to advertise its own cost to reach X as
infinity.
When a router B receives an RA from router A that identifies B to be
involved in a routing loop for destination X, router B notes the IDs
of routers involved in the loop and enters the "loop correction"
state taking the actions identified above.
Thus, all routers involved in the loop enter the "loop correction"
state and advertise infinite cost to destination X. The neighbor
routers of these routers will generate new RAs advertising new costs
for destination X that exclude previously in-loop routers from
consideration. Assuming that:
o a path, excluding in-loop routers, does exist from the router to
destination X and
o the "loop correction" state lasts long enough to allow the router
to receive new advertisements from all its neighbor routers based
on such a path,
the router would select one such out-of-loop neighbor router as a
next hop for destination X when it comes out of the "loop correction"
state. Immediately, the router generates a new RA listing its new
Goyal Expires January 28, 2010 [Page 10]
Internet-Draft draft-goyal-roll-dv-01 July 2009
cost to destination X.
Thus, all previously in-loop routers, when they come out of the "loop
correction" state, advertise any paths they may have to destination X
that do not include previously in-loop routers. These advertisements
would allow these routers to determine new optimal, and loop-free,
paths to destination X.
7. IANA Considerations
TBD
8. Security Considerations
TBD
9. Informative References
[I-D.dt-roll-rpl]
Winter, T. and R. Team, "RPL: Routing Protocol for Low
Power and Lossy Networks", draft-dt-roll-rpl-01 (work in
progress), July 2009.
[I-D.ietf-roll-building-routing-reqs]
Martocci, J., Riou, N., Mil, P., and W. Vermeylen,
"Building Automation Routing Requirements in Low Power and
Lossy Networks", draft-ietf-roll-building-routing-reqs-05
(work in progress), February 2009.
[I-D.ietf-roll-home-routing-reqs]
Porcu, G., "Home Automation Routing Requirements in Low
Power and Lossy Networks",
draft-ietf-roll-home-routing-reqs-06 (work in progress),
November 2008.
[I-D.ietf-roll-indus-routing-reqs]
Networks, D., Thubert, P., Dwars, S., and T. Phinney,
"Industrial Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-indus-routing-reqs-06 (work in
progress), June 2009.
[I-D.ietf-roll-protocols-survey]
Tavakoli, A., Dawson-Haggerty, S., and P. Levis, "Overview
of Existing Routing Protocols for Low Power and Lossy
Networks", draft-ietf-roll-protocols-survey-07 (work in
Goyal Expires January 28, 2010 [Page 11]
Internet-Draft draft-goyal-roll-dv-01 July 2009
progress), April 2009.
[I-D.ietf-roll-routing-metrics]
Vasseur, J. and D. Networks, "Routing Metrics used for
Path Calculation in Low Power and Lossy Networks",
draft-ietf-roll-routing-metrics-00 (work in progress),
April 2009.
[I-D.ietf-roll-terminology]
Vasseur, J., "Terminology in Low power And Lossy
Networks", draft-ietf-roll-terminology-01 (work in
progress), May 2009.
[RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel,
"Routing Requirements for Urban Low-Power and Lossy
Networks", RFC 5548, May 2009.
[trickle] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S.,
Patel, N., Polastre, J., Shenker, S., Szewezyk, R., and A.
Woo, "The emergence of a networking primitive in wireless
sensor networks", Communications of the ACM , July 2008.
Author's Address
Mukul Goyal
University of Wisconsin Milwaukee
3200 N Cramer Street
Milwaukee, Wisconsin 53201
USA
Phone: +1 414 229 5001
Email: mukul@uwm.edu
Goyal Expires January 28, 2010 [Page 12]
