Dynamic traffic shaping based on path self-interference

In one embodiment, a method is disclosed in which a device in a network receives self-interference information from one or more nodes in the network. A degree of self-interference along a communication path in the network is determined based on the received self-interference information. A packet to be sent along the communication path is also identified and traffic shaping is performed on the communication path based on the degree of self-interference along the path.

TECHNICAL FIELD

The present disclosure relates generally to computer networks, and, more particularly, to mechanisms for shaping network traffic flow based on self-interference experienced along a communication path.

BACKGROUND

Low power and Lossy Networks (LLNs), e.g., sensor networks, have a myriad of applications, such as Smart Grid and Smart Cities. Various challenges are presented with LLNs, such as lossy links, low bandwidth, battery operation, low memory and/or processing capability of a device, etc. Changing environmental conditions may also affect device communications. For example, physical obstructions (e.g., changes in the foliage density of nearby trees, the opening and closing of doors, etc.), changes in interference (e.g., from other wireless networks or devices), propagation characteristics of the media (e.g., temperature or humidity changes, etc.), and the like also present unique challenges to LLNs.

In some cases, an LLN device may communicate simultaneously using multiple link technologies, such as radio frequency (RF), power line communication (PLC), and/or cellular. Link technologies common to LLN deployments also typically communicate on shared media. For example, LLN devices may communicate on different electrical phases of a tri-phase electrical system using PLC transceivers. For these reasons, different pairs of devices communicating within close physical proximity may interfere with each other, resulting in a type of interference called self-interference. Unlike interference due to external sources (e.g., environmental conditions, etc.), self-interference is a form of localized interference that can be attributed to the network itself. Particularly in the context of LLNs, it is challenging and difficult to devise network solutions that account for the effects of self-interference between devices.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

According to one or more embodiments of the disclosure, a method is disclosed in which a device in a network receives self-interference information from one or more nodes in the network. A degree of self-interference along a communication path in the network is determined based on the received self-interference information. A packet to be sent along the communication path is also identified and traffic shaping is performed on the communication path based on the degree of self-interference along the path.

In further embodiments, a method is disclosed in which the performance of a communication link between network nodes is monitored. The presence of self-interference associated with the communication link is also identified and reported to a traffic shaping device.

DESCRIPTION

FIG. 1is a schematic block diagram of an example computer network100illustratively comprising nodes/devices200(e.g., labeled as shown, “root,” “11,” “12,” . . . “45,” and described inFIG. 2below) interconnected by various methods of communication. For instance, the links105may be wired links or shared media (e.g., wireless links, PLC links, etc.) where certain nodes200, such as, e.g., routers, sensors, computers, etc., may be in communication with other nodes200, e.g., based on distance, signal strength, current operational status, location, etc. Those skilled in the art will understand that any number of nodes, devices, links, etc. may be used in the computer network, and that the view shown herein is for simplicity. Also, those skilled in the art will further understand that while the network is shown in a certain orientation, particularly with a “root” node, the network100is merely an example illustration that is not meant to limit the disclosure.

Data packets140(e.g., traffic and/or messages sent between the devices/nodes) may be exchanged among the nodes/devices of the computer network100using predefined network communication protocols such as certain known wired protocols, wireless protocols (e.g., IEEE Std. 802.15.4, Wi-Fi, Bluetooth®, etc.), PLC protocols, or other shared-media protocols where appropriate. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.

FIG. 2is a schematic block diagram of an example node/device200that may be used with one or more embodiments described herein, e.g., as any of the nodes shown inFIG. 1above. The device may comprise one or more network interfaces210(e.g., wired, wireless, PLC, etc.), at least one processor220, and a memory240interconnected by a system bus250, as well as a power supply260(e.g., battery, plug-in, etc.).

The network interface(s)210include the mechanical, electrical, and signaling circuitry for communicating data over links105coupled to the network100. The network interfaces may be configured to transmit and/or receive data using a variety of different communication protocols. Note, further, that the nodes may have two different types of network connections210, e.g., wireless and wired/physical connections, and that the view herein is merely for illustration. In other words, device200may communicate with another network device using two or more different communication technologies/physical layers (e.g., wireless, PLC-based, etc.). Also, while the network interface210is shown separately from power supply260, for PLC the network interface210may communicate through the power supply260, or may be an integral component of the power supply. In some specific configurations, the PLC signal may be coupled to the power line feeding into the power supply.

