FORM 2
The Patent Act 1970
(39 of 1970)
&
The Patent Rules, 2005

COMPLETE SPECIFICATION
(SEE SECTION 10 AND RULE 13)

TITLE OF THE INVENTION

“Quality of Service based Gateway Node Selection in Wireless Communication Networks”

APPLICANTS:

Name Nationality Address
Alcatel Lucent France 54 rue de la Boétie, 75008 Paris, France

The following specification particularly describes and ascertains the nature of this invention and the manner in which it is to be performed:-

TECHNICAL FIELD
1. The present invention relates to communication networks and, more particularly, to selection of gateway nodes in communication networks.

BACKGROUND
2. Nodes in a communication network are active electronic devices capable of sending, receiving or forwarding information over a communications channel. In multi-hop wireless networks, most nodes may need to communicate with the outside world or with the core of the network through gateway nodes connected to a backhaul. The nodes thus route data packets to destination through nodes that have a backhaul connection. Different nodes have different capabilities in terms of the path metrics on the path to the gateway node. Different gateway nodes in a network have different capabilities and the capabilities may include throughput, delay and jitter along the path to the network core. Current systems sending all the traffic at a particular node through the same gateway node may not utilize the capabilities of the gateway node optimally. If the capability of the gateway node is lesser than the Type of Service (ToS) requirement of the routed data packet, then the ToS requirement of the data packet is not satisfied.

3. In current systems, the nodes in a network compute their bandwidth requirements and convey the determined bandwidth information to other nodes in the network. Based on the received bandwidth information, the nodes determine the bandwidth available to each node. The nodes in a network may also compute the available bandwidth to neighboring nodes in the network. The determined bandwidth information may also be distributed to other nodes in the network.
4. In some current systems, the data queued at the nodes is determined and nodes route data packet through other nodes in such a way as to reduce the latency experienced by the data packet. The latency that a data packet may experience at a node is determined using the information about the data queue at the particular node. Also, the data packets queued at nodes is reduced by routing data packets through nodes having a lesser number of queued data packets. However, other metrics such as jitter and bandwidth offered by a node are not being considered before transmitting a data packet through a node. Also, the ToS requirement of a data packet may not be satisfied by the node selected to route the data packet.

