TECHNICAL FIELD

[001] The present invention relates to communication networks and, more particularly, to nodes in communication networks.

BACKGROUND

[002] In wireless multi-hop mesh networks, nodes may use multiple network interfaces to communicate with other nodes in the network. In a typical multi-hop wireless network, the network interfaces belong to the same IP subnet, thereby enabling communication between nodes through any of the interfaces. By assigning non-interfering frequencies to individual interfaces of the node, multiple interfaces of the node can be operated simultaneously. However, only by assigning non-interfering frequencies to individual interfaces of the node, the data traffic in the node cannot be uniformly distributed among the multiple interfaces of the node.

[003] Distributed reactive routing algorithms may be used to find a route from the source node to the destination node. The route may pass through interfaces of nodes. A drawback of current reactive routing algorithms is that the data traffic in a node is not distributed uniformly among the multiple interfaces of the node. Thus some interfaces may be over-used while other interfaces would be underutilized. Also, there may be congestion at some interfaces of the node. The problem is encountered when all the interfaces of the node are assigned to the same IP subnet.

[004] Current systems use bond interfaces to uniformly distribute data traffic among the multiple interfaces of the node. Bond interfaces can be used to perform round robin scheduling between multiple interfaces. But, round robin scheduling does not allow simultaneous operation of the interfaces. Broadcast mechanism of bond interfaces supports simultaneous broadcast of data on multiple interfaces. However, the same data is broadcast over all network interfaces and bond interfaces do not support sending different data to different destinations, simultaneously on multiple network interfaces.

SUMMARY

[005] In view of the foregoing, an embodiment herein provides a method for uniform distribution of load among multiple interfaces of a node in a communication network, wherein there are multiple nodes in the communication network. The node maintains a "weight" associated with each of the multiple interfaces of the node and the node calculates a value of "Load" between one of the multiple interfaces of the node and one of the multiple interfaces of a second node, wherein "Load" is calculated using the weight and a LinkMetric. The node calculates a value of PathMetric between one of the multiple interfaces of the node and one of the multiple interfaces of a second node, wherein PathMetric is calculated using the value of Load. A destination node determines the best route between a source node and a destination node using the value of PathMetric. The source node broadcasts a route discovery request packet to other the nodes in the communication network and the destination node replies to the route discovery request packet by sending a route discovery reply packet to the source node. The node decrements the weight associated with the interface by 1 if the route through the interface has expired and the node increments the weight associated with the interface by 1 if the route passes through the interface In other words, on any node, whenever a route using an interface i is inserted, the "weight" associated with that interface i is incremented by 1 and whenever a route using an interface i is deleted, the "weight" associated with the interface i is decremented by 1. The value of "Load" is calculated by multiplying value of the "weight" with value of the LinkMetric and the value of PathMetric is included in the route discovery request packet. The node adds the value of Load to the value of PathMetric. LinkMetric depends on at least one of expected transmission time of the route, expected transmission count of the route, hop count and reliability of the route. The source node communicates with the destination node through the determined route.

[006] Embodiments further disclose a node for uniform distribution of load among multiple interfaces of the node in a communication network, wherein there are multiple nodes in the communication network. The node maintains a weight associated with each of the multiple interfaces of the node and the node calculates a value of Load between one of the multiple interfaces of the node and one of the multiple interfaces of a second the node, wherein Load is calculated using the weight and a LinkMetric. The node calculates a value of PathMetric between one of the multiple interfaces of the node and one of the multiple interfaces of a second node, wherein the PathMetric is calculated using the values of Load. A destination node determines a route from a source node to a destination node using the value of PathMetric. The node decrements the weight associated with the interface by 1 if the route through the interface has expired and increments the weight associated with the interface by 1 if a route passes through the interface. The node includes the value of PathMetric in the route discovery request packet and the node adds the value of Load to the value of PathMetric.

[007] These and other aspects of the embodiments herein will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings.

BRIEF DESCRIPTION OF THE FIGURES

[008] The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which:

[009] FIG. 1 illustrates a block diagram of nodes in a communication network, according to an embodiment herein;

[0010] FIGS. 2a, 2b and 2c are flowcharts depicting a method for uniformly distributing the load across multiple interfaces of a node, according to an embodiment herein;

[0011] FIG. 3 illustrates an example of selecting the optimum route for communication session between the source node and destination node, according to an embodiment herein

DETAILED DESCRIPTION OF EMBODIMENTS

