HK1138445B

HK1138445B - Method and apparatus for determining a route metric

Info

Publication number: HK1138445B
Application number: HK10103639.9A
Authority: HK
Inventors: Xianchao Xu; Weihua Wu
Original assignee: Intel Corporation
Filing date: 2006-12-27
Publication date: 2012-11-02

Description

Method and apparatus for determining routing metrics

Technical Field

The present invention relates to a method and apparatus for determining routing metrics.

Background

Two algorithms are generally available for measuring routing metrics in mesh networks: ETX (expected number of transmissions) and ETT (expected time of transmission). The ETX metric may measure the packet loss rate for each link between two adjacent nodes along the route. The ETT metric may take into account packet loss rate and data rate and use min { ETX_rate[ Rate ] as a metric for each link, where ETX_rateMay represent different packet loss rates at different data rates.

Disclosure of Invention

According to a first embodiment, the present invention provides a method for determining a routing metric, comprising:

analyzing a characteristic of a packet, wherein the characteristic of the packet indicates a group containing at least one of whether the packet is transmission quality sensitive and whether the packet is transmission throughput sensitive;

determining a weight relationship between a packet loss rate and a data rate for a route, wherein the weight relationship varies with a characteristic of the packet; and

determining a routing metric for the route based on the packet loss rate, the data rate, and the weight relationship.

According to a second embodiment, the present invention provides an apparatus for determining a routing metric, comprising:

a packet analysis module that analyzes a characteristic of a packet, wherein the characteristic indicates at least one of a group containing whether the packet is transmission quality sensitive and whether the packet is transmission throughput sensitive; and

a metric module that determines a weight relationship between a packet loss rate and a data rate for a route, and determines a routing metric for the route based on the packet loss rate, the data rate, and the weight relationship, wherein the weight relationship varies with a characteristic of the packet.

According to a third embodiment, the present invention provides an apparatus for determining a routing metric, comprising:

a packet analysis module that analyzes a characteristic of a packet, wherein the characteristic of the packet indicates at least one of a group containing whether the packet is transmission quality sensitive and whether the packet is transmission throughput sensitive; and

a metric module that determines, for each route of a plurality of routes, a weight relationship between a packet loss rate and a data rate, and determines a plurality of route metrics for the plurality of routes, wherein each route metric of the plurality of route metrics corresponds to the each route and is determined based on the packet loss rate, the data rate, and the weight relationship for the each route, and wherein the weight relationship varies with a characteristic of the packet.

Drawings

The invention described herein is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings. Elements illustrated in the figures have not necessarily been drawn to scale for simplicity and clarity of illustration. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals have been repeated among the figures to indicate corresponding or analogous elements.

Fig. 1 illustrates an embodiment of a mesh network including a plurality of nodes.

Fig. 2 illustrates an embodiment of a node in a mesh network.

Fig. 3 illustrates an embodiment of a method for nodes in a mesh network to select routes based on route metrics.

Detailed Description

The following description describes techniques for determining routing metrics. In the following description, numerous specific details such as logic implementations, pseudo code, methods of specifying operands, resource partitioning/sharing/duplication implementations, types and interrelationships of system components, and logic partitioning/integration choices are set forth in order to provide a more thorough understanding of the present invention. However, the invention may be practiced without such specific details. In other instances, control structures, gate level circuits and full software instruction sequences have not been shown in detail in order not to obscure the invention. Those of ordinary skill in the art, with the included descriptions, will be able to implement appropriate functionality without undue experimentation.

References in the specification to "one embodiment," "an example embodiment," etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.

Embodiments of the invention may be implemented in hardware, firmware, software, or any combination thereof. Embodiments of the invention may also be implemented as instructions stored on a machine-readable medium, which may be read and executed by one or more processors. A machine-readable medium may include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computing device). For example, a machine-readable medium may include read-only memory (ROM), random-access memory (RAM), magnetic disk storage media, optical storage media, flash-memory devices, electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.), and others.

