Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-04-28
2001-05-01
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S236000, C370S395430, C370S413000
Reexamination Certificate
active
06226298
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates primarily to a class of digital communication systems known as asynchronous transfer mode (ATM) switching systems and more generally to intercomputer communications architectures. The invention more specifically relates to systems and methods for removing undeliverable cells in an output routing table within an ATM network.
A building block in a switch-fabric architecture ATM switch system is a structure known as a switch element. A switch element provides packet signal routing from one of a plurality of input ports to one or more of a plurality of output ports by maintaining an array of crosspoints for connecting any input port to any output port. Switch elements may be aggregated in various patterns to provide arbitrarily large N by N possible interconnection of input ports to output ports.
Another building block in a switch-fabric architecture ATM switch system is a structure known as a routing table (RT). In an ATM switch there generally is functionally an output routing table (ORT) and an input routing table (IRT).
One solution to the problem of buffering cells as they flow through various switch devices, including RTs, is the use of a shared pool of memory for storing queued cells. A shared pool more effectively utilizes available memory. However, a shared pool is also more susceptible to various types of “blocking,” wherein cells which are delayed within the shared pool block the passage of other cells through the device when these other cells might otherwise be able to be transmitted through a device.
Increasing demands for communications speed and capacity have created a need for a higher performance ATM architecture as described in 60/033,029. This architecture differs from an earlier architecture designed by one of the inventors of the present invention in that the primary shared pool memory areas are associated with an input routing table (IRT) and output routing table (ORT). Shared pool buffer memories associated with individual switch elements are generally used only when handling multicast traffic. The new architecture is different also in that it provides for a number of virtual outputs (VOs) for each output line from an ORT and a number of virtual inputs (VIs) for each input line to an IRT. In one specific embodiment, the ORT and IRT are combined into a single device referred to as a Quad Routing Table (QRT). The QRT may be used in connection with a switch fabric constructed of switch elements (SEs) as described in earlier applications or may be used in connection with a switch fabric made up of update quad switch elements (QSEs) as described in 60/033,029.
In various reference materials and in the 60/029,543 application, a VO of a QRT connects to a PHY. A PHY (for PHYsical connection) generally represents a connection to a different physical device. In a telephone network, the different PHYs might be trunk lines to different cities; in a wide-area-network router, the PHYs might be connecting to different floors in a building; in a local-area-network switch, the PHYs might be different individual workstations. Throughout this document, the term VO should be understood to be connected to a PHY, unless the context requires otherwise.
A particular problem that can arrive in a switch architecture with VOs and some type of shared buffer space is what happens when one of the physical connections to which a VO is connected unexpectedly becomes disabled or broken. In general, it will take some time for higher layer communication protocols to detect that a VO cannot receive data. During that time, cells queued for the disabled VO may fill up the buffer pool in the ORT, thus degrading the performance of delivery of cells directed to other VOs which remain operational. Furthermore, in many ATM applications, such as live telephone or video, once a cell has been delayed even a short time from when it was expected, the cell effectively becomes stale and delivery of stale cells would be worse than non-delivery of those cells. In various references in the art, identifying and eliminating from an ATM system stale or undeliverable cells is referred to as cell flushing.
Some prior-art ATM architectures do not have specific mechanisms for detecting and flushing cells in an ORT that are directed to a particular disabled VO. If one of the VOs breaks, traffic to that VO back up, disrupting traffic to other VOs of the ORT. In this case, the only alternative is to reset the entire ORT, thereby deleting all of the cells that are pending in the ORT.
A different technique is to have a mechanism within the ORT that accurately knows the rate that a VO is expected to be able to receive cells. In this technique, if one of the VOs stops accepting cells, the ORT can force that VO to accept cells anyway at the rate it would expect the VO to normally accept cells. This solution is complex to implement, however, in terms of both hardware and processing of cells.
A different technique is to include a special flushing dequeue routine, different from the normal dequeue mechanism, for removing undeliverable or late cells. This solution is also complex to implement and expensive in terms of gates and processing.
What is needed is a method or apparatus for an ATM architecture having shared resources in an output routing table that allows the ORT to effectively detect and delete cells directed to physical connections or virtual outputs that are disabled.
SUMMARY OF THE INVENTION
The invention is a method and/or mechanism for detecting when a particular VO has stopped accepting cells. In one embodiment, the detection system can be implemented in a very small number of gates by defining an interval which is longer than the interval in which it would be expected that a VO would indicate it could accept at least one cell. A flag is then set to a first state at the start time of the interval. Whenever during the interval a VO indicates that it is ready to accept a cell, the flag state is changed to an active state. At the end of the interval, the flag for a VO is examined and if it remains in the first state set at the beginning of the interval, it is concluded that a VO has become disabled.
In a very compact implementation, only two bits of state per VO are necessary, and a single interval count is used for all VOs. In a further aspect of the invention, cells in an ORT directed to a disabled VO are marked with a lowest priority and are processed during otherwise inactive bandwidth time by the ORT using the normal ORT dequeue routine to clear the cells from the ORT memory. A variation on a simply embodiment includes a additional enable bit per VO. The enable bit is set by the ORT controller to indicate that a VO is enabled. Once a VO has been marked disabled, it remains marked disabled until the controller resets the enable bit.
In a specific embodiment, the invention may be described in terms of the transmit or egress UTOPIA interface having a function called the WatchDog. The WatchDog exists to protect the QRT Virtual Output queues from overflow in the event that a PHY sink connected to a VO goes off line or stops requesting cells. The WatchDog can be configured by way of the UTOPIA CONFIG register in the processor interface. The WatchDog can be turned off or set to tolerate either OC-3, DS1 or DS0 level outputs. The WatchDog operates by observing the liveliness of the Transmit ATM Cell Available signals. When a PHY is detected to have stopped accepting cells, the cells intended for that PHY are played out using the standard dequeue mechanism with otherwise normal UTOPIA signalling (in one variation) at the lowest priority whenever spare bandwidth is available. This is done in the event that the PHY can accept these cells and the nature of the cell available response dormancy is due to a stuck-at fault. Cells also may be dequeued by the normal dequeue routine without playing-them out to the PHY.
Numerous alternative implementations are possible and the invention should not be limited except as in the attached claims. The invention will be further understo
Alleyne Brian D.
Braun Darren S.
Holden Brian D.
Allen Kenneth R.
Kizou Hassan
PMC-Sierra (Maryland), Inc.
Slavitt Mitchell
Townsend and Townsend / and Crew LLP
LandOfFree
Method and apparatus for detecting disabled physical devices... 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 detecting disabled physical devices..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting disabled physical devices... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2534597