Manipulating data streams in data stream processors

Abstract

Techniques for performing user-configurable traffic management functions on streams of packets. The functions include multicasting, discard, scheduling, including shaping, and segmentation and reassembly. In the techniques, the functions are not performed directly on the packets of the stream, but instead on descriptors that represent stored packets. A packet's descriptor includes at least an identifier for the packet and a specifier for a set of traffic management functions to be performed on the descriptor. The user configures a set of traffic management functions for a traffic queue of descriptors. The specifier in the descriptor specifies a set of traffic management functions by specifying a descriptor queue. In multicasting, a descriptor is copied and placed on more than one traffic queue; with regard to discard, when the discard function associated with a traffic queue determines that a packet is to be discarded, the descriptor is placed in a discard traffic queue. Packets represented by descriptors in a discard traffic queue are discarded from the buffer. Output of descriptors from all traffic queues, including discard traffic queues, is scheduled. Scheduling is done using a hierarchy of schedulers. The form of the hierarchy and the scheduling algorithms used by the schedulers in the hierarchy are both user configurable. As disclosed, the techniques are implemented in a traffic management coprocessor integrated circuit. The traffic manager coprocessor is used with a digital communications processor integrated circuit that performs switching functions. The buffers for the packets are in the digital communications processor. Also disclosed are a modified partial packet discard algorithm and a frame based deficit round robin scheduling algorithm.

