Variable translucency no-sight routing for AD-HOC networks

• US 8,144,595 B1
• Filed: 03/23/2005
• Issued: 03/27/2012
• Est. Priority Date: 03/25/2004
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Inventors: Troxel, Gregory Donald, Ramanathan, Subramanian
• Primary Examiner(s): Wong, Xavier S.
• Application Number:
  US11/087,406
• Time in Patent Office: 2,561 Days
• Field of Search: 370/238, 370/238.1, 455/445
• US Class Current: 370/238
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• 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: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/286 Time to live
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality

Abstract

A system comprising a plurality of nodes forming a network and a link-state packet capable of being transmitted by a source node in the network to a destination node in the network over a communication link; wherein the source node subtracts a transmission cost associated with the communication link from a time-to-live value associated with the link-state packet prior to transmitting the link-state packet to the destination node. Each node in the network may be configured to use a routing protocol, such as a no-sight routing protocol, to assign the transmission cost to the communication link.

Claims

1. A system comprising:

a plurality of nodes forming a network; and

a link-state packet configured to be transmitted by one of said plurality of said nodes acting as a source node in said network to other of said plurality of said nodes acting as destination nodes in said network over a plurality of communication links;

wherein said source node is configured to subtract a respective predetermined transmission cost associated with each one of said communication links from a time-to-live value associated with said link-state packet prior to transmitting said link-state packet over one of said communication links to said respective destination node, said respective predetermined transmission cost reflecting a particular cost of transmitting data over the associated communication link such that a respective particular cost is subtracted from each packet transmitted by said source node, wherein said predetermined costs are determined prior to receipt of the link-state packet by the source node; and

wherein said source node is configured to determine whether the time-to-live value is greater than said respective predetermined transmission cost for one of said communication links and selectively transmit said link-state packet based on the determination.

2. The system according to claim 1, wherein

each node in said network is configured to use a routing protocol;

and

said transmission cost is assigned to said communication link by said routing protocol.

3. The system according to claim 2, wherein said routing protocol is a no-sight routing protocol.

4. The system according to claim 2, wherein said routing protocol is a hazy-sighted routing protocol.

5. The system according to claim 1, wherein the value of said transmission cost is based at least in part on the bandwidth capacity of said communication link.

6. The system according to claim 1, wherein said transmission cost is computed by a source node in accordance with a predetermined heuristic.

7. The system according to claim 6, wherein the predetermined heuristic is based on parameters of the communication link including at least one of the physical length of the communication link, the bandwidth capacity of the communication link, and the type of medium used to facilitate the communication link.

8. The system according to claim 1, wherein said source node is configured to only transmit said link-state packet over one of communication links with a transmission cost lower than said time-to-live value associated with said link-state packet.

9. A source node in a set of nodes forming a network, comprising:

a transmitting portion configured to transmit a link-state packet over a plurality of communication links in said network;

wherein said source node is configured to subtract a respective predetermined transmission cost associated with each one of said communication links from a time-to-live value associated with said link-state packet prior to transmitting said link-state packet over one of said communication links, said respective predetermined transmission cost reflecting a particular cost of transmitting data over the one of said communication links such that a respective particular cost is subtracted from each packet transmitted by said transmitting portion, wherein said predetermined costs are determined prior to receipt of the link-state packet by the source node; and

wherein said source node is configured to determine whether the time-to-live value is greater than said respective predetermined transmission cost for one of said communication links and selectively transmit said link-state packet based on the determination.

10. The source node according to claim 9, wherein

said source node is configured to use a routing protocol;

and

said transmission cost is assigned to said communication link by said routing protocol.

11. The source node according to claim 10, wherein said routing protocol is a no-sight routing protocol.

12. The source node according to claim 10, wherein said routing protocol is a hazy-sighted routing protocol.

13. The source node according to claim 9, wherein the value of said transmission cost is based at least in part on the bandwidth capacity of said communication link.

14. The source node according to claim 9, wherein said source node is configured to only transmit said link-state packet over one of said communication links with a transmission cost lower than said time-to-live value associated with said link-state packet.

15. A method for transmitting data in a network, comprising:

assigning a respective predetermined transmission cost to each of a plurality of communication links, each of said respective predetermined transmission costs reflecting a particular cost of transmitting data over an associated one of the communication links, wherein said respective predetermined costs are determined prior to receipt of a link-state packet by a node configured to transmit said link-state packet over one of said communication links;

determining whether the time-to-live value is greater than at least one of said respective predetermined transmission costs for at least one of said communication links;

subtracting one of said respective predetermined transmission costs from a time-to-live value associated with said link-state packet; and

selectively transmitting said link-state packet to a destination node within said network over said one of said communication links based on the determination, said one of said communication links corresponding to said one of said respective predetermined transmission costs.

16. The method according to claim 15, further comprising

establishing each node in said network as using a routing protocol;

and

assigning said transmission cost to said communication link by said routing protocol.

17. The method according to claim 16, further comprising establishing said routing protocol as a no-sight routing protocol.

18. The method according to claim 16, further comprising establishing said routing protocol as a hazy-sighted routing protocol.

19. The method according to claim 15, further comprising basing the value of said transmission cost at least in part on the bandwidth capacity of said communication link.

20. The method according to claim 15, further comprising assigning a plurality of different predetermined transmission costs to said one of said plurality of communication links.

21. The method according to claim 20, further comprising establishing said plurality of predetermined transmission costs as corresponding to a plurality of packet types transmitted by a source node in communication with said destination node.

22. The method according to claim 15, further comprising modifying said one of said predetermined transmission costs assigned to said one of said communication links.

23. The method according to claim 15, wherein selectively transmitting said link-state packet includes only transmitting said link-state packet over one of said communication links with a transmission cost lower than said time-to-live value associated with said link-state packet.

24. A method comprising:

providing a plurality of nodes where one of said nodes is a source node and other of said nodes are destination nodes;

establishing a plurality of links between said source node and said destination nodes;

assigning a predetermined transmission cost to each of said plurality of links;

providing a link-state packet configured to be transmitted by said source node to one or more of said destination nodes over said plurality of links;

assigning a time-to-live value to said link-state packet;

subtracting said predetermined transmission cost from said time-to-live value for each of said plurality of links to determine whether the time-to-live value for said link-state packet is greater than said predetermined transmission cost for at least one of said links; and

selectively transmitting said link-state packet to one of said destination nodes via one of said links if the time-to-live value of said link-state packet is greater than said predetermined cost for said one of said links.