- 6LoWPAN standardizes the adaptations of IPv6 for networks that use IEEE 802.15.4 PHY layer.
- Routing over Low-Power and Lossy Links (RoLL) standardizes a link-independent IPv6 routing protocol for resource constrained devices. It defines the RPL routing protocols, which builds a robust topology over lossy links with minimal state requirements.
RoLL studied the routing requirements for a broad range of applications based on more than a decade of research in WSN, and produced four RFCs describing routing in four environments:
- RFC5548: Routing Requirements for Urban Low-Power and Lossy Networks
- RFC5673: Industrial Routing Requirements in Low-Power and Lossy Networks
- RFC5826: Home Automation Routing Requirements in Low-Power and Lossy Networks
- RFC5867: Building Automation Routing Requirements in Low-Power and Lossy Networks
- LLN devices maintain very little state and are optimized for saving energy,
- the traffic patterns in LLN can be more complex than unicast flows,
- the traffic must be carried over links that can forward only small frames.
These characteristics impose unique requirements that make existing routing protocols unsuitable for LLNs. RPL was defined to address this shortcoming. RPL supports 3 traffic patterns: multipoint-to-point (MP2P), point-to-multipoint (P2MP) and point-to-point (P2P). MP2P is currently the dominant traffic type for LLN applications.
The following mechanisms influence the design of RPL.
- Routing state propagation. Existing routing protocols disseminate state using scoped floods or periodic routing beacons to maintain freshness of routing information. Both approaches are unsuitable for large, low-bandwidth network. RPL uses the Trickle algorithm for scalable state propagation. It is an epidemic protocol that reacts quickly to change in routing state and tapers off as the rate of state change decreases.
- Spatial diversity. LLN is an environment where nodes are likely to fail due to environmental factors and interference might cause a previously good link to become unreliable. Nodes must be able to switch from unavailable / unreliable routes. RPL uses spatial diversity to achieve reliability. A router can maintain multiple potential parents towards a destination instead of just one.
- Expressive link and node metrics. Conventional routing protocols define static link costs, which is used to respond to link breaks. This is unsuitable in LLNs due to significant temporal variations. RPL uses a flexible framework, such as estimated number of transmissions (ETX), to take into consideration dynamic link metrics.
RPL is a IPv6 distance vector routing protocol that builds Destination Oriented Directed Acyclic Graph (DODAG). The root is at the sink to minimize the cost of reaching the sink from any node in the network. The cost is specified by the Objective Function (OF) and is used to minimize a particular metric, e.g., hop count or ETX. RPL was designed to be flexible and it supports a variety of OFs that are capable of building a routing topology according to various link / node metrics and constrains.
The root of the DAG starts sending out DAG Information Option (DIO) messages, containing information about itself (its distance from the backbone network, OF, DAG-ID etc). Any node that is connected to a non-RPL implementing node or a backbone network can act as a root or LLN Border Router (LBR) - this node has a rank of 1.
RPL defines rules for parent selection based on the local quality of the links, the advertised OF, path cost, rank etc. Any node with a lower rank is considered as a candidate parent.
A node that receives a DIO calculates its rank based on the rank in the received DIO and the cost of reaching the sending node from itself. When a node broadcasts its DIO, it includes information about its rank, OF and the DAG it has joined. DIOs propagate down to the most distant nodes from the root and help create a DODAG in the network.
DIOs are transmitted periodically from each node, triggered by a trickle timer, whose duration increases exponentially (doubled each time). The smallest interval between two DIOs is denoted by I_min and the number of times I_min can be doubled before maintaining a constant rate is denoted by I_doubling. Therefore, I_max = I_min * 2I_doubling.
When a node joins the network, it either waits to receive a DIO or it multicasts a solicitation message, called DODAG Information Solicitation (DIS). Other nodes that receive the DIS start sending DIOs so that the newly arrived node can join the DAG.
Nodes also multicast Destination Advertisement Option (DAO) for 1-hop reachability and unicast reachable prefix to their parent in the DAG to advertise their addresses and prefixes. Nodes that receive the DAOs update their routing table. When no entry is available in the routing table, or for traffic to the root, the node forwards the packet up to its most preferred parent.
While sending packets up the DAG, a node must not forward it to a node with a greater rank to prevent a loop in the routing path. If no parent is available, the node can forward the data to a sibling (i.e., a node of the same rank). By doing this, the packet goes from the source up to a common ancestor of the source and destination in the DAG, and then it travels down to the destination.
A node can move closer to the destination (decreases its rank value) without poisoning its own routes because this action cannot lead to a routing loop. This rule allows RPL to provide reliable data collection from a large set of nodes to one destination while optimizing for metrics defined by the OF. RoLL has defined standard metrics for link quality, latency and throughput.
The LBR periodically transmits DIO with a new sequence number (DAGSequenceNumber) in order to recalculate the DAG and repair any broken links. When a node encounters a DIO with a greater sequence number, it restarts the parent selection process as per the updated link cost and confidence about the parents so that for the next iteration, it has a better path to the root. This also helps a node finds a parent in case its parent list is depleted due to unsuccessful probes or low confidence.
RPL specifies local and global repair mechanisms to recompute routes when it detects an inconsistency. Repairs are also carried out due to administrative decisions. A local repair involves detaching a node's sub-DODAG by increasing its rank value. A global repair requires all nodes in a DODAG to recompute their rank values and reconfigure their parent sets.
Solid arrows represent a node's preferred parent, which is determined from the node's neighbours and their rank values. Dashed lines point to other nodes in the parent set.
RPL uses the Destination Advertisement Object (DAO) message to support routing to destinations. It supports cases where nodes do not have enough memory to store routes to all possible destinations. A DAO message contains information about the desired parent set of a destination node, and it is propagated up the DODAG until it reaches the root. The root gathers DAO messages from all nodes and uses them to construct down routes to the destinations. Data to the advertised destinations is forwarded along a DODAG until it reaches the root, which then attaches a source routing header and sends it back down the DAG.
Alternatively, nodes in the DODAG may store next-hops to downstream destinations. At the moment, a mixed-mode operation is not supported. All nodes must either store or not store routes.
Source:
- K.Kalinowska-Górska and F.S. Donado, "Constructing Fair Destination-Oriented Directed Acyclic Graphs for Multipath Routing", Journal of Applied Mathematics Volume 2014, 2014
- J. Go, A. Terzis, S. Dawson-Haggerty, D.E. Culler, J.W. Hui, P. Levis, "Connecting Low-Power and Lossy Networks to the Internet", IEEE Communications Magazine Vol. 49 Issue 4, April 2011
- RFC6550: RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks
No comments:
Post a Comment