Flexible bandwidth allocation in high-capacity grooming switches
AssigneeAT&T Corp.
InventorAleksandra Smiljanic
Life of this patent
Estimating the term…
Abstract
A method and apparatus for flexible sharing of bandwidth in switches with input buffering by dividing time into a plurality of frames of time slots, wherein each frame has a specified integer value of time slots. Counters associated with the input-output queues of the switches are loaded with a negotiated integer value once per frame. The inputs sequentially select available outputs to which the inputs send packets in specified future time slots. Priority is given to input-output queues with counters having positive values. The selection of outputs by the inputs is done using a pipeline technique and a schedule is calculated within multiple time slots. The counters for selected queues are then decremented by 1.
Claims19
A method of allocating bandwidth for use at a packet switch having a plurality of inputs and a plurality of outputs for switching to specified ones of said outputs, and a plurality of corresponding input buffers having input-output queues, and associated counters, said method comprising the steps of
- dividing time into a plurality of frames of time slots, each frame having a specified integer value of time slots;
- loading said counters associated with said input-output queues to a negotiated integer value once per said frame;
- said inputs sequentially selecting said outputs that are available to which said inputs send packets in specified future time slots, wherein priority is given to those of input-output queues whose associated ones of said counters having positive values;
- said selection of outputs by said inputs being done using a pipeline technique where input i, i=0,1, . . . , N−1 chooses output for time slot k in time slot k−┌(N−i)/p┐, where p is the number of selections made in one time slot, N is the number of inputs of said switch, and ┌(N−i)/p┐ is the smallest integer greater or equal to * (N−i)/p, and wherein a schedule is calculated within multiple time slots, wherein schedules for multiple future time slots being calculated in each time slot;
- and
- decrementing said counters of selected queues by 1.
The method of claim 1 implemented for packet transmission time T wherein new bandwidth can be allocated by using methods of claims 12 and 13 within time FT, wherein F is an integer corresponding to the number of time slots in said frame and wherein one time slot per frame guarantees bandwidth of B/F by using methods of claims 12 or 13, where B is the line bit-rate and a minimum guaranteed bandwidth can be made low by increasing F.
A method of allocating bandwidth in a circuit switch having a plurality of inputs for switching to outputs, input tables and input-output counters, said method comprising the steps of:
- dividing time into a plurality of data frames comprising data time slots, and reservation frames comprising reservation time slots, each data frame having a specified number of data time slots;
- loading said counters to a difference between a current total number of negotiated credits and a total number of released credits in the previous said reservation frames of said reservation frame;
- said inputs sequentially releasing the time slot reservations for outputs if said inputs corresponding counters have negative values;
- said inputs sequentially reserving time slots for unreserved outputs if said inputs corresponding counters have positive values;
- whenever one of said inputs releases an output, the corresponding counter is incremented by 1, and whenever one of said inputs reserves an output the corresponding counter is decremented by 1;
- said input tables being updated after all inputs have had a chance to release and reserve outputs for future time slots, storing outputs reserved in each time slot of a frame, and outputs reserved by the corresponding input in each time slot of a frame;
- and
- said release of time slot reservation, reserving of time slots, and said updating of input tables being done using a pipeline technique, wherein a schedule is calculated within multiple reservation time slots, and schedules for multiple future time slots are calculated in each reservation time slot.
An apparatus for allocating bandwidth for use at a packet switch having a plurality of inputs for switching to specified outputs and a plurality of corresponding input buffers having input-output queues, said buffers being coupled to said input-output queues having associated counters, said apparatus comprising:
- means for loading said counters associated with said input-output queues to said negotiated integer value once per said a frame of a preselected number of time slots;
- and
- means for negotiating values of time slots per frame associated with input-output pairs, wherein input-output pair (i,j) can be allocated additional Δaij, time slots per frame of length F if it holds that:
- ∑
- m
-
- a
- im
- +
- ∑
- m
-
- a
- mj
- -
- a
- ij
- +
- Δ
-
-
- a
- ij
- ≤
- F
- ,
- where ak,l, 0≦k, l≦N−1, is the number of time slots previously assigned to input-output pair (k,l), and N is the number of inputs and outputs, and F is an integer corresponding to the number of time slots in said frame;
- wherein said inputs sequentially selecting said outputs that are available to which said inputs send packets in specified future time slots, wherein priority is given to input-output queues with counters having positive values;
- and wherein selection of outputs by said inputs is done using a pipeline technique, and wherein not all inputs select outputs for a specified time slot in the future while other inputs choose outputs for some other future time slots.
Dependencies are inferred from the claim text.