[go: up one dir, main page]

WO1999035792A1 - Procede assurant des delais independants de la taille des repartiteurs dans un central crossbar accelere - Google Patents

Procede assurant des delais independants de la taille des repartiteurs dans un central crossbar accelere Download PDF

Info

Publication number
WO1999035792A1
WO1999035792A1 PCT/US1999/000684 US9900684W WO9935792A1 WO 1999035792 A1 WO1999035792 A1 WO 1999035792A1 US 9900684 W US9900684 W US 9900684W WO 9935792 A1 WO9935792 A1 WO 9935792A1
Authority
WO
WIPO (PCT)
Prior art keywords
output
input
channel
queues
switch
Prior art date
Application number
PCT/US1999/000684
Other languages
English (en)
Inventor
Anna Charny
Pattabhiraman Krishna
Naimish Patel
Robert J. Simcoe
Original Assignee
Cabletron Systems, Inc.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Cabletron Systems, Inc. filed Critical Cabletron Systems, Inc.
Priority to AU23174/99A priority Critical patent/AU736780B2/en
Priority to CA002318163A priority patent/CA2318163A1/fr
Priority to EP99903061A priority patent/EP1048151A1/fr
Publication of WO1999035792A1 publication Critical patent/WO1999035792A1/fr

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/25—Routing or path finding in a switch fabric
    • H04L49/253—Routing or path finding in a switch fabric using establishment or release of connections between ports
    • H04L49/254—Centralised controller, i.e. arbitration or scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
    • H04Q11/0478—Provisions for broadband connections
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/10—Packet switching elements characterised by the switching fabric construction
    • H04L49/101—Packet switching elements characterised by the switching fabric construction using crossbar or matrix
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/30—Peripheral units, e.g. input or output ports
    • H04L49/3018—Input queuing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/30—Peripheral units, e.g. input or output ports
    • H04L49/3027—Output queuing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/30—Peripheral units, e.g. input or output ports
    • H04L49/3045—Virtual queuing

