Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-11-16
2003-12-30
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S236000, C370S244000, C370S388000, C370S390000, C370S429000
Reexamination Certificate
active
06671255
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a method and an apparatus for flow control of a data packet flow.
BACKGROUND
Traditionally, the traffic in ATM networks has been dominated by Constant Bit Rate (CBR) connections. This type of connection requires that the network, and all nodes in the network, be dimensioned in such a way that all subscribers can utilize their peak load at the same time, so that the risk of congestion in a buffer is small or negligible.
New services such as Available Bit Rate (ABR), Variable Bit Rate (VBR), real-time Variable Bit Rate (rt-VBR) and Unspecified Bit Rate (UBR), on the other hand, imply a very uneven and unpredictable flow, in which the information packets are transferred in bursts. If all buffers on all levels were to be dimensioned to handle this, very large buffer memories would be required, which would in turn lead to long storage times causing long delays.
A known solution to the problem is to provide a separate unit in the exchange, receiving information from all buffers about their degree of fullness, and, if a buffer becomes too full, transmits a bandwidth limiting signal to all units transmitting cells to this buffer. An apparatus and a method based on this principle are disclosed in European Patent Specification EP 0 374 928 A2.
EP 0 661 851 A2 describes a method for blockage supervision in a packet switched network in which threshold values are used to determine if a unit in the network has reached a too high degree of fullness. The information about a unit having a too high degree of fullness is added in the header field of a cell passing through the unit.
When the cell reaches the receiver, the receiver transmits a message to the source, that the transmission rate has to be decreased.
Alternatively, the unit for which the degree of fullness is too high transmits such a message itself.
SUMMARY
An object of the present invention is to provide a method and an apparatus for flow control which will maximize the utilization of the parts of the network when the traffic has a burst character.
Another object of the invention is to provide a packet switched exchange, such as an ATM exchange, that can provide new service classes, such as ABR, VBR, rt-VBR and others.
These objects are achieved according to the invention through flow control by means of relative addressing of buffers according to the following:
a receiving unit which is permanently or temporarily unable to receive data packets transmits a backpressure message to the unit or units from which it is arranged to receive data packets;
a unit receiving such a backpressure message changes and/or makes additions to this message so that it comprises information about all units that the message has passed;
the source node or nodes for the data packet flows, when a backpressure message is received, reduces or stops all data packet flows intended to pass the unit from which the backpressure message originated.
The backpressure message comprises a first field (m) indicating the number of levels passed by the message.
According to a first preferred embodiment the following steps are repeated for each unit passed by the message:
incrementing the message level indicator in the first field (m);
adding a field indicating from which unit the message last came, relative to the unit in which the message is currently found;
forwarding the message to all units from which the unit in which the message is currently found is arranged to receive data.
According to a second preferred embodiment the following steps are repeated for each unit passed by the message:
incrementing the message level indicator in the first field (m);
adding a field indicating the unit in which the message is now located, relative to the level from which this unit is arranged to receive data packets;
forwarding the message to all units from which the unit in which the message is currently found is arranged to receive data.
The unit from which a backpressure message is received in another unit is identified by its number, of the total number of units, to which the receiving unit is connected.
A standard value may be set for bow long a back pressure message should be considered valid.
The message may also comprise an extra field arranged to contain additional information, which may, for example, be arranged to assume one of two possible values indicating that the backpressure message signifies the start of the problems and that the problems have ceased, respectively. The field for additional information may also comprise information about the degree of fullness of the buffer, indicating the action to be taken by the receiving unit in response to the backpressure message, or information about the length of the period in which the backpressure message should be considered valid.
The unit from which the backpressure message originates may be a buffer in a hierarchy of buffers in a packet switch, and that the unit receiving and acting on the backpressure message is a buffer on a higher level in the same buffer hierarchy.
The unit from which the backpressure message originates may also be a node in a packet switched network and that the unit receiving and acting on the backpressure message is a host in said packet switched network.
A hierarchical structure of buffers in which each buffer is arranged to receive data packets from at least one buffer on the next preceding hierarchical level and to transmit data packets to at least one buffer on the next succeeding hierarchical level is also disclosed comprising, for each buffer, or for a group of buffers on the same hierarchical level, control logic, arranged to
compare the degree of fullness of the buffer or buffers to one or more threshold values;
when the degree of fullness of a buffer exceeds a threshold value, transmit a back-pressure message to the next preceding hierarchical level;
when such a backpressure message is received from the control logic of a buffer on a subsequent hierarchical level, change or add information to this message so that it will comprise information about the unit the message has passed.
A node for use in a packet switched network is also disclosed, which is arranged to
when a problem with the reception or transmission of packets to or from the node arises: transmit a backpressure message indicating the character of the problem to all nodes in the network from which the node receives packets;
when a backpressure message is received, add information to the message so that the message comprises information about all nodes the message has passed.
An advantage of the solution according to the invention is that the method may be used independently of the size of the exchange (and thus of the exchange core), and the network.
For the method to be used, an arbitrary buffer in the exchange core does not have to know its own location in the system, or how many other buffers, or nodes, respectively, are found on the same hierarchical level.
A level in a structure according to the invention may be defined as a place in the structure where a path selection is made. In these places data packets must be stored in buffers, since data packets may be received from several different units in the level immediately above.
REFERENCES:
patent: 5253248 (1993-10-01), Dravida et al.
patent: 5319638 (1994-06-01), Lin
patent: 5457687 (1995-10-01), Newman
patent: 5475682 (1995-12-01), Choudhury et al.
patent: 5493566 (1996-02-01), Ljungberg et al.
patent: 5689500 (1997-11-01), Chiussi et al.
patent: 5787071 (1998-07-01), Basso et al.
patent: 5790770 (1998-08-01), McClure et al.
patent: 5825751 (1998-10-01), Papierniak et al.
patent: 6011779 (2000-01-01), Wills
patent: 6052376 (2000-04-01), Wills
patent: 6490248 (2002-12-01), Shimojo
patent: 0 374 928 (1990-06-01), None
patent: 0 512 495 (1992-11-01), None
patent: 0 647 081 (1995-04-01), None
patent: 0 661 851 (1995-07-01), None
patent: 0 712 220 (1996-05-01), None
patent: 0 719 012 (1996-06-01), None
patent: 95/19675 (1995-07-01), None
Leonardi et al, Congestion Control in Asynchronous High-speed Wormhole Routing Networks,
Buhrgard Magnus
Kaminski Krzysztof
Larsson Bernt
Wicklund Göran
Elallam Ahmed
Kizou Hassan
Telefonaktiebolaget LM Ericsson
LandOfFree
Method and apparatus in a packet switched network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus in a packet switched network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus in a packet switched network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3182067