Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-01-15
2002-08-06
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S395320
Reexamination Certificate
active
06430181
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a connection scheduler for a crossbar switch and, more particularly, pertains to a scheduling technique for an input-buffered N×N non-blocking crossbar switch which can be enhanced to support rate-based traffic scheduling. Simulation results indicate that the rate-based scheduling mechanism of this invention provides an excellent average bounding of the difference between requested service delay and actual service delay through the switch fabric. This behavior is robust to a large variety of traffic patterns as long as the requested traffic load is no greater than a large fraction of unity, &ggr;. These empirical results are described with reference to the simulations discussed in the Detailed Description of the Preferred Embodiments.
2. Description of the Related Art
A variety of connection schedulers are known in the art. Each employs one or several scheduling policies. These policies range from simple and practical schemes such as Strict Priority, Round Robin, or Weighted Round Robin, to more elaborate schemes such as Weighted Fair Queuing. There are also many variations of these policies and other policies known in the literature.
A few of the typical performance metrics used to compare the various scheduling methods are jitter and latency of data delivery, fairness of arbitration, and scalability of port count and port bandwidth. Simpler scheduling methods provide only best effort delivery of traffic, while other more complex methods allow traffic flows to establish contracts that establish certain performance guarantees with the network. Typical of these guarantees is the provision of a minimum bandwidth capacity to a traffic flow. Slightly more elaborate traffic contracts may also offer a maximum bounding of cell delivery jitter or delay.
SUMMARY OF THE INVENTION
The present invention is a component of a crossbar data switch. Such a switch must have several components. It must have multiple network interfaces. It must have some amount of data buffering at the ingress of the switch. This buffer is able to receive packets at the network interface line rate, and to forward packets at the rate supported by the crossbar switch fabric. When there is contention for an output port of the crossbar from more than one of its input ports, then the buffering at those input ports will be used to store packets for the duration of the mismatch of the receive and forwarding rates caused by contention from other inbound ports for the outbound switch port. If contention is sufficiently long lasting, inbound buffering may become full, and packets will be dropped as a result. There must be an inbound controller to the crossbar that keeps track of how many traffic flows reside in the buffering, where their packets reside, and which outbound port they are destined to. Using this information it must submit forwarding requests to the scheduler, retrieve grants from the scheduler and forward traffic on the granted connection paths. Outbound buffering may also be used to match the crossbar forwarding rate to the outbound network interface line rate. Inbound and outbound controllers may also be responsible for multiplexing traffic from multiple network interfaces into a shared crossbar port, or for demultiplexing traffic from a common outbound switch port to multiple network interface destinations, respectively.
FIG. 1
illustrates a block diagram for an exemplary, preferred crossbar buffered switch
10
according to the present invention. Inbound port controllers
12
buffer data from the physical network link
11
, and forward this data across the switch fabric
13
. To forward data, the inbound port controllers
12
must participate in cell scheduling which involves the submission of requests and the retrieval of grants. Outbound port controllers
14
receive cells from the fabric
13
and transmit them to a physical network link
15
with minimal buffering being required. An input port controller
12
or output port controller
14
may attach to the fabric
13
in more than one location to improve the physical distribution of I/O bandwidth for a particular implementation. Also shown in
FIG. 1
is a connection scheduler
17
, herein composed of an active diagonal sequencer
16
and a grant selector
18
, which is described below. The grant selector
18
is described in the enclosed pseudo code.
Of these necessary mechanisms for a crossbar data switch, only the connection scheduler is described in detail. The other mechanisms are conventional.
The present invention describes a simple best effort scheduler named Max
2
d. The present invention also describes a more elaborate scheduler, named Rate
2
d, that provides minimum average bandwidth guarantees. The Rate
2
d method is an elaboration of the Max
2
d method. Both Max
2
d and Rate
2
d scale well to implementations with very large port number and per port bandwidth.
In accordance with a specific illustrative embodiment of the present invention, a connection scheduler for an input-buffered N×N crossbar switch is presented.
In one aspect of the present invention, the connection scheduler
17
and forwarder
23
are constructed from a two-dimensional cooperative mesh of one-dimensional round robin schedulers. There are
2
*N one-dimensional round robin schedules at work, one scheduler
17
associated with each of N input ports
19
A-N of the fabric
13
and one scheduler
17
associated with each of N output ports
21
A-N of the fabric
13
. Although round robin scheduling is well known in the art, the manner in which the schedules employed by this invention cooperate is novel. This cooperative synchronization of the round robin schedulers achieves maximal matching among a set of N
2
possible requests from N input ports
19
to N output ports
21
. This cooperative synchronization of round robin schedulers is the fundamental basis of this invention and will be referred to as two dimensional round robin scheduling.
Two dimensional round robin scheduling is described in detail as the specification of Max
2
d. This connection scheduler
17
works in conjunction with a data forwarder
23
as described earlier in this section.
In another aspect of the present invention, the Max
2
d scheduler is enhanced to implement a rate-based scheduler with deterministic maximal scheduling of connection requests with strict scheduling prioritization derived from requested service delays. This enhanced scheduling method is named Rate
2
d, and is empirically shown to provide minimum average bandwidth guarantees.
In a broad aspect of the present invention, the connection scheduler for an input-buffered N×N non-blocking crossbar switch is adapted to support rate-based traffic scheduling and to provide average-case inter-switch port cell forwarding service delays which are deterministic and well bounded.
In another aspect of the present invention, the connection scheduler is adapted to implement maximal scheduling of connection requests with strict scheduling prioritization derived from requested service delays.
In another aspect of the present invention, the connection scheduler
17
implements a two-dimensionally synchronized round robin arbitration of connection requests stored at the switch elements SE
yx
(where 0≦y≦N−1 and 0≦x≦N−1) of a crossbar switch fabric
13
.
In another aspect of the present invention, the connection scheduler
17
is adapted to implement maximal matching among a set of N
2
possible requests from N input ports
19
to N output ports
21
of a crossbar switch fabric
13
. Arbitration of a single matching completes in order N time.
REFERENCES:
patent: 5517495 (1996-05-01), Lund
patent: 6072772 (2000-06-01), Charny
patent: 6134217 (2000-10-01), Stiliades
patent: 6144662 (2000-11-01), Colmant
patent: 6188690 (2001-02-01), Holden
Nick McKeown and Thomas E. Anderson, “A Quantitative Comparison of Scheduling Algorithms for Input-Queued Switches,” 1993.
Dimitrios Stiliadis and Anujan Varma, “Latency-Rate Servers: A Gen
LSI Logic Corporation
Maiorana PC Christopher P.
Pizarro Ricardo M.
LandOfFree
Crossbar switch fabric with deterministic maximal scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Crossbar switch fabric with deterministic maximal scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Crossbar switch fabric with deterministic maximal scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2895877