Systems and methods for forwarding data units in a communications network

• US 7,606,927 B2
• Filed: 08/27/2003
• Issued: 10/20/2009
• Est. Priority Date: 08/27/2003
• Status: Active Grant

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: BBN Technologies (Rtx Corporation)
• Inventors: Redi, Jason Keith, Tasman, Mitchell Paul, Rockwell, Richard Dennis
• Primary Examiner(s): BOUTAH, ALINA A
• Application Number:
  US10/649,030
• Publication Number:
  US 20050050221A1
• Time in Patent Office: 2,246 Days
• Field of Search: 709/232, 709/238, 709/250, 370/389
• US Class Current: 709/232
• CPC Class Codes: H04W 52/46 in multi hop networks, e.g. wireless relay networks

Abstract

A network device (110) includes a forwarding module (230) and one or more network interfaces (240) that may be configured to transmit data units. The forwarding module (230) may be configured to identify one of the network interfaces (240) to transmit a data unit when the data unit is received by the network device (110) or generated by the network device (110), determine one of the network interfaces (240) to transmit the data unit when the data unit is ready to be transmitted by the network device (110), and forward the data unit to the determined network interface (240) for network when the determined network interface (240) is the identified network interface (240).

Claims

1. A method for transmitting data units from a node in a communications network, the node including a plurality of network interfaces, the plurality of network interfaces being associated with respective transmission queues, the method comprising:

identifying a first network interface of the plurality of network interfaces of the node for transmitting a first data unit;

subsequent to identifying the first network interface, storing the first data unit in a transmission queue associated with the first network interface;

subsequent to storing the first data unit in the transmission queue associated with the first network interface, identifying a second network interface of the plurality of network interfaces of the node from which the first data unit is to be transmitted;

determining if the second network interface is different than the first network interface; and

in response to determining that the second network interface is different from the first network interface, forwarding the data unit to the second network interface for transmission.

2. The method of claim 1 wherein the communications network is an ad hoc network.

3. The method of claim 1 further comprising:

determining, prior to storing the first data unit, whether the first data unit is a multicast data unit.

4. The method of claim 3 further comprising:

determining, when the first data unit is not a multicast data unit, a priority for the first data unit; and

storing the first data unit in a sub-queue within the transmission queue associated with the first network interface based on the determined priority.

5. The method of claim 3 further comprising:

determining, when the first data unit is a multicast data unit, a priority for the first data unit; and

storing the first data unit in a sub-queue within a transmission queue associated with each of the plurality of network interfaces based on the determined priority.

6. The method of claim 3 further comprising:

determining, when the first data unit is a multicast data unit, a priority for the first data unit; and

storing the first data unit in a sub-queue within a transmission queue associated with at least one of the plurality of network interfaces based on the determined priority.

7. The method of claim 3 wherein, when the first data unit is a multicast data unit, identifying the second network interface includes:

identifying a next node to receive the first data unit from a list of next nodes, and identifying the second network interface based on the identified next node.

8. The method of claim 7, wherein in response to determining that the first network interface is the same as the second network interface, storing a copy of the first data unit in the transmission queue associated with the second network interface, and recording a current position in the list of next nodes.

9. The method of claim 7 further comprising:

dropping the first data unit when no next node is identified from the list of next nodes.

10. The method of claim 1 further comprising:

assigning a sequence number to the first data unit, and wherein the storing the first data unit includes;

storing the sequence number with the first data unit in the transmission queue associated with the first network interface.

11. The method of claim 10 further comprising:

in response to determining that the first network interface is different than the second network interface, storing the first data unit in a transmission queue associated with the second network interface.

12. The method of claim 11 wherein the storing the first data unit in the transmission queue associated with the second transmission interface includes:

storing the first data unit in the transmission queue associated with the second transmission interface based on the sequence number assigned to the first data unit.

13. A network device comprising:

a plurality of transmission queues for storing data units;

a plurality of network interfaces associated with respective transmission queues and being configured to forward the one or more data units to other network devices; and

