Algorithm for time based queuing in network traffic engineering

• US 20020122387A1
• Filed: 10/22/2001
• Published: 09/05/2002
• Est. Priority Date: 03/02/2001
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Ni, Shih-Hsiung
• Granted Patent: US 7,042,843 B2
• Time in Patent Office: Days
• US Class Current: 370/231
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5683 for avoiding head of line blocking
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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/28 in relation to timing considerations
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The present invention provides a method for prioritizing packet flows within a switching network. The method includes the steps of receiving packets at an input port, stamping the packets with an arrival time, and classifying the packet into a flow, wherein the flow is determined based upon at least a class of service of the packet, assigning the packet to a queuing ring according to the flow of the packet, and maintaining a flow ratio pending within the switch based upon the classification of the packet.

Claims

1. A method of prioritizing packet flows within a switch, said method comprising the steps of:

receiving a packet at an input port;

stamping the packet with an arrival time;

classifying the packet into a flow, wherein the flow is determined based upon at least a class of service of the packet;

assigning the packet to a queuing ring according to the flow of the packet; and

maintaining a flow ratio pending within the switch based upon the flow of the packet.

2. The method as recited in claim 1, wherein the flow ratio is based upon a number of voice packets compared to a number of video packets pending within the switch.

3. A switch for prioritizing and routing a packet through a communication system, said switch comprising:

an input port for receiving the packet from an input source;

a time stamp for stamping the packet with an arrival time;

a classification module for determining a flow of the packet, wherein the flow is determined based upon at least a class of service of the packet;

a queuing module for assigning the packet to a queuing ring according to the flow of the packet; and

a flow control module for maintaining a flow ratio pending within the switch based upon the flow of the packet.

4. The switch as recited in claim 3, wherein the flow ratio is based upon a number of voice packets compared to a number of video packets pending within the switch.

5. A switch for prioritizing and routing a packet through a communication system, said switch comprising:

receiving means for receiving a packet at an input port;

stamping means for stamping the packet with an arrival time;

determining means for determining a flow of the packet, wherein the flow is determined based upon at least a class of service of the packet;

queuing means for assigning the packet to a queuing ring according to the flow of the packet; and

maintaining means for maintaining a flow ratio pending within the switch based upon the flow of the packet.

6. The switch as recited in claim 5, wherein the flow ratio is based upon a number of voice packets compared to a number of video packets pending within the switch.

7. A switch for prioritizing and routing a packet through a communication system, said switch comprising:

an input port for receiving a packet from an input source and an output port for transmitting the packet to an output destination;

a queuing module configured to determine a flow of the packet and assign the packet in a queue based upon the flow, wherein the flow is determined based upon at least a class of service of the packet;

a scheduling module configured to schedule the transmission of the packet from the queue within a selected time interval before the transmission of a next outgoing packet;

a flow control module configured to maintain a flow ratio pending within the switch based upon the flow of the packet, and to control a transmission rate of the packet from the output port based upon the flow of the packet;

a conflict determination module configured to determine if a conflict exists when the packet is scheduled to be transmitted from the output port;

a threshold indicator module configured to provide a threshold status based upon the flow ratio; and

a transmission module to transmit the packet from the output port according to the schedule determined by the scheduling module.

8. The switch as recited in claim 7, wherein the flow ratio is based upon a number of voice packets compared to a number of video packets pending within the switch.

9. The switch as recited in claim 8, further comprising:

a conflict resolution module configured to instruct the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to drop from the output port the next outgoing packet of the flow that exceeds the threshold.

10. The switch as recited in claim 8, further comprising:

a conflict resolution module configured to instruct the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to deny entry into the input port of a next incoming packet belonging to a new voice flow or a new video flow.

11. The switch as recited in claim 9, further comprising:

a conflict resolution module configured to instruct the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to select f or transmission the packet from the flow which does not exceed the threshold.

13. The method as recited in claim 12, wherein the flow ratio is based upon a

number of voice packets compared to a number of video packets pending within the switch.

14. The method as recited in claim 13, further comprising the steps:

instructing the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to drop from the output port the next outgoing packet of the flow that exceeds the threshold.

15. The method as recited in claim 13, further comprising the steps:

instructing the scheduling module, if the conflict exists and the flow exceeds the threshold, to deny entry into the input port of a next incoming packet belonging to a new voice or video flow.

16. The method as recited in claim 13, further comprising the steps:

instructing the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to select for transmission the packet from the flow which do not exceed the threshold.

18. The switch as recited in claim 17, wherein the flow ratio is based upon a number of voice packets compared to a number of video packets pending within the switch.

19. The switch as recited in claim 18, further comprising:

instructing means for instructing the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to drop from the output port the next outgoing packet of the flow that exceeds the threshold.

20. The switch as recited in claim 18, further comprising:

instructing means for instructing the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to deny entry into the input port of a next incoming packet belonging to a new voice or video flow.

21. The switch as recited in claim 18, further comprising:

instructing means for instructing the scheduling module, if the conflict exists and the flow ratio exceeds the threshold, to select for transmission the packet from the flows which do not exceed the threshold.

12. A method of prioritizing packet flows, comprising the steps of:

receiving a packet into an input port;

transmitting the packet from an output port;

determining a flow of the packet, wherein the flow is determined based upon at least a class of service of the packet;

assigning the packet to a queue according to the flow of the packet;

scheduling the transmission of the packet from the queue within a selected time interval before the transmission of a next outgoing packet;

maintaining a flow ratio pending within the switch based upon the flow of the packet;

controlling a transmission rate of the packet from the output port based upon the flow of the packet;

determining if a conflict exists when the packet is scheduled to be transmitted from the output port;

providing a threshold status based upon the flow ratio; and

transmitting the packet from the output port within the selected time interval.

17. A switch for prioritizing and routing a packet through a communication system, the switch comprising:

receiving means for receiving a packet into an input port;

transmitting means for transmitting the packet from an output port;

determining means for determining a flow of the packet, wherein the flow is determined based upon at least a class of service of the packet;

assigning means for assigning the packet in a queue according to the flow of the packet;

scheduling means for scheduling the transmission of the packet from the queue within a selected time interval before the transmission of a next outgoing packet;

maintaining means for maintaining a flow ratio pending within the switch;

controlling means for controlling a transmission rate of the packet from the output port based upon the flow of the packet;

determining means for determining if a conflict exists when the packet is scheduled to be transmitted from the output ports;

providing means for providing a threshold status based upon the flow ratio; and

transmitting means for transmitting the packet from the output port within the selected time interval.