[12] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description.
Descriptions of well-known components and processing techniques are omitted so as to not unnecessarily obscure the embodiments herein. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein may be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.

[13] The embodiments herein disclose a system and method for uniform load distribution across multiple interfaces of a node in a communication network. Referring now to the drawings, and more particularly to FIGS. 1 through 3, where similar reference characters denote corresponding features consistently throughout the figures, there are shown embodiments.

[14] FIG. 1 illustrates a block diagram of nodes in a communication network. In a communication network, a node 101 can act as a starting point of a communication session, as a destination of a communication session, as a connection point between a source and a destination or as a redistribution point in the communication network. The
node 101 in a communication network is an entity that is connected to the network and is capable of sending, receiving and forwarding information over a communications channel. For example, a node 101 in a network may be a modem, hub, bridge, switch or a computer. In a second example, a node 101 may be a telephone exchange or a remote concentrator. The nodes 10 101 may be directly connected to other nodes 101 in the network or a first node 101 may be connected to a second node 101 through a third node 101 in the network. An interface connects one node 101 to another node 101 in the network. Multiple interfaces help in connecting a node 101 to multiple other nodes 101 in the network. For example, interfaces i, j and k' may help connect node A 101 to node B 101, node C 101 and to node F 101 respectively. Communication between two nodes 101 happen through the interfaces. For example, the communication channel between two nodes 101 may be said to be an interface between the two nodes 101.

[15] The load in a node 101 is uniformly distributed across all the 20 interfaces in the node 101. The load is the data traffic being handled by the node 101 during a communication session between two nodes 101. When there is data transfer between nodes 101, the load is distributed uniformly between the multiple interfaces. Also, the data on the multiple interfaces can be transmitted simultaneously and data can be transmitted to multiple destinations simultaneously using the multiple interfaces.

[16] Before a communication session can start between a source node 101 and a destination node 101, a route must be established between the source node 101 and the destination node 101. A route to the destination is determined only when a data packet has to be transmitted to the destination. To establish the route, the source node 101 broadcasts a route discovery request packet in the communication network. This route discovery request packet is typically broadcast in the network. Potentially, several copies of the route discovery request packet reach the destination node 101 traversing different paths in the network.

[0017] A route metric is associated with each node 101 in the network. The route metric of a route indicates the metrics to determine if one route performs better than a second route in the network. For example, the route metric may be the expected transmission time of the links on the route, the expected transmission count of the links on the route, the total hop count, the total delay incurred on the route, or any metric associated with the quality of a network link and the route with the desirable aggregate metric may be considered to be the better route. The route metric between interface 'i' of node 101 'n' and interface 'j' of node 101 'm' is called as LinkMetriC(ij). Each node 101 maintains a weight 'Xi' associated with each interface 'i' of the node 101. When there are no routes passing through interface 'i', the weight, 'Xi' is set equal to 1. When a route discovery reply packet passes through interface 'i' of the node 101, then the weight, 'Xi', is incremented by 1. When a route through interface 'i' expires, then the weight, 'Xi', is decremented by 1. The 'Load' between interface 'i' of a node 101 'n' and interface 'j' of node 101 'm' is calculated as, Load(ij) = LinkMetriC(i, j) * Xi, where 'Xi', is the weight associated with interface 'i'. The values of 'Load' are calculated for all interfaces of each node 101 traversed by the route discovery request packet on the way to the source node 101. For example, if the route discovery request packet passes through interface 'a' of node 101 'n' and interface 'b' of node 101 'm' , before reaching the destination node 101, then the values of 'Load' are calculated for interface 'a' of node 101 'n' and interface 'b' of node 101 'm'. In the example, node 101 'n' and node 101 'm' could be any node 101 in the network and having multiple interfaces. When the route discovery request packet passes through multiple nodes 101, en route to the source node 101, the 'Load' values is calculated each time the route discovery request packet passes through a node 101. All the values of 'Load' are aggregated and included in the route discovery request packet header and denoted as a 'PathMetric' value. As the route discovery request packet passes through a node 101, the node 101 calculates the value of 'Load' and adds the calculated value of 'Load' to the 'PathMetric'. For example, if the route discovery request packet passes through 3 nodes 101 before reaching the destination node 101 and if the values of 'Load' calculated for each individual link through which the route discovery request packet passes is 10, and respectively, then the value of 'PathMetric' after the route
discovery request packet passes from the first node 101 to the second node 101 is 10, the value of'PathMetric' after the route discovery request packet passes from the second node 101 to the third node 101 is 10 + 5 = 15 and the value of 'PathMetric' after the route discovery reply packet passes from the third node to the final node is 15 + 3 = 18. When the destination node 10 101 receives the route discovery request packet, the destination node 101 also obtains the total value of 'PathMetric' from the route discovery request packet. The value of 'PathMetric' is used by the destination node 101 to determine the best possible route from the source node 101 to the destination node 101. For example, the value of'PathMetric' can be used to 15 determine the route in such a way as to obtain uniform distribution of load across all the interfaces of the node 101. The value 'PathMetric' helps ensure that both the link quality and the number of routes passing through an interface are taken into account while selecting routes. Once a route is selected by the destination node 101, the route is tied to the interfaces in the route and the interfaces are not changed during the lifetime of the route. If a route becomes inactive, the inactive route is removed and the weight on the interface is reduced by 1.

