Field of the Invention

The present invention concerns a routing mechanism, particularly, but not exclusively, for the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) within the context of the Internet of Things (loT). More particularly, the invention concerns a leaf-based downward routing mechanism.

Background of the Invention

Low-Power and Lossy Networks (LLNs) are a class of network in which both the routers and their interconnects are constrained. LLN routers typically operate with constraints on processing power, memory, and energy (e.g. battery or solar power). Their interconnects are characterized by high loss rates, low data rates, and instability. LLNs are typically comprised of anything from a few dozen to thousands of routers. Supported traffic flows include point-to-point (between devices inside the LLN), point-to-multipoint (from a central control point to a subset of devices inside the LLN), and multipoint-to-point (from devices inside the LLN towards a central control point). The IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) provides a mechanism whereby multipoint-to-point traffic from devices inside the LLN towards a central control point as well as point-to-multipoint traffic from the central control point to the devices inside the LLN are supported. Support for point- to-point traffic is also available.

LLNs typically are made up of many embedded devices with limited power, memory, and processing resources. Devices may be interconnected by a variety of types of links, such as IEEE 802.15.4, Bluetooth, Low Power WiFi, wired or other low power PLC (Powerline Communication) links.

In LLNs, three traffic patterns have been envisaged by the research community, namely: MultiPoint-to-Point (MP2P), the Point-to-Multipoint (P2MP) and the Point-to- Point (P2P) traffic patterns. In several LLNs applications, the three communication patterns usually coexist under the same network topology which dictates the need for bidirectional routing. To fulfil this requirement, bidirectional routing capabilities have been provided by standard RPL routing protocol for Upward routing in the direction of the root (usually for data collection) and for the Downward routing in the direction of the associated nodes.

To facilitate the MP2P communication pattern (Upward routing), a physical network is organized into one or more non-overlapping Destination Oriented Directed Acyclic Graphs (DODAGs), where those nodes bridging the topology with other IPv6 domains act as the DAG roots, referred to as LLN Border Routers (LBRs). In the DODAG topology each node should set up its default route by selecting one of its neighbours to act as its preferred parent (next hop) towards the DODAG root (LBR).

In order to facilitate the P2MP and P2P communication patterns, the Downward routes need to be created. This process is achieved by means of a control message referred to as the Destination Advertisement Object (DAO). Each node that is willing to advertise itself as a destination (i.e. to be reachable from the DODAG root point of view), and that has already joined the DODAG, unicasts a DAO to its preferred parent advertising its destination prefix. The processing of the received DAO by the parent depends on the current Mode of Operation (MOP) supported by RPL nodes. RPL provides two MOPs or mechanisms for establishing the Downward routes, namely: storing (table-driven) and non-storing (source-routing). In the storing mode, when a parent receives a DAO from one of its children, the parent performs the following primary steps:

a) It stores the announced prefix locally in its routing table along with the DAO sender address as the next hop to reach the announced destination prefix.

b) It forwards the received DAO, in turn, to its own preferred parent ensuring the propagation of the advertised destination upward through the DODAG until it reaches the DODAG root.

Each RPL router running the storing mode must maintain a routing entry for each destination in its own sub-DODAG. This poses a major challenge to memory- constrained LLNs as a router may easily run out of memory, rendering it unable to accommodate new entries in its routing table. The incapacity of a router to add new routes will render certain destinations in its sub-DODAG unreachable from the root point of view. This in turn will affect negatively the application reliability, as the root would drop all the packets intended for destinations that are unreachable from its perspective.

Prior patent publications related to boosting the efficiency of the storing mode in RPL include the following:

US2012/0307652-A1 discloses A DODAG root node that monitors Internet Protocol (IP) overhead (e.g., route table sizes) within a directed acyclic graph (DAG) in a computer network. If it is determined that the IP overhead is above a configured threshold then, in response, a trigger is initiated to have devices within the DAG label-switch downward traffic directed away from the root node within the DAG.

KR101208400-B1 discloses a mixed mode routing node in an RPL routing protocol that mixes the storing (table-driven) and non-storing modes (source-routing) of RPL.

US2014/0029445-A1 discloses a mechanism to cache source routes by the intermediate nodes based on received data packet headers so they can be used later to forward packets that do not indicate the next hop, based on the cached entry. This is related to the non-storing mode of RPL and uses caching principles to cache source routes for later use.

