Computationally-efficient traffic shaper

Abstract

A computationally-efficient traffic shaper replaces per-virtual-circuit shaping queues that all must be processed during each cell-emission period, with a sequence ( ) of shaping queues ( ) shared by a plurality of virtual circuits and only one of which must be processed during each cell-emission period. N shaping queues are used, where N is the maximum cell delay effected by the traffic shaper divided by the cell emission period; for constant-bit-rate narrowband virtual circuits, N is 47. Each virtual circuit is assigned one or more of the shaping queues, spaced evenly in the sequence, as its serving queues, proportionally to its size. A dequeue state machine ( ) cyclically transmits the contents of a current one of the shaping queues during each period. Per-virtual-circuit instances of an enqueue state machine ( ) each enqueue received ATM cells of its corresponding virtual circuit. If the cell arrives on time, it is enqueued in the current queue which is one of the virtual circuit's serving queues. If the cell arrives early, it is enqueued in the virtual circuit's next serving queue. If the cell arrives late, it is enqueued in the current queue, and designation of all of the virtual circuit's serving queues is shifted an equal amount in the sequence so that the current queue becomes one of the virtual circuit's new serving queues. For variable-bit-rate virtual circuits, an additional overflow queue ( ) is used to temporarily hold overflow received cells until the dequeuing makes room for them in the shaping queues.