The memory240comprises a plurality of storage locations that are addressable by the processor220and the network interfaces210for storing software programs and data structures associated with the embodiments described herein. Note that certain devices may have limited memory or no memory (e.g., no memory for storage other than for programs/processes operating on the device and associated caches). The processor220may comprise hardware elements or hardware logic adapted to execute the software programs and manipulate the data structures245. An operating system242, portions of which are typically resident in memory240and executed by the processor, functionally organizes the device by, inter alia, invoking operations in support of software processes and/or services executing on the device. These software processes and/or services may comprise routing process/services244and an interference analyzer248, as described herein. Note that while processes244,248are shown in centralized memory240, alternative embodiments provide for the processes to be specifically operated within the network interfaces210.

Notably, mesh networks have become increasingly popular and practical in recent years. In particular, shared-media mesh networks, such as wireless or PLC networks, etc., are often on what is referred to as Low-Power and Lossy Networks (LLNs), which are a class of network in which both the routers and their interconnect are constrained: LLN routers typically operate with constraints, e.g., processing power, memory, and/or energy (battery), and their interconnects are characterized by, illustratively, high loss rates, low data rates, and/or instability. LLNs are comprised of anything from a few dozen and up to thousands or even millions of LLN routers, and support point-to-point traffic (between devices inside the LLN), point-to-multipoint traffic (from a central control point such at the root node to a subset of devices inside the LLN) and multipoint-to-point traffic (from devices inside the LLN towards a central control point).

An example protocol specified in an Internet Engineering Task Force (IETF) Proposed Standard, Request for Comment (RFC) 6550, entitled “RPL: IPv6 Routing Protocol for Low Power and Lossy Networks” by Winter, et al. (March 2012), provides a mechanism that supports multipoint-to-point (MP2P) traffic from devices inside the LLN towards a central control point (e.g., LLN Border Routers (LBRs) or “root nodes/devices” generally), as well as point-to-multipoint (P2MP) traffic from the central control point to the devices inside the LLN (and also point-to-point, or “P2P” traffic). RPL (pronounced “ripple”) may generally be described as a distance vector routing protocol that builds a Directed Acyclic Graph (DAG) for use in routing traffic/packets140, in addition to defining a set of features to bound the control traffic, support repair, etc. Notably, as may be appreciated by those skilled in the art, RPL also supports the concept of Multi-Topology-Routing (MTR), whereby multiple DAGs can be built to carry traffic according to individual requirements.

Also, a directed acyclic graph (DAG) is a directed graph having the property that all edges are oriented in such a way that no cycles (loops) are supposed to exist. All edges are included in paths oriented toward and terminating at one or more root nodes (e.g., “clusterheads” or “sinks”), often to interconnect the devices of the DAG with a larger infrastructure, such as the Internet, a wide area network, or other domain. In addition, a Destination Oriented DAG (DODAG) is a DAG rooted at a single destination, i.e., at a single DAG root with no outgoing edges. A “parent” of a particular node within a DAG is an immediate successor of the particular node on a path towards the DAG root, such that the parent has a lower “rank” than the particular node itself, where the rank of a node identifies the node's position with respect to a DAG root (e.g., the farther away a node is from a root, the higher is the rank of that node). Note also that a tree is a kind of DAG, where each device/node in the DAG generally has one parent or one preferred parent. DAGs may generally be built (e.g., by DAG process246and/or routing process244) based on an Objective Function (OF). The role of the Objective Function is generally to specify rules on how to build the DAG (e.g. number of parents, backup parents, etc.).

Another distinguishing characteristic of LLNs and other forms of shared media networks is the increased possibility of self-interference conditions within the network. In general, self-interference occurs when communications between different pairs of network nodes/devices within close physical proximity interfere with one another. One example of a self-interference condition is illustrated inFIG. 3. As shown, assume that nodes/devices12,22,32, and42communicate wirelessly using a half-duplex setup. In such a setup, a device can only receive or transmit at any given time, regardless of which wireless channels are used. For example, assume that wireless communications to and from node32are half-duplexed and that node32is currently transmitting data to node42. In such a case, data cannot be received by node32from node22at the same time, thereby causing a self-interference condition.

FIG. 4illustrates another example of a self-interference condition along a communication path. As shown, assume that each of nodes12,22,32, and42independently determine their own channel hopping schedules. Such a schedule may indicate the channel on which a node may receive data at a particular point in time. To facilitate communications between the nodes, each node may share its channel hopping schedule with its neighboring devices. Thus, node12may not have knowledge of the channel usage of nodes32,42and vice versa. Now, assume that node32is communicating data to node42using a particular channel and that node32has a transmission range402. In such a case, a self-interference condition may be present if node12attempts to communicate with node22using the same channel, since node22is also within transmission range402of node32.

