Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-03-31
2002-08-27
Vincent, David (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395700, C370S230000
Reexamination Certificate
active
06442172
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to digital LAN and WAN traffic switches, particularly asynchronous transfer mode (ATM) switches.
An ATM cell switch takes cells from many sources, and routes them to many destinations. Such a switch may be hardware-based, or hardware- and software-based. The architecture can be generalized as shown in FIG.
1
. Cells arrive on input ports
1
to N
in
and are switched through a switch fabric
100
to various ones of output ports
1
to N
out
.
A cell is a fixed size unit which constitutes a fraction of a larger communication. Cells come in on input ports, and get routed to output ports.
Sometimes, collisions take place between cells. That is, cells come in on two or more input ports that are destined for the same output port. There are two scenarios which describe the condition when two or more cells are destined for the same output port: (1) momentary contention or cell collision; and (2) sustained contention or congestion.
In either case, the collisions create the need for queueing, where one or more cells have to wait in line to be delivered to the output port.
With some architectures, even when there are no collisions, blocking can take place. Blocking occurs when a cell cannot be delivered because the delivery of other cells is taking up the resources necessary for the delivery of the blocked cell. This is often referred to as “head of line” blocking. Blocking is undesirable, since it can delay the delivery of other cells. Also, blocked cells must be queued, just like cells delayed due to collisions.
Due to these inevitable delays in delivery, a successful architecture must properly queue cells for delivery to output ports. Such queueing is also referred to as “buffering”. Buffering requires buffer control. Buffer control tells buffers when to release a cell from a queue for delivery to an output port.
Even with buffer control, it is sometimes necessary to “drop” cells. For instance, when cells come in on input ports “1” and “2”, all destined for output port “3”, it is often the situation that more cells come in than can be output from port “3”. The cells begin to be queued-up in the buffers. If this situation persists, the buffers get filled-up, and cells must be thrown away, or “dropped”. A good design minimizes the number of dropped cells.
A highly effective buffer control strategy is dynamic input buffering and output control (DIBOC). In a DIBOC architecture, a switch fabric has an input side and an output side for switching cells received at any of a plurality of input ports to any of a plurality of output ports. Cells received at the input side and destined for the output side are buffered at the input side. The output side monitors the status of the output ports, and eventually transmits grants to release the cells buffered in the input side. Buffering cells at inputs controlled by outputs has numerous advantages. First, input buffering means that cells are dropped before being transmitted across the switch fabric whenever dropping is required, reducing the traffic load on the switch fabric during congested periods. Second, output control means that the switch may be designed according to output port bandwidth limitations, improving scalability. Third, output control means that precise control algorithms may be implemented to allocate grants in a fair manner, i.e., output control allows grants to be allocated in a logical order based on considerations such as source input port, cell priority and destination output port.
Known DIBOC architectures have relied on handshaking procedures in which requests and grants are exchanged on a “per cell” basis to secure release of cells. In such handshaking procedures, the input side transmits to the output side a request for release for each cell received. Such requests typically identify a logical output queue for the cell, e.g., the cell priority level, output, etc. The output side either queues the entire requests in an request buffer, as in Hayter, U.S. Pat. No. 5,448,559, or increments a “backlog” value in a status buffer reserved for the logical output queue, as in Khacherian, application Ser. No. 08/679,360, U.S. Pat. No. 5,768,257, the output side's issuance of a grant to release the cell across the switching fabric to the identified output. The grants are issued on a “per cell” basis in a logical order by arbitrating among the logical output queues having at least one request pending.
Despite the significant advantages of DIBOC as an overall buffer control strategy, there is room to improve on the “per cell” handshaking procedures implemented in known DIBOC architectures. Such handshaking procedures have several weaknesses. First, a request must be transmitted to the output side for each cell even though the cell's logical output queue may already have a cell pending, resulting in the transmission of superfluous control traffic. Second, each request received by the output side must be queued even though the logical output queue with which the request is associated may already have a cell pending, or at the very least a multi-bit “backlog” value must be retained and updated for each logical output queue, imposing unnecessary status buffering requirements. Third, whenever a request does not reach the output side due to a collision or corruption during transmission, the output side develops an inaccurate view of the status of a logical output queue, which is not easily remedied. Analogous weaknesses arise in connection with the transmission of grants to the input side on a “per cell” basis. Accordingly, there is a need for a novel buffer control strategy which provides the traditional advantages of DIBOC without the side effects of “per cell” handshaking.
SUMMARY OF THE INVENTION
In its most basic feature, the present invention provides a DIBOC buffer control strategy for a digital traffic switch which avoids the side effects of “per cell” handshaking through the expedient of queue status-based buffer control.
In one aspect of the invention, the transmission of requests on a “per cell” basis is eliminated by relying on changes in the content status of logical output queues from “empty” to “not empty”, or vice versa, as the basic triggering event for transmitting status messages from the input side to the output side. A “not empty” status message for a logical output queue is transmitted whenever the. state of the logical output queue has changed from “empty” to “not empty”. An “empty” status message is transmitted whenever the state of a logical output queue has reverted to “empty”. The content status of each logical output queue is monitored at the output side by retaining and updating a single status bit which has a particular binary value (e.g., a “0”) when the last-received status message indicates a logical output queue's status as “empty” and the opposite binary value (e.g., a “1”) when the last-received status message indicates a logical output queue's status as “not empty”. The output side may then, in a logical order, grant clearance to logical output queues whose content status is indicated as “not empty” to release discrete information units from the input side to the output side. By limiting the transfer frequency and output-retained bit-count of content status information to the instances and information required to effectuate the logical order for granting clearance to release discrete information units, control traffic and status buffering requirements are reduced.
In another aspect, the transmission of grants on a “per cell” basis is eliminated by relying on changes in the clearance status of logical output queues from “clear to release” to “not clear to release”, or vice versa, as the basic triggering event for transmitting status messages from the output side to the input side. A “clear to release” status message for a logical output queue is transmitted whenever the status of the logical output queue has changed from “not clear to release” to “clear to release”. A “not clear to release” status message is transmitted whenever
Hoogenboom Chris L.
Nishimura Michael J.
Wallner John D.
Wilson Michael K.
Alcatel Internetworking, Inc.
Boakye Alexander O.
Christie Parker & Hale LLP
Vincent David
LandOfFree
Input buffering and queue status-based output control for 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 Input buffering and queue status-based output control for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Input buffering and queue status-based output control for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2967553