An embodiment of a mesh network 1 comprising a plurality of nodes is shown in fig. 1. As shown, the mesh network may include four nodes 110, 120, 130, and 140. However, it should be understood that the mesh network 1 may have any number of nodes. Each node may have one or more neighboring nodes, and two neighboring nodes may communicate with each other via a wireless link. Examples for a node may include a mainframe computer, a microcomputer, a personal computer, a portable computer, a laptop computer, and other devices used to transceive and process data.

Many protocols are available for routing in mesh networks, such as the ad hoc on-demand distance vector routing (AODV) protocol. These protocols may determine routes to direct data from a source node (e.g., node 110) to a destination node (e.g., node 140) based on various factors such as packet loss rate and data rate. A routing protocol may define a route metric to measure some characteristic for each route between a source node and a destination node and select a route directing data based on the route metric. For example, there may be two routes from node 110 to node 140, such as a route through nodes 110, 120, and 140 and a route through nodes 110, 130, and 140. The routing protocol may measure a route metric for each route and select a route between nodes 110 and 140 that directs data based on the route metric.

Although fig. 1 illustrates a mesh network, it should be understood that the present invention can be used with other types of networks.

Fig. 2 illustrates an embodiment of a node in a mesh network. As shown, the node may include one or more processors 21, memory 22, chipset 23, network interface 24, firmware 25, and possibly other components. The one or more processors 21 may be communicatively coupled to various components (e.g., chipset 23) via one or more buses, such as a processor bus. The processor 21 may be implemented as an Integrated Circuit (IC) having one or more processing cores that may execute code under a suitable architecture, including, for example, that available from Intel corporation of Santa Clara, CalifXeonT^M、Pentium^TM、Itanium^TMAnd (5) architecture.

The memory 22 may store data and instructions in the form of a routing application 202 and an operating system 201. Examples of the memory 22 may include one of or any combination of semiconductor devices such as Synchronous Dynamic Random Access Memory (SDRAM) devices, RAMBUS Dynamic Random Access Memory (RDRAM) devices, Double Data Rate (DDR) memory devices, Static Random Access Memory (SRAM), and flash memory devices.

The operating system 201 may control the tasks that the nodes may perform and manage system resources to optimize performance. Examples of operating system 201 may include, but are not limited to, different versionsAnd real-time operating systems, e.g.And the like. The operating system 201 may include a number of modules to bridge and perform resource optimization between upper-level applications and underlying hardware. For example, operating system 201 may include a driver 2010 to control a device (e.g., network interface 24) according to commands from a user application (e.g., routing application 202).

The driver 2010 may receive the routing command from the routing application 202 and instruct the network interface 24 to direct the data to the destination node indicated in the routing command. Driver 2010 may also analyze packets to be routed for any characteristic of interest, such as whether the packet is transmission quality sensitive (e.g., a voice packet) or whether the packet is transmission throughput sensitive (e.g., a file transfer protocol packet). The driver 2010 may report characteristics of the packet to the routing application 202 for routing metric computation (calculation) and/or route determination.

Drive 2010 may include a routing table 2011 that records a plurality of routes from the node to a plurality of destination nodes. The routing table 2011 may take various forms. For example, the routing table 2011 may include multiple entries, one for each destination node. Each entry may include a number of items such as a destination node, a next hop node, a routing metric, a data rate, and characteristics of the packet to be routed. The routing table may use different ways to represent packet characteristics. For example, the routing table may use a "packet priority" of no greater than 3 to indicate that the packet is transmission quality sensitive, and a "packet priority" of greater than 3 to indicate that the packet is transmission throughput sensitive.

Driver 2010 may also include packet analysis logic 2012 to analyze characteristics of the packets. The characteristics may assist the driver 2010 in searching for a route from a routing table that corresponds to the characteristics of the packet, or assist the routing application 202 in determining a routing metric for the route, where the characteristics of the packet may assist in determining a weight relationship between a packet loss rate and a data rate used to compute the routing metric.

