Packet data queuing and processing

• US 20030103497A1
• Filed: 10/23/2002
• Published: 06/05/2003
• Est. Priority Date: 10/24/2001
• Status: Active Grant

• Current Assignee: Intellectual Ventures II LLC (Intellectual Ventures LLC)
• Original Assignee: IPWireless Inc. (NVIDIA Corporation)
• Inventors: Speight, Timothy James
• Granted Patent: US 7,385,994 B2
• Time in Patent Office: Days
• US Class Current: 370/355
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method of processing queued data packets in a packet data communication system includes allocating a tier of service for substantially each of a plurality of individual packet data queues and determining a total number of data packets that can use an available communication resource. A proportion of a total number of data packets is allocated to a number of the tiers of service to allow individual packet data queues on a number of tiers to share a communication resource. A communication resource is provided to queued packet data users on a tier-by-tier basis, such that the communication resource is made available to substantially all tiers.

Such a technique is considerably easier to implement, it allows better control of resources when throughput rates vary on a per user basis. It is also more applicable when the when the number of allocated resource units per round is small compared to the total number of clients requiring service. Furthermore, the technique reduces the amount of processing required to transfer a number of data packets and is more flexible to changes in the overall number of users served changes.

Claims

1. A method of processing queued data packets in a packet data communication system, the method, comprising the step of:

allocating a tier of service for substantially each of a plurality of individual packet data queues;

wherein the method is characterised by the steps of;

determining a total number of data packets that can use an available communication resource;

allocating a proportion of said total number of data packets to a number of the tiers of service to allow individual packet data queues on a number of tiers to share a communication resource; and

providing said communication resource to queued packet data users on a tier-by-tier basis, such that said communication resource is made available to a substantial number of tiers.

2. The method of processing queued data packets in a packet data communication system according to claim 1, wherein said step of allocating a proportion of a total number of data packets is further characterised by the step of:

providing a commitment that a proportion of an entire communication system bandwidth will be allocated, to users operating on a particular tier.

3. The method of processing queued data packets in a packet data communication system according to claim 1, the method further characterised by the step of:

allocating different weights to each tier of service to provide a differential level of service in the allocation of said communication resource between said tiers.

4. The method of processing queued data packets in a packet data communication system according to claim 1, wherein said step of allocating a proportion of a total number of data packets is performed by using rate allocating service disciplines.

5. The method of processing queued data packets in a packet data communication system according to claim 1, the method further characterised by the step of:

providing a packet data user with an identification code to assist in the tier allocation step, wherein, for example, the identification code provides an identifier for the user and/or an indication of a number of data packets that the user wishes to transfer.

6. The method of processing queued data packets in a packet data communication system according to claim 5, the method further characterised by the steps of:

determining, for substantially each respective tier, that a number of data packets are requested to be processed; and

allocating a proportion of said communication resource to substantially each tier in response to said determination.

7. The method of processing queued data packets in a packet data communication system according to claim 1, the method further characterised by the step of:

placing a user at a tail of an allocated queue, depending on the user'"'"'s tier of service when said user provides data packets for queuing.

8. The method of processing queued data packets in a packet data communication system according to claim 1, the method further characterised by the step of:

allocating data packets to a user at a head of the tier queue;

moving said user at said head of the tier queue to the tail of the queue when the user'"'"'s data packets have been sent; and

moving other users in the queue closer to the head of the queue.

9. The method of processing queued data packets in a packet data communication system according to claim 8, the method further characterised by the step of:

repeating the steps of claim 8 until the total number of packets allocated to the tier is transferred.

10. The method of processing queued data packets in a packet data communication system according to claim 1, the method further characterised by the step of:

determining a tier of service for each user when a packet data session for each user commences.

24. A packet data communication system adapted to facilitate the method of any of claim 1.

25. A storage medium storing processor-implementable instructions for controlling a processor to carry out the method of claim 1.

11. A packet data scheduler queuing data packets in a packet data communication system, the packet data scheduler comprising:

means for allocating a tier of service for substantially each of a plurality of individual packet data queues;

means for determining a total number of data packets that can use an available communication resource;

means, operably coupled to the aforementioned means, for allocating a proportion of said total number of data packets to a number of the tiers of service to allow individual packet data queues on a number of tiers to share a communication resource;

wherein the packet data scheduler is characterised by;

scheduling means to provide said communication resource to queued packet data users on a tier-by-tier basis, such that said resource is made available to substantially all tiers.

12. The packet data scheduler according to claim 11, wherein said means for allocating a proportion of a total number of data packets provides a commitment that a proportion of an entire communication system bandwidth will be allocated to users operating on a particular tier.

13. The packet data scheduler according to claim 11, wherein said means for allocating a proportion of a total number of data packets further allocates different weights to each tier of service to provide a differential level of service in the allocation of said communication resource between said tiers.

14. The packet data scheduler according to claim 11, wherein said means for allocating a proportion of a total number of data packets allocates data packets using rate allocating service disciplines.

15. The packet data scheduler according to claim 11, wherein said means for allocating a proportion of a total number of data packets provides a packet data user with an identification code to assist in the tier allocation step, wherein, for example, the identification code provides an identifier for the user and/or an indication of a number of data packets that the user wishes to transfer.

16. The packet data scheduler according to claim 15, wherein said means for allocating a proportion of a total number of data packets determines, for substantially each respective tier, that a number of data packets are requested to be processed;

and allocates a proportion of said communication resource to substantially each tier in response to said determination.

17. The packet data scheduler according to claim 11, wherein said scheduling means places a user at a tail of the allocated queue, depending on the user'"'"'s tier of service when said user provides data packets for queuing.

18. The packet data scheduler according to claim 11, wherein said scheduling means:

allocates data packets to a user at a head of the tier queue;

moves said user at said head of the tier queue to the tail of the queue when the user'"'"'s data packets have been sent; and

moves other user'"'"'s in the queue closer to the head of the queue.

19. The packet data scheduler according to claim 18, wherein said scheduling means repeats the operation of moving data packets and allocating data packets to a head of a tier queue until the total number of packets allocated to the tier has been transferred.

20. A communication unit comprising the packet data scheduler of claim 11.

21. The communication unit according to claim 20, wherein said communication unit operates as a gateway to and/or from two packet data networks.

22. The communication unit of claim 20, wherein said communication unit is a radio network controller for operation in a third Generation Partnership Project (3GPP) specification for wide-band code-division multiple access (WCDMA) communication system.

23. A packet data communication system comprising the packet data scheduler of claim 11.