SUMMARY
5. In view of the foregoing, an embodiment herein provides a method for routing data packets by a node in a wireless communication network, the wireless communication network further comprising of a plurality of nodes and a plurality of gateway nodes. The plurality of gateway nodes sends a message to a plurality of nodes in the network, where the message has information about the path metrics of the corresponding gateway node. The node selects an optimum gateway node from the plurality of gateway nodes by referring to the message, when the node has to route the data packets to a destination, where the selection is done based on Type of Service (ToS) requirement of the data packets and ToS that can be supported by the plurality of gateway nodes. The node transmits the data packets through the selected gateway node. The plurality of nodes maintain a list of active gateway nodes from among the plurality of gateway nodes and a list of routes to the plurality of gateway nodes and the path metrics of the routes. The node extracts path metrics and route traversed by the message before reaching the node. The node adds the route traversed by the message to a list of edge disjoint routes to the corresponding gateway node, if the route traversed by the message is edge disjoint from the list of routes to the corresponding gateway node. The node updates the list of routes to the plurality of gateway nodes and the path metrics of the routes using the extracted path metrics and extracted route. The selection of the optimum gateway node is done by comparing the ToS supported by the plurality of gateway nodes and the ToS requirement of data packet to be routed. The ToS that can be supported by the plurality of gateway nodes is determined using the path metrics of the plurality of gateway nodes. The message is updated by the node by adding address of the node to list of routes traversed by the message and by updating the path metrics of the route traversed by the message. The updated message is transmitted by the node to the plurality of nodes in the network.
6. Embodiments further disclose a node for routing data packets in a wireless communication network, the wireless communication network further comprising of a plurality of nodes and a plurality of gateway nodes. The node comprising atleast one means adapted for sending a message by the plurality of gateway nodes to a plurality of nodes in the network, where the message has information about the path metrics of corresponding gateway node. An optimum gateway node is selected from the plurality of gateway nodes by the node, when the node has to route the data packets to a destination, where the selection is done based on Type of Service (ToS) requirement of the data packets and ToS that can be supported by the plurality of gateway nodes. The data packets are transmitted through the selected gateway node by the node. The node is adapted to maintain a list of active gateway nodes from among the plurality of gateway nodes. The node also maintains a list of routes to the plurality of gateway nodes and path metrics of the routes. The node determines the ToS that can be supported by the plurality of gateway nodes using the path metrics of the plurality of gateway nodes. The node updates the message by adding address of the node to list of routes traversed by the message and by updating the path metrics of the route traversed by the message. The updated message is transmitted by the node to the plurality of nodes in the network.
7. Embodiments herein also disclose a wireless communication network comprising of a plurality of nodes and a plurality of gateway nodes. The plurality of gateway nodes sends a message to a plurality of nodes in the network, where the message has information about the path metrics of the corresponding gateway node. The node selects an optimum gateway node from the plurality of gateway nodes by referring to the message, when the node has to route the data packets to a destination, where the selection is done based on Type of Service (ToS) requirement of the data packets and ToS that can be supported by the plurality of gateway nodes. The node transmits the data packets through the selected gateway node. The plurality of nodes also maintain a list of active gateway nodes from among the plurality of gateway nodes and a list of routes to the plurality of gateway nodes and the path metrics of the routes. The node extracts path metrics and route traversed by the message before reaching the node. The node adds the route traversed by the message to a list of edge disjoint routes to the corresponding gateway node, if the route traversed by the message is edge disjoint from the list of routes to the corresponding gateway node. The node updates the list of routes to the plurality of gateway nodes and the path metrics of the routes using the extracted path metrics and extracted route. The selection of the optimum gateway node is done by comparing the ToS supported by the plurality of gateway nodes and the ToS requirement of data packet to be routed. The ToS that can be supported by the plurality of gateway nodes is determined using the path metrics of the plurality of gateway nodes. The message is updated by the node by adding address of the node to list of routes traversed by the message and by updating the path metrics of the route traversed by the message. The updated message is transmitted by the node to the plurality of nodes in the network.
8. Also, disclosed herein is a gateway node for routing data packets in a wireless communication network, the wireless communication network further comprising of a plurality of nodes and a plurality of gateway nodes, the gateway node comprising atleast one means adapted for maintaining measurements of path metrics of the gateway node and sending a message comprising the path metrics to the plurality of nodes in the network.
9. 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
10. The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which:
11. FIG. 1 illustrates a block diagram of interconnected nodes in a communication network, according to an embodiment herein;
12. FIG. 2 illustrates a block diagram of a node in a communication network, according to an embodiment herein;
13. FIG. 3 is a flowchart depicting a method for routing a data packet through a gateway node, according to an embodiment herein; and
14. FIG. 4 is a flowchart depicting a method for determining an optimum gateway node and routing a data packet through the gateway node, according to an embodiment herein.

