Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2002-04-30
2004-07-20
Nguyen, Chau (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
C370S395100, C370S412000, C370S432000, C370S468000
Reexamination Certificate
active
06765867
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to Asynchronous Transfer Mode communications devices. More particularly, the invention relates to methods and apparatus for buffering ATM cells, particularly during multicasting.
2. State of the Art
ATM, by nature, is “bursty”. Consequently, buffers must be provided in ATM devices so that cell loss is minimized. If one buffer is shared by more than one physical destination (PHY), an adverse effect known as “head of line blocking” can occur. Head of line blocking occurs when a cell at the head of a buffer cannot be transmitted to its PHY because of any number of reasons. This cell then blocks the transmission of all of the cells behind it. Head of line blocking can be avoided by providing separate buffers for each PHY in an ATM device. However, this can be costly and space consuming.
In an ATM network, it is often desirable to effect a multicast of ATM cells; i.e., to transport ATM cells from a source terminal to a plurality of different destinations. Each of the destinations of the multicast will typically have its own address. Thus, it is necessary to duplicate the ATM cells, provide different headers for each of the cells, and send the cells out on different virtual circuits (VCs). The different VCs may be located at different PHYs in the case of a spatial multicast or the same PHY in the case of a logical multicast. In the case of spatial multicast, extensive buffering may be necessary in order to accommodate all of the copies of each incoming multicast cell. It will be appreciated that the outgoing buffers will rapidly fill with copies of each single incoming multicast cell. In order to reduce the amount of buffer space required for multicasting, it is known to use a single buffer for multicast incoming cells and to replicate the cells just as they are ready to be transmitted out of the switch. Although this saves buffer space, it makes head of line blocking a more likely occurrence.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide methods and apparatus for preventing head of line blocking in an ATM device.
It is also an object of the invention to provide methods and apparatus for preventing head of line blocking in an ATM device which do not require extensive use of buffer memory.
In accord with these objects which will be discussed in detail below, the apparatus of the present invention includes a UTOPIA interface, a scheduler, at least one multicast queue, at least one unicast queue, a multicast session table, a multicast timer, and a problem PHY vector. The methods of the invention include alternate scheduling between multicast queue(s) and unicast queue(s). In particular, the PHY devices are serviced in round robin or other fair scheduling order. According to first embodiment, which is not the presently preferred embodiment, as each PHY is serviced, it is determined whether there exists a unicast cell or a multicast cell or both for this PHY. If both unicast and multicast cells are scheduled for this PHY, scheduling is alternated between them. If only unicast or multicast cells are scheduled for this PHY, alternation is not necessary.
For purposes of this invention, the act of replicating a multicast cell to plural PHY destinations is referred to as a multicast “session” and the identities of the PHY destinations are stored in a multicast session table for each session. The copying of the cell to one of the PHYs in the multicast session is referred to as a “leaf” in the session. According to the first embodiment, a multicast timer is started when a multicast cell reaches the head of the multicast queue. The timer is a count down timer preferably based on the slowest PHY device. If a PHY device in a session is inactive, it is skipped and the next PHY in the session is serviced. The session ends when one of three events occurs: all PHYs in the session table have been serviced, the timer expires, or the only PHYs remaining in the session are PHYs listed in the problem PHY vector. At the end of each multicast session, the problem PHY vector is updated. The problem PHY vector includes a list of all of the PHYs which are deemed to be presently inactive based on the last multicast session and all previous multicast sessions. The problem PHY vector is updated whenever an inactive PHY becomes active, either in a unicast or a multicast cell transfer. The problem PHY vector is preferably used to shorten the multicast session before the timer expires. It may also be used by an external device to modify multicast session tables.
According to a second and presently preferred embodiment of the invention, the servicing of PHYs is driven by the status of the queues. In a background process, the status of the unicast and multicast queue is repeatedly updated. The status of PHYs is obtained through the UTOPIA interface. If the multicast queue is not empty and the last queue serviced was a unicast queue, the multicast queue is serviced by copying the head of line cell to the next active PHY in the multicast session (i.e. the next leaf of the session). If the multicast queue is empty or if the last cell serviced was not a unicast cell, the next (in round robin) available unicast queue is serviced. As used herein, “available unicast queue” means a queue with a cell ready to be sent to an active PHY which is not part of the current multicast session. During the multicast session, if the only PHYs remaining in the session table are PHYs which are in the problem PHY vector, the session is ended and the problem PHY vector is updated. If the only PHYs remaining in the multicast session include inactive PHYs which are not in the problem PHY vector, the multicast timer is started. The scheduler continues to attempt to complete the multicast session until the timer expires or until the only PHYs left are in the problem PHY vector. When the timer expires, the session is ended and the problem PHY vector is updated.
REFERENCES:
patent: 4660169 (1987-04-01), Norgren et al.
patent: 5526344 (1996-06-01), Diaz et al.
patent: 5572686 (1996-11-01), Nunziata et al.
patent: 5764641 (1998-06-01), Lin
patent: 5893162 (1999-04-01), Lau et al.
patent: 5926458 (1999-07-01), Yin
patent: 6092108 (2000-07-01), DiPlacido et al.
patent: 6122251 (2000-09-01), Shinohara
patent: 6122252 (2000-09-01), Aimoto et al.
patent: 6163528 (2000-12-01), Nagamoto
patent: 6246682 (2001-06-01), Roy et al.
patent: 6307858 (2001-10-01), Mizukoshi et al.
patent: 6438134 (2002-08-01), Chow et al.
patent: 6445705 (2002-09-01), Holden et al.
patent: 6519225 (2003-02-01), Angle et al.
Parrella Eugene L.
Preston Thomas M.
Shanley Timothy M.
Srinivasan Desikan V.
Gordon & Jacobson P.C.
Juntima Nittaya
Nguyen Chau
Transwitch Corporation
LandOfFree
Method and apparatus for avoiding head of line blocking in... 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 avoiding head of line blocking in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for avoiding head of line blocking in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3259189