Multiple-criteria queueing and transmission scheduling system for multimedia networks

• US 6,188,698 B1
• Filed: 01/26/1998
• Issued: 02/13/2001
• Est. Priority Date: 12/31/1997
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Fichou, Aline, Galand, Claude, Munier, Jean-Marie, Berthaud, Jean-Marc, Foriel, Pierre-Andre, Enger, Marcus, Spagnol, Victor
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): PHAN, MAN U
• Application Number:
  US09/013,701
• Time in Patent Office: 1,114 Days
• Field of Search: 370/412, 370/416, 370/229, 370/230, 370/409, 370/418, 370/391, 370/400, 370/438, 370/413, 370/415, 370/417
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• 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: H04L 47/625 for service slots or service orders
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A packet scheduling system for use in a switching node of a high speed packet switching network. Incoming packets are enqueued in connection queues. Each connection is classified as red (exceeding traffic profile) or green (within traffic profile). QOS priority is also identified for each connection. Packets are dequeued for transmission as a function of priority class and connection class. Higher priority class connections have priority over lower priority class connections. Within a given priority class of connections, green connections have priority over red connections. Round robin scheduling is used for packets from connections in the same priority and connection class. In addition, a dynamic priority coupling mechanism is provided to prevent red higher priority traffic from blocking green lower priority traffic.

Claims

1. A packet scheduling system for use in a switching node of a high speed packet switching network, the switching node having a plurality of input and output links for receiving and transmitting packets received on a plurality of connections from a wide range of applications, said packet scheduling system comprising:

connection classification logic for assigning each of the plurality of connections either to a first class of connections carrying excess traffic or to a second class of connections not carrying excess traffic, said connection classification logic marking, as green, each originating connection which does not carry excess traffic and, as red, each originating connection which does carry excess traffic and wherein each packet includes an identifier indicative of the priority class of its originating connection;

a set of connection queues for temporarily storing packets received from the plurality of connections into a plurality of queues, each said queue being assigned to only one connection;

priority classification logic for assigning each of the plurality of connections to a priority class as a function of the quality of service requested by each connection;

packet scheduling logic for scheduling the transmission of the packets over at least one output link, said packet scheduling logic dequeueing packets from said plurality of connection as a function of the priority class and connection class of each of the connections, said packet scheduling logic

assigning a higher transmission priority to packets from a higher priority class than to packets from a lower priority class,

assigning priority to packets received on packets received on connections belong to the first class of connections if contending packets are from connections falling within the same priority class but different connection classes, and

assigning priority using round-robin scheduling if contending packets are from connections falling within the same priority class and the same connection class; and

additional logic for assigning transmission preference to packets from a given lower priority class having a green connection classification relative to contending packets from a given higher priority class having a red connection classification, said additional logic comprising

a first counter for computing the total number of red packets already queued in the connection queues associated with said given first and second priority classes;

a second counter for computing the total number of green packets already queued in the connection queue associated with said second priority class; and

a comparator for comparing the total number of red packets of said first priority class to a dynamic threshold and discarding any incoming red, first priority packets if said total amount of red first priority packets is greater than said dynamic threshold;

said dynamic threshold being set to a first predefined value when the total number of queued green packets of said second priority class is greater than zero, or to a second predefined value otherwise, said second predefined value being greater than said first predefined value.

2. The system as set forth in claim 1 wherein said connection classification logic further comprises:

a counter which is incremented for each new incoming red packet and decremented for each new incoming green packet; and

a comparator for comparing the contents of said counter to a first threshold and to a second threshold with said first threshold being greater than or equal to said second threshold,

said connection classification logic identifying a classification as red when said counter contents are greater than said first threshold and as green when said counter contents are less than said first threshold.

3. For use in a switching node of a high speed packet switching network, the switching node having a plurality of input and output links for receiving and transmitting packets received on a plurality of connections from a wide range of applications, a method of scheduling packets for transmission on said output links, said method comprising the steps of:

classifying each connection carrying excess traffic as belonging to a red connection class and each connection not carrying excess traffic as belonging to a green connection class;

temporarily storing packets received from the plurality of connections into a plurality of queues, each said queue being assigned to only one connection;

assigning a priority class to each of the plurality of connections, said priority class being a function of the quality of service requested by the respective connection;

scheduling contending packets for transmission as a function of said priority class and said connection class of the connections carrying the packets;