[0018] The destination node 101 responds to the route discovery request packet by sending a route discovery reply packet to the source node 101 through the selected route. The route discovery reply packet may pass through other nodes 101 in the network en route to the source node 101. All nodes 101 that receive and forward the route discovery request packet store the route to the source node 101. All nodes 101 that receive the route discovery reply packet learn that they are on the route from the source node 101 to the destination node 101. All nodes 101 that receive and forward the route discovery reply packet store the route to the destination 101. Once the 10 route discovery reply packet reaches the source node 101, the source node 101 learns the route selected by the destination node 101 and the source node can then communicate with the destination node 101 through the selected route.

[0019] For example, if node 101 A is the source node 101 and if node 101 E is the destination node 101, then node 101 A broadcasts a route discovery request packet. The route discovery request packet would be eventually received by all other nodes 101 shown in Fig. L. The route discovery request packet may pass through node 101 F, node 101 B and node 101 C before reaching node 101 E. The possible routes for communication between node 101 A and node 101 E are: node 101 A - node 101 F - node 101 E, node 101 A - node 101 C - node 101 E and node 101 A - node 101 C - node 101 D - node 101 E. If the total value of 'PathMetric' for the three possible routes are: node 101 A - node 101 F - node 101 E = 15, node 101 A - node 101 C - node 101 E = 20 and node 101 A - node 101 C - node 101 D - node 101 E =35. Node 101 E uses the value of 'PathMetric' and selects the route that distributes the load uniformly between interfaces i, j and k. If by choosing the route 'node 101 A - node 101 C - node 101 E' with 'PathMetric' = 20 the load can be distributed uniformly between the interfaces, then node 101 E chooses the route 'node 101 A - node 101 C - node 101 E' to communicate with node 101 E. Depending on which route is chosen, node 101 E unicasts a route discovery reply packet to the source on the chosen path.

[0020] FIGS. 2a, 2b and 2c are flowcharts depicting a method for uniformly distributing the load across multiple interfaces of a node. Before a communication session can start between a source node 101 and a destination node 101, a route must be established between the source node 101 and the destination node 101. A route to the destination is determined before a data packet has to be transmitted to the destination. Each node 101 maintains (201) a weight 'Xi' associated with each interface 'i' of the node 101. If there are no routes passing through interface 'i' of the node 101, the weight, 'Xi' associated with interface 'i' is set equal to 1.

[0021] To establish the route from the source node 101 to the destination node 101, the source node 101 broadcasts (202) a route discovery request packet in the communication network. The route discovery request packet may pass through other nodes 101 in the network en route to the destination node 101. If the route discovery request packet 25 has not reached (203) the destination node 101, then the node 101 that has received the route discovery request packet calculates (206) the values of 'Load' for all interfaces traversed by the route discovery request packet on the way to the destination node 101. The value of 'Load' is calculated each time the route discovery request packet passes through a node 101. The 'PathMetric' is then determined (207) by aggregating the values of 'Load'. As the route discovery request packet passes through a node 101, the node 101 calculates the value of 'Load' and adds the calculated value of 'Load' to the 'PathMetric'. The node 101 includes (208) the value of'PathMetric' in a header in the route discovery request packet, stores (209) the route to the source node 101 and sends (2010) the route discovery request packet towards the destination node 101. Potentially, several copies of the route discovery request packet reach the destination node 101 traversing different paths in the network.