US2014/0204759-A1 is concerned with load balancing the traffic in RPL network based on the ratio of the workload.

Other published work regarding the storing mode in RPL tackles the issue using different policies.

Summary of the Invention

The present invention provides a“Leaf-Based” mechanism useful for establishing the Downward routes in LLNs that seeks to provide a novel, scalable and efficient routing solution for LLNs, which are the backbone of the Internet of Things (loT). In this mechanism, a router needs only to maintain the routing state of its sub-network’s leaf nodes in its memory, rather than the whole group of nodes as is the case in the current standardized protocol. This approach allows a reduction in the number of routing entries that each router needs to maintain, so as to improve network scalability, especially in long "chain-like" topologies, such as traffic lights along a street. For example, in a chain-like topology each router needs only to maintain one routing entry regardless of the number of nodes in the network. This represents a significant improvement over the current table-driven mechanism used by the standard protocol in which a router needs to maintain n routing entries where n is the number of nodes in its sub-Network.

Numerous applications may benefit from the invention, including, but not limited to sensing data applications, smart cities, monitoring, etc. In such applications the invention allows a large number of sensors to be deployed while significantly reducing the possibility that some of the deployed sensors may run out of memory. On the one hand, this will enhance the reliability of the application by providing the sensors with communication capabilities even under scarce memory resources. On the other hand, it will cut the cost of manufacturing sensors directed toward LLN applications as the size of memory needed to run the protocol would be much less than the memory size needed by currently standardized protocols.

In accordance with the present invention, the forwarding of a data packet to its intended destination is not only based on its own address, but also on the address of another node in its sub-DODAG. In the context of conventional Downward routing in LLN, a data packet from the DODAG root to a destination within the DODAG would carry the sender source address (DODAG root address) and the receiver destination address for correctly delivering the packet to the intended destination. This requires each intermediate router to maintain a routing entry for each destination reachable through that intermediate router. In accordance with the present invention, a data packet needs to carry a“Branch Address” in addition to the source and destination addresses in order to forward the packet correctly, however each intermediate router only needs to store a destination address and a corresponding nexthop address for each leaf node in its sub-DODAG.

In accordance with a first aspect, the invention provides a network comprising a root node device and a plurality of non-root node devices, each device having an address. The plurality of non-root node devices includes at least one intermediate node device and at least one leaf node device, each leaf node device defining a network branch. Each non-root node device is a child of one parent device and each intermediate node device being the parent of at least one child device. The root node device stores routing information that includes the address of each non-root node device and, for each non-root device, a first nexthop address, being the address of a child device of the root node device in the direction of that non-root node device, and that enables the root node device to identify, for each intermediate node device, a branch address, being the address of a leaf node device that is reachable via that intermediate node device. Each intermediate node device stores a routing table that includes an entry for each leaf node device that is reachable via that intermediate node device, each entry comprising the branch address of the respective leaf node device and a second nexthop address, being the address of a child device of the intermediate node device in the direction of that branch address. The root node device is configured to add, to a packet having the address of one of the non-root devices as its destination address, the branch address of a leaf node that is reachable via the destination address. Each intermediate node device is configured to receive packets from its parent device and, if the intermediate node receiving the packet is not the destination of the packet, to read the branch address added to the packet by the root node device, and to forward the packet to the second nexthop address associated with the branch address in its routing table.

In some embodiments, the routing information stored by the root node device comprises a child-parent relationship table having an entry for each non-root node device. Each entry comprises a first destination address, being the address of the non-root node device with which the entry is associated, a first parent address, being the address of the parent device of the non-root node device with which entry is associated, and the first nexthop address for the non- root node device with which the entry is associated. The root node device is configured to search the child-parent relationship table to identify, as leaf node devices, non-root node devices that are not the parents of any other non-root node devices, and to identify, as the branch address for each intermediate node device, a particular leaf node device that is reachable via that intermediate node device. In some embodiments, the routing information stored by the root node device comprises a routing table having an entry for each non-root node device, each entry comprising a first destination address, being the address of the non-root node device with which entry is associated, a first branch address, being the address of a leaf-node that is reachable via the destination address, the first nexthop address for the non-root node device with which the entry is associated.

In these embodiments the routing table may derived from the child-parent relationship table discussed above.

The network may be a Low-Power and Lossy Network, LLN.

