Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1998-02-13
2001-01-09
Olms, Douglas W. (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
C370S252000, C370S395430, C370S412000
Reexamination Certificate
active
06172963
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The invention relates to a method and a device, in preferably an ATM-switch which manages data communication and telephone traffic, in order to be able to have in readiness a large capacity even with relatively small and inexpensive buffers.
DESCRIPTION OF RELATED ART
In modern telecommunication systems, information is grouped into small data units called “packets” where each such packet comprises a field with a “head” which is used in order to identify the packet and a field containing useful information. A packet can also contain a field with information about where the cell originally came from. The packet is guided normally through the communication system from a source to a destination through switches intended for such packet switching which lead the packets through the data network in accordance with the information in the head of each packet and tables in the switches. Such switches receive a flow of data packets from a number of inputs. The head is read and the packet then is guided through the switch towards one of the many outputs which are present.
An ATM-network (Asynchronous Transfer Mode) transmits data which is divided up and packeted in packets with a fixed size, so-called cells, instead of packets with variable lengths as in traditional packet transmissions. The cells are transmitted with a high speed over e.g. optical fibres and experience fast hardware switching. An ATM-network is flexible and can offer services which require different transmission speeds and the network furthermore effectively makes use of various choices of transmission paths.
ATM-connections where the traffic is sent with a strong “burst-like” character require large buffers which are both expensive and difficult to implement.
The prior art shows two main switch structures. The first has buffers on the output connections. This structure has the best performance but is expensive and difficult to implement since large buffers are required. The reason is that each buffer must have the same capacity as the whole switch, as in the worst case situation it can happen that all the inputs transmit towards the same output simultaneously. As ATM-switches work with a data speed per link of up to 622 megabits per second and a total capacity of 10 Gbps or more, it is extremely difficult to construct output buffers with sufficient bandwidth and memory capacity as is required for certain of the services which should be able to be supported in an ATM-switch.
In the second structure, buffers are placed at the inputs to the switch. The buffers are made from normal FIFO-memories and are usually placed in so-called switch ports. This solution with a buffer for each input means that each buffer only is required to cope with the same cell speed which corresponds to the traffic on the same input. The problem with this model is that a flow control is required as cells would be lost if several inputs sent simultaneously to the same output. Another disadvantage with the same switch structure is the known head-of-the-line (HOL) problem. This occurs when certain FIFO for a period of time are prevented by the control logic from sending cells in turn to a certain output since other inputs simultaneously want to send there. Consequently, in the stopped FIFO all the cells behind the one waiting to be sent are prevented from being sent even if they are to go to a different output which perhaps at that time is not at all loaded with traffic. The HOL-problem thus results in a bad utilization of the switch.
In this technical field a crucial factor for costs and “time to market” is whether the buffers can be made with commercial memory capsules or whether they must be comprised in large specially constructed circuits.
In order to cope with certain of the problems, sometimes ATM-switches with switch ports both in towards and out from the switch core with respective in- and output buffers are used, which can be seen in e.g. U.S. Pat. No. 5,493,566 where a form of STOP-GO solution is used, where the degree of fillness in the output buffers is supervised and when a certain so-called “STOP-level” is reached in the buffers, a STOP-signal is sent to certain input ports with the order to stop sending to that particular output where the buffer is about to become filled. When the output buffer reaches a lower so-called “GO-level”, a GO-signal is sent to the input ports concerned to begin to send cells again. This solution requires that each input port has an input buffer which is divided into a FIFO-memory for each output. The size of the output buffers are here i.a. dependent on how many cells an output buffer maximally can receive after a STOP-signal has been sent in a “worst case”-situation.
The above mentioned patent thus shows a system for flow control through an ATM-switch which has both input and output buffers. The degree of fullness in the output buffers are measured and reported to a so-called “access device” for the input buffers. This comprises both input buffers and a choke mechanism in order to be able to stop the cell flow and thereby retain the cells in the input buffers when the degree of fullness in the output buffers exceeds a certain predetermined level. A status message concerning the degree of fullness of the output buffers is compared with an access message which indicates which output buffers are addressed by cells in the input buffers, and only the cells addressed to the overfull output buffers are stopped by the choke mechanism.
Another known method for controlling the flow of cells is to use a so-called “credit-based scheme” where the different inputs make a request for transmission of a certain number of cells during a fixed predetermined time interval. Even here every input buffer is divided into a number of FIFOs, one for each output. A control procedure among all the FIFOs which have made a request shows how much traffic which is destined to each output. The outputs can then decide, based on the result of the control procedure among the FIFO-memories, how many cells each FIFO may be allowed to send.
When the inputs make their request for transmission of a certain number of cells during a certain time interval, they only request transmission of that much which can be sent without risking queue formation at the outputs. In those cases therefore, no output buffers are required. The prior art also shows how in credit-based schemes, output buffers are used which store cells when there are long predetermined time intervals between the requests. According to the prior art there are in this case two trends. One way where the cells are allowed to be transmitted directly through the switch core as soon as they receive permission. This requires large and expensive output buffers since the number of cells transmitted during the long time interval can vary greatly, especially with the use of ATM-cells which often have a strongly burstlike traffic distribution.
Another way is to produce so-called “shaping” which means that during the time interval it is attempted to spread out the sending of the cells. If, for example, the time interval between the requests is set to 100 cell times and the input port has 10 cells in its buffer, one cell can be transmitted every tenth cell interval. In this way the size of the output buffers can be reduced. The disadvantage with this technique is, however, that one then postpones the transmission of cells which perhaps quite well could have been sent earlier during the time interval with reference taken to the total traffic intensity. The consequence is a bad degree of exploitation of the switch. Moreover, with burst-like traffic there will be requests for fewer cells than that which the switch core during low traffic can take care of while requests will be refused during high traffic, which contributes to a bad degree of utilization of the switch.
SUMMARY
It must be considered to be a problem to be able to keep a high degree of utilization of the switch in the so-called “Credit based scheme”. It must also be considered to be a problem to maintain a hi
Buhrgard Magnus
Kaminski Krzysztof
Larsson Berndt
Burns Doane Swecker & Mathis L.L.P.
Hom Shick
Olms Douglas W.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Flow control for switching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flow control for switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flow control for switching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2500904