Systems and methods for forwarding data units in a communications network

• US 20050050221A1
• Filed: 08/27/2003
• Published: 03/03/2005
• Est. Priority Date: 08/27/2003
• Status: Active Grant

• Current Assignee: Raytheon BBN Technologies Corp. (Rtx Corporation)
• Original Assignee: Raytheon BBN Technologies Corp. (Rtx Corporation)
• Inventors: Redi, Jason Keith, Tasman, Mitchell Paul, Rockwell, Richard Dennis
• Granted Patent: US 7,606,927 B2
• Time in Patent Office: Days
• 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 one or more network interfaces, each of the one or more network interfaces being associated with at least one queue, the method comprising:

identifying one of the one or more network interfaces for transmitting a first data unit;

storing the first data unit in a queue of the at least one queue associated with the identified network interface;

retrieving, for the identified network interface, the first data unit from the queue associated with the identified network interface;

determining one of the one or more network interfaces from which the first data unit is to be transmitted; and

forwarding the data unit to the determined network interface for transmission when the determined network interface is the identified network interface.

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 queue associated with the identified 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 queue of the at least one queue associated with each of the one or more 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 queue of the at least one queue associated with at least one of the one or more network interfaces based on the determined priority.

7. The method of claim 3 wherein, when the first data unit is a multicast data unit, the determining one of the one or more network interfaces includes:

identifying a next node to receive the first data unit from a list of next nodes, and

determining the one of the one or more network interfaces based on the identified next node.

8. The method of claim 7 further comprising:

storing, prior to the forwarding, a copy of the first data unit in the queue associated with the identified network interface when the determined network interface is the identified 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 queue associated with the identified network interface.

11. The method of claim 10 further comprising:

storing the first data unit in a queue of the at least one queue associated with the determined network interface when the determined network interface is different from the identified network interface.

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

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

13. The method of claim 10 further comprising:

discarding the first data unit when the determined network interface is different from the identified network interface.

14. A network device comprising:

one or more queues, each of the one or more queues storing one or more data units;

one or more network interfaces, each of the one or more network interfaces being associated with at least one of the one or more 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,

identify one of the one or more network interfaces for transmitting the first data unit,

store the first data unit in a queue of the at least one queue associated with the identified network interface,

retrieve the first data unit from the queue associated with the identified network interface,

determine one of the one or more network interfaces for transmitting the first data unit, and

forward the first data unit to the determined network interface when the determined network interface corresponds to the identified network interface.

15. The network device of claim 14 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.

16. The network device of claim 15 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 queue associated with the identified network interface based on the determined priority.

17. The network device of claim 15 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 queue of the at least one queue associated with each of the one or more network interfaces based on the determined priority.

18. The network device of claim 15 wherein, when determining the one of the one or more network interfaces, 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

determine the one of the one or more network interfaces based on the identified next node.

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

store the first data unit in the queue associated with the identified network interface when the determined network interface is the identified network interface, and

record a current position in the list of next nodes.

20. The network device of claim 18 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.

21. The network device of claim 14 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 queue associated with the identified network interface.

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

store the first data unit in a queue of the at least one queue associated with the determined network interface when the determined network interface is different from the identified network interface.

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

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

24. The network device of claim 15 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 queue of the at least one queue associated with at least one of the one or more network interfaces based on the determined priority.

25. A system for transmitting data units from a node in a communications network, the node including one or more network interfaces, each of the one or more network interfaces being associated with at least one queue, the system comprising:

means for identifying one of the one or more network interfaces for transmitting a data unit;

means for storing the data unit in a queue of the at least one queue associated with the identified network interface;

means for retrieving, for the identified network interface, the data unit from the queue associated with the identified network interface;

means for separately determining one of the one or more network interfaces from which the data unit is to be transmitted; and

means for sending the data unit to the determined network interface for transmission when the determined network interface corresponds to the identified network interface.

26. 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 one of a group of one or more network interfaces for transmitting a data unit;

storing the data unit in a location corresponding to the first network interface;

retrieving, for the first network interface, the data unit from the location;