Another aspect of the invention provides a method of routing a packet, in the foregoing network, downwards from the root node device to one of the non-root node devices. The method comprises adding, by the root node device, to a packet, a destination address, being the address of the non-root node device to which the packet is to be routed, if the packet does not already include the destination address. The method further comprises identifying, by the root node device, from the routing information, the branch address of a leaf node that is reachable via the destination address, adding, to the packet, by the root node device, the first branch address, and forwarding, by the root node device, the packet to the first nexthop address associated with the destination address of the packet in the routing information.

The method may further comprise receiving, by the non-root node device at the first nexthop address, the packet and, if the first nexthop address is not the destination address of the packet, forwarding, by the non-root node device at the first nexthop address, the packet to the second nexthop address associated with the first branch address of the packet in the routing table of the non-root node device at the first next-hop address.

The method may further comprise receiving, by the non-root node device at the second next-hop address, the packet and, if the second next-hop address is not the destination address of the packet, forwarding, by the non-root node device at the second next-hop address, the packet to the second next-hop associated with the first branch address of the packet in the routing table of the non-root node device at the second next-hop address.

Another aspect of the invention provides a method of updating the routing information of the root node device of the foregoing network when a non-root node device is added to the network. The method comprises receiving, by the root node device from a first child device of the root node device, a control message including the address of the non-root node device added to the network, the address of a chosen parent device of the non-root node device added to the network, and an indication of whether or not the non-root node device added to the network is a leaf node device. The method further comprises storing, by the root node device the address of the non-root node device being added to the network in association with the address of the chosen parent node of that non-root node device identified in the control message and a first next-hop address, being the address of the first root child device from which the control message was received by the root node device.

Another aspect of the invention provides a method of updating the routing table of an intermediate node device of the foregoing network when a non-root node device is added to the network. The method comprises receiving, by the intermediate node device from a first child device of the intermediate node device, a control message including the address of the non-root node device added to the network, the address of a chosen parent device of the non-root node device added to the network, and an indication of whether or not the non- root node device added to the network is a leaf node device. If the control message indicates that the non-root node device added to the network is a leaf node device, the method further comprises storing, by the intermediate node device in its routing table, a new entry for the non-root node device added to the network, the new entry comprising the address of the non-root node device added to the network and a second nexthop address, being the address of the first child device of the intermediate node device from which the control message was received by the intermediate node device, and removing, by the intermediate node device from its routing table, any existing entry associated with the parent device identified in the control message. If the control message indicates that the non- root node device added to the network is a non-leaf node device, the method further comprises leaving the routing table of the intermediate node device unchanged, and forwarding, by the intermediate node device to its own parent device, the received control message.

Other aspects of the invention provide a network device configured to operate as a root node device in the foregoing network, a network device configured to operate as an intermediate node device in the foregoing network and a network device configured to operate as a leaf node device in the foregoing network.

Any of the foregoing aspects of the invention may be implemented using the IPv6 Routing Protocol for Low-Power and Lossy Networks, RPL. Branch addresses may be carried in the Hop-by-Hop RPL Option of IPv6 packets.

Brief Description of the Drawings

Embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

Fig.1 is a diagram illustrating a first example of a network topology;

Fig. 2 is a diagram illustrating a second example of a network topology;

Fig. 3. illustrates the DAO Format in the storing mode of the conventional RPL protocol;

Fig. 4. illustrates the DAO adapted for the purposes of the present invention; Fig. 5. illustrates a standard IPv6 header including a Destination Address;

Fig. 6. illustrates the RPL Hop-by-Hop Option (a) before and (b) after modification for the purposes of the present invention.

Description of Preferred Embodiments

Fig. 1 illustrates an example of a network DODAG (as discussed above) that includes a root node device LBR (as discussed above) and non-root node devices A- M, each of the node devices having a network address. Node devices are referred to hereinafter simply as nodes, for convenience. The DODAG of Fig. 1 includes sub- DODAGS (as discussed above); e.g. nodes C, F, G, J and K constitute a sub- DODAG.

Each non-root node A-M is a child of one parent node; e.g. node A is a child of root node LBR, node H is the child of node D, etc. The non-root nodes include

intermediate nodes A-E, F, G and I, each of which is the parent of at least one child device; e.g. node A is the parent of nodes C and D, node G is the parent of node K, etc. The non-root nodes further include leaf nodes J, K, L and M. A leaf node has no child nodes; i.e. it is not the parent of any other node. Each leaf node J, K, L and M thus defines a network branch that terminates at the leaf node.

