US5978359A — Allocated and dynamic switch flow control

Claim 1

Independent Claim 213 words

A method for controlling flow of a data unit within a network switch, comprising the steps of: receiving the data unit in the switch, the data unit being received at an input port associated with an input queue, the input queue associated with at least one input buffer; storing the data unit in the at least one input buffer associated with the input queue; forwarding a request to transmit the data unit to at least one output buffer associated with an output queue, the output queue associated with an output port; providing, by the output port in response to the request to transmit, a feedback message to the input port indicating to cease forwarding requests to transmit data units from the at least one input buffer associated with the input queue to the at least one output buffer associated with the output queue in the event that a total number of the output buffers associated with the output queue and available for data unit storage is less than a predetermined threshold; and ceasing forwarding requests to transmit data units from the at least one input buffer associated with the input queue to the at least one output buffer associated with the output queue, responsive to receiving the feedback message by the input port.

Claim 2

Independent Claim 213 words

A method for controlling flow of a data unit within a network switch, comprising the steps of: receiving the data unit in the switch, the data unit being received at an input port associated with an input queue, the input queue associated with at least one input buffer; storing the data unit in the at least one input buffer associated with the input queue; forwarding a request to transmit the data unit to at least one output buffer associated with an output queue, the output queue associated with an output port; providing, by the output port in response to the request to transmit, a feedback message to the input port indicating to cease forwarding requests to transmit data units from the at least one input buffer associated with the input queue to the at least one output buffer associated with the output queue in the event that a total number of the output buffers associated with the output queue and available for data unit storage is less than a predetermined threshold; and ceasing forwarding requests to transmit data units from the at least one input buffer associated with the input queue to the at least one output buffer associated with the output queue, responsive to receiving the feedback message by the input port.

Claim 3

Dependent Claim 95 words

The method of claim 1 wherein a plurality of data units are received in a plurality of input queues and said forwarding a request step includes the further step of forwarding a request from each respective one of said plurality of input queues in receipt of at least one of said plurality of data units to respective ones of a plurality of output queues for which each respective one of said plurality of data units is destined, each request to transmit being specific to the respective input and output queues on a per transmission basis.

Claim 4

Dependent Claim 29 words

The method of claim 1 further comprising assigning the input queue and the output queue to a selected connection, whereby flow control is executed on a per connection basis.

Claim 5

Dependent Claim 50 words

The method of claim 1 wherein the feedback message includes a first signal indicating acceptance or rejection of the submitted request, the data unit being transmitted to the output queue if the first signal indicates acceptance, and not being transmitted to the output queue if the first signal indicates rejection.

Claim 6

Dependent Claim 31 words

The method of claim 4, wherein said transmitting includes transmitting the data unit to a plurality of output queues, wherein each such output queue is associated with a different output port.

Claim 7

Dependent Claim 48 words

The method of claim 4 further comprising assigning the input queue and the output queue to a selected service class, wherein each service class is associated with a transmission priority level and requests to transmit are accepted and rejected based at least in part on such priority level.

Claim 8

Dependent Claim 79 words

The method of claim 4 wherein at least one connection is established through the switch and including the further step of assigning the input queue and the output queue to a selected connection and a selected service class, wherein each service class is associated with a transmission priority level, whereby flow control is executed on a per connection, per service class basis, and requests to transmit are accepted and rejected based at least in part on such priority level.

Claim 9

Dependent Claim 22 words

The method of claim 4 wherein a subsequent request to transmit is forwarded after a delay if the first signal indicates rejection.

Claim 10

Dependent Claim 66 words

The method of claim 4 further comprising providing a second signal in the feedback message indicating either an instruction to cease forwarding requests to transmit or no operation as part of the feedback message, wherein each input queue receiving an instruction to cease forwarding requests to transmit ceases submitting requests to tranmit to such output queue having provided such instruction to cease forwarding requests to transmit.

Claim 11

Dependent Claim 162 words

The method of claim 9 wherein at least one inputted data unit is received in at least one input queue and said forwarding a request step includes the further step of forwarding a request from each respective input queue of the at least one input queue in receipt of the at least one inputted data unit to respective output queues of at least one output queue for which each respective inputted data unit of the at least one inputted data unit is destined, each request to transmit being specific to the respective input and output queues on a per transmission basis, and including, in the case of transmission from a single input queue to a plurality of output queues, the further step of performing a logical OR operation on the respective first and second signals of the feedback messages from the at least one output queue such that transmission from a single input queue to a plurality of output queues is contemporaneous.

