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]