Driver 2010 may search a routing table for a route directing data from a current node to a destination node, and the route may correspond to the analyzed packet characteristics. However, if driver 2010 cannot find a route from the routing table, driver 2010 may notify routing application 202 that routing application 202 may determine whether a route exists from the current node to the destination node. In response to a route existing, routing application 202 may compute a route metric for the route based on the packet characteristics and add the route and its route metric to the routing table. However, if there are multiple routes from the current node to the destination node, e.g., there may be two routes from node 110 to node 140, routing application 202 may compute a routing metric for each route based on the packet characteristics and select a route to route the data based on the routing metrics.

The routing application 202 may include a routing table 2011 to store routes for each destination node. Routing application 202 may keep the routing tables in itself consistent by updating both routing tables simultaneously with the routing tables in drive 2010.

Routing application 202 may further include metric logic 2020 to compute routing metrics based on packet characteristics analyzed by driver 2010. Metric logic 2020 may operate the routing metric using the following equation:

metric_routecan represent metrics for a route, and metric_linkMay represent a metric for the link of the route. Two neighboring nodes may establish a link, e.g., a link between nodes 110 and 120. n may be an integer and may represent the number of links a route may have. For example, a route (110, 120, 140) may have two links, namely a link (110, 120) and a link (120, 14). The rate may represent a data rate on a link, and data may be transmitted at different data rates on the link. p is a radical of_rateMay represent packet loss rates at the data rate, and different data rates may be associated with different packet loss rates. a and b may be determinable packet loss rates (p)_rate) And a weight relationship with a data rate (rate).

As described above, the packet characteristics may help metric logic 2020 determine a weighted relationship between packet loss rate and data rate. For example, metric logic 2020 may assign a greater weight to a packet loss rate than to a data rate assignment if the packet is transmission quality sensitive, and to a data rate than to a packet loss rate assignment if the packet is transmission throughput sensitive. In the case of the above equation, for quality sensitive packets, parameter a may be greater than parameter b (e.g., a-10 and b-1), while for throughput sensitive packets, parameter b may be greater than parameter a (e.g., b-10 and a-1).

Other algorithms may operate the routing metrics in other ways. For example, metric logic 2020 may operate a routing metric by the following equation:

routing application 202 may further include routing logic 2021 to select routes based on the routing metrics for each available route from the current node to the destination node. For the passing equationTo compute the route metric, the route selection logic 2021 may select the route having the smallest route metric. The routing logic 2021 may perform other functions, such as updating the routing table 2011 with new routes.

In accordance with the present invention, routing application 202 can select different routes for different packets having different characteristics, even if the same packet loss rate and data rate pair is used. For example, three pairs of packet loss rates and data rates may be used for data transmission on the link between nodes 110 and 120 and the link between nodes 120 and 140.

Packet loss rate	Data rate
		50	54
40	36
		10	6

Three more pairs of packet loss rates and data rates may be used for data transmission on the link between nodes 110 and 130 and the link between nodes 130 and 140.

Packet loss rate	Data rate
		60	54
50	36
		7	6

Metric logic 2020 may determine that parameters a and b are 10 and 1 for the transmission of quality sensitive packets and that parameters a and b are 1 and 10 for the transmission of throughput sensitive packets. Thus, for packets that are transmission quality sensitive, the routing metric for the route through nodes 110, 120, and 140 may be:

metric_110-120-140＝metric_110-120+metric_120-140

＝min{50/(10+1*54)，40/(10+1*36)，10/(10+1*6)}+

min{50/(10+1*54)，40/(10+1*36)，10/(10+1*6)}

＝1.25

also, the routing metric for a route through nodes 110, 130, and 140 may be:

metric_110-130-140＝metric_110-130+metric_130-140

＝Min{60/(10+1*54)，50/(10+1*36)，7/10+1*6)}+

min{60/(10+1*54)，50/(10+1*36)，7/(10+1*6)}

＝0.875

however, for packets that are transmission throughput quality sensitive, the routing metric for the route through nodes 110, 120, and 140 may be:

metric_110-120-140＝metric_110-120+metric_120-140

＝min{50/(1+10*54)，40/(1+10*36)，10/(1+10*6)}+

