Resynchronization method and apparatus for local memory buffers management for an ATM adapter implementing credit based flow control

Claim 2

An asynchronous transfer mode (ATM) network device comprising: a receiver portion, said receiver portion capable of receiving a plurality of ATM cells on one of a plurality of virtual circuits (VCs) from an upstream ATM switch, the plurality of ATM cells resulting from a disassembly of a plurality of packets in the upstream ATM switch; a local memory, said local memory used to store the plurality of ATM cells; means for managing said local memory using a plurality of queues; means for assembling ATM cells into a plurality of packets in the local memory; means for transmitting said plurality of packets to a host memory; means for resynchronizing a plurality of ATM credits, each of said ATM credits representing an available buffer in the local memory to receive an ATM cell; and a transmitter portion, said transmitter portion having a means for indicating said transmitting of said packets to said host memory to said upstream ATM switch.

Claim 3

The ATM network device according to claim 1 wherein said local memory further comprises: a dynamic pool of memory in said local memory, said dynamic pool used to reassemble said plurality of ATM cells into a plurality of packets; and a static pool of memory in said local memory, said static pool used to store said plurality of ATM cells arriving from said upstream ATM switch.

Claim 4

The ATM network device according to claim 2 wherein the static pool of memory is sized as a minimum memory size said ATM network device requires to have as buffering in said local memory.

Claim 5

The ATM network device according to claim 2 wherein the static pool of memory is sized by taking a product of a number representing a VC and a number of initial credits per VC.

Claim 6

The ATM network device according to claim 2 wherein said local memory further comprises a plurality of reassembly queues for packet reassembly.

Claim 7

The ATM network device according to claim 5 wherein each of said plurality of reassembly queues comprise: an active queue; a plurality of stalled queues; and means for controlling an interaction between said active queue and said plurality of stalled queues.

Claim 8

The ATM network device according to claim 6 wherein said plurality of stalled queues comprise eight stalled queues.

Claim 9

The ATM network device according to claim 6 wherein said means for controlling said interaction between said active queue and said plurality of stalled queues comprises: means for receiving said plurality of ATM cells of a first virtual circuit (VC); means for determining where to place said plurality of ATM cells of said first VC in said plurality of queues; and means for returning an ATM credit to said upstream ATM switch.

Claim 10

The ATM network device according to claim 8 wherein one of said plurality of ATM credits is returned to said upstream ATM switch when said VC is placed in said active queue.

Claim 11

The ATM network device according to claim 8 wherein one of said plurality of ATM credits is stored in said local memory while said ATM cell of the VC is stored in one of said stalled queues.

Claim 12

The ATM network device according to claim 10 wherein said ATM credit is returned to said upstream ATM switch when said ATM cell of the VC is dequeued from said one of said stalled queues and enqueued to said active queue.

Claim 13

The ATM network device according to claim 8 wherein said means for determining comprises: means for storing in said local memory a list of supported VCs in a descriptor entry, said descriptor entry containing two pointers, said pointers used to form a doubly-linked list by which said active queue and said plurality of stalled queues are constructed, said descriptor entry having a counter entry, said counter entry used to indicate the number of VC in said doubly-linked list, said descriptor entry having a plurality of indicator variables; means for receiving a first VC; means for placing said first VC in said active queue; means for placing said first VC in one of said plurality of stalled queues; and means for moving said first VC in said one of said plurality of stalled queues to said active queue.

Claim 14

The ATM network device according to claim 12 wherein said plurality of indicator variables comprise: a VC queue variable, a value of said VC queue variable indicating whether said first VC is not queued at all, whether said first VC is queued in said active queue, and whether said first VC is queued in one of said plurality of said stalled queues; a VC credit count variable, said VC credit count variable indicating the number of ATM cells which said ATM device has received on said VC while queued in one of said plurality of said stalled queues; a VC count variable, said VC count variable indicating the number of ATM cells received by said ATM network device which belong to said VC; and a commitment counter, said commitment counter indicating the number of memory buffers the ATM network device is committed for.

Claim 15

The ATM network device according to claim 13 wherein said means for controlling said interaction between said active queue and one of said plurality of stalled queues further comprises: means for checking an initial available buffer size of said local memory; means for marking said initial available buffer size as committed; and means for changing said initial available buffer size, said means for changing comprising the steps of: committing a maximum packet on said VC when said packet is moved from one of said stalled queues to said active queue; adjusting said size by the size of the received packet if the packet has not been sent to said host memory to the difference between said maximum packet size and said size of said received packet size; and adjusting said size of said received packet if said packet is ready to be sent to said host memory and has not been sent to said host memory by said received packet.

Claim 16

