Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-06-05
2004-09-14
Pham, Chi (Department: 2667)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S461000, C370S462000
Reexamination Certificate
active
06791992
ABSTRACT:
FIELD OF THE INVENTION
The invention is generally applicable to cell switched networks. The invention specifically concerns a switch architecture for organizing and controlling the flow of cells between a plurality of input ports and output ports.
BACKGROUND OF THE INVENTION
Cell switched networks permit sharing of available communication bandwidth by multiple data sets having different sources and destinations. In contrast to circuit switching theory, where a connection is dedicated for communication between a source and destination, cell switching theory allows a connection resource to be used by multiple sources and destinations. This requires breaking data sets into discrete cells, which are then reassembled at the destination. Cells must contend for available bandwidth during transmission from a source to a destination. Such transmission bandwidth is typically allocated and controlled by a cell switch.
High speed communication media, e.g., optical fiber, are typically used in cell switched networks. A cell switch therefore has the potential to become, and does become in practice, the point of bottleneck in a cell switched network. High speed cell switches are therefore required to utilize the available bandwidth of the communication media. High speed cell switches must meet conflicting requirements in terms of service guarantees and resource (bandwidth) utilization. Real-time and interactive applications, such as terminal emulation, multimedia, and tele-presence, require various network guarantees on parameters such as latency, throughput, and loss rate. Some of these applications require low latency but do not require high throughput.
Fast cell switching is a technique to communicate a message between a source endpoint and a destination endpoint of a switching network using a series of information passing elements. One or more fast cell switches are used for transmission between the two endpoints. Data transmissions are now evolving with a specific focus on applications with varying network service demands. As a result, high-speed cell switches must be able to satisfy network service guarantees without sacrificing resource utilization. In a connection-oriented environment, switch resources are reserved to accommodate service guarantees. Resources, in this context, include transmission bandwidth and buffer space.
However, this is often not the most efficient use of the network resources. Conventionally, statistical multiplexing is used to increase resource utilization. Essentially, the bandwidth and buffer reservations reflect the average throughput rate, but the aggregate peak rates of all the admitted connections generally exceeds the capacity of the switch. The problem is that cells do not arrive at regular intervals. Rather, a source sends a burst of cells followed by an idle period. This type of traffic is referred to as bursty, which has significant implications on the behavior of the switch. When two sources send cells to the same destination, there is contention for the destination port. As a result, one or more cells must be buffered or discarded. When bursty traffic patterns exist, contention may persist for many cell cycles which in turn causes many cells to be buffered. This model contrasts sharply with the traditional assumption that arrivals are independent (not bursty). Under this traditional model, very small buffers are sufficient to prevent loss. In fact, however, bursty traffic necessitates large buffers. Accordingly, a switch must have sufficiently large buffers to accommodate bursty traffic and thereby minimize the loss rate, while simultaneously ensuring timely delivery of the cells.
Various cell buffering techniques exist in the prior art. One conventional technique relies on first-in-first-out (FIFO) queues. While this technique is fast and simple to implement in shared memory buffers, it is not adequate for efficient provision of guaranteed service. As used in this sense, “guaranteed service” means cell transmission characterized by guaranteed levels of latency and loss rate. One way that the FIFO queue may partially meet the demand of network service guarantees is by making the network very fast so that the offered load is always low. This minimizes the degree of queuing, thereby minimizing the queuing delay. Because the demand for network bandwidth is constantly increasing over time, the increased speed of the infrastructure is unlikely to yield acceptable performance in the long run. The demand will eventually rise to the point that contentions are unavoidable in the system, causing large numbers of cells to be stored. Although large FIFO buffers can withstand periods of contention, all cells are nevertheless subject to potentially significant delay. A tradeoff between loss-rate and delay is inevitable when using FIFO queues. FIFO queuing is also unable to protect one traffic stream from another. Furthermore, random cells are lost when a FIFO queue overflows. As a result, contentions must be handled intelligently for acceptable real time performance and to avoid degrading the quality of service afforded to important traffic. For example, it should be possible to schedule important or late-arriving traffic to be transmitted with minimal delay relative to other competing traffic.
A modified FIFO arrangement known in the art provides some service differentiation by replacing each individual FIFO queue with several FIFO queues. Each FIFO queue is used for a particular traffic class, i.e., deadline or priority. However, this solution is inadequate for a wide range of traffic classes due to its small number of priority levels. It is similarly unable to isolate traffic streams of the same class.
Thus, there is a need for an improved cell switching architecture which addresses some or all of the aforementioned difficulties. It is an object of the invention to provide such an improved cell switching architecture.
SUMMARY OF THE INVENTION
These and other needs are met or exceeded by the present cell switching architecture. According to the cell switching architecture of the present invention, there is an input queue for each input port. Furthermore, within each input queue, there is at least one earliest-deadline-first (EDF) queue for each of the output ports so that no two output ports share a common EDF queue. Cells are arranged in each EDF queue according to deadlines, but each EDF queue handles only cells for a single destination output port for a particular input port. In other words, each EDF queue arranges the cells for a single output port.
The architecture provides a method for switching cells between a plurality of input ports and a plurality of output ports. Cells are accepted from input ports into a plurality of corresponding input queues. Cells are sorted into groups according to the destination output port such that each group includes cells destined for a single output port. Within each input queue, at least one group is formed for every output port for which cells are available. Cells within the group are arranged according to deadlines, earliest deadline first. Transmission control directs the earliest deadline cell for a given output port to be transmitted in a particular cycle. Arbitration is implemented to avoid conflicts between input queues transmitting cells in a given cycle.
REFERENCES:
patent: 5517495 (1996-05-01), Lund et al.
patent: 6009077 (1999-12-01), Firoiu et al.
patent: 6072772 (2000-06-01), Charny et al.
patent: 6088734 (2000-07-01), Martin et al.
patent: 6442166 (2002-08-01), McDonald et al.
patent: 6532213 (2003-03-01), Chiussi et al.
B. Prabhakar, N. McKeown, R. Ahuja, “Multicast Scheduling for Input-Queued Switches”.
N. McKeown, B. Prabhakar, M. Zhu, Matching Output Queueing with Combined Input and Output Queueing.
A. Mekkittikul, N. McKeown, “A Practical Scheduling Algorithm to Achieve 100% Throughtput in Input-Queued Switches”.
B. Prabhakar, “On the Speedup Required for Combined Input and Output Queued Switching”.
S.T. Chuang, A. Goel, N. McKeown, B. Prabhakar, “Matching Output Queueing with a Combined Input and
James Kevin W.
Yun Kenneth Y.
Boakye Alexander O.
Pham Chi
LandOfFree
Earliest-deadline-first queuing cell switching architecture... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Earliest-deadline-first queuing cell switching architecture..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Earliest-deadline-first queuing cell switching architecture... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3231782