min{50/(1+10*54)，40/(1+10*36)，10/(1+10*6)}

＝0.185

also, the routing metric for a route through nodes 110, 130, and 140 may be:

metric110-130-140＝metric110_-130+metric_130-140

＝Min{60/(1+10*54)，50/(1+10*36)，7/(1+10*6)}+

min{60/(1+10*54)，50/(1+10*36)，7/(1+10*6)}

＝0.222

thus, routing logic 2021 may route packets that are transmission quality sensitive (110, 130, 140) and packets that are transmission throughput sensitive (110, 130, 140).

Chipset 23 may provide one or more communication paths between one or more processors 21, memory 22, and other components, such as a network interface 24 and firmware 25.

The network interface 24 may transceive packets over a mesh network. Examples of network interface 24 may include a network card, a bluetooth device, an antenna, and other devices for transceiving data.

Firmware 25 may store BIOS routines that the node executes during system boot to initialize processor 21, chipset 23, and other components of the node and/or EFI routines that interface firmware 25 with operating system 201 and provide a standard environment for booting operating system 201.

Fig. 3 illustrates an embodiment of a method of selecting a route based on route metrics. In block 301, a source node (e.g., node 110) may determine to transmit a packet to a destination node (e.g., node 140). In block 302, a driver 2010 of the source node may analyze characteristics of the packet. For example, the characteristic may indicate whether the packet is transmission quality sensitive or transmission throughput sensitive. In block 303, the source node may search the routing table 2011 for entries corresponding to packet characteristics and destination nodes.

If an entry is found in block 304, the driver 2010 of the source node may send the packet through the route indicated by the entry in block 305. If no entry is found in block 304, the source node may broadcast a routing request to its neighboring nodes to request a route from the neighboring nodes to the destination node in block 306. For example, node 110 may broadcast a route request to nodes 120 and 130 requesting a route from each neighboring node to destination node 140.

The route request may include the destination node and packet characteristics. The neighboring node may search its own routing table for a requested route, which may correspond to the packet characteristics and the destination node, and may send a route request reply including the requested route back to the node. However, if the requested route is not found from the routing table stored in the neighboring node, the neighboring node may broadcast another route request to its neighboring nodes, and if the route is eventually found, may send a route request reply back to the source node.

If, in block 307, the source node receives multiple route request replies from multiple neighboring nodes (e.g., from nodes 120 and 130), then, in block 308, the metric logic 2020 of the node may compute a route metric for each route indicated by each route request reply. For example, each of the routes may be from the source node to the destination node (e.g., a route through nodes 110, 120, and 140 and/or a route through nodes 110, 130, and 140) through each of the neighboring nodes that may send out a route request reply. In computing the routing metric, the metric logic 2020 may also utilize the packet characteristics to determine a weighted relationship between the packet loss rate and the data rate.

Subsequently, in block 309, the routing logic 2021 of the source node may select a route to route the packet from the source node to the destination node based on the routing metric computed in block 308. For example, the routing logic 2021 may select the route with the smallest routing metric. Meanwhile, routing logic 2021 may update the routing table by adding the selected route and its routing metrics to the routing table.

If only one route request reply is received in block 310, the driver 2010 of the node may send the packet over the route indicated by the route request reply in block 311. For example, the route may be from the node to the destination node through a neighboring node that may send out a route request reply. At the same time, the routing logic 2010 may compute a routing metric for the route and update the routing table by adding the route and its routing metric to the routing table. In response to not receiving a route request reply in block 310, the node may abort sending the packet.

Other techniques may implement other embodiments of methods for selecting routes. For example, the route request reply may further include a route metric for the route from the neighboring node to the destination node. The source node may then simply need to compute a link metric for the link between the source node and the neighboring node and obtain a route metric for the route from the source node to the destination node by adding the link metric to the route metric in the route request reply.

While certain features of the invention have been described with reference to example embodiments, the description is not intended to be construed in a limiting sense. Various modifications of the example embodiments, as well as other embodiments of the invention, which are apparent to persons skilled in the art to which the invention pertains are deemed to lie within the spirit and scope of the invention.