Definitions

  • the present invention relates generally to variable and fixed size packet switches, and more particularly, to an apparatus and method for scheduling packet cell inputs through such packet switches.
  • output-buffered or shared memory non-blocking architectures require the existence of high-speed memory.
  • an output-buffered switch requires that the speed of memory at each output must be equal to the total speed of all inputs.
  • the rate of the increase in memory speed available with current technology has not kept pace with the rapid growth in demand for providing large-scale integrated services networks.
  • building an output buffered switch at this speed has become a daunting task given the present state of technology. Similar issues arise with shared memory switches as well.
  • WPIM Weighted Probabilistic Iterative Matching
  • an algorithm allows for the emulation of a non-blocking output- buffered switch with an output FIFO queue by using an input-buffered crossbar with speedup independent of the size of the switch. See B. Prabhakar and N. McKeown, "On the Speedup Required for Combined Input and Output Queued Switching," Computer Systems Lab. Technical Report CSL-TR-97-738, Stanford University. More specifically, this reference shows that such emulation is possible with a speedup of 4 and conjectures that a speedup of 2 may suffice.
  • the above and other purposes are attained by a method of providing delay performance independent of a switch size in an input-buffered switch with a speedup S greater than two having input channels and output channels for transferring cells therebetween.
  • the method includes providing, to each of the input channels, per-output-channel queues to buffer cells awaiting transfer to the output channels, each per-output-channel queue being associated with a respective input channel and output channel, and having an assigned rate and an ideal service associated therewith; providing an arbiter to control transmission of buffered cells from input channels to output channels, the arbiter having a rate controller to schedule at a given cell slot the queues in the input channels, the rate controller to guarantee to each queue an amount of actual service that is within fixed bounds from the ideal service of the queue, the fixed bounds each being equal to one cell.
  • a pair of state variables is maintained including a first and a second state variable, the first state variable corresponding to an ideal beginning time of a next cell of the per-output queue and the second state variable corresponding to an ideal finishing time of transmission of the next cell of the per-output queue.
  • the method further includes initializing the first and second state variables, the first state variable being equal to one and the second state variable being equal to one divided by the assigned rate; initializing an arbiter clock counter to count switch phases to zero; providing a set match set and a set _queues set; initializing the set match set to include an empty set and the set_queues set to include all of the pairs; running the rate controller to select from the set_queues set ones of the pairs having a smallest eligible finish time first and, for the selected pair, updating the first state variable with the ideal finish time and the second state variable with an ideal beginning time plus one divided by the assigned rate; adding the selected pair to the set_match set; removing from the set_queues set those pairs corresponding to the same input channel and output channel as the selected pair; determining whether or not the set_queues set is empty.
  • the method includes notifying the input channels of the per-output- channel queues corresponding to those pairs added to the setjmatch set, incrementing the counter by one and returning to the step of initializing the set_match and set_queues sets; and when the set_queues set is determined to be not empty, then returning to the step of running the rate controller.
  • the present invention achieves several important goals. It provides per cell/packet delay independent of the switch size comparable to delay guarantees associated with non-blocking output-buffered architectures, while utilizing the scalability of a crossbar. It allows arbitrary assignment of rates (as long as the rates are feasible in the sense that the sum of all rates does not exceed the total available bandwidth at any input or any output). Additionally, it allows the flexibility to quickly admit new flows and change the rate assignment of existing flows. Moreover, it ensures protection of well-behaved flows against misbehaved flows. More specifically, simulations indicate that such a system is capable of providing delays comparable to those of an output buffered switch, with any speedup of greater than or equal to two, and the delays observed are independent of switch size.
  • the invention is primarily related to providing per-packet/cell delays to guaranteed flows, it can be used in conjunction with best-effort traffic as well. If best effort traffic is present, it is assumed that the invention as described herein is run at an absolute priority over any scheduling algorithm for best effort traffic.
  • FIG. 1 is block diagram depicting an input-buffered crossbar switch capable of utilizing per-output-channel queue scheduling and arbitration schemes in accordance with the present invention
  • FIG. 2 is a flow diagram illustrating a queue scheduling and arbitration scheme for providing delays independent of the switch size in accordance with the present invention.
  • an input-buffered crossbar switch 10 implementing a crossbar arbitration scheme in accordance with the present invention.
  • the underlying architecture of the input- buffered crossbar switch 10 is represented as an n x m crossbar.
  • " «" is the number of input channels / (1 ⁇ i ⁇ n) 12
  • "w” is the number of output channels/ (1 ⁇ j ⁇ m) 14.
  • Each input channel has one or more input ports 16, each of which corresponds to a physical input link 18.
  • the output channels each have one or more output ports 20, each corresponding to a physical output link 22.
  • the input channels 12 are connected to the output channels 14 by way of a crossbar unit 24.
  • the crossbar unit as depicted in FIG. 1 includes a crossbar switch fabric of known construction, the details of which have been omitted for purposes of simplification. It is the crossbar switch fabric that is responsible for transferring cells between input and output channels.
  • the total capacity of all input channels and all output channels is assumed to be the same, although the capacity of individual links may be different.
  • r_c the capacity of a single channel
  • the speed of the switch fabric, denoted by rjsw is assumed to be S times faster than the speed of any channel.
  • the switch and the channel clocks are not assumed to be synchronized.
  • the speedup values may be arbitrary (and not necessarily integer) values in the range of 1 ⁇ S ⁇ n. It is further assumed that the switch operates in phases of duration Tjsw defined as the time needed to transmit a unit of data at speed r_sw. Such phases are referred to as matching phases.
  • packets received on a given input link 18 are typically buffered at the input ports.
  • each flow to which the received packets correspond may be allocated a separate buffer or queue at the input channel.
  • These "per-flow" queues may be located in an area of central memory within the input channel. Alternatively, flow queues may be located in a memory in the input ports associated with the input channel.
  • the packets received from the input links are of variable length, they are fragmented into fixed-size cells. If the packets arriving at the switch all have a fixed length, e.g., a cell in ATM networks, no fragmentation is required. In packet switching networks, where arriving packets are of different sizes, the implementation is free to choose the size of the cell as is convenient.
  • Rates assigned to guaranteed flows can also be changed during a renegotiation of service parameters as allowed by the current RSVP specification. It is assumed that the rate assignment is feasible, i.e., the sum of the rates of all flows at each input port channel does not exceed the capacity of this input port channel, and the sum of rates of all flows across all input ports destined to a particular output port does not exceed the capacity of that output port. If the sum of port capacities equals the channel capacity as assumed here, the feasibility of rates across all input and output ports implies the feasibility of rates across all input and output channels.
  • Rate r J assigned to the flow is any overhead associated with packet fragmentation and re-assembly.
  • the actual data rate negotiated at connection setup may therefore be lower.
  • no segmentation and re-assembly is required. Thus, no overhead is present.
  • each input channel 12 has m virtual output queues (VOQs) or per- output-channel queues 26 (also referred to as per-output or virtual output queues), denoted by Q(i,j), 1 ⁇ j m, one for each output channel/ 14.
  • the input channel maintains a single flow-level scheduler S_f(i) 28, which needs to schedule only a single flow per cell time. Once scheduler S_f(i) schedules some flow/, it adds the index of this flow/ (or, alternatively, the head of the line (HOL) cell of flow f) to the tail of queue Q(i,j).
  • Q(i,j) may contain either cells or pointers to cells of individual flows. Any known QoS-capable scheduler, such as those described above, can be used for the S 7 scheduler.
  • each input channel could maintain one flow-level scheduler SJ( ⁇ i,j) for each output. When the input channel i needs to transmit a cell to a given output/, it invokes scheduler S_f(ij) to determine which flow destined to/ should be chosen.
  • the flow-level schedulers SJ(i,j) must be capable of choosing up to S cells per cell time as it is possible that this input may need to send a cell to the same output in all S matching phases of the current cell slot.
  • the input can run m parallel S_/schedulers, one per output. Each of these schedulers may schedule 1 ⁇ k ⁇ S cells per cell time. When a flow is scheduled by S_f, an index to this flow is added to Q(i,j).
  • arbiter 30 is also included in the input-buffered crossbar switch 10 . It is the arbiter's responsibility to determine which of the input channels should be able to transmit a cell to particular output channels, i.e., cells from which per-output-channel queues should be transmitted. It is assumed that arbiter 24 operates in matching phases. The duration of each phase is equal to the duration of the channel cell slot divided by the speedup S. The goal of the arbiter is to compute a maximal (conflict-free) match between the input and output channels so that at most one cell leaves any input channel and at most one cell enters any output channel during a single matching phase.
  • maximal match (or, alternatively, “maximal matching”) is well understood by those skilled in the art, a definition may be had with reference to papers by N. McKeown et al. and Stiliadis et al., cited above, as well as U.S. Patent No. 5,517,495 to Lund et al.
  • the arbiter decides which input can send a cell to which output by computing a maximal matching between all inputs and all outputs.
  • the algorithm used to compute the maximal match is described in detail in paragraphs to follow.
  • the arbiter notifies each input of the output to which it can send a cell by sending to the input channel the index of the per-output queue from which the cell is to be transmitted. The input channel then picks a cell to send to that output channel and the cell is transmitted to the output channel.
  • the arbiter 30 maintains for each input/output pair i j, a pair of variables (bj,j, f_i,j) denoted as A(ij) ' 32. How the arbiter utilizes these input/output pairs will be described in detail later with reference to FIG. 2.
  • an input channel 12 When an input channel 12 receives from the arbiter 24 the index of the Q(i,j) corresponding to the output channel 14 for the current matching phase, it forwards the HOL cell o ⁇ Q(i,j) (or, alternatively, the cell pointed to by the HOL pointer in Q(ij) ) to the output channel /. If Q(i,j) is empty that is, there is no cell of a guaranteed flow in the queue, then a cell of a lower-priority service destined to the same output is sent instead. If there is no best effort traffic at this input matching phase, then no cell is sent.
  • a cell forwarded by an input channel i to an output channel / is added to a queue maintained by the output channel.
  • queuing disciplines can be used, such as FIFO, per-input-port, or per flow.
  • each output has an additional scheduler, shown in FIG. 1 as output scheduler S o 34. This output scheduler determines the order in which cells are transmitted onto the output link from the output channel. It is assumed that any required reassembly occurs before S o is used, so that S o schedules packets rather than cells.
  • Any known QoS-capable scheduler such as those mentioned above can be used for the schedule S o.
  • each scheduler S_f, S_o operates independently of the other, the delay of an individual cell in the switch is the sum of the delay of this cell under its input and output schedulers S " and S_o, plus the delay due to the potential arbitration conflicts.
  • the delay of a packet segmented in cells is comprised of the delay experienced by its last cell plus the segmentation and re-assembly delays.
  • each of the queues Q(i j) contains cells (or pointers to cells) which have already been scheduled by S_/but which have not yet been transmitted to their destination output channel with which the VOQ is associated due to arbitration conflicts.
  • the present invention undertakes the task of deterniining the sequence of transmissions between input channels and output channels satisfying the crossbar constraint that only one cell can leave an input channel and enter an output channel per phase in such a way that the arbitration delay is bounded for each cell awaiting its transmission at the input channel.
  • the arbiter maintains a pair of variables (b_i,j, fj,j) or A(ij) for each input/output pair ,/.
  • These variables b_i,j and f_i,j will be referred to as starting time and finish time, respectively.
  • the starting time is the ideal beginning time of transmission of the next cell of the queue with which the input/output pair is associated.
  • the finish time is the ideal finishing time of transmission of the next cell of the queue with which the input/output pair is associated.
  • the arbiter obtains for each input/output pair i,j the rate r_i,j, which is the sum of the assigned rates of all flows going from input / to output/. Also, in the same step, variables b_i,j and f_i,j are initialized (to zero and ⁇ lr_i,j, respectively) and a count value time is set to zero. As further illustrated in FIG. 2, at each matching phase the arbiter computes the maximal match as follows. In step 44, the arbiter initializes a SetJAatch set to an empty set and a Set Queues set to all A(i,j). Now referring to step 46 in FIG.
  • the arbiter selects the pair A(i,j) having the smallest finish time /N among all eligible pairs, where eligible pairs are defined as those whose starting time b_i,j is at or before the current time.
  • step 54 the arbiter returns to step 46 and performs the next iteration of the matching process. Otherwise, the matching is complete.
  • step 56 for each A(i,j) in the match, the arbiter informs the input i to send to all output/. As can be seen, the A(i,j) in the match correspond to the per-output-channel queues Q(i,j) from which a cell should be transmitted in the current matching phase. The arbiter then proceeds to the next matching phase, incrementing count time by one (step 58) and updating the rates r_i,j as necessary (step 60) before returning to step 44.
  • the delay bound is a function of the size of the switch (i.e., the number of input/channels).
  • the arbiter of the present invention runs a single rate controller across all queues regardless of the input or output channels to which they correspond and uses finish times (rather than scheduled times) as described above.
  • the input rate controllers which schedule per-output queues at each input are oblivious to potential arbitration conflicts. The arbitration conflicts are resolved at the arbiter using timestamps of the scheduling times of the input rate controllers.
  • the rate controller which is run in the arbiter uses ideal start and finish times of all input/output pairs directly and explicitly resolves arbitration conflicts as part of the operation of the rate controller.
  • the advantage of the present invention is that the observed delays are independent of the size of the switch and depends only on the rate of the flow.
  • the rate controller must operate at the faster speed of the switch fabric whereas the input channel rate-controllers in the co-pending application need to operate at a slower channel speed.
  • the size of the input to the rate-controller in the present invention is man, whereas in the co-pending invention the input to each of the rate- controllers is only m.
  • the implementation of the co-pending invention may be less expensive, especially at high speeds.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