Self-interference conditions may also be present in other forms of shared media, such as PLC links. For example, as shown inFIG. 5, nodes32,33,42, and43may communicate on a given electrical phase present in the power line system. In particular, node32may communicate with node42on first electrical phase (phase A) and node33may communicate with node43on a second electrical phase (phase B) on adjacent communication links. In some cases, crosstalk502may present, meaning that the data transmitted on phase A makes its way onto phase B or vice-versa. The degree of crosstalk between electrical phases may vary in both the time and space domains. Thus, a self-interference condition due to crosstalk502may exist if node33attempts to transmit data to node43when node32is transmitting data to node42.

In some cases, a given PLC device may use different electrical phases to transmit data to a neighboring device simultaneously. As shown in the example ofFIG. 6, assume that nodes32,42are both connected to electrical phases A and B. Thus, node32may use both phases A and B, to communicate data to node42. However, a self-interference condition may result if node32attempts to use both phases at the same time and crosstalk602exists between the two phases.

As noted above, self-interference conditions present unique challenges in shared media networks, such as LLNs. In particular, the presence of self-interference is often unpredictable in such networks and may vary with time.

Dynamic Traffic Shaping Based on Path Self-Interference

The techniques herein provide for the dynamic adjustment of traffic shaping policies used within a network, such as an LLN, based on the degree of self-interference that occurs along communication paths within the network. In one aspect, data regarding the degree of self-interference along a path and between adjacent paths may be reported to a traffic shaping device, such as a path computation engine (PCE), DODAG Root, etc. In another aspect, the traffic shaping device may dynamically adjust traffic shaping policies used in the network for delivering packets along a given communication path. In another aspect, traffic shaping may also be applied to adjacent communication paths that are used simultaneously, based on the reported self-interference. In a further aspect, packet scheduling may be adjusted based on the self-interference. In yet another aspect, feedback may be provided to the traffic shaping device regarding self-interference and used as part of a closed-loop control mechanism for the applied traffic shaping.

In general, traffic shaping is a technique that delays some or all datagrams to match a desired traffic profile. In other words, traffic shaping is a form of rate limiting and is especially important in networks that have limited resources (e.g., LLNs). A Traffic shaper may be parameterized by a desired traffic profile and is often implemented using leaky bucket or token bucket algorithms. A number of input/output traffic shaping techniques have been developed in the past for many types of link layers (e.g., ATM, FR, IP, etc.).

Specifically, according to one or more embodiments of the disclosure as described in detail below, a method is disclosed in which a device in a network receives self-interference information from one or more nodes in the network. A degree of self-interference along a communication path in the network is determined based on the received self-interference information. A packet to be sent along the communication path is also identified and traffic shaping is performed on the communication path based on the degree of self-interference along the path.

Illustratively, the techniques described herein may be performed by hardware, software, and/or firmware, such as in accordance with the processes244,248, which may include computer executable instructions executed by the processor220(or independent processor of interfaces210) to perform functions relating to the techniques described herein. For example, the techniques herein may be treated as extensions to conventional protocols, such as the various PLC protocols or wireless communication protocols, and as such, may be processed by similar components understood in the art that execute those protocols, accordingly.

Operationally, techniques are disclosed whereby traffic shaping polices may be adjusted and enforced based on the degree of self-interference that occurs along paths used to deliver packets in a network. In particular, the degree of self-interference along a path may be quantified, reported to a traffic shaping device (e.g., a PCE, DODAG Root, etc.), and used to adjust network traffic shaping policies based on the degree of self-interference.

FIG. 7illustrates an example format for a message700that may be used for discovery and route dissemination when building a DAG, e.g., as a DAO message. Message700illustratively comprises a header702with one or more fields704that identify the type of message (e.g., a RPL control message), and a specific code indicating the specific type of message (e.g., as a DAO message). Within the body/payload706of the message may be a plurality of fields used to relay the pertinent information. In particular, the fields may comprise various flags/bits708, a sequence number710, an instance ID712, a DODAG ID714, destination prefixes716, and/or a transit information field718, among others (e.g., DAO_Sequence used for ACKs, etc.). One or more additional sub-option fields722may also be used to supply additional or custom information within message700.

