Communication scheduling of network nodes using fair access and weighting techniques

• US 7,801,153 B2
• Filed: 11/30/2007
• Issued: 09/21/2010
• Est. Priority Date: 10/01/2007
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: POWERWAVE COGNITION, INC.
• Inventors: Hughes, Timothy J., Anderson, Arthur E., Kishaba, Wendell Y.
• Primary Examiner(s): Shah, Chirag G
• Assistant Examiner(s): PERSAUD, AMARNAUTH G
• Application Number:
  US11/947,928
• Publication Number:
  US 20090086752A1
• Time in Patent Office: 1,026 Days
• Field of Search: None
• US Class Current: 370/395.4
• 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 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/535 based on resource usage policies

Abstract

In one aspect, a method to schedule network communications in a network having nodes connected by links includes sending a bandwidth value of a first node for each link connected to the first node to neighbors of the first node, receiving bandwidth values from the neighbors of the first node; and determining node weight values of the first node and the neighbors of the first node based on the bandwidth values received from the neighbors of the first node and the bandwidth value of the first node. The method also includes sending the node weight values of the first node to the neighbors of the first node, receiving the node weight values from the neighbors of the first node, determining access values for each node based on a fair access technique and determining network scheduling based on the access values and the node weight values.

Claims

1. A method to schedule network communications in a network having nodes connected by links comprising:

sending a bandwidth value of a first node for each link connected to the first node to neighbors of the first node, the bandwidth value associated with a number of packets in one or more outbound queues of the first node;

receiving bandwidth values from the neighbors of the first node;

determining a node weight value of the first node based on a ratio of the bandwidth value of the first node to the bandwidth values from the neighbors of the first node;

sending the node weight value of the first node to the neighbors of the first node;

receiving node weight values from the neighbors of the first node;

determining access values for each node based on a fair access technique; and

determining a network scheduling for one or more of the first node and the neighbors of the first node based on the access values biased according to the node weight value of the first node and the node weight values from the neighbors of the first node.

2. The method of claim 1 wherein sending a bandwidth value of a first node for each link connected to the first node to neighbors of the first node comprises sending a bandwidth value of a first node for each link connected to the first node to one-hop neighbors of the first node.

3. The method of claim 2 wherein receiving bandwidth values from the neighbors comprises receiving bandwidth values for two-hop neighbors of the first node from the one-hop neighbors.

4. The method of claim 1 wherein determining access values for each node based on a fair access technique comprises determining random values for each two-hop neighbor of the first node using a Node Activation Multiple Access (NAMA) technique.

5. The method of claim 1 wherein sending a bandwidth value of a first node for each link connected to the first node to neighbors of the first node comprises sending a bandwidth value of a first node during a control timeslot.

6. The method of claim 5, further comprising sending a counter value with the bandwidth value during the control timeslot.

7. The method of claim 6, further comprising using the bandwidth value for network scheduling when the counter value is equal to a predetermined value.

8. An apparatus to schedule communications in a network having nodes connected by links, comprising circuitry to:

send a bandwidth value of a first node for each link connected to the first node to neighbors of the first node, the bandwidth value associated with a number of packets in one or more outbound queues of the first node;

receive bandwidth values from the neighbors of the first node;

determine a node weight value of the first node based on a ratio of the bandwidth value of the first node to the bandwidth values from the neighbors of the first node;

send the node weight value of the first node to the neighbors of the first node;

receive node weight values from the neighbors of the first node;

determine access values for each node based on a fair access technique; and

determine a network scheduling for one or more of the first node and the neighbors of the first node based on the access values biased according to the node weight value of the first node and the node weight values from the neighbors of the first node.

9. The apparatus of claim 8 wherein the circuitry comprises at least one of a processor, a memory, programmable logic and logic gates.

10. The apparatus of claim 8 wherein circuitry to send a bandwidth value of a first node for each link connected to the first node to neighbors of the first node comprises circuitry to send a bandwidth value of a first node for each link connected to the first node to one-hop neighbors of the first node.

11. The apparatus of claim 10 wherein circuitry to receive bandwidth values from the neighbors comprises circuitry to receive bandwidth values for two-hop neighbors of the first node from the one-hop neighbors.

12. The apparatus of claim 8 wherein circuitry to determine access values for each node based on a fair access technique comprises circuitry to determine random values for each two-hop neighbor of the first node using a Node Activation Multiple Access (NAMA) technique.

13. The apparatus of claim 8 wherein circuitry to send a bandwidth value of a first node for each link connected to the first node to neighbors of the first node comprises circuitry to send a bandwidth value of a first node during a control timeslot.

14. The apparatus of claim 13, further comprising circuitry to send a counter value with the bandwidth value during the control timeslot.

15. The apparatus of claim 14, further comprising circuitry to use the bandwidth value for network scheduling when the counter value is equal to a predetermined value.

16. An article comprising a non-transitory machine-readable medium that stores executable instructions to schedule communications in a network having nodes connected by links, the instructions causing a machine to:

send a bandwidth value of a first node for each link connected to the first node to neighbors of the first node, the bandwidth value associated with a number of packets in one or more outbound queues of the first node;

receive bandwidth values from the neighbors of the first node;

determine a node weight value of the first node based on a ratio of the bandwidth value of the first node to the bandwidth values from the neighbors of the first node;

send the node weight value of the first node to the neighbors of the first node;

receive node weight values from the neighbors of the first node;

determine access values for each node based on a fair access technique; and

determine a network scheduling for one or more of the first node and the neighbors of the first node based on the access values and biased according to the node weight value of the first node and the node weight values from the neighbors of the first node.

17. The article of claim 16 wherein instructions causing a machine to send a bandwidth value of a first node for each link connected to the first node to neighbors of the first node comprises instructions causing a machine to send a bandwidth value of a first node for each link connected to the first node to one-hop neighbors of the first node.

18. The article of claim 17 wherein instructions causing a machine to receive bandwidth values from the neighbors comprises instructions causing a machine to receive bandwidth values for two-hop neighbors of the first node from the one-hop neighbors.

19. The article of claim 16 wherein instructions causing a machine to determine access values for each node based on a fair access technique comprises instructions causing a machine to determine random values for each two-hop neighbor of the first node using a Node Activation Multiple Access (NAMA) technique.

20. The article of claim 16 wherein instructions causing a machine to send a bandwidth value of a first node for each link connected to the first node to neighbors of the first node comprises instructions causing a machine to send a bandwidth value of a first node during a control timeslot.

21. The article of claim 20, further comprising instructions causing a machine to send a counter value with the bandwidth value during the control timeslot.

22. The article of claim 21, further comprising instructions causing a machine to use the bandwidth value for network scheduling when the counter value is equal to a predetermined value.