The direction of travel of network traffic from the root node LBR towards any non-root node is referred to as“downwards”, while the direction of travel of network traffic from any non-root node towards the root node LBR is referred to as“upwards”. All network traffic entering and leaving the network is routed via the root node LBR, which thus acts as a router for all traffic between the non-root nodes A-M and network addresses external to the network. The intermediate nodes A-E, F, G and I act as routers for traffic to and from nodes in their respective network branches.

Each node stores routing information as required to enable the routing of network traffic. Intermediate nodes are thus required to route packets upwards in the direction of the root node and downwards in the direction of leaf nodes, and may also be referred to as intermediate routers or non-root routers, as described elsewhere in the present description.

The network of Fig. 1 is merely a simple example of a network DODAG topology for the purposes of describing the invention. The individual node devices may be any of a variety of wired and/or wireless, fixed and/or mobile network devices capable of communicating with other network devices in a manner that will be well understood by persons skilled in the art. Such devices will typically include a processor, memory and network interface and other hardware dependent on the function of the device, as will also be well understood by persons skilled in the art, who will be able to implement the present invention on the basis of the information provided herein. As will be described in more detail below, the present invention concerns a routing mechanism that improves upon the standard RPL storing mode by reducing the number of routing entries that need to be maintained by non-root nodes. In the mechanism described herein, a non-root node needs only to maintain the routing state of the leaf children in its sub-DODAG rather than its whole set of children, in order to fulfil the requirements of downward routing. For example, node A of Fig. 1 needs only to maintain the routing state of leaf nodes H, J and K, rather than all of nodes C, D, F, G, H, J and K.

This is based on the fact that a packet destined to any node should pass by its parent node first. Thus, if the root node LBR has a packet destined to a particular node (e.g. node C), it may destine the packet to both the destination address C and to a leaf node (in this example, either J or K) that is reachable via C. Then, an intermediate node (e.g. node A) would be able to forward that packet based on the leaf node address if it already has a routing entry for that leaf node. When the packet arrives at the intended destination (C), it will consume the message based on the first attached address, which is its own address, and stop forwarding that packet further down the DODAG. In other words, there is no need for an intermediate node to maintain a routing entry for any downward node that has at least one child. It is only necessary for the intermediate node to maintain a routing entry for any leaf node that is reachable via that intermediate node. Each such routing entry comprises the leaf node address and the address of the nexthop in the direction of the leaf node. For example, the routing information stored by node A would comprise the addresses (J, C), (K, C) and (H, D).

This is very useful in networks having large number of intermediate nodes compared to the number of leaf nodes, as in chain-like topologies. For instance, all the intermediate nodes in a chain-like topology network would need only to maintain one routing entry, i.e. the address of the last node in the chain, regardless of number of nodes in the network. To enable this mechanism for intermediate nodes, the DODAG root (LBR) must maintain information that matches each intermediate node to at least one leaf node that is reachable via that intermediate node, and this information should be attached to each packet destined to that intermediate node. This is detailed in the following sections. A. Leaf-based routing

In this section, the mechanism for downward routing in RPL according to the invention is presented highlighting the differences between this new mechanism and the conventional storing mode of RPL. This mechanism requires several changes to both the control-plane and the data-plane, as will now be described.

A.1 Control Plane

A.1.1 Table Routing Structure

In the known storing mode of RPL, each node acting as a router should store a routing entry for each destination in its sub-DODAG. Hence, a node should store in its routing table the destination along with its next hop in the form of destination-next hop relationships. For example, for the topology shown in Figure 1 , the conventional RPL storing mode would construct routing tables as depicted in Table 1 :

Table 1.

From Table 1 , it is clear that each intermediate node (non-root router) needs to store one routing entry per destination in its sub-DODAG. For example, node A needs to store seven routing entries, one for each of the nodes (C, D, F, G, H, J, K) located in its sub-DODAG. Each entry in all of the routing tables consists of a destination address and a nexthop address in the direction of the destination.

The present inventors have recognised that, in a DODAG topology, if a node X has learnt a path to destination Y, then the node X is able to communicate with any ancestor for the destination, Y, providing that X knows that Y is located on that ancestor sub-DODAG. Thus, if the DODAG root LBR in Fig. 1 has learnt a path, for example, to the destination J, and has also learnt that the nodes A, C and F are ancestors for the destination J, then the DODAG root can communicate and deliver messages to those ancestors with the guidance of the address of the node J. Hence, it is enough for the intermediate nodes between J and the DODAG root LBR (i.e. nodes A, C and F), to maintain one routing entry which is the address of the leaf node J.

