Efficient path learning in network

• US 20020186665A1
• Filed: 03/14/2001
• Published: 12/12/2002
• Est. Priority Date: 03/14/2001
• Status: Abandoned Application

• Current Assignee: Telephonics Wireless Corporation
• Original Assignee: Telephonics Wireless Corporation
• Inventors: Matthews, Gary, DʼAgati, Laurence, Chaffee, Donald
• Application Number:
  US09/808,635
• Publication Number:
  US 20020186665A1
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes

Abstract

The present invention relates to a network nodes that are interconnected by communication links. Each node is capable of determining communication paths or routes from itself to as many other nodes as possible, either directly or relaying through other nodes, in order to complete the network. These paths are evaluated as new information concerning a route is generated, according to selected criteria, so that the best paths are identified, remembered and used when communication is performed. This invention is concerned with the determination of best paths through a network and the maintenance of these paths as communication conditions and node population changes.

Claims

1. A network comprising a plurality of nodes wherein each of said nodes has a memory, a computing capability, and an ability to communicate with one or more other nodes wherein a communication sent from a source node to a destination node is sent along a path containing one or more nodes wherein each of said nodes in said path that receives said communication determines the best path for said communication to the destination node through a neighboring node based on information received from each neighboring node.

2. The network according to claim 1 wherein communication paths are re-evaluated as new information concerning a path is generated by neighboring nodes.

3. The network according to claim 2 wherein the best path is one that minimizes a selected cost function.

4. The network according to claim 3 wherein the cost function is composed of one or more metrics that are defined by the goals of the particular network.

5. The network according to claim 4 wherein the metric includes the number of nodes that a message must pass through before reaching the destination node.

6. The network according to claim 4 wherein the metric includes the probability of successful transmission though a route.

7. The network according to claim 4 wherein the metric includes the worst probability of successful transmission in a segment of the route.

8. The network according to claim 4 wherein the metric includes the traffic burden on individual nodes in the network.

9. The network according to claim 4 wherein a path is evaluated by selecting a parameter and basing the decision on whether a given route is the best route for the transmission based on the single weakest point along the path.

10. The network according to claim 4 wherein a path is evaluated by selecting a parameter and basing the decision on whether a given route is the best route for the communication based on the single best point along the path..

11. The network according to claim 4 wherein a value is determined for each of a selected group of parameters and based on the relative value of each parameter a weighted computation is made to determine the best route along the path.

12. The network according to claim 11 wherein the information concerning a path for a communicating a message from a node is determined by said node only from communications from the nodes that are in direct communication with said node

13. The network according to claim 9 wherein the information concerning a path for a communicating a message from a node is determined by said node only from communications from the nodes that are in direct communication with said node.

14. The network according to claim 1 wherein the selection of the first node in a chain of nodes to a destination node depends on data generated by each node in calculating the best path to each of the other nodes in the network from information received from adjacent nodes.

15. The network according to claim 2 wherein information that is used for path selection is maintained in a table in each node.

16. The network according to claim 15 wherein each table has one or more rows indexed by a final destination and one or more columns each containing that node'"'"'s computation of a specific metric for the path to that destination.

17. The network according to claim 16 wherein the information that is placed in a node'"'"'s table is determined by processing information from each neighboring node'"'"'s table.

18. The network according to claim 4 wherein the metrics may be sent to neighbor nodes as a separate transmission.

19. The network according to claim 4 wherein the metrics may be sent to neighbor nodes by concatenation with normal message traffic.

20. The network according to claim 18 wherein changes in the metrics are prioritized according to the time of their last update.

21. A method of transmitting a communication from a source node to a destination node in a network having a plurality of nodes comprising determining the best path for said communication from said source node to the destination node through each neighboring node based on information received from each neighboring node;

transmitting said communication from said source node to a the neighboring receiving node determined to be the best path for said communication to said destination node;

determining the best path from the receiving node to the destination node through each neighboring node based on information received from each of said neighboring nodes;

continuing the steps until the destination node receives the communication.

22. The method according to claim 21 wherein communication paths are re-evaluated as new information concerning a path is generated by neighboring nodes.

23. The method according to claim 22 wherein the best path is one that minimizes a selected cost function.

24. The method according to claim 23 wherein the cost function is composed of one or more metrics that are defined by the goals of the particular network.

25. The method according to claim 24 wherein the metric includes the number of nodes that a message must pass through before reaching the destination node.

26. The method according to claim 24 wherein the metric includes the probability of successful transmission though a route.

27. The method according to claim 24 wherein the metric includes the worst probability of successful transmission in a segment of the route.

28. The method according to claim 24 wherein the metric includes the traffic burden on individual nodes in the network.

29. The method according to claim 24 wherein a path is evaluated by selecting a parameter and basing the decision on whether a given route is the best route for the transmission based on the single weakest point along the path.

30. The method according to claim 24 wherein a path is evaluated by selecting a parameter and basing the decision on whether a given route is the best route for the communication based on the single best point along the path.

31. The method according to claim 24 wherein a value is determined for each of a selected group of parameters and based on the relative value of each parameter a weighted computation is made to determine the best route along the path.

32. The method according to claim 31 wherein the information concerning a path for a communicating a message from a node is determined by said node only from communications from the nodes that are in direct communication with said node

33. The method according to claim 29 wherein the information concerning a path for a communicating a message from a node is determined by said node only from communications from the nodes that are in direct communication with said node.

34. The method according to claim 22 wherein information that is used for path selection is maintained in a table in each node.

35. The method according to claim 34 wherein each table has one or more rows indexed by a final destination and one or more columns each containing that node'"'"'s computation of a specific metric for the path to that destination.

36. The method according to claim 24 wherein the metrics may be sent to neighbor nodes as a separate transmission.

37. The method according to claim 24 wherein the metrics may be sent to neighbor nodes by concatenation with normal message traffic.

38. The method according to claim 24 wherein changes in the metrics are prioritized for sending to neighboring nodes according to the time of their last update.

39. The method according to claim 37 wherein the forwarding of path metric information throughout the network adds only a relatively small amount of overhead to normally transmitted messages.

40. A node in a network comprising a plurality of nodes, said node having a memory, a computing capability, and an ability to communicate with one or more other nodes, said node being adapted to receive a communication sent from a source node to be sent to a destination node, said node being adapted to send said communication along a path containing one or more nodes wherein said node determines the best path for said communication to the destination node through neighboring nodes based on information received from said neighboring nodes.