Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-12-19
2001-02-06
Vincent, David R. (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395430
Reexamination Certificate
active
06185206
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to multicasting in a data processing network and, more particularly, to a method and apparatus for banked multicast 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 which 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 multicast, 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 of the number of copies of the cell made and transmitted is stored in a count memory. As copies of the cell exit the switch, the count memory is decremented. When the last cell copy is issued, the count memory is reduced to zero (“0”). At this point the address can be reused for another cell and is returned to a list of free memory locations.
Referring now to
FIG. 1
, there is shown a block diagram of common memory switch
100
capable of performing multicasting. As shown, switch
100
includes a data store
102
, which acts as a central buffer where incoming cells
104
are stored. Common memory switch
100
also contains a multicast count memory
106
, which may be used to keep track of the number of copies of the cell produced for purposes of maintaining a list of free memory address spaces in the data store
102
.
Known multicast cell counting implementations use a single memory to count the cell copies exiting the memory switch.
FIG. 2
is useful for discussing the single memory multicast count implementation. This implementation requires several memory operations to track cell copies. The cell count value is written to the memory on enqueue, i.e., when a cell enters the switch (step
200
). When the cell leaves the switch, the cell count value is read (step
202
) from the multicast count memory and decremented (step
204
). The decremented count value is then written to and stored in the multicast count memory (step
206
). 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 subsequent dequeuing of that cell from the switch. Since three memory accesses are performed for each cell arrival, the memory must function generally three times as fast as the cell arrival rate. This performance requirement for the memory greatly limits the types of memory that can successfully perform the task of multicast counting in common memory switches. Generally, only small, fast memories are capable of supporting multicasting. 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.
It is, therefore, desirable to provide a method and apparatus for multicasting incorporating a cell counting strategy having a reduced number of per-memory accesses. Such a method and apparatus for multicasting would in turn feature a memory capable of operating at a reduced speed relative to the cell arrival rate compared to existing implementations, broadening the variety of memories available for performing multicast cell counting. The ability to use a wider variety of memories yields cost savings and allows higher capacity switches to be built.
SUMMARY OF THE INVENTION
The present invention satisfies this and other desires by providing banked memories for tracking cell copies during multicasting.
A method for counting multicast cell copies in a switch in an ATM network consistent with the present invention includes the steps of writing a cell count value to a first memory on a cell enqueue, and retrieving the cell count value from the first memory after a first cell dequeue. The method further includes the steps of decrementing the cell count value to reflect the first cell dequeue, and transferring the decremented cell count value to a second memory.
Apparatus and networks are also provided for carrying out methods consistent with the present invention.
The advantages accruing to the present invention are numerous. For example, the use of separate memories for enqueuing and dequeuing a multicast cell count value spreads the memory accesses over multiple memories, yielding a reduction in the number of per memory accesses per cell cycle. This, in turn, lowers the memory speed requirement.
The above desires, other desires, features, and advantages of the present invention will be readily appreciated by one of ordinary skill in the art from the following detailed description of the preferred implementations when taken in connection with the accompanying drawings.
REFERENCES:
patent: 5111385 (1992-05-01), Hattori
patent: 5724358 (1998-03-01), Headrick et al.
patent: 5875189 (1999-02-01), Brownhill et al.
patent: 5903564 (1999-05-01), Ganmukhi et al.
patent: 5917819 (1999-06-01), Yang et al.
patent: 6009078 (1999-12-01), Sato
Brown David A.
Nichols Stacy W.
Stuart David G.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Nortel Networks Limited
Vincent David R.
LandOfFree
ATM switch which counts multicast cell copies and uses a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with ATM switch which counts multicast cell copies and uses a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ATM switch which counts multicast cell copies and uses a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2604813