Then, in order to enable downward routing of a packet to one of these nodes, the packet needs to include two addresses. The first address is the real destination address and the second address is the address of a leaf node in the sub-DODAG that includes the real destination address, referred to herein as the“branch address”; i.e. the second address is the address of a leaf node that is reachable via the real destination address (of course, the real destination address may be the leaf node itself). Assuming that the packet received by the root node LBR already includes the real destination address, root node LBR needs to attach the leaf node address to the packet, based on DODAG information acquired and stored by root node LBR for the DODAG. If necessary, the real destination address can be added to the packet by the root node LBR also (e.g. if for any reason the real destination address needs to be determined by the root node rather than being included in the packet received by the root node).

The leaf node address (branch address) will be used by the intermediate nodes to forward the packet as if it is destined for that leaf node, while the first address will be inspected by each intermediate node to check whether that intermediate node is the real destination, in which case the packet is consumed by that node. For the topology shown in Fig. 1 , in one embodiment of the invention the mechanism may construct routing tables as depicted in Table 2. Table 2.

From Table 2, it can be observed that the routing table for root node LBR includes an entry for each non-route node (destination) in the DODAG, each entry consisting of the destination address, a corresponding branch (leaf node) address and the nexthop address in the direction of the branch address. For example, the root node routing table records that node F has a branch address of J and that node A is the nexthop in the direction of J. The branch address for a particular node may be any branch address that is reachable via that node. Node C, for example, may have a branch address of either K (as shown in the table) or J, whereas node D may only have a branch address H. The root node routing table of Table 2 thus differs from the conventional root node routing table of Table 1 in that each entry includes a branch address in addition to the destination and nexthop addresses.

The routing table of each intermediate node includes an entry for each leaf node (branch address) that is reachable via that intermediate node, each entry consisting of the branch address and the nexthop in the direction of the branch address; i.e. each intermediate node needs to store routing entries in the form of destination- nexthop relations only for the leaf nodes in its sub-DODAG, in comparison with the conventional intermediate node routing tables of Table 1 , which need to store destination-nexthop routing entries for all nodes nodes in its sub-DODAG.

The routing information stored by the intermediate nodes does not provide enough information about the network topology in their respective sub-DODAGs to enable them to route packets to non-leaf nodes based only on a destination address. The root node stores additional routing information that it attaches to packets to instruct intermediate nodes along the path to the destination how to forward a packet destined to a non-leaf node. In the embodiment represented by Table 2, this additional information is stored in the root node routing table in the form of the destination-branch-nexthop relationships. The branch entry in this representation refers to a node in the destination sub-DODAG which has no children at the time of adding that entry. Thus, the root node stores for each destination the three fields shown in Table 2 and discussed above: the destination address, the last advertised leaf node address in that destination sub-DODAG (branch address; i.e. a leaf node that is reachable via the destination) and the nexthop to that leaf node. Here, for example, the routing entry (F, J, A) in the LBR routing table represents the destination F with a Branch Address of J and next hop of A. The routing entries in the intermediate nodes each represent a destination and the next hop to that destination, as in the conventional RPL storing mode, but only include entries for leaf nodes in their sub-DODAGS. Compared to the conventional RPL storing mode, this mechanism significantly reduces the number of routing entries needed to be stored at the intermediate nodes, as is clear from Table 1 and Table 2. For example, while node A would need to store seven routing entries in the conventional RPL storing mode, it only needs to store three routing entries in the present mode.

Thus, if the LBR has a packet that needs to be sent to the node F, for example, it should attach to the packet, firstly, the real destination address, which is the address of node F itself (if the packet does not already include the destination address) and secondly, the address of node J which is the leaf node on the sub-DODAG of node F. The intermediate nodes between the root node LBR and the leaf node J need only to know how the packet should be forwarded to J by maintaining the entry associated with it in their routing tables as depicted in Table 2. Thus, the nodes A and C will forward the packet as if it is destined to J based on the branch address. When the packet reaches its real destination F, which can be recognized from the real destination address, the packet will be forwarded to the node F upper network layers.