identifying, after retrieving the data unit, a second one of the group of one or more network interfaces from which the data unit is to be transmitted; and

forwarding the data unit to the second network interface for transmission when the second network interface corresponds to the first network interface.

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

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

wherein the method further comprises;

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 location associated with at least one of the one or more network interfaces based on the determined priority.

28. A method for transmitting data units from a node that includes one or more network interfaces, comprising:

identifying a first one of the one or more network interfaces from which to transmit a data unit when the data unit is received by the node or generated by the node;

determining a second one of the one or more network interfaces to transmit the data unit when the data unit is ready to be transmitted by the node; and

transmitting the data unit via the second network interface when the second network interface is the same as the first network interface.

29. The method of claim 28 further comprising:

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

storing the data unit in a queue associated with the second network interface when the second network interface is different from the first network interface.

30. The method of claim 28 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 queue associated with each of the one or more network interfaces.

31. The method of claim 28 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.

32. A network device comprising:

one or more network interfaces configured to transmit data units; and

a forwarding module configured to;

identify one of the one or more network,interfaces to transmit a data unit when the data unit is received by the network device or generated by the network device,

determine one of the one or more network interfaces to transmit the data unit when the data unit is ready to be transmitted by the network device, and

forward the data unit to the determined network interface for transmission when the determined network interface is the identified network interface.

33. The network device of claim 32 further comprising:

one or more queues, each of the one or more queues being associated with one of the one or more network interfaces and configured to store data units for the associated network interface.

34. The network device of claim 33 wherein the forwarding module is further configured to:

store the data unit in a queue of the one or more queues associated with the identified network interface, and

store the data unit in a queue of the one or more queues associated with the determined network interface when the determined network interface is not the identified network interface.

35. The network device of claim 33 wherein the forwarding module is further configured to:

store the data unit in a queue of the one or more queues associated with each of the one or more network interfaces, and

transmit the data unit, via each of the one or more network interfaces, to zero or more neighboring nodes.

36. The network device of claim 32 wherein the one or more network interfaces is configured to transmit the data units via a wireless link.

37. The network device of claim 32 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.

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

identifying one of the one or more network interfaces to transmit a data unit when the data unit is received by the node or generated by the node;

determining one of the one or more network interfaces to transmit the data unit when the data unit is ready to be transmitted by the node; and

transmitting the data unit via the determined network interface when the determined network interface corresponds to the identified network interface.

39. A method for storing data units in a node that includes a plurality of queues, each queue in the plurality of queues being associated with a priority and one or more buffers, the method comprising:

determining whether a data unit is locally generated, the data unit being associated with a priority;

determining, when the data unit has been locally generated, whether a number of buffers in use for data units of equal or higher priority exceeds a threshold;

dropping the data unit when the number of buffers in use exceeds the threshold;

determining, when the data unit is not locally generated or the number of buffers in use does not exceed the threshold, if a free buffer exists;

storing, when a free buffer exists, the packet in the free buffer;

selecting a non-empty, lower priority queue when no free buffer exists;

emptying a buffer from the selected lower priority queue; and

storing the data unit in the emptied buffer.

40. The method of claim 39 wherein the threshold is configurable.

41. The method of claim 39 further comprising:

dropping the packet when a non-empty, lower priority queue cannot be selected.

42. The method of claim 39 wherein the buffer from the selected lower priority queue includes a buffer at one of a head or tail of the selected lower priority queue.

43. The method of claim 39 wherein the buffer from the selected lower priority queue includes a random buffer in the selected lower priority queue.

44. A method for processing a multicast data unit in a node that includes one or more network interfaces, each of the one or more network interfaces being associated with at least one queue, comprising:

storing the multicast data unit in a memory;

storing a virtual placeholder in a queue of the at least one queue associated with at least one of the one or more network interfaces;

identifying, when one of the virtual placeholders reaches a head of one of the at least one queue, neighboring nodes to receive the multicast data unit;

identifying, for each identified neighboring node, one network interface of the one or more network interfaces; and

placing a copy of the multicast data unit at a head of a queue of the at least one queue associated with each of the identified one network interfaces.