Weighed round-robin multiplexing of ATM cells by updating weights with counter outputs

[0002] 1. Field of the Invention

[0003] The present invention relates generally to asynchronous transfer mode (ATM) networks, and more specifically to an ATM network node wherein a plurality of servers of different classes are examined in a round robin fashion to forward buffered cells according to the frequency weights allocated to their service classes.

[0004] 2. Description of the Related Art

[0005] Weighted round-robin cell multiplexing is described in a paper titled “Weighted Round-Robin Cell Multiplexing in a General-Purpose ATM Switch Chip”, Manolis Katevenis et al., IEEE Journal on Selected Areas in Communications, Vol 9, No. 8, October 1991, pages 1265 to 1279. According to this prior art, ATM Cells of different traffic (or service class) are stored in corresponding buffers and counters are associated respectively with the buffers. Different values of frequency weights are loaded into the counters corresponding to the service classes. In a round-robin fashion, a cell is forwarded from each buffer until the associated counter is decremented to zero. At the end of a round robin cycle, all the counters are reset and the frequency weights are reloaded into the counters to begin a new cycle.

[0006] However, the arrival of cells in a rapid succession would form a queue in a buffer if the other buffers are also receiving rapidly arriving cells. When this occurs, the counter is decremented to zero and the stored cells must wait for their turn until the next round robin cycle begins. If these cells are of the type which must be processed on a real-time basis, delays caused by the weighted round robin multiplexing cannot be ignored.

[0007] It is therefore an object of the present invention to provide an ATM network node wherein cells are multiplexed on a weighted round-robin fashion with reduced delays for cells arriving at short time intervals.

[0008] According to a first broader aspect of the present invention, there is provided an ATM network node which comprises a plurality of buffers for respectively storing cells of different service classes and a plurality of counters respectively associated with the buffers, the counters being initially loaded with initial weight values respectively corresponding to the service classes. Updating circuitry is provided for respectively updating the initial count values with output values of the counters. Control circuitry sequentially interrogates the buffers and the counters in a round-robin fashion. If the output value of each interrogated counter is not decremented to a predetermined value, a cell is forwarded from the associated buffer and the counter is decremented by one. At the end of a round robin cycle, all of the counters are reloaded with the initial count values of the updated count values depending on the number of cells forwarded from each of the buffers.

[0009] According to a first specific aspect, the updated count values are smaller than the initial count values by amounts corresponding to negative output values of the counters.

[0010] According to a second specific aspect, the updated count values are respectively greater than the initial count values by amounts corresponding to positive output values of the counters but respectively smaller than predetermined upper limit values.

[0011] According to a third specific aspect, the updated count values are respectively smaller than the initial count values by amounts corresponding to negative output values of the counters or respectively greater than the initial count values by amounts corresponding to positive output values of the counters but respectively smaller than predetermined upper limit values.

[0012] According to a second broader aspect, the present invention provides a method for an ATM network node which comprises a plurality of buffers for respectively storing cells of different service classes, and a plurality of counters respectively associated with the buffers, the counters being initially loaded with full-count values respectively corresponding to the service classes. The method comprises the steps of (a) determining whether the output value of a successive one of the counters is not decremented to a predetermined count value, (b) if the counter is not decremented to the predetermined count value, causing the buffet associated with the counter to forward a cell and decrementing the counter by one, (c) updating the full-count value of the counter with an output value thereof, (d) repeating the steps (a) to (c) in a round robin fashion, and (e) reloading each of the counters with the initial weight or the updated weight at the end of a round robin cycle depending on the number of cells forwarded from the buffer associated with the counter.

[0013] According to a third broader aspect, the present invention provides a method for an ATM network node which comprises a plurality of buffers for respectively storing cells, and a plurality of counters of different service classes respectively associated with the buffers, the counters being initially loaded with respective full-count values corresponding to weight values of the service classes, wherein each of the counters produces a first indication when the counter is decremented to a predetermined value and each of the buffers produces a second indication when there is no cell to transmit. The method comprisies comprises the steps of (a) setting a counter-pointing variable “i” to one, and (b) making an affirmative decision when the counter pointed by variable “i” is producing the first indication or the buffer associated with the counter is producing the second indication or a negative decision when both of the counter and the associated buffer are not producing the respective indications. If the decision at step (b) is negative, step (c) is performed by forwarding a cell from the associated buffer, decrementing the counter by one and updating the full-count value with an output value of the counter. Decision step (d) is then performed: If, in each of the service classes, the counter is producing the first indication or the buffer is producing the second indication, all of the counters are reloaded with thin initial full-count values or the updated full-count values of the counters depending on the number of cells forwarded from the buffers associated with the counters. If, in at least one of the service classes, both of the counter and the buffer are not producing the respective indications, the variable “i” is incremented by one and the step (b) and those that follow are repeated. If the decision at step (b) is affirmative, decision step (d) and those that follow are repeated.

[0014] Step (c) may further include the step of resetting the variable “i” to zero. With the variable resetting step, cells of higher priority levels are forwarded preferentially over those of lower priority levels.

[0015] The present invention will be described in further detail with reference to the accompanying drawings, in which:

