Route selection in a communications network using combined values of metrics of different characteristics

• US 8,027,275 B2
• Filed: 03/20/2003
• Issued: 09/27/2011
• Est. Priority Date: 03/20/2002
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Ebata, Koichi, Furukawa, Hiroshi
• Primary Examiner(s): Ton; Dang
• Assistant Examiner(s): O CONNOR, BRIAN T
• Application Number:
  US10/392,174
• Publication Number:
  US 20030179718A1
• Time in Patent Office: 3,113 Days
• Field of Search: 370/235, 370/238, 370/248, 370/250, 370/255, 709/238, 709/241, 709/249
• US Class Current: 370/255
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

A control packet is broadcast over a route, containing first and second metric values of different transmission characteristics of the route. At a local node, control packets from multiple nodes are received and examined for their source. If the packets are received from upstream nodes, the metrics of the received packets are updated, the second metric is weighted and summed with the first metric to produce a number of combined metrics and a minimum value of the combined metrics is detected. One of the routes having the detected value is selected as a route to an upstream node. If the control packets are received from downstream nodes, the second metric is weighted and summed with the first metric to produce a number of combined metrics and a smaller values of combined metrics are detected corresponding in number to usable antennas and routes of the detected values are selected.

Claims

1. A method of determining a route in a communications network, comprising the steps of:

a) broadcasting control packets from a plurality of nodes via a plurality of routes to a local node, each of said control packets containing a first metric value of a first category and a second metric value of a second category, said first and second categories respectively representing transmission quality and hop count of a corresponding one of said routes;

b) receiving, at said local node, control packets from said plurality of nodes; and

c) multiplying the second metric value of each of the received control packets by a coefficient of said first category and summing the first metric value and the multiplied second metric value of each of the received control packets to produce a plurality of summed metric values corresponding in number to said plurality of routes and selecting at least one of said routes according to said plurality of summed metric values,

wherein the first metric value and the second metric value have different units of measurement.

2. The method of claim 1, wherein the step (c) comprises detecting a minimum value of said summed metric values and selecting one of said routes having the detected minimum value when said control packets are received from upstream nodes.

3. The method of claim 2, wherein the step (b) further comprises updating the first and second metric values of each of said received control packets.

4. The method of claim 1, wherein said coefficient is variable with the second metric value.

5. The method of claim 1, wherein said coefficient is infinity when said hop count number exceeds a predetermined value.

6. The method of claim 1, wherein each of said nodes is a wireless node, further comprising the steps of detecting a plurality of smaller values of said summed metric values corresponding in number to wireless links that can be established from said local node and selecting routes having the detected smaller values from said plurality of routes when said control packets are received from downstream nodes.

7. The method of claim 6, wherein said plurality of nodes are located on downstream side of said local node.

8. The method of claim 1, wherein said plurality of nodes are located on upstream side of said local node.

9. The method of claim 1, wherein the step (c) comprises the steps of:

A) storing the first and second metric values of each control packet in an entry of a memory;

B) determining whether a sufficient amount of metric values are stored in said memory; and

C) if a sufficient amount of metric values are stored in said memory, performing step (c).

10. A method of determining a route in a wireless communications network, comprising the steps of:

a) broadcasting control packets from a plurality of wireless nodes via a plurality of routes to a local wireless node, each of said control packets containing a first metric value of a first category and a second metric value of a second category, said first and second categories respectively representing transmission quality and hop count of a corresponding one of said routes;

b) receiving, at said local node, control packets from said plurality of nodes;

c) determining whether the received control packets are received from upstream nodes or downstream nodes;

d) if the control packets are received from upstream nodes, updating the first and second metric values of the received control packets and multiplying the second metric value of each of the received control packets by a coefficient of said first category and summing the first metric value and the multiplied second metric value of each of the received control packets to produce a plurality of summed metric values and selecting one of said routes according to said plurality of summed metric values; and

e) if the control packets are received from downstream nodes, multiplying the second metric value of each of the received control packets with a coefficient of said first category and summing the first metric value with the multiplied second metric value of said each control packet to produce a plurality of summed metric values and determining smaller values of the summed metric values corresponding in number to wireless links that can be established from said local wireless node and selecting routes having the detected smaller values of the summed metric values from said plurality of routes,

wherein the first metric value and the second metric value have different units of measurement.

11. A network node for a communications network wherein said network node is one of a plurality of interconnected nodes of said network, comprising:

an interface connected to the network;

a metric table having a plurality of entries; and

routing control means for broadcasting a control packet to said network via said interface, said control packet containing a first metric value of a first category and a second metric value of a second category, said first and second categories respectively representing transmission quality and hop count of one of a plurality of routes from said network node, receiving said control packets from said plurality of nodes via said interface, storing the first and second metric values of each of the received control packets in respective entries of said metric table, multiplying, in each of said entries, the second metric value with a coefficient of said first category and summing the first metric value and the multiplied second metric value to produce a plurality of summed metric values and selecting at least one of said routes according to said plurality of summed metric values,

wherein the first metric value and the second metric value have different units of measurement.

12. The network node of claim 11, wherein said routing control means detects a minimum value of said summed metric values and selects one of said routes having the detected minimum value.

13. The network node of claim 12, wherein the routing control means updates the first and second metric values of each of said received control packets before multiplying said second metric value and summing the updated first metric value with the multiplied updated second metric value to produce said plurality of summed metric values.

14. The network node of claim 11, wherein said coefficient is variable with the second metric value.

15. The network node of claim 11, wherein said coefficient is infinity when said hop count number exceeds a predetermined value.

16. The network node of claim 11, wherein said interface is a wireless interface and wherein said routing control means further detects a plurality of smaller values of said summed metric values corresponding in number to wireless links that can be established from said wireless interface and select routes having the detected smaller values from said plurality of routes.

17. The network node of claim 16, wherein said plurality of nodes from which said control packets are received are located on downstream side of said network node.

18. The network node of claim 11, wherein said plurality of nodes from which said control packets are received are located on upstream side of said network node.