System and method for a quality of service in a multi-layer network element

• US 6,094,435 A
• Filed: 06/30/1997
• Issued: 07/25/2000
• Est. Priority Date: 06/30/1997
• Status: Expired due to Fees

• Current Assignee: Microsoft Corporation, Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Khamisy, Asad, Hoffman, Don, Murthy, Shree
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US08/885,258
• Time in Patent Office: 1,121 Days
• Field of Search: 370/412, 370/413, 370/414, 370/417, 370/418, 370/415, 370/416, 370/400, 370/401, 370/429, 370/468
• US Class Current: 370/414
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]
• 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/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 47/6265 past bandwidth allocation
• 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 49/9042 Separate storage for different parts of the packet, e.g. header and payload
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9078 using an external memory or storage device
• CPC Class Codes: H04Q 2213/13103 : Memory

Abstract

A multi-layer network element for forwarding received packets from an input port to one or more output ports with quality of service. When output queues exceed or meet a threshold value below the queue'"'"'s capacity packets are ramdomly discarded. When the queue becomes full, the network element determines which flow caused the queue to overflow. The priority of that flow is lowered. In a multicast packet, the packet may have different priorities at each output port. Scheduling of multiple output queues at each output port uses a weight round robin approach that allocates a weight portion of packets to transmit at each time interval. A packet is not interrupted during its transmission, even if the weight portion is met during a packet'"'"'s transmission. The excess number of bytes transmited as a result of not interrupting the packet are accounted for in the next round.

Claims

1. An apparatus for detecting and handling queue congestion in an output port of a multi-layer network element comprising:

a central processing unit (CPU);

a switching element coupled to the CPU and configured to output packets to a network through the output port, the switching element including;

at least one output queue having storage locations for packet pointers, each pointer configured to point to portions of a packet to be transmitted on the network, associated with the output port, and wherein the number of storage locations is variable,

a start register configured to store a pointer to the storage location at the front of the queue,

an end register configured to store a pointer to the storage location at the end of the queue as determined by the number of storage locations,

a next-free register configured to store a pointer to the next available storage location, wherein packet pointers are stored in the output queue beginning at the location pointed to by the start register and the next-free register is incremented as the next available storage location moves toward the second pointer,

a programmable threshold register configured to store a threshold pointer to a storage location between the location represented by the start register and the location represented by the end register,

threshold logic configured to output a congestion signal when the value in the next free register represents a storage location logically located between the location pointed to key the threshold register and including the storage location pointed to by the end register,

random discarding logic configured to randomly select packets to discard in response to the signal, so that once the threshold is exceeded, incoming packets are randomly discarded,

capacity logic configured to output a queue full signal to the CPU when the value in the next free register is equal to the value in the end register,

a memory having at least one entry configured to store information about forwarding decisions for the packet, wherein the entry is adapted to indicate whether packets associated with that entry should be counted,

memory access logic configured to access the entry when an incoming packet associated with that entry arrives at the switching element, and

a packet counter configured to count the number of times the entry is accessed, to represent an entry bandwidth; and

a computer program mechanism coupled to the CPU configured to compare the contents of the packet counter to a reservation-based protocol negotiated value for lowering a priority of any future packet associated with the entry and destined for the output queue.

2. An apparatus for queue scheduling in a network element comprising:

at least one output port configured to output packets, each packet having a byte length;

at least two queues associated with each output port, configured to queue packets to be output at each output port;

a weight register associated with each queue and adapted to receive a value representing a weight number;

weighting logic for generating the weight number for each queue;

transmitting logic at each output port configured to transmit packets identified in each queue according to a queue select signal and responsive to a done signal;

scheduling logic at each output port configured to select one of the queues and to generate the queue select signal to the transmitting logic to indicate which queue will be transmitting;

counter logic, at each output port, associated with the counters configured to decrement the weight register equal to a number of bytes transmitted by the transmitting logic; and

reloading logic configured to determine the number of packets transmitted after the done signal and to place in the weight register a value equal to the weight number minus the number of packets transmitted after the done signal.

3. The apparatus of claim 2, wherein the scheduling logic is configured to respond to the done signal and the transmitting logic to select a next transmitting queue.

4. The apparatus of claim 2, wherein the scheduling logic is configured to select a next transmitting queue at a time prior to the zero logic generating the done signal.