JPH03114327A - Congestion monitoring device for computer networks - Google Patents

Abstract

PURPOSE: To apply a congestion monitor device to a wide range and to simplify its practical use by providing a timer, which generates a pulse at intervals of a certain time and an integer adder which adds the waiting information string length to the average of waiting information string lengths at intervals of this pulse for the purpose of holding the average of waiting information storing lengths while in the middle of continuation. CONSTITUTION: A timer 60 which generates a pulse at intervals of a certain time and an integer adder 28' which adds the waiting information string length to the average of waiting information string lengths at intervals of the pulse for the purpose of holding the average of waiting information storing lengths in the middle of continuation are provided. Continuous measurement of the average of waiting information string lengths is performed by integer addition in contrast to that being performed by integer multiplication in a conventional system. Thus, this device is applicable to a wide range of operation for a computer network system, and its practical use is simplified.

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Application of the Invention) The present invention relates to computer networks, and particularly to improvements in congestion monitoring devices in computer networks.

(Background of the Invention) A so-called computer network is a network made up of a combination of information transfer points (called nodes), and equipment (generally called a host computer or simply a host) that transmits and receives various information. They are configured by being interconnected. Information originates from and is received by each host. Therefore, the role of a network in a computer network is to set up transmission paths between multiple hosts. Each node of the network is typically connected to a number of other nodes. Each node is equipped with an input buffer circuit corresponding to each host connected to it and each other node, and is also equipped with means for inspecting the information being sent. identify which node or host to forward to.