DETAILED DESCRIPTION OF EMBODIMENTS
15. 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.
16. The embodiments herein adaptively achieve suitable gateway node selection by taking into consideration the Type of Service (ToS) required and the capabilities of the gateway node. The most suitable gateway node in the cluster is determined for a node to route data packets. The selection of the optimum gateway node is done for different classes of traffic based on the ToS requirement of the data packet to be routed and the path metrics of the gateway nodes in the network. The path metrics of a gateway node is used to determine the capability of the particular gateway node. A gateway node having the capability to satisfy the ToS requirements of the data packet is selected to route the data packet to the destination. Referring now to the drawings, and more particularly to FIGs. 1 through 4, where similar reference characters denote corresponding features consistently throughout the figures, there are shown embodiments.
17. FIG. 1 illustrates a block diagram of interconnected nodes in a communication network. In a communications network, the various network elements are interconnected using nodes 102. For example, the elements of a communication network may be base stations, switching centers, servers and computers. The network node 102 is an active electronic device that is attached to a network, and is capable of sending, receiving or forwarding information over a communications channel. The nodes 102 that are connected to a backhaul network 103 are called as gateway nodes 101. The backhaul 103 portion of the network comprises the intermediate links between the core of the network and the small sub-networks at the edge of the entire hierarchical network. For example, cell phones communicating with a single base station constitute a small sub-network and the connection between the base station and the rest of the world begins with a backhaul link to the core of the communication network. When a node 102 receives a packet of data, the node 102 routes the data to the destination and the route may include other nodes 102 in the network. The route would include gateway nodes 101 in the network and the data packet passes through a gateway node 101 before entering the core of the network. There could be multiple routes through which a data packet can be routed and the routes may pass through different gateway nodes 101. A node 102 selects a suitable gateway node 101 from the plurality of gateway nodes 101 to route the data packet to the destination. The selection of the gateway node 101 is done by considering the ToS requirement of the data packet and the capabilities of the gateway nodes 101. The capabilities of gateway nodes 101 are determined by considering the path metrics of the gateway nodes 101. The path metrics of a route in the network indicate the capacity of the route. For example, a path metric may be the bandwidth supported by a gateway node 101.
18. FIG. 2 illustrates a block diagram of a node in a communication network. The nodes 102 that are connected to a backhaul network 103 are called as gateway nodes 101. A gateway node 101 can send, receive or forward information over a communications channel. When a node 102 receives a packet of data, the node 102 routes the data to the destination and the route may include other nodes 102 and gateway nodes 101 in the network. The gateway node 101 provides the data packet a route to the core of the network through the backhaul network 103. A receiver 206 receives data packets coming into the gateway node 101 and a transmitter 205 transmits the data packet to the destination. If the received data has been modulated or encoded, then the receiver 206 may de-modulate or decode the received data. If the data to be transmitted has to be modulated or encoded before being transmitted, then the transmitter 205 modulates or encodes the data before being transmitted. For example, data may be modulated through Phase Shift Keying or Quadrature Amplitude Modulation or the data may be encoded using Non-Return-to-Zero encoding. A processor 204 controls the functioning of the gateway node 101. The processor 204 controls the modulation, de-modulation, encoding, decoding of received and transmitted data and controls the functioning of all the modules in the gateway node 101. A routing module 201 controls the tasks of routing and forwarding data to other elements in the network. The route that the data packet takes to reach the destination is determined by the router 201. The optimum route that the data has to take in order to reach the destination is determined by the router 201 using a routing table 203. For example, the optimum route may be the route that can deliver the data packet to the destination at a faster rate and with a lower error rate. The routing table 203 stores the routes that a data packet can take to reach the destination and the metrics associated with the routes. For example, the metric stored in the routing table 203 may be the bandwidth and delay of a particular node 102 in the network. The routing table 203 contains a list of all the nodes 102 in the network that can be used as a possible route for the data. The path metrics for all the nodes 102 is also stored in the routing table 203. The list of nodes and the path metrics for each node is updated periodically. The routing module 201 uses the routing table 203 to generate the route to be assigned for the transmission of a specific data packet. The forwarding portion 202 is responsible for the actual process of sending a data packet received on a logical interface to an outbound logical interface. The modulated or encoded data from the transmitter 205 is sent on a physical outbound interface by the forwarding portion 202.
19. FIG. 3 is a flowchart depicting a method for routing a data packet through a gateway node. When a node 102 receives a packet of data, the node 102 routes the data to the destination and the route may include other nodes 102 in the network. The route would include gateway nodes 101 in the network and the data packet passes through a gateway node 101 before entering the core of the network. The gateway node 101 maintains a list of various metrics of the gateway node 101. For example the metrics may include the bandwidth and the delay experienced by a data packet from the gateway node 101 to the edge router in the network. The edge router may also be the edge router of an interest service provider. The gateway node 101 may obtain the metrics by actively probing the route using tools designed for calculating the route metrics or by computation of the metrics based on the existing traffic in the route. The gateway node 101 periodically sends (301) out messages to other nodes 102 in the network. The messages contain information about the metrics of the gateway node 101. For example, the message may be an advertisement indicating the presence of the particular gateway node 101 in the network. On receiving (302) the message, the node 102 updates the stored information in the routing table 203 regarding the routes and the path metrics of the routes using the information obtained from the message. The node 102 also updates (303) the messages by adding the IP address of the particular node 102 to the list of nodes traversed by the message. Also, the information regarding the path metrics of the route traversed by the message is updated. If the particular node 102 had received a packet of data that must be routed to the destination, then the node 102 determines (305) an optimum route for the data to reach the destination. An optimum route is determined by considering the path metrics of all the possible gateway nodes in the route and selecting the route with the gateway node 101 having the best path metrics. Information about all the possible routes and the path metrics of the routes is obtained from the routing table 203. A gateway node 101 is selected whose path metrics are best suited to provide the type of service required to be provided for the data packet. There are different Types of Service (ToS) by which each node 102 sends data across a gateway node 101 to the core of the network. Each class of traffic has different requirements in terms of bandwidth, delay, jitter and reliability. For example, a type of service to be provided to a data packet from a particular user may be the bandwidth assigned to the user. A data packet may be routed from a node to the internet through the gateway node 101. A route is determined (305) only when a data packet has to be routed to the destination. After determining the optimum route, the node transmits (306) the data packet through the selected gateway node in the route. For example if there are gateway nodes 101 G1, G2 and G3 in the network and the bandwidth supported by G1 is 100 Kbps, the bandwidth supported by G2 is 200 Kbps and the bandwidth supported by G3 is 300 Kbps. If a node 102 has to route data packets to the destination and the bandwidth requirement of the data packet is 250 Kbps, then the node chooses gateway node 101 G3 as the optimum route to send the data packet. The various actions in method 300 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 3 may be omitted.
20. FIG. 4 is a flowchart depicting a method for determining an optimum gateway node and routing a data packet through the gateway node. The nodes 102 that are connected to a backhaul network 103 are called as gateway nodes 101. Gateway nodes 101 help transmit a data packet to the core of the network. When a node 102 receives a packet of data, the node 102 routes the data to the destination and the route may include other nodes 102 in the network. The route would include gateway nodes 101 in the network. All nodes 102 in the network maintain routes to the gateway nodes 101 in the network. The gateway node 101 maintains a list of various metrics of the gateway node 101. The gateway node 101 may obtain (401) the metrics by actively probing the route using tools designed for calculating the route metrics or by computation of the metrics based on the existing traffic in the route. The gateway node 101 periodically sends (402) out messages to other nodes 102 in the network. The messages contain information about the metrics of the gateway node 101. The messages may be received (403) by all the other nodes 102 in the network. On receiving (302) the message, the node 102 extracts the path traversed by the message before reaching the particular node 102. The node 102 also extracts the path metrics of the route traversed by the message. The node 102 then compares the route with other stored routes for the particular gateway node 101 that sent the message and examines (405) if the route is edge disjoint from already stored routes. If the route is edge disjoint from the stored routes, then the node 102 adds (407) the route to the list of edge disjoint routes to the particular gateway node 101. If the route is not edge disjoint from the stored routes, then the node 102 does not add the route to the list of routes to the particular gateway node 101. The node 102 then updates (406) the stored path metrics of the corresponding route in the routing table 203. Also, the bandwidth and total delay of the route is calculated and stored (408) in the routing table 203. For example, the bandwidth, total delay and other path metrics may be calculated for the path between the particular node 102 and the edge router of an internet service provider. The available bandwidth of the route would be the available bandwidth of the weakest path and the total delay is the sum of the delays experienced on the route from the node to the edge router of the internet service provider. Weakest path may be the path with the minimum amount of bandwidth in the route.
21. There are different ToS by which each node 102 sends data across a gateway node 101 to the core of the network. For example ToS may be the bandwidth assigned for the particular user, jitter and reliability of the route. Each class of traffic has different requirements in ToS. A node 102 routes the data packet through a gateway node 101 offering the ToS requirement of the data packet. The node 102 computes (409) the ToS offered by the gateway nodes 101 in the network using the path metrics stored in the routing table 203. Based on the ToS computed for each gateway node 101 and the ToS requirement of the data packet, the node 102 determines (4010) the gateway node 101 offering the required ToS. The gateway node 101 offering the required ToS is noted. For example, if the value for each path metric offered by a gateway node 101 is above a pre-determined value, a bit in the byte may be set to one. Here the byte represents the capabilities of the gateway node 101. The value of the byte would then represent the ToS supported by a particular gateway node 101 in the route. The node 102 then updates (4011) the message received from the gateway node 101. The node adds the IP address of the particular node 102 to the list of nodes traversed by the message. Also, the information regarding the path metrics of the route traversed by the message is updated. After updating the message, the node 102 forwards (4012) the message to other nodes 102 in the network. After determining the gateway node 101 offering the required ToS, the node 102 determines the route optimum route for transmitting the data packet to the destination. If there are multiple gateway nodes 101 offering the required ToS, then the gateway node 101 having the best path metrics among all the gateway nodes 101 is chosen as the gateway node 101 for transmitting the data packet. A route is determined only when a data packet has to be routed to the destination. After determining the optimum route for transmitting the data, the node 102 transmits the data packet through the determined gateway node 101. The various actions in method 400 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 4 may be omitted.
22. 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.
23. The embodiment disclosed herein specifies a method and system for selecting the optimum gateway node for routing a date packet. The mechanism allows determining the optimum route for transmitting a date packet to the destination, providing a system thereof. Therefore, it is understood that the scope of the protection is extended to such a program and in addition to a computer 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 programming 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. Thus, the means are at least one hardware means and/or at least one software means. 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.
24. 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 routing data packets by a node in a wireless communication network, said wireless communication network further comprising of a plurality of nodes and a plurality of gateway nodes, said method comprising
said plurality of gateway nodes sending a message to a plurality of nodes in the network, where said message has information about the path metrics of corresponding gateway node;
said node selecting an optimum gateway node from said plurality of gateway nodes by referring to said message, when said node has to route said data packets to a destination, where said selection is done based on Type of Service (ToS) requirement of said data packets and ToS that can be supported by said plurality of gateway nodes; and
said node transmitting said data packets through said selected gateway node.

2. The method, as claimed in claim 1, wherein said plurality of nodes maintain a list of active gateway nodes from among said plurality of gateway nodes, and a list of routes to said plurality of gateway nodes, and said path metrics of said routes.

3. The method, as claimed in claim 1, wherein said node extracts said path metrics and route traversed by said message before reaching said node and adds said extracted route traversed by said message to list of edge disjoint routes to corresponding said gateway node, if route traversed by said message is edge disjoint from said list of routes to corresponding said gateway node.

4. The method, as claimed in claim 1, wherein said node updates said list of routes to said plurality of gateway nodes and said path metrics of said routes using said extracted path metrics and said extracted route.

5. The method, as claimed in claim 1, wherein said selection of said optimum gateway node is done by comparing said ToS supported by said plurality of gateway nodes and said ToS requirement of data packet to be routed, wherein said ToS that can be supported by said plurality of gateway nodes is determined using said path metrics of said plurality of gateway nodes.

6. The method, as claimed in claim 1, wherein said message is updated by said node by adding address of said node to list of routes traversed by said message and by updating said path metrics of said route traversed by said message and said updated message is transmitted by said node to said plurality of nodes in the network.

7. A node for routing data packets in a wireless communication network, said wireless communication network further comprising of a plurality of nodes and a plurality of gateway nodes, said node comprising atleast one means adapted for
sending a message by said plurality of gateway nodes to a plurality of nodes in the network, where said message has information about the path metrics of corresponding gateway node;
selection of an optimum gateway node from said plurality of gateway nodes by said node, when said node has to route said data packets to a destination, where said selection is done based on Type of Service (ToS) requirement of said data packets and ToS that can be supported by said plurality of gateway nodes; and
transmitting said data packets through said selected gateway node by said node.

8. The node, as claimed in claim 7, wherein said node is adapted to maintain a list of active gateway nodes from among said plurality of gateway nodes.

9. The node, as claimed in claim 7, wherein said node is adapted to maintain a list of routes to said plurality of gateway nodes and path metrics of said routes.

10. The node, as claimed in claim 7, wherein said node is adapted to determine ToS that can be supported by said plurality of gateway nodes using said path metrics of said plurality of gateway nodes.

11. The node, as claimed in claim 7, wherein said node is adapted to update said message by adding address of said node to list of routes traversed by said message and by updating said path metrics of said route traversed by said message and said updated message is transmitted by said node to said plurality of nodes in the network.

12. A wireless communication network comprising of a plurality of nodes and a plurality of gateway nodes, said node comprising atleast one means adapted for
sending a message by said plurality of gateway nodes to a plurality of nodes in the network, where said message has information about the path metrics of corresponding gateway node;
selection of an optimum gateway node from said plurality of gateway nodes by said node, when said node has to route said data packets to a destination, where said selection is done based on Type of Service (ToS) requirement of said data packets and ToS that can be supported by said plurality of gateway nodes; and
transmitting said data packets through said selected gateway node by said node.

13. The wireless communication network, as claimed in claim 12, wherein said plurality of nodes is adapted to maintain a list of active gateway nodes from among said plurality of gateway nodes and said path metrics of said routes.

14. The wireless communication network, as claimed in claim 12, wherein said plurality of nodes is adapted to extract said path metrics and route traversed by said message before reaching said node and adds said extracted route traversed by said message to list of edge disjoint routes to corresponding said gateway node, if route traversed by said message is edge disjoint from said list of routes to corresponding said gateway node.

15. The wireless communication network, as claimed in claim 12, wherein said plurality of nodes is adapted to update said list of routes to said plurality of gateway nodes and said path metrics of said routes using said extracted path metrics and said extracted route.

16. The wireless communication network, as claimed in claim 12, wherein said selection of said optimum gateway node is done by comparing said ToS supported by said plurality of gateway nodes and said ToS requirement of data packet to be routed, wherein said ToS that can be supported by said plurality of gateway nodes is determined using said path metrics of said plurality of gateway nodes.
17. The wireless communication network, as claimed in claim 12, wherein said message is updated by said node by adding address of said node to list of routes traversed by said message and by updating said path metrics of said route traversed by said message and said updated message is transmitted by said node to said plurality of nodes in the network.

18. A gateway node for routing data packets in a wireless communication network, said wireless communication network further comprising of a plurality of nodes and a plurality of gateway nodes, said gateway node comprising atleast one means adapted for
maintaining measurements of path metrics of said gateway node; and
sending a message comprising said path metrics to said plurality of nodes in the network.

Dated this 9th September 2009

Dr. Kalyan Chakravarthy
Patent Agent