[0016] FIG. 1 is a block diagram of an ATM network node according to a first embodiment of the present invention;

[0017] FIG. 2 is a flowchart of the operation of the controller of FIG. 1;

[0018] FIG. 3 is a block diagram of an ATM network node according to a second embodiment of the present invention;

[0019] FIG. 4 is a flowchart of the operation of the controller FIG. 3;

[0020] FIG. 5 is a block diagram of an ATM network node according to a third embodiment of the present invention; and

[0021] FIG. 6 is a flowchart of the operation of the controller of FIG. 1 according to a fourth embodiment of the present invention.

[0022] In FIG. 1, there is shown an ATM network node according to a first embodiment of the present invention. The network node has a discriminator 1 which examines the header of an incoming packet, or 53-byte ATM cell from an input line 5 and distributes it to a corresponding one of a plurality of identical servers 2-1 through 2-N respectively identified as class-1 to class-N servers.

[0023] Each server, as represented by server 2-1, comprises a buffer 10 for receiving class-1 ATM cells from the discriminator 1 to form a queue, waiting for their turn to be forwarded onto an output line 6 in response to a forward command signal from the server controller 4. Initially, the server controller 4 resets all servers 2. In response, a down counter 15 is loaded with the output of a selector 14 which is initially set equal to a counter initial value stored in a register 11. The initial count value of each server is the “frequency weight” of the server and corresponds to the service class of the server. Thus, it differs from one server to another.

[0024] The initial count value loaded into counter 15 is decremented by 1 in response to the output command signal from the server controller 4 so that each time a cell is delivered from the buffer 10 the loaded value is decremented by 1. If the number of the forwarded cells exceeds the initial count value, a zero/minus count indication is produced by the counter 15. If that number further increases, the counter 15 produces a negative count value, and this negative value is summed with the initial value of register 11 by adder 12. Therefore, the output of adder 12 will become smaller than the initial count value and maintained by selector 14 if the number of forwarded cells exceeds the initial count value. When the counter 15 is reset again, it will be loaded with a count value which is smaller than the initial count value by an amount corresponding to the number of cells forwarded after the initial count value is decremented to zero. When the buffer 10 is empty, it supplies a zero-queue length indication to the server controller 4.

[0025] The output of counter 15 is supplied to an adder 12 where it is summed with the ouput of register 11. The outputs of register 11 and adder 12 are compared with each other in a comparator 13 and one of these having a smaller magnitude is determined. Selector 14 is responsive to the output of comparator 13 for selecting the smaller of the outputs of register 11 and adder 12. As long as the down counter 15 produces and output of positive value, the output of selector 14 equals the output of register 11. The output of counter 15 is further compared by a comparator 16 with a counter lower limit of negative value stored in a register 17. Comparator 16 supplies an underflow signal to the server controller 4 when the negative output value of down counter 15 becomes equal to the negative lower limit value of register 17.

[0026] As will be understood, the underflow signal from a server prevents the server controller 4 from further supplying the forward command signal to that server when it has forwarded a predetermined number of cells after its initial count (i.e., weight) value has been decremented to zero.

[0027] The operation of the server controller 4 will be described below with the aid of a flowchart shown in FIG. 2. Initially, server controller 4 supplies a reset signal to all servers 2-1 to 2-N, so that their down counters are loaded with initial frequency weights. At step 31, a variable “i”, representing the service class, is set equal to 1. Flow proceeds to decision step 32 to determine whether an underflow or zero-queue length indication is received from the class-i server.

[0028] The server controller makes an affirmative decision when the counter pointed by variable “i” is producing an underflow indication or the buffer associated with this counter is producing a zero-queue length indication and makes a negative decision when both of the counter and the associated buffer are not producing the respective indications.

[0029] If the decision at step 32 is negative, server controller 4 commands the class-i server to forward a cell from its buffer onto the output line 6 at cell transmit timing (steps 33, 34), and proceeds to step 35. If the decision at step 32 is affirmative, cell transmission from this server is not performed at steps 33 and 34 and controller 4 proceeds to step 35.

[0030] Meanwhile, the full-count value maintained by the selector 14 is updated with the current output value of the counter (FIG. 1).

[0031] As step 35, the controller checks for the presence of a zero/minus count indication or zero-queue length indication from all servers. If either one of zero/minus count or zero-queue length indications is received from all servers. The server controller makes an affirmative decision when, in each of the service classes, the count is producing a zero/minus count indication or the buffer is producing a zero-queue length indication and makes a negative decision when, in at least one of the service classes, both of the counter and the buffer are not producing the respective indications.

[0032] If the decision at step 35 is affirmative, flow returns to step 30 to reset the counters 15 of all servers so that they are reloaded with individual full-count values currently maintained at the output of their selectors 14, whereupon the server controller completes a round robin cycle.

[0033] If the decision at step 35 is negative, flow proceeds to step 36 to check to see if the variable “i” is equal to N. If i≠N, the variable is incremented by one at step 37 and if i=N it is set equal to one at step 38. Following the execution of either step 37 or 38, control returns to step 32 to repeat the process.