What is claimed is:  
     
         1 . An interface that transfers information between a first traffic steam processing device that performs a first plurality of stream processing functions on traffic streams made up of packets, the packets being represented in the device by descriptors, and a second traffic management device that performs a second plurality of traffic management functions for the traffic stream processing device using the descriptors, the interface comprising: 
 a first data path between the first and second devices that transfers the descriptor and at least a first selector from the first device to the second device, the first selector selecting a first subset of the plurality of traffic management functions; and    a second data path between the first and second devices that transfers the descriptor and at least a second selector from the second device to the first device after having performed a function in the first subset, the second selector selecting a second subset of the stream processing functions.    
     
     
         2 . The interface set forth in  claim 1  and further comprising: 
 a third data path between the first and second devices that transfers the second selector from the first device to the second device when the first device is able to perform a function in the second subset on the packet represented by the descriptor, the second device using the second selector to control flow of descriptors representing packets upon which the function is performed from the second device to the first device.  
 
     
     
         3 . The interface set forth in  claim 2  wherein: 
 the first device employs a first queue to associate the descriptor with the second subset of the stream processing functions;  
 the second device employs a second queue to associate the descriptor with the first subset of the traffic management functions;  
 the first selector specifies the second queue and the second selector specifies the first queue; and  
 the second selector is transferred to the second device when a descriptor is removed from the head of the first queue.  
 
     
     
         4 . The interface set forth in  claim 1  further comprising: 
 a fourth data path between the first and second devices that transfers an indication whether the second device can accept a transfer via the first data path from the first device to the second device;  
 a fifth data path between the first and second devices that transfers an indication whether the first device can accept a transfer via the second data path from the second device to the first device; and  
 a sixth data path between the first and second devices that transfers an indication whether the second device can accept a transfer via the third data path from the second device to the first device.  
 
     
     
         5 . Apparatus that performs traffic management operations for traffic streams that are made up of packets and are processed by a traffic stream processor, 
 the apparatus comprising: 
 a plurality of traffic management functions;  
 an input device that receives a descriptor associated with a traffic management function specifier from the traffic stream processor, the descriptor representing a packet being processed by the traffic stream processor and the traffic management function specifier associated with the descriptor specifying a subset of the traffic management functions;  
 a processing component that executes at least one traffic management function in the subset specified by the associated traffic management function specifier on the descriptor and associates the descriptor with a traffic stream processor function specifier that specifies a function in the traffic stream processor; and  
 an output device that provides the descriptor and the traffic stream processor function specifier to the traffic stream processor.  
   
     
     
         6 . Apparatus that performs traffic management operations for traffic streams made up of packets, 
 the apparatus comprising: 
 a plurality of sets of descriptors, a descriptor representing a packet in a traffic stream;  
 a plurality of traffic management functions, a given set of descriptors being associated with a subset of the plurality of traffic management functions; and  
 a processing component which executes at least one traffic management function in the subset associated with a set of descriptors on a descriptor belonging to the given set.  
   
     
     
         7 . The apparatus set forth in  claim 6  wherein: 
 a descriptor is received from a stream processor that processes the traffic streams and is provided to the stream processor after a traffic management function associated with the set of descriptors has been performed on the descriptor.  
 
     
     
         8 . The apparatus set forth in  claim 7  wherein: 
 the descriptor as received from the stream processor includes a set specifier specifying one of the sets of descriptors.  
 
     
     
         9 . The apparatus set forth in  claim 8  wherein: 
 the traffic management functions include a multicasting function; and  
 the sets of descriptors include a multicasting set of descriptors for descriptors that the multicasting function copies to a plurality of other ones of the sets of descriptors.  
 
     
     
         10 . The apparatus set forth in  claim 8  wherein: 
 the traffic management functions include a set of discard functions that select received descriptors representing packets to be discarded instead of being placed in the set specified by the descriptor's set specifier, the selected descriptors being provided to the stream processor with an indication that the packets represented by the descriptors are to be discarded.  
 
     
     
         11 . The apparatus set forth in  claim 10  wherein: 
 the apparatus further includes a model of the state of traffic stream to which the packets represented by the descriptors in the set thereof belong; and  
 the discard functions in the set employ the model to determine whether a packet from the set is to be discarded.  
 
     
     
         12 . The apparatus set forth in  claim 11  wherein: 
 the model models the state of a buffer in the stream processor, the buffer being used to store payloads from packets belonging to the stream.  
 
     
     
         13 . The apparatus set forth in  claim 11  wherein: 
 the model models the bandwidth usage of the stream.  
 
     
     
         14 . The apparatus set forth in  claim 7  wherein: 
 the traffic management functions include a set of scheduling functions that determine when a received descriptor is to be provided to the stream processor.  
 
     
     
         15 . The apparatus set forth in  claim 14  wherein: 
 the scheduling functions further determine a specifier for a set of descriptors in the stream processor that is included with the descriptor when the descriptor is provided to the stream processor.  
 
     
     
         16 . The apparatus set forth in  claim 7  wherein: 
 the traffic management functions include a set of discard functions that select received descriptors presenting packets to be discarded instead of being placed in the set specified by the descriptor's set specifier and a set of scheduling functions that determine when a descriptor is to be provided to the stream processor and add a specifier for a set of descriptors in the steam processor to the descriptor being provided;  
 the sets of descriptors include a set of discard descriptors containing descriptors representing packets to be discarded; and  
 the added specifier added to a provided descriptor from the set of discard descriptors specifies a set of descriptors in the stream processor that represent packets to be discarded.  
 
     
     
         17 . The apparatus set forth in  claim 7  wherein: 
 the apparatus receives the descriptor from the stream processor before a message that is contained at least in part in the packet represented by the descriptor has been completely received in the stream processor.  
 
     
     
         18 . The apparatus set forth in  claim 17  wherein: 
 the traffic management functions include a set of scheduling functions that determine when a descriptor is to be provided to the stream processor;  
 the stream processor provides a notification to the apparatus when the message has been completely received in the stream processor; and  
 when the descriptor is received from the stream processor before the message has been completely received in the stream processor, the processing component does not execute a scheduling function on the descriptor until the notification has also been received.  
 
     
     
         19 . The apparatus set forth in  claim 7  wherein: 
 the traffic management functions include a segmenting function that produces a sequence of descriptors representing portions of a packet from the descriptor for the packet.  
 
     
     
         20 . The apparatus set forth in  claim 7  wherein: 
 the traffic management functions include a reassembly function that provides an uninterrupted sequence of descriptors representing packets that are to be reassembled into a larger packet to the stream processor.  
 
     
     
         21 . The apparatus set forth in  claim 6  wherein: 
 the association between a given set of descriptors and a subset of the plurality of traffic management functions is configurable.  
 
     
     
         22 . The apparatus set forth in  claim 21  wherein: 
 the traffic management functions in the plurality are configurable.  
 
     
     
         23 . The apparatus set forth in  claim 6  wherein: 
 the plurality of traffic management functions and the processing component are implemented in a single integrated circuit.  
 
     
     
         24 . The apparatus set forth in  claim 7  wherein: 
 the sets of descriptors are organized as queues, with received descriptors being placed at the tails of the queues and provided descriptors being provided from the heads of the queues.  
 
     
     
         25 . Apparatus that performs traffic management operations for traffic streams that are made up of packets and are processed by a traffic stream processor, 
 the apparatus comprising: 
 traffic management functions including multicast functions, discard functions, and scheduling functions, the traffic management functions being user-configurable;  
 a plurality of traffic management queues of descriptors representing the packets, each traffic management queue having a user-configurable association with one or more of the traffic management functions; and  
 a processing component that responds to a descriptor and a queue specifier associated therewith that are received from the stream processor by employing the traffic management functions associated with the traffic management queue specified by the associated queue specifier to place the descriptor in a traffic management queue and schedule the descriptor for output to the traffic stream processor together with a specifier for a queue in the traffic stream processor.  
   
     
     
         26 . In a system wherein packets are represented by descriptors, a method of discarding packets belonging to a sequence thereof, the sequence carrying a message, the method being used when the system is assembling the packets carrying the message into an assembled packet, and 
 the method comprising the steps of: 
 upon a first decision to discard a packet of the sequence, marking the descriptor representing the packet as a descriptor for an end of message packet and as a descriptor for a defective packet and providing the descriptor to an assembler that responds to the descriptors by assembling the packets represented by the descriptors into the assembled packet;  
 providing the descriptors for the packets of the message that follow the marked descriptor to a packet discarder in the system that discards the packets in response to the descriptors; and  
 in the assembler, responding to the marked descriptor by discarding the assembled packet.  
   
     
     
         27 . In a system wherein packets are represented by descriptors, a method of beginning processing of a descriptor representing a packet of a message before the entire message is received in the system, the method comprising the steps of: 
 performing processing on the descriptor other than scheduling the descriptor; and    upon receiving a notification that the entire message has been received in the system, scheduling the descriptor.    
     
     
         28 . The method set forth in  claim 27  further comprising the steps of: 
 determining that the notification probably will not arrive; and  
 causing the system to discard the packet represented by the descriptor.  
 
     
     
         29 . The method set forth in  claim 28  wherein: 
 the descriptor represents a packet that contains the entire message.  
 
     
     
         30 . The method set forth in  claim 28  wherein: 
 the descriptor represents a packet in a multi-packet sequence of packets that contains the message.  
 
     
     
         31 . Apparatus for scheduling packets for further processing in a device that processes streams thereof, 
 the apparatus comprising: 
 a plurality of schedulers, the schedulers forming nodes of a hierarchy having at least an interior node and a leaf node;  
 a set of packets associated with the leaf node scheduler; and  
 a processor that executes the leaf node scheduler and the interior node scheduler to select a packet of the set associated with the leaf node scheduler for scheduling,  
   the schedulers being individually configurable to schedule according to a scheduling algorithm selected from a plurality thereof.    
     
     
         32 . The apparatus set forth in  claim 31  wherein: 
 the association between the set of packets and the leaf node scheduler is configurable.  
 
     
     
         33 . The apparatus set forth in  claim 31  wherein: 
 the form of the hierarchy is configurable.  
 
     
     
         34 . The apparatus set forth in  claim 31  wherein: 
 the hierarch has a single interior node scheduler that is a root node for the hierarchy;  
 there is a unique path through the hierarchy from each leaf node scheduler to the root node; and  
 the unique path is associated with a mode of further processing for the packet.  
 
     
     
         35 . The apparatus set forth in  claim 34  wherein: 
 the mode is specified by a virtual output port number associated with the path.  
 
     
     
         36 . The apparatus set forth in  claim 31  wherein: 
 the set of packets is associated with the leaf node scheduler by means of a set of descriptors that represent packets in the set.  
 
     
     
         37 . The apparatus set forth in  claim 36  wherein: 
 the set of descriptors is organized into at least one traffic queue of descriptors and at least one scheduler queue of the traffic queues, each scheduler queue being associated with an input of the leaf node scheduler that the set of descriptors is associated with.  
 
     
     
         38 . The apparatus set forth in  claim 31  wherein: 
 the plurality of scheduling algorithms includes a strict priority algorithm, a round robin algorithm, and a weighted fair queueing algorithm.  
 
     
     
         39 . The apparatus set forth in  claim 38  wherein: 
 a scheduler in a node of the hierarchy is configured from scheduler resources including a guaranteed scheduler, an excess scheduler, and a strict priority scheduler that gives first priority to the guaranteed scheduler.  
 
     
     
         40 . The apparatus set forth in  claim 38  wherein: 
 there is a plurality of weighted fair queueing algorithms, the plurality including non-work-conserving weighted fair queueing algorithms.  
 
     
     
         41 . A method of scheduling varying-length packets, the method employing two sets of sets of the packets and 
 the method comprising the steps of: 
 selecting a given set of packets belonging to a current set of the two sets of sets of packets for scheduling, each set of packets belonging to the current set of the sets of packets being associated with a maximum quantum and a minimum quantum, the given set of packets remaining selected for scheduling as determined by the minimum quantum, and the minimum quantum determining a total size of packets that may be scheduled from the selected set of packets before again selecting a set of the packets belonging to the current set of the sets for scheduling;  
 placing the given set of packets in the other of the two sets of sets of the packets as determined by the maximum quantum, the maximum quantum determining a total size of packets that may be scheduled from the selected set before the selected set is placed in the other of the two sets of the sets of packets; and  
 when the current set of sets of packets becomes empty, swapping the current set of sets of packets and the other set of sets of packets.  
   
     
     
         42 . The method set forth in  claim 41  further comprising the step of: 
 when the set of packets is moved from the current set to the next set, computing a new maximum quantum using the difference between the total size of the packets actually scheduled and the maximum quantum at the time the set of packets is placed in the other of the two sets of packets.  
 
     
     
         43 . The method set forth in  claim 41  further comprising the steps of: 
 when a set of the packets belonging to the current set becomes ineligible for scheduling, removing the ineligible set of packets from the current set; and  
 when an ineligible set of packets becomes eligible for scheduling, adding the eligible set to the next set.  
 
     
     
         44 . The method set forth in  claim 41  wherein: 
 the current set of sets of packets is an ordered set and the sets of packets are selected for scheduling in round-robin fashion.  
 
     
     
         45 . The method set forth in  claim 41  wherein: 
 the sets of packets in the current set are ordered sets and when a set of packets has been selected for scheduling, a packet is selected therefrom in round-robin fashion.  
 
     
     
         46 . The method set forth in  claim 41  wherein: 
 the method employs a third set of sets of packets that has priority for scheduling over the current set of sets of packets; and  
 the given set of packets belongs to the third set of sets of packets while the given set of packets remains selected for scheduling as determined by the minimum quantum and is thereafter moved to the current set of sets of packets and scheduled therefrom as determined by the maximum quantum.  
 
     
     
         47 . The method set forth in  claim 46  wherein: 
 the current set of sets of packets and the third set of sets of packets are ordered sets and the sets of packets are selected for scheduling in the current set of packets and in the third set of packets in round-robin fashion.  
 
     
     
         48 . The method set forth in  claim 47  wherein: 
 the sets of packets in the current set and the third set of sets of packets are ordered sets and when a set of packets has been selected for scheduling, a packet is selected therefrom in round-robin fashion.  
 
     
     
         49 . The method set forth in  claim 41  wherein: 
 each packet is represented by a descriptor; and in the set of packets, the packets are represented by their descriptors.