Allocating priority levels in a data flow

• US 7,970,888 B2
• Filed: 04/03/2003
• Issued: 06/28/2011
• Est. Priority Date: 10/03/2000
• Status: Expired due to Fees

• Current Assignee: Gos Holdings Limited
• Original Assignee: U4EA Technologies Limited
• Inventors: Lafave, Laura Anne, Vowden, Christopher James, Thompson, Peter William, Holyer, Judith Yvonne, Davies, Neil James
• Primary Examiner(s): Nguyen; Quang N.
• Application Number:
  US10/407,910
• Publication Number:
  US 20040199655A1
• Time in Patent Office: 3,008 Days
• Field of Search: 709/223, 709/247, 370/229, 370/412, 370/252, 370/395.7, 370/395.53, 370/395.62, 370/230, 370/232
• US Class Current: 709/224
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of allocating a priority level in an information flow in a data transmission system including receiving a plurality of data packets and allocating a priority level to each data packet is provided with a controller employing such method. The priority level may be determined in accordance with determining a class of loss of the data packet and a class of service for the data packet. The priority level is also a function of the current load of the information flow. It has been established that the choice for each degree of freedom should preferably be made independently and concurrently. The invention, therefore, provides a method for performing such a composite choice.

Claims

1. A method of allocating a priority level in an information flow in a data transmission system, comprising:

receiving, at a controller, a plurality of data packets;

selectively admitting the data packets to at least one queue; and

allocating, at the controller, a priority level to each of said plurality of data packets by determining a class of loss for the data packet and a class of urgency of service for the data packet, wherein the priority levels are allocated based on;

a function of a current state of said at least one queue to which the data packets are selectively admitted, such that the priority levels are allocated in dependence on the current load of the information flow, and

a probabilistic choice according to the current state of the at least one queue, wherein the at least one queue has a set of predefined states, each predefined state being associated with a probability of a packet being allocated a particular priority level.

2. The method as recited in claim 1 further comprising generating a modified information flow by providing a variable spacing between the data packets.

3. The method as recited in claim 2 wherein the variable spacing between data packets is random.

4. The method as recited in claim 2 wherein the variable spacing between data packets is exponentially distributed.

5. The method as recited in claim 1 wherein a spacing between at least some of the data packets corresponds to a spacing in the information flow.

6. The method as recited in claim 1 wherein there are a plurality of said queues and the method further comprises multiplexing an output of the queues.

7. The method as recited in claim 1 further comprising selectively discarding data packets.

8. The method as recited in claim 1 further comprising allocating a data packet identifier to each data packet and storing each data packet in a sequence.

9. The method as recited in claim 1 further comprising servicing each data packet based on the priority level and outputting each data packet in a sequence.

10. A controller for allocating a priority level in an information flow, comprising:

means for receiving a plurality of data packets;

means for selectively admitting the data packets to at least one queue; and

means for allocating a priority level to each of said plurality of data packets packet including determining a class of loss for the data packet and determining a class of urgency for the data packet, the priority levels being allocated based on;

a function of a current state of said at least one queue to which the data packets are selectively admitted, such that the priority levels are allocated in dependence on the current load of the information flow, and

a probabilistic choice according to the current state of the at least one queue, wherein the at least one queue has a set of predefined states, each predefined state being associated with a probability of a packet being allocated a particular priority level.

11. The controller as recited in claim 10 further comprising means for generating a modified information flow by providing a variable spacing between the data packets.

12. The controller as recited in claim 11 wherein the means for generating a modified information flow is embodied at least in part in a policer/shaper.

13. The controller as recited in claim 11 wherein the means for generating a modified information flow employs one of a random pattern and a pseudo-random pattern.

14. A controller for allocating a priority level in an information flow, comprising:

a policer/shaper configured to receive a plurality of data packets, and configured to allocate a priority level to each of said plurality of data packets including determining a class of loss for the data packet and determining a class of urgency for the data packet; and

a queue memory manager configured to selectively admit the data packets to at least one queue;

wherein the policer/shaper is further configured to allocate the priority levels based on;

a function of a current state of said at least one queue to which the data packets are selectively admitted, such that the priority levels are allocated in dependence on the current load of the information flow, and

a probabilistic choice according to the current state of the at least one queue, wherein the at least one queue has a set of predefined states, each predefined state being associated with a probability of a packet being allocated a particular priority level.

15. The controller as recited in claim 14 wherein the policer/shaper is configured to generate a modified information flow by employing a variable spacing between the data packets.

16. The controller as recited in claim 15 wherein the policer/shaper employs one of a random pattern and a pseudo-random pattern.

17. The controller as recited in claim 14 wherein the controller is configured to generate a plurality of information flows, the controller including a cherish/urgency multiplexer for multiplexing the information flows into a cascaded arrangement.