Proportionally fair-share time slot reservations with a fast increase, slow decrease rate controller

• US 7,957,410 B2
• Filed: 12/10/2008
• Issued: 06/07/2011
• Est. Priority Date: 12/10/2008
• Status: Expired due to Fees

• Current Assignee: Majandro LLC (IP Edge LLC)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Solis, Ignacio, Mosko, Marc E.
• Primary Examiner(s): Rao; Seema
• Assistant Examiner(s): Wu; Jianye
• Application Number:
  US12/331,823
• Publication Number:
  US 20100142551A1
• Time in Patent Office: 909 Days
• Field of Search: None
• US Class Current: 370/461
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 74/0833 Random access procedures, e.g. with 4-step access

Abstract

One embodiment of the present invention provides a system for facilitating proportionally fair-share time slot reservations with a fast increase, slow decrease rate controller in an ad hoc dynamic wireless broadcast network. During operation, the system determines local time slot demand, based on transmitted and queued data corresponding to one or more previous decision points. Next, the system broadcasts the local time slot demand to one or more neighbors. The system also determines neighbor time slot demands, where a respective neighbor time slot demand indicates a particular neighbor'"'"'s local time slot demand corresponding to one or more previous decision points. Next, the system determines neighborhood time slot demand, based on the local time slot demand and the neighbor time slot demands. Next, the system determines allowable reserved time slots based on the local time slot demand and allowable reserved time slots corresponding to one or more previous decision points.

Claims

1. A computer-executed method for facilitating proportionally fair-share time slot reservations at a decision point at a node, comprising:

determining local time slot demand, based on transmitted and queued data corresponding to one or more previous decision points;

broadcasting the local time slot demand to one or more neighbors;

determining neighbor time slot demands, wherein a respective neighbor time slot demand indicates a particular neighbor'"'"'s local time slot demand corresponding to one or more previous decision points;

determining neighborhood time slot demand, based on the local time slot demand and the neighbor time slot demands;

determining a proportionally fair-share time slot assignment based on the neighborhood time slot demands, which involves determining a difference between a first time slot demand and a second time slot demand using a fast-increase and slow-decrease principle, wherein the second time slot is next to the first time slot;

determining allowable reserved time slots, based on the local time slot demand and allowable reserved time slots corresponding to one or more previous decision points; and

producing a result which indicates the allowable reserved time slots.

2. The method of claim 1, wherein determining local time slot demand further comprises:

determining a weighted byte demand corresponding to a previous decision point, based on transmitted and queued data;

determining an exponentially weighted moving average byte demand, based on the weighted byte demand and exponentially weighted moving average byte demands corresponding to one or more previous decision points; and

determining broadcast bandwidth and a maximum reservable time slots per frame.

3. The method of claim 2, wherein determining the weighted byte demand comprises determining a weighted sum of one or more traffic priorities of the transmitted and queued data corresponding to a previous decision point.

4. The method of claim 1, wherein broadcasting the local time slot demand to one or more neighbors comprises encoding the local time slot demand into a load representing a fixed number of bits.

5. The method of claim 1, wherein determining neighbor time slot demands comprises determining that each respective neighbor is within a specific distance from the node, wherein the specific distance can be increased based on a timer.

6. The method of claim 1, wherein determining neighborhood time slot demand comprises determining a weighted sum of the local time slot demand and the neighbor time slot demands.

7. The method of claim 1, wherein determining the proportionally fair-share time slot assignment comprises:

determining a ratio between the local time slot demand and the neighborhood time slot demand; and

determining a maximum reservable time slots per frame.

8. The method of claim 1, wherein determining allowable reserved time slots comprises:

determining a differential between the proportionally fair-share time slot assignment and a weighted sum of the allowable reserved time slots corresponding to one or more previous decision points;

determining a change factor based on the differential;

determining an allowable change based on the differential and the change factor; and

determining allowable reserved time slots based on a weighted sum of the allowable change and the allowable reserved time slots corresponding to one or more previous decision points.

9. An apparatus for facilitating proportionally fair-share time slot reservations at a decision point at a node, comprising:

a local-time slot-demand-determining mechanism configured to determine local time slot demand, based on transmitted and queued data corresponding to one or more previous decision points;

a broadcasting mechanism configured to broadcast the local time slot demand to one or more neighbors;

a neighbor-time-slot-demand-determining mechanism configured to determine neighbor time slot demands, wherein a respective neighbor time slot demand indicates a particular neighbor'"'"'s local time slot demand corresponding to one or more previous decision points;

a neighborhood-time slot-demand-determining mechanism configured to determine a neighborhood time slot demand based on the local time slot demand and the neighbor time slot demands;

a proportionally fair-share time slot-assignment-determining mechanism configured to determine a proportionally fair-share time slot assignment based on the neighborhood time slot demands, which involves determining a difference between a first time slot demand and a second time slot demand using a fast-increase and slow-decrease principle, wherein the second time slot is next to the first time slot;

an allowable-reserved-time slot-determining mechanism configured to determine allowable reserved time slots, based on the local time slot demand and allowable reserved time slots corresponding to one or more previous decision points; and

