Multicast cell buffer for network switch
View Patent ↗An input port for a network switch includes a cell buffer for receiving incoming unicast and multicast cells and for writing each cell into an internal cell memory. The cell buffer thereafter forwards each unicast cell from the cell memory to one network switch output port and forwards a separate copy of each multicast cell to each of several network switch output ports. When the cell buffer writes a unicast cell to the cell memory, it sends a pointer to the storage location of the unicast cell to a queue manager. When the cell buffer writes a multicast cell to the cell memory, it sends several pointers to the queue manager, one for each output port that is to receive a copy of the multicast cell, with each pointer pointing not to the multicast cell's storage location but to an empty storage location in the cell memory. The cell buffer also maintains a database relating each pointer it sent to the queue manager to an actual storage location of a unicast or multicast cell. The queue manager queues the pointers an order in which cells are to be forwarded from the cell buffer, and thereafter returns a pointer to the cell buffer whenever the cell buffer is to forward a unicast cell or a copy of a multicast cell from the cell memory. The cell buffer applies each returned pointer to the database to determine the actual location of the unicast or multicast cell to be forwarded.
1. An apparatus for receiving, storing and forwarding multicast cells and unicast cells, the apparatus comprising:
a cell buffer, including a plurality of storage locations and a first database, for receiving and writing a multicast cell into a first one of its plurality of storage locations, for thereafter generating a plurality of first pointers, each referencing a separate one of said plurality of storage locations other than the first storage location to which the multicast cell was written, and for creating a separate entry in its first database for each generated first pointer, the entry relating the first pointer to the first storage location to which the multicast cell was written; and
a queue manager for receiving the first pointers generated by the cell buffer and for thereafter returning the first pointers to the cell buffer,
wherein upon receiving each first pointer returned by the queue manager, the cell buffer consults the first pointer's entry in the first database to determine the first storage location the entry relates to the first pointer, and then reads an instance of the multicast cell out of that first storage location.
2. The apparatus in accordance with claim 1
wherein the cell buffer also receives and writes a unicast cell into a second one of the storage locations, forwards a single second pointer to the queue manager referencing the second storage location, and thereafter creates another entry in the first database for the second pointer relating the second pointer to the second storage location,
wherein the queue manager also receives and stores the second pointer generated by the cell buffer and thereafter returns the second pointer to the cell buffer, and
wherein upon receiving the second pointer returned by the queue manager, the cell buffer consults the second pointer's entry in the first database to determine the second storage location the entry relates to the second pointer, and then reads the unicast cell out of the second storage location.
3. The apparatus in accordance with claim 1
wherein the multicast cell includes a multicast flow identification number (FIN) having a value identifying the multicast cell as forming a part of an incoming sequence of cells,
wherein the cell buffer further includes a second database relating the multicast FIN's value to a plurality of child FINs having values differing from the multicast FIN value,
wherein each child FIN identifies a corresponding instance of the multicast cell to be read out of the first storage location as forming a part of a separate outgoing sequence of cells,
wherein the cell buffer reads the multicast FIN included in the multicast cell when it stores the multicast cell in the first storage location and thereafter consults the second database to determine the plurality of child FINs related to the multicast FIN, generates a separate one of the first pointers corresponding to each of the child FINs, arid forwards each first pointer with its corresponding child FIN to the queue manager, and
wherein the queue manager makes a determination as to when to return each first pointer to the cell buffer stored as the value of its corresponding child FIN.
4. The apparatus in accordance with claim 3
wherein the cell buffer maintains a tree list of pointers, each referencing a separate one of the plurality of storage locations that is available for storing a cell,
wherein the cell buffer obtains a pointer to the first storage location from the free list when it writes the multicast cell to the first storage location, and then removes that pointer from The free list.
5. The apparatus in accordance with claim 4 wherein the cell buffer generates each of the first pointers by obtaining it from the free list and thereafter removes each of the first pointers from the free list.
6. The apparatus in accordance with claim 5 wherein whenever the queue manager returns any one of the first pointers to the cell buffer, the cell buffer returns that first pointer to the free list.
7. The apparatus in accordance with claim 6 wherein the cell buffer maintains a first pointer count, wherein the cell buffer increments the first pointer count whenever it sends one of the first pointers to the queue manger, and decrements the first pointer count whenever the queue manager returns one of the first pointers.
8. The apparatus in accordance with claim 7 wherein the cell buffer returns a pointer to the first storage location to the free list when the count indicates the queue manager has returned all of the plurality of first pointers to the cell buffer.
9. The apparatus in accordance with claim 8
wherein the cell buffer also receives a unicast cell, obtains a second pointer to a second storage location from the free list, forwards the second pointer to the queue manager, removes the second pointer from the free list, and thereafter creates another entry in the first database relating the second pointer to the second storage location,
wherein the queue manager also receives and stores the second pointer generated by the cell buffer, and thereafter returns the second pointer to the cell buffer, and
wherein upon receiving each second pointer from the queue manager, the cell buffer consults the second pointer's entry in the first database to determine the second storage location referenced thereby, and then reads the unicast cell out of the referenced storage location arid returns the second pointer to the free list.
10. The apparatus in accordance with claim 9 further comprising:
a switch interface circuit for receiving each instance of the multicast cell that the cell buffer reads out of the first storage location in response to each first pointer returned by the queue manager;
a plurality of output ports, each for receiving, storing and forwarding cells; and
a switch fabric for providing paths for conveying cells from the switch interface circuit to each of the plurality of output ports,
wherein the switch interface circuit forwards each instance of the multicast cell to a separate one of the output ports via the paths provided by the switch fabric.
11. The apparatus in accordance with claim 10
wherein the queue manager includes a third database relating each child FIN to one of a plurality of virtual output queues, each virtual output queue (VOQ) corresponding to a separate one of the output ports,
wherein when the queue manager returns any aria of the first pointers to the cell buffer, it also sends to the cell butter a VOQ number identifying the VOQ to which the third database relates the first pointer's corresponding child FIN,
wherein when the cell buffer reads the multicast cell out of the first storage location upon receiving that first pointer, it forwards the multicast cell and the VOQ number it received from the queue manager to the switch interface circuit, and
wherein the switch interface circuit forwards the received multicast cell to the output port associated with the VOQ identified by the VOQ number it received with the multicast cell.
12. The apparatus in accordance with claim 3 further comprising;
a switch interface circuit for receiving each instance of the multicast cell that the cell buffer reads out of the first storage location in response to each first pointer returned by the queue manager;
a plurality of output ports, each for receiving, storing and forwarding cells; and
a switch fabric for providing paths for conveying cells from the switch interface circuit to each of the plurality of output ports,
wherein The switch interface circuit forwards each instance of the multicast cell to a separate one of the output ports via the paths provided by the switch fabric.
13. The apparatus in accordance with claim 12
wherein the queue manager includes a third database relating each child FIN to one of a plurality of virtual output queues, each virtual output queue (VOQ) corresponding to a separate one of the output ports,
wherein when the queue manager returns any one of the first pointers to the cell buffer, it also sends to the cell buffer a VOQ number identifying the VOQ to which the third database relates the first pointer's corresponding child FIN,
wherein when the cell buffer reads the multicast cell out of the first storage location upon receiving that first pointer, it forwards the multicast cell and the VOQ number it received from the queue manager to the switch interface circuit, and
wherein the switch interface circuit forwards the received multicast cell to the output port associated with the VOQ identified by the VOQ number it received with the multicast cell.
14. The apparatus in accordance with claim 1 further comprising:
a switch interface circuit for receiving each instance of the multicast cell that the cell buffer reads out of the first storage location in response to each first pointer returned by the queue manager;
a plurality of output ports, each for receiving, storing and forwarding cells; and
a switch fabric for providing paths for conveying cells from the switch interface circuit to each of the plurality of output ports,
wherein the switch interface circuit forwards each instance of the multicast cell to a separate one of the output ports via the paths provided by the switch fabric.
15. A method for receiving, storing and forwarding multicast cells and unicast cells, the method comprising the steps of:
a. receiving and writing a multicast cell into a first one of a plurality of storage locations;
b. generating a plurality of first pointers, each referencing a separate one of said plurality of storage locations other than the first storage location to which the multicast cell was written,
c. creating a separate entry in a first database for each generated first pointer, the entry relating the first pointer to the first storage location to which the multicast cell was written;
d. sending the first pointers to a queue manage which stores the first pointers and controls when instances of the multicast cells are read out of the first storage location by thereafter sequentially providing the first pointers as output; and
e. responding to each first pointer the queue manager provides as output by consulting the first pointer's entry in the first database to determine the first storage location that the entry relates to the first pointer and then reading an instance of the multicast cell out of that first storage location.
16. The method in accordance with claim 15 further comprising the steps of:
f. receiving and writing a unicast cell into a second one of the storage locations;
g. creating an entry in the first database for the second pointer relating the second pointer to the second storage location;
h. forwarding a single second pointer to the queue manager referencing the second storage location, wherein the queue manager also receives and stores the second pointer and thereafter provides the second pointer as output; and
i. responding to the second pointer when provided as output by the queue manager by consulting the second pointer's entry in the first database to determine the second storage location the entry relates to the second pointer and then reading the unicast cell out of the second storage location.
17. The method in accordance with claim 15 wherein the multicast cell includes a multicast flow identification number (FIN) having a value identifying the multicast cell as forming a part of a sequence of multicast cells, the method further comprising the steps of:
f. reading the multicast FIN included in the multicast cell;
g. consulting a second database to determine a plurality of child FINs the second database relates to the multicast FIN, each of the first pointers generated at step b corresponding to a separate one of the child FINs, wherein each child FIN identifies a corresponding instance of the multicast cell to be read out of the first storage location as forming a part of a separate outgoing sequence of cells; and
h. forwarding each child FIN to the queue manager with a corresponding one of the pointers sent at step b, wherein the queue manager determines a time at which to provide each first pointer as output based on a value of its corresponding child FIN.
18. The method in accordance with claim 17 further comprising the steps of:
i. maintaining a free list of pointers, each referencing a separate one of the plurality of storage locations that is available for storing a cell,
j. obtaining a pointer to the first storage location from the free list when writing the multicast cell to the first storage location, and then
k. removing that pointer from the free list.
19. The method in accordance with claim 18 wherein each of the first pointers is generated at step b by obtaining them from the free list, wherein the method further comprises the step of:
l. removing each of the first pointers from the free list after forwarding the first pointers to the queue manager.
20. The method in accordance with claim 19 further comprising the step of
m. adding each of the first pointers to the free list when provided as output by the queue manger.
21. The method in accordance with claim 20 further comprising the steps of:
n. incrementing a first pointer count whenever one of the first pointers is sent to the queue manger,
o. decrementing the first pointer count whenever the queue manager provides one of the first pointers as output, and
p. adding a pointer to the first storage location to the free list when the count indicates the queue manager has provided each one of the plurality of first pointers as output.
22. The method in accordance with claim 21 further comprising the steps of:
q. forwarding each instance of the multicast cell read out of the first storage location in response to each first pointer provided by the queue manager as output to a separate destination.
23. The method in accordance with claim 22 wherein the queue manager includes a third database relating each child FIN to one of a plurality of virtual output queues, each virtual output queue (VOQ) corresponding to a separate multicast cell destination, wherein when the queue manager provides any one of the first pointers as output, it also provides as output a VOQ number identifying the VOQ to which the third database relates the first pointer's corresponding child FIN, and wherein each instance of the multicast cell is forwarded at step g in response to each first pointer to the destination corresponding to the VOQ identified by the VOQ number the queue manager provided as output with the first pointer.