[0022] If the route discovery request packet has reached (203) the destination node 101, then the destination node 101 may wait until other route discovery request packets also reach the destination node 101 by traversing through multiple different routes in the network. If the destination node 101 waits (204) for other route discovery request packets, then the destination node 101 stores (205) the route discovery packets that have been received. If the destination node 101 does not wait any longer (204) for other route discovery request packets, then the destination node 25 101 determines (2011) the optimum route to the source node 101 by using the value of 'PathMetric' in the received route discovery request packets. The destination node 101 responds to the route discovery request packet by sending (2012) a route discovery reply packet to the source node 101 through the selected route.

[0023] If the route request reply packet has not reached (2013) the source node 101, but is received by any other node 101 in the network, the node 101 stores (2015) the route to the destination. If the route discovery reply packet passes through an interface of the node 101, then the weight associated with the interface is incremented (2017) by 1. For example, if the route discovery reply packet passes through interface 'j' of node 101 'n' then the weight, 'Xj' associated with interface 'j' is incremented by 1. The node then sends (2018) the route discovery reply packet towards the source node 101. If the route request reply packet has reached (2013) the source node 101, the source node 101 learns the route to the destination and stores (2014) the route. After determining the best route, the source node 101 can start (2016) a communication session with the destination node 101. After the source node 101 completes communicating with the destination node 101, the node 101 checks to see if the route through an interface has expired. If the route through an interface has expired, then the node 101 decrements the weight associated with the interface by 1. The various actions in method 200 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 2 may be omitted.

[0024] FIG. 3 illustrates an example of selecting the optimum route for communication session between the source node and destination node. Considering a communication network with each node 101 having 2 interfaces namely Intfl and Intf2. Each interface is assigned a different IP address in the same subnet 192.168.1.0/24. Each node 101 also has a routing table wherein information about how to reach the next hop neighbor is maintained. For ex: If we look at Node 101 A's routing table, we see that Node A 101 can reach Intfl on Node B 101 (192.168.1.3) through interface Intfl and the expected time of transmission (ETT) is 2 ms. Since there are two routes using interface Intfl, the "weight" on Intfl is 2. The "Load" value is calculated as ETT * Weight. Now suppose Node 101 A wants to communicate with Node 101 D. Node 101 A broadcasts a route discovery request packet over all of its interfaces. When Node 101 B receives the route discovery request packet. Node 101 B updates the PathMetric in the header to either 4 or 6.' PathMetric' is updated to value 4 if the route discovery request packet was transmitted from Intfl of Node 101 A and received on Intfl of Node 101 B. 'PathMetric' is updated to value 6 if the route discovery request packet was transmitted on Intf2 of Node 101 A and received on Intf2 of Node 101 B. 'PathMetric' is updated based on the value of "Load" in the routing table and indicates how much load the interface is already routing. After updating the value of 'PathMetric', Node lOlB broadcasts the route discovery request packet over both the interfaces. Node 101 D receives this route discovery request packet. Node 101 D waits for some time to receive the route discovery request packets potentially traversing other paths in the network or on other interfaces. In this case, Node 101 D may receive another route discovery request packet from Node 101 C which Node 101 C received from Node 101 A. Node 101 D compares the value of 'PathMetric' in all the route discovery request packet headers, at the end of the waking period. Node 101 D chooses the "best path" as the path with least 'PathMetric'. This is because 'PathMetric' incorporates both Expected Transmission Time on a link and the load on a link. Node 101 D responds with a route discovery reply packet over the interface over which Node 101 D received the best route discovery request packet. Any node 101 that forwards this route discovery reply packet updates the "weight" on the interface through which the route discovery reply packet is passed. The weight is updated by increasing the weight by 1. This is because route discovery reply packets are unicast over the path finally chosen for communication between the source and destination, in this case Node 101 A and Node 101 D. So, all the nodes that forward the route discovery reply path are sure that they are on the path between the source node 101 and the destination node 101.

[0025] 'PathMetric' as defined herein ensures that both the link quality and the number of routes passing through an interface are taken into account while selecting routes. A route once selected, is tied to interfaces in the route and may not be changed during the lifetime of the route. This ensures that no out-of-order packets result because of load balancing ping- pong effect between interfaces is avoided. Also, different data may be sent to different destinations simultaneously on multiple network interfaces. Embodiments disclosed herein can be implemented with any reactive routing methods. For example, the embodiments disclosed may be implemented with Ad hoc On-Demand Distance Vector (AODV) Routing and Hybrid Wireless Mesh Protocol (HWMP). RREQ packets in AODV may be used to carry the values of 'Load'. The RREQ packets may also be broadcast over all the interfaces in the node 101 in a network.