A large amount of information (sometimes continuous information) is transferred between each host via a computer network. When information is transferred within a network, it happens to pass from node to node via the same transmission path (link) (if a group of information is transferred, the link is It becomes impossible to carry all the information.At this time, the output ports of the nodes where a large number of information is concentrated, more specifically, the nodes related to the connection links, become axle state.This means that , the amount of information input to a particular node is greater than the amount of information output from that node.The excess information is temporarily stored in a queue inside the node. It is also possible to have storage means for storing such queues, but with such means the size of such a queue must gradually increase.

Therefore, for some reason, i! When a situation arises, some kind of measure is needed to remedy it. As a remedy for this, for example, a congested node can notify its neighboring nodes of congestion to reduce the load on the dependent links, thereby increasing the information transmission path of the network as a whole. It can also be adjusted. Furthermore, a method of transmitting information to each host related to a congested node so as to limit the amount of information to be sent is also conceivable.

It is easy to notify downstream nodes and hosts of congestion. One bit in each information header is used to indicate congestion, and when information passes through a congested node, the signal bit is set and transmitted. However, in the first place, the wheel spindle state should be alleviated by lowering the sending speed of information sent from nodes and hosts located downstream of the congested node.
You cannot expect to get a quick response using the method just described. Since the wheel axis is related to the probability that information will pass between two hosts in both directions, a host that receives information that includes a signal bit indicating congestion will respond by slowing down the information transmission rate. Sends information containing instructions to be passed to the host. (The information returned may be simple acknowledgment information.) This method has been shown to yield fairly good results.

Congestion control schemes are designed to detect when a computer network system's capacity begins to degrade and to reduce the load on the system when congestion occurs. The capacity of a computer network system is typically measured as the system's transmission efficiency (throughput). Operations for congestion control (or recovery from wheel set conditions) are then performed when the transmission efficiency of the system begins to decline.

Other countermeasures include the DEC-TR-506 paper, ``Non-Switched Connections'' by Rajan, K.K. Ramakrishnan, and Da Minh Chu, published by Digital Equipment Corporation in August 1987. proposed in ``Congestion Avoidance Method in Computer Networks''. This method focuses on transmission time delays in the system as a measure of system capability, and wheelset avoidance maneuvers are initiated when the transmission time in the system begins to increase.

The information transmission efficiency of the system in the wheel set avoidance method is substantially lower than that in the system using conventional wheel set control, insofar as the information transmission delay is actually very small due to the wheel set avoidance action. In the conventional wheel axle control method, the buffer storage circuit of this node is generally prevented from overflowing with the queue information.And when the size of the queue information approaches the storage capacity of the buffer storage circuit, On the other hand, the wheel set avoidance method attempts to avoid the occurrence of the waiting information string itself, and works to reduce the average length of the waiting information string. Of course, the wheel set avoidance method A system based on this method can also be combined with a conventional wheel set control method.This makes it possible to control the wheel set even in exceptional cases, such as when a high density of information arrives such that the information transmission efficiency is reduced. can be recovered.

In either method, it is not necessary for all nodes to be equipped with wheel axle detection means. However, if there is a node that does not have congestion detection means even though it is a wheel-shaft-friendly node, the information transmission ability of the entire system will obviously be impaired.

The present invention mainly relates to a congestion avoidance system, and more specifically, to a congestion state monitoring device in a network node.

The size of the queue information at the output port of the node is measured and the wheel set is detected thereby. However, since the value of the length of the queue information itself fluctuates randomly, it is not suitable as an indicator to express the state of dripping, and therefore some kind of smoothing or averaging method for the measured values is required. becomes.

(A well-known numerical smoothing method is the exponential smoothing method. In this method, relatively important meaning is given to the recent course of the value of an observed variable, and previous observed values are gradually This method has the advantage of being easy to introduce.

However, there are drawbacks in the current situation, for example, the impact of periods of intense convergence, although diminishing, is not detected as the time of decline in information carrying capacity is not detected in relation to the size of the network. , it will remain longer (in the network) compared to the influence during the average wheel set.

In the axle avoidance system described in the above-mentioned paper, the axle occurs cyclically and repeatedly, and a cycle of radiance follows a period in which the length of the waiting information queue continues as one or more states. , is defined as the period obtained by adding the period in which the length of the queue information string is 0, that is, the period in which congestion occurs, and the subsequent period in which no wheel axle occurs. In this wheel axle avoidance system, it is necessary to measure the average waiting information queue length for the sum of the latest full congestion cycle and the current incomplete congestion cycle at a certain node and a certain output link from that node. . If this average waiting information queue length exceeds a certain constant (1 is used), it is assumed that congestion has occurred, and a congestion drop bit is added to all information passing through the link of that node. .

As a result, the host receiving this information identifies the congestion bit present in the received information and sends out a signal indicating this fact of wheel axle in the information sent back to the original host. The host that is the information sending source receives this signal and reduces the sending speed of the information sent thereafter based on the transmitted signal indicating the condition of the wheel axle. By reducing the speed at which information is sent out from the host, the amount of information flowing into the congested node is gradually reduced. The response time delay in this feedback corresponds to the length of the congestion cycle. Therefore, using the latest full-width axis cycle plus the currently incomplete congestion cycle for congestion detection at a node automatically provides a feedback time commensurate with the size of the network. The effects of previous vergence cycles are no longer significant and any stored values are erased.

In such conventional systems, averaging of wheel set cycles is generally performed as follows. The length of the current wheel axle cycle currently being continued and the integrated value of the waiting information string length or the average waiting information string length are continuously measured. Also, the length of the latest total congestion cycle and the average waiting information string length are stored.

For each transmission or reception of information, its time is stored and the time interval between previous transmissions or receptions is calculated by subtracting the time stored during the previous processing from the current time. The length of this vergence cycle is increased by adding the measured time interval. Then, the queue information queue length is increased or decreased in units of 1.

If this system (input/output port of a node) is in a congestion cycle, multiply the time interval from the previous time by the current waiting information string length, and use the product obtained in this way to calculate the waiting time in the current wheel axle cycle. The integral value of the information string length is updated.

The total average queue length is then calculated by dividing the total integrated value of the queue lengths for the current and previous congestion cycles by the total time of these two congestion cycles.

If the total average value of the waiting information queue length calculated in this way is
If it is greater than a predetermined constant value, the edge bit is added to all information output from that node and transmitted by links related to that node until the grand average value falls below that constant value. Can be erected. As a constant value, l
is used.

Then, when the congestion cycle ends, the waiting information queue length becomes O.
decreases to At this time, the step of updating the integral value of the waiting information string length is omitted because it simply adds O to the integral value. Then new information arrives and a new congestion cycle begins. At this time, the integral values of the current wheel axle cycle length and waiting information string length are replaced with those values from the previous time, and are stored and stored as new previous values. The length integral value is reset to O in preparation for a new wheel set cycle.

This system has significant practical drawbacks. When updating the integral value of the waiting information queue length each time information is sent and received (it is necessary to multiply the waiting information queue length by a full integer time interval), A full floating point division is required when the total length integral is divided by the total current and previous wheel set cycle time.This adds a heavy fixed component (overhead) to the processing time and equipment at each node port. ).

The conventional technology outlined above will be further explained in detail with reference to FIGS. 3 to 6.

Computer Network FIG. 3 is a computer network configured such that several hosts 10 are interconnected by a network including nodes 11. Computer Network FIG.

Each host IO is connected to a node 11. The nodes 11 are connected to each other as shown in the figure.

Each host 10 can send out information that is transmitted to any other host via the network. Each piece of information includes a header (head part), and the header is provided with storage locations for various types of control information, including information for identifying the host to which the information is sent. Each node of the network is
It has sufficient information about the location of the network so that information arriving at that node can be directed to the host identified by the information header.

Although a detailed explanation of the route setting method is not meaningful in the description of the present invention, for example, the information transmission route is set by a fixed connection or a switched connection.

Each node is generally located at a geographically distant location. This also applies to hosts. However, it is also possible for two or more nodes to be co-located, although logically different. It may even be used as a single hardware configuration, as shown in Node IIA.

Nodes of the Network As shown in FIG. 4, a node 11 is provided with a number of input ports 12 and a number of output ports 13. Typically, but not necessarily, these input and output ports are paired, and each link in the network (to another node or host) is bidirectional. Each input port 12 has an input buffer circuit 1 coupled thereto.
5, each of which can store one piece of information. Further, each output port 13 has an output queue information string buffer circuit 16 coupled thereto, and can store several pieces of information transmitted via the output port 13. The output waiting information string buffer circuit 16 is "downward passage"
The information input to the top of the output queue information buffer circuit 16 descends within the output queue buffer circuit 16 until it reaches the information that already exists as a queue information queue, and in this way the information is forms a continuous chunk of information at the bottom of the output queue information string buffer circuit 16.

The input buffer circuit 15 is connected to the output queue information string buffer circuit 16 by switching means 17 .

Further, the node 11 has a control circuit 18, which monitors the header of the input information in the header section 15A of the input buffer circuit 15, so that information can pass from the incoming host identification signal in the header. The output waiting information string buffer circuit 16 to be outputted is determined and the switching means 17 is controlled. Control circuit 18 is further connected to output port 13 .

By measuring the information entering and exiting the node, it is possible to observe the number of information stored in each output queue information string buffer circuit 16.Control circuit 1
8 also fulfills other functions.

Although the input buffer circuit 15 and the output queue information string buffer circuit 16 are logically separate, they are physically configured as a single common storage device, and their respective storage areas are controlled by the control circuit 18. Assigned for different functions. This allows the length of information and the length of the queue information to be changed at will, with the restriction that the total length of all stored information cannot exceed the total storage capacity.

The switching means 17 and the control circuit 18 are also operated at a speed sufficient to always pass the information present in the input buffer circuit 15 to the appropriate output queue buffer circuit 16 before the arrival of the primary input information. It needs to work. This condition is based on the input buffer circuit 15 and the output queue information string buffer circuit 1.
6 is provided in a designated area of the common storage device, when transmitting information from the input buffer circuit 15 to the output queue information string buffer circuit 16, the designation of the storage area occupied by the information is simply changed. This can be more easily achieved by making it possible to do it alone.

Conventional Convergence Monitoring Technique [Circuit] FIG. 5 is a block diagram showing the logical configuration of a portion of the control circuit 18 in a conventional system. This block diagram shows the wheel set monitoring function of the control circuit for a single output port. It will be clear that this is shown in simplified diagrammatic form, and in particular many features relating to temporal matters are not shown.

The control circuit responds by sending or receiving information; the control circuit shown is responsive to the sending or receiving of information from the respective output port 13 concerned, or from any input port of information to that particular output port 13. 12, the operation starts. The input and output of such information are shown as logic signals on two lines, DEP and ARR, respectively. These two lines are connected to an OR gate 2o, and the OR gate 20 generates a logic signal EV representing the input and output of each piece of information.

A time signal expressed as an integer value is continuously connected to the line TIME
appear above. This time signal then provides the current time (year, month, to microseconds). The term "integer" is used for signals in integer format, as opposed to signals in logical or floating point format. Also, the word "integral" is used for a time integral or a signal that vaguely represents an average value. Obviously, the lines carrying signals in integer and floating point formats are lines made up of pits. The contents of the previous time register 21 at the time of transmission/reception of the current time signal and the previous information are supplied to an integer subtraction circuit 22, and the integer subtraction circuit 22 compares the current time with the time stored in the previous time register 21. Calculate the difference between When transmitting and receiving information (signal EV), the output signal of the integer subtraction circuit 22 is supplied to the interval register 23, so that the contents of the interval register 23 provide the time interval between the previous information transmission and reception time and the current time. Become. At this time, the contents of the previous time register 21, which was the time of the previous information transmission/reception, are simultaneously updated to the current time.

Interval register 23 and current wheel axle cycle length register 24
The contents of are supplied to the integer adder 25, and the result is fed back to the current wheel axle cycle length register 24. When transmitting and receiving information (signal EV), this ill! ! The cycle length is updated by adding the length of the time interval between the previous cycle and the current cycle to the previous value.

The waiting information string length counter 26 stores the length of the waiting information string of the output waiting information string buffer circuit 16 corresponding to the output port 13. The arrival of information (signal ARR) increases the count by one. The transmission of information (signal DEP) reduces the count by one. The waiting information string length is supplied to the integer multiplier 27, and the integer multiplier 27 is simultaneously supplied with the interval signal from the interval register 23, and the product of the information transmission/reception interval and the waiting information string length (
Waiting information queue length integral value) is created. This product is supplied to the integer adder 28, but the integer adder 28 is simultaneously supplied with the contents of the current register 29, and the integer adder 28 is
8 supplies its output to the integration register 29 this time. When transmitting and receiving information (signal EV), the integrated value of the waiting information string length up to the present time is updated by adding the product by the integer multiplier 27 to the previous value.

In addition to the current wheel axle cycle length register 24 and the current integral register 29, there is also a previous wheel axle cycle length register 30.
and a previous integration register 31 are provided. These two 1IvI! Cycle length register 24.30 provides its output signal to integer adder 32. The integer adder 32 calculates the total wheel set cycle time by combining the previous wheel set cycle length and the current wheel set cycle length. Further, the two integral registers 29 and 31 supply their output signals to an integer adder 33, and the integer adder 33 calculates the total integrated value of the waiting information sequence length in the previous wheel set cycle and the current wheel set cycle. . The outputs of these two integer adders 32,33 are:
The data is supplied to the floating point divider 34, and the total average value of the waiting information string lengths in the previous and current wheelset cycles is calculated.

The calculation result of the divider 34 is supplied to a floating point comparator 35, which determines whether the grand average value exceeds one. If it is exceeded, the output on the line GONGBIT becomes the truth value (1). This output signal is output port 1
3 and the next information to be transmitted t'
l 4. ” [M Piritoi! Meeting and power supply n Rokugensu wheel axle cycle start and end is wait information queue length counter 2
6 and the empty state of the flip-flop 36, which is normally in an empty state. Flip-flop 36 is set by a combination of the transmission of information (signal DEP) and the count value of waiting information queue length counter 26 being decreased by the transmission of that information. This combination is
Detected by AND gate 37, AND gate 37 sets flip-flop 36. This is cleared by the arrival of the next information, which is AND gate 3
8, whose output provides the clear input of flip-flop 36. The flip-flop 36 is connected to the previous wheel axle cycle length register 30 and the previous integral register 31.
control is performed to update the contents of the current wheel axle cycle length register 24 and the current integral register 29. This update is then performed when the signal from AND gate 38 goes high to clear flip-flop 36. This signal is a hole. +-:”+ zu h /l A “rL DeCmuC1 sets the contents of the minute register 29 to 0 at the start of the next congestion cycle.
Clear to. Furthermore, the update of the integral register 29 this time is actually controlled not only by the informant output signal EV, but also by a combination of this signal and the O-side output of the flip-flop 36 generated by the AND gate 39. be done. As a result, this time the integral register 2
9 is prohibited from being performed at the input/output of the first information of a new wheel set cycle. That is, at that time, the waiting information string length is O, the product of the multiplier 27 is O, and there is no need to add this to the integral register 29 this time.

[Flowchart] FIG. 6 is a simplified flowchart illustrating the operation of the control circuit of FIG. 5. Until input/output of information occurs in the control circuit, the register 21 in step 45 is updated. Then, the current wheel axle cycle length register 24 is also updated (step 46). Then, as a result of detecting in step 47 whether the processing is for incoming or outgoing information, the waiting information queue length counter 26 is increased or decreased. If the system is not at the point of transition to a congestion cycle, as detected by steps 50 or 5, then the integral register 29 is now updated (steps 52 or 53). A total average value of the queue length of the queue information is calculated in step 54 (adders 32, 33, and divider 34), and this value is compared with a predetermined constant 1 in step 55. If this number exceeds 1, a congestion bit is set in the header of the next information sent in step 56. The system then returns to the standby state in step 45.

If the system is at the point of conversion to a wheel set cycle and the information is outgoing, step 51 continues to step 58, after which a set of flip-flops 36 immediately leading to step 54 is executed in step 58. . If the system is at the point of transition to a congestion cycle, and
When information is received, step 50 switches the flip-flop 3
Continuing to step 57, in which step 6 is cleared, further, in step 59, the previous wheel axle cycle length register 30 and the previous integral register 31 are updated, and the current cycle length register 24 and current integral register 29 are set to 0. Clear and step 54 is executed immediately.

The various registers of this control circuit must be provided individually for each output port 13, while the numerical circuits (adders, multipliers, etc.) must be time-shared to different output ports 13. used. For this purpose,
It goes without saying that the numerical circuit needs to operate at sufficient speed to be able to meet the numerical calculation demands from all output ports 13. Furthermore, it is necessary to provide means for appropriately controlling various operation timings of the control circuit for each output port 13.

(Object of the Invention) The main object of the present invention is to provide an improved congestion monitoring device which has wide applicability in the operation of computer network systems and which is inherently simple to implement. It is to provide.

(Characteristics of the Invention) The present invention provides a method for determining the ongoing wheelset cycle length (congestion cycle refers to the period between two successive changes from O in the queue information sequence) and the node The first step is to measure the average waiting information queue length, which is the number of information held in a node, waiting to be transmitted from the output port of the node.
and a second measuring means for measuring the total average length of the queue information queue during the period in which the queue information queue exists, the system comprising: A timer means for generating pulses at intervals, and an addition means for adding the length of the waiting information string to the average length of the waiting information string at the intervals of the pulses in order to maintain the average length of the ongoing waiting information string. , and is characterized by.

According to the present invention, continuous measurement of the average queue length is performed by integer multiplication in conventional systems, whereas
This is done by integer addition.

Although the system of the present invention does not produce exactly the same results as with the conventional system, the differences between the system of the present invention and the conventional system are generally small (and, as discussed below, Minor fixes have been made to the system to improve performance.

It is preferable to include means for storing an average of the wheel spindle cycle length and the waiting information length in at least one previous wheel spindle cycle. Various minor changes, described below, are also made to reduce the number of registers required and/or their arrangement.

Furthermore, the second measuring means for measuring the grand average preferably includes means for comparing the sum of the averages of the same length of waiting information with the total concentric cycle time. By such means, the calculation of the grand average, as in conventional systems,
This is done by simply adding or comparing integers, without using floating point calculations.

If the constant predetermined as the total average of the same length of waiting information such that a wheel axle bit is added to the information output from the node is 1, then the comparison to determine the wheel load is based on the total average of the same length of waiting information. and the total congestion cycle time. Furthermore, it is desirable to treat this as a variable rather than a constant. In order to maintain the characteristic that the decision is made by simple comparison, the average of the wheelset cycle length and/or the waiting information length must be multiplied as a factor of an appropriate scale. Various techniques that are convenient for doing this are discussed below.

In the system according to the present invention, the waiting information length is added to the average of the ongoing waiting information lengths at regular time intervals, and quantization is performed according to the time interval. If the time interval is long, the quantization will be inaccurate. Two techniques for correcting this (timer period net incoming call accumulation and direct incoming outgoing adjustment) are also discussed below.

(Examples of the Invention) Specific examples of the present invention and some applications thereof will be described by way of examples using figures.

Radius Monitoring [Circuit] of the Present Invention FIG. 1 is a block diagram of a part of the control circuit 18 according to the basic configuration of the present invention. This circuit corresponds to some extent to FIG. 5, and therefore has corresponding reference numbers and a corresponding block arrangement.

This control circuit responds to the input and output of information, and the input and output of information may be sending information from a specific output port, or transmitting information for a specific output port to any input port. An incoming call is also fine. The control circuit 18 also includes a free-running timer to which the rest of the circuit responds, so that updates occur at regular intervals.

A high frequency clock signal CLK (eg, a small multiple of the bit frequency in the information) is provided to the timer 60. The timer 60 operates as a one-period counter,
Generates timer output pulse TICK at regular intervals. The duration of the timer output pulse should be long enough to separate the update operations of the control circuit 18 associated with each output port in time. The timer output pulses are supplied to the current wheelset cycle length register 24' and counted.

The waiting information equal length counter 26' stores the length of the waiting information string of the output waiting information string buffer circuit corresponding to the output port. Incoming information (signal ARR) increases the count by 1,
The transmission of information (signal DEP) reduces the count by one. The waiting information is supplied to the integer multiplier 28, and at the same time, the contents of the integral register 29' are supplied to the integer adder 28.
' supplies its output to the integration register 29' this time. Due to the timer output pulse TICK, the integrated value of the wait information length up to the current time is updated by adding the wait information length to the previous value at the end of the timer output pulse period.

In addition to the current wheelset cycle length register 24' and the current integration register 29', a previous cycle cycle length register 30' and a previous integration register 31' are provided. These two width cycle length registers 24', 30' provide their output signals to an integer adder 32'. The integer adder 32' calculates the total vergence cycle time, which is the sum of the previous wheel axle cycle length and the current wheel axle cycle length. The two integral registers 29' and 31' supply their output signals to an integer adder 33', and the integer adder 33' calculates the total integrated value of the queue lengths of the previous and current radial cycles. . The outputs of these two integer adders 32', 33' are:
The signal is supplied to an integer comparator 61, which measures whether the total convergence cycle time exceeds the total integrated value of the queue length. If it exceeds the output C0NGB
IT becomes the truth value. This output signal is carried to the output port and added as a wheelset bit signal to the header of the next information to be transmitted.

The start and end of the axis cycle are determined from the count in the queue length counter 26' and the state of the flip-flop 36', which is normally in the clear state. Flip-flop 36' is set by the combination of the transmission of information (signal DEP) and the queue length counter 26' being decremented to O by the transmission of that information. This combination is detected by AND gate 37', which sets flip-flop 36'.

This is cleared by the arrival of the next information, which is detected by AND gate 38', the output of which provides the clear input of flip-flop 36'. Flip-flop 36' is the last time i! Cycle length register 30'
Control is also performed to update the contents of the previous integral register 31' to the contents of the current wheel axle cycle length register 24' and the current integral register 29'. This update is performed when the signal from AND gate 38' goes high to clear flip-flop 36'.

This signal also clears the contents of the current wheel cycle length register 24' and the current integral register 29' to 0 for the start of the next wheel axis cycle, and also to inhibit normal addition by signal ARR. Wait information queue length counter 2
Clear 6'.

[Flowchart] FIG. 2 is a simplified flowchart illustrating the operation of the control circuit. The control circuit remains in the waiting loop of step 65 or step 45' until a timer output or information input/output occurs. At the time of timer output, the current wheel axle cycle length register 24' is added, and the current integration register 29' is updated by adding the current waiting information string length. (Step 66) When the system is not at the point of conversion to a wheelset cycle, the wait information queue length counter 26' will be set as determined in step 47' when there is an input or output of information. It is added or subtracted depending on whether there is a call or an outgoing call. (Step 48' or 49') The total integrated value of the queue length and the total wheel set cycle time are calculated by integer adders 32' and 33' in step 54'. If their ratio holes are greater than 1, the axle bit is set. This is accomplished by comparator 61 comparing these two sums in step 55'. If the total integrated value of the queue length is greater than the total width overlap cycle time, then in step 56' the cox bit is set to the information about to be transmitted. The system then returns to standby state. (Steps 45', 65) If the system is at the point of conversion to a radial cycle and information is being transmitted, steps 51' to 58
The process moves to step 54', the flip-flop 36' is set, and then the process immediately moves to step 54'. If the system is at the transition point to a radial cycle and information is being received, step 50' transfers to step 57' where flip-flop 36' is cleared. After that, the process moves to step 59', where the previous wheel axle cycle length register 30' and the previous integral register 31' are updated, the current wheel axle cycle length register 24' and the current integral register 29' are cleared to 0, and the wait information string long counter 26'
is set to 1. Then, the process moves to step 54'.

The total integrated value of the waiting information string length from the integer adder 33' is
If the total wheel set cycle time from integer adder 32' is greater than the total wheelset cycle time, the signal on line C0NGBIT is set to 1; if the output of integer adder 33' is less than the output of integer adder 32', the signal on line C0NGBIT is set to 1. C0NGB The signal on IT is O
is set to These two integer adders 33', 32
If the outputs of ' are equal, the integer comparator 61 outputs 0. The reason for this is that in the initial stage, the outputs of the two integer adders are 0, and it is desirable to assume that there is no wheel set in this state.

Regarding the question of what happens -e-wise when the contents of a register reach the maximum value that the register can store,
It has not yet been clearly considered. Timer 60 is also a register, but as mentioned above, this register is periodic. Therefore, its contents return to O from the maximum value. However, since registers are generally aperiodic, their contents are held at a maximum value instead of returning to zero. Similarly, when a register is subtracted, it is typically held at zero instead of returning to its maximum value.

[Comparison with Prior Art] This control circuit has two major differences compared to the control circuits of FIGS. 5 and 6.

The first difference is that the integration of the waiting information string length in the conventional system is replaced with a somewhat smoother integration. In conventional systems, the integral value of the queue length of queue information is updated every time information is input or output. This requires the queue length to be integer multiplied by the variable time interval between previous and current input and output of information. In the system of the present invention,
Integration of the waiting information string length is performed not every time information is input/output, but every timer output. Therefore, the time interval is the same for each update. No multiplication required. The reason is that the wheel axle cycle length is detected during the timer output pulse, so
The length of the timer output pulse period is one. All that is required is to add the wait information string length to the integral value at each timer output.

The second difference is that the grand average of queue lengths is no longer calculated, so floating point divisions and comparisons are no longer needed. The total average value is the total integrated value of the queue length divided by the total wheel set cycle time. This is compared to 1. This is equivalent to simply comparing the total integral value to the total wheel set cycle time, and this is what is done by the present invention.

Two operations involving large operating time and complexity, multiplication and floating point division, have been eliminated by the present invention.

Variations and Developments The system of the invention described above can be varied and developed in many ways to improve its implementation in various ways.

"Register transformation" The current uncompleted wheel spindle cycle length is Tc, the previous full width cycle length is Tp, and the integral value of the corresponding waiting information string length is rc
, Ip, the circuit of the prior art is (I c+ I
p)/(Tc+Tp) and comparing the value with 1. The system of the invention described above evaluates the two sums (Ic+Ip) and (Tc+Tp) separately and compares them. This is (I c+ I p
-Tc-Tp) and determining whether it is positive or negative. Since the value of the previous convergence cycle length is fixed, the difference (Ip - Tp) can be calculated at the beginning of the wheelset cycle, and a single register is used instead of the two registers 30' and 31'. can be memorized.

Furthermore, the difference (Ic - Tc) is two separate values Ic and Tc
and can be stored in a single register instead of the two registers 24' and 29'. In this case, two changes occur in the difference (Ic-Tc) at each timer output.

This difference must increase by the queue length and decrease by l. This can be achieved in various ways. For example, a circuit that decrements by one may be included in the feedback circuit from the integer adder 28' to the register that stores the difference (Ic-Tc). Alternatively, the waiting information equal length counter can be configured such that its stored value is always one less than the true waiting information string length.

Similarly, the equation (Ic+Ip-Tc-Tp) can be stored as a single quantity that is increased by the same length of wait information and decreased by l at each timer output. The flush bit is set when this value is greater than O. Amount (I
c-Tc) also needs to be preserved. The reason is,
This is because this quantity needs to be known when it becomes (Ip-Tp) at the end of the vergence cycle. Difference (Ic-T
Storing c) and (Ic+Ip-Tc-Tp) as a single quantity has the advantage of facilitating limit control of these quantities.

It should be noted that the time when the wait information parity length is O is treated as part of the flush cycle. As soon as the wait information parity is greater than or equal to 0, a new wheel set cycle is started and the difference (Ic-Tc) is transferred to become the previous difference (Ip-Tp). That wheelset cycle becomes the latest previous smoothing cycle. If the waiting information length is a considerable time O, the difference (Ic-Tc) is decreased by 1 for each timer output. In this way, this difference slowly decreases. This means that when a new wheel set cycle begins, the effectiveness of the previous wheel set cycle decreases, depending on how long ago the previous fluent cycle was active. If there is a sufficient time interval at the end of the previous wheel set cycle where the wait information length is O.

It does not matter how large the waiting information queue is.

“Timer Output Pulse Period Length” The selection of the timer output pulse period length is influenced by various factors. The natural unit for measuring the duration of a timer output pulse is the time required to transmit a single piece of information, ie the reciprocal of the maximum information ratio. The duration of the timer output pulse quantizes the current and previous convergence cycle length measurements by registers 24' and 30'. If the duration of the timer output pulse is short compared to this natural time, this quantization reduces the accuracy of the system somewhat.

However, given the long duration of the timer output pulse, quantization introduces inaccuracies. This inaccuracy can be reduced by two techniques: accurate incoming counting of information during the timer output pulses and rapid incoming and outgoing adjustment.

If the interval between timer output pulses is a very large multiple (e.g. 20 times) of the time required to transmit a single piece of information, then the integration of the waiting information length is sufficiently inaccurate for high information ratios. It can be. If the waiting information length becomes O during the timer output pulse, the current flush cycle ends, but if it rises significantly and then becomes O again, this fact will not be detected. Thus, the integral of waiting information isolength determined by the system will be somewhat lower.

To prevent this, an incoming call counter can be added. This counter counts the arrival of information during the timer output pulse period, adds the counted value to the current integral value of the same length of waiting information at the end of the timer output pulse period, and is reset to zero at the same time.

The degree of such protection is reduced, for example, by adding only half the contents of the incoming call counter, ie by truncating the lowest J6 bids.

If complete prevention is required, the counter is not used, but instead the integral value is increased by 1 for each incoming call. Similarly, if 50% protection is required, instead of using a counter, use a flip-flop, change the state of the flip-flop each time a call arrives, and increase the integral value only when the flip-flop is set. .

System activity is improved by rapid incoming and outgoing counting techniques. The formula for generating Ic increases with each incoming call and decreases with each outgoing call. (Ic+Ip-Tc-Tp)
>1, the congestion bit is set. A constant of 1 is required. The reason is that a single incoming call after a long quiet time interval will cause the congestion bit to immediately set to 1, indicating the appearance of permanent congestion. The necessary adjustment is equivalent to calculating Tc for information arriving at the beginning of the timer output pulse period rather than at the end.

"Generalized standard for equal length of average waiting information" As explained above, the effect of the system is that when the total average value of the waiting information queue length in the previous and current congestion cycles is greater than 1,
Setting the wheel axle bit. It is desirable to use a predetermined critical position qt different from 1.

As mentioned above, this system determines whether the total average value of the waiting information queue length is greater than 1, that is, iql/lct >
1 or not. (iql is the total integrated value of the waiting information string length in the previous and current congestion cycles, and tct is the total width recycle time in the previous and current congestion cycles.) Although this format requires division, In our system, this inequality is implemented in the form iql>tct. This format only involves addition and comparison (subtraction). Replacing the parameter qt with a constant 1 is to change the fundamental inequality to iql/lct>qt. This is the format iql>qt・tc
t or 1ql-qt・tct>O. Generally, this format involves undesirable floating point multiplications.

Therefore, let qt be a rational fraction qtn/qtd, and let the inequality contain only integer multiplication: qtd-iql> qtd4c
It is preferable to convert it to t.

To accomplish this, the integral value of the queue length and the constant in the rate at which the current cycle length increases need to be changed. This time, the wheel axle cycle length is added by qtn rather than 1 for each timer output pulse. this is,
By providing an adder in the feedback loop from the wheel set cycle length register 24' back to itself, or
For each timer output pulse, the current wheel axle cycle length register 24
This is achieved by providing a pulse generator that provides a plurality of pulses to . This addition can be made programmable by providing a ratio register which is initially set to an arbitrary value and adding it to the current wheel axle cycle length for each timer output pulse. Changing the constant of the integral this time is slightly more complicated, but instead of qt
This can be achieved by adding the queue length to it d times. This can be done serially or in parallel by feeding the queue length to one or more inputs of a multi-input adder with appropriate shifts.

It is of course easily possible to introduce two σ elements by appropriately shifting the outputs of the registers, rather than by multiple addition. Therefore, it is desirable to select qtd, which is a power of 2, and shift the register output appropriately.

If prompt coordination of incoming and outgoing calls is implemented,
For the reasons mentioned above, qt and 1ql− rather than 0
It is necessary to compare qt and tct.

"Modification of fulfillment method" If the input/output of information is an incoming call, steps 54' to
56' is not necessary. Whether it is better to perform these steps on all information input and output, or to modify the system slightly so that these steps are performed only on outgoing information, depends on the particular implementation method chosen. If the implementation method results in taking more time compared to the time required for information transmission in the method described above, the method can be slightly modified to save the signal C0NGBIT and use it to set the congestion bit for the next information. (if the information is outgoing rather than incoming). If this is done, steps 54'-56' should clearly be performed for each information input/output. (Similar considerations apply to the conventional systems of FIGS. 5 and 6.) The various registers of this control circuit are physically organized in a single common storage device selected by known means. Of course, what is possible is possible.

Also, various registers with different ports.

may also be configured in the same single common storage,
Alternatively, - sets of storage devices may be provided, and each storage device may configure a corresponding register, one for each port. Also, the various functions performed by these registers may be performed by a single arithmetic and logic unit performing different functions in a known manner.

(Effects of the Invention) As described above, according to the present invention, the timer means generates pulses at regular intervals, and the wait information is stored at intervals of the pulses in order to maintain the average length of the ongoing queue information queue. By providing an addition means for adding the queue length to the average waiting information queue length, continuous measurement of the average waiting information queue length is performed by integer addition, whereas in the conventional system, it is performed by integer multiplication. Because of this, it can be applied to a wide range of applications in the operation of computer network systems, and can be essentially simplified in practical use.

[Brief explanation of drawings]

FIG. 1 is a simplified block diagram of a control circuit according to an embodiment of the present invention, FIG. 2 is a flowchart showing the operation of the control circuit shown in FIG. 1, and FIG. 3 is a partial diagram of a conventional computer network. 4 is a simplified block diagram of a conventional network node, FIG. 5 is a simplified block diagram of a control circuit that is part of a conventional node, and FIG. 6 is a simplified block diagram of a conventional network node. 3 is a flowchart showing the operation of the control circuit of FIG. IO...Host, 11...Node, 1
2...Input port, 13...Output port, 15...Input buffer circuit, 16...
Output waiting information string buffer circuit, 17... Switching means, 18... Control circuit, 24'...
- Current wheel axle cycle length register, 26'...Waiting information same length counter, 28'...Integer adder,
29'...This time the integral register, 30'...
・・Previous wheel axle cycle length register, 31'...
Previous integral register, 32'... Integer adder, 3
3'...Integer adder, 36'...Flip-flop, 60...Timer, 61...
...Integer comparator, ARR... Signal (incoming call),
DEP...signal (transmission), TICK...
...Timer output pulse.

Claims (1)

[Claims] (1) Waiting information that is the ongoing congestion cycle length in the current congestion cycle and the number of information residing in the node waiting to be transmitted from the output port of the node. a first measuring means for measuring the average queue length; a second measuring means for measuring the total average length of the waiting information queue during a period in which the waiting information queue exists; and a timer means for generating pulses at regular intervals; 2. A congestion monitoring device for a computer network, comprising: adding means for adding a waiting information string length to the average waiting information string length at intervals of the pulses in order to maintain an average of the ongoing waiting information string length. 2. A congestion monitoring device for a computer network according to claim 1, wherein the adding means adds a multiple of the length of the waiting information string to the average length of the waiting information string at intervals of pulses of the timer means. 3. The congestion monitoring device for a computer network according to claim 1, further comprising means for storing an average of the congestion cycle length and waiting information string length of at least one previous congestion cycle. (4) Second step to measure the total average of waiting information queue length
2. The congestion monitoring device for a computer network according to claim 1, wherein the measuring means includes a comparator. (5) Claim 1 comprising a single register for storing each congestion cycle length and the corresponding waiting information string length in the form of a difference.
A congestion monitoring device in the described computer network. (6) an incoming counter for counting the number of information arriving during an interval of pulses of the timer means; and means for adding a predetermined percentage of the counted value of the incoming counter at the end of the interval of pulses of the timer means; 2. A congestion monitoring device for a computer network according to claim 1. (7) The congestion monitoring device for a computer network according to claim 1, further comprising means for immediately adjusting the waiting information queue length upon arrival or reception of information.