The extent to which the number of routing entries stored by intermediate nodes can be reduced using the present mechanism depends largely on the network topology and also the number of non-root nodes compared to number of leaf nodes. The greater the number of non-root nodes compared to the number of leaf nodes, the less the number of routing entries needed to be maintained using the mechanism. For instance, Fig. 2 illustrates a simple“chain” topology having a root node LBR, thirteen intermediate nodes a-m and a single leaf node, n. Compared to the conventional RPL storing mode, the maximum number of entries that need to be maintained at any intermediate node using the present mechanism is only one entry, as depicted in Table 3:

Table 3.

By comparison, using the conventional RPL storing mode as shown in Table 4 below, node a would need to store thirteen entries, node b twelve entries, etc. Table 4.

This reduction in the number of routing table entries that need to be stored by intermediate nodes enables wide deployments of large-scale networks with "chain like" topologies that contain paths of any conceivable length, such as traffic lights along a street. Even for more complex topologies, the present mechanism may still offer a significant improvement compared to the standard RPL approach as shown previously. The higher the ratio of intermediate nodes to leaf nodes, the greater the benefit provided by the present invention.

It will be understood that, for the purposes of the present invention, the root node needs to be able to attach to a packet the address of a leaf node (branch address) that is reachable via the real destination address. In the embodiment described above, the root node maintains a routing table that explicitly defines a branch address for each destination address, along with the nexthop address in the direction of the branch address. However, it is not necessary for the root node to store branch addresses in this way. In other embodiments, the root node may store only sufficient information for it to be able to derive or calculate a branch address when needed for a particular destination address.

For example, and as described further below, the root node may receive information when a new non-root node is added to the network, in the form of a control message (DAO) that includes the address of the new non-root node device added to the network and the address of a chosen parent device of the new non- root node. Thus, for each non-root node, the root node will know the address of the parent of that non-root node and the address of the node from which its control message was received, which is the nexthop in the direction of that non-root node. For example, for node G in Fig. 1 , the root node will know that the parent of G is C, that G is a child of C, and the nexthop in the direction of G is A. The root node may search the child-parent information it has to identify leaf nodes, i.e. nodes that are not the parents of any other nodes, and to identify a particular leaf node that is reachable via a particular intermediate node. In this example, root node LBR can identify that node G is the parent of node K and that node K is not the parent of any other node. Accordingly, for a packet destined for node G, root node LBR can attach the address of node K as the branch address to enable node A to forward the packet to node C, on the basis of its routing table entry (K, C), and node C to forward the packet to node G, on the basis of its routing table entry (K, G).

Thus, the root node can determine branch addresses on the fly, on the basis of child- parent relationships, or can store the branch addresses explicitly as described above. It will be understood that the branch addresses in the root node routing table of Table 2 can be derived in the same manner that they are determined on the fly as described above.

The routing mechanism described herein may be implemented in a new network protocol, or by adaptation of an existing protocol, or within the constraints of an existing protocol. The following describes example implementations within the constraints of the existing IPv6 RPL standard. A.1.2. The RPL DAO Format

As mentioned previously, each node wishing to advertise itself as a destination should transmit a control message, i.e. a Destination Advertisement Object (DAO), to its preferred parent towards the DODAG root. This DAO carries the necessary information on how a specific destination can be reached. The format of the DAO Base Object including the Target Option as it has been specified by the existing RPL standard is depicted in Fig. 3.

In the conventional RPL storing mode, the RPL Target Option is used by the DAO initiator to advertise its destination IPv6 address in the field of the Target Prefix.

Thus, when a node running the conventional storing mode receives a DAO, it adds the target prefix to its routing table along with the IPv6 address of the DAO sender as the next hop to the advertised target (destination).

In the conventional non-storing mode of RPL, the DAO must also contain information regarding the advertised target’s parent IPv6 address in addition to the destination address. This information is carried in the RPL Transit Option in the Parent Address field (not shown in Fig. 3) and is intended to help the DODAG root in constructing the source routing headers based on“per hop” routing segments received from all the nodes in the network.

In the present scheme, the root node needs to learn the last advertised leaf node in that destination sub-DODAG (the branch address). This information can be calculated based on child-parent relationship segments received from all network nodes, as described above. Thus, like the conventional RPL non-storing mode, the Parent Address field within the Transit Option must be presented in the DAOs transmitted using the present mechanism. A suitable DAO format for the present mechanism is depicted in Fig. 4.

The Parent Address field serves two purposes in the present mechanism:.

First, it enables the DODAG root node to calculate the branch addresses as discussed above. Second, it enables the non-root nodes to remove any existing routing entries for this parent that have been previously stored in the non-route node router tables. For example, if node c in Figure 2 has advertised its destination before node d, then node a and b would have an existing routing entry for c as it was the last advertised leaf node. When node d subsequently advertises its destination up to the DODAG root, setting c as its parent address, nodes a and b should remove c from their routing tables as it is no longer a leaf node. This is done by inspecting their routing tables for an entry similar to the parent of the newly advertised destination and then removing that entry.

Removing a parent from an intermediate node’s routing table by inspecting the destination’s parent address in the Transit Information Option deals with the issue of a previously unknown parent that has been added to the routing table; i.e. that has been added before it becomes a parent. However, there is also a possibility of receiving a DAO from a parent node; i.e. a node sends a DAO after it receives a DAO from one of its children. In the current format, the routers do not have the capacity to distinguish between a leaf node and non-leaf (parent) advertised in DAO messages. As a result, a non-root router will always add the destination advertised in the DAO message whether it is a leaf node or a parent and it should wait until it receives a DAO from one of the parent’s children in order to remove that parent. That is, if a non-leaf node (say a node X) sends a DAO to its parent (say a node Y) , that parent (Y) will consider the sending non-leaf node (X) as it is a leaf node because it has no mechanism to differentiate between a leaf and a non-leaf node. Thus, Y will add X’s destination prefix to its routing table. Adding X’s prefix to the routing table of Y is incorrect as X is a non-leaf node. This incorrect information at Y can be removed later when Y receives a DAO from one of the children of X (say node M). At this point, Y will realize that X is a non-leaf node as X is the parent of a node called M. However, this is inefficient as takes some time for the wrong entry to be removed (i.e. Until Y receives a DAO from M).

To resolve this issue and to allow for a non-root node to prevent adding an already known parent to its routing table, the present mechanism may use one of the bits in the Flags field within the DAO base object to represent the current status of the DAO initiator. This bit may be referred to as the Leaf Flag (abbreviated as L flag) as depicted also in Fig 4. When this flag is set to zero, the DAO initiator is considered a leaf node and a non-root node must add the entry advertised in the DAO to its routing table. On the other hand, when the L flag is set to one, the DAO initiator is already a parent and the DAO should be forwarded without adding that entry to the non-root node routing table.

A.1.3. Control Plane Operations for Building the Routing Tables

In the present mechanism, each node wishing to participate in downward routing should unicast a DAO to its preferred parent advertising its own IP address in addition to its parent’s IP address. It should also set its L flag to zero or one based on whether it is currently a leaf or non-leaf node.

A non-root node receiving that DAO should perform the following operations:

If the L flag bit in the DAO is set to zero, indicating that the destination advertised in the DAO is a leaf node, the non-root node should add a routing entry for the advertised destination to its routing table along with the DAO sender (i.e. the node from which the DAO is received, rather than the new node that is advertising itself) as the nexthop towards the advertised destination. If the L flag bit in the DAO is set to one, indicating that the destination advertised in the DAO is a non-leaf node, the routing entry should not be added.

Remove any existing routing entry associated with the parent address advertised in the DAO Transit Information Option (i.e. if the parent address was previously a leaf node).

Set its own L flag bit to the value of one, if its own L flag bit is currently set to zero (i.e. if the non-root node receiving the DAO is the parent advertised in the DAO).

Forward the DAO further up towards the DODAG root node; i.e. to its own parent node.

The root node receiving that DAO should perform the following operations, in the first embodiment described above, using the root node routing table of Table 2:

The DODAG root node must add a routing entry for the destination advertised in the DAO if it does not already have an entry for that destination, or update an existing entry for the destination; e.g. if the leaf node status of the destination has changed. The root node routing entry should include three fields, as described above: the destination address, the branch address, and the nexthop. The branch address for each destination can be calculated based on child-parent relationship segments received from all network nodes, as described above.

In the alternative embodiment where branch addresses are determined on the fly, the root node adds an entry to a child-parent relationship table, in which each entry comprises a destination address, being the address of the non-root node device with which the entry is associated, a parent address, being the address of a parent node of that non-root node device and a next hop address, being the address of a child device of the root node device in the direction of that non-root node device, normally the device from which the root node receives the DAO.

A.2. Data Plane

A.2.1. RPL Hop-by-Hop Option

In an IPv6 network, a node wishing to unicast an IPv6 packet to a specific destination must attach that destination address in the Destination Address field in the IPv6 fixed header, which is depicted in Fig. 5.

In the present scheme, the packet should carry two addresses in its header - the destination address and the branch address, as previously described - so that a non root node can correctly forward that packet. A standard IPv6 fixed header contains only the information that is necessary for a conventional IPv6 router. All additional information, which is not always used, is carried in the form of Extension Headers placed between the Fixed Header and the Upper Layer Header. Several extension headers have previously been defined, such as the Hop-by-Hop Options header and the Routing header. Among all defined extension headers, only the Hop-by-Hop header is to be processed by each router along a packet's delivery path. All other headers are allowed to be processed only at the packet's destination so as to increase the speed of header processing and also to enhance the forwarding process performance. This allows the option to carry the branch address of the present invention within the existing Hop-by-Hop Option, as this address needs to be examined by every router along the path to the destination. In this context, the Internet Engineering Task Force (IETF) has defined a new Hop-by-Hop option called RPL Option for the purpose of data-path verification. In the data-path verification, some routing information is carried within the RPL option to help in detecting routing inconsistencies such as loops. The format of the Hop-by-Hop Option header including the RPL Option is depicted in Fig. 6a. Also, the IPv6 standard dictates that each Option header may appear at most once in the IPv6 packet:“Each extension header should occur at most once, except for the Destination Options”. Taking this into consideration, the present invention may be implemented under IPv6 by carrying the Branch IPv6 address within the already specified Hop-by-Hop RPL Option, by defining a new field, which may be referred to as the Branch Address, in order to carry the Branch IPv6 address. This is depicted in Fig. 6b.

An intermediate node on the path to the destination should then inspect the Branch Address and also the Destination Address presented in the IPv6 fixed header to correctly forward the packet. The operation of how these two addresses should be used is explained in the Data-Plane Operations section below.

A.2.2. Data Plane Operations

A.2.2.1. Root Node Operations:

In the conventional RPL storing mode, when the root node sends a packet to a destination in its sub-DODAG, it attaches the destination IP address in the

Destination address field of the IPv6 header. Then, it forwards that packet to the next hop associated with that destination. A receiving node on the path to the destination simply inspects its routing table for an entry associated with that destination to determine the next downward hop. This process is repeated by all the intermediate nodes along the path to the destination until the packet finally reaches the intended destination.

In the present mechanism, inspecting the destination address by an intermediate node will not be enough to correctly forward the packet to the next hop. This is because only the root node stores the routing information of the entire topology while a non-root node stores only the routing information of the leaf nodes in its sub- DODAG. Thus, in addition to the destination Address, the root node also needs to attach the branch address associated with that destination in the branch address field within the RPL Hop-by-Hop option, as described above, and then forward the packet to the nexthop.

A.2.2.2. Non-root Node Operations:

As explained earlier, the branch address represents the last leaf address advertised in that destination sub-DODAG. Once the packet is received by an intermediate node, that node performs the following:

First, it inspects the destination address within the IPv6 fixed header. If that destination address is the node’s own address, it consumes the packet. If the destination address is not the node’s own address and is found in the node’s routing table, the packet is forwarded to the destination address (in which case the destination address itself is a leaf node of the intermediate node’s sub-DODAG). If the destination address is not the node’s own address and is not found in the node’s routing table, instead of dropping the packet, the node assumes that the packet is to be forwarded towards a leaf node and proceeds to the next step.

Second, if the destination address is not the node’s own address and is not found in the node’s routing table, the router inspects the Branch Address within the RPL Hob-by-Hop option, looks up the branch address in its routing table and forwards the packet to the nexthop address associated with that branch address.

These steps are repeated by each non-root node on the path to the destination until the packet reaches its intended destination.

As described herein in its various embodiments and examples, the present invention provides a scalable and energy efficient routing solution suitable for Low-Power and Lossy Networks (LLNs), which are the backbone of the Internet of Things (loT). Applications that can benefit from the invention include but are not limited to sensing data applications, smart cities, monitoring, etc.

The invention may be implemented as a downward routing mechanism within any routing protocol, although particular embodiments described herein are tailored to work within the constraints of the standard RPL, for establishing the Downward routes in LLNs. Improvements and modifications may be incorporated without departing from the scope of the invention.