Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1998-02-04
2001-06-05
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
C370S235000, C709S223000
Reexamination Certificate
active
06243358
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a process for allocating resources in a packet transmission digital network.
BACKGROUND OF THE INVENTION
In networks for transmitting data, in packet mode, which exhibit a high bit rate, of the order of 34 Mbit/s to 622 Mbit/s for example, the behaviour of the sources is generally very irregular.
Moreover, while crossing a network, a set of data may pass through transmission links which support very different bit rates.
Even when the capacities of the various transmission links are identical, several data streams originating from different nodes may show up simultaneously at a particular input of a node, creating a “bottleneck” liable to give rise to a state of congestion in the network.
It is sought both to make the best use of the available passband, by authorizing the sources to send as soon as this is possible and to prevent congestion leading to data loss, by slowing down the sources as appropriate: this is referred to as flow control.
Flow control methods are already known, two main families being distinguishable: flow control based on allocating credits and flow control based on allocating bit rates; the invention lies in the first family.
The principle of flow control based on allocating credits is as follows: a sender is prohibited from transmitting data so long as it has not received from the receiver the indication that the receiver is able to accommodate them. To do this, the receiver regularly dispatches packets of credits to the sender, containing information about its capacity to receive data.
The number of “credits” transported by each packet of credits dispatched by the receiver to the sender corresponds, for each virtual input channel of the sender, to the number of unoccupied slots in an input buffer register assigned to this virtual channel. Various algorithms for managing credits have been proposed. Reference can be made for example to the article by H. T. Kung et al., “Credit-based flow control for ATM networks: credit update protocol, adaptive credit allocation and statistical multiplexing”, ACM 1994.
A drawback of this process is due to the time required for the control information to make its way back to the sender. The sender's reaction to a request from the receiver is therefore delayed, which may cause under-utilization of the resources, this being all the greater the larger the distance between the transmitter node and the receiver node. If for example this distance is 500 km, the propagation time Rtt is 5 ms. The upstream or sender node therefore only reacts to a dispatch of credits 5 ms after the instant of availability. This delay Rtt corresponds to the send duration for 1768 packets of 53 bytes at 150 Mbit/s. Unless extremely long input buffers are used at the receiver node, this method of allocating credits results in under-utilization of the transmission link between the sender and receiver nodes.
In the present document, unless advised otherwise, the term “transmitting a packet” is regarded as meaning dispatching this packet and erasing it from the buffer which stores this packet. If this is not the case, explicit mention will be made that the sender “preserves” the said packet.
SUMMARY OF THE INVENTION
The objective of the present invention is to provide a flow control process with allocation of credits which makes it possible to do away with the limitations related to the propagation time Rtt.
In order to achieve this objective, the present invention proposes a process for allocating resources in a packet data transmission digital network, between a data sender node and an adjacent data receiver node which resends in the downstream direction, according to which:
(a) the receiver node dispatches to the sender node packets of credits containing information about the capacity of the receiver node to receive data packets originating from the said sender node;
(b) the sender dispatches the data packets which it needs to transmit so long as it has sufficient credits;
wherein:
(c) when its credits are exhausted, the sender node continues to dispatch, in advance, the waiting data packets which it needs to transmit and preserves each data packet sent in advance until reception thereof is confirmed by the arrival of specific packets originating from the receiver;
(d) the receiver dispatches to the sender information indicating the lost data packets;
(e) the sender retransmits the data packets whose loss has been signalled by the receiver and destroys the data packets which were sent in advance and preceding the lost data packets.
In a particular embodiment, the data packets sent bear a sequence number and the packets of credits contain the highest one of said sequence numbers of said data packets which the receiver is ready to receive.
If the sender possesses several queues respectively associated with several network propagation channels, the data packets being sent in the order of their sequence number, the sender first transmits data packets originating from those of the queues for which the sequence number contained in the last packet of credits received originating from the receiver is strictly greater than the number of the last data packet dispatched, and the sender then transmits, in advance, data packets originating from those of the queues for which sending in advance is authorized (see below), for which the sequence number contained in the last packet of credits received originating from the receiver is less than or equal to the number of the last data packet dispatched and for which the difference between the two sequence numbers is smallest, the sender preserving the data packets transmitted in advance.
If the receiver possesses several queues associated with several network propagation channels, upon the arrival of a data packet with sequence number m which cannot be admitted at the receiver, through lack of space in the corresponding queue, while the preceding data packet in respect of this queue has been admitted, the receiver dispatches to the sender a rejection detection packet which includes the sequence number m and systematically rejects all the succeeding data packets, until the arrival, by retransmission, of a fresh version of that data packet whose sequence number is m.
When the sender receives a packet of credits, respectively a rejection detection packet, originating from the receiver, it destroys all the data packets, necessarily sent in advance, whose sequence number is less than or equal to, respectively less than, the sequence number indicated in the packet of credits, respectively in the rejection detection packet.
When the sender receives a rejection detection packet originating from the receiver, it disables the sending in advance of data packets in respect of the relevant propagation channel, until the arrival of a packet of credits which includes a sequence number greater than or equal to the sequence number of the first data packet waiting to be resent or to be transmitted next over this propagation channel.
All these operations may be controlled by programming a processor or controller or performed by hard-wired logic.
In a particular embodiment, the receiver dispatches a packet of credits to the sender as soon as one or the other of the following events occurs: (i) the number of data packets which have departed downstream, since the sending of the last packet of credits to the sender, is equal to a predetermined number; (ii) a predetermined duration of non-sending of packets of credits has elapsed since the sending of the last packet of credits to the sender. In case (ii), the number of credits dispatched by the receiver to the sender may be zero.
By way of non-limiting example, the duration of non-sending may be chosen equal to half the time for the round trip propagation of a data packet between the sender and receiver nodes.
The present invention also proposes a device for allocating resources in a packet data transmission digital network, comprising:
a data receiver node which includes
a predetermined number n of input buffers, respectively associated wi
Chin Wellington
France Telecom
Nguyen Steven
Oliff & Berridg,e PLC
LandOfFree
Process and device for allocating resources in a packet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process and device for allocating resources in a packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process and device for allocating resources in a packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2469423