Method for organizing packets belonging to streams, and associated equipment
View Patent ↗The inventive method consists in determining a flow (F) to which belongs each new incoming packet (P), when said flow (F) is on a list of active flows, in introducing said packet into a fair share scheduling mechanism ( 6 ), when said flow (F) is absent from the list of active flows, in obtaining an estimation of the quantity of incoming data items (I.Bytes) with respect to said flow over a reference time period, in comparing said estimation with a maximum value (MaxBytes), wherein the reference time period or the maximum value are determined according to a fair share data rate, in adding said flow to the list of active flows and in introducing the packet (P) into the fair share scheduling mechanism ( 6 ), if said estimation exceeds the maximum value, and in introducing the packet (P) into the end of a priority queue ( 5 ), in the alternative case.
1. A method for organizing data packets belonging to streams, comprising:
/a/ determining the stream to which an incoming packet belongs, wherein a flow rate class is associated with said stream;
/b/ when said stream is part of a list of active streams, introducing the packet into a fair sharing organization mechanism for the purpose of delivering the packet, the fair sharing organization mechanism being designed to deliver the packets from each stream substantially as per the same fair flow rate weighted by the flow rate class associated with the corresponding stream; and
/c/ when said stream is not part of the list of active streams:
obtaining an estimate of the quantity of incoming data items in relation to said stream over a reference time interval;
comparing the estimate of the quantity of incoming data items in relation to said stream over the reference time interval with a maximum value, at least either the reference time interval or the maximum value being determined on the basis of an estimate of the fair flow rate;
adding said stream to the list of active streams and introducing the packet into the fair sharing organization mechanism for the purpose of delivering the packet, if the estimate of the quantity of incoming data items in relation to said stream over the reference time interval exceeds the maximum value; and
otherwise, introducing the packet at the end of a priority queue for the purpose of delivering the packet.
2. The method as claimed in claim 1 , wherein said maximum value is a quantity of data items dependent on the flow rate class associated with said stream.
3. The method as claimed in claim 1 , wherein the estimate of the quantity of incoming data items in relation to said stream comprises an estimate of a number of incoming packets in said stream over the reference time interval and in which said maximum value is a fixed number of packets independent of the flow rate class associated with said stream.
4. The method as claimed in claim 1 , wherein obtaining the estimate of the quantity of incoming data items in relation to said stream comprises updating, in the course of said reference time interval, a field in a table whose address corresponds to a function of an identifier of said stream, each field in the table being reset to zero at the start of the reference time interval.
5. The method as claimed in claim 1 , wherein estimating the fair flow rate comprises successive evaluations of the fair flow rate and smoothing at least some of said successive evaluations.
6. The method as claimed in claim 1 , wherein the fair sharing organization mechanism is part of at least either a round robin mechanism or a stamping mechanism.
7. The method as claimed in claim 1 , comprising a prior admission control in which it is decided whether or not the packet needs to be rejected before step /b/, on the basis of an available passband and a filling level for the priority queue.
8. The method as claimed in claim 1 , wherein all of the packets introduced into the priority queue are delivered, and then at least some of the packets introduced into the fair sharing organization mechanism are delivered.
9. An apparatus capable of being used to organize data packets belonging to streams, comprising:
/a/ means for determining a stream to which an incoming packet belongs, a flow rate class being associated with said stream;
/b/ means for introducing the packet into a fair sharing organization mechanism for the purpose of delivering the packet, when said stream is part of a list of active streams, the fair sharing organization mechanism being designed to deliver the packets from each stream substantially as per the same fair flow rate weighted by the flow rate class associated with the corresponding stream; and
/c/ means for, when said stream is not part of the list of active streams:
obtaining an estimate of the quantity of incoming data items in relation to said stream over a reference time interval;
comparing the estimate of the quantity of incoming data items in relation to said stream over the reference time interval with a maximum value, at least either the reference time interval or the maximum value being determined on the basis of an estimate of the fair flow rate;
adding said stream to the list of active streams and introducing the packet into the fair sharing organization mechanism for the purpose of delivering the packet, if the estimate of the quantity of incoming data items in relation to said stream over the reference time interval exceeds the maximum value; and
otherwise, introducing the packet at the end of a priority queue for the purpose of delivering the packet.
10. A router capable of being used to organize data packets belonging to a stream, comprising:
means for determining the stream to which an incoming packet belongs, a flow rate class being associated with said stream;
means for introducing the packet into a fair sharing organization mechanism for the purpose of delivering the packet, when said stream is part of a list of active streams, the fair sharing organization mechanism being designed to deliver the packets from each stream substantially as per the same fair flow rate weighted by the flow rate class associated with the corresponding stream; and
means for, when said stream is not part of the list of active streams:
obtaining an estimate of the quantity of incoming data items in relation to said stream over a reference time interval;
comparing the estimate of the quantity of incoming data items in relation to said stream over the reference time interval with a maximum value, at least either the reference time interval or the maximum value being determined on the basis of an estimate of the fair flow rate;
adding said stream to the list of active streams and introducing the packet into the fair sharing organization mechanism for the purpose of delivering the packet, if the estimate of the quantity of incoming data items in relation to said stream over the reference time interval exceeds the maximum value; and
otherwise, introducing the packet at the end of a priority queue for the purpose of delivering the packet.
11. A computer program product comprising memory encoded with computer-executable instructions for organizing data packets belonging to streams, the computer-executable instructions comprising:
determining the stream to which an incoming packet belongs, a flow rate class being associated with said stream;
when said stream is part of a list of active streams, introducing the packet into a fair sharing organization mechanism for the purpose of delivering the packet, the fair sharing organization mechanism being designed to deliver the packets from each stream substantially as per the same fair flow rate weighted by the flow rate class associated with the corresponding stream; and
when said stream is not part of the list of active streams:
obtaining an estimate of the quantity of incoming data items in relation to said stream over a reference time interval;
comparing the estimate of the quantity of incoming data items in relation to said stream over the reference time interval with a maximum value, at least either the reference time interval or the maximum value being determined on the basis of an estimate of the fair flow rate;
adding said stream to the list of active streams and introducing the packet into the fair sharing organization mechanism for the purpose of delivering the packet, if the estimate of the quantity of incoming data items in relation to said stream over the reference time interval exceeds the maximum value; and
otherwise, introducing the packet at the end of a priority queue for the purpose of delivering the packet.