Manipulating data streams in data stream processors
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
130 Citations
49 Claims
-
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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
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. - View Dependent Claims (28, 29, 30)
-
-
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. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40)
-
-
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. - View Dependent Claims (42, 43, 44, 45, 46, 47, 48, 49)
-
Specification