L'invention porte sur un schéma d'ordonnancement et d'arbitrage dans un central à mise en tampon des entrées à largeur de bande déterministe accélérée et délai d'attente indépendant de la taille du central. Le schéma d'ordonnancement et d'arbitrage qui présente un cadre à structure crossbar à plusieurs canaux d'entrée et de sortie détermine la séquence des transmissions de paquets de taille fixe ou de cellules entre les canaux d'entrée et les canaux de sortie en satisfaisant à la restriction selon laquelle une seule cellule peut quitter un canal d'entrée et entrer dans un canal de sortie par phase de façon telle que le délai d'arbitrage soit limité pour chacune des cellules attendant d'être transmise au niveau du canal d'entrée. Si les paquets de taille fixe résultent de la fragmentation de paquets de dimensions variables, le schéma d'ordonnancement et d'arbitrage implique que si des garanties de délais sont données au niveau des cellules, elles le soient également au niveau des paquets initiaux de taille variable, même lorsqu'ils ont été reconstitués au niveau du canal de sortie.
PCT/US1999/000684 1998-01-12 1999-01-12 Procede assurant des delais independants de la taille des repartiteurs dans un central crossbar accelere WO1999035792A1 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
AU23174/99A AU736780B2 (en) 1998-01-12 1999-01-12 Method for providing delays independent of switch size in a crossbar switch with speedup
CA002318163A CA2318163A1 (fr) 1998-01-12 1999-01-12 Procede assurant des delais independants de la taille des repartiteurs dans un central crossbar accelere
EP99903061A EP1048151A1 (fr) 1998-01-12 1999-01-12 Procede assurant des delais independants de la taille des repartiteurs dans un central crossbar accelere

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US574098A 1998-01-12 1998-01-12
US09/005,740 1998-01-12