a result-producing mechanism configured to produce a result which indicates the allowable reserved time slots.

10. The apparatus of claim 9, wherein the local-time slot demand-determining mechanism comprises:

a weighted-byte-demand-determining mechanism configured to determine a weighted byte demand, based on transmitted and queued data corresponding to a previous decision point;

an exponentially-weighted-moving-average-byte-demand-determining mechanism configured to determine an exponentially weighted moving average byte demand based on the weighted byte demand and exponentially weighted moving averages corresponding to one or more previous decision points; and

a bandwidth-and-reservation-determining mechanism configured to determine broadcast bandwidth and a maximum reservable time slots per frame.

11. The apparatus of claim 10, wherein while determining the weighted-byte demand, the weighted-byte-demand-determining mechanism comprises a weighted-sum-determining mechanism configured to determine a weighted sum of one or more traffic priorities of the transmitted and queued data corresponding to a previous decision point.

12. The apparatus of claim 9, wherein while broadcasting the local time slot demand, the broadcasting mechanism comprises an encoding mechanism configured to encode the local time slot demand into a load representing a fixed number of bits.

13. The apparatus of claim 9, wherein while determining the neighbor time slot demand, the neighbor-time-slot-demand-determination mechanism comprises a distance-determining mechanism configured to determine that each respective neighbor is within a specific distance from the node, wherein the specific distance can be increased based on a timer.

14. The apparatus of claim 9, wherein while determining the neighborhood time slot demand, the neighborhood-time-slot-demand determining mechanism comprises a weighted-sum determination mechanism configured to determine a weighted sum of the local time slot demand and the neighbor time slot demands.

15. The apparatus of claim 9, while determining the proportionally fair-share time slot assignment, the proportionally fair-share time-slot-assignment-determining mechanism comprises:

a ratio-determining mechanism configured to determine a ratio between the local time slot demand and the neighborhood time slot demand; and

a maximum-reservable-time-slot determining mechanism configured to determine a maximum reservable time slots per frame.

16. The apparatus of claim 9, wherein while determining the allowable reserved time slots, the allowable-reserved-time-slots-determining mechanism comprises:

a differential-determining mechanism configured to determine a differential between the proportionally fair-share time slot assignment and a weighted sum of the allowable reserved time slots corresponding to one or more previous decision points;

a change-factor-determining mechanism configured to determine a change factor based on the differential;

an allowable-change-determining mechanism configured to determine an allowable change based on the differential and the change factor; and

an allowable-reserved-time-slot determining mechanism configured to determine allowable reserved time slots based on a weighted sum of the allowable change and the allowable reserved time slots corresponding to one or more previous decision points.

17. A non-transitory computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for facilitating proportionally fair-share time slot reservations at a decision point at a node, the method comprising:

determining local time slot demand, based on transmitted and queued data corresponding to one or more previous decision points;

broadcasting the local time slot demand to one or more neighbors;

determining neighbor time slot demands, wherein a respective neighbor time slot demand indicates a particular neighbor'"'"'s local time slot demand corresponding to one or more previous decision points;

determining neighborhood time slot demand based on the local time slot demand and the neighbor time slot demands;

determining a proportionally fair-share time slot assignment based on the neighborhood time slot demands, which involves determining a difference between a first time slot demand and a second time slot demand using a fast-increase and slow-decrease principle, wherein the second time slot is next to the first time slot;

determining allowable reserved time slots, based on the local time slot demand and allowable reserved time slots corresponding to one or more previous decision points; and

producing a result which indicates the allowable reserved time slots.

18. The storage device of claim 17, wherein determining local time slot demand further comprises:

determining a weighted byte demand, based on transmitted and queued data corresponding to a previous decision point;

determining an exponentially weighted moving average byte demand, based on the weighted byte demand and exponentially weighted moving average byte demands corresponding to one or more previous decision points; and

determining broadcast bandwidth and a maximum reservable time slots per frame.

19. The storage device of claim 18, wherein determining a weighted byte demand comprises determining a weighted sum of one or more traffic priorities of the transmitted and queued data corresponding to a previous decision point.

20. The storage device of claim 17, wherein broadcasting the local time slot demand to one or more neighbors comprises encoding the local time slot demand into a load representing a fixed number of bits.

21. The storage device of claim 17, wherein determining neighbor time slot demands comprises determining that each respective neighbor is within a specific distance from the node, wherein the specific distance can be increased based on a timer.

22. The storage device of claim 17, wherein determining neighborhood time slot demand comprises determining a weighted sum of the local time slot demand and the neighbor time slot demands.

23. The storage device of claim 17, wherein determining the proportionally fair-share time slot assignment comprises:

determining a ratio between the local time slot demand and the neighborhood time slot demand; and

determining a maximum reservable time slots per frame.

24. The storage device of claim 17 wherein determining allowable reserved time slots comprises:

determining a differential between the proportionally fair-share time slot assignment and a weighted sum of the allowable reserved time slots corresponding to one or more previous decision points;

determining a change factor based on the differential;

determining an allowable change based on the differential and the change factor; and

determining allowable reserved time slots based on a weighted sum of the allowable change and the allowable reserved time slots corresponding to one or more previous decision points.