transmitting contending packets from a higher priority class connection before packets from a lower priority class connection such that where the connections over which contending packets are received are in the same priority class, transmitting packets received on green connections before transmitting packets received on red connections, and where the connections over which contending packets are received are in the same priority class and in the same connection class scheduling packets using a round-robin service discipline; and

transmitting a packet received over a green connection having a given lower priority class in preference to a contending packet received over a red connection having a given higher priority class.

4. The method as set forth in claim 3 wherein said step of transmitting a packet further comprises the steps of:

maintaining a count of the total number of temporarily stored packets received over red connections in either the given lower priority class or the given higher priority class;

maintaining a count of the total number of temporarily stored packets received on green connections; and

comparing the total count of red packets of said higher priority class to a dynamic coupling threshold and discarding any incoming red packet in said higher priority class if said total amount of red first priority packets is greater than said dynamic coupling threshold, said dynamic threshold being a function of the total number of green packets in said lower priority class.

5. A packet scheduling system suitable for use in a switching node in a packet switching network for scheduling the transmission of switched packets onto a plurality of connections, each connection having a pre-determined quality of service (QoS) requirement, the switching node having a plurality of connection queues for receiving the switched packets from a switching fabric, each switched packet marked as a non-excess packet when within the reserved bandwidth of the respective connection or marked as an excess packet when over the reserved bandwidth of the respective connection, each connection queue being assigned to a corresponding connection, said packet transmission scheduling system comprising:

transmission priority classification logic for assigning a transmission priority to each connection, said transmission priority being a function of the QoS requirement for the corresponding connection, such that a connection having a reserved bandwidth is assigned a higher said transmission priority than a said transmission priority assigned to a connection having no reserved bandwidth, and such that a connection having higher sensitivity to delay and jitter is assigned a higher said transmission priority than a said transmission priority assigned to a connection having lower sensitivity to delay and jitter;

transmission priority grouping logic for placing those connections assigned a particular said transmission priority into a group, the priority of said group being a function of said particular transmission priority such that a higher-priority group includes connections of a higher said transmission priority than said transmission priority of connections placed into a lower-priority group;

packet transmission scheduling logic for scheduling the transmission of packets over respective connections as a function of said group priorities such that packets queued on connections in said higher-priority group are dequeued before packets queued on connections in said lower-priority group;

connection group dequeueing logic for dequeueing packets queued within a particular said group using round-robin scheduling;

connection classification logic for classifying connection queues as a function of switched traffic behavior, such that a particular connection queue is classified as well-behaving if the number of queued non-excess switched packets in said particular connection queue is less than a first predetermined threshold value, or is classified as misbehaving if the number of queued excess switched packets in said particular connection queue is greater than a second predetermined threshold value; and

connection classification grouping logic for placing connections of a selected said group into connection subgroups as a function of connection classification, such that a well-behaving connection queue is placed into a well-behaving connection subgroup and a misbehaving connection queue is placed into a misbehaving connection subgroup.

6. The packet scheduling system as set forth in claim 5 comprising connection subgroup prioritizing logic for scheduling the transmission of packets within a said group as a function of subgroup classification, such that packets queued on connections in said well-behaving connection subgroup are dequeued before packets queued on connections in said misbehaving connection subgroup.

7. The packet scheduling system as set forth in claim 6, further comprising priority coupling logic for assigning relative transmission priorities between said well-behaving connection subgroup in said lower-priority group and said misbehaving connection subgroup in said higher-priority group.

8. The packet scheduling system as set forth in claim 7 wherein said priority coupling logic comprises:

a first counter for determining the number of non-excess switched packets queued in the connection queue associated with said well-behaving connection subgroup in said lower-priority group, to give a non-excess packet count;

coupling threshold logic for setting a coupling threshold parameter to either a first threshold value when said non-excess packet count is equal to zero, or to a second threshold value when said non-excess packet count is not equal to zero;

a second counter for determining the number of excess switched packets queued in the connection queue associated with said misbehaving connection subgroup in said higher priority group, to give an excess packet count; and

a coupling comparator for comparing said excess packet count to said coupling threshold parameter such that said excess switched packets are dequeued if said coupling threshold parameter is set to said first threshold value, and said excess switched packets are not dequeued if said coupling threshold parameter is set to said second threshold value.

9. The packet scheduling system as set forth in claim 5 herein said connection classification logic further comprises:

a packet counter which is incremented for each excess switched packet incoming on a selected connection, and decremented for each non-excess switched packet incoming on said selected connection; and

a classification comparator for comparing the counter reading to an excess threshold value and to a non-excess threshold value with said excess threshold value being greater than or equal to said non-excess threshold value,