[0034] If the number of cells forwarded from a given server becomes greater than its full-count value initially given by register 11, the output of adder 12 becomes smaller than this full-count value by an amount equal to the number of cells excessively (additionally) forwarded after the counter 15 is decremented to zero. Therefore, when counter 15 is reset, it is reloaded with a new full-count value which is smaller than the initial weight by an amount corresponding to the number of such excessively forwarded cells. Since some of the servers might have forwarded such excessive cells when the counters 15 of all servers are reset in response to an affirmative decision at step 35, the full-count values of such servers will be updated to smaller-than-the-initial full-count values and a new cycle begins with the updated values.

[0035] In this way, the present invention allows servers to forward cells more than their weight values if they arrive in rapid succession. Therefore, the cells of the type requiring real-time processing are delivered to the output line without delays.

[0036] A second embodiment of this invention is shown in FIGS. 3 and 4. In this embodiment, the down count value of a server obtained at the instant it is reset is used as a “saved” value during the next cycle to allow this server to increase the number of cells to be forwarded by that amount. In FIG. 3, each server includes a register 50 to supply a counter upper limit value to the selector 14 and comparison is made between the upper limit value and the output of adder 12 to determine the smaller of these values. Selector 14 selects this smaller value according to the output of comparator 13. The upper limit values are appropriately determined for individual servers. The upper limit value of each server is greater than the initial full-count (i.e., weight) value of the server.

[0037] It is seen that the comparator 16 of FIG. 1 is dispensed with. Therefore, step 60 is provided instead of step 32 of FIG. 2, as shown in FIG. 4, in order to skip cell transmission steps 33 and 34 when the down counter produces a zero count indication. The output of down counter 15 is thus equal to or greater than zero. This count value is supplied to the adder 12. When the counter 15 is reset, the positive output count value obtained at this instant is summed with the initial full-count value of the server and compared with the upper limit value.

[0038] Assume that the initial full-count (or weight of the service class) value of the server is “10” and the counter 15 has been decremented to “2” at the reset instant, and the upper limit value is equal to “14”. Under these circumstances, the output of the adder is selected and loaded into the down counter 15 to be used as an updated full-count value. Thus, in the next cycle, the server is allowed to forward two cells more than the initial full-count value of “10”.

[0039] It is seen therefore that the counter upper limit value will be selected if the “saved” value of a given cycle is unusually larger. This prevents the server from forwarding an exceedingly large number of cells during the next cycle.

[0040] The “saving” feature of the second embodiment can be advantageously combined with the “underflow” feature of the first embodiment as shown in FIG. 5, wherein parts corresponding in significance to those of FIGS. 1 and 3 are marked with the same numerals as used in FIGS. 1 and 3. The server controller 4 of this modified embodiment operates in the same manner as the controller of FIG. 1 by using the flowchart of FIG. 2.

[0041] If the number of cells forwarded from a server in a given cycle exceeds the weight, or initial full-count value of the server, the server controller 4 allows it to continue forwarding cells as long as the decremented count value is higher than the lower limit of register 17. If the number of cells received during the previous cycle is unusually small, the down counter 15 has been loaded with a relatively high count value due the the “saved” count of the previous cycle. Therefore, this modified embodiment has an averaging effect over successive cycles, so that a rapid increase in the number of arriving cells can be compensated for by the combined “saving” and “underflow” features of this invention.

[0042] FIG. 6 illustrates a flowchart of the operation of the server controller of FIG. 1 according to a further embodiment of the present invention in which parts corresponding in significance to those of FIG. 2 are marked with the same numerals as used in FIG. 2. FIG. 6 differs from FIG. 2 in that it additionally includes step 70 following step 34 to reset the variable “i” to zero. Following the execution of step 70 or the affirmative decision of step 32, control proceeds to decision step 35. The provision of the variable-resetting step 70 causes the server controller to increment the variable “i” to “1” at step 37 provided that the decision at step 35 is negative. Thus, steps 32 to 34 are repeated on the class-1 server 2-1 if it has a cell to transmit. Assume that class-1 to class-N servers are given priority of different levels with the class-1 server being the highest and the class-N server being the lowest. Therefore, as long as the class-1 server has at least one cell to transmit at the instant the variable “i” is incremented to “1” at step 37, the decision at step 32 is negative and the cell of the highest priority is forwarded (steps 33, 34). If the class-1 server has no more cells to transmit, the decision at step 32 is affirmative and the variable “i” is incremented to “2” at step 37 to repeat steps 32 to 34 on the class-2 server. Thus, as long as the class-2 server has at least one cell to transmit at the instant the variable “i” is incremented to “2”, the decision at step 32 is negative and the cell of the second highest priority is forwarded (steps 33, 34). If the class-2 server has no more cells to transmit, the decision at step 32 is affirmative and the variable “i” is incremented to “3” to repeat steps 32 to 34 on the class-3 server.

[0043] Therefore, higher priority cells are forwarded with smaller delays than lower priority cells.

[0044] While it is shown that the variable resetting step is combined with the flowchart of FIG 2, it could equally be as well combined with the flowchart of FIG. 4.