Frame relay priority queses to offer multiple service classes

Abstract

There is provided a message service device for a switching network. The device provides an input port for receiving messages from a number of network connections. The device includes a storage device for storing a number of predetermined priority levels pertaining to the received messages, one of the priority levels being assigned to each of the network connections. A number of first-in first-out message queues are provided for storing the received messages. The queues respectively correspond to each of the predetermined priority levels. Each queue is associated with at least one of a number of predetermined congestion thresholds whereby a congestion severity status may be determined for each queue. The congestion severity status corresponds proportionally to the number of the congestion thresholds which have been exceeded by the queue. The message service device further provides a processor for determining the network connection associated with each of the received messages. The processor allocates each of the messages to the tail of a corresponding one of the queues based upon the priority level assigned to the determined network connection and supplied to the processor from the storage device. A server for the arbitration of message frames from the queues is also provided. The server determines the congestion severity status for each of the queues prior to selecting a message from the queues. The server selects the message from the head of the queue which has the highest congestion severity status where only one queue has such status and from the queue corresponding to the highest priority level where more than one queue has such status. The message service device provides an output port for dispatching messages selected from the queues by the server.

What is claimed: 
     
       1. A message service apparatus for a switching network, the message service apparatus comprising: (a) an input port for receiving messages from a plurality of network connections,   (b) a plurality of message queues for storing said received messages, the queues respectively corresponding to each of a plurality of predetermined priority levels pertaining to said received messages, one of said priority levels being assigned to each network connection of said plurality of network connections, each queue having associated therewith at least one of a plurality of predetermined congestion thresholds whereby a congestion severity status may be determined for each queue, the congestion severity status corresponding proportionally to the number of said congestion thresholds which have been exceeded by the queue;   (c) a processor for determining the network connection associated with each of said received messages, and for allocating each of said messages to a corresponding one of said queues based upon the priority level assigned to said determined network connection;   (d) a server for the arbitration of messages from said queues, wherein said server determines said congestion severity status for each of said queues, identifies which of said queues has the highest congestion severity status, and determines whether more than one of said queues has been identified as having the highest congestion severity status, whereupon: (d.1) if only one queue has said highest congestion severity status, said server selects a next message to be dispatched from the queue having said highest congestion severity status and   (d.2) if more than one queue has said highest congestion severity status, said server determines, from among those queues having said highest congestion severity status, which of said queues has the highest priority level, and said server instead selects said next message to be dispatched from the queue having said highest priority level; and     (e) an output port for dispatching said messages selected from the queues by said server.   
     
     
       2. The apparatus according to claim 1, wherein said message queues are first-in first-out queues, each queue having a head and a tail thereof, said processor allocating said messages to the tail of said one of said corresponding queues, said server selecting each next message to be dispatched from the head of a queue which has been identified for service according to the procedure of step (d). 
     
     
       3. The apparatus according to claim 2, further comprising a storage device for storing said plurality of predetermined priority levels pertaining to said received messages. 
     
     
       4. The apparatus according to claim 3, wherein said plurality of predetermined priority levels consists of four priority levels and said apparatus provides four message queues. 
     
     
       5. The apparatus according to claim 4, wherein two predetermined congestion thresholds are applied to each of the queues. 
     
     
       6. The apparatus according to claim 5, wherein each congestion threshold is established in equivalent units of delay time and queue depth corresponding respectively to a delay congestion threshold and a depth congestion threshold, such that a delay congestion status and a depth congestion status may be determined for each queue, the delay congestion status corresponding proportionally to the number of delay congestion thresholds which have been exceeded by the queue and the depth congestion status corresponding proportionally to the number of depth congestion thresholds which have been exceeded by the queue, the number of exceeded delay congestion thresholds for a queue being determined on the basis of elapsed time from which a message at the head of said queue has been allocated to said queue, the number of exceeded delay congestion thresholds for a queue being determined on the basis of message depth within said queue, and wherein said congestion severity status for each queue is determined as the highest of the delay congestion status and the age congestion status for that queue when each such status is not the same, and as either of the delay congestion status and the age congestion status when each such status is the same. 
     
     
       7. The apparatus according to claim 6, further comprising a timer for time stamping each of the messages received from said input port prior to said messages being allocated to said corresponding queue, the time stamping thereby enabling a determination of said elapsed time. 
     
     
       8. The apparatus according to claim 7, wherein said switching network is a Frame Relay network and said messages are message frames. 
     
     
       9. The apparatus according to claim 8, wherein the predetermined congestion thresholds for each queue correspond to mild congestion threshold (MCT) and severe congestion threshold (SCT) for a network connection associated with said queue. 
     
     
       10. The apparatus according to claim 9, wherein said storage device is a lookup table. 
     
     
       11. A method for servicing messages received from a plurality of network connections in a switching network, the method comprising the steps of (a) determining the network connection associated with each of said received messages;   (b) allocating each of said received messages to a corresponding one of a plurality of message queues, the queues respectively corresponding to each of a plurality of predetermined priority levels pertaining to said received messages, one of said priority levels being assigned to each of said network connections, each queue having associated therewith at least one of a plurality of predetermined congestion thresholds, the received messages being allocated to said corresponding one of said queues based upon the predetermined priority level assigned to said determined network connection;   (c) determining a congestion severity status for each of said queues prior to each dispatch of a message therefrom, the congestion severity status corresponding proportionally to the number of said congestion thresholds which have been exceeded by the queue;   (d) identifying which of said queues has the highest congestion severity status;   (e) determining whether more than one of said queues has been identified as having the highest congestion severity status, and (e.1) if only one queue has said highest congestion severity status, said server selects a next message to be dispatched from the queue having said highest congestion severity status, and   (e.2) if more than one queue has said highest congestion severity status said server determines, from among those queues having said highest congestion severity status, which of said queues has the highest priority lever, and said server instead selects said next message to be dispatched from the queue having said highest priority level and;     (f) dispatching said selected message from the queue.   
     
     
       12. The method according to claim 11, wherein said message queues are first-in first-out queues, each queue having a head and a tail thereof, said received messages being allocated to the tail of said corresponding one of said queues based upon the predetermined priority level assigned to said determined network connection, said next message to be dispatched being selected from the head of a queue which has been identified for service according to the procedure of step (e). 
     
     
       13. The method according to claim 12, wherein said plurality of predetermined priority levels consists of four priority levels and wherein four message queues are provided. 
     
     
       14. The method according to claim 13, wherein two predetermined congestion thresholds are associated with each queue. 
     
     
       15. The method according to claim 14, wherein each congestion threshold is established in equivalent units of delay time and queue depth corresponding respectively to a delay congestion threshold and a depth congestion threshold, such that a delay congestion status and a depth congestion status may be determined for each queue, the delay congestion status corresponding proportionally to the number of delay congestion thresholds which have been exceeded by the queue and the depth congestion status corresponding proportionally to the number of depth congestion thresholds which have been exceeded by the queue, the number of exceeded delay congestion thresholds for a queue being determined on the basis of elapsed time from which a message stored at the head of said queue has been allocated to said queue, the number of exceeded delay congestion thresholds for a queue being determined on the basis of message depth within said queue, and wherein said congestion severity status for each queue is determined as the highest of the delay congestion status and the age congestion status of that queue when each such status is not the same, and as either of the delay congestion status and the age congestion status when each such status is the same. 
     
     
       16. The method according to claim 15, wherein each message is time stamped prior to being allocated to a corresponding one of said queues, to thereby enable computation of said elapsed time. 
     
     
       17. The method according to claim 16, wherein said switching network is a Frame Relay network and said messages are message frames. 
     
     
       18. The method according to claim 17, wherein the predetermined congestion thresholds for each queue correspond to mild congestion threshold (MCT) and severe congestion threshold (SCT) for a network connection associated with said queue. 
     
     
       19. The method according to claim 18, wherein said plurality of predetermined priority levels is stored in a lookup table. 
     
     
       20. An apparatus for servicing messages received from a plurality of network connections in a switching network, the apparatus comprising; (a) means for determining the network connection associated with each of said received messages;   (b) means for allocating each of said received messages to a corresponding one of a plurality of message queues, the queues respectively corresponding to each of a plurality of predetermined priority levels pertaining to said received messages, one of said priority levels being assigned to each of said network connections, each queue having associated therewith at least one of a plurality of predetermined congestion thresholds, the received messages being allocated to said corresponding one of said queues based upon the predetermined priority level assigned to said determined network connection,   (c) means for determining a congestion severity status for each of said queues prior to each dispatch of a message therefrom, the congestion severity status corresponding proportionally to the number of said congestion thresholds which have been exceeded by the queue, wherein means for determining identifies which of said queues has the highest congestion severity status and determines whether more than one of said queues has been identified as having the highest congestion severity status;   (d) means for selecting a next message to be dispatched from said queues wherein: (d.1) if only one queue has said highest congestion severity status, said server selects a next message to be dispatched from the queue having said highest congestion severity status and,   (d.2) if more than one queue has said highest congestion severity status, said server determines, from among those queues having said highest congestion severity status, which of said queues has the highest priority level, and said server instead selects said next message to be dispatched from the queue having said highest priority level, and     (e) means for dispatching said selected message from the queue.