Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1998-03-30
2001-10-30
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S395430, C370S412000, C370S429000, C711S005000
Reexamination Certificate
active
06310875
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to multicasting in a communications network and, more particularly, to a method and apparatus for port memory multicast cell tracking in common memory switches for use in an asynchronous transfer mode (ATM) network.
ATM networks pass data in the form of cells. The cells, which are of fixed size, pass through one or more switches on the way to a specified destination that may be another switch, a terminal, or some other component in the network. An individual cell may need to be sent to several different destinations in the network from a single switch.
For purposes of this discussion, the term “multicasting” refers to the distribution of a cell to multiple destinations. When multicasting, an individual cell is copied in a switch, and the copies are sent to multiple destinations from the switch. In a common memory switch, the cell copying operation can be efficiently achieved by storing the cell in memory and generating multiple copies of the cell memory location (the cell address). Each copy of the cell address is stored at an output queue of the switch. A count memory stores a count of the number of copies of the cell made and transmitted. As copies of the cell exit the switch, the count in the count memory decrements. When the last cell copy is transmitted, the value of the count in the count memory is zero. At this point the address can be reused for another cell and is returned to a list of free memory locations.
One known multicast cell counting implementation uses a single memory to count the cell copies exiting the switch.
FIG. 1
is useful for discussing the single memory multicast count implementation. This implementation requires several memory operations to track cell copies. The cell count value (ie., the number of copies of the cell to be transmitted) is written to the memory
10
on enqueue, i.e., when a cell enters the switch (step
12
). When a cell leaves the switch, the cell count value is read (step
14
) from the multicast count memory and decremented (step
16
). The decremented count value is then written to and stored in the multicast count memory (step
18
). A cell count value of zero indicates all cell copies have been transmitted from the switch to the intended destinations.
This approach thus requires three memory accesses on the memory per cell cycle. For purposes of this discussion, a cell “cycle” is the enqueuing of a single cell to a switch and the dequeuing of that cell from the switch. Since three memory accesses are performed for each cell cycle, the memory must function three times as fast as the cell rate. This performance requirement for the memory greatly limits the types of memory that can successfully perform the task of multicast counting in high capacity common memory switches. Generally, only small, fast memories are capable of supporting this implementation. This limits the capacity of the switch or restricts the number of memory locations that can be used for multicast cells, as the multicast counting operation is the most demanding (in terms of memory bandwidth) in a common memory switch.
Another known cell counting implementation is disclosed and claimed in U.S. patent application Ser. No. 08/994,792, titled “Method and Apparatus for Banked Multicast Common Memory Switches” and filed on Dec. 19, 1997, which is hereby expressly incorporated by reference. In this implementation, two separate memories are used to count cell copies to be transmitted, resulting in a reduced number of memory accesses per memory per cycle. While this approach is an improvement over the single memory implementation, it can not dequeue cells at the full rate when commercial L2 cache memory and banking techniques are used.
It is, therefore, desirable to provide a method and apparatus for multicasting incorporating a cell tracking strategy having a reduced number of per-memory accesses and capable of cell dequeue rates that permit use of commercial memories.
SUMMARY OF THE INVENTION
The present invention satisfies this and other desires by providing a port memory multicast common memory switch and associated control strategy providing multicast cell counting having a reduced number of per memory accesses per cycle and supporting full rate cell dequeue.
A method for tracking multicast cell copies in a switch in an ATM network consistent with the present invention includes the steps of enqueuing a cell into the switch, and receiving a bit map into a port memory controller on the enqueue of a cell into the switch, the bit map including a bit corresponding to each output port register. The method also includes the step of writing to each output port register a bit from the bit map corresponding to that port register. The method further includes the steps of, on a cell dequeue, clearing the bit in the output port register associated with the output port from which the cell was dequeued, and reading the bits in the other output port registers. When all bits have been cleared, the cell has been sent out the appropriate number of times and the cell address may be used to store other cells.
An apparatus for tracking multicast cell copies and including a plurality of output ports from which cell copies are transmitted toward destinations includes a plurality of output port registers, each output port register being associated with at least one switch output port, and a port memory controller for receiving a bit map on the enqueue of a cell into the switch. The bit map includes a bit corresponding to each output port register, and the controller includes means for writing to each output port register the bit from the bit map corresponding to that port register.
Another method consistent with the present invention tracks multicast cell copies in a switch including a port memory controller and a plurality of groups of output ports, each group having an associated output port register. The method includes the steps of enqueueing into the switch a cell to be dequeued from the switch, and receiving a bit map into the port memory controller on the cell enqueue, the bit map including a bit corresponding to each output port register. The method also includes the steps of writing to each output port register the bit from the bit map corresponding to that output port register, the bit indicating that at least one copy of the enqueued cell is to be dequeued from the group of output ports associated with that output port register; and maintaining a count of the copies of the cell that have been dequeued from each group of output ports. The method also includes the steps of determining when the last copy of the cell has been dequeued from a group of output ports; and clearing the bit in the output port register after the last copy of the cell has been dequeued from the group associated with the output port register.
Another apparatus consistent with the present invention tracks multicast cell copies and includes a plurality of output ports from which cell copies are dequeued toward destinations. The apparatus includes a plurality of output port registers, each output port register being associated with a group of switch output ports, and first and second multicast cell count memories for storing a cell count value used to determine when a last cell copy has been transmitted from a group of switch output ports. The apparatus also includes a port memory controller for receiving a bit map on the enqueue of cell into the switch, the bit map including a bit for each output port register.
Yet still another apparatus consistent with the present invention tracks multicast cell copies and includes a plurality of output ports from which cell copies are transmitted toward destinations. The apparatus includes a plurality of output port registers, each output port register being associated with at least one switch output port, and first and second port memory controllers, at least one of the controllers receiving a bit map on the enqueue of a cell into the switch, the bit map including a bit corresponding to each output port register
Brown David A.
Nichols Stacy W.
Stuart David G.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Hsu Alpus H.
Nortel Networks Limited
Qureshi Afsar M.
LandOfFree
Method and apparatus for port memory multicast common memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for port memory multicast common memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for port memory multicast common memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605774