Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-05-01
2002-02-26
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S414000, C370S422000, C370S429000
Reexamination Certificate
active
06351466
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to switching systems and to methods of operation of switching systems. For example, the switching systems with which the invention is concerned might find application as crosspoint switches in local area network (LAN) switches, asynchronous transfer mode (ATM) switches and Internet protocol (IP) routers.
More particularly, the switching system to which the invention relates is intended for connection between a plurality of input lines and a plurality of output lines, and comprises a transfer stage operable to transfer packets of data from any of the input lines to those of the output lines for which those packets are destined. It is necessary with such switches to provide some form of queueing for the packets of data.
2. Description of the Prior Art
Many commercial switches and routers today employ output-queueing. When a packet arrives on an input line of an output queue switch, it is immediately transferred by the transfer stage to a queue at an output stage that is dedicated to its output line, where it will wait until departing from the switch. This approach is known to maximize the throughput of the switch; so long as no input or output is oversubscribed, the switch is able to support the traffic, and the occupancies of queues remain bounded.
The use of a separate queue for each output means that flows of packets for different outputs are kept separate, and cannot interfere with each other. By carefully scheduling the time a packet is placed onto the outgoing line, a switch or router can control the packet's latency, and hence provide quality-of-service guarantees. But output queueing is impractical for switches with high line rates, or with a large number of ports. The fabric and memory (i.e. transfer stage) of an N×N switch must run N times as fast as the line rate. Unfortunately, at high line rates, memories with sufficient bandwidth are simply not available.
On the other hand, the fabric and the memory of an input-queued switch need only run as fast as the line rate. This makes input queueing very appealing for switches with fast line rates, or with a large number of ports. For a given speed of memory, it is possible to build a faster switch; or for a given speed switch, it is possible to use slower, lower-cost memory device.
But, the main problem of input-queued switching is head-of-line blocking, whose effect on throughput can be severe. It has been shown that if each input maintains a single first-in-first-out queue, then head-of-line blocking can limit the throughput to just 58.6%.
One method that has been proposed to reduce head-of-line blocking is to increase the “speedup” of a switch. A switch with a speedup of S can remove up to S packets from each input and deliver up to packets to each output within a time slot, where a time slot is the time between packet arrivals at the inputs. Hence, an output-queued switch has a speedup of S=N while an input-queued switch has a speedup of S=1. For values of S between 1 and N, buffers are needed at the inputs before switching as well as buffers at the outputs after switching. Hence such a switch will be referred to a combined-input-and-output-queued switch.
Both analytical and simulation studies of a combined-input-and-output-queued switch which maintains a single first-in-first-out queue at each input have been conducted for various values of the speedup. A common conclusion of these studies is that, with a speedup of S=4 or 5, one can achieve about 99% throughput when arrivals are independent and identically distributed at each input and the distribution of packet destinations is uniform across the outputs.
But it has been shown that a throughput of 100% can be achieved with a speedup of just one, if the inputs are arranged differently. That is, head-of-line blocking can be eliminated entirely using a scheme known as “virtual output queueing” in which each input maintains a separate queue for each output. It has been shown that for independent arrivals, the throughput of an input-queued switch can be increased to 100%. The conclusion may be drawn that speedup is not necessary to eliminate the effect of head-of-line blocking.
In practice, it is not only the throughput of a switch which is of interest, but also the latency of individual packets. This is particularly important if a switch or router is to offer quality-of-service guarantees. Packets in an input-queued switch not only contend for an output, they also contend for entry into the switch fabric with packets that are destined for other outputs. This phenomenon is called “input contention” which places a packet at the mercy of other packets destined for other outputs. This is in stark contrast with an output-queued switch, where a packet is unaffected by packets destined for other outputs. The conclusion may be drawn that, to control delay, a mechanism is needed which eliminates input contention.
SUMMARY OF THE INVENTION
Previous studies of combined-input-and-output-queued switches make no guarantees about the delay of an individual packet, but only about average delay and throughput. The present invention is concerned with the delay of individual packets. Rather than find values of speedup that work well on average, or with simplistic traffic models, the invention is concerned with providing a combined-input-and-output-queued switch which behaves similarly, and preferably identically to an output-queued switch, preferably for all types of traffic, and preferably with the minimum speedup.
The present invention achieves this, in one aspect, by providing a method of operation of the switching system which comprises the steps of: for each output stage, noting the temporal order in which the packets destined for that output stage are received by the input stages; and controlling the transfer stage so that, for each output stage, the packets destined for that output stage are transferred from the input stages to that output stage in the noted order.
Preferably, the system operates according to time slots such that: no more than one packet is received by each input stage during each time slot; and no more than one packet is supplied by each output stage during each time slot; and each time slot is divided into a plurality of phases, for example between two and four such phases, such that: no more than one packet is transferred from each input stage by the transfer stage during each phase; and no more than one packet is transferred to each output stage by the transfer stage during each phase.
As will be shown later in this specification, if each such time slot is divided into four such phases (i.e. a speedup of four), the switching system can be made to behave identically to an output-queued switch.
In one example to achieve this, the controlling step includes the step, during each phase and for each output stage, of: selecting that one of the input stages, if any, having that one of the packets which are destined for that output stage which is earliest in the noted temporal order; and transferring that one packet from the selected input stage to that output stage unless there is input contention due to the selected input stage also having been selected for another of the output stages. If there is such input contention, that one of the output stages whose destined packet is earliest in the noted temporal order may be selected, unless there is none which is earliest. If none of the packets is earliest, selection between the output stages may be made in accordance with the predetermined ranking. In the case of input contention, the controlling step is preferably repeated for the or each output stage which is not selected in respect of the next earliest packet in the noted temporal order.
As in the known combined-input-and-output-queued switch, each input stage preferably comprises a plurality of input buffers, one for each output stage, the method further including the step of placing each received packet in that one of the input buffers for the input line on whic
McKeown Nick
Prabhakar Balaji
Hewlett--Packard Company
Kizou Hassan
Tran Thien D
LandOfFree
Switching systems and methods of operation of switching systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Switching systems and methods of operation of switching systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switching systems and methods of operation of switching systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2975812