[go: up one dir, main page]

WO2004095783A2 - Procede et dispositif de controle d’un trafic de paquets de donnees en entrée d’un reseau - Google Patents

Procede et dispositif de controle d’un trafic de paquets de donnees en entrée d’un reseau Download PDF

Info

Publication number
WO2004095783A2
WO2004095783A2 PCT/FR2004/000955 FR2004000955W WO2004095783A2 WO 2004095783 A2 WO2004095783 A2 WO 2004095783A2 FR 2004000955 W FR2004000955 W FR 2004000955W WO 2004095783 A2 WO2004095783 A2 WO 2004095783A2
Authority
WO
WIPO (PCT)
Prior art keywords
tokens
priority level
network
token
packets
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/FR2004/000955
Other languages
English (en)
Other versions
WO2004095783A3 (fr
Inventor
Gérard Babonneau
Wissem Loudhaief
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Orange SA
Original Assignee
France Telecom SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom SA filed Critical France Telecom SA
Priority to EP04742535A priority Critical patent/EP1616414A2/fr
Priority to US10/553,617 priority patent/US7542417B2/en
Publication of WO2004095783A2 publication Critical patent/WO2004095783A2/fr
Publication of WO2004095783A3 publication Critical patent/WO2004095783A3/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS
    • H04L47/2441—Traffic characterised by specific attributes, e.g. priority or QoS relying on flow classification, e.g. using integrated services [IntServ]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/215—Flow control; Congestion control using token-bucket
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/32—Flow control; Congestion control by discarding or delaying data units, e.g. packets or frames

Definitions

  • the field of the invention is that of communication networks, and in particular but not exclusively of networks of IP type or equivalent. More specifically, the invention relates to a method for controlling traffic of data packets entering a network, in the case where the traffic comprises a plurality of streams and / or substreams each associated with a priority level , and where each of the packets is marked with the priority level associated with the stream or substream to which this packet belongs. In other words, the invention relates to a network mechanism making it possible to optimize the flow of incoming traffic on a network.
  • the invention has numerous applications, such as for example the control of multimedia streams (for example MPEG streams), alone or by aggregates, or even the control of a multiplex of streams of different natures (for example a video stream / multiplex audio with a TCP stream, on an ADSL access).
  • multimedia streams for example MPEG streams
  • aggregates for example a video stream / multiplex audio with a TCP stream, on an ADSL access.
  • a multiplex of streams of different natures for example a video stream / multiplex audio with a TCP stream, on an ADSL access.
  • TCP Transmission Control Protocol
  • TCP Transmission Control Protocol
  • session level control the protocol parameters make it possible to detect possible congestion, and to adapt the bit rate of the source to the constraints of the network. The objective is then to limit the speed if the network cannot handle everything, and to avoid sending packets which will be lost.
  • Many studies today seek to apply equivalent mechanisms to video streams, with the real-time constraint of a dynamic adaptation of coders to the available bit rate.
  • the real-time and audiovisual protocols currently do little processing, and are mainly limited to marking the transmission time and the encapsulation of packets of the application for their routing in the IP layer (for example RTP / UDP), in charge of the applications to cope with the received data.
  • IP layer for example RTP / UDP
  • IntServ defines means for reserving a resource with guaranteed speed between two nodes of a network
  • DiffServ defines means for dynamically controlling the flow of flow aggregates as a function of the network load. Compared with end-to-end solutions (analogous to TCP) solutions located in routers have several advantages:
  • Processing in routers is based on a distinction between packets arriving in routers supporting “quality of service” (QoS, “Quality of Service”) mechanisms.
  • QoS quality of service
  • the size of the images P is generally much smaller than that of the images I, and coding with few I images makes it possible to obtain, at equivalent bit rate, a much higher decoding quality. Under these conditions, the loss of an image is not equivalent depending on the nature of the information it contains. This structure of information must lead to considering the importance or the weight of each piece of information in its processing by the network. There are two reasons for keeping images I:
  • Another way of considering this weight of information is to split an MPEG4 stream into several hierarchical levels to obtain a variable quality according to the overall content received by the user.
  • a hierarchical level N must be supported on the presence of the Nl lower levels to provide additional quality.
  • An elementary case is to consider a video made up of a basic stream (containing I and P images) and of an enhancement stream (containing P and B images). For this elementary case, the basic flow as a whole is considered to have higher priority than the enhancement flow.
  • ADSL Asymmetry Digital Subscriber Line
  • bursts are the most important information because they correspond to a change of scene or at least to a significant change in the content of the image. Very often, these images are of type I (Intra) whose loss is very critical, because it becomes impossible to reproduce the following images, even if the latter are correctly received.
  • I Intra
  • Traffic shaping and conditioning mechanisms are used in “quality of service” (QoS) IP networks.
  • QoS quality of service
  • TSPEC Traffic Specifier
  • Traffic specification Traffic smoothing
  • Traffic smoothing (TS) algorithms are however widely used in coding in order to control the bit rate of coders. This remains insufficient to control flows at the network level.
  • TS Smoothing smoothes the bursts by “buffering” (that is to say by buffering) the packets concerned by the excess of bursts in the border equipment of the network. It can reduce congestion to acceptable levels, especially that scheduling algorithms such as CBQ (“Class Based Queuing” ie “management of queues based on service classes) ”) Or PQ (“ Priority Queuing ”that is to say“ queue management by priorities ”) are not able to do this. Used alone, these mechanisms propagate bursts in the network.
  • CBQ Class Based Queuing
  • PQ Priority Queuing
  • traffic rule control limits the traffic rate to the configured rate. But instead of "buffering" packets like smoothing (TS), non-compliant packets are either rejected or noticed to lower their priorities. Traffic rule control (TP) therefore does not smooth traffic, but it does not introduce a "buffering" delay either.
  • the network service provider (NSP) is not required to treat MPEG streams differently.
  • the traffic aggregate resulting from several audio-visual streams is generally difficult to describe: - the packet arrival process is self-similar;
  • the media access gateway (MAG, for “Media Access Gateway”) is for example responsible for this task.
  • This MAG gateway manages traffic according to the specified SLS. This approach facilitates the negotiation of SLA / SLS for services in continuous mode (“Streaming”) and imposes on the client a very specific traffic profile.
  • the WRED Weighted Random Early Drop
  • This mechanism is based on an average filling rate of the transmission queue on a network link.
  • this technique introduces a random nature of packet rejections, and the filling rate of the queue is not optimized. Depending on the size of the bursts and their frequency, these rejections can occur for a low filling or a very high filling of the queue. This leads on the one hand to an underuse of the queue, and on the other hand to the reservation of consequent memory size for the realization of this queue. This problem exists for any type of application, and it is even more real for audiovisual streams because of their large bursts.
  • the WRED mechanism is therefore not suitable for controlling flows characterized by an average value over a fixed duration.
  • the invention particularly aims to overcome these drawbacks of the prior art and offer an optimal solution in the event of network congestion.
  • one of the objectives of the present invention is to provide a method and a device for traffic control making it possible to control gusts and to smooth traffic over a set of flows and / or substreams associated with levels of priorities.
  • an objective of the present invention is to provide a method and a device for traffic control making it possible to protect the important information from the bursts, in order to provide a solution to the contradiction between the optimization of a stream (for example a video stream) containing bursts and smoothing the bursts for quality transport in the network.
  • a stream for example a video stream
  • the invention also aims to provide such a method and device which are simple to implement and inexpensive.
  • Another objective of the invention is to provide such a method and device making it possible to efficiently offer traffic contracts (SLA / SLS) between network operators and service providers.
  • SLA / SLS traffic contracts
  • a method for controlling a traffic of data packets entering a network comprising N stream and / or substream each associated with a priority level, N> 2, each of the packets being marked with the priority level associated with the stream or substream to which said packet belongs, said method comprising an implementation step an N-level token bucket mechanism with N token buffers each containing a number of available tokens, the tokens of each of the N token buffers being used to process one of the N levels of priority, each packet being accepted or refused depending on whether or not it is possible to allocate tokens according to it tokens available at least in the token buffer used to process the priority level of said packet.
  • the general principle of the invention therefore consists in using a multi-level token bucket (MLTB, for “Multi Layer Token Bucket”) to reject packets outside a required profile and characterized by the N operating levels of the bucket multi-level tokens.
  • MLTB multi-level token bucket
  • Each packet undergoes processing according to a marking corresponding to its priority level. Accepted packets are placed in a queue.
  • the multi-level token bucket makes it possible to selectively and jointly process several levels of flow priorities. It is well suited to characterizing traffic between the size of incoming gusts and the flow of outgoing traffic. We know that in the event of network congestion, it is illusory to seek available bandwidth.
  • the adjustment of the parameters of the multi-level token bucket ensures a relationship between the priority levels to balance the operating constraints between the flow rates by priority levels and the bursts acceptable by the token bucket according to the constraints of the transported applications.
  • the characterization of the parameters of the N sets of parameters of the multi-level token bucket allows numerous solutions and can be adapted to almost all operating cases:
  • an extreme case is the behavior with N sets of independent parameters acting like buckets with independent tokens;
  • another extreme case is the possibility for the highest priority level to take all the tokens and result in a rejection of the packets from all the other levels;
  • the invention therefore makes it possible to process bursts on the highest priority levels, because there is for each priority level a reserve available to prevent any sudden arrival of a set of data which must not be rejected.
  • a usual token bucket has only one operating level (it has a single set of parameters) and therefore processes all packets indiscriminately. Packets are therefore dropped in the event of network congestion regardless of their priority level.
  • the present invention is fully compatible with IP streams “unicast” (single recipient) and “multicast” (selectively broadcast). It will also be noted that the present invention makes it possible to transmit several groups of flows with different priorities in the same class of service.
  • the invention makes it possible to provide processing adapted to one or a group of video streams (IPB or hierarchical) in accordance with a contracted traffic profile (SLS) by characteristic values of the token bucket type.
  • SLS traffic profile
  • the easily measurable and adaptable parameters of a multi-level token bucket (MLTB) are an effective means of proposing traffic contracts (SLA / SLS) between network operators and service providers. The presence of priority information leads to the specification of this bucket.
  • the multiple versions of this bucket are a means of offering classes of services adapted to customer requirements.
  • the traffic profile involves the main elements of characterization of a flow in a network: the speed and the delay.
  • the invention is therefore a means of defining a contract with a negotiated compromise between the speed, the size of the bursts, and the transmission time.
  • the traffic comprises N sub-flows each corresponding to one of the N hierarchical levels of a hierarchical flow or of an aggregate of hierarchical flows.
  • the traffic comprises N sub-streams each corresponding to one of the N types of images of a multimedia stream or of an aggregate of multimedia streams.
  • the traffic comprises N streams each corresponding to one of the stream of a multiplex of at least two streams.
  • This is for example a multiplex video / audio stream with a TCP stream, on an ADSL access.
  • the traffic comprises N flows and / or substreams belonging to the same class of service.
  • the invention thanks to the multi-level token bucket, makes it possible to transmit several flows and / or sub-flows with different priorities in the same service class.
  • service classes such as for example the "streaming" class (containing audio and video streams, the "priority TCP” class, the "Best IP network effort” class, ...) and use a bucket with multi-level token for each class.
  • Each class of service can be defined by marking packets, by the source or destination IP address of the packets, by the protocol used for the packets, etc.
  • the refused packets are discarded.
  • the packets refused are those which do not comply with the traffic profile defined by the parameters of the N operating levels of the multi-level token bucket.
  • Another option, less efficient but which nevertheless falls within the scope of the present invention, is to transmit the refused packets after having marked them again with a lower priority level.
  • this option has the disadvantage of increasing the probability of packet rejection in congested network nodes.
  • the network is of IP type or equivalent.
  • each of the N operating levels of the token bucket mechanism is managed by a regulator bi (r b b ⁇ i;), i G ⁇ 1 to N ⁇ , with: r j the nominal flow rate of the regulator; - bn; the maximum size of the controller token buffer; bi (t) the instantaneous value of the filling of the regulator token buffer.
  • the tokens of the N token buffers are shared between the N priority levels, a packet of priority level i being able to be allocated tokens of a token buffer associated with a priority level j less priority when the tokens available in the token buffer of priority level i are not sufficient.
  • the allocation of tokens to a packet of priority level i is carried out according to a discontinuous mode per packet and consists in assigning: either tokens available in the token buffer memory of priority level i; - or tokens available in a token buffer of priority level j with lower priority, when the tokens available in the buffer of tokens of priority level i are not sufficient.
  • a packet can use resources (tokens) only on one level of operation of the multi-level token bucket.
  • the allocation of tokens to a packet of priority level i is carried out in a continuous mode per bit and consists in allocating: tokens available in the buffer of level tokens of priority i; and in addition to the tokens available in at least one buffer of tokens of priority level j with lower priority, when the tokens available in the buffer of tokens of priority level i are not sufficient.
  • a packet in the continuous mode, can use the resources (tokens) of several operating levels of the multi-level token bucket at a time.
  • the packets accepted by the token bucket mechanism with N operating levels are placed in a queue.
  • the method further includes a step of implementing a token bucket mechanism at a single level of operation with a single token buffer, so as to take the packets contained in the queue and send them over the network by performing traffic smoothing by limiting the instantaneous speed to a value acceptable by the network .
  • the single-level token bucket (TBTS, for “Token
  • Bucket Traffic Shaper therefore makes it possible to limit the peak bit rates emitted by the network equipment supporting the invention. It delays gusts when they exceed the tolerated flow in the network.
  • the invention also relates to a computer program comprising program code instructions for executing the steps of the method as mentioned above, when said program is executed on a computer.
  • the invention also relates to a device for controlling a traffic of data packets entering a network, the traffic comprising N streams and / or substreams each associated with a priority level, N> 2, each of the packets being marked with the priority level associated with the stream or sub-stream to which said packet belongs, said device comprising means for implementing a token bucket mechanism with N operating levels with N token buffer memories each containing a number of tokens available, the tokens of each of the N token buffer memories being used to process one of the N priority levels, each of the packets being accepted or refused according to whether or not it is possible to assign tokens to it according to the tokens available at least in the token buffer memory used to process the priority level of said packet.
  • said method comprises means for sharing the tokens of the N token buffer memories between the N priority levels, a packet of priority level i being able to be allocated tokens from a token buffer associated with a lower priority level j when the tokens available in the token buffer of priority level i are not sufficient.
  • said sharing means comprise means for guaranteeing a quantity of tokens reserved exclusively for packets having said priority level.
  • the invention also relates to network equipment comprising a control device as mentioned above, said network equipment belonging to the group comprising: network equipment located between a network of an application or service provider and a network of a provider of 'a network service, constituting said network at the input of which is carried out the control of a data packet traffic; - routers included in nodes of a network of a network service provider, constituting said network at the input of which is carried out the control of a traffic of data packets
  • FIG. 1 presents an example of network architecture in which the traffic control method according to the invention can be implemented
  • FIG. 2 illustrates a particular embodiment of the method according to the invention, implementing two functions, based on the use respectively of a multi-level token bucket and a single-level token bucket
  • FIG. 3 illustrates a regulator managing an operating level of the multi-level token bucket illustrated in FIG. 2, as well as the use in this regulator of a parameter K j guaranteeing a minimum of resource for the priority level associated with this regulator;
  • FIG. 1 presents an example of network architecture in which the traffic control method according to the invention can be implemented
  • FIG. 2 illustrates a particular embodiment of the method according to the invention, implementing two functions, based on the use respectively of a multi-level token bucket and a single-level token bucket
  • FIG. 3 illustrates a regulator managing an operating level of the multi-level token bucket illustrated in FIG. 2, as well as the use in this regulator of a parameter K j guaranteeing a minimum of resource for the priority level associated with this regulator
  • FIG. 4 illustrates an example of allocation of tokens in the case where the operation of the multi-level token bucket is described with independent buffer memories (buffers);
  • FIG. 5 illustrates an example of allocation of tokens in the case where the operation of the multi-level token bucket is described with correlated buffers.
  • the invention therefore relates to a method for controlling data packet traffic entering a network.
  • the traffic is of the type comprising N streams and / or substreams each associated with a priority level, with N> 2.
  • Each of the packets is marked with the priority level associated with the stream or substream to which it belongs.
  • the invention makes it possible to transmit, as a priority, the essential information of a video stream, or of several video streams grouped in an aggregate.
  • this distinction is for example possible either by IBP type images (see definition above), or by the n layers of a hierarchical flow. If in the first case the average bit rate of the images I remains low compared to the global bit rate, in the second case the most important information and to be protected as much as possible is defined by the fraction of the global bit rate occupied by the base layer, and which can represent up to 50% of the flow. In general, the base layer is the only one to contain the reference information contained in the images I.
  • all data with the same priority level is treated the same.
  • all basic streams or all I frames are treated as a single higher bit rate stream than a single video.
  • Internet Service provider offering a streaming video transmission service.
  • the example of (simplified) architecture illustrated in Figure 1 includes:
  • IP network of type "DiffServ” an IP network of type "DiffServ" 1, managed by a network operator (also called network service provider, or NSP (for "Network service
  • Each network of service providers 3, 4 also comprises end equipment 8 , 9 connected to one of the routers on the IP network, called the edge router 2 , which is responsible for sending data from a server to a main route of an IP core network;
  • the method according to the invention is implemented in network equipment forming a traffic conditioner for entry into the IP network 1.
  • This network equipment can be located between the network of the service provider 3, 4 and the IP network 1 :
  • the network equipment implementing the method according to the invention can also be any router placed at a congestion point in the network (in particular for any access to an ADSL link).
  • FIG. 2 a particular embodiment of the method according to the invention. It protects important information from bursts and provides solutions to the contradiction between optimizing a video stream containing bursts and smoothing the bursts for quality transport in the network.
  • the overall mechanism forms a “multi-layer decentralized traffic conditioner” called “MLDTC” (for “Multi-Layers Decentralized Traffic Conditioner”). It consists of two functions executed sequentially:
  • MLTR Multi-Layers Traffic Regulator
  • N operating levels
  • N buffers of virtual tokens Each token buffer corresponds to a hierarchical level. Each operating level is defined by a set of parameters (see detailed discussion below).
  • TBTS for “Token Bucket Traffic Shaper” because it is based on a single-level token bucket algorithm (“Token Bucket”) (referenced 31) and performs a smoothing of the traffic for a regular flow on the network by limiting the instantaneous flow to a value acceptable by the network.
  • the TBTS function buffer is of reasonable capacity to guarantee a lower cost of the systems and a limited transfer time in the supply of information to the user.
  • the counterpart of the finite size is the limitation of the bursts accepted at the input of the network.
  • the MLTR function is adapted to the differentiated acceptance of bursts according to the priority level. It applies to IP packets (referenced 20 to 26 in Figure 2) whose DSCP (“Differentiated Services Code point”) field is marked either by the source or by a classification system.
  • Each priority level i has its own parameters, for a single buffer, common to the 3 levels, but with varying levels of acceptance of data packets. This mechanism meets the expectations of a video signal, since it does not process all information uniformly. Indeed, it is recalled that an MPEG coding results in several levels of information which should be treated differently according to their importance.
  • the objective is to favor the bursts of a level i compared to a level j, whose information is less important (j> i).
  • the packets relating to level i then have priority to exploit the available resources.
  • the same average bit rate is obtained for different burst sizes, and taking into account the interval separating them.
  • Such a mechanism is well suited to bursts of video streams, which are variable, due to the great diversity of content transported (sports, news, landscapes, ).
  • each operating level i of the token bucket with three operating levels 30 is managed by a regulator bj, bm ; ), i E ⁇ 1, 2, 3 ⁇ , with: - the nominal flow of this regulator;
  • Compliant packets i.e. those to which it has been possible to allocate tokens by the multi-level bucket 30
  • a buffer of packets to be sent 28 which forms a means of managing a queue wait. If an insufficient number of tokens is available in the multi-level bucket, the packets are then considered as non-compliant and are discarded. They are thrown in the trash referenced 27.
  • Another option is to transmit these packets with a lower priority. However, re-marking packets to give them a lower priority increases the probability of packet rejection in congested nodes.
  • a packet of priority level i can be allocated tokens from a token buffer associated with a priority level j of lower priority (j> i) when the tokens available in the buffer of level tokens of priority i are not sufficient.
  • the solution is to limit this borrowing by a parameter K j , specific to level j, the objective of which is to protect the latter from higher priority levels by guaranteeing a quantity of resources (tokens) reserved exclusively for packets of level j. Consequently, the parameter K j guarantees a threshold for filling the token buffers below which packets of a higher priority level can no longer be used.
  • the parameter K j of the level regulator j is illustrated in Figure 3.
  • K j The value of K j must be chosen such that bmj> K j > MTU.
  • K j is adapted to the useful size of a packet on the network (MTU (“Maximum Transfer Unit”, ie “maximum size of an elementary transfer unit”) for a network IP) corresponds to a guarantee of the nominal flow rate r j for level j but without guarantee of gusts. Token resources could be used by higher priority levels.
  • MTU Maximum Transfer Unit
  • FIG. 4 is a graphic representation of this token allocation algorithm in the case where the operation of the multi-level token bucket is described with independent buffers. It shows the possible use of the resources b t , b 2 and b 3 for each of the levels.
  • the thick lines (referenced 41, 42 and 43) show the filling of the token buffers (that is to say the number of tokens available) for each level, and the arrows the resources (that is to say tokens) taken by incoming packets (PI, P2 or P3) according to their priority.
  • B x ⁇ t + T) b x (t) + b 2 (t) + b 3 (t) + (r x + r 2 + r 3 ) l
  • B 2 (t + ⁇ ) b 2 ( ⁇ + b 3 (t) + (r 2 + r 3 ) TB 3 (t + T) ⁇ b 3 (t) + r 3 .T
  • FIG. 5 is a graphic representation of the token allocation algorithm in the case where the operation of the multi-level token bucket is described with correlated buffers. It shows the possible use of resources B ,, B 2 and B 3 for each of the levels. As in Figure 4, the thick lines (referenced 51, 52 and 53) show the filling of the token buffers (that is to say the number of tokens available) for each level, and the arrows the resources (i.e. tokens) taken by incoming packets (PI, P2 or P3) according to their priority.
  • a packet can only use one regulator
  • a packet can use several regulators at the same time.
  • the taking into account of the arrival of the packet is obtained by the following algorithm:
  • a packet is served by the resources of the level corresponding to the packet (level i) or of a lower priority level (level j). It should be noted that this operation is not optimal, since an incoming packet is rejected even if the sum of the available resources distributed over the 3 levels is sufficient.
  • the taking into account of the arrival of the packet is obtained by the following algorithm: shipment;
  • bits is more optimal than the discontinuous mode (packets). Indeed, it allows maximum use of own resources of the level before requesting resources at a lower priority level.
  • the single-level token bucket 31, on which this SELV function is based is for example defined by the following parameters:
  • - S the instantaneous value of filling the packet buffer 28 (S max is the maximum size of the packet buffer 28); - T, the time between the arrival of two consecutive packets;
  • Compliant packets i.e. those to which it was possible to allocate tokens by the single-level bucket 31
  • non-compliant packets are transmitted while non-compliant packets are delayed in the packet buffer 28 to contain them in the targeted traffic envelope.
  • the size of the packet buffer 28 should be handled with care because it can induce an additional delay, which must remain reasonable.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

L'invention concerne un procede de controle d'un traffic de paquets de donnees en entree d'un reseau, le trafic comprenant N flux et/ou sous-flux associes chacun a un niveau de priorite, N ≥ 2, chacun des paquets etant marque avec le niveau de priorite associe au flux ou sous-flux auquel appartient ledit paquet. Le procede comprend une etape de mise en oeuvre d'un mecanisme de seau a jetons a N niveaux de fonctionnement avec N memoires-tampons de jetons contenant chacune un nombre de jetons disponibles, les jetons de chacune des N memoires-tampons de jetons etant utilises pour traiter l'un des N niveaux de priorite, chacun des paquets etant accepte ou refuse selon qu'il est possible ou non de lui attribuer des jetons en fonction des jetons disponibles au moins dans la memoire-tampon de jetons utilisee pour traiter le niveau de priorite dudit paquet. Dans un mode de realisation particulier, les jetons des N memoires-tampons de jetons sont partages entre les N niveaux de priorite, un paquet de niveau de priorite i pouvant se voir attribuer des jetons d'une memoire-tampon de jetons associee a un niveau de priorite j moins prioritaire lorsque les jetons disponibles dans la memoire-tampon de jetons de niveau de priorite i ne sont pas suffisants.

Description

Procédé et dispositif de contrôle d'un trafic de paquets de données en entrée d'un réseau, programme d'ordinateur et équipement réseau correspondants.
Le domaine de l'invention est celui des réseaux de communication, et notamment mais non exclusivement des réseaux de type IP ou équivalents. Plus précisément, l'invention concerne un procédé de contrôle d'un trafic de paquets de données en entrée d'un réseau, dans le cas où le trafic comprend une pluralité de flux et/ou sous-flux associés chacun à un niveau de priorité, et où chacun des paquets est marqué avec le niveau de priorité associé au flux ou sous-flux auquel appartient ce paquet. En d'autres termes, l'invention concerne un mécanisme réseau permettant d'optimiser l'écoulement d'un trafic entrant sur un réseau.
L'invention a de nombreuses applications, telles que par exemple le contrôle de flux multimédia (par exemple des flux MPEG), seuls ou par agrégats, ou encore le contrôle d'un multiplex de flux de différentes natures (par exemple un flux vidéo/audio multiplexe avec un flux TCP, sur un accès ADSL). On présente maintenant brièvement le contexte réseau dans lequel se situe la présente invention.
L'augmentation des performances des ordinateurs ainsi que les débits offerts par les nouvelles générations de réseaux ouvrent la voie à de nouveaux services basés sur les flux multimédias. De fait, le nombre d'informations audiovisuelles transmises sur les réseaux (par exemple de type IP (« Internet Protocol »)) croît sans cesse, et les algorithmes de compression (par exemple de type MPEG (« Moving Picture Experts Group »)) s'améliorent, offrant une qualité meilleure avec des débits plus faibles. Cependant, aujourd'hui le niveau de qualité n'est pas toujours acceptable. Si chaque maillon de la chaîne a les capacités intrinsèques pour fournir cette qualité, leur mise bout à bout et le partage des ressources réseau IP par de nombreux usagers aboutissent parfois à des résultats médiocres.
D'une manière générale, la transmission d'informations dans un réseau IP s'appuie sur la couche transport pour un contrôle de la qualité entre la source et les récepteurs. Cette couche, située entre le routage et les applications, est réalisée traditionnellement par le protocole TCP (« Transmission Control Protocol »). D'un point de vue application, TCP se charge de retransmettre les informations perdues ou mal reçues, par un contrôle au niveau de la session. D'un point de vue réseau, certains paramètres du protocole permettent de déceler des possibles congestions, et d'adapter le débit de la source aux contraintes du réseau. L'objectif est alors de limiter le débit si le réseau ne peut pas tout écouler, et d'éviter d'envoyer des paquets qui seront perdus. De nombreuses études cherchent aujourd'hui à appliquer des mécanismes équivalents aux flux vidéo, avec la contrainte temps réel d'une adaptation dynamique des codeurs au débit disponible.
Mais en raison du temps important de réaction entre un ou plusieurs clients et la source vidéo, les protocoles temps réel et audiovisuels ne font actuellement que peu de traitements, et se limitent principalement au marquage du temps d'émission et à l'encapsulation des paquets de l'application pour leur routage dans la couche IP (par exemple RTP/UDP), à charge des applications de se débrouiller avec les données reçues.
L'évolution des réseaux offre la possibilité de gérer la « qualité de service »
(QoS) dans les routeurs. Or, il est pertinent de remarquer que c'est le lieu où se produisent la plupart des pertes des réseaux IP, et des mécanismes sont mis en oeuvre à ce niveau pour traiter sélectivement les différents flux en vue d'assurer au mieux des objectifs de qualité. Les moyens déployés pour améliorer la qualité des flux transmis sont l'objet des travaux des groupes « IntServ » (pour « integrated services », c'est-à-dire « intégration de services ») et « DiffServ » (pour « differentiated services », c'est-à-dire « services différenciés ») à l'IETF (Internet Ingineering Task Force) :
- « IntServ » définit des moyens pour réserver une ressource en débit garantie entre deux nœuds d'un réseau ;
- « DiffServ » définit des moyens pour contrôler dynamiquement le débit d'agrégats de flux en fonction de la charge du réseau. En comparaison avec les solutions de bout en bout (analogues à TCP) les solutions localisées dans les routeurs ont plusieurs avantages :
- elles s'affranchissent de toute contrainte de session ;
- elles sont aussi adaptées au temps réel, car leur action dans les routeurs est immédiate sans nécessiter de retour d'informations en provenance des usagers ; - elles sont donc naturellement adaptées à la diffusion sélective (« multicast »), car indépendantes du nombre d'usagers alimentés par le flux et indépendantes de rapports en provenance d'un nombre variable d'usagers.
Les traitements dans les routeurs s'appuient sur une distinction des paquets arrivant dans les routeurs supportant des mécanismes de « qualité de service » (QoS, pour « Quality of Service »).
Cette distinction existe naturellement dans les flux MPEG, car la compression des flux vidéo MPEG aboutit à une suite de données de natures différentes et non indépendantes. On distingue trois types d'images : I, P et B. Les images de type I (Intra), sont chacune codées sans faire référence à une autre image, la compression étant limitée à la réduction des redondances spatiales au sein de chaque image. Pour optimiser la quantité d'informations transmises, les codeurs MPEG exploitent le fait que deux images consécutives sont peu différentes en général. Une détection de mouvement ne considère que la partie qui vient de changer par rapport à l'image précédente pour obtenir une information de taille réduite codée dans une image de type P (Prédite).
D'autres moyens permettent d'obtenir une information encore plus réduite en interpolant les mouvements entre deux images de type I ou P ; ces images sont alors de type B (Bidirectionnelle).
La taille des images P est beaucoup plus petite en général que celle des images I, et un codage avec peu d'images I permet d'obtenir, à débit équivalent, une qualité de décodage bien supérieure. Dans ces conditions, la perte d'une image n'est pas équivalente en fonction de la nature de l'information qu'elle contient. Cette structure de l'information doit conduire à considérer l'importance ou le poids de chaque information dans son traitement par le réseau. Deux raisons justifient la conservation d'images I :
- la re-synchronisation périodique du flux en cas de pertes ;
- tout changement de scène car il n'est plus possible de s'appuyer sur les images précédentes pour un codage de mouvement.
Une autre manière de considérer ce poids de l'information est la découpe d'un flux MPEG4 en plusieurs niveaux hiérarchiques pour obtenir une qualité variable en fonction du contenu global reçu par l'usager. Un niveau hiérarchique N doit s'appuyer sur la présence des N-l niveaux inférieurs pour apporter un complément de qualité. Un cas élémentaire est de considérer une vidéo constituée d'un flux de base (contenant des images I et P) et d'un flux de rehaussement (contenant des images P et B). Pour ce cas élémentaire, le flux de base dans sa globalité est considéré plus prioritaire que le flux de rehaussement.
La distinction de nature des images ou des flux dans le trafic MPEG est à exploiter dans les routeurs « DiffServ » pour traiter sélectivement les différentes informations d'un flux vidéo :
- soit par un marquage du champs TOS (« type of service », c'est-à-dire « type de service ») ou DSCP (« Differentiated Services Code Point », c'est-à-dire
« valeur de marquage pour services différenciés ») des paquets par le serveur vidéo,
- soit par une classification effectuée par le routeur, ce qui aboutit également à un marquage des paquets IP. Dans le présent document, on considère que le marquage des paquets est possible dans tous les cas. Les moyens de réaliser ce marquage sont considérés comme bien connus de l'homme du métier. Ils ne sont donc pas discutés en détail.
Quand une situation de congestion apparaît dans un routeur, les paquets reçus sont éliminés en fonction de la charge et de leur niveau de priorité. Une caractéristique importante des données contenus dans ces paquets est leur variation importante en fonction du contenu de la scène. Or, les informations les plus critiques pour la restitution à l'usager sont contenues dans les rafales les plus importantes, et le problème principal des réseaux IP de type « Best effort » (c'est-à-dire sans garantie) est leur difficulté à laisser passer les rafales en cas de congestion. De ce fait, le simple marquage des flux élémentaires d'un flux MPEG n'est pas suffisant pour leur traitement optimal. En effet, les mécanismes « DiffServ » usuels sont prévus pour accepter des rafales que l'on trouve habituellement dans les réseaux IP, avec les applications qui sont majoritaires aujourd'hui : le transfert d'URL (« Uniform Resource Locator ») pour les applications WEB et les transferts de fichiers par FTP (« File Transport Protocol »). Toutes ces applications exploitent le protocole TCP dont les mécanismes ont fait l'objet de nombreuses études afin d'obtenir une montée en charge progressive, et une adaptation du débit en fonction de la charge du réseau.
Or, les flux vidéo remettent en cause ce fonctionnement car leur comportement est qualifié d'agressif, dans la mesure où ils ignorent généralement l'état et la charge du réseau. De plus, la plupart des mécanismes introduits dans les réseaux IP ont tous pour objectif le lissage des flux pour favoriser un bon écoulement du trafic. Paradoxalement, les codeurs fournissent une qualité meilleure quand ils produisent des flux à débit variable, qui sont les plus maltraités dans les réseaux IP.
L'introduction de flux vidéo dans le réseau IP se heurte donc à trois contradictions :
- augmenter la qualité des codages, conduit pour un débit moyen défini, à produire des rafales de paquets quand la séquence codée l'exige ;
- les réseaux d'accès offrent une bande passante maximale limitée (y compris en ADSL (« Asymétrie Digital Subscriber Line ») car les applications sont tentées d'exploiter un débit moyen proche du maximum pour procurer la meilleure qualité aux usagers ;
- les rafales sont les informations les plus importantes car elles correspondent à un changement de scène ou au moins à un changement important du contenu de l'image. Bien souvent, ces images sont du type I (Intra) dont la perte est très critique, car il devient impossible de reproduire les images suivantes, même si ces dernières sont correctement reçues. On présente maintenant les techniques connues de conditionnement de trafic visant à réduire les congestions dans les réseaux.
On notera tout d'abord que les travaux sur l'application de la mise en forme pour les flux MPEG dans les réseaux IP en se basant sur UDP et RTP comme protocoles de transport sont très rares. La majorité des travaux concernent les réseaux ATM
(« Asynchronous Transfer Mode ») et l'utilisation de TCP comme protocole de transport.
Les mécanismes de mise en forme et de conditionnement de trafic sont utilisés dans les réseaux IP à « qualité de service » (QoS). On peut notamment se reporter au document « Traffic Shaping for MPEG video transmission over next génération internet » (lissage de trafic pour la transmission de vidéo MPEG sur l'internet de prochaine génération), M.F Alan, M. Atiquzzaman, M.A. Karim. Dans ce document, le lissage de trafic (TS) est utilisé pour assurer la conformité des flux MPEG au TSPEC (« Traffic Spécifier » c'est-à-dire « spécification de trafic ») nécessaire à la réservation de ressources dans les réseaux « IntServ ». Pour les réseaux « DiffServ », le traitement se fait par agrégat de flux et donc sans trop se soucier des applications. Les algorithmes de lissage de trafic (TS) sont par contre largement utilisés au niveau du codage dans le but de contrôler le débit des codeurs. Ceci reste insuffisant pour maîtriser les flux au niveau réseau. L'utilisation de la mise en forme, par lissage de trafic (TS, pour « Traffic
Shaping ») ou contrôle des règles de trafic (ou TP, pour « Traffic Policing »), pour réduire la congestion dans le réseau peut améliorer d'une manière significative le niveau de « qualité de service » (QoS) que le réseau est capable de délivrer aux applications.
Le lissage (TS) lisse les rafales en « bufferisant » (c'est-à-dire en mettant en mémoire-tampon) les paquets concernés par l'excès de rafales dans les équipements de frontière du réseau. Il peut réduire la congestion à des niveaux acceptables, surtout que les algorithmes d'ordonnancement (« scheduler ») tels que CBQ (« Class Based Queuing » c'est-à-dire « gestion de files d'attente basées par classes de services ») ou bien PQ (« Priority Queuing » c'est-à-dire « gestion de files d'attentes par priorités ») ne sont pas capables de le faire. Utilisés seuls, ces mécanismes propagent les rafales dans le réseau.
Comme le lissage (TS), le contrôle des règles de trafic (TP) limite le débit du trafic au débit configuré. Mais au lieu de « bufferiser » les paquets comme le lissage (TS), les paquets non-conformes sont soit rejetés, soit remarqués pour diminuer leurs priorités. Le contrôle des règles de trafic (TP) ne lisse pas par conséquent le trafic mais il n'introduit pas de délai de « bufferisation » non plus.
Dans la majorité des architectures qui supportent la « qualité de service » (QoS), un contrat de service existe entre le fournisseur du service réseau (NSP, pour « Network Service Provider ») et le fournisseur de l'application (ASP, pour « Application Service Provider »). Dans les réseaux ATM, ce contrat est appelé « Contrat de trafic ». Dans les réseaux « DiffServ », les aspects de contractualisation sont traités dans le SLA (« Service Level Agreement ») et plus précisément dans le SLS (« Service Level Spécification »).
On connaît également le document suivant : RFC2475, « An Architecture for Differentiated Services » (une architecture pour des services différenciés), Décembre 1998. Il précise que les sources de trafic peuvent assurer les tâches de classification et de. conditionnement de trafic. En effet, le trafic peut être marqué avant de quitter le domaine source. Ce marquage initial est appelé « Initial Marking » ou « Pre-marking ». L'avantage du marquage initial est que les préférences et les besoins des applications peuvent être mieux pris en compte pour décider quels paquets doivent recevoir un meilleur traitement dans le réseau.
La prévention contre la surcharge d'une classe de service donnée n'est pas une tâche facile dans les réseaux « DiffServ ». En plus, en cas de surcharge dans une classe de service, il faut noter que tous les flux de cette classe de service souffrent d'une dégradation de la « qualité de service » (QoS). En plus, plusieurs mécanismes utilisés dans la mise en œuvre de « DiffServ » fonctionnent d'une façon moins efficace en présence des rafales. Le mécanisme RED (« Random Early Drop »), par exemple, est plus efficace lorsqu'il est appliqué à un trafic lissé, sinon ce sont les flux lissés qui sont pénalisés alors que les flux en rafales ne subissent pas une amélioration significative. Les flux MPEG sont caractérisés par le fait qu'ils présentent des rafales (nature
« bursty ») et par leur sensibilité aux pertes de paquets. Ces pertes causent une dégradation de la qualité subjective, mais il est très difficile de prévoir le niveau de cette dégradation suite à des pertes. Cette dégradation est fortement liée à la nature des informations transportées par les paquets perdus. Les mécanismes de correction d'erreurs sont utilisés lors du décodage pour palier aux pertes.
Gérer les flux MPEG dans le réseau, ou même dans les routeurs d'extrémité (ER, pour « Edge Router »), est une tâche compliquée. Le fournisseur du service réseau (NSP) n'est pas obligé de traiter différemment les flux MPEG. En plus, l'agrégat de trafic résultant de plusieurs flux audio-visuels est généralement difficile à décrire : - le processus d'arrivée de paquets est auto-similaire ;
- grande variation des données transportées par les paquets ; - la dynamique des protocoles.
Une solution consiste à marquer les paquets et à leur attribuer le niveau de « qualité de service » (QoS) approprié avant qu'ils quittent le domaine du fournisseur de service sur Internet (ISP, pour « Internet Service Provider »). La passerelle d'accès au média (MAG, pour « Media Access Gateway ») est par exemple responsable de cette tâche. Cette passerelle MAG gère le trafic selon le SLS spécifié. Cette approche facilite la négociation de SLA/SLS pour les services en mode continu (« Streaming ») et impose au client un profil de trafic bien particulier.
Parmi les techniques actuelles, la plus répandue pour contrôler le trafic est le mécanisme WRED (« Weighted Random Early Drop ») qui consiste en une perte de paquets aléatoire et différente en fonction du marquage des paquets. Ce mécanisme se base sur un taux de remplissage moyen de la file d'attente d'émission sur un lien d'un réseau. Mais cette technique introduit un caractère aléatoire des rejets de paquets, et le taux de remplissage de la file d'attente n'est pas optimisée. Selon les tailles des rafales et leur fréquence, ces rejets peuvent se produire pour un remplissage faible ou un remplissage très élevé de la file d'attente. Ce qui conduit d'une part à une sous utilisation de la file d'attente, et d'autre part à la réservation de taille mémoire conséquente pour la réalisation de cette file. Ce problème existe pour tout type d'application, et il est encore plus réel pour les flux audiovisuels en raison de leurs rafales importantes.
Pour détailler ce point, il est fondamental de remarquer tout d'abord que les rafales des flux vidéo sont imprévisibles, autant en taille qu'en durée, tout en garantissant un débit moyen sur une période de l'ordre d'une seconde. Cette fenêtre de calcul du débit moyen est beaucoup trop grande pour obtenir des tailles raisonnables des files d'attente associées. De fait, les routeurs réagissent en calculant les moyennes de remplissage sur une dizaine de paquets reçus, alors que certaines rafales peuvent largement dépasser les 20 paquets.
Ainsi, une succession de rafales peut aboutir à des rejets par saturation de la capacité de la file d'attente, inhibant le fonctionnement normal du mécanisme. A l'opposé, quand un trafic faible survient après une suite de rafales, la valeur moyenne peut rester temporairement anormalement élevée et des paquets sont rejetés alors que la file est pratiquement vide.
Le mécanisme WRED n'est donc pas adapté au contrôle de flux caractérisés par une valeur moyenne sur une durée fixe. L'invention a notamment pour objectif de pallier ces inconvénients de l'état de la technique et offrir une solution optimale en cas de congestion du réseau.
Plus précisément, l'un des objectifs de la présente invention est de fournir un procédé et un dispositif de contrôle de trafic permettant de contrôler des rafales et de lisser le trafic sur un ensemble de flux et/ou sous-flux associés à des niveaux de priorités.
En d'autres termes, un objectif de la présente invention est de fournir un procédé et un dispositif de contrôle de trafic permettant de protéger les informations importantes des rafales, afin d'apporter une solution à l'antinomie entre l'optimisation d'un flux (par exemple un flux vidéo) contenant des rafales et le lissage des rafales pour un transport de qualité dans le réseau.
L'invention a également pour objectif de fournir de tels procédé et dispositif qui soient simples à mettre en œuvre et peu coûteux.
Un autre objectif de l'invention est de fournir de tels procédé et dispositif permettant de proposer efficacement des contrats de trafic (SLA/SLS) entre opérateurs réseau et fournisseurs de services.
Ces différents objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints selon l'invention à l'aide d'un procédé de contrôle d'un trafic de paquets de données en entrée d'un réseau, le trafic comprenant N flux et/ou sous-flux associés chacun à un niveau de priorité, N > 2, chacun des paquets étant marqué avec le niveau de priorité associé au flux ou sous-flux auquel appartient ledit paquet, ledit procédé comprenant une étape de mise en œuvre d'un mécanisme de seau à jetons à N niveaux de fonctionnement avec N mémoires-tampons de jetons contenant chacune un nombre de jetons disponibles, les jetons de chacune des N mémoires-tampons de jetons étant utilisés pour traiter l'un des N niveaux de priorité, chacun des paquets étant accepté ou refusé selon qu'il est possible ou non de lui attribuer des jetons en fonction des jetons disponibles au moins dans la mémoire-tampon de jetons utilisée pour traiter le niveau de priorité dudit paquet.
Le principe général de l'invention consiste donc à utiliser un seau à jetons multi- niveau (MLTB, pour « Multi Layer Token Bucket ») pour rejeter les paquets en dehors d'un profil requis et caractérisé par les N niveaux de fonctionnement du seau à jetons multi-niveau. Chaque paquet subit un traitement selon un marquage correspondant à son niveau de priorité. Les paquets acceptés sont placés dans une file d'attente.
Le seau à jetons multi-niveau permet de traiter sélectivement et conjointement plusieurs niveaux de priorités de flux. Il est bien adapté à la caractérisation du trafic entre la taille des rafales en entrée et l'écoulement du trafic en sortie. On sait qu'en cas de congestion du réseau, il est illusoire de chercher de la bande passante disponible. Le réglage des paramètres du seau à jetons multi-niveau assure une relation entre les niveaux de priorité pour équilibrer les contraintes de fonctionnement entre les débits par niveaux de priorité et les rafales acceptables par le seau à jeton selon les contraintes des applications transportées. La caractérisation des paramètres des N jeux de paramètres du seau à jetons multi-niveau permet de nombreuses solution et peut s'adapter à peu près à tous les cas de fonctionnement :
- un cas extrême est le comportement avec N jeux de paramètres indépendants agissant comme des seaux à jetons indépendants ; - un autre cas extrême est la possibilité pour le niveau le plus prioritaire de prendre tous les jetons et d'aboutir à une rejet des paquets de tous les autres niveaux ;
- entre ces deux extrêmes, toutes les configurations sont possibles, autorisant plus ou moins de rafales ou plus ou moins de débit réservé par niveau. L'invention permet donc de traiter des rafales sur les niveaux les plus prioritaires, du fait qu'il existe pour chaque niveau de priorité une réserve disponible pour prévenir toute arrivée soudaine d'un ensemble de données qui ne doivent pas être rejetées.
On rappelle qu'un seau à jeton habituel ne possède qu'un seul niveau de fonctionnement (il dispose d'un unique jeu de paramètres) et traite donc tous les paquets indistinctement. En cas de congestion du réseau, les paquets sont donc rejetés indépendamment de leur niveau de priorité.
On notera que la présente invention est totalement compatible avec les flux IP « unicast » (à destinataire unique) et « multicast » (diffusés sélectivement). On notera également que la présente invention permet de transmettre dans une même classe de service plusieurs groupes de flux avec des priorités différentes. En particulier, l'invention permet de fournir un traitement adapté à un ou un groupe de flux vidéo (IPB ou hiérarchique) conformément à un profil de trafic contractualisé (SLS) par des valeurs caractéristiques de type seau à jeton. En effet, les paramètres facilement mesurables et adaptables d'un seau à jetons multi-niveau (MLTB) sont un moyen efficace de proposer des contrats de trafic (SLA/SLS) entre opérateurs réseau et fournisseurs de services. La présence d'informations prioritaires conduit à la spécification de ce seau. Les multiples déclinaisons de ce seau sont un moyen d'offrir des classes de services adaptées aux exigences des clients. Quelles que soient les applications, le profil de trafic fait intervenir les principaux éléments de caractérisation d'un flux dans un réseau : le débit et le délai. L'invention est donc un moyen de définir un contrat avec un compromis négocié entre le débit, la taille des rafales, et le délai de transmission.
Dans une première application avantageuse de l'invention, le trafic comprend N sous-flux correspondant chacun à un des N niveaux hiérarchiques d'un flux hiérarchique ou d'un agrégat de flux hiérarchiques.
Il s'agit par exemple d'un flux hiérarchique audio/vidéo comprenant les sous- flux suivants : un sous-flux audio, un sous-flux vidéo de base et un sous-flux vidéo de réhaussement. Dans une deuxième application avantageuse de l'invention, le trafic comprend N sous-flux correspondant chacun à un des N types d'images d'un flux multimédia ou d'un agrégat de flux multimédia.
Il s'agit par exemple d'un flux vidéo MPEG comprenant trois sous-flux correspondant aux trois types d'images I, P et B. Dans une troisième application avantageuse de l'invention, le trafic comprend N flux correspondant chacun à un des flux d'un multiplex d'au moins deux flux. Il s'agit par exemple d'un flux vidéo/audio multiplexe avec un flux TCP, sur un accès ADSL.
Avantageusement, le trafic comprend N flux et/ou sous-flux appartenant à une même classe de service. Ainsi, l'invention, grâce au seau à jetons multi-niveau, permet de transmettre dans une même classe de service plusieurs flux et/ou sous-flux avec des priorités différentes. On peut distinguer plusieurs classes de service, telles que par exemple la classe « streaming » (contenant des flux audio et vidéo, la classe « TCP prioritaire », la classe « Best Effort de réseau IP », ...) et utiliser un seau à jeton multi-niveau pour chaque classe. Chaque classe de service peut être définie par marquage des paquets, par l'adresse IP source ou destination des paquets, par le protocole utilisé pour les paquets, etc.
Préférentiellement, les paquets refusés sont jetés.
Les paquets refusés sont ceux qui ne sont pas conformes au profil de trafic défini par les paramètres des N niveaux de fonctionnement du seau à jetons multi-niveau.
Une autre option, moins performante mais qui rentre néanmoins dans le cadre de la présente invention, est de transmettre les paquets refusés après les avoir à nouveau marqués avec un niveau de priorité plus faible. Cette option présente toutefois l'inconvénient d'augmenter la probabilité de rejet de paquets dans les nœuds congestionnés du réseau.
Avantageusement, le réseau est de type IP ou équivalent.
Selon une caractéristique avantageuse, chacun des N niveaux de fonctionnement du mécanisme de seau à jetons est géré par un régulateur bi(rb bπi;), i G {1 à N}, avec : rj le débit nominal du régulateur ; - bn ; la taille maximale de la mémoire-tampon de jetons du régulateur ; bi(t) la valeur instantanée du remplissage de la mémoire-tampon de jetons du régulateur.
De façon préférentielle, les jetons des N mémoires-tampons de jetons sont partagés entre les N niveaux de priorité, un paquet de niveau de priorité i pouvant se voir attribuer des jetons d'une mémoire-tampon de jetons associée à un niveau de priorité j moins prioritaire lorsque les jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ne sont pas suffisants.
De cette façon, on favorise les rafales des niveaux les plus prioritaires.
Avantageusement, pour chaque niveau de priorité hormis le niveau de priorité le plus prioritaire, on garantit une quantité de jetons réservés exclusivement aux paquets possédant ledit niveau de priorité.
Ainsi, on garantit une ressource minimum pour chaque niveau de priorité, sans exclure un usage partiellement partagé des ressources (c'est-à-dire des jetons des différents niveaux de fonctionnement du seau à jetons multi-niveau). Dans un premier mode de réalisation particulier de l'invention, l'attribution de jetons à un paquet de niveau de priorité i est effectuée selon un mode discontinu par paquet et consiste à attribuer : soit des jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ; - soit des jetons disponibles dans une mémoire-tampon de jetons de niveau de priorité j moins prioritaire, lorsque les jetons disponibles dans la mémoire- tampon de jetons de niveau de priorité i ne sont pas suffisants.
Ainsi, dans le mode discontinu, un paquet ne peut se servir des ressources (jetons) que d'un seul niveau de fonctionnement du seau à jetons multi-niveau. Dans un second mode de réalisation particulier de l'invention, l'attribution de jetons à un paquet de niveau de priorité i est effectuée selon un mode continu par bit et consiste à attribuer : des jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ; et en complément des jetons disponibles dans au moins une mémoire-tampon de jetons de niveau de priorité j moins prioritaire, lorsque les jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ne sont pas suffisants.
En d'autres termes, dans le mode continu, un paquet peut se servir des ressources (jetons) de plusieurs niveaux de fonctionnement du seau à jetons multi-niveau à la fois.
De façon avantageuse, les paquets acceptés par le mécanisme de seau à jetons à N niveaux de fonctionnement sont placés dans une file d'attente. Ledit procédé comprend en outre une étape de mise en œuvre d'un mécanisme de seau à jetons à un seul niveau de fonctionnement avec une unique mémoire-tampon de jetons, de façon à prendre les paquets contenus dans la file d'attente et les envoyer sur le réseau en exécutant un lissage du trafic par limitation du débit instantané à une valeur acceptable par le réseau. Le seau à jetons à un seul niveau de fonctionnement (TBTS, pour « Token
Bucket Traffic Shaper ») permet donc de limiter les débits crêtes émis par l'équipement réseau supportant l'invention. Il réalise une temporisation des rafales quand elles dépassent le débit toléré dans le réseau.
On utilise par exemple une zone mémoire, dont l'entrée est gérée par le seau multi-niveau (contrôle des rafales) et dont la sortie est gérée par le seau à un seul niveau
(lissage de trafic).
L'invention concerne également un programme d'ordinateur comprenant des instructions de code de programme pour l'exécution des étapes du procédé tel que précité, lorsque ledit programme est exécuté sur un ordinateur. L'invention concerne aussi un dispositif de contrôle d'un trafic de paquets de données en entrée d'un réseau, le trafic comprenant N flux et/ou sous-flux associés chacun à un niveau de priorité, N > 2, chacun des paquets étant marqué avec le niveau de priorité associé au flux ou sous-flux auquel appartient ledit paquet, ledit dispositif comprenant des moyens de mise en œuvre d'un mécanisme de seau à jetons à N niveaux de fonctionnement avec N mémoires-tampons de jetons contenant chacune un nombre de jetons disponibles, les jetons de chacune des N mémoires-tampons de jetons étant utilisés pour traiter l'un des N niveaux de priorité, chacun des paquets étant accepté ou refusé selon qu'il est possible ou non de lui attribuer des jetons en fonction des jetons disponibles au moins dans la mémoire-tampon de jetons utilisée pour traiter le niveau de priorité dudit paquet.
De façon préférentielle, ledit procédé comprend des moyens de partage des jetons des N mémoires-tampons de jetons entre les N niveaux de priorité, un paquet de niveau de priorité i pouvant se voir attribuer des jetons d'une mémoire-tampon de jetons associée à un niveau de priorité j moins prioritaire lorsque les jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ne sont pas suffisants. Avantageusement, pour chaque niveau de priorité hormis le niveau de priorité le plus prioritaire, lesdits moyens de partage comprennent des moyens de garantie d'une quantité de jetons réservés exclusivement aux paquets possédant ledit niveau de priorité. L'invention concerne encore un équipement réseau comprenant un dispositif de contrôle tel que précité, ledit équipement réseau appartenant au groupe comprenant : des équipements réseau situés entre un réseau d'un fournisseur d'application ou de service et un réseau d'un fournisseur d'un service réseau, constituant ledit réseau en entrée duquel est effectué le contrôle d'un trafic de paquets de données ; - des routeurs compris dans des nœuds d'un réseau d'un fournisseur d'un service réseau, constituant ledit réseau en entrée duquel est effectué le contrôle d'un trafic de paquets de données
D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante d'un mode de réalisation préférentiel de l'invention, donné à titre d'exemple indicatif et non limitatif, et des dessins annexés, dans lesquels : la figure 1 présente un exemple d'architecture de réseaux dans laquelle peut être mis en œuvre le procédé de contrôle de trafic selon l'invention ; la figure 2 illustre un mode de réalisation particulier du procédé selon l'invention, mettant en œuvre deux fonctions, basées sur l'utilisation respectivement d'un seau à jetons multi-niveau et un seau à jetons à niveau unique ; la figure 3 illustre un régulateur gérant un niveau de fonctionnement du seau à jetons multi-niveau illustré sur la figure 2, ainsi que l'utilisation dans ce régulateur d'un paramètre Kj garantissant un minimum de ressource pour le niveau de priorité associé à ce régulateur ; la figure 4 illustre un exemple d'attribution de jetons dans le cas où le fonctionnement du seau à jetons multi-niveau est décrit avec des mémoires- tampons (buffers) indépendantes ; la figure 5 illustre un exemple d'attribution de jetons dans le cas où le fonctionnement du seau à jetons multi-niveau est décrit avec des mémoires- tampons (buffers) corrélées. L'invention concerne donc un procédé de contrôle d'un trafic de paquets de données en entrée d'un réseau. Le trafic est du type comprenant N flux et/ou sous-flux associés chacun à un niveau de priorité, avec N > 2. Chacun des paquets est marqué avec le niveau de priorité associé au flux ou sous-flux auquel il appartient. A titre d'exemple, l'invention permet de transmettre en priorité les informations essentielles d'un flux vidéo, ou de plusieurs flux vidéo regroupés dans un agrégat. Selon la nature du flux, cette distinction est par exemple possible soit par les images de type IBP (voir définition ci-dessus), soit par les n couches d'un flux hiérarchique. Si dans le premier cas le débit moyen des images I reste faible devant le débit global, dans le second cas l'information la plus importante et à protéger au maximum est définie par la fraction du débit global occupé par la couche de base, et pouvant représenter jusqu'à 50% du flux. En général, la couche de base est la seule à contenir les informations de références contenues dans les images I.
Dans un agrégat, toutes les données de même niveau de priorité subissent le même traitement. Par exemple, tous les flux de base ou toutes les images I sont traités comme un seul flux de débit plus important qu'une vidéo seule.
On présente maintenant, en relation avec la figure 1, un exemple d'architecture de réseaux dans laquelle peut être mis en œuvre le procédé de contrôle de trafic selon l'invention. Dans cet exemple, on considère le cas de fournisseurs de service (ISP, pour
« Internet Service provider ») offrant un service de transmission de vidéo en mode continu (« streaming »).
L'exemple d'architecture (simplifiée) illustrée sur la figure 1 comprend :
- un réseau IP de type « DiffServ » 1, géré par un opérateur réseau (aussi appelé fournisseur du service réseau, ou NSP (pour « Network service
Provider »)) et comprenant une pluralité de routeurs 2{ à 25 compris dans des nœuds du réseau IP ;
- deux réseaux de fournisseurs de service « streaming » 3 et 4, l'un comprenant deux serveurs 5 et 6, et l'autre un serveur 7. Chaque réseau de fournisseurs de service 3, 4 comprend en outre un équipement d'extrémité 8, 9 connecté à l'un des routeurs du réseau IP, appelé routeur d'extrémité (« edge routeur ») 2,, qui est chargé d'envoyer les données d'un serveur vers une artère principale d'un cœur de réseau IP ;
- deux terminaux clients 10 et 11, chacun connecté au réseau IP 1 par exemple via un lien ADSL 12, 13. On suppose qu'il existe deux contrats de trafic (symbolisés par les flèches référencées SLAl et SLA2 respectivement sur la figure 1) : l'un entre l'opérateur du réseau IP 1 et le fournisseur de service dont le réseau est référencé 3, et l'autre entre l'opérateur du réseau IP 1 et le fournisseur de service dont le réseau est référencé 4.
Le procédé selon l'invention est mis en œuvre dans un équipement réseau formant un conditionneur de trafic pour l'entrée dans le réseau IP 1. Cet équipement réseau peut être situé entre le réseau du fournisseur du service 3, 4 et le réseau IP 1 :
- soit dans l'un des équipements d'extrémité 8, 9 des réseaux de fournisseurs de service 3 et 4 ;
- soit dans le routeur d'extrémité 2, du réseau IP 1. L'équipement réseau implémentant le procédé selon l'invention peut également être tout routeur placé au niveau d'un point de congestion dans le réseau (en particulier pour tout accès à un lien ADSL).
On présente maintenant, en relation avec la figure 2, un mode de réalisation particulier du procédé selon l'invention. Il permet de protéger les informations importantes des rafales et apporter des solutions à l'antinomie entre l'optimisation d'un flux vidéo contenant des rafales et le lissage des rafales pour un transport de qualité dans le réseau.
Dans ce mode de réalisation particulier du procédé selon l'invention, le mécanisme d'ensemble forme un « conditionneur de trafic décentralisé multi-couche » appelé «MLDTC » (pour « Multi-Layers Decentralized Traffic Conditioner »). Il est constitué de deux fonctions exécutées séquentiellement :
- la première est appelée « MLTR » (pour « Multi-Layers Traffic Regulator ») du fait qu'elle forme un « régulateur de trafic multi-couche ». Elle assure le contrôle de rafales par niveau hiérarchique. Elle est basée sur la mise en œuvre d'un seau à jetons à N niveaux de fonctionnement (référencé 30), avec
N buffers (mémoires-tampons) de jetons virtuels. Chaque buffer de jetons correspond à un niveau hiérarchique. Chaque niveau de fonctionnement est défini par un jeu de paramètres (voir discussion détaillée ci-après). La fonction MLTR assure l'attribution de jetons en fonction de la priorité du paquet entrant et de la ressource disponible dans le buffer de jetons correspondant. Dans l'exemple de la figure 2, on a N = 3 et la représentation de trois seaux indique uniquement la distinction des trois jeux de paramètres
(il n'y a en réalité qu'un seul seau à trois niveaux de fonctionnement) ;
- la seconde est appelée « TBTS » (pour « Token Bucket Traffic Shaper ») du fait qu'elle est basée sur un algorithme de type seau à jetons à niveau unique (« Token Bucket ») (référencé 31) et exécute un lissage du trafic pour un écoulement régulier sur le réseau en limitant le débit instantané à une valeur acceptable par le réseau. La mémoire tampon de la fonction TBTS est de capacité raisonnable pour garantir un coût moindre des systèmes et un temps de transfert limité dans la fourniture de l'information à l'usager. La contrepartie de la taille finie est la limitation des rafales acceptées en entrée du réseau.
La fonction MLTR est adaptée à l'acceptation différentiée des rafales en fonction du niveau de priorité. Elle s'applique aux paquets IP (référencés 20 à 26 sur la figure 2) dont le champ DSCP (« Differentiated Services Code point ») est marqué soit par la source, soit par un système de classification. Chaque niveau de priorité i dispose de ses propres paramètres, pour un tampon unique, commun aux 3 niveaux, mais avec des niveaux d'acceptation des paquets de données variables. Ce mécanisme répond aux attentes d'un signal vidéo, car il ne traite pas uniformément toutes les informations. En effet, on rappelle qu'un codage MPEG aboutit à plusieurs niveaux d'informations qu'il convient de traiter différemment selon leur importance. L'objectif est de favoriser les rafales d'un niveau i par rapport à un niveau j, dont les informations sont moins importantes (j > i). Les paquets relatifs au niveau i ont alors la priorité pour exploiter les ressources disponibles.
Grâce à la fonction TBTS, le même débit moyen est obtenu pour des tailles de rafales différentes, et tenant compte de l'intervalle les séparant. Un tel mécanisme est bien adapté aux rafales des flux vidéo, qui sont variables, en raison de la grande diversité des contenus transportés (sports, actualités, paysages, ...).
On présente maintenant de façon détaillée un exemple de réalisation de la fonction MLTR, qui assure la régulation et le contrôle de rafales. Dans la suite de la description, on étudie à titre d'exemple le cas où cette fonction MLTR est basée sur un seau à jetons à trois niveaux de fonctionnement (N = 3).
Comme illustré sur la figure 3, chaque niveau de fonctionnement i du seau à jetons à trois niveaux de fonctionnement 30 est géré par un régulateur bj , bm;), i E {1, 2, 3}, avec : - le débit nominal de ce régulateur ;
- bmj la taille maximale du buffer de jetons de ce régulateur ;
- bj(t) la valeur instantanée du remplissage du buffer de jetons de ce régulateur. La taille du buffer de jetons (b impose une taille maximale pour les rafales pour chaque niveau. La tolérance d'un régulateur de niveau i vis-à-vis des rafales de grande taille dépend de la taille du buffer de jetons b; et du débit .
Les paquets conformes (c'est-à-dire ceux à qui il a pu être attribué des jetons par le seau multi-niveau 30) sont placés dans un buffer de paquets à émettre 28, qui forme un moyen de gestion d'une file d'attente. Si un nombre insuffisant de jetons est disponible dans le seau multi-niveau, les paquets sont alors considérés comme non- conformes et sont éliminés. Ils sont jetés dans la poubelle référencée 27. Une autre option est de transmettre ces paquets avec une priorité plus faible. Cependant, le nouveau marquage des paquets pour leur attribuer une priorité plus faible augmente la probabilité de rejet de paquets dans les nœuds congestionnés.
Pour favoriser les rafales des niveaux les plus prioritaires, les trois buffers de jetons, bl, b2 et b3 sont partagés entre les différents niveaux. En d'autres termes, un paquet de niveau de priorité i peut se voir attribuer des jetons d'un buffer de jetons associé à un niveau de priorité j moins prioritaire (j > i) lorsque les jetons disponibles dans le buffer de jetons de niveau de priorité i ne sont pas suffisants.
Cependant, à cause de ce principe d'emprunt, les paquets de niveau i risquent d'utiliser toutes les ressources en jetons des niveaux moins prioritaires j. Ceci peut empêcher de garantir le débit nominal au niveau j au profit du niveau i. Comme illustré sur la figure 3, la solution est de limiter cet emprunt par un paramètre Kj, propre au niveau j, et dont l'objectif est de protéger ce dernier des niveaux plus prioritaires en garantissant une quantité de ressources (jetons) réservées exclusivement aux paquets de niveau j. Par conséquent, le paramètre Kj garantit un seuil de remplissage des buffers de jetons au-dessous duquel les paquets d'un niveau plus prioritaire ne peuvent plus se servir. Le paramètre Kj du régulateur de niveau j est illustré sur la figure 3.
La valeur de Kj doit être choisie telle que bmj > Kj > MTU.
Ceci revient à garantir pour les paquets de niveau j le débit nominal et des rafales limitées par Kj. Le cas particulier où Kj est adapté à la taille utile d'un paquet sur le réseau (MTU (« Maximum Transfer Unit », c'est-à-dire « taille maximale d'une unité élémentaire de transfert ») pour un réseau IP) correspond à une garantie du débit nominal rj pour le niveau j mais sans garantie de rafales. Les ressources en jetons pourraient être utilisées par les niveaux plus prioritaires.
Les trois jeux de paramètres définissant les trois niveaux de fonctionnement du seau à jetons multi-niveau peuvent être décrits :
- soit par une représentation de trois buffers indépendants, avec un usage partagé des ressources entre les trois niveaux ;
- soit par une représentation cumulée des ressources faisant mieux ressortir les priorités entre les niveaux et les interdépendances de fonctionnement provenant du partage des ressources.
Toutefois, ces représentations sont identiques dans leur fonctionnement. On présente maintenant, en relation avec la figure 4, une description du fonctionnement du seau à jetons multi-niveau avec des buffers (mémoires-tampons) indépendants. Le rechargement des buffers de jetons est calculé pour chacun des trois niveaux au moment de l'arrivée d'un nouveau paquet, en fonction du temps le séparant du paquet précédent.
(Équation 1)
Figure imgf000022_0001
La prise en compte du paquet arrivant de niveau i et de taille P, est obtenue par l'algorithme suivant : (mode paquets)
(Équation 2)
Figure imgf000023_0001
La figure 4 est une représentation graphique de cet algorithme d'attribution de jetons dans le cas où le fonctionnement du seau à jetons multi-niveau est décrit avec des buffers indépendants. Elle montre l'usage possible des ressources bt, b2 et b3 pour chacun des niveaux. Les traits épais (référencés 41, 42 et 43) montrent le remplissage des buffers de jetons (c'est-à-dire le nombre de jetons disponibles) pour chacun des niveaux, et les flèches les ressources (c'est-à-dire les jetons) prises par les paquets entrants (PI, P2 ou P3) selon leur priorité.
On présente maintenant, en relation avec la figure 5, une description du fonctionnement du seau à jetons multi-niveau avec des buffers corrélés.
Le fonctionnement avec trois régulateurs indépendants
Figure imgf000023_0002
i G {1, 2, 3}, est équivalent au fonctionnement avec trois régulateurs dépendants Bi Ri,BMi ) avec :
- Biψ) la valeur instantanée du remplissage du buffer de jetons virtuel relatif aux paquets de niveau i ;
- BMj la taille maximale du buffer de jetons virtuel relatif aux paquets de niveau i.
Les tailles de buffers de jetons par niveau sont obtenus par : (Équation 3)
Figure imgf000024_0001
Ce mode implique que : Bl ≥ B2 ≥ B3
Le rechargement des buffers de jetons peut alors s'exprimer sous une forme équivalente à Equation 1 par :
Bx (t + B2 (t + T)= min[(b2 (t)+
Figure imgf000024_0004
min[(b3 (t)+
Figure imgf000024_0003
B3 (t + T ) = min[(&3 (t )+ r31 ) bm3 ]
(Équation 4)
Si on suppose que min[(ô1(t)+ r,.T')bmi.]= b,(t)+ r. , (Equation 4) devient
Bx{t + T)= bx (t)+ b2 (t)+ b3 (t)+ (rx + r2 + r3 )l B2(t + τ)= b2(ή+ b3(t)+ (r2 + r3 )T B3(t + T)≈ b3(t)+ r3.T
La figure 5 est une représentation graphique de l'algorithme d'attribution de jetons dans le cas où le fonctionnement du seau à jetons multi-niveau est décrit avec des buffers corrélés. Elle montre l'usage possible des ressources B,, B2 et B3 pour chacun des niveaux. De même que sur la figure 4, les traits épais (référencés 51, 52 et 53) montrent le remplissage des buffers de jetons (c'est-à-dire le nombre de jetons disponibles) pour chacun des niveaux, et les flèches les ressources (c'est-à-dire les jetons) prises par les paquets entrants (PI, P2 ou P3) selon leur priorité.
Si les équations du rechargement traduisent exactement le même comportement pour les deux approches, le choix de l'attribution des jetons aux paquets à l'arrivée peut se réaliser par deux alternatives :
- en mode discontinu (paquets): un paquet ne peut se servir que d'un seul régulateur ;
- en mode continu (bits): un paquet peut se servir de plusieurs régulateurs à la fois. Selon le fonctionnement en mode discontinu (paquets), la prise en compte de l'arrivée du paquet est obtenue par l'algorithme suivant :
Figure imgf000025_0001
Il est à noter que (Equation 2) et (Equation 5) sont équivalentes.
Dans ce mode de fonctionnement discontinu (paquets), un paquet est servi par les ressources du niveau correspondant au paquet (niveau i) ou d'un niveau moins prioritaire (niveau j). Il est à noter que ce fonctionnement n'est pas optimal, car un paquet entrant est rejeté même si la somme des ressources disponibles réparties sur les 3 niveaux est suffisante.
Selon le fonctionnement en mode continu (bits), la prise en compte de l'arrivée du paquet est obtenue par l'algorithme suivant : envoi;
Figure imgf000026_0001
A priori ce mode de fonctionnement continu (bits) est plus optimal que le mode discontinu (paquets). En effet, il permet une utilisation maximale de ressources propres du niveau avant de demander des ressources à un niveau moins prioritaire.
On présente maintenant de façon détaillée un exemple de réalisation de la fonction TBTS qui assure la mise en forme du trafic.
Le seau à jetons à niveau unique 31, sur lequel est basé cette fonction TBTS, est par exemple défini par les paramètres suivants :
- R, le débit moyen ;
- Rmax, le débit maximal à la sortie ;
- B(t), la valeur instantanée du remplissage du buffer de jetons (Bmax est la taille maximale du buffer de jetons) ;
- S, la valeur instantanée du remplissage du buffer de paquets 28 (Smax est la taille maximale du buffer de paquets 28) ; - T, le temps séparant l'arrivée de deux paquets consécutifs ;
- τ, la durée d'une rafale de paquets.
Les paquets conformes (c'est-à-dire ceux à qui il a pu être attribué des jetons par le seau à niveau unique 31) sont transmis alors que les paquets non-conformes sont retardés dans le buffer de paquets 28 pour les contenir dans l'enveloppe de trafic ciblé. La taille du buffer de paquets 28 est à manipuler avec précaution car elle peut induire un délai supplémentaire, qui doit rester raisonnable.
Le fonctionnement du seau à niveau unique 31 (et donc de la fonction TBTS) peut être décrit par les équations suivantes :
B(t + τ)= min[(B(t)+R.τ)Bm
L.ï ≤ L, + ϋ.τ →τ ≤ - 5raax
La prise en compte du paquet P; est obtenue par l'algorithme suivant :
Figure imgf000027_0001
Si on considère rmax, le débit maximal à la sortie de la fonction MLTR, l'évolution du remplissage du buffer de paquets 28 entre l'arrivée de deux paquets consécutifs peut être décrit par l'équation suivante :
S(t + τ)≤ S(t)-Bmm + (rmsx -R)T
et S(t)-R.T-Bmm ≤ S(t + τ)≤ S{t)+ (rmax -R)τ

Claims

REVENDICATIONS
1. Procédé de contrôle d'un trafic de paquets de données en entrée d'un réseau, le trafic comprenant N flux et/ou sous-flux associés chacun à un niveau de priorité, N > 2, chacun des paquets étant marqué avec le niveau de priorité associé au flux ou sous-flux auquel appartient ledit paquet, caractérisé en ce qu'il comprend une étape de mise en œuvre d'un mécanisme de seau à jetons à N niveaux de fonctionnement avec N mémoires-tampons de jetons contenant chacune un nombre de jetons disponibles, les jetons de chacune des N mémoires- tampons de jetons étant utilisés pour traiter l'un des N niveaux de priorité, chacun des paquets étant accepté ou refusé selon qu'il est possible ou non de lui attribuer des jetons en fonction des jetons disponibles au moins dans la mémoire-tampon de jetons utilisée pour traiter le niveau de priorité dudit paquet.
2. Procédé selon la revendication 1, caractérisé en ce que le trafic comprend N sous-flux correspondant chacun à un des N niveaux hiérarchiques d'un flux hiérarchique ou d'un agrégat de flux hiérarchiques.
3. Procédé selon la revendication 1, caractérisé en ce que le trafic comprend N sous-flux correspondant chacun à un des N types d'images d'un flux multimédia ou d'un agrégat de flux multimédia.
4. Procédé selon la revendication 1, caractérisé en ce que le trafic comprend N flux correspondant chacun à un des flux d'un multiplex d'au moins deux flux.
5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que le trafic comprend N flux et/ou sous-flux appartenant à une même classe de service.
6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce que les paquets refusés sont jetés.
7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que le réseau est de type IP ou équivalent.
8. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce que chacun des N niveaux de fonctionnement du mécanisme de seau à jetons est géré par un régulateur bj η, bπij), i E {1 à N}, avec : - r-, le débit nominal du régulateur ; birii la taille maximale de la mémoire-tampon de jetons du régulateur ; bj(t) la valeur instantanée du remplissage de la mémoire-tampon de jetons du régulateur.
9. Procédé selon l'une quelconque des revendications 1 à 8, caractérisé en ce que les jetons des N mémoires-tampons de jetons sont partagés entre les N niveaux de priorité, un paquet de niveau de priorité i pouvant se voir attribuer des jetons d'une mémoire-tampon de jetons associée à un niveau de priorité j moins prioritaire lorsque les jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ne sont pas suffisants.
10. Procédé selon la revendication 9, caractérisé en ce que, pour chaque niveau de priorité hormis le niveau de priorité le plus prioritaire, on garantit une quantité de jetons
(Kj) réservés exclusivement aux paquets possédant ledit niveau de priorité.
11. Procédé selon l'une quelconque des revendications 9 et 10, caractérisé en ce que l'attribution de jetons à un paquet de niveau de priorité i est effectuée selon un mode discontinu par paquet et consiste à attribuer : - soit des jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ; soit des jetons disponibles dans une mémoire-tampon de jetons de niveau de priorité j moins prioritaire, lorsque les jetons disponibles dans la mémoire- tampon de jetons de niveau de priorité i ne sont pas suffisants.
12. Procédé selon l'une quelconque des revendications 9 et 10, caractérisé en ce que l'attribution de jetons à un paquet de niveau de priorité i est effectuée selon un mode continu par bit et consiste à attribuer : des jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ; et en complément des jetons disponibles dans au moins une mémoire-tampon de jetons de niveau de priorité j moins prioritaire, lorsque les jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ne sont pas suffisants.
13. Procédé selon l'une quelconque des revendications 1 à 12, caractérisé en ce que les paquets acceptés par le mécanisme de seau à jetons à N niveaux de fonctionnement sont placés dans une file d'attente, et en ce que ledit procédé comprend en outre une étape de mise en œuvre d'un mécanisme de seau à jetons à un seul niveau de fonctionnement avec une unique mémoire-tampon de jetons, de façon à prendre les paquets contenus dans la file d'attente et les envoyer sur le réseau en exécutant un lissage du trafic par limitation du débit instantané à une valeur acceptable par le réseau.
14. Programme d'ordinateur, caractérisé en ce qu'il comprend des instructions de code de programme pour l'exécution des étapes du procédé selon l'une quelconque des revendications 1 à 3, lorsque ledit programme est exécuté sur un ordinateur.
15. Dispositif de contrôle d'un trafic de paquets de données en entrée d'un réseau, le trafic comprenant N flux et/ou sous-flux associés chacun à un niveau de priorité, N > 2, chacun des paquets étant marqué avec le niveau de priorité associé au flux ou sous-flux auquel appartient ledit paquet, caractérisé en ce qu'il comprend des moyens de mise en œuvre d'un mécanisme de seau à jetons à N niveaux de fonctionnement avec N mémoires-tampons de jetons contenant chacune un nombre de jetons disponibles, les jetons de chacune des N mémoires- tampons de jetons étant utilisés pour traiter l'un des N niveaux de priorité, chacun des paquets étant accepté ou refusé selon qu'il est possible ou non de lui attribuer des jetons en fonction des jetons disponibles au moins dans la mémoire-tampon de jetons utilisée pour traiter le niveau de priorité dudit paquet.
16. Dispositif selon la revendication 15, caractérisé en ce qu'il comprend des moyens de partage des jetons des N mémoires-tampons de jetons entre les N niveaux de priorité, un paquet de niveau de priorité i pouvant se voir attribuer des jetons d'une mémoire-tampon de jetons associée à un niveau de priorité j moins prioritaire lorsque les jetons disponibles dans la mémoire-tampon de jetons de niveau de priorité i ne sont pas suffisants.
17. Dispositif selon la revendication 16, caractérisé en ce que, pour chaque niveau de priorité hormis le niveau de priorité le plus prioritaire, lesdits moyens de partage comprennent des moyens de garantie d'une quantité de jetons (K,) réservés exclusivement aux paquets possédant ledit niveau de priorité.
18. Equipement réseau comprenant un dispositif de contrôle selon l'une quelconque des revendications 15 à 17, caractérisé en ce que ledit équipement réseau appartient au groupe comprenant : des équipements réseau situés entre un réseau d'un fournisseur d'application ou de service et un réseau d'un fournisseur d'un service réseau, constituant ledit réseau en entrée duquel est effectué le contrôle d'un trafic de paquets de données ; des routeurs compris dans des nœuds d'un réseau d'un fournisseur d'un service réseau, constituant ledit réseau en entrée duquel est effectué le contrôle d'un trafic de paquets de données.
PCT/FR2004/000955 2003-04-18 2004-04-16 Procede et dispositif de controle d’un trafic de paquets de donnees en entrée d’un reseau Ceased WO2004095783A2 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP04742535A EP1616414A2 (fr) 2003-04-18 2004-04-16 Procede et dispositif de controle d'un trafic de paquets de donnees en entree d'un reseau
US10/553,617 US7542417B2 (en) 2003-04-18 2004-04-16 Method and device for controlling data packet traffic at the input of a network, and corresponding computer program and network equipment

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0304903A FR2854018A1 (fr) 2003-04-18 2003-04-18 Procede et dispositif de controle d'un trafic de paquets de donnees en entree d'un reseau, programme d'ordinateur et equipement reseau correspondants
FR03/04903 2003-04-18

Publications (2)

Publication Number Publication Date
WO2004095783A2 true WO2004095783A2 (fr) 2004-11-04
WO2004095783A3 WO2004095783A3 (fr) 2005-01-06

Family

ID=33041984

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2004/000955 Ceased WO2004095783A2 (fr) 2003-04-18 2004-04-16 Procede et dispositif de controle d’un trafic de paquets de donnees en entrée d’un reseau

Country Status (4)

Country Link
US (1) US7542417B2 (fr)
EP (1) EP1616414A2 (fr)
FR (1) FR2854018A1 (fr)
WO (1) WO2004095783A2 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007128208A1 (fr) * 2006-04-24 2007-11-15 Huawei Technologies Co., Ltd. Dispositif d'accès, procédé et moyen de contrôle de largeur de bande assuré par le dispositif d'accès

Families Citing this family (42)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7545815B2 (en) * 2004-10-18 2009-06-09 At&T Intellectual Property Ii, L.P. Queueing technique for multiple sources and multiple priorities
JP4567433B2 (ja) * 2004-12-27 2010-10-20 ルネサスエレクトロニクス株式会社 ホスト装置、デバイス装置、通信システム及びデータ送受信方法
EP1847071A4 (fr) * 2005-01-26 2010-10-20 Internet Broadcasting Corp B V Multi-diffusion en couches et attribution exacte de largeur de bande et priorisation de paquets
US7609634B2 (en) * 2005-03-22 2009-10-27 Alcatel Lucent Communication traffic policing apparatus and methods
US20070127521A1 (en) * 2005-12-02 2007-06-07 The Boeing Company Interface between network data bus application and avionics data bus
US20070157316A1 (en) * 2005-12-30 2007-07-05 Intel Corporation Managing rogue IP traffic in a global enterprise
US9306852B2 (en) * 2006-01-27 2016-04-05 Avaya Inc. Coding and packet distribution for alternative network paths in telecommunications networks
US7817556B2 (en) * 2006-04-20 2010-10-19 Cisco Technology, Inc. Modification of policing methods to make them more TCP-friendly
ES2382108T3 (es) * 2006-07-27 2012-06-05 Contextream Ltd. Red de borde distribuida
US7826358B2 (en) * 2006-12-29 2010-11-02 Ellacoya Networks, Inc. Hierarchical virtual queuing
US7848237B2 (en) * 2007-01-18 2010-12-07 Ineoquest Technologies, Inc. System and method for selective packet discard for the transport of multiple transportation streams of streaming media in packet-based networks
US8670394B2 (en) 2007-08-14 2014-03-11 Qualcomm Incorporated Uplink requests
ATE445954T1 (de) * 2007-08-31 2009-10-15 Alcatel Lucent Verfahren zur steuerung einer paketstromübertragung
US8929372B2 (en) * 2007-10-30 2015-01-06 Contextream Ltd. Grid router
TWI351849B (en) * 2007-12-31 2011-11-01 Ind Tech Res Inst Apparatus and method for transmitting streaming se
US8467295B2 (en) * 2008-08-21 2013-06-18 Contextream Ltd. System and methods for distributed quality of service enforcement
US20100082353A1 (en) * 2008-09-29 2010-04-01 Apple Inc. Reward system for managing a digital workflow
US8000235B2 (en) * 2008-10-05 2011-08-16 Contextream Ltd. Bandwidth allocation method and apparatus
US8379516B2 (en) * 2009-12-24 2013-02-19 Contextream Ltd. Grid routing apparatus and method
US8813065B2 (en) 2010-04-26 2014-08-19 Vmware, Inc. Microcloud platform delivery system
US8572706B2 (en) 2010-04-26 2013-10-29 Vmware, Inc. Policy engine for cloud platform
US9448790B2 (en) 2010-04-26 2016-09-20 Pivotal Software, Inc. Rapid updating of cloud applications
US9772831B2 (en) 2010-04-26 2017-09-26 Pivotal Software, Inc. Droplet execution engine for dynamic server application deployment
US8904027B2 (en) 2010-06-30 2014-12-02 Cable Television Laboratories, Inc. Adaptive bit rate for data transmission
US9015710B2 (en) 2011-04-12 2015-04-21 Pivotal Software, Inc. Deployment system for multi-node applications
US9170798B2 (en) 2012-03-02 2015-10-27 Vmware, Inc. System and method for customizing a deployment plan for a multi-tier application in a cloud infrastructure
US9047133B2 (en) 2012-03-02 2015-06-02 Vmware, Inc. Single, logical, multi-tier application blueprint used for deployment and management of multiple physical applications in a cloud environment
US10031783B2 (en) 2012-03-02 2018-07-24 Vmware, Inc. Execution of a distributed deployment plan for a multi-tier application in a cloud infrastructure
US9052961B2 (en) 2012-03-02 2015-06-09 Vmware, Inc. System to generate a deployment plan for a cloud infrastructure according to logical, multi-tier application blueprint
US9348652B2 (en) 2012-07-02 2016-05-24 Vmware, Inc. Multi-tenant-cloud-aggregation and application-support system
US9148379B1 (en) 2013-01-09 2015-09-29 “Intermind” société à responsabilité limitée Method and system for prioritizing audio traffic in IP networks
CN104079499A (zh) * 2014-07-18 2014-10-01 福建星网锐捷网络有限公司 基于令牌桶的报文处理方法及装置
US20170104733A1 (en) * 2015-10-09 2017-04-13 Intel Corporation Device, system and method for low speed communication of sensor information
US9871610B2 (en) * 2015-10-30 2018-01-16 Citrix Systems, Inc. Method for packet scheduling using multiple packet schedulers
CA2944306C (fr) 2015-10-30 2023-11-14 The Toronto-Dominion Bank Validation de donnees chiffrees a partir d'un jeton multicouche
US11216808B2 (en) * 2015-11-04 2022-01-04 The Toronto-Dominion Bank Token-based system for excising data from databases
CA2943962C (fr) * 2015-11-05 2024-01-16 The Toronto-Dominion Bank Securisation des donnees au moyen de jetons multicouches
CN109729018B (zh) * 2017-10-30 2022-12-13 北京华为数字技术有限公司 基于流量整形的突发尺寸确定方法及相关设备
US10884815B2 (en) 2018-10-29 2021-01-05 Pivotal Software, Inc. Independent services platform
US12224942B2 (en) * 2020-03-05 2025-02-11 Nippon Telegraph And Telephone Corporation Network management systems, edge devices, network management devices, and programs
CN113938435B (zh) * 2021-08-30 2024-01-16 奇安信科技集团股份有限公司 数据传输方法、装置、电子设备、存储介质及程序产品
US20240232693A1 (en) * 2023-01-05 2024-07-11 Bank Of America Corporation System and method for electronic compliance evaluation of transmitted object data via a machine learning model

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6247061B1 (en) * 1998-06-09 2001-06-12 Microsoft Corporation Method and computer program product for scheduling network communication packets originating from different flows having unique service requirements
US6862265B1 (en) * 2000-04-13 2005-03-01 Advanced Micro Devices, Inc. Weighted fair queuing approximation in a network switch using weighted round robin and token bucket filter
AUPQ712500A0 (en) * 2000-04-27 2000-05-18 Commonwealth Scientific And Industrial Research Organisation Telecommunications traffic regulator
US6748435B1 (en) * 2000-04-28 2004-06-08 Matsushita Electric Industrial Co., Ltd. Random early demotion and promotion marker
US7095753B1 (en) * 2000-09-19 2006-08-22 Bbn Technologies Corp. Digital network processor-based multi-protocol flow control
EP1220493A1 (fr) * 2000-12-28 2002-07-03 Alcatel Appareil marqueur et procédé correspondant
US7382727B2 (en) * 2001-02-21 2008-06-03 Cisco Technology, Inc. System and method for asymmetrical bandwidth management
US6901050B1 (en) * 2001-03-05 2005-05-31 Advanced Micro Devices, Inc. Systems and methods for flow-based traffic shaping
US6925055B1 (en) * 2001-03-05 2005-08-02 Advanced Micro Devices, Inc. Systems and methods for traffic shaping
US7085236B2 (en) * 2002-05-20 2006-08-01 University Of Massachusetts, Amherst Active queue management for differentiated services
US7627675B2 (en) * 2003-05-01 2009-12-01 Cisco Technology, Inc. Methods and devices for regulating traffic on a network

Non-Patent Citations (5)

* Cited by examiner, † Cited by third party
Title
HUBERT, VAN MOOK ET ALL: "Linux Advanced Routing and Traffic control" INTERNET PUBLICATION, [Online] 22 juillet 2002 (2002-07-22), XP002255410 Extrait de l'Internet: URL:www.tldp.org/HOWTO/adv-routing-HOWTO/> [extrait le 2003-09-23] *
MARTIN DEVERA: "Hierarchical Token Bucket theory" INTERNET PUBLICATION, [Online] 5 mai 2002 (2002-05-05), XP002255408 Extrait de l'Internet: URL:luxik.cid.cz/~devik/qos/htb> [extrait le 2003-09-23] *
MARTIN DEVERA: "Issues regarding 2.4 kernels" INTERNET PUBLICATION, [Online] 2002, XP002255409 Extrait de l'Internet: URL:luxik.cid.cz/~devik/> [extrait le 2003-09-23] *
SAHA,MUKHERJEE, TRIPATHI: "Carry-over round robin: a simple cell scheduling mechanism for ATM networks" 1994 INTERNATIONAIEEE\SLASH ACM TRANSACTIONS ON NETWORKING, vol. 6, no. 6, 1998, pages 779-796, XP002255412 Boston,MA,USA *
SHREEDHAR, VARGHESE: "Efficient Fair Queuing using Deficit Round Robin" SIGCOMM 1995, [Online] août 1995 (1995-08), pages 231-242, XP002255411 Extrait de l'Internet: URL:citeseer.nj.nec.com> [extrait le 2003-09-23] *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007128208A1 (fr) * 2006-04-24 2007-11-15 Huawei Technologies Co., Ltd. Dispositif d'accès, procédé et moyen de contrôle de largeur de bande assuré par le dispositif d'accès

Also Published As

Publication number Publication date
EP1616414A2 (fr) 2006-01-18
US20070058548A1 (en) 2007-03-15
US7542417B2 (en) 2009-06-02
WO2004095783A3 (fr) 2005-01-06
FR2854018A1 (fr) 2004-10-22

Similar Documents

Publication Publication Date Title
EP1616414A2 (fr) Procede et dispositif de controle d'un trafic de paquets de donnees en entree d'un reseau
CN1293733C (zh) 用于传输具有不同质量的应用数据的方法
CN105164982B (zh) 通过指派丢弃优先级来管理流之间的带宽分配
US8971184B2 (en) Latency based random early discard for network packets
FR2850816A1 (fr) Dispositif et procede de commande de vitesse d'acheminement du trafic dans un reseau de telecommunications utilisant un compartiment fuyant a plusieurs seuils
US20130205002A1 (en) Wide area network optimization
US20020188732A1 (en) System and method for allocating bandwidth across a network
US20050013244A1 (en) System for actively controlling distributed applications
EP2504950B1 (fr) Controle d'admission pour abonnement de service
FR2854296A1 (fr) Procede et dispositif pour differenciation implicite de la qualite de service dans un reseau
US9270616B1 (en) Low-latency quality of service
Shin et al. Quality of service for internet multimedia
EP0874533A1 (fr) Procédé d'ordonnancement de paquets à pertes équitables
EP2103055B1 (fr) Procédé d'optimisation du partage d'une pluralité de ressources réseau entre une pluralité de flux applicatifs
EP3989494B1 (fr) Procédé d'agrégation et de régulation de messages via un canal de communication bidirectionnel contraint
EP1039761B1 (fr) Procédé de diffusion de paquets de données numériques par un ensemble de canaux
FR2867007A1 (fr) Procede de repartition de la ressource radio entre differentes classes de mobiles
FR3044503A1 (fr) Procedes de traitement de paquets de donnees, dispositif, produit programme d'ordinateur, medium de stockage et nœud de reseau correspondants.
Braun et al. Motivation and Basics
Rosen Quality of Service for IP Networks: In Theory and Practice
Heggi et al. A New Historical Based Policing Algorithm for IP Networks
Dong Efficient resource management in multimedia streaming networks
Kakadia et al. Enterprise Quality of Service (QoS)-Part I: Internals
Siekkinen T-110.5116 Computer Networks II Quality of Service
Zoi et al. A framework for the delivery of MPEG-4 interactive content over QoS aware IP networks

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): BW GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2004742535

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2004742535

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2007058548

Country of ref document: US

Ref document number: 10553617

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 10553617

Country of ref document: US