such that said connection classification logic classifies said selected connection as misbehaving when said counter reading is greater than said excess threshold value and classifies said selected connection as well-behaving when said counter reading is smaller than said non-excess threshold value.

10. The packet scheduling system as set forth in claim 6 further comprising:

an excess packet counter for determining the number of said excess switched packets queued in the connection queue associated with said misbehaving connection subgroup, to give an excessive value; and

an excess packet comparator for comparing said excessive value to an excessive threshold value, such that said excess switched packets are dequeued if said excessive value is less than said excessive threshold value, and such that said excess switched packets are discarded if said excessive value is greater than or equal to said excessive threshold value.

11. A packet queueing and transmission scheduling method suitable for use in scheduling the transmission of switched packets onto a plurality of connections from a switching node in a packet switching network, each connection having a pre-determined quality of service (QoS) requirement, the switching node having a plurality of connection queues for receiving the switched packets from a switching fabric, each switched packet marked as a non-excess packet when within the reserved bandwidth of the respective connection or marked as an excess packet when over the reserved bandwidth of the respective connection, each connection queue being assigned to a corresponding connection, said method comprising the steps of:

assigning a transmission priority to each connection, said transmission priority being a function of the QoS requirement for the corresponding connection, such that a connection having a reserved bandwidth is assigned a higher said transmission priority than a said transmission priority assigned to a connection having no reserved bandwidth, and such that a connection having higher sensitivity to delay and jitter is assigned a higher said transmission priority than a said transmission priority assigned to a connection having lower sensitivity to delay and jitter;

placing those connections assigned a particular said transmission priority into a group, the priority of said group being a function of said particular transmission priority such that a higher-priority group includes connections of a higher said transmission priority than said transmission priority of connections placed into a lower-priority group;

scheduling the transmission of packets over respective connections as a function of said group priorities such that packets queued on connections in said higher-priority group are dequeued before packets queued on connections in said lower-priority group;

dequeueing packets queued within a particular said group using round-robin scheduling;

classifying connection queues as a function of switched traffic behavior, such that a particular connection queue is classified as well-behaving if the number of queued non-excess switched packets in said particular connection queue is less than a first predetermined threshold value, or is classified as misbehaving if the number of queued excess switched packets in said particular connection queue is greater than a second predetermined threshold value; and

placing connections of a selected said group into connection subgroups as a function of connection classification, such that a well-behaving connection queue is placed into a well-behaving connection subgroup and a misbehaving connection queue is placed into a misbehaving connection subgroup.

12. The method as set forth in claim 11 further comprising the step of:

scheduling the transmission of packets within a said connection group as a function of subgroup classification, such that packets queued on connections in said well-behaving connection subgroup are dequeued before packets queued on connections in said misbehaving connection subgroup.

13. The method as set forth in claim 12 further comprising the steps of:

determining the number of non-excess switched packets queued in the connection queue associated with said well-behaving connection subgroup in said lower-priority group, to give a non-excess packet count;

setting a coupling threshold parameter to either a first threshold value when said non-excess packet count is equal to zero, or to a second threshold value when said non-excess packet count is not equal to zero;

determining the number of excess switched packets queued in the connection queue associated with said misbehaving connection subgroup in said higher priority group, to give an excess packet count; and

comparing said excess packet count to said coupling threshold parameter such that said excess switched packets are dequeued if said coupling threshold parameter is set to said first threshold value, and said excess switched packets are not dequeued if said coupling threshold parameter is set to said second threshold value.

14. The method as set forth in claim 13 further comprising the steps of:

incrementing a packet counter for each excess switched packet incoming on a selected connection, and decrementing said packet counter for each non-excess switched packet incoming on said selected connection; and

comparing the counter reading to an excess threshold value and to a non-excess threshold value, with said excess threshold value being greater than or equal to said non-excess threshold value, such that said selected connection is classified as misbehaving when said counter reading is greater than said excess threshold value and such that said selected connection is classified as well-behaving when said counter reading is smaller than said non-excess threshold value.

15. The method as set forth in claim 12 further comprising the steps of:

determining the number of said excess switched packets queued in the connection queue associated with said misbehaving connection subgroup, to give an excess value; and

comparing said excessive value to an excessive threshold value, such that said excess switched packets are dequeued if said excessive value is less than said excessive threshold value, and such that said excess switched packets are discarded if said excessive value is greater than or equal to said excessive threshold value.