Variable translucency no-sight routing for ad-hoc networks

• US 9,161,290 B2
• Filed: 03/06/2012
• Issued: 10/13/2015
• Est. Priority Date: 03/25/2004
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation), Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Troxel, Gregory Donald, Ramanathan, Subramanian
• Primary Examiner(s): WONG, XAVIER S
• Application Number:
  US13/413,434
• Publication Number:
  US 20120163230A1
• Time in Patent Office: 1,316 Days
• US Class Current: 1/1
• 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 method comprising:

determining whether a propagation limit of a packet is greater than a predetermined transmission cost assigned to a first link from a first node of a network to a second node of the network, the propagation limit established based at least in part on a node density of the network, the transmission cost assigned to the first link according to an aggregate cost of transmitting data over a route to a destination using the first link;

if the propagation limit is greater than the transmission cost associated with the first link, adjusting the propagation limit of the packet based at least in part on the transmission cost and transmitting the packet over the first link from the first node to the second node;

associating a first bandwidth with the first link; and

determining the transmission cost assigned to the first link based at least in part on the first bandwidth associated with the first link.

2. The method as set forth in claim 1, the transmission cost of the link varies inversely with the first bandwidth associated with the first link.

3. The method as set forth in claim 1, wherein the first link includes at least one of a wireless link, a copper link and a fiber optic link.

4. The method as set forth in claim 1, further comprising:

determining whether the adjusted propagation limit of a packet is greater than a second predetermined transmission cost assigned to a second link, the second link carrying traffic from the second node to a third node of the network, the second transmission cost assigned to the second link according to a cost of transmitting data over the second link; and

if the adjusted propagation limit is greater than the second transmission cost associated with the second link, further adjusting the propagation limit of the packet by the second transmission cost and transmitting the packet over the link from the second node to the third node, thereby providing the packet along a route including the first link and the second link.

5. The method as set forth in claim 4, further comprising:

determining the respective transmission cost of the second link based at least in part on a second bandwidth associated with the second link.

6. The method as set forth in claim 5, wherein a summation of the respective transmission costs includes at least the respective transmission costs of the first link and the second link.

7. The method as set forth in claim 1, further comprising selecting a route over which to provide the packet, the selected route including the first link associated with the first bandwidth, a second link associated with a second bandwidth, and a third link associated with a third bandwidth, the first link, the second link, and the third link each including at least one of a wireless link, a copper link, and a fiber optic link.

8. The method as set forth in claim 7, further comprising:

determining the respective transmission cost of the second link based at least in part on the second bandwidth;

determining the respective transmission cost of the third link based at least in part on the third bandwidth; and

wherein a summation of the respective transmission costs includes at least the respective transmission costs of the first link, the second link, and the third link.

9. The method as set forth in claim 1, further comprising:

identifying a type of the packet to be transmitted by the first node; and

establishing the propagation limit for the packet based at least in part on the identified type of the packet and the node density of the network.

10. The method as set forth in claim 1, further comprising setting a propagation limit for a multicast data packet transmitted from the first node to a higher value than a propagation limit of a multicast member link-state update packet transmitted from the first node.

11. The method as set forth in claim 1, further comprising adjusting the propagation limit of the packet based at least in part on a physical distance that the packet has traveled from an origination node.

12. The method as set forth in claim 1, further comprising adjusting the propagation limit of the packet based at least in part on a physical distance between the nodes.

13. A system comprising:

a plurality of nodes of a network, each configured to receive and transmit packets, wherein a first node of the network is configured to;

determine whether a propagation limit of a packet is greater than a predetermined transmission cost assigned to a link from the first node to a second node of the network, the propagation limit established based at least in part on a node density of the network, the transmission cost assigned to the link according to an aggregate cost of transmitting data over a route to a destination using the link; and

if the propagation limit is greater than the transmission cost associated with the link, adjust the propagation limit of the packet based at least in part on the transmission cost and transmit the packet over the link from the first node to the second node;

wherein the network is configured to

associate a bandwidth with the link; and

determine the transmission cost assigned to the link based at least in part on a bandwidth associated with the link.

14. The system as set forth in claim 13, wherein a second node is configured to associate a second bandwidth with a second link.

15. The system as set forth in claim 14, wherein the first node is configured to determine the transmission cost based at least in part on the first bandwidth and the second node is configured to determine the second transmission cost based at least in part on the second bandwidth.

16. The system as set forth in claim 14, wherein at least one of the link and the second link includes at least one of a wireless link and a physical link.

17. The system as set forth in claim 13, wherein a second node of the network is configured to:

determine whether the adjusted propagation limit of the packet is greater than a second predetermined transmission cost assigned to a second link, the second link carrying traffic from the second node to a third node of the network, the second transmission cost assigned to the second link according to a bandwidth capacity-of the second link; and

if the adjusted propagation limit is greater than the second transmission cost associated with the second link, further adjusting the adjusted propagation limit of the packet by the second transmission cost and transmit the packet over the link from the second node to the third node, thereby providing the packet along a route including the first link and the second link.

18. A method comprising:

assigning a respective transmission cost to each of a plurality of links associated with a route connecting nodes of a network, the respective transmission cost assigned according to an aggregate cost of transmitting data over the route to a destination based on an aggregate bandwidth capacity of the respective links;

establishing, based at least in part on a node density of the network, a propagation limit in a header of a packet to be transmitted by a first node of the network;

determining, by the first node, whether the propagation limit included in the header of the packet is greater than a first predetermined transmission cost assigned to a first link of the plurality of links, the first link being from the first node to a second node of the network; and

if the propagation limit is greater than the transmission cost associated with the first link, reducing the propagation limit of the header of the packet by the first predetermined transmission cost and transmitting the packet over the first link from the first node to the second node.

19. The method as set forth in claim 18, further comprising:

determining, by the second node, whether the reduced propagation limit of the packet is greater than a second predetermined transmission cost assigned to a second link, the second link carrying traffic from the second node to a third node of the network, the second transmission cost assigned to the second link according to a bandwidth capacity of the second link; and

if the reduced propagation limit is greater than the second transmission cost associated with the second link, further reducing the reduced propagation limit of the packet by the second transmission cost and transmitting the packet over the link from the second node to the third node, thereby providing the packet along a route including the first link and the second link.