Apparatus and methods for scheduling packets in a broadband data stream
View Patent ↗A packet scheduler includes a packet manager interface, a policer, a congestion manager, a scheduler, and a virtual output queue (VOQ) handler. The policer assigns a priority to each packet. Depending on congestion levels, the congestion manager determines whether to send a packet based on the packet's priority assigned by the policer. The scheduler schedules packets in accordance with configured rates for virtual connections and group shapers. A scheduled packet is queued at a virtual output queue (VOQ) by the VOQ handler. In one embodiment, the VOQ handler sends signals to a packet manager (through the packet manager interface) to instruct the packet manager to transmit packets in a scheduled order.
1. A method for managing congestion of packets in a data stream, comprising:
determining a set of congestion regions by compliance levels, said compliance levels indicating a hierarchy of compliance, compliance being conformance of incoming traffic with a specified data rate;
receiving a packet in a queue, said packet having an assigned compliance identifier indicating compliance based on an arrival time of the packet, a theoretical arrival time based on the specified data rate, and a packet delay variation tolerance of the packet;
determining an instantaneous queue size of said queue;
comparing said instantaneous queue size to said set of congestion regions; and
passing said packet based on said comparing and said assigned compliance identifier.
2. The method of claim 1 , further comprising:
calculating a percentage in a congestion region;
generating a random number;
comparing said percentage to said random number; and
dropping said packet if said percentage is greater than said random number.
3. The method of claim 1 , further comprising:
passing all packets when said instantaneous queue size is smaller than a lowest compliance congestion region.
4. The method of claim 3 , wherein said lowest compliance congestion region is a passing region.
5. The method of claim 1 , further comprising:
dropping all packets when said instantaneous queue size is larger than or equal to a highest compliance congestion region.
6. The method of claim 5 , wherein said highest compliance congestion region is a dropping region.
7. The method of claim 1 , wherein said compliance levels are determined based on compliance per virtual circuit, per port and per priority for each packet.
8. The method of claim 1 , further comprising:
receiving unused memory space information regarding a chip; and
managing congestion level of said chip based on said unused memory space information; said managing including allocating a portion of said unused memory space to each traffic priority.
9. A computer readable medium encoded with a computer program for managing congestion of packets in a data stream, the computer program comprising:
logic code for determining a set of congestion regions by compliance levels, said compliance levels indicating a hierarchy of compliance, compliance being conformance of incoming traffic with a specified data rate;
logic code for receiving a packet in a queue, said packet having an assigned compliance identifier indicating compliance based on an arrival time of the packet, a theoretical arrival time based on the specified data rate, and a packet delay variation tolerance of the packet;
logic code for determining an instantaneous queue size of said queue;
logic code for comparing said instantaneous queue size to said set of congestion regions; and
logic code for passing said packet based on said comparing and said assigned compliance identifier.
10. The computer readable medium of claim 9 , wherein the computer program further comprises:
logic code for calculating a percentage in a congestion region;
logic code for generating a random number;
logic code for comparing said percentage to said random number; and
logic code for dropping said packet if said percentage is greater than said random number.
11. The computer readable medium of claim 9 , wherein the computer program further comprises:
logic code for passing all packets when said instantaneous queue size is smaller than a lowest compliance congestion region.
12. The computer readable medium of claim 11 , wherein said lowest compliance congestion region is a passing region.
13. The computer readable medium of claim 9 , wherein the computer program further comprises:
logic code for dropping all packets when said instantaneous queue size is larger than or equal to a highest compliance congestion region.
14. The computer readable medium of claim 13 , wherein said highest compliance congestion region is a dropping region.
15. The computer readable medium of claim 9 , wherein said compliance levels are determined based on compliance per virtual circuit, per port and per priority for each packet.
16. The computer readable medium of claim 9 , wherein the computer program further comprises:
logic code for receiving unused memory space information regarding a chip; and
logic code for managing congestion level of said chip based on said unused memory space information; said logic code for managing including logic code for allocating a portion of said unused memory space to each traffic priority.
17. A system for managing congestion of packets in a data stream, comprising:
means for determining a set of congestion regions by compliance levels, said compliance levels indicating a hierarchy of compliance, compliance being conformance of incoming traffic with a specified data rate;
means for receiving a packet in a queue, said packet having an assigned compliance identifier indicating compliance based on an arrival time of the packet, a theoretical arrival time based on the specified data rate, and a packet delay variation tolerance of the packet;
means for determining an instantaneous queue size of said queue;
means for comparing said instantaneous queue size to said set of congestion regions; and
means for passing said packet based on said comparing step and said assigned compliance identifier.
18. The system of claim 17 , further comprising:
means for calculating a percentage in a congestion region;
means for generating a random number;
means for comparing said percentage to said random number; and
means for dropping said packet if said percentage is greater than said random number.
19. The system of claim 17 , further comprising:
means for passing all packets when said instantaneous queue size is smaller than a lowest compliance congestion region.
20. The system of claim 17 , further comprising:
means for dropping all packets when said instantaneous queue size is larger than or equal to a highest compliance congestion region.