Claim 12

Dependent Claim 45 words

The method of claim 10 including, in the case of transmission from a plurality of input queues to a particular output queue, the further step of setting the threshold to provide sufficient buffers for contemporaneous receipt of data units from the plurality of input queues.

Claim 13

Dependent Claim 61 words

The method of claim 9 including the further step of providing a third signal in a subsequent feedback message to countermand the instruction to cease forwarding requests to transmit by re-enabling the input queue to forward requests to transmit to the output queue when sufficient buffers become available for receipt of a predetermined number of data units by said output queue.

Claim 14

Dependent Claim 29 words

The method of claim 12 including the further step of providing the third signal upon dequeueing a data unit from the one of the at least one output queue.

Claim 15

Dependent Claim 34 words

The method of claim 12 including providing the third signal when the total number of output buffers available for data unit storage and associated with the output queue is greater than the predetermined threshold.

Claim 16

Dependent Claim 32 words

The method of claim 12 including the further step of providing the third signal to the input queue after passage of a predetermined period of time following transmission of the second signal.

Claim 17

Dependent Claim 22 words

The method of claim 12 including the further step of providing the third signal to the input queue on a periodic basis.

Claim 18

Dependent Claim 24 words

The method of claim 12 including the further step of providing the third signal from the output queue to a plurality of input queues.

Claim 19

Dependent Claim 49 words

The method of claim 1 including the further step of organizing the input buffers and output buffers into a hierarchy of levels with multiple individual flows of data units at each hierarchical level, wherein feedback messages are provided for each level based on combined flow at the respective level.

Claim 20

Dependent Claim 42 words

The method of claim 1 including the further step of organizing the input buffers and output buffers into a hierarchy of levels with multiple individual flows of data units at each hierarchical level, wherein feedback messages are provided for each individual flow.

Claim 21

Dependent Claim 18 words

The method of claim 1 wherein the request to transmit is a request to transmit utilizing dynamic bandwidth.

Claim 22

Dependent Claim 46 words

The method of claim 20, wherein the feedback message indicates to cease forwarding requests to transmit utilizing dynamic bandwidth to the output queue, and wherein the input queue, responsive to receiving the feedback message, ceases forwarding requests to transmit utilizing dynamic bandwidth to the output queue.

Claim 23

Dependent Claim 18 words

The method of claim 1 wherein the request to transmit is a request to transmit utilizing allocated bandwidth.

Claim 24

Dependent Claim 46 words

The method of claim 22, wherein the feedback message indicates to cease forwarding requests to transmit utilizing allocated bandwidth to the output queue, and wherein the input queue, responsive to receiving the feedback message, ceases forwarding requests to transmit utilizing allocated bandwidth to the output queue.

Claim 25

Dependent Claim 257 words

A network switch for controlling flow of at least one data unit within a telecommunications network, comprising: at least one input port for receiving the at least one data unit into the switch; at least one output port for transmitting the at least one data unit out of said switch; at least one input buffer queue associated with said at least one input port for enqueuing the at least one data unit received at the at least one input port; at least one output buffer queue associated with said at least one input buffer queue for receiving and temporarily storing the at least one data unit from said at least one input buffer queue; at least one transmission request generator operative to generate one or more requests for permission to transmit the at least one data unit from said at least one input buffer queue to said at least one output buffer queue; at least one feedback message generator operative to provide at least one feedback message to said at least one input buffer queue, said at least one feedback message including a signal having first and second states, said first and second states respectively indicating no operation and an instruction to cease sending requests for permission to transmit, and wherein each of said at least one input buffer queue receiving the signal in the second state from one or more of said at least one output buffer queue ceases submitting requests to transmit to said one or more of said at least one output buffer queue.

Claim 26

Dependent Claim 257 words