The ATM network device according to claim 14 wherein said plurality of indicator variables further comprise: a free buffers variable, said free buffers variable containing a value which represents the sum of the dynamic pool of memory and the static pool of memory for all VCs destined to said active queue; a static buffers variable, said static buffers variable containing a value which represents a number of static pool of memory across all of said VCs destined to said active queue; a committed buffers variable, said committed buffers variable containing a value which represents a number of ATM cell buffers said ATM network device has committed to; and a maximum packet length variable, said maximum packet length variable containing a value which represents a maximum packet length on a plurality of VCs destined to said active queue.

Claim 17

The ATM network device according to claim 13 further comprising: means for managing said plurality of static pool of memory and dynamic pool of memory; and means for managing a return of credits from said transmitter portion to said upstream ATM switch.

Claim 18

The ATM network device according to claim 16 wherein said means for managing said plurality of static pool of memory and dynamic pool of memory comprises means for responding to the movement of one of said plurality of ATM cells, said means for responding operating according to a plurality of rules.

Claim 19

The ATM network device according to claim 17 wherein said plurality of rules comprise: a first rule, said first rule applied if said received ATM cell is a first ATM cell; a second rule, said second rule applied for every received ATM cell; a third rule, said third rule applied if said received ATM cell is said last ATM cell received; a fourth rule, said fourth rule applied when storing one of said plurality of packets in said host memory; a fifth rule, said fifth rule applied when determining when to activate one of said stalled queue; and a sixth rule, said sixth rule applied when activating said one stalled queue.

Claim 20

The ATM network device according to claim 18 wherein said first rule comprises the steps of: determining whether a value of said free buffers variable minus said committed buffers variable minus said maximum packet length variable is greater than said value of said static buffers variable; enqueuing said first ATM cell to said stalled queue if said value is not greater than said value of said static buffers variable; and enqueuing said VC to said active queue if said value is greater than said value of said static buffers variable.

Claim 21

The ATM network device according to claim 18 wherein said second rule comprises the steps of: decrementing said free buffers variable by one; incrementing said VC count variable by one; decrementing said committed buffers variable by one if said VC is in said active queue; decrementing said static buffers by one if said VC is in said stalled queue; and incrementing said VC credit count variable by one if said VC is in said stalled queue.

Claim 22

The ATM network device according to claim 18 wherein said third rule comprises the steps of: assigning said committed buffers variable the value of the committed buffers variable minus said maximum packet length variable plus said VC count variable if said VC is in said active queue; and setting the VC count variable equal to zero if said VC is in said active queue.

Claim 23

The ATM network device according to claim 18 wherein said fourth rule comprises the step of adding the number of cell buffers freed to said free buffers variable.

Claim 24

The ATM network device according to claim 18 wherein said fifth rule comprises the steps of: activating a VC if the value of free buffers minus committed buffers minus said maximum value of said VC credit count variable is greater than the value of said static buffers variable; and activating a VC if the value of free buffers minus committed buffers minus said maximum value of said VC credit count variable minus said maximum packet length minus said VC Count variable is greater than the value of said static buffers variable.

Claim 25

The ATM network device according to claim 18 wherein said sixth rule comprises the steps of: setting the value of said static buffers variable to said static buffers variable plus said VC credit count; dequeuing said VC from stalled queue; and setting the value of said committed buffers variable to committed buffers variable plus said maximum packet length variable minus aid VC count variable if aid packet has not completed reassembly.

Claim 26

The ATM network device according to claim 16 wherein said means for managing a return of credits from said transmitter portion to said upstream ATM switch comprises: a plurality of first-in-first out (FIFO) queues, a first FIFO queue used to store a plurality of credits scheduled to be returned, a second FIFO queue used to store aid VC number as a credit; and arbitration means to determine from which of said FIFOs to return credits.

Claim 27

The ATM network device according to claim 25 wherein said arbitration means comprises a 1-of-N arbitration method.

Claim 28

The ATM network device according to claim 13 wherein the means for resynchronizing the plurality of credits comprises: means for detecting in said transmitter portion a plurality of events which indicate ATM credit resynchronization; means for generating a credit resynchronization request in said transmitter portion in response to said means for detecting; means for sending said credit resynchronization request to said receiver portion; means for moving a selected virtual circuit in one of the plurality of stalled queues to the head of said queue; means for acknowledgements in said activate queue; means for setting a resynchronization flag to "ON" in said activate queue; means for informing said receiver portion when said resynchronization flag is "ON"; means for informing said receiver portion when a plurality of ATM credits have departed from said activate queue; and means, in said receiver portion, for sending a resynchronization complete message to said transmitter portion.