US6865154B1 — Method and apparatus for providing bandwidth and …

Claim 1

Independent Claim 128 words

An apparatus for providing bandwidth and delay guarantees in a crossbar switch including a crossbar unit, the apparatus comprising: a rate controller to receive cells at an input of the crossbar switch and process the received cells, including controlling a rate at which the received cells are provided to an input of the crossbar unit; and an arbiter to schedule sending the cells received at the input of the crossbar unit to an output of the crossbar switch, the arbiter implementing a work-conserving algorithm such that when at least one input cell is available for scheduling by the arbiter to be sent to an output of the crossbar switch, at least one cell will be transmitted from said output of the crossbar switch during a subsequent cell time.

Claim 2

Independent Claim 128 words

An apparatus for providing bandwidth and delay guarantees in a crossbar switch including a crossbar unit, the apparatus comprising: a rate controller to receive cells at an input of the crossbar switch and process the received cells, including controlling a rate at which the received cells are provided to an input of the crossbar unit; and an arbiter to schedule sending the cells received at the input of the crossbar unit to an output of the crossbar switch, the arbiter implementing a work-conserving algorithm such that when at least one input cell is available for scheduling by the arbiter to be sent to an output of the crossbar switch, at least one cell will be transmitted from said output of the crossbar switch during a subsequent cell time.

Claim 3

Dependent Claim 33 words

The apparatus as recited in claim 1 , wherein the rate controller processes received input cells such that only one cell is output from the rate controller to the arbiter at a time.

Claim 4

Dependent Claim 31 words

The apparatus as recited in claim 1 , wherein the rate controller processes input cells received from a source such that a predetermined bandwidth rate for the source is not exceeded.

Claim 5

Dependent Claim 23 words

The apparatus as recited in claim 3 , wherein the rate controller is implementing a Rate-Controlled Smallest Eligible Finish Time First (RSEFTF) algorithm.

Claim 6

Dependent Claim 18 words

The apparatus as recited in claim 1 , wherein the arbiter is emulating an output-buffered switch with FIFO.

Claim 7

Dependent Claim 28 words

The apparatus as recited in claim 5 , wherein the arbiter is running a Lowest Occupancy Output First Algorithm (LOOFA) algorithm with a speedup of at least three.

Claim 8

Dependent Claim 28 words

The apparatus as recited in claim 1 , wherein the arbiter is running a Lowest Occupancy Output First Algorithm (LOOFA) algorithm with a speedup of at least two.

Claim 9

Dependent Claim 26 words

The apparatus as recited in claim 1 , wherein the arbiter is running a Most Urgent Cell First Algorithm (MUCFA) algorithm with a speedup of four.

Claim 10

Dependent Claim 28 words

The apparatus of claim 1 , wherein the rate controller arranges the received input cells into per-flow queues based on flows to which the received input cells belong.

Claim 11

Dependent Claim 18 words

The apparatus of claim 9 , wherein the rate controller receives the received input cells on multiple inputs.

Claim 12

Dependent Claim 15 words

The apparatus of claim 9 , wherein the rate controller isolates flows from misbehaving flows.

Claim 13

Dependent Claim 36 words

The apparatus of claim 9 , wherein each flow has a respective bandwidth guarantee, and the rate controller presents each flow to the arbiter at a rate corresponding to the respective bandwidth guarantee of the flow.

Claim 14

Dependent Claim 15 words

The apparatus of claim 1 , wherein the received input cells are fixed length cells.

Claim 15

Dependent Claim 14 words

The apparatus of claim 1 , wherein the received input cells are ATM cells.

Claim 16

Dependent Claim 13 words

The apparatus of claim 1 , wherein the rate controller comprises a scheduler.

Claim 17

Dependent Claim 11 words

The apparatus of claim 15 , wherein the scheduler is QoS-capable.

Claim 18

Dependent Claim 20 words

