ROLL WG G. Mulligan Internet-Draft Proto6 Expires: September 2, 2010 March 1, 2010 Optimized RIP for embedded RF networks draft-mulligan-roll-ripless-00.txt Abstract This document specifies an optimization to the Routing Information Protocol (RIP) routing protocol for use in embedded RF IPv6 internets such as those used in 6lowpan [7] networks. RIPless specifies the minimal changes to RIP, as specified in RIPng [2], RIP [3] and RIPv2 [4] to allow the protocol to be used in a lossy RF network where the routing fabric of the network is built upon powered nodes and that only the edge devices may be battery powered. 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 September 2, 2010. Copyright Notice Copyright (c) 2010 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 Mulligan Expires September 2, 2010 [Page 1] Internet-Draft RIPless Routing Protocol March 2010 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Routing Plane vs. Forwarding Plane . . . . . . . . . . . . 4 1.2. RIP Optimizations . . . . . . . . . . . . . . . . . . . . 4 2. Definition Of Terms . . . . . . . . . . . . . . . . . . . . . 4 3. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 5. RIPless Operation . . . . . . . . . . . . . . . . . . . . . . 6 5.1. 6LR and 6LER operation . . . . . . . . . . . . . . . . . . 7 5.2. 6LowPAN Host operation . . . . . . . . . . . . . . . . . . 7 6. RIP Optimizations . . . . . . . . . . . . . . . . . . . . . . 7 6.1. Routing Metric . . . . . . . . . . . . . . . . . . . . . . 7 6.2. Count to Infinity . . . . . . . . . . . . . . . . . . . . 8 6.3. RIP message timing . . . . . . . . . . . . . . . . . . . . 8 6.4. Requiring Split Horizon . . . . . . . . . . . . . . . . . 8 6.5. Compresses Addresses . . . . . . . . . . . . . . . . . . . 8 6.6. Modification to RIP message format . . . . . . . . . . . . 8 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 10.1. Normative References . . . . . . . . . . . . . . . . . . . 11 10.2. Informative References . . . . . . . . . . . . . . . . . . 11 Appendix A. Summary of optimizations . . . . . . . . . . . . . . 12 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12 Mulligan Expires September 2, 2010 [Page 2] Internet-Draft RIPless Routing Protocol March 2010 1. Introduction RIPless is an optimization to the Routing Information Protocol (RIP) as specified in RIPng [2], RIP [3] and RIPv2 [4] to allow the protocol to be used in a lossy RF network. The RF network envisioned to use RIPless is different from the network planned for the RPL protocol [10]. Where RPL was designed to take into account and deal with battery operated routers RIPless assumes that the "routers" inside the RF network have plenty of power, but that as with all low-output-power RF networks, the "link" is lossy and devices that at one moment are on-link the next moment may not. Because the routing fabric of the RF network is not power resource limited and is expected not to be bandwidth limited, it is alright to send periodic routing update information - even occasional flooding is not prohibitive. In addition, the goals of RIPless are to provide a good mechanism for forwarding packets from the Internet into the 6LowPAN network and to the end nodes and to provide a good ability to transmit packets point to point (P2P) within the 6LowPAN. This is in addition to ability to send data from 6LowPAN nodes to Internet devices and servers (MP2P). It is also envisioned that through the use of network prefixes RIPless will allow route aggregation witin the 6LowPAN network thereby reducing routing table entries to just include 6LowPAN routers and not Hosts connected by those routers. Since RIP is one of the most widely depolyed and well understood routing protocols the goal was to change as little as possible in the fundementals of RIP, but to make only those optimizations necessary to allow RIP to operate in these resource constrained (memory and output power) devices. This document does not describe the theory of RIP or Distance Vector protocols. For background and understanding of RIP, read RFC1058 [3] and RFC2080 [2]. It is important to understand that generally the devices that ran RIP had multiple interfaces and that RIP was used to route between those interface. In the case of RIPless, the devices on a 6LowPAN network have only a single interface (except for the 6LowPAN Edge Router) and that RIPless is used to forward routing information over a single interface, but between routing nodes. Because the focus for this development is 6lowpan [7] type networks, the basis of RIPless is the RIPng [2] since it updates RIP for use with IPv6 addresses. Mulligan Expires September 2, 2010 [Page 3] Internet-Draft RIPless Routing Protocol March 2010 1.1. Routing Plane vs. Forwarding Plane Like RIP, RPL, OSPF, IS-IS and most other routing protocols, this document does not attempt to change the separation of the "Routing Plane" from the "Forwarding Plane". Separation of routing plane and forwarding plane came from the fact the changes in routing topology tended to be very infrequent compared to the frequency of packets being forwarded. The number of packets transmitted is very large compared to number of changes in routing therefore it was important to try to make packet forwarding very fast and efficient compared to detecting changes in routing topology. In RF this may be different as the time scale for changes in routing is much smaller (especially over a large mesh network) when compared to the number of packets being transmitted. Combining the Routing plane and forwarding plane, while out of scope for this document, might provide a more efficient and robust mechanism for moving packets through RF connected links. 1.2. RIP Optimizations As stated the goal of this document is to change only those things that are necessary to allow RIP to be used in this RF lossy environment, but to leave the basic operating fundementals unchanged. To that end only the following are the optimizations: o Routing Metric o Count to Infinity o RIP message timing o Require Split Horizon o Compressed addresses o RIP message format 2. Definition Of Terms The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [1]. 6LowPan-link: It is a wireless link determined by single hop reachability of neighboring nodes. 6LowPan-router(6LR): These are the intermediate routers in the 6LowPan network who can communicate with other 6LowPan-routers in the same 6LowPan network. These are also the immediate first-hop router for 6LowPan host nodes. 6LowPan routers are present only in "route- Mulligan Expires September 2, 2010 [Page 4] Internet-Draft RIPless Routing Protocol March 2010 over" topologies. 6LowPAN Edge Router(6LER): It is a 6LowPan-router located at the junction of 6LowPan networks or between a 6LowPan network and a legacy IP network. There may be one or more 6LER. network. Host node: A host node in 6LowPan network is considered a IPv6 node without routing and forwarding capability. Mesh-under: A network configuration topology where 6LowPan host nodes are connected to the 6LowPAN Edge Router through a the use of Layer-2 forwarding. In a "mesh-under" configuration all IPv6 host nodes in a 6LowPan network are only one IP hop away from any other 6LowPAN host, 6LER within the 6LowPAN network. This topology simulates the typical IP-subnet topology with one router with multiple nodes in the same subnet. Route-over: This is a configuration where 6LowPan host nodes are connected to the 6LER through a set of intermediate Layer-3 routers (6LR). Here host nodes are typically multiple hops away from the 6LER. The Route-over topology typically consists of a IPv6 edge router, a set of nodes capable of IP routing and possibly some host nodes. 3. Assumptions o 6LowPan nodes will use EUI-64 style Interface-id in their IPv6 address. Optionally for 16-bit IEEE 802.15.4 short addresses, DHCP addresses are recommended to ensure address uniqueness. o All routers (6LRs and 6LERs) are powered and do not sleep, ie. they are "always on". As a result periodic routing update messages are not prohibitive. o 6LowPAN networks will be relavtively limited in size and depth. It is not expected that within any single 6lowpan there will be more than 50 routing nodes, though there could very likely be 10 to 20 host nodes "attached" to each routing node. o 6LRs are highly memory and processing constrained and as such cannot store very large routing tables. o A 6LER is capable of routing/forwarding packets between a 6LowPan network and a backbone network. The 6LER is responsible for assigning a /64 IPv6 prefix to the 6LowPan network. It advertises one or more IPv6 prefixes to the 6LowPAN network. o The 6LRs that are in range of 6LER use the /64 prefix advertised by the 6LER. The 6LRs store this prefix and use them for forming its own global autoconfigured addresses. 6LRs may use DHCP for short address assignment. When sending Router Advertisements, 6LowPan-routers use the same prefix(es). A 6LR SHOULD relay any prefix related options received from its parent router during Mulligan Expires September 2, 2010 [Page 5] Internet-Draft RIPless Routing Protocol March 2010 Neighbor Discovery procedure. o The 6LowPan host nodes either autoconfigure IPv6 address based on the prefix received in the Router Advertisement, or it uses DHCP for short address assignment. It can receive multiple Router Advertisements and should configure at least one default router as its immediate nexthop. It may configure multiple default routers, but this is implementation specific. The 6LowPan host nodes always send their packets to the default router. If one default router becomes unavailable, it chooses the next available default router or it may restart the ND process. 4. Applicability Statement This document aims to guide implementors in choosing an appropriate routing protocol for a 6LowPan network that conforms to the previous assumptions. In particular, sensor and Smart Grid networks where the routing fabric of the network will be "always-on" and where only the host nodes may sleep. In addtion, this protocol would be usable highly constrained devices with limited RAM or processing power, so long as the total number of routing nodes in the 6LowPAN is limited to approimately 50. The total number of nodes within the 6LowPAN could be greater than 500. 5. RIPless Operation The enviroment for a 6LowPAN network to use RIPless is one where the 6LRs are "always-on". They may be line-powered or powered by very large batteries or some form of energy harvesting, but they do not sleep. Clustered around each of the 6LRs are a number of 6LowPAN hosts (o in the figure below). These host nodes may be always-on or may sleep, but they expect that the routing fabric will be available when they need to send data. This is not to say that they expect that the particular 6LR that they "spoke" with prviously (their "default router") will be available, but that some 6LR will respond to RS/RA messages should the default router not be available. In addtion to the 6LRs, there will be at least one 6LER in the network that attaches the 6LowPAN network to "Legacy" or wired world. Mulligan Expires September 2, 2010 [Page 6] Internet-Draft RIPless Routing Protocol March 2010 o o | | o-LR--LR-o | | o | o-ER-o | =========== Legacy It is important to understand that the RIP routing information used within the 6LowPAN network will not be used or "leaked" past the 6LER. Just because RIP is being used inside the 6LowPAN network does not mean that the routing nodes inside the network exchange or participate in any RIP routing outside the 6LowPAN network - the 6LowPAN network is a distinct and separate sub-network. 5.1. 6LR and 6LER operation It is expected that the 6LER will run some routing protocol to both advertise the 6LowPAN network and to participating in routing over the Legacy network. The 6LR will likely advertise a "default route" to the 6LowPAN network. Each node within the 6LowPAN network will use some form of Neighbor Discovery to learn the 6LRs or 6LERs around it. The 6LRs will run the RIPless protocol to echange routing information with other neighbor 6LRs or the 6LER. 5.2. 6LowPAN Host operation The 6LowPAN hosts will also use a Neighbor Discovery mechanism to learn of the 6LRs or 6LERs nearby. The will simply configure the learned router as their default router. If that router is not available when the host needs to send data, it will learn of a new default router through another RS/RA exchange or if so configured will use an alternative default router. 6. RIP Optimizations This sections decribes the modifications and optimizations to the basic RIP routing protocol. 6.1. Routing Metric The routing metric described in the RIP RFCs is a simple hop-count. It is thought in the RF sensor networking community (???need reference???) that just a simple hop count is insufficient to Mulligan Expires September 2, 2010 [Page 7] Internet-Draft RIPless Routing Protocol March 2010 properly determine the "best path" between two nodes. It is suggest here that a weighted hop-count might provide a better metric. The hop-count would be weighted by the RSSI/LQI value for the link between each node. The specific weighting could be implementation specific, but for an IEEE 802.15.4 [9] type network using 8 discrete LQI values links with an LQI of 0x00 and 0x01 might have the metric set to "infinite", LQIs of 0x02 through 0x05 would set metric to 2 and an LQI of 0x06 or 0x07 would use the standard metric value of 1. If the implementor would rather use RSSI values or more values in LQI (256) are available some different step funtion might be use. 6.2. Count to Infinity The current value for Infinity in RIP is 15. For these small 6LowPAN networks the value 15 is probably too large. This large value means that it takes more time for routes to converge when route disappears. Therefore rather than using the standard value of 15 for infinite a smaller value of 6 MUST be used. 6.3. RIP message timing The standard timing for RIP update messages is 30 seconds. This appears to be much to slow for usefulness in the 6LowPAN environment. It is expected that the RF connectivity between nodes will change more frequently and as a result the timing for RIP messages SHOULD be reduced to 15 seconds. Since it is assumed that the routing nodes are powered this will not impact battery lifetime as there is no battery. 6.4. Requiring Split Horizon This section is still TBD 6.5. Compresses Addresses Since IPv6 addresses are very large and since the frame size of IEEE 802.15.4 is very small, rather than sending full IPv6 addresses the IPv6 network prefix MUST be elided and only the EUI 64 or the short address will be sent. 6.6. Modification to RIP message format The standard RIPng message format is: Mulligan Expires September 2, 2010 [Page 8] Internet-Draft RIPless Routing Protocol March 2010 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | command (1) | version (1) | must be zero (2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Route Table Entry 1 (20) ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ ... ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Route Table Entry N (20) ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ where each Route Table Entry (RTE) has the following 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ IPv6 prefix (16) ~ | | +---------------------------------------------------------------+ | route tag (2) | prefix len (1)| metric (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ instead a new RTE will be used: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |reserved |w|S|s|prefix len |resevered | mtrc | rsvd | +---------------------------------------------------------------+ | IP address | | Who (optional) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The "w" bit is set if the information about who the route was recieved from is present. Mulligan Expires September 2, 2010 [Page 9] Internet-Draft RIPless Routing Protocol March 2010 The "S" bit is set if the IP IID is a short addresses. The "s" bit is set if the who address is a short addresses. The "mtrc" is the metric field. The Prefix len to specify that the IP address is a subnet prefix rather than an IID. This would allow for route aggregation for all 6LowPAN hosts "attached" to a specific router and thereby reducing the number of routing table entries required as opposed to a completely flat routing topology. As mentioned rather than full IPv6 addresses being sent the Network Prefix would be elided and only the EUI 64 IID or the short address would be sent. Rather than sending the Prefix length the field will be used differently. The S bit is set to indicate that a short address is being used. It was suggested in RIPng [2] that the RIP message format be updated to include information about who the route was heard from for each route in the RIP message. The purpose of this is reduce the convergence time. Since message latency can be an important factor in 6LowPAN networks reducing the time to determine the proper route can be critical. Therefore in RIPless each RIP packet may include who the route was heard from. 7. Security Considerations These optimizations are not known to introduce any new threats against RIP beyond what is already documented for RIP[RFC 2080]. The 6lowpan security analysis [12] discusses possible threats. 8. IANA Considerations There are no IANA considerations for this document. 9. Acknowledgements The ideas behind this came from discussion with a number of people including Matt Gillmore, Pat Kinney, Eric Gnoske, Colin O'Flynn and folks working on 6LowPAN and ROLL WGs. 10. References Mulligan Expires September 2, 2010 [Page 10] Internet-Draft RIPless Routing Protocol March 2010 10.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Malkin, G. and R. Minnear, "RIPng for IPv6", RFC 2080, January 1997. [3] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1988. [4] Malkin, G., "RIP Version 2 - Carrying Additional Information", STD 56, RFC 1723, November 1994. [5] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, "Neighbor Discovery for IP version 6", RFC 4861, September 2007. [6] Montenegro, G. and N. Kushalnagar, "Transmission of IPv6 Packets over IEEE 802.15.4 networks", RFC 4944, September 2007. [7] Kushalnagar, N. and G. Montenegro, "6LoWPAN: Overview, Assumptions, Problem Statement and Goals", RFC 4919, August 2007. 10.2. Informative References [8] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6), Specification", RFC 2460, December 1998. [9] IEEE Computer Society, "IEEE Std. 802.15.4-2003", , October 2003. [10] Winter, T. and P. Thubert, "RPL: IPv6 Routing Protocol for low power and lossy Networks", draft-ietf-roll-rpl-05.txt (work in progress), December 2009. [11] Thomson, S., Narten, T., and T. Jinmei, "IPv6 Stateless Autoconfiguration", RFC 4862, September 2007. [12] Park, D., Kim, K., Seo, E., and S. Chakrabarti, "IPv6 over Low Power WPAN Security Analysis", draft-daniel-6lowpan-security-analysis-02.txt (work in progress), January 2007. Mulligan Expires September 2, 2010 [Page 11] Internet-Draft RIPless Routing Protocol March 2010 Appendix A. Summary of optimizations TBD Author's Address Geoff Mulligan Proto6 2175 Cloverdale Drive Colorado Springs, CO 80920 USA Email: geoff@proto6.com Mulligan Expires September 2, 2010 [Page 12]