ROLL Working Group R. Kelsey Internet-Draft Ember Corporation Intended status: Informational April 23, 2009 Expires: October 25, 2009 LIP: Label Information Protocol draft-kelsey-roll-lip-00 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 October 25, 2009. 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. Kelsey Expires October 25, 2009 [Page 1] Internet-Draft LIP: Label Information Protocol April 2009 Abstract LIP is an extension of MPLS for use in Lossy and Low power Networks (LLN). Use of MPLS allows rapid response to local topology changes within an LLN, while still using full IP routing both within the LLN and for packets that cross into other domains. LIP has optional RIP commands for discovering and maintaining label switched tree routes. To support local route repair, labeled packets include a path metric used to detect loops in label-switched paths. Labeled messages may optionally include a source route or route record at the label level in order to allow their use without losing the advantages of label switching. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Acronyms and Abbreviations . . . . . . . . . . . . . . . . 4 2. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Local Label Map . . . . . . . . . . . . . . . . . . . . . 4 2.2. Root Label Map . . . . . . . . . . . . . . . . . . . . . . 4 2.3. Path Label Map . . . . . . . . . . . . . . . . . . . . . . 5 3. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 5 3.1. LIP Label Stack Entry . . . . . . . . . . . . . . . . . . 5 3.2. Label Map Request . . . . . . . . . . . . . . . . . . . . 6 3.3. Label Map Response . . . . . . . . . . . . . . . . . . . . 7 4. Detailed Operation . . . . . . . . . . . . . . . . . . . . . . 7 4.1. Label Switching . . . . . . . . . . . . . . . . . . . . . 7 4.1.1. Labels and Label Assignment . . . . . . . . . . . . . 7 4.1.2. Labeled Packets . . . . . . . . . . . . . . . . . . . 8 4.1.3. TTL Processing . . . . . . . . . . . . . . . . . . . . 8 4.1.4. Forwarding . . . . . . . . . . . . . . . . . . . . . . 8 4.1.5. Route Record Processing . . . . . . . . . . . . . . . 9 4.2. Tree Creation and Maintenance . . . . . . . . . . . . . . 9 4.2.1. Label Map Requests . . . . . . . . . . . . . . . . . . 9 4.2.2. Label Map Responses . . . . . . . . . . . . . . . . . 10 5. Configuration Parameters . . . . . . . . . . . . . . . . . . . 10 6. Applicability Statement . . . . . . . . . . . . . . . . . . . 11 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 10.1. Normative References . . . . . . . . . . . . . . . . . . . 12 10.2. Informative References . . . . . . . . . . . . . . . . . . 12 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12 Kelsey Expires October 25, 2009 [Page 2] Internet-Draft LIP: Label Information Protocol April 2009 1. Introduction LIP is an extension of Multiprotocol Label Switching (MPLS) for use in Lossy and Low power Networks (LLN). The primary motivation for LIP is to enable quick, localized route changes in response to short term changes in the network topology. Local repairs to label switched paths can be made without invoking or affecting the full IP routing protocol. A secondary advantage, in networks where the L2 MTU is less than the L3 MTU, as in 6LoWPAN networks [RFC4944], is that the use of MPLS allows message fragments to traverse multiple hops within the LLN without the need to be reassembled and refragmented at each hop. The main extension to MPLS is the addition of optional source route and route record data to labeled packets. LLNs frequently make use of source routes and route records. Having them available in labeled packets allows their use without losing the advantages of using label switching. LIP includes optional methods for discovering and maintaining trees of label switched paths in LLNs. The trees thus created route messages upwards to the root; there is no provision for downward tree routing. Tree discovery and maintenance is based on the Route Information Protocol (RIP) augmented by including loop detection information in data packets. The ROLL protocols survey [I-D.ietf-roll-protocols-survey] specifically allows per-node routing state to scale as O(D) where D is the number of 'unique destinations'. In order to comply with this, the 'unique destinations' should correspond exactly to the roots of trees. In summary, LIP can route packets based on either an included source route or by using next hop information stored in a Label Map. There are three methods for installing Label Map entries: o Out-of-scope Label distribution protocol; labels may be assigned to either nodes or flows o Tree discovery o A source-routed message may optionally add its route to the Label Maps of the forwarding nodes. LIP is intended to be compatible with centralized routing as used in HYDRO [I-D.tavakoli-hydro]. Alternatively, it could be extended to a full routing solution by having Access Routers distribute portions of their routing tables to other routes in the domain, using Trickle or something similar. This would allow a Node to determine the best Access Point for use in routing to a particular destination by adding Kelsey Expires October 25, 2009 [Page 3] Internet-Draft LIP: Label Information Protocol April 2009 its LIP cost to an Access Point to that Access Point's cost to the destination. 1.1. Requirements Language 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 RFC 2119 [RFC2119]. 1.2. Terminology root label a label that has been assigned to the root of a routing tree local label a label assigned to a neighboring node 1.3. Acronyms and Abbreviations 2. Data Structures 2.1. Local Label Map Each Node MUST maintain a Local Label Map, whose entries contain the following fields: o Label: a label that has been assigned to a neighboring node. o Neighbor: the neighboring node to which it has been assigned. o Link Cost: L2 link cost to the neighbor. The Local Label Map is a cache of information obtained from L2 message exchange or other L2 mechanisms. 2.2. Root Label Map Each Node MAY maintain a Root Label Map, whose entries contain the following fields: o Label: a label that has been assigned to a root node. o Next Hop: the node to be used as a next hop when forwarding packets with this label. o Path Cost: expected cost to the destination associated with this label. Kelsey Expires October 25, 2009 [Page 4] Internet-Draft LIP: Label Information Protocol April 2009 o Maximum Path Cost: the maximum allowed cost for routes back to the root. The Root Label Map is a cache of information obtained from Label Map Responses sent by neighboring nodes. All nodes in a network that uses LIP's path creation and maintenance feature MUST maintain a Root Label Map. 2.3. Path Label Map Each Node MAY maintain a Path Label Map, whose entries contain the following fields: o Label: a label assigned to a node or a flow. o Next Hop: the node to be used as a next hop when forwarding packets with this label. The Path Label Map is a cache of information obtained from Path Creation Source Routes or from some other Label distribution protocol. 3. Message Formats The LIP headers extend the normal MPLS Label Stack Encoding RFC 3032 [RFC3032] by adding one or more headers at the top of the stack. If more than one LIP header is present, any Label Map Requests must come first, followed by any Label Map Responses, followed by at most one LIP Label Stack Entry. Label Map Requests and Responses are removed by the receiving device; they MUST NOT be forwarded. The LIP headers appear after the data link layer headers and before any network layer headers. 3.1. LIP Label Stack Entry +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Rte| Length | Path Cost | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route Label[0] | Route Label[1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Label |1|1|1|1|S| COS | TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: LIP Label Stack Entry Kelsey Expires October 25, 2009 [Page 5] Internet-Draft LIP: Label Information Protocol April 2009 Rte Type of included route +-----+---------------------------+ | Rte | Meaning | +-----+---------------------------+ | 00 | No included route | | 01 | Route Record | | 10 | Source Route | | 11 | Path Install Source Route | +-----+---------------------------+ Length Length of included route or, if there is no route, a command +---------+--------------------+ | Command | Meaning | +---------+--------------------+ | 000000 | Unicast | | 000001 | Label Map Request | | 00001x | Label Map Response | | ... | Reserved | +---------+--------------------+ Path Cost Expected maximum path cost Route Label[i] Source route or route record Destination Label The packet's destination S Bottom of stack COS Class Of Service TTL Time to live The last 32 bits constitute a standard MPLS Label Stack Entry. The four one bits prevent a Label of 0 from appearing as a reserved MPLS label value. 3.2. Label Map Request +-+-+-+-+-+-+-+-+ |0|0|0|0|0|0|0|1| +-+-+-+-+-+-+-+-+ Figure 2: LIP Label Map Request Kelsey Expires October 25, 2009 [Page 6] Internet-Draft LIP: Label Information Protocol April 2009 3.3. Label Map Response +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|0|0|0|0|0|1|C|S|E| Count | Label[0] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Path Cost[0] | Maximum Cost[0] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | Figure 3: LIP Label Map Response C Contiguous, set if the Labels form an ordered, contiguous set of Root Labels from the sender's Root Label Map S Start, set if C is set and the Labels include the minimum Label from the sender's Root Label Map E End, set if C is set and the Labels include the maximum Label from the sender's Root Label Map Count The number of Root Label Map entries included Label Label value Path Cost The sender's Path Cost for this Label. A Path Cost of FFFFFFF indicates that the sender does not have a Root Label Map entry for the Label. Maximum Cost The maximum path cost for this label The C, S, and E flags allow the receiver to determine that it has received a complete copy of the sender's Root Label Map, possibly spread across several packets. 4. Detailed Operation 4.1. Label Switching 4.1.1. Labels and Label Assignment Although the label field in the label stack is 20 bits in length, LIP labels are limited 16 bits in length in order to reduce the size and simplify the processing of source routes and route records. A Node becomes a root by including its own Label includes the Label Kelsey Expires October 25, 2009 [Page 7] Internet-Draft LIP: Label Information Protocol April 2009 in Label Map Responses. In this case the Path Cost for the Label MUST be zero. The Maximum Cost may be any value. Every node in the domain MUST be assigned a label. In order to avoid ambiguity, Root Labels SHOULD be uniquely assigned within a domain. In very large domains a Root Label MAY be assigned to multiple roots if the maximum costs associated with the Labels prevent any node from being in or adjacent to two distinct trees using the same Root Label Neighbor Labels MUST be assigned such that no node has two neighbors with the same Label. These requirements imply that Neighbor Labels MAY be assigned using an L2 mechanism and Root Labels MUST be assigned using an L3 mechanism. 4.1.2. Labeled Packets A labeled packet contains a label stack consisting of one or more label stack entries. A LIP labeled packet is a labeled packet where the topmost label stack entry has the additional LIP fields. Only the topmost label stack entry may contain the additional LIP fields; additional label stack entries MUST NOT be added on top of a LIP label stack entry. 4.1.3. TTL Processing The use of LIP labeling does not alter the number of hops a packet is allowed to traverse. When adding a LIP label entry to an unlabeled packet, the TTL field of the LIP stack entry MUST be set to the value of the packet's IP Hop Limit field. The "incoming TTL" of a received LIP labeled packet is defined to be the value of the TTL field of the LIP label entry. The "outgoing TTL" of a labeled packet is defined to be zero if the incoming TTL is one or less, and one less than the incoming TTL otherwise. If the outgoing TTL is zero, then the LIP labeled packet MUST NOT be forwarded. When a LIP label is popped, and the resulting label stack is empty, then the value of the packet's IP Hop Limit field MUST BE replaced with the outgoing TTL value. 4.1.4. Forwarding If the label in a received LIP labeled packet matches the label assigned to the receiving node, the LIP label stack entry is removed and the packet is processed as if it had been received without the LIP label stack entry. Kelsey Expires October 25, 2009 [Page 8] Internet-Draft LIP: Label Information Protocol April 2009 If the LIP label stack entry contains a source route, the packet is forwarded to the topmost label in the source route. If the topmost label has been assigned to a neighbor the label is removed from the source route, the Path Cost field is set to zero, and the packet is forwarded to that neighbor. If the topmost label is not in the Local Label Map, the packet is forwarded to the topmost label in the source route as if it were the destination label of the packet (loose source routing). Finally, if the source route is a path install source route, the destination Label is added to the Path Label Map with the next hop obtained from the source route. If there is no entry in any of the Label Maps matching the destination label the packet MUST NOT be forwarded. If the source of the packet can be determined, an ICMP message MAY be sent to the source of a discarded packet. If more than one Label Map contains the destination Label, the Root and Local Label Maps take precedence over the Path Label Map. If the Root and Local Label Maps both contain the destionation Label, the entry with the lower cost takes precedence. When forwarding a packet using a Root Label Map entry, if the packet's Path Cost is greater than the Path Cost obtained from the Root Label Map, then the Path Cost in the packet is set to the value obtained from the Root Label Map and the packet is forwarded to the Next Hop listed in the Root Label Map. If a packet's Path Cost is less than or equal to the Path Cost obtained from the Root Label Map a potential loop has been detected. The action taken in that case is beyond the scope of this document. 4.1.5. Route Record Processing If an incoming LIP labeled packet contains a route record, the receiver MAY preserve the recorded route for future use. When forwarding a LIP labeled packet that contains a route record, the forwarding node first adds its own label to the front of the route record. The forwarding node MAY examine the route record in order to detect path loops, which it MAY then remove before forwarding the packet. Any additional action taken when a loop is detected is beyond the scope of this document. 4.2. Tree Creation and Maintenance 4.2.1. Label Map Requests A node may at any time send a Label Map Request to one or more neighbors. In particular, a node that has rebooted may send requests Kelsey Expires October 25, 2009 [Page 9] Internet-Draft LIP: Label Information Protocol April 2009 to its neighbors in order to initialize its own Root Label Map. 4.2.2. Label Map Responses A Label Map Response may be sent in response to a Label Map Request or at the option of the sending node. When sending a Label Map Response, the Path Cost included for a Label is the Path Cost in the Root Label Map plus any forwarding cost that will incurred by the sender. If that total cost is equal to or greater than the Maximum Path Cost for that Label, the Label MUST NOT be included in a Label Map Response. Upon receipt of a Label Map Response, the receiver SHOULD update its Root Label Map using the supplied information. If the sender's cost to a Label is FFFFFFFF or if the Label is not present in a Contiguous Label Map Response that would otherwise have included it, and the sender is the Next Hop for that Label, then the Label SHALL be removed from the Label Map. The receiver's potential Path Cost for a Label in a Label Map Response is the receiver's L2 cost to the sender plus the sender's Path Cost as found in the Label Map Response. If the receiver has no Root Label Map entry for the Label it SHOULD add an entry, with the sender as the Next Hop. If the receiver has a Root Label Map entry for the Label with a Path Cost greater than the potential Path Cost plus a fixed hysteresis value, it SHOULD update the entry using the potential Path Cost and using the sender as the Next Hop. Whenever a Label's Path Cost is updated using information from a Label Map Response, the Label's Maximum Path Cost SHALL be set to the Maximum Path Cost from the same Response. 5. Configuration Parameters Actually using RIP in a network requires that the devices in the network agree on a number of parameters and procudures, including: o The size of the various label maps. o How labels are assigned. o Which devices, if any, are the roots of trees. o When and how label map entries are timed out or replaced. Kelsey Expires October 25, 2009 [Page 10] Internet-Draft LIP: Label Information Protocol April 2009 o The cost metrics for links and forwarding. o The policy and timing constraints for sending unsolicited Label Map Responses. 6. Applicability Statement Although not a complete routing solution, LIP is compatible with the ROLL routing requirements as detailed in the ROLL protocols survey [I-D.ietf-roll-protocols-survey]. This section assumes that the sending of Label Map Requests and Responses are controlled using Trickle or some similar mechanism, the details of which are outside the scope of this document. Routing State: The routing state is the Label Maps, which need only to be large enough to hold the Root Labels and some fixed number of neighbors. In dense regions the Local Label Map may not be large enough to store the labels of all actual neighbors. This introduces a trade off between routing state size and routing efficiency. Correct operation only requires that the network remain connected when only considering neighbors listed in Local Label Maps. Further increasing the size of the Local Label Map may shorten routes. The method for determining which neighbors should be included in the Local Label Map is beyond the scope of this document. Loss Response: Because the Root Label Map contains only the Next Hop and the Path Cost, changes made in response to topology changes need only be propogated as far as they have a significant effect on Path Cost. A change with only local effects on Path Cost requires only local distribution. Control Cost: There is no requirement that Label Map Requests and Responses be sent except in response to data message failures, and even then they can be limited to the vicinity of any topology changes. For efficient operation, it is probably desirable to send unsolicited Label Map Responses at a slow rate in order to reduce the latency added by on-demand path rediscovery. Link and Node Cost: Path cost calculations include both link and node costs. 7. Security Considerations Kelsey Expires October 25, 2009 [Page 11] Internet-Draft LIP: Label Information Protocol April 2009 8. IANA Considerations This document includes no request to IANA. 9. Acknowledgements In addition to the usual suspects, RIP, MPLS, and so forth, LIP was inspired by the work on the Collection Tree Protocol. 10. References 10.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 10.2. Informative References [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-06 (work in progress), February 2009. [I-D.tavakoli-hydro] Tavakoli, A., Dawson-Haggerty, S., Hui, J., and D. Culler, "HYDRO: A Hybrid Routing Protocol for Lossy and Low Power Networks", draft-tavakoli-hydro-01 (work in progress), March 2009. [RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y., Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack Encoding", RFC 3032, January 2001. [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, "Transmission of IPv6 Packets over IEEE 802.15.4 Networks", RFC 4944, September 2007. Kelsey Expires October 25, 2009 [Page 12] Internet-Draft LIP: Label Information Protocol April 2009 Author's Address Richard Kelsey Ember Corporation Boston, MA USA Phone: +1 617 951 1225 Email: kelsey@ember.com Kelsey Expires October 25, 2009 [Page 13]