[0026] The embodiments disclosed herein can be implemented through at least one software program running on at least one hardware device and performing network management functions to control the network elements. The network elements shown in Fig. 1 include blocks which can be at least one of a hardware device, or a combination of hardware device and software module.

[0027] The embodiment disclosed herein specifies a system and method for uniform load distribution across multiple interfaces of a node in a communication network. Therefore, it is understood that the scope of the protection is extended to such a program and in addition to a computer 25 readable means having a message therein, such computer readable storage means contain program code means for implementation of one or more
steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The method is implemented in a preferred embodiment through or together with a software program written in e.g. Very high speed integrated circuit Hardware Description Language (VHDL) another coding language, or implemented by one or more VHDL or several software modules being executed on at least one hardware device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof, e.g. one processor and two FPGAs. The device may also include means which could be e.g. hardware means like e.g. an ASIC, or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. The method embodiments described herein could be implemented in pure hardware or partly in hardware and partly in software. Alternatively, the invention may be implemented on different hardware devices, e.g. using a plurality of CPUs.

[0028] The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments herein that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and, therefore, such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Therefore, while the embodiments herein have been described in terms of preferred embodiments, those skilled in the art will recognize that the embodiments herein can be practiced with modification within the spirit and scope of the claims as described herein.

CLAIMS

What is claimed is:

1. A method for uniform distribution of load among multiple interfaces of a node (101) in a communication network, wherein there are multiple said nodes (101) in said communication network, the method comprising steps of:

said node (101) maintaining a weight associated with each of said multiple interfaces of said node (101);

said node (101) calculating a value of Load between one of said multiple interfaces of said node (101) and one of said multiple interfaces of a second said node (101), wherein said Load is calculated using said weight and a LinkMetric;

said node (101) calculating a value of PathMetric between said one of said multiple interfaces of said node (101) and said one of said multiple interfaces of a second said node (101), wherein said PathMetric is calculated using said value of Load; and

a source node or destination node (101) determining a route to a destination node (101) using said value of PathMetric.

2. The method, as claimed in claim 1, wherein said source node (101) broadcasts a route discovery request packet to other said nodes (101) in said communication network.

3. The method, as claimed in claim 1, wherein said destination node (101) replies to said route discovery request packet by sending a route discovery reply packet to said source node (101).

4. The method, as claimed in claim 1, wherein said node (101) decrements said weight associated with said interface by 1 if said route through said interface has expired.

5. The method, as claimed in claim 1, wherein said node (101) increments said weight associated with said interface by 1 if said route passes through said interface.

6. The method, as claimed in claim 1, wherein said value of Load is calculated by multiplying value of said weight with value of said LinkMetric.

7. The method, as claimed in claim 1, wherein said value of PathMetric is included in said route discovery request packet.

8. The method, as claimed in claim 1, wherein said node (101) adds said value of Load to said value of PathMetric.

9. The method, as claimed in claim 1, wherein said LinkMetric depends on at least one of:

expected transmission time of said route;

expected transmission count of said route;

hop count; and reliability of said route.

10. The method, as claimed in claim 1, wherein said source node (101) communicates with said destination node (101) through said determined route.

11. A node (101) for uniform distribution of load among multiple interfaces of said node (101) in a communication network, wherein there are multiple said nodes (101) in said communication network, said node (101) having at least one means adapted for:

said node (101) maintaining a weight associated with each of said multiple interfaces of said node (101);

said node (101) calculating a value of Load between one of said multiple interfaces of said node (101) and one of said multiple interfaces of a second said node (101), wherein said Load is calculated using said weight and a LinkMetric;

said node (101) calculating a value of PathMetric between said one of said multiple interfaces of said node (101) and said one of said multiple interfaces of a second said node (101), wherein said PathMetric is calculated using said value of Load; and

a source node (101) determining a route to a destination node (101) using said value of PathMetric.

12. The node (101), as claimed in claim 11, wherein said node (101) is adapted to decrement said weight associated with said interface by 1 if said route through said interface has expired.

13. The node (101), as claimed in claim 11, wherein said node (101) is adapted to increment said weight associated with said interface by 1 if said route passes through said interface.

14. The node (101), as claimed in claim 11, wherein said node (101) is adapted to include said value of PathMetric in said route discovery request packet.

15. The node (101), as claimed in claim 11, wherein said node (101) is adapted to add said value of Load to said value of PathMetric.