a forwarding module configured to;

receive a first data unit at the network device,

identify a first network interface of the plurality of network interfaces of the network device for transmitting the first data unit,

subsequent to identifying the first network interface, store the first data unit in a transmission queue associated with the first network interface,

subsequent to storing the first data unit in the transmission queue, identify a second network interface of the plurality of network interfaces of the network device for transmitting the first data unit,

determining if the second network interface is different than the first network interface, and

in response to determining that the first network interface is different from the second network interface, forward the first data unit to the second network interface.

14. The network device of claim 13 wherein the forwarding module is further configured to:

determine, prior to storing the first data unit, whether the first data unit is a multicast data unit.

15. The network device of claim 14 wherein the forwarding module is further configured to:

determine, when the first data unit is not a multicast data unit, a priority for the first data unit, and store the first data unit in a sub-queue within the transmission queue associated with the first network interface based on the determined priority.

16. The network device of claim 14 wherein the forwarding module is further configured to:

determine, when the first data unit is a multicast data unit, a priority for the first data unit; and

store the first data unit in a sub-queue within a transmission queue associated with each of the plurality of network interfaces based on the determined priority.

17. The network device of claim 14 wherein, when identifying the second network interface, the forwarding module is, when the first data unit is a multicast data unit, further configured to:

identify a next node to receive the first data unit from a list of next nodes, and identify the second network interface based on the identified next node.

18. The network device of claim 17 wherein the forwarding module is further configured to, in response to determining that the first network interface is the same as the second network interface, store the first data unit in the transmission queue associated with the second network interface, and record a current position in the list of next nodes.

19. The network device of claim 17 wherein the forwarding module is further configured to:

discard the first data unit when no next node is identified in the list of next nodes.

20. The network device of claim 13 wherein the forwarding module is further configured to:

assign a sequence number to the first data unit, and wherein, when storing the first data unit, the forwarding module is configured to;

store the sequence number with the first data unit in the transmission queue associated with the first network interface.

21. The network device of claim 20 wherein the forwarding module is further configured to:

in response to determining that the first network interface is different than the second network interface, store the first data unit in a transmission queue associated with the second network interface.

22. The network device of claim 21 wherein, when storing the first data unit in the transmission queue associated with the second network interface, the forwarding module is configured to:

store the first data unit in the transmission queue associated with the second network interface based on the sequence number assigned to the first data unit.

23. The network device of claim 14 wherein the forwarding module is further configured to:

determine, when the first data unit is a multicast data unit, a priority for the first data unit, and store the first data unit in a sub-queue within a transmission queue associated with at least one of the plurality of network interfaces based on the determined priority.

24. The network device of claim 13, wherein the second network interface transmits the data unit over an ad hoc network.

25. A system for transmitting data units from a node in a communications network, the node including a plurality of network interfaces, the plurality network interfaces being associated with respective transmission queues, the system comprising:

means for identifying a first network interface of the node for transmitting a data unit;

means for, subsequent to identifying the first network interface, storing the data unit in an transmission queue associated with the first network interface;

means for separately identifying, subsequent to storing the data unit in the transmission queue, a second network interface of the node from which the data unit is to be transmitted;

means for determining if the second network interface is different than the first network interface; and

means for, in response to determining that the first network interface is different from the second interface, sending the data unit to the second network interface for transmission.

26. The system of claim 25, wherein the second network interface transmits the data unit over an ad hoc network.

27. A computer-readable medium containing a plurality of instructions that, when executed by at least one processor, causes the at least one processor to perform a method for transmitting data units in a communications network, the method comprising:

identifying a first network interface of a plurality of network interfaces of the node for transmitting a data unit;

subsequent to identifying the first network interface, storing the data unit in a transmission location corresponding to the first network interface;

identifying, after storing the data unit, a second network interface of the plurality of network interfaces of the node from which the data unit is to be transmitted; and

determining if the second network interface is different than the first network interface;