In various embodiments, message700may include self-interference information720that includes information regarding self-interference associated with a given communication path. In one embodiment, self-interference information720may simply indicate whether a communication link between a node and its DODAG parent exhibits self-interference (e.g., a node/device may indicate whether the device has detected self-interference). For example, in the case of crosstalk, a device may be configured to determine that crosstalk exists between electrical phases and include an indication of such in interference information720. In another embodiment, interference information720may be further augmented with the link or set of links that exhibit crosstalk effects (e.g., a node/device may identify both the presence of self-interference as well as determining where the interference is occurring). In further embodiments, interference information720may include information that may be used by a central network device (e.g., root, NMS, etc.) to detect the presence of self-interference. As would be appreciated, crosstalk introduces dependencies between different physical communication media. Thus, message700may be sent to a traffic shaping device, such as a path computation engine (PCE), DODAG Root, or other network node, and used to determine self-interference along a communication path in the network.

In some cases, interference information720may include link information regarding which links/physical layers a particular device is using or is capable of using. For example, interference information720may indicate whether the device is able to use one or more PLC links or a wireless connection with another device. Interference information720may further include information regarding the links, such as the hopping schedule of a wireless link, signal strength information, information regarding dropped packets, etc. In some cases, a device may not be able to identify self-interference on its own. In such cases, a central network device (e.g., traffic shaper, PCE, etc.) may use the link information from different devices along a path to identify the presence of self-interference. In cases in which a node/device detects self-interference on its own, the central device may still use interference information720to verify the determination. In further embodiments, the central device may use the link information to identify points along the path that may exhibit self-interference, regardless of whether self-interference has actually occurred (e.g., devices in close proximity using the same communication media).

The degree of self-interference may be reported to (e.g., as determined by the node/device and included in interference information720), or otherwise identified by, a traffic shaping device in any number of ways. In other words, the reporting node and/or the central device may determine the degree of self-interference. In one embodiment, the degree of self-interference may correspond to the number of links along a path that experience self-interference with one or more links along the path. In another embodiment, the degree of self-interference may correspond to the maximum number of consecutive links along a communication path that experience self-interference. Such a representation may be useful since the overall throughput along a path is reduced in proportion to the number of consecutive links that experience self-interference. For example, when a path includes two consecutive links that experience self-interference, the overall throughput is reduced by half. Similarly, when a path includes three consecutive links that experience self-interference, the overall throughput is reduced to only one-third. While a path that includes more than three consecutive links that experience self-interference can service one-third the traffic in theory, in practice the throughput is further reduced due to the likelihood that packet drops, random backoffs, etc. will amplify the effects of self-interference. In yet another embodiment, the self-interference may be represented by the distribution of links along the path that experience self-interference. For example, if a path has two sets of links that experience self-interference, the sets are more likely to introduce additional delays in aggregate when they are closer together in the same path. One brute force approach that may also be used is to simply list all links along a path and indicate whether or not they experience self-interference with any neighboring links.

Based on the presence of self-interference along a given communication path in the network, a traffic shaping device may dynamically perform traffic shaping by adjusting a traffic shaping policy. Thus, a PCE, DODAG Root, or other device that acts as a traffic shaper may compute the degree of self-interference for packets along a given communication path and apply traffic shaping techniques to packets that utilize that path. An example of traffic shaping being performed along a path is shown inFIGS. 8A-8B. Assume in the example shown that the DODAG Root device acts as a traffic shaper and is attempting to forward packets along a path802. If any adjacent links105along path802experience self-interference (e.g., the links between nodes12,22and22,32), the Root device may decrease the transmission rate used by one half. In another example, if one of the links105along path802experiences self-interference with two adjacent links (e.g., the link between nodes22,32exhibits self-interference with the links between nodes12,22and nodes32,42), the Root device may decrease the data rate to one third. If there are multiple groups of links that experience self-interference along a path, the traffic rate may be reduced even further.

In some embodiments, the traffic shaper (e.g., the PCE/DODAG Root, etc.) may dynamically adjust the traffic shaper policy when delivering packets along different but adjacent paths. For example, as shown inFIGS. 9A-9B, assume that the Root device is attempting to send data packets via adjacent paths902and904. As noted previously, adjacent communication paths in some shared media networks may experience self-interference due to crosstalk effects (e.g., crosstalk between different electrical phases in a PLC system, etc.). When the Root device uses the adjacent paths902,904to deliver packets at the same time and it is determined that self-interference exists between the two paths, the Root may dynamically adjust the traffic shaper policies for those paths by further reducing the traffic rate. As with the previous example shown inFIGS. 8A-8B, the Root may adjust the traffic rate based on the degree of self-interference between the two adjacent paths, as measured by the number of links that experience self-interference, and/or the proximity of links that experience self-interference. For example, two links that experience self-interference are likely to amplify their effects of adding delay and variance when they are closer together along a path.

