Multiple-criteria queueing and transmission scheduling system for multimedia networks

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.

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.

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.