in response to determining that the first network interface is different than the second network interface, forwarding the data unit to the second network interface for transmission.

28. The computer-readable medium of claim 27 further comprising:

determining whether the data unit is a multicast data unit, and wherein the method further comprises;

determining, when the data unit is a multicast data unit, a priority for the data unit, and store the data unit in an transmission location associated with at least one of the plurality of network interfaces based on the determined priority.

29. The computer readable medium of claim 27, wherein the second network interface transmits the data unit over an ad hoc network.

30. A method for transmitting data units from a node that includes a plurality of network interfaces, comprising:

upon one of receipt of a data unit by the node and generation of a data unit by the node, identifying a first network interface of the plurality of network interfaces of the node from which to transmit the data unit to another node;

determining that the node is ready to transmit the data unit;

subsequent to identifying the first network interface, and in response to determining that the node is ready to transmit the data unit, identifying a second network interface of the plurality of network interfaces of the node to transmit the data unit;

determining if the second network interface is different than the first network interface; and

in response to determining that the first network interface is different than the second network interface, transmitting the data unit via the second network interface.

31. The method of claim 30 further comprising:

storing the data unit in an transmission queue associated with the first network interface; and

subsequent to identifying the second network interface, storing the data unit in a transmission queue associated with the second network interface.

32. The method of claim 30 further comprising:

determining whether the data unit is a multicast data unit; and

storing, when the data unit is a multicast data unit, the data unit in a transmission queue associated with each of the plurality of network interfaces.

33. The method of claim 30 wherein the data unit is a multicast data unit, and wherein the method further comprises:

storing, for each neighboring node, information indicating whether the multicast data unit has been transmitted to that neighboring node.

34. The method of claim 30, wherein the second network interface transmits the data unit over an ad hoc network.

35. A network device comprising:

a plurality of network interfaces configured to transmit data units; and

a forwarding module configured to;

upon one of receipt of a data unit by the network device and generation of a data unit by the network device, identify a first network interface of the plurality of network interfaces of the network device to transmit the data unit to another network device,

determine that the network device is ready to transmit the data unit;

determine, subsequent to identifying the first network interface and in response to determining that the network device is ready to transmit the data unit, a second network interface of the plurality of network interfaces of the network device to transmit the data unit, and

determine if the second network interface is different than the first network interface;

in response to determining that the first network interface is different than the second network interface, forward the data unit to the second network interface for transmission.

36. The network device of claim 35 further comprising:

a plurality of transmission queues associated with respective network interfaces of the plurality of network interfaces and configured to store data units for the associated respective network interfaces.

37. The network device of claim 36 wherein the forwarding module is further configured to:

store the data unit in a transmission queue associated with the first network interface, and subsequent to forwarding the data to the second network interface, store the data unit in a transmission queue associated with the second network interface.

38. The network device of claim 35 wherein the plurality of network interfaces are configured to transmit the data units via a wireless link.

39. The network device of claim 35 wherein the data unit is a multicast data unit, and wherein the forwarding module is further configured to:

store, for each neighboring node, information indicating whether the multicast data unit has been transmitted to that neighboring node.

40. The network device of claim 35, wherein the second network interface transmits the data unit over an ad hoc network.

41. A computer-readable medium containing a plurality of instructions that, when executed by at least one processor in a node that includes a plurality of network interfaces, causes the at least one processor to perform a method for transmitting data units in a communications network, the method comprising:

upon one of receipt of a data unit by the node and generation of a data unit by the node, identifying a first network interface of the plurality of network interfaces of the node to transmit the data unit to another node;

determining that the node is ready to transmit the data unit;

subsequent to identifying the first network interface and in response to determining that the node is ready to transmit the data unit, determining a second network interface of the plurality of network interfaces of the node to transmit the data unit;

determining if the second network interface is different than the first network interface; and

in response to determining that the first network interface is different from the second network interface, transmitting the data unit via the second network interface.

42. The computer readable medium of claim 41, wherein the second network interface transmits the data unit over an ad hoc network.