 |
Claims  |
|
|
What is claimed is:
1. An apparatus for scheduling packets in an input-buffered multipoint switch comprising:
a plurality of input channels;
a plurality of output channels;
multilevel request buffers, each multilevel request buffer being specific to one of said plurality of input channels, said multilevel request buffers having discrete buffer priority levels for storing requests having alternative quality of
service (QoS) priorities, said requests having specific request buffer priorities that are determined by the discrete buffer priority level in which said requests are stored; and
scheduler means in communication with said multilevel request buffers for
indicating a transmission status for each of said input and output channels, said transmission status being indicative of channel availability,
arbitrating among selected requests which have an equal QoS priority and which are stored in any of said discrete buffer priority levels of said multilevel request buffers, said arbitrating being at least partially based upon a combination of
said request buffer priorities and said transmission statuses of said input and output channels, and
issuing grants to said requests in a channel-by-channel sequence based upon said arbitrating among said selected requests having equal QoS priority.
2. The apparatus of claim 1 further comprising parallel links between each discrete buffer priority level of said multilevel request buffers and said scheduler means, said scheduler means being enabled to simultaneously access all of said
discrete buffer priority levels of each said request buffer.
3. The apparatus of claim 2 further comprising additional parallel links between said multilevel request buffers and said scheduler means, wherein said additional parallel links carry QoS priority indicators that are related to said stored
requests.
4. The apparatus of claim 1 wherein said scheduler means includes a mask generator circuit operationally connected to said multilevel request buffers to generate mask vectors that are indicative of each output channel that is requested at each
of said alternative QoS priorities except the lowest QoS priority, each said mask vector being associated with one of said QoS priorities.
5. The apparatus of claim 4 wherein said scheduler means further includes QoS priority-specific mask comparator circuits operationally connected to said mask generator circuit and said multilevel request buffers to compare said mask vectors to
associated requests.
6. The apparatus of claim 5 wherein said scheduler means further includes a plurality of QoS priority-specific scheduler circuits, each QoS priority-specific scheduler circuit being operationally connected to an associated output of said mask
comparator circuit to generate a QoS priority-specific grant for a request having an available input channel and available requested output channels.
7. The apparatus of claim 6 wherein said scheduler means further includes QoS priority-specific priority encoder circuits operationally connected to said QoS priority-specific scheduler circuits to select a highest priority grant from all grants
generated from said QoS priority-specific scheduler circuits for a specific channel and to transmit said selected highest priority grant to an input channel that corresponds to said selected highest priority request.
8. A method for scheduling transmissions of switching cells across an input-buffered network switch that connects a plurality of input channels to a plurality of output channels, each switching cell being associated with one of said plurality of
input channels, said method including the steps of:
storing a first plurality of requests in a first request buffer that buffers requests related to a first input channel, each said request corresponding to one of said switching cells and having a request buffer priority and a quality of service
(QoS) priority;
assigning request buffer priorities to each of said first plurality of requests ranging from highest request buffer priority to lowest request buffer priority;
storing a second plurality of requests in a second request buffer that buffers requests related to a second input channel, each said request corresponding to one of said switching cells and having a request buffer priority and a QoS priority;
assigning request buffer priorities to each of said second plurality of requests ranging from highest request buffer priority to lowest request buffer priority;
accessing each request of said first and second pluralities of requests in parallel such that requests of all said request buffer priorities are accessed simultaneously;
sorting said first and second pluralities of requests by QoS priority;
arbitrating among said accessed and QoS sorted requests based upon said request buffer priority, availability of said first and second input channels, and availability of requested output channels; and
issuing grants in response to said arbitration to said accessed and QoS sorted requests that have a highest request buffer priority and for which respective input channels and output channels are available.
9. The method of claim 8 further including a step of receiving a done signal that indicates the completion of a transmission of switching cells related to a single packet.
10. The method of claim 8 wherein said step of arbitrating includes a step of arbitrating requests one channel at a time in descending channel priority from a highest channel priority to a lowest channel priority.
11. The method of claim 8 wherein said step of arbitrating includes a sub-step of arbitrating all requests of a same QoS priority stored in a request buffer associated with a particular input channel in parallel.
12. The method of claim 11 wherein said step of arbitrating requests of the same QoS priority in parallel includes a step of executing said arbitrations in a fixed sequence with respect to said input channels.
13. The method of claim 11 wherein said step of arbitrating requests of the same QoS priority includes sub-steps of:
generating masks that represent all requests having a QoS priority that is equivalent to or higher than a designated QoS priority; and
comparing a mask for said designated QoS priority to a request having a lower QoS priority to determine availability of output channels required by said request.
14. The method of claim 11 further including the steps of:
identifying an input channel having a highest round-robin priority among said plurality of input channels for arbitration purposes; and
reserving requested output channels for a multicast request when said multicast request is associated with an input channel that has said highest round-robin priority among said plurality of input channels.
15. An apparatus for scheduling cells in an input-buffered multipoint switch having input channels and output channels, wherein said cells have been assigned a particular quality of service (QoS) priority and wherein requests identify desired
output channels for corresponding cells, comprising:
a request buffer specific to each one of said input channels, each said request buffer having a plurality of register levels for storing requests of corresponding request buffer priority levels;
a QoS priority indicator buffer specific to each one of said input channels, each said QoS priority indicator buffer having a plurality of register levels that are directly related to said register levels of said request buffers for storing QoS
priority indicators that correspond to said requests stored in said request buffers;
means, connected to said request buffers and said QoS priority indicator buffers, for sorting said requests by QoS priority;
means, connected to said means for sorting, for arbitrating among said sorted requests on a QoS priority basis and for issuing request grants to highest request buffer priority requests that have available input channels and available output
channels;
a scheduler and first parallel data links between each register level of said request buffers and said means for sorting to provide said scheduler with simultaneous access to all of said requests stored in all of said request buffers; and
second parallel data links between each register level of said QoS priority indicator buffers and said means for sorting that provide said scheduler with simultaneous access to all of said QoS priority indicators stored in all of said QoS
priority indicator buffers.
16. The apparatus of claim 15 further comprising a means for generating a mask vector that represents an aggregate of requested output channels for a minimum QoS priority level, said means for generating a mask vector being operatively connected
to said request buffers.
17. The apparatus of claim 16 further comprising a means for performing parallel mask comparisons between said mask vector and requests from respective QoS priority levels for a particular input channel to indicate output channel conflicts
between requests, said means for performing parallel mask comparisons being operatively connected to said means for generating said mask vector.
18. The apparatus of claim 17 further comprising a means, specific to each QoS priority, for performing request buffer priority-specific scheduling between said QoS priority sorted requests from respective request buffer priority levels,
available input and output channels, and a round-robin channel priority, said means for performing request buffer priority-specific scheduling having three outputs per request buffer priority level, a request buffer priority-specific request grant, an
updated input channel vector, and an updated output channel vector.
19. The apparatus of claim 18 further comprising a means for selecting which request buffer priority-specific grant has a highest priority among all request buffer priority-specific grants for a single input channel and for transmitting said
selected request grant from said means for selecting.
20. An apparatus for scheduling packets in an input-buffered multipoint switch comprising:
a plurality of input channels;
a plurality of output channels;
multilevel request buffers, each multilevel request buffer being specific to one of said plurality of input channels, said multilevel request buffers having discrete levels for storing requests having alternative quality of service (QoS)
priorities, said requests having specific request buffer priorities that relate to said discrete levels within said multilevel request buffers; and
scheduler means in communication with said multilevel request buffers for
indicating a transmission status for each of said input and output channels, said transmission status being indicative of channel availability,
arbitrating among selected requests which have an equal QoS priority and which are stored in any of said levels of said plurality of multilevel request buffers, said arbitrating being at least partially based upon a combination of said request
buffer priorities and said transmission statuses of said input and output channels, and
issuing grants to said requests in a channel-by-channel sequence based upon said arbitrating among said selected requests having equal QoS priority;
said scheduler means including a mask generator circuit operationally connected to said multilevel request buffers to generate mask vectors that are indicative of each output channel that is requested at each of said alternative QoS priorities
except the lowest QoS priority, each said mask vector being associated with one of said QoS priorities.
21. The apparatus of claim 20 wherein said scheduler means further includes QoS priority-specific mask comparator circuits operationally connected to said mask generator circuit and said multilevel request buffers to compare said mask vectors to
associated requests.
22. The apparatus of claim 21 wherein said scheduler means further includes a plurality of QoS priority-specific scheduler circuits, each QoS priority-specific scheduler circuit being operationally connected to an associated output of said mask
comparator circuit to generate a QoS priority-specific grant for a request having an available input channel and available requested output channels.
23. The apparatus of claim 22 wherein said scheduler means further includes QoS priority-specific priority encoder circuits operationally connected to said QoS priority-specific scheduler circuits to select a highest priority grant from all
grants generated from said QoS priority-specific scheduler circuits for a specific channel and to transmit said selected highest priority grant to an input channel that corresponds to said selected highest priority request. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
TECHNICAL FIELD
The invention relates generally to the scheduling of packets in a high-bandwidth input-buffered multipoint switch, for instance as used in gigabit ethernet networks. More particularly, the invention relates to a non-blocking scheduler that
utilizes a parallel multilevel arbitration method.
BACKGROUND OF THE INVENTION
Networks are widely used to transfer voice, video, and data between various network devices such as telephones, televisions, and computers. Data transmitted through a network is typically segmented into packets, and under some network protocols
data is segmented into fixed-length cells. For example, Asynchronous Transfer Mode (ATM) protocol requires 53-byte cells, with 5 bytes of each cell designated for a header and 48 bytes of each cell designated for payload. Other network protocols, such
as ethernet or Internet protocol, carry data in variable-size packets.
Switches are integral parts of most networks. Switches receive packets from input channels and direct the packets to the appropriate output channels of the switch. Typical switches have three components: a physical switch fabric to provide the
connections from input channels to output channels, a scheduling mechanism to direct traffic when multiple packets arrive on different input channels destined for the same output channel, and a buffering or queuing mechanism at the switch input or output
to accommodate traffic fluctuations without undue packet loss. FIG. 1 is a diagram of a prior art switch 10 that has four input channels 12, 14, 16 and 18 and four output channels 20, 22, 24 and 26. The switch has a serial input queue 28, 30, 32, and
36 for each input channel, a crossbar physical switch 38, and a crossbar scheduler 40. The crossbar scheduler receives a signal, referred to as a request, from an input queue. The request dictates the output channel or channels that will receive the
queued packet. The scheduler arbitrates between competing requests and sends a signal, referred to as a grant, back to the input buffers that have been selected to deliver a packet.
In switches such as the switch 10 described in reference to FIG. 1, each input queue 28-36 provides requests to the scheduler 40, one at a time, on a first-in-first-out (FIFO) basis and the scheduler arbitrates among the four requests received
from the four input queues, with a goal of maximizing utilization of the input channels 12-18 and output channels 20-26 of the switch. As a grant is issued to a particular input channel to access a target output channel or channels, a new request is
accessible by the scheduler in place of the granted request.
A problem known as head-of-line (HOL) blocking is created when one of the requests at the head of a queue line is a request for an output channel that is not available. HOL blocking is common when a multicast request is made, because there is a
lower probability that all of the output channels for the multicast request will be available immediately. When a request from a particular input channel is forced to wait until all output channels are available, all of the packets associated with the
particular input channel are also forced to wait, thereby slowing the transfer of data from that input channel.
As one remedy for solving HOL blocking problems, parallel input queues have been implemented. Parallel input queues provide a separate FIFO queue for each output channel of the switch, with each queue providing a corresponding request to the
scheduler. Referring to FIG. 2, an N input channel by N output channel switch requires N input queues 46 for each input channel, for a total of N.sup.2 input queues. With an N.sup.2 scaling factor, the number of input queues connected to the crossbar
scheduler 50 may be very high. For example, in a 16.times.16 switch, 256 separate queues are required. In spite of the added complexity, the advantage that the parallel design provides is that, with respect to any one of the input channels, a series of
requests for available output channels is not held up by a single request for in-use output channels.
A variety of arbitration techniques can be used with parallel input channels to provide an efficient throughput through a switch. For example, maximum matching algorithms are designed in an attempt to assign output channels to input channels in
such a way that a maximum number of transfers occur simultaneously. However, under heavy load conditions, maximum matching algorithms can prevent some requests from being granted, creating a new blocking problem. For example, referring to FIG. 3, input
channel 1 is represented as requesting a transfer of cells from its output-distributed queue 54 to output channel 1 only, while input channel 2 is requesting a transfer of cells from its output-distributed queue 56 to output channels 1 and 2. Under a
maximum matching approach, input channel 1 transmits cells to output channel 1 and input channel 2 transmits cells to output channel 2. However, input channel 2 will be blocked from transferring cells destined for output channel 1, since this would
require the cell transfer from input channel 1 to output channel 1 to stop, and as a result, only output channel 1 would be utilized. As shown in FIG. 4, sending cells from input channel 2 to output channel 1 causes input channel 1 and output channel 2
to remain idle and does not achieve maximum matching.
Arbitration methods developed to optimize performance of high speed switches utilizing parallel input queues are disclosed in U.S. Pat. No. 5,500,858, entitled "Method and Apparatus for Switching Cells in an Input-Queued Switch," issued to
McKeown and in U.S. Pat. No. 5,517,495, entitled "Fair Prioritized Scheduling in an Input-Buffered Switch," issued to Lund et al. Although these arbitration approaches are effective for their intended purpose, they both require that an N.times.N switch
have N.sup.2 distinct FIFO input queues. Since there are N.sup.2 distinct FIFO input queues, there will also be N.sup.2 requests delivered to the scheduler. As the number of input and output channels increases, the complexity of providing N.sup.2 input
queues and sending N.sup.2 requests to the scheduler becomes costly and difficult to implement.
In addition to the problem of added complexity, the output-distributed queue architecture does not easily support multicast requests, which are more common in network protocols such as ethernet than in network protocols such as ATM. For example,
in order to utilize the output-distributed architecture of FIG. 2 to satisfy a multicast request, the cell that is to be multicasted must either be replicated into all of the output channel queues that are indicated by the request or a separate multicast
queue must be established in addition to the N.sup.2 queues already present.
A third concern is that output distributed queue architectures do not readily enable a switch to provide quality of service (QoS) guarantees for packet transfers across a switch. For example, in an enterprise network, there are many different
packet flows having different sources, destinations, and packet protocols. Because of user-specific needs, some packet flows are deemed more critical to the enterprise than other packet flows and can be prioritized accordingly. For example, a packet
flow related to a mission-critical application (i.e., SAP, People Soft, Baan, or Custom Client/Server applications) can be assigned a different QoS priority than HTTP-based Internet traffic. A QoS priority can then be related to specific forwarding
rules or transfer rate limits across the network switch to provide different levels of service. In the queue arrangements of FIGS. 1 and 2, packets, or their related requests, are not differentiated by QoS priority and, as a result, a high priority
packet is forwarded through the switch in the same manner as a lower priority packet. In, for example, an enterprise network environment, non-prioritized queue arrangements may mean that packets carrying time-critical video teleconferencing data are
treated the same as packets carrying non-time-critical e-mail messages, thereby causing severe degradation in the video teleconferencing performance.
As a result of the shortcomings of conventional output-distributed queue architecture, what is needed is a method and apparatus that limit the number of input queues and the complexity of sending requests to a scheduler, while maintaining fair
and efficient scheduling and providing QoS functionality.
SUMMARY OF THE INVENTION
A method and an apparatus for scheduling data packets in a multipoint switch utilize request buffers having multilevel request registers linked in parallel to a scheduler that arbitrates among requests based upon the location of the requests
within the multilevel request buffers and based upon a quality of service (QoS) priority assigned to the requests in order to maximize data packet transfer through the switch, while adhering to QoS requirements. To arbitrate among requests based upon
request buffer location and QoS priority, the scheduler sorts all of the available requests by QoS priority and issues grants on a QoS priority basis in a channel-by-channel arbitration process. Since there can be more than one request of the same QoS
priority stored in a multilevel request buffer of a single channel, the location of a request stored within a multilevel request buffer, referred to as the request buffer priority, is used to award a grant among requests having the same QoS priority. To
ensure that conflicting grants are not issued for requests of different QoS priorities, a mask generation and compare process is used to block conflicting requests of lower QoS priority from entering the grant process.
The preferred multipoint switch has sixteen input channels and sixteen output channels, with each input channel having a request buffer with four request registers. The four request registers have different request buffer priorities and the
requests stored in the registers are scheduled at least partially based upon their request buffer priorities. The requests also have a QoS priority that is assigned to each request based upon the source, destination, and/or application of the
corresponding data packet. There are four QoS priority designations, referred to as control, high, medium, and low and the QoS priority of a packet is unrelated to the request buffer priority of the same packet.
The sixteen request buffers are connected to a data path multiplexer and a scheduler. The four request registers from each of the sixteen request buffers along with four QoS priority registers are connected in parallel to the scheduler, such
that the scheduler can simultaneously access all sixty-four of the available requests and identify their respective QoS priorities. The request buffers are filled from peripheral systems and prioritized based upon the age of the requests in the buffer,
with the oldest request having the highest request buffer priority and the newest request having the lowest request buffer priority. Whenever a grant is issued in response to a request, the request buffer adjusts on a FIFO basis, thereby leaving a
vacant request register at the lowest request buffer priority. The vacant request register then receives a new request that takes on the lowest request buffer priority.
The scheduler of the preferred embodiment includes a mask generator unit, four QoS priority-specific request multiplexing units (RMUs), four QoS priority-specific multilevel schedulers (MLSs), a global resource manager, and a frame counter. The
mask generator unit is a circuit that generates three QoS priority-specific masks that are utilized in the scheduling process to indicate which output channels are identified by requests having a QoS priority level higher than a designated minimum QoS
priority level. There are only three masks since there can be no higher QoS priority level if the highest priority (i.e., control QoS priority) is the "designated minimum QoS priority level." In the preferred 16.times.16 switch, QoS priority-specific
masks consist of 16-bit vectors where each bit is dedicated to one of the output channels. The three QoS priority-specific masks are generated from the control, high, and medium priority requests. Specifically, the control priority mask is a 16-bit
vector that represents all outputs which are being requested by the pending control priority requests, the high priority mask is a 16-bit vector that represents all outputs that are being requested by the pending control priority requests and the pending
high priority requests, and the medium priority mask is a 16-bit vector that represents all outputs that are being requested by the combination of pending control priority requests, pending high priority requests, and pending medium priority requests.
The four QoS priority-specific RMUs are circuits that sort all of the incoming requests based on QoS priority and then compare the sorted requests to the QoS priority-specific masks. For each input channel, the priority-specific RMUs output to
the MLSs as many as four requests (one for each of the four request buffer priorities). In operation, the RMU for a particular QoS priority cycles through the requests for each channel and sorts out any requests that are in the particular QoS priority.
If a channel, for example channel 0, has any of the QoS priority requests active in the request buffer registers, then the requests will be forwarded through the RMU. In the case of the high, medium, and low priority RMUs, the forwarded requests are
sent through mask compare units. However, in the case of the control priority RMU, mask compare units are not necessary because there are no higher priority requests that need to be masked out of the MLSs. In the mask compare process, requests from a
specific QoS priority are compared to a mask that represents all requests of higher QoS priority. For example, the high priority requests are compared to the control priority mask to block high priority requests that conflict with pending control
priority requests. The mask compare process prevents conflicting lower priority requests from entering the MLSs and guarantees that each input only receives a single grant in one arbitration cycle and that each output is allocated to only one input.
Because the control priority is the highest QoS priority, no masking process is required in the control priority RMU. Once the mask compare process is complete within each RMU, any requests from the four request buffer priority levels that have not been
masked out are forwarded to the respective QoS priority-specific MLS.
The four QoS priority-specific MLSs are arranged to receive QoS priority-sorted and masked (except for the control priority) requests from the RMUs. The MLSs utilize a strict request buffer priority scheme to arbitrate among requests of the same
QoS priority and from the same channel. In addition to the strict request buffer priority scheme, the MLSs utilize a round-robin scheme to arbitrate among requests of the same QoS priority but different channels. To facilitate scheduling on a request
buffer priority basis, each QoS priority-specific MLS includes four 16-stage round-robin schedulers that correspond to the four request buffer priorities. In operation, the round-robin schedulers receive request buffer prioritized requests from the RMUs
for a single QoS priority and a single channel and then compare input and output vectors to the requesting channel and to the request vector to determine if a grant can be issued. Any grants issued from the round-robin schedulers for a particular QoS
priority are forwarded to a QoS priority-specific priority encoder unit.
The QoS priority-specific priority encoder units within each MLS are the circuits that are responsible for implementing the request buffer priority scheme. When there are one or more possible grants transmitted to a priority encoder unit from
the four round-robin schedulers within an MLS, the priority encoder unit picks the grant corresponding to the request with the highest request buffer priority and passes the QoS priority-specific grant on to the requesting channel.
In order to ensure that conflicting grants are not issued within each MLS, a local resource manager is located within each MLS. Each local resource manager receives updated input and output vectors from a global resource manager at the start of
each arbitration cycle. Each time a grant is issued within a particular MLS, the input vector and output vector within the MLS are updated appropriately by the local resource manager. Upon completion of an arbitration cycle, updated QoS
priority-specific input vectors and output vectors are sent from each local resource manager to the global resource manager.
The global resource manager is responsible for maintaining the status of global input and output vectors within the scheduler. As stated, the global resource manager receives updated input and output vectors from each MLS at the completion of
each arbitration cycle. Upon receiving the updated QoS priority-specific input and output vectors, the global resource manager aggregates all of the priority-specific vectors to create updated global input and output vectors. The updated global input
and output vectors are then fed back to the local resource managers before the next arbitration cycle.
Round-robin managers located within each of the priority-specific MLSs promote fairness between requests of the same QoS priority level but of different channels. Under the round-robin scheme, a particular channel is initially designated as
having the highest round-robin priority and when the high priority channel receives a grant the high round-robin priority designation is shifted to the next channel. Note that round-robin priority is relevant to the channel priority order inside the
four round-robin schedulers of each MLS and is different from the request buffer priority and the QoS priority related to each request. Round-robin priority is maintained independently by each MLS and requests are processed between channels in
round-robin priority such that the requests from channels with higher round-robin priority are granted access to output channels before requests from lower round-robin priority channels.
The frame counter within the scheduler provides timing signals in the form of clock signals and framing pulses to the MLSs. The timing signals provided by the frame counter ensure that the four QoS priority-specific arbitration processes are
synchronized.
In the operation of one arbitration cycle, the scheduler first generates three QoS priority-specific masks. Next, the sixty-four requests are sorted and processed by four QoS priority-specific request multiplexer/multilevel scheduler
combinations. Each request multiplexer/multilevel scheduler combination processes the requests on a channel-by-channel basis over sixteen clocks, with each combination maintaining its own round-robin channel priority. Grants are issued from each QoS
priority-specific multilevel scheduler and channel conflicts between grants are prevented by the mask compare process that is performed in the request multiplexers.
An advantage of the invention is that the sixteen request buffers with four request registers per buffer utilized in a 16.times.16 switch are significantly less complex than the 256 queues required for a 16.times.16 switch using a conventional
output-distributed scheduling architecture. In addition, the multilevel request buffers eliminate the HOL blocking problem because the scheduler has simultaneous and in-parallel access to more than one request for each input channel. Further, by
dividing the scheduler into QoS priority-specific scheduling modules, QoS requirements can be implemented in a high volume non-blocking switch circuit.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram of a prior art switch that has four input channels and four output channels.
FIG. 2 is a prior art N input channel by N output channel switch with N.sup.2 output-distributed input queues.
FIG. 3 is a depiction of the transferring of cells from output-distributed input queues to output channels where maximum matching between input and output channels is achieved using prior art techniques.
FIG. 4 is a depiction of the transferring of cells from output-distributed input queues to output channels where maximum matching between input and output channels is not achieved using the prior art techniques.
FIG. 5 is a diagram of the switch architecture in accordance with the present invention.
FIG. 6 is a diagram of a data packet and an expanded switching cell that is transmitted through the switch fabric of FIG. 5.
FIG. 7 is an expanded diagram of a channel module as shown in FIG. 5.
FIG. 8 is a depiction of the crossbar of FIG. 5 that includes a more detailed representation of the connections that are made between the channel modules, the scheduler, and the data path multiplexer in accordance with the invention.
FIG. 9 is a logic diagram of the scheduler in accordance with the invention.
FIG. 10 is an expanded logic diagram of a request multiplexing unit and a multilevel scheduler as shown in FIG. 9 in accordance with the invention.
FIG. 11A is a depiction of the preferred arbitration process for the control QoS priority in accordance with the invention.
FIG. 11B is a depiction of the preferred arbitration process for the high QoS priority in accordance with the invention.
FIG. 11C is a depiction of the preferred arbitration process for the medium QoS priority in accordance with the invention.
FIG. 11D is a depiction of the preferred arbitration process for the low QoS priority in accordance with the invention.
FIG. 12 is a depiction of a preferred method of scheduling cells in accordance with the invention.
DETAILED DESCRIPTION
FIG. 5 is a depiction of the preferred architecture of a multipoint switch that is compatible with network protocols such as ethernet and TCP/IP. Although a 16-channel switch is shown for description purposes, the switch may have a different
number of channels. The preferred architecture includes data links 22, 24, 26, and 28 connected to input/output (I/O) controllers 12, 14, 16, and 18. The I/O controllers are connected to channel-specific packet processing units 82, 84, 86, and 88,
which are connected to channel modules 112, 114, 116, and 118 of a switch crossbar 60. The channel modules are connected separately to a data path multiplexer 130 and a scheduler 132. The preferred embodiment of the invention provides a method and
apparatus for fair and efficient scheduling of variable-size data packets in an input buffered multi-channel switch.
The data links 22-28 connected to the I/O controllers 12-18 provide the medium for transferring packets of data into and out of the switch. In a preferred embodiment, the number of data links connected to each I/O controller is based on the
bandwidth capacity of the data link. For example, the single and double data links 22, 24, and 26 represent 1,000 Megabits per second (Mbps) connections and the eight data links 28 represent 10 and/or 100 Mbps connections, although these connection
bandwidths can be smaller or larger. In addition, the physical makeup of the data links is preferably twisted pair wires and/or single mode optical fiber, although other data links such as coaxial cable, multi-mode optical fiber, infrared, and/or radio
frequency links are possible.
The I/O controllers 12-18 connected to the data links 22-28 and the packet processing units 82-88 provide the pack | | |