Publications (1)

Publication Number Publication Date
WO1999035792A1 true WO1999035792A1 (fr) 1999-07-15

Family

ID=21717481

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1999/000684 WO1999035792A1 (fr) 1998-01-12 1999-01-12 Procede assurant des delais independants de la taille des repartiteurs dans un central crossbar accelere

Country Status (4)

Country Link
EP (1) EP1048151A1 (fr)
AU (1) AU736780B2 (fr)
CA (1) CA2318163A1 (fr)
WO (1) WO1999035792A1 (fr)

Cited By (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2364469A (en) * 2000-07-05 2002-01-23 Roke Manor Research Switching devices
US6757246B2 (en) 2001-08-14 2004-06-29 Pts Corporation Method and apparatus for weighted arbitration scheduling separately at the input ports and the output ports of a switch fabric
US6973036B2 (en) 2001-11-01 2005-12-06 International Business Machines Corporation QoS scheduler and method for implementing peak service distance using next peak service time violated indication
US6982986B2 (en) 2001-11-01 2006-01-03 International Business Machines Corporation QoS scheduler and method for implementing quality of service anticipating the end of a chain of flows
US6990072B2 (en) 2001-08-14 2006-01-24 Pts Corporation Method and apparatus for arbitration scheduling with a penalty for a switch fabric
US7046626B2 (en) 2000-07-05 2006-05-16 Roke Manor Research Limited Switching devices
US7046676B2 (en) 2001-11-01 2006-05-16 International Business Machines Corporation QoS scheduler and method for implementing quality of service with cached status array
US7103051B2 (en) 2001-11-01 2006-09-05 International Business Machines Corporation QoS scheduler and method for implementing quality of service with aging time stamps
US7187684B2 (en) 2001-11-01 2007-03-06 International Business Machines Corporation Weighted fair queue having extended effective range
US7257124B2 (en) 2002-03-20 2007-08-14 International Business Machines Corporation Method and apparatus for improving the fairness of new attaches to a weighted fair queue in a quality of service (QoS) scheduler
US7280474B2 (en) 2001-11-01 2007-10-09 International Business Machines Corporation Weighted fair queue having adjustable scaling factor
US7310345B2 (en) 2001-11-01 2007-12-18 International Business Machines Corporation Empty indicators for weighted fair queues
US7317683B2 (en) 2001-11-01 2008-01-08 International Business Machines Corporation Weighted fair queue serving plural output ports
US7408959B2 (en) * 2002-06-10 2008-08-05 Lsi Corporation Method and apparatus for ensuring cell ordering in large capacity switching systems and for synchronizing the arrival time of cells to a switch fabric
US7680043B2 (en) 2002-03-20 2010-03-16 International Business Machines Corporation Network processor having fast flow queue disable process
US8964771B2 (en) 2005-04-15 2015-02-24 Altera Corporation Method and apparatus for scheduling in a packet buffering network

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112608891B (zh) * 2020-12-18 2023-06-30 云南中科灵长类生物医学重点实验室 一种间充质干细胞无血清培养基及其应用

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2293720A (en) * 1994-09-30 1996-04-03 Roke Manor Research ATM queuing and scheduling apparatus
WO1997031460A1 (fr) * 1996-02-22 1997-08-28 Fujitsu Ltd. Procede et dispositif permettant de coordonner les acces a la sortie d'un dispositif d'acheminement dans un reseau de commutation par paquets
EP0817436A2 (fr) * 1996-06-27 1998-01-07 Xerox Corporation Système de communication à commutation par paquets

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2293720A (en) * 1994-09-30 1996-04-03 Roke Manor Research ATM queuing and scheduling apparatus
WO1997031460A1 (fr) * 1996-02-22 1997-08-28 Fujitsu Ltd. Procede et dispositif permettant de coordonner les acces a la sortie d'un dispositif d'acheminement dans un reseau de commutation par paquets
EP0817436A2 (fr) * 1996-06-27 1998-01-07 Xerox Corporation Système de communication à commutation par paquets

Cited By (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2364469B (en) * 2000-07-05 2004-03-17 Roke Manor Research Improvements in or relating to switching devices
GB2364469A (en) * 2000-07-05 2002-01-23 Roke Manor Research Switching devices
US7046626B2 (en) 2000-07-05 2006-05-16 Roke Manor Research Limited Switching devices
US6990072B2 (en) 2001-08-14 2006-01-24 Pts Corporation Method and apparatus for arbitration scheduling with a penalty for a switch fabric
US6757246B2 (en) 2001-08-14 2004-06-29 Pts Corporation Method and apparatus for weighted arbitration scheduling separately at the input ports and the output ports of a switch fabric
US7103051B2 (en) 2001-11-01 2006-09-05 International Business Machines Corporation QoS scheduler and method for implementing quality of service with aging time stamps
US6982986B2 (en) 2001-11-01 2006-01-03 International Business Machines Corporation QoS scheduler and method for implementing quality of service anticipating the end of a chain of flows
US7046676B2 (en) 2001-11-01 2006-05-16 International Business Machines Corporation QoS scheduler and method for implementing quality of service with cached status array
US6973036B2 (en) 2001-11-01 2005-12-06 International Business Machines Corporation QoS scheduler and method for implementing peak service distance using next peak service time violated indication
US7187684B2 (en) 2001-11-01 2007-03-06 International Business Machines Corporation Weighted fair queue having extended effective range
US7280474B2 (en) 2001-11-01 2007-10-09 International Business Machines Corporation Weighted fair queue having adjustable scaling factor
US7310345B2 (en) 2001-11-01 2007-12-18 International Business Machines Corporation Empty indicators for weighted fair queues
US7317683B2 (en) 2001-11-01 2008-01-08 International Business Machines Corporation Weighted fair queue serving plural output ports
US7257124B2 (en) 2002-03-20 2007-08-14 International Business Machines Corporation Method and apparatus for improving the fairness of new attaches to a weighted fair queue in a quality of service (QoS) scheduler
US7680043B2 (en) 2002-03-20 2010-03-16 International Business Machines Corporation Network processor having fast flow queue disable process
US7408959B2 (en) * 2002-06-10 2008-08-05 Lsi Corporation Method and apparatus for ensuring cell ordering in large capacity switching systems and for synchronizing the arrival time of cells to a switch fabric
US8964771B2 (en) 2005-04-15 2015-02-24 Altera Corporation Method and apparatus for scheduling in a packet buffering network

Also Published As

Publication number Publication date
AU736780B2 (en) 2001-08-02
CA2318163A1 (fr) 1999-07-15
EP1048151A1 (fr) 2000-11-02
AU2317499A (en) 1999-07-26

Similar Documents

Publication Publication Date Title
EP1048186B1 (fr) Procede pour etablir des garanties de delai et de largeur de bande dans un commutateur crossbar avec acceleration
AU746166B2 (en) Fair and efficient cell scheduling in input-buffered multipoint switch
EP1055350B1 (fr) Procede d'arbitrage et appareil destine a un commutateur non bloquant
Krishna et al. On the speedup required for work-conserving crossbar switches
US6351466B1 (en) Switching systems and methods of operation of switching systems
US7154885B2 (en) Apparatus for switching data in high-speed networks and method of operation
US8937964B2 (en) Apparatus and method to switch packets using a switch fabric with memory
US7065046B2 (en) Scalable weight-based terabit switch scheduling method
EP1048151A1 (fr) Procede assurant des delais independants de la taille des repartiteurs dans un central crossbar accelere
US6865154B1 (en) Method and apparatus for providing bandwidth and delay guarantees in combined input-output buffered crossbar switches that implement work-conserving arbitration algorithms
US20020150047A1 (en) System and method for scheduling transmission of asynchronous transfer mode cells
US6643294B1 (en) Distributed control merged buffer ATM switch
Kesidis et al. Output-buffer ATM packet switching for integrated-services communication networks
Briem et al. Traffic management for an ATM switch with per-VC queuing: Concept and implementation
US20040071144A1 (en) Method and system for distributed single-stage scheduling
Chiussi et al. Providing QoS guarantees in packet switches
US6647011B1 (en) Method and system for switching using an arbitrator
Chrysos et al. Crossbars with minimally-sized crosspoint buffers
James et al. A 40 Gb/s packet switching architecture with fine-grained priorities
Guan et al. Packetized smooth switching for buffered crossbar switches
Farajianzadeh et al. Toward a differentiated-service enabled parallel packet switch

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AL AM AT AU AZ BA BB BG BR BY CA CH CN CU CZ DE DK EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK SL TJ TM TR TT UA UG UZ VN YU ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): GH GM KE LS MW SD SZ UG ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE BF BJ CF CG CI CM GA GN GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 23174/99

Country of ref document: AU

ENP Entry into the national phase

Ref document number: 2318163

Country of ref document: CA

Ref country code: CA

Ref document number: 2318163

Kind code of ref document: A

Format of ref document f/p: F

NENP Non-entry into the national phase

Ref country code: KR

WWE Wipo information: entry into national phase

Ref document number: 1999903061

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 1999903061

Country of ref document: EP

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

WWG Wipo information: grant in national office

Ref document number: 23174/99

Country of ref document: AU

WWW Wipo information: withdrawn in national office

Ref document number: 1999903061

Country of ref document: EP