Browse Prior Art Database

Design of 2-Dimensional Round-Robin Scheduler

IP.com Disclosure Number: IPCOM000114067D
Original Publication Date: 1994-Nov-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 144K

Publishing Venue

IBM

Related People

Pecoraro, TQ: AUTHOR [+2]

Abstract

Disclosed is the design of a 2-Dimensional Round-Robin (2DRR) scheduler for a 4-port switch employing 4 input queues per input port, each queue in an input port corresponding to a different output port. The switch is considered to be a cell based switch with a clock period of 40ns, where each cell transmission has a duration of 32 clock cycles. The use of the 2-Dimensional Round-Robin scheduler provides good fairness properties without sacrificing overall throughput. A description of the 2-Dimensional Round-Robin Scheduling algorithm is given in (*).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 39% of the total text.

Design of 2-Dimensional Round-Robin Scheduler

      Disclosed is the design of a 2-Dimensional Round-Robin (2DRR)
scheduler for a 4-port switch employing 4 input queues per input
port, each queue in an input port corresponding to a different output
port.  The switch is considered to be a cell based switch with a
clock period of 40ns, where each cell transmission has a duration of
32 clock cycles.  The use of the 2-Dimensional Round-Robin scheduler
provides good fairness properties without sacrificing overall
throughput.  A description of the 2-Dimensional Round-Robin
Scheduling algorithm is given in (*).

The Design of the Scheduler

      Incoming bits represent control information to the scheduler
indicating whether new transmission requests exist or past requests
are reset.  The output of the scheduler is another control bit stream
indicating the cell transmissions granted.  Cell data movement is
assumed to progress in parallel to control bit flow.

      Clocks - The scheduler uses 2 external clocks: B0 and C0.  The
period of the C0 clock is 40ns.  The B0 clock, with period 1.28
microsecs, is synchronous with the data cells of the switch.  One B0
clock period contains 32 cycles of the C0 clock.  In the design
another clock is also used, the L0 clock, which is derived from the
B0 clock by shifting it one C0 cycle.

      Input Ports - The input ports are responsible for latching the
appropriate bits from the incoming bitstream.  The data of interest
are the PRDA and S/R fields, where PRDA respresents the index of an
output port and S/R represents the Set/Reset of a request from the
input port to the indicated output port (index 0 is used to indicate
that there is no port requesting a Set/Reset).  The ports used in the
scheduler use the indices  3, 4, 5 and 6.

      The incoming serial control bit stream is shifted in a shift
register composed of 2 cascaded 7496 5-bit shift registers.  The B0
clock is used to latch the PRDA field in a 74174 register, since all
the PRDA bits are valid by the falling edge of the B0 pulse.  During
the following C0 cycle, the PRDA field is decoded and the asserted
output line of the 74138 decoder causes the corresponding flip-flop
(within the 7474 modules) to store the incoming value of the S/R bit.
The 3 flip flops storing the remaining requests from Input Port are
fed back with the value they had during the previous cycle.  This
design allows the request flip-flops (7474 modules) to be clocked
with the L0 clock, thus avoiding glitches that may appear when the L0
clock is gated (actually, the flip flops are clocked with the
complement of C0, because the modules store using positive edge clock
signals).

      Pattern Sequence State Machine - The Pattern Sequence State
Machine (PSSM) is responsible for generating the right diagonal
sequence patterns as required by the 2DRR algorithm.  The 4 diagonal
signals are denoted as PSSM-D0, PSSM-D1, PSSM-D2, and PSSM-D3.  Since
t...