A network switch for controlling flow of at least one data unit within a telecommunications network, comprising: at least one input port for receiving the at least one data unit into the switch; at least one output port for transmitting the at least one data unit out of said switch; at least one input buffer queue associated with said at least one input port for enqueuing the at least one data unit received at the at least one input port; at least one output buffer queue associated with said at least one input buffer queue for receiving and temporarily storing the at least one data unit from said at least one input buffer queue; at least one transmission request generator operative to generate one or more requests for permission to transmit the at least one data unit from said at least one input buffer queue to said at least one output buffer queue; at least one feedback message generator operative to provide at least one feedback message to said at least one input buffer queue, said at least one feedback message including a signal having first and second states, said first and second states respectively indicating no operation and an instruction to cease sending requests for permission to transmit, and wherein each of said at least one input buffer queue receiving the signal in the second state from one or more of said at least one output buffer queue ceases submitting requests to transmit to said one or more of said at least one output buffer queue.

Claim 27

Dependent Claim 25 words

The switch of claim 24 wherein each one of said at least one output port includes one of said at least one feedback message generator.

Claim 28

Dependent Claim 49 words

The switch of claim 24 wherein a plurality of connections are established within the switch and each such connection utilizes one of said at least one input buffer queue and one of said at least one output buffer queue, whereby flow control is executed on a per connection basis.

Claim 29

Dependent Claim 47 words

The switch of claim 24 wherein one or more of said at least one input buffer queue and one or more of said at least one output buffer queue are assigned to a selected service class, whereby flow control is executed on a per service class basis.

Claim 30

Dependent Claim 64 words

The switch of claim 24 wherein a plurality of connections are established within the switch and each of said at least one input buffer queue and each of said at least one output buffer queue are assigned to a respective one of said plurality of connections and a selected service class, whereby flow control is executed on a per connection, per service class basis.

Claim 31

Dependent Claim 94 words

The switch of claim 24 including a logic circuit which, in the case of transmission from a single one of said at least one input buffer queue to a plurality of said at least one output buffer queue, performs a logical OR operation on the respective first and second signals of the feedback messages from said plurality of said at least one output buffer queue such that transmission from the single one of said at least one input buffer queue to the plurality of said at least one output buffer queue is serially contemporaneous.

Claim 32

Dependent Claim 92 words

The switch of claim 25 wherein, in the case of transmission from a plurality of said at least one input buffer queue to a particular one of said at least one output buffer queue, a dynamically adjustable threshold at which the first signal in the second state is provided in connection with the particular one of said at least one output buffer queue is increased in order to provide sufficient buffers for contemporaneous receipt of the at least one data unit from the plurality of said at least one input buffer queue.

Claim 33

Dependent Claim 59 words

The switch of claim 20 wherein said at least one input buffer queue and said at least one output buffer queue are each arranged in a hierarchy of levels with multiple individual flows of data units at each hierarchical level, said at least one feedback message being provided for each level based on combined flow at the respective level.

Claim 34

Dependent Claim 56 words

The switch of claim 24 wherein said at least one input buffer queue and said at least one output buffer queue are each arranged into a hierarchy of levels with multiple individual flows of data units at each hierarchical level, an individual one of said at least one feedback message being provided for each individual flow.

Claim 35

Dependent Claim 113 words

The network switch of claim 24, said at least one feedback message further comprising a second signal having a first state and a second state, wherein said first state indicates a grant of permission to transmit the at least one data unit from one or more of the at least one input buffer queue where the data unit is enqueued to one or more of said at least one output buffer queue and said second state indicates a denial of permission to transmit the enqueued data unit from the one or more of the at least one input buffer queue to said one or more of said at least one output buffer queue.

Claim 36

Dependent Claim 32 words

The switch of claim 32 wherein said at least one feedback message generator provides said at least one feedback message in response to said one or more requests for permission to transmit.

Claim 37

Dependent Claim 47 words

The switch of claim 32 wherein the at least one data unit is transmitted if the second signal indicates that permission to transmit is granted and the at least one data unit is not immediately transmitted if the second signal indicates that permission to transmit is denied.

Claim 38

Dependent Claim 58 words

The switch of claim 33 wherein a third signal is provided in said at least one feedback message to countermand the first signal in the second state by re-enabling one or more of said at least one input buffer queue to forward permission requesting signals to said one or more of said at least one output buffer queue.

Claim 39

Dependent Claim 29 words

The switch of claim 36 wherein said third signal is provided upon dequeueing a data unit from said one or more of said at least one output buffer queue.

Claim 40

Dependent Claim 62 words