A device may perform traffic shaping by adjusting the scheduling of when the data is sent in addition to, or in lieu of, performing traffic shaping by adjusting a data rate for data transmittal. Still referring toFIGS. 9A-9B, assume that the Root device determines that paths902and904exhibit self-interference. In some cases, the Root device may adjust the scheduling of data transmissions by alternating the train of packets in terms of time schedule. For example, the Root device may send n-number of packets along path902, and then send m-number of packets along path904, return to sending packets along path902, etc.

In another embodiment, the traffic shaper functionality may be distributed among nodes in the LLN (i.e., not just on the Root or other supervisory device). A node may indicate to the Root (e.g., in a RPL DAO message or a new control message) that it implements traffic shaper functionality. For example, as shown inFIG. 10, node22may identify itself to the Root device that node22is capable of implementing traffic shaping. The Root could then dynamically enable or disable the traffic shaper functionality on any of the nodes that support such a mechanism.

While some aspects herein attempt to be proactive based on the self-interference reports from the nodes (e.g., as part of RPL DAO messages send at certain times), there may be cases where external conditions (e.g., external interference, etc.) can further amplify the effects of self-interference. Thus, in some cases, a traffic shaper device may also receive feedback from network nodes as part of a closed-loop control mechanism. For example, as shown inFIG. 11, the Root device may receive interference information1105from node12on an ongoing basis as part of a closed-loop mechanism. In response, the Root device may adjust traffic shaper policy1110imposed on node12. In one embodiment, interference information1105may be sent if the degree of self-interference experienced by node12exceeds a threshold level.

FIG. 12illustrates an example simplified procedure for performing traffic shaping in a shared-media communication network based on self-interference, in accordance with one or more embodiments described herein. The procedure1200may start at step1205, and continues to step1210, where, as described in greater detail above, self-interference information is received at a traffic shaping device (e.g., a DODAG Root, PCE, node configured to operate as a traffic shaper, etc.) by one or more network nodes. As detailed above, the self-interference information may be included in a DAO message or any other message passed to the traffic shaping device.

At step1215, a degree of self-interference along a path is determined based on the received interference information. As detailed above, the degree of self-interference along a path may be quantified in any number of ways. For example, the degree of self-interference along a path may be quantified as the total number of links along a path that experience self-interference, the highest number of adjacent links in the path that experience self-interference, a distribution of links in the path that experience self-interference, or the like.

At step1220, one or more packets are identified that are going to be sent along the communication path. As detailed above, for example, a Root device may identify a train of packets that are going to be sent along a particular communication path.

At step1225, traffic shaping is performed on the communication path based on the degree of self-interference along the path. As described in greater detail above, a traffic shaping may be performed by adjusting the data rate used to send the one or more packets from step1220and/or adjusting the scheduling of when the packet(s) are sent. For example, if two adjacent links along a communication path experience self-interference, the traffic shaping device may reduce the data rate used to send the packet(s) by half. Procedure1230then ends at step1230.

FIG. 13illustrates an example simplified procedure for reporting self-interference to a traffic shaping device, according to various embodiments. The procedure1200may start at step1205, and continues to step1210, where, as described in greater detail above, a communication link between a pair of network nodes is monitored. For example, a given node may monitor the performance of data sent to the node from its DODAG parent.

At step1315, the presence of self-interference is identified. As described in detail above, various conditions may result in self-interference on a link. For example, the receiving device may be transmitting at the same time it is to receive a packet (e.g., in a half-duplex system), a given channel is used simultaneously by multiple devices within close proximity, cross-talk effects exists between different electrical phases, etc.

At step1320, the network node/device then reports any identified self-interference to the traffic shaping device. For example, as described in greater detail above, interference information may be included in a DAO message, a message as part of a closed loop mechanism, a control message, or any other form of message. Also as described in greater detail above, the reported self-interference may include information regarding different communication media used by the node (e.g., wireless links, PLC links, etc.). Procedure1300then ends at step1330.

The techniques described herein, therefore, provide for dynamically adjusting the traffic shaping policies based on the degree of self-interference for paths being used in an LLN. The degree of self-interference can vastly change the rate of traffic a path can deliver, where self-interference can reduce traffic rates to one-third or less, and the data rate may be adjusted accordingly. Thus, the techniques herein allow the better utilization of available network resources while avoiding issues caused by congestion (e.g., added latency, higher variance, reduced end-to-end reliability, inaccurate link-quality metrics, etc.).

While there have been shown and described illustrative embodiments that provide for dynamic enabling of routing devices in a shared-media communication network, it is to be understood that various other adaptations and modifications may be made within the spirit and scope of the embodiments herein. In addition, while certain protocols are shown, such as RPL, other suitable protocols may be used, accordingly.