The apparatus of claim 15 , wherein the scheduler is implementing a Rate-Controlled Smallest Eligible Finish Timer First (RSEFTF) algorithm.

Claim 19

Dependent Claim 32 words

The apparatus of claim 1 , wherein the rate controller processes received input cells received from an input link such that a predetermined bandwidth rate for the input link is not exceeded.

Claim 20

Dependent Claim 17 words

The apparatus of claim 1 , wherein the rate controller fragments the received input cells into fragments.

Claim 21

Dependent Claim 24 words

The apparatus of claim 19 , wherein the fragments are assigned to per-flow queues corresponding to flows to which the received input cells belong.

Claim 22

Dependent Claim 13 words

The apparatus of claim 1 , further comprising output queues at said output.

Claim 23

Dependent Claim 26 words

The apparatus of claim 21 , wherein the arbiter schedules input cells output from the rate controller based on an occupancy characteristic of the output queues.

Claim 24

Dependent Claim 177 words

A switch for providing bandwidth and delay guarantees to a data flow transmitted in a communications network, the data flow comprising at least one data cell, the switch comprising: a rate controller to receive the at least one data cell and to output the received at least one data cell at a predetermined rate for the respective data flow; a cross-bar unit to receive the at least one data cell output from the rate controller at an input of the cross-bar unit, the at least one data cell identifying an output of the switch; an arbiter, connected to the cross-bar unit, to control the connection of the at least one data cell, output from the rate controller, from the input of the cross-bar unit to the identified output of the switch according to a work-conserving algorithm; wherein the work-conserving algorithm requires that when at least one data cell is received by the cross-bar unit and is destined for an output, at least one data cell will be output from the identified output during a subsequent cell time.

Claim 25

Dependent Claim 177 words

A switch for providing bandwidth and delay guarantees to a data flow transmitted in a communications network, the data flow comprising at least one data cell, the switch comprising: a rate controller to receive the at least one data cell and to output the received at least one data cell at a predetermined rate for the respective data flow; a cross-bar unit to receive the at least one data cell output from the rate controller at an input of the cross-bar unit, the at least one data cell identifying an output of the switch; an arbiter, connected to the cross-bar unit, to control the connection of the at least one data cell, output from the rate controller, from the input of the cross-bar unit to the identified output of the switch according to a work-conserving algorithm; wherein the work-conserving algorithm requires that when at least one data cell is received by the cross-bar unit and is destined for an output, at least one data cell will be output from the identified output during a subsequent cell time.

Claim 26

Dependent Claim 34 words

The apparatus of claim 23 , wherein the rate controller processes the at least one data cell such that only one cell is output from the rate controller to the arbiter at a time.

Claim 27

Dependent Claim 31 words

The apparatus of claim 23 , wherein the rate controller processes input cells received from a known source such that a predetermined bandwidth rate for the known source is not exceeded.

Claim 28

Dependent Claim 21 words

The apparatus of claim 25 , wherein the rate controller is implementing a Rate-Controlled Smallest Eligible Finish Time First (RSEFTF) algorithm.

Claim 29

Dependent Claim 16 words

The apparatus of claim 23 , wherein the arbiter is emulating an output-buffered switch with FIFO.

Claim 30

Dependent Claim 26 words

The apparatus of claim 27 , wherein the arbiter is running a Lowest Occupancy Output First Algorithm (LOOFA) algorithm with a speedup of at least three.

Claim 31

Dependent Claim 26 words

The apparatus of claim 23 , wherein the arbiter is running a Lowest Occupancy Output First Algorithm (LOOFA) algorithm with a speedup of at least two.

Claim 32

Dependent Claim 26 words

The apparatus of claim 23 , wherein the arbiter is running a Most Urgent Cell First Algorithm (MUCFA) algorithm with a speedup of at least three.

Claim 33

Dependent Claim 34 words

The apparatus of claim 23 , wherein the rate controller arranges the at least one data cell into a per-flow queue based on a flow to which the at least one data cell belongs.

Claim 34

Dependent Claim 22 words

The apparatus of claim 31 , wherein the rate controller receives the at least one data cell on one of multiple inputs.

Claim 35

Dependent Claim 25 words

The apparatus of claim 31 , wherein the rate controller isolates the flow to which the at least one data cell belongs from misbehaving flows.

Claim 36

Dependent Claim 52 words

The apparatus of claim 31 , wherein the flow to which the at least one data cell belongs has a bandwidth guarantee, and the rate controller presents the flow to which the at least one data cell belongs to the arbiter at a rate corresponding to the bandwidth guarantee of the flow.

Claim 37

Dependent Claim 18 words

The apparatus of claim 23 , wherein the at least one data cell is a fixed length cell.

Claim 38

Dependent Claim 16 words

The apparatus of claim 23 , wherein the at least one data cell are ATM cells.

Claim 39

Dependent Claim 13 words

The apparatus of claim 23 , wherein the rate controller comprises a scheduler.

Claim 40

Dependent Claim 11 words

The apparatus of claim 37 , wherein the scheduler is QoS-capable.

Claim 41

Dependent Claim 20 words

The apparatus of claim 37 , wherein the scheduler is implementing a Rate-Controlled Smallest Eligible Finish Timer First (RSEFTF) algorithm.

Claim 42

Dependent Claim 34 words

The apparatus of claim 23 , wherein the rate controller processes at least one data cell received from an input link such that a predetermined bandwidth rate for the input link is not exceeded.

Claim 43

Dependent Claim 19 words

The apparatus of claim 23 , wherein the rate controller fragments the at least one data cell into fragments.

Claim 44

Dependent Claim 28 words

The apparatus of claim 41 , wherein the fragments are assigned to a per-flow queue corresponding to a flow to which the at least one data cell belongs.

Claim 45

Dependent Claim 14 words

The apparatus of claim 23 , further comprising output queues at the identified output.

Claim 46

Dependent Claim 36 words

The apparatus of claim 43 , wherein the arbiter controls the connection of the at least one data cell to the identified output of the crossbar switch based on an occupancy characteristic of the output queues.

Claim 47

Independent Claim 65 words

A method for transferring packets from input ports to output ports comprising: receiving packets at the input ports; fragmenting the packets into cells; arranging the cells into per-flow queues based on flows to which the packets belong; scheduling the cells for transfer according to a Rate-Controlled Eligible Finish Time First (RSEFTF) algorithm; and transferring the cells to the output ports according to a work-conserving algorithm.

Claim 48

Independent Claim 65 words

A method for transferring packets from input ports to output ports comprising: receiving packets at the input ports; fragmenting the packets into cells; arranging the cells into per-flow queues based on flows to which the packets belong; scheduling the cells for transfer according to a Rate-Controlled Eligible Finish Time First (RSEFTF) algorithm; and transferring the cells to the output ports according to a work-conserving algorithm.

Claim 49

Dependent Claim 23 words

The method of claim 45 , wherein the act of transferring further comprises transferring according to a Lowest Occupancy Output First Algorithm (LOOFA).

Claim 50

Dependent Claim 23 words

The method of claim 45 , wherein the act of transferring further comprises transferring according to a Most Urgent Cell First Algorithm (MUCFA).

Claim 51

Dependent Claim 39 words

The method of claim 45 , wherein a work-conserving algorithm is defined as: when at least one input cell is available for arbitration to be sent to an output port, a cell will be transmitted from the output port.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2008-03-07	2008-09-06	2009-03-08	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2012-03-07	2012-09-06	2013-03-08	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2016-03-07	2016-09-06	2017-03-08	$7700.00	Window Closed / Lapsed

Method and apparatus for providing bandwidth and delay guarantees in combined input-output buffered crossbar switches that implement work-conserving arbitration algorithms

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag