One document matched: draft-kelsey-roll-lip-00.txt
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]
| PAFTECH AB 2003-2026 | 2026-04-21 19:21:34 |