The switch of claim 36 wherein a threshold is set in said one or more of said at least one output buffer queue, said third signal being provided when a total number of output buffers available to store said at least one data unit in said one or more of said at least one output buffer queue is greater than said threshold.

Claim 41

Dependent Claim 42 words

The switch of claim 31 wherein said third signal is provided to said one or more of said at least one input buffer queue after passage of a predetermined period of time following receipt of said second signal in the second state.

Claim 42

Dependent Claim 29 words

The switch of claim 31 wherein said third signal is provided to said one or more of said at least one input buffer queue on a regular time basis.

Claim 43

Dependent Claim 35 words

The switch of claim 31 wherein said third signal is provided from said one or more of said at least one output buffer queue to a plurality of said at least one input buffer queue.

Claim 44

Independent Claim 162 words

A method for controlling flow of at least one inputted cell within a network switch having a plurality of input buffers associated with at least one input queue and a plurality of output buffers associated with at least one output queue, the method comprising the steps of: receiving the at least one inputted cell in the switch, the cell being received in the input queue of the input memory; forwarding a request to transmit the at least one inputted cell to one of said at least one output queue; and asserting, when a traffic type cell count of all cells shared by all existing connections is not greater than or equal to a first limit and a dynamic buffer count associated with one of said at least one output queue is greater than or equal to a second limit, both a first signal denying said request and a second signal causing cessation of forwarding requests to transmit to the one output queue.

Claim 45

Independent Claim 162 words

A method for controlling flow of at least one inputted cell within a network switch having a plurality of input buffers associated with at least one input queue and a plurality of output buffers associated with at least one output queue, the method comprising the steps of: receiving the at least one inputted cell in the switch, the cell being received in the input queue of the input memory; forwarding a request to transmit the at least one inputted cell to one of said at least one output queue; and asserting, when a traffic type cell count of all cells shared by all existing connections is not greater than or equal to a first limit and a dynamic buffer count associated with one of said at least one output queue is greater than or equal to a second limit, both a first signal denying said request and a second signal causing cessation of forwarding requests to transmit to the one output queue.

Claim 46

Dependent Claim 56 words

The method of claim 42 including the further step of, when the traffic type cell count is not greater than or equal to the first limit and the dynamic buffer count associated with the one output queue is not greater than or equal to the second limit, asserting neither the first signal nor the second signal.

Claim 47

Dependent Claim 56 words

The method of claim 43 including the further step of, when the traffic type cell count is greater than or equal to the first limit and the dynamic buffer count associated with the one output queue is not greater than or equal to the second limit, not asserting the second signal and asserting the first signal.

Claim 48

Dependent Claim 54 words

The method of claim 44 including the further step of, when the traffic type cell count is greater than or equal to the first limit and the dynamic buffer count associated with the one output queue is greater than or equal to the second limit, asserting both the first signal and the second signal.

Claim 49

Dependent Claim 67 words

The method of claim 45 including the further step of, asserting neither the first signal nor the second signal when an allocated buffer-state count associated with the one output queue is greater than or equal to a second imit, the traffic type cell count is greater than or equal to the first limit, and an allocated buffer count is greater than or equal to a third limit.

Claim 50

Dependent Claim 33 words

The method of claim 46 including the further step of asserting both the first signal and the second signal when the allocated buffer count is greater than or equal to the third limit.

Claim 51

Dependent Claim 65 words

The method of claim 47 including the further step of, when the allocated buffer count is not greater than or equal to the third limit, but either the allocated buffer-state count is greater than or equal to the second limit or the traffic type cell count is greater than or equal to the first limit, asserting the second signal and not asserting the first signal.

Claim 52

Dependent Claim 28 words

The method of claim 48 including the further step of, when an output queue has already asserted the first signal, reasserting the first signal on a subsequent probe.

Claim 53

Independent Claim 196 words

A system for controlling flow of a received data unit in a network switch, comprising: an input queue associated with a receive buffer for storing the received data unit, the input queue associated with an input port, a first traffic type, and a first connection; a plurality of traffic type output queues associated with an output port, each one of the plurality of traffic type output queues further associated with a respective traffic type, each one of the traffic type output queues including a plurality of connection specific output queues; and a feedback message generator operative to determine whether there is insufficient buffer space in one of the connection specific output queues associated with the first connection included in one of the traffic type output queues associated with the first traffic type and the first output port, the feedback message generator further operative to provide a first feedback message to the input queue responsive to determining there is insufficient buffer space in the one of the connection specific output queues associated with the first connection included in the one of the traffic type output queues associated with the first traffic type and the first output port.