Claims

1. A method for determining routing metrics, comprising:

2. The method of claim 1, wherein if the packet is sensitive to the transmission quality, the weight relationship is determined by assigning a greater weight to the packet loss rate than to the data rate assignment.

3. The method of claim 1, wherein if the packet is transmission throughput sensitive, the weight relationship is determined by assigning a greater weight to the data rate than to the packet loss rate.

4. The method of claim 1, wherein if the route includes a plurality of links, determining the routing metric by adding a plurality of link metrics, wherein each link metric corresponds to each of the plurality of links and is a function of the packet loss rate, the data rate, and the weight relationship.

5. The method of claim 1, wherein the routing metric is determined based on the following equation:

wherein, metric_routeRepresenting said routing metric, metric_linkRepresenting each link metric corresponding to each link of said route, n being an integer and representing the number of links said route has, rate representing said data rate, p_rateRepresenting a packet loss rate at said data rate, a and b being parameters determining said weighted relation between said packet loss rate and said data rate.

6. The method of claim 1, wherein the routing metric is determined based on the following equation:

wherein, metric_routeRepresenting said routing metric, metric_linkRepresenting each link metric corresponding to each link of said route, n beingInteger and representing the number of links the route has, rate representing the data rate, p_rateRepresenting a packet loss rate at said data rate, a and b being parameters determining said weighted relation between said packet loss rate and said data rate.

7. An apparatus for determining routing metrics, comprising:

8. The apparatus of claim 7, wherein if the packet is sensitive to the transmission quality, the weight relationship is determined by assigning a greater weight to the packet loss rate than to the data rate assignment.

9. The apparatus of claim 7, wherein the weight relationship is determined by assigning a greater weight to the data rate than to the packet loss rate if the packet is transmission throughput sensitive.

10. The apparatus of claim 7, wherein if the route includes a plurality of links, the route metric is determined by adding a plurality of link metrics, wherein each link metric corresponds to each of the plurality of links and is a function of the packet loss rate, the data rate, and the weight relationship.

11. The apparatus of claim 7, wherein the routing metric is determined based on the following equation:

12. The apparatus of claim 7, wherein the routing metric is determined based on the following equation:

13. An apparatus for determining routing metrics, comprising:

14. The apparatus of claim 13, further comprising a routing module to select a route from the plurality of routes to direct the packet based on the plurality of routing metrics.

15. The apparatus of claim 13, further comprising a driver to:

searching a table for a route corresponding to a characteristic of the packet;

if the table does not record the route, sending a route request to a plurality of neighboring nodes, the route request including characteristics of the packet; and

receiving a plurality of route request replies, each route request reply from each of the plurality of neighboring nodes and including a sub-route.

16. The apparatus of claim 15, wherein the metrics module further determines each routing metric corresponding to the each route based on a sub-route metric for the sub-route.

17. The apparatus of claim 13, wherein if the packet is sensitive to the transmission quality, the weight relationship is determined by assigning a greater weight to the packet loss rate than to the data rate assignment.

18. The apparatus of claim 13, wherein the weight relationship is determined by assigning a greater weight to the data rate than to the packet loss rate if the packet is transmission throughput sensitive.

19. The apparatus of claim 13, wherein the metrics module determines the each routing metric based on the following equation:

wherein, metric_routeRepresenting said each routing metric, metric_linkRepresenting each link metric for each link corresponding to said each route, n being an integer and representing the number of links said each route has, rate representing the data rate for said each route, p_rateRepresenting a packet loss rate at said data rate, a and b being parameters determining said weighted relation between said packet loss rate and said data rate.

20. The apparatus of claim 13, wherein the metric module determines the routing metric based on the following equation:

wherein, metric_routeRepresenting said each routing metric, metric_linkRepresenting each link metric for each link corresponding to said each route, n being an integer and representing the number of links said each route has, rate representing the data rate for said each route, p_rateRepresenting a packet loss rate at said data rate, a and b being integers determining said weighted relationship between said packet loss rate and said data rate.