Claim 54

Independent Claim 196 words

A system for controlling flow of a received data unit in a network switch, comprising: an input queue associated with a receive buffer for storing the received data unit, the input queue associated with an input port, a first traffic type, and a first connection; a plurality of traffic type output queues associated with an output port, each one of the plurality of traffic type output queues further associated with a respective traffic type, each one of the traffic type output queues including a plurality of connection specific output queues; and a feedback message generator operative to determine whether there is insufficient buffer space in one of the connection specific output queues associated with the first connection included in one of the traffic type output queues associated with the first traffic type and the first output port, the feedback message generator further operative to provide a first feedback message to the input queue responsive to determining there is insufficient buffer space in the one of the connection specific output queues associated with the first connection included in the one of the traffic type output queues associated with the first traffic type and the first output port.

Claim 55

Dependent Claim 19 words

The system of claim 50, wherein the first feedback message denies a request to transmit the received data unit.

Claim 56

Dependent Claim 22 words

The system of claim 50 wherein the input queue is one of a plurality of input queues associated with the input port.

Claim 57

Dependent Claim 14 words

The system of claim 50 wherein the first traffic type is variable bit rate.

Claim 58

Dependent Claim 14 words

The system of claim 50 wherein the first traffic type is constant bit rate.

Claim 59

Dependent Claim 14 words

The system of claim 50 wherein the first traffic type is available bit rate.

Claim 60

Dependent Claim 45 words

The system of claim 50 wherein said feedback message generator is further operative to provide a second feedback message to the input queue responsive to determining there is sufficient buffer space in the one of the connection specific output queues associated with the first connection.

Claim 61

Dependent Claim 31 words

The system of claim 56, wherein the second feedback message enables transmission of the received data unit to the one of the connection specific output queues associated with the first connection.

Claim 62

Independent Claim 210 words

A method for controlling flow of a data unit within a network switch, comprising: receiving the data unit in the switch, the data unit being received at an input port associated with an input queue, the input queue associated with at least one input buffer; storing the data unit in the at least one input buffer associated with the input queue; at least at some times, forwarding a plurality of requests to transmit the data unit from the input port to a plurality of output queues, the plurality of output queues associated with a respective plurality of output ports; providing, by at least one of the respective plurality of output ports in response to the plurality of requests to transmit, a feedback message to the input port denying the request to transmit the data unit in the event that a total number of the output buffers associated with the respective output queue and available for data unit storage is less than are needed to store the data unit; and delaying transmission of the data unit from the input queue to the respective plurality of output ports in the event that the at least one of the output ports provides the feedback message denying the request to transmit the data unit.

Claim 63

Independent Claim 210 words

A method for controlling flow of a data unit within a network switch, comprising: receiving the data unit in the switch, the data unit being received at an input port associated with an input queue, the input queue associated with at least one input buffer; storing the data unit in the at least one input buffer associated with the input queue; at least at some times, forwarding a plurality of requests to transmit the data unit from the input port to a plurality of output queues, the plurality of output queues associated with a respective plurality of output ports; providing, by at least one of the respective plurality of output ports in response to the plurality of requests to transmit, a feedback message to the input port denying the request to transmit the data unit in the event that a total number of the output buffers associated with the respective output queue and available for data unit storage is less than are needed to store the data unit; and delaying transmission of the data unit from the input queue to the respective plurality of output ports in the event that the at least one of the output ports provides the feedback message denying the request to transmit the data unit.

Claim 64

Dependent Claim 40 words

The method of claim 58 further comprising forwarding the data unit to each of the plurality of output queues in the event that none of the to plurality of output ports provide the feedback message denying the request to transmit.

Claim 65

Dependent Claim 46 words

The method of claim 58 wherein the feedback message includes a bit indicating whether the request to transmit is granted or denied, and further comprising logically ORing the bit from a plurality of feedback messages to determine whether transmission of the data unit should be delayed.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-11-01	2003-05-03	2003-11-02	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-11-01	2007-05-03	2007-11-02	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-11-01	2011-05-03	2011-11-02	$7700.00	Window Closed / Lapsed

Allocated and dynamic switch flow control

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag