Brevet FR2877173A1 — publié le 20060428

La présente invention concerne un procédé de planification de diffusions de contenus dans un milieu de transmission de données. Elle concerne également un dispositif mettant en oeuvre ce procédé et un support de données lisibles par ordinateur pour son exécution. Ce procédé est généralement mis en oeuvre dans un contexte de diffusions de contenus utilisant une infrastructure de diffusion de type Multicast, par exemple par satellite, grâce à laquelle plusieurs serveurs de diffusion se partagent les ressources d'un même milieu de transmission de données dont les capacités sont limitées. Par "contenu" on entend tout type de contenu numérique ou analogique: par exemple des données audio, vidéo et/ou alphanumériques. Une diffusion Multicast d'un contenu est une diffusion simultanée de ce contenu en direction d'un nombre limité mais non nécessairement prédéterminé de destinataires. Ce mode de diffusion a pour avantage de permettre de diffuser le contenu dans un même milieu de transmission de données en un unique flux pouvant atteindre l'ensemble des destinataires. Le milieu de transmission de données peut être utilisé pour transmettre plusieurs contenus devant être diffusés simultanément. Cependant il a une capacité maximale en général constante et exprimée en débit total maximal pouvant être transmis à chaque instant. Pour partager les ressources du milieu de transmission entre plusieurs terminaux clients désireux de diffuser des contenus, on prévoit un serveur de planification qui reçoit des requêtes de la part de ces terminaux. Chaque requête comporte des données permettant de déterminer un créneau temporel et un débit requis pour une diffusion de contenu. Un créneau temporel est une portion de temps limitée par un instant marquant le début et un instant marquant la fin du créneau. Ce serveur de planification peut mettre en oeuvre un procédé consistant à effectuer a priori une partition du milieu de transmission de données en un nombre prédéterminé de canaux de transmission, chaque canal étant associé à un débit, de telle sorte que la somme des débits des canaux soit égale à la capacité maximale du milieu de transmission de données. De façon classique, chaque canal du milieu de transmission peut prendre, dans un créneau temporel donné, l'un des deux états suivants: - un état disponible, indiquant qu'il n'y a pas de diffusion planifiée dans ce créneau temporel; et - un état occupé, indiquant qu'il y a au moins une diffusion planifiée dans au moins une partie de ce créneau temporel. Ainsi, le procédé de planification consiste à recevoir une requête de diffusion d'un contenu, puis à déterminer s'il reste un canal disponible dans le créneau temporel requis et dont le débit est supérieur au débit requis. Si c'est le cas, on planifie la diffusion requise dans le canal retenu, dans le créneau temporel et au débit requis. Si ce n'est pas le cas, la requête est rejetée. Ce procédé présente l'inconvénient de ne pas permettre d'allouer les canaux de façon optimale. En effet les débits associés aux canaux sont fixés à l'avance. Or, le débit requis pour la diffusion d'un contenu peut être inférieur au débit du canal qui lui est attribué, ce qui entraîne une sous-utilisation du canal attribué. Il n'est pas réaliste non plus d'imposer que les contenus soient diffusés à un débit commun prédéfini pour tous les canaux du milieu de transmission, sous prétexte d'optimiser l'allocation des canaux. Une amélioration de ce procédé consiste à ne pas définir a priori de canaux, mais à estimer la valeur maximale d'un débit total déjà planifié dans le milieu de transmission dans le créneau temporel requis, chaque fois que l'on reçoit une nouvelle requête de diffusion d'un contenu. Ainsi, on peut vérifier que le débit requis ajouté à cette valeur maximale ne dépasse jamais la capacité totale du milieu de transmission de données à l'intérieur du créneau temporel requis, avant d'accepter la requête et de planifier la diffusion correspondante. Une méthode connue pour estimer cette valeur maximale consiste à échantillonner le créneau temporel requis, à calculer le débit total déjà planifié dans le milieu de transmission à chaque instant de l'échantillonnage et à retenir la valeur maximale prise par les débits calculés aux instants de l'échantillonnage. Ainsi, plus l'échantillonnage est fin, plus l'estimation de la valeur maximale du débit total déjà planifié est précise. Cependant en contrepartie, plus l'échantillonnage est fin, plus le calcul est complexe et nécessite des ressources importantes. Pour simplifier le calcul, on peut limiter le nombre d'instants auxquels on calcule le débit total déjà planifié, mais cela rend plus incertaine l'estimation de la valeur maximale. L'invention vise à remédier à cet inconvénient en fournissant un procédé de planification de diffusions de contenus, basé lui aussi sur une estimation de la valeur maximale du débit total déjà planifié dans le milieu de transmission, qui augmente les chances d'obtenir une bonne estimation de cette valeur maximale tout en ne nécessitant pas de ressources trop importantes. L'invention a donc pour objet un procédé de planification de diffusions de contenus dans un milieu de transmission de données, comportant les étapes suivantes: - on reçoit une requête de diffusion d'un contenu, la diffusion étant à planifier dans ce milieu de transmission, la requête comportant des données permettant de déterminer un créneau temporel requis et un débit constant requis pour cette diffusion; - on estime la valeur maximale d'un débit total déjà planifié dans le milieu de transmission dans le créneau temporel requis, par le calcul d'au moins une valeur prise par ce débit total déjà planifié à au moins un instant compris dans ce créneau temporel requis; caractérisé en ce que l'instant auquel on calcule le débit total déjà planifié est: - l'instant marquant le début du créneau temporel requis, ou - un instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission. L'invention part du constat selon lequel, dans les applications de diffusions de contenus en mode Multicast, la capacité globale du milieu de transmission de données est en général constante et le débit requis dans la requête de diffusion d'un contenu est lui aussi constant. Ainsi, la fonction temporelle représentant le débit total déjà planifié dans le milieu de transmission au cours du temps est une fonction constante par morceaux. La valeur prise par cette fonction est susceptible d'augmenter uniquement à un instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifié dans le milieu de transmission. Par conséquent, la valeur maximale du débit total déjà planifié dans le milieu de transmission dans le créneau temporel requis est atteinte: - à l'instant marquant le début du créneau temporel requis, ou - à un instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission. Ainsi, en calculant le débit total déjà planifié à au moins l'un de ces instants, on augmente ses chances d'obtenir une bonne estimation de la valeur maximale, tout en limitant le nombre de calculs nécessaires pour y parvenir. De façon optionnelle, on calcule le débit total déjà planifié à l'instant marquant le début du créneau temporel requis et à chaque instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission. En effet, le calcul du débit total déjà planifié à chacun de ces instants est nécessaire et suffisant pour obtenir de façon certaine la vraie valeur maximale du débit total déjà planifié. Dans un mode de réalisation particulier, le procédé de planification comporte ensuite une étape de traitement de la requête lors de laquelle on vérifie que la valeur maximale estimée du débit total déjà planifié ajoutée au débit requis est inférieure à une capacité maximale du milieu de transmission. Lorsque cette condition est vérifiée, on accepte la requête et on planifie la diffusion correspondante dans le milieu de transmission de données. Sinon on rejette la requête. On notera que la capacité maximale du milieu de transmission peut prendre une valeur constante, ou bien variable dans le temps mais connue. De préférence, la requête comporte des données indiquant les instants marquant le début et la fin du créneau temporel requis, et le débit requis pour cette diffusion. En effet, ces données sont les données pertinentes pour la mise en oeuvre du procédé de planification. Elles permettent de déduire immédiatement sans calcul supplémentaire le créneau temporel et le débit de la diffusion requise. L'invention a également pour objet un support de données lisibles par un ordinateur, comportant des instructions pour l'exécution d'un procédé de planification de diffusions de contenus tel que décrit précédemment. Ce support de données peut être un support matériel de stockage, par exemple un CD-ROM, une disquette magnétique ou un disque dur, ou bien un support transmissible tel qu'un signal électrique, optique ou radio. L'invention a également pour objet un dispositif de planification de diffusions de contenus dans un milieu de transmission de données, comportant: - des moyens de réception d'une requête de diffusion d'un contenu, la diffusion étant à planifier dans ce milieu de transmission, des moyens de détermination d'un créneau temporel requis et d'un débit constant requis pour cette diffusion à partir de données contenues dans la requête; - des moyens d'estimation de la valeur maximale d'un débit total déjà planifié dans le milieu de transmission dans le créneau temporel requis, par le calcul d'au moins une valeur prise par ce débit total déjà planifié à au moins un instant compris dans ce créneau temporel requis, caractérisé en ce les moyens d'estimation comportent des moyens de calcul du débit total déjà planifié : - à l'instant marquant le début du créneau temporel requis, ou - à un instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission. De façon optionnelle, un dispositif de planification de diffusions de contenus selon l'invention comporte des moyens de vérification que la valeur maximale du débit total déjà planifié ajoutée au débit requis est inférieure à une capacité maximale du milieu de transmission. L'invention sera mieux comprise à l'aide de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins annexés dans lesquels: - la figure 1 représente schématiquement la structure générale d'une installation comportant un dispositif de planification de diffusions de contenus selon l'invention; - la figure 2 illustre une application concrète de diffusions de contenus à planifier à l'aide d'un procédé selon l'invention; et - la figure 3 représente les étapes successives d'un procédé de planification de diffusions de contenus selon l'invention. L'installation représentée sur la figure 1 comporte un groupe 10 de terminaux clients, chaque terminal client étant adapté pour l'émission de requêtes de diffusion de contenu dans un milieu 12 de transmission de données, en fonction d'une bande passante qui lui est allouée. Ce milieu de transmission 12 est par exemple un conduit associé à une capacité maximale de transmission de données, ce conduit étant par exemple matérialisé par un gestionnaire de bande passante satellite allouée pour le groupe 10 de terminaux clients. Il gère les requêtes émises par le groupe 10 de terminaux clients qui lui sont rattachés. Plus précisément, le milieu de transmission 12 comporte un serveur d'accès 14 adapté pour recevoir les requêtes en provenance des terminaux clients du groupe 10. Ce serveur d'accès constitue l'interface entre ces terminaux clients et un serveur 16 de planification de diffusions de contenus dans le milieu de transmission 12. Le serveur de planification 16 est adapté pour la mise en oeuvre d'un procédé de planification de diffusions de contenus selon l'invention. Les diffusions de contenus planifiées par le serveur 16 sont ensuite réparties, par un serveur 18 de répartition des flux, entre une pluralité de serveurs 20 de diffusion de ces flux. La somme des capacités des serveurs de diffusion de flux est égale à la capacité maximale du milieu de transmission 12, c'est-à-dire qu'elle correspond à sa bande passante satellite allouée. Le milieu de transmission 12 peut en outre être géré par un opérateur, à l'aide d'au moins un serveur 22, éventuellement distant. Pour remplir sa fonction de planification des diffusions de contenus dans le milieu de transmission 12, le serveur de planification 16 comporte des moyens 24 de réception d'une requête de diffusion d'un contenu émise par l'un des terminaux clients du groupe 10. Il comporte en outre des moyens 26 de détermination d'un créneau temporel et d'un débit requis pour cette diffusion à partir de données contenues dans la requête, et des moyens 28 d'estimation de la valeur maximale d'un débit total déjà planifié dans le milieu de transmission dans le créneau temporel requis. Il réalise cette estimation grâce à l'accès des moyens d'estimation 28 à une base de données 30 qui conserve en mémoire les créneaux temporels et les débits requis des diffusions déjà planifiées dans le milieu de transmission 12. Enfin, le serveur de planification comporte des moyens 32 de vérification que la valeur maximale estimée du débit total déjà planifié ajoutée au débit requis est toujours inférieure à la capacité maximale du milieu 12 de transmission dans le créneau temporel requis. Dans un mode de réalisation préféré de l'invention, une requête comporte des données indiquant les instants marquant le début et la fin de la diffusion à planifier, et le débit requis pour cette diffusion. Le couple constitué de l'instant marquant le début de la diffusion et de l'instant marquant la fin de la diffusion définit le créneau temporel requis. On a représenté sur la figure 2 un exemple concret d'un ensemble de diffusions de contenus dans le milieu de transmission 12, dont certaines sont déjà planifiées et dont l'une est à planifier. Une première requête R1 de diffusion déjà planifiée est définie par un débit d1, un instant de début hd1, un instant de fin hf1, ainsi que par un contenu à diffuser. De même, des requêtes R2, R3, R4 et R5 de diffusions déjà planifiées sont définies respectivement par des débits d2, d3, d4, d5, des instants de début hd2, hd3, hd4, hd5 et des instants de fin hf2, hf3, hf4, hf5, ainsi que par des contenus à diffuser. Enfin, une requête R de diffusion à planifier est définie par un débit d, un instant de début hd, un instant de fin hf, ainsi que par un contenu à diffuser. Le premier diagramme temporel de la figure 2 situe les différentes diffusions planifiées et à planifier les unes par rapport aux autres dans le temps (en abscisse) et dans la limite de la capacité maximale du milieu de transmission 12 (en ordonnée). Dans cet exemple: hdl Comme cela est visible sur le deuxième diagramme temporel de la figure 2, à chaque instant on peut calculer la valeur de la somme des débits déjà planifiés dans le milieu de transmission 12 et la valeur du débit requis d. Pour que la diffusion requise puisse être transmise dans le milieu de transmission de données 12 dans le créneau temporel requis, il faut que dans ce créneau temporel la somme des débits des diffusions déjà planifiées ajoutée au débit requis soit toujours inférieure à la capacité maximale du milieu de transmission 12. Puisque les débits des diffusions déjà planifiées sont constants entre le début et la fin de leurs créneaux temporels respectifs, la fonction qui donne la valeur de la somme des débits des contenus déjà planifiés au cours du temps est une fonction constante par morceaux qui atteint nécessairement son maximum dans le créneau temporel requis [hd, hf] à l'un des instants suivants: - l'instant marquant le début du créneau temporel requis, ou - un instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission 12. Ainsi, dans l'exemple représenté sur le premier diagramme de la figure 2, cette fonction atteint son maximum dans le créneau temporel requis à l'un des instants 15 suivants: - l'instant hd marquant le début du créneau temporel requis de la requête R; - l'instant hd4 marquant le début du créneau temporel de diffusion du contenu de la requête R4; - l'instant hd3 marquant le début du créneau temporel de diffusion du 20 contenu de la requête R3; - l'instant hd2 marquant le début du créneau temporel de diffusion du contenu de la requête R2. Les requêtes R1 et R5 concernent des diffusions de contenus dont le début est prévu à des instants antérieurs ou postérieurs au créneau temporel requis de la 25 requête R. La requête R1 a un instant de début de diffusion antérieur au début du créneau temporel requis. Son éventuelle contribution au débit total déjà planifié dans le créneau requis est prise en compte dans le calcul à l'instant hd marquant le début du créneau temporel requis de la requête R. La requête R5 a un instant de début de diffusion postérieur à la fin du créneau temporel requis. Elle n'apporte par conséquent aucune contribution au débit total déjà planifié dans le créneau requis. En fait, on remarque que le maximum atteint par la fonction temporelle donnant le débit planifié dans le milieu de transmission 12 est dans le cas de notre exemple atteint à l'instant hd2. En conclusion, on remarque qu'il est nécessaire et suffisant de calculer la valeur de la fonction donnant la somme des débits déjà planifiés aux instants hd, hd4, hd3 et hd2, pour connaître la valeur exacte du maximum atteint dans le créneau temporel [hd, hf]. En limitant le calcul à ces instants précis, on limite les ressources sollicitées sans pour autant prendre le risque d'aboutir à une mauvaise estimation. Ainsi, d'une façon générale, pour décider de satisfaire ou non à la requête R, il 5 est nécessaire et suffisant de vérifier que les fonctions booléennes suivantes sont vraies: débit(hd) + d 5 d max et 11 (débit(hdj) + d d max), MIE M d,hf) avec: - dmax, la capacité maximale du milieu de transmission 12; E (hd, hf), l'ensemble des instants marquant le début d'une diffusion 10 déjà planifié compris entre hd et hf; - débit(t) = di.D(t, hdi, hfi) ; si tE [hd, hf] 0 sinon - l'indice i balayant un ensemble de n diffusions planifiées. Un procédé de planification mis en oeuvre par le serveur de planification 16 pour parvenir à ce résultat va maintenant être décrit en référence à la figure 3. Lors d'une première étape 100, on reçoit la requête R de diffusion d'un contenu à planifier dans le créneau temporel [hd, hf] au débit requis d. Ensuite, lors d'une étape 101, on calcule la bande passante occupée dans le milieu de transmission 12 à l'instant hd de début de la diffusion requise. Pour cela, on calcule la valeur du débit total déjà planifié à cet instant dans le milieu de transmission 12. Ce débit total déjà planifié est égal à la somme des débits des diffusions déjà planifiées et en cours dans le milieu de transmission 12 à l'instant hd. On lui ajoute le débit requis d. Lors de l'étape de test 102 suivante, on teste si le résultat calculé à l'étape précédente est inférieur à la capacité maximale du milieu de transmission 12: Débit(hd) + d d max ? Si c'est le cas, on passe à une étape 104 lors de laquelle on extrait l'ensemble des valeurs des instants de début de diffusions déjà planifiées dans le milieu de transmission 12: hdl, hd2, hd3, hd4 et hd5. On définit une constante n, égale au nombre de diffusions déjà planifiées dans le milieu de transmission 12 (n = 5) et on initialise une variable i à la valeur 1. - D(t,hd,hf)= Puis, on sélectionne l'instant hdi lors d'une étape 106. Lors de l'étape de test 108 suivante, on vérifie si hdi appartient à l'intervalle de temps [hd, hf]. Si c'est le cas on passe à une étape 110 lors de laquelle on calcule la bande passante occupée dans le milieu de transmission 12 à l'instant hdi. Pour cela, on calcule la valeur du débit total déjà planifié à cet instant qui est la somme des débits de diffusions déjà planifiées et en cours à l'instant hdi dans le milieu de transmission 12 et on lui ajoute le débit requis d. Lors de l'étape de test 112 suivante, on teste si le résultat calculé à l'étape précédente est inférieur à la capacité maximale du milieu de transmission 12: Débit(hdi) + d d max ? Si c'est le cas, on passe à une étape 114 lors de laquelle on incrémente l'indice i d'une unité. On passe également directement à l'étape 114 sans passer par les étapes 110 et 112 si, lors de l'étape de test 108, on constate que hdi n'appartient pas à l'intervalle de temps [hd, hf]. Ensuite, lors d'une étape de test 116, si i On passe également directement à l'étape 118 sans passer par les étapes 104, 106, 108, 110, 112, 114 et 116 si, lors de l'étape de test 102, on constate que le résultat calculé à l'étape 101 est supérieur à la capacité maximale du milieu de transmission 12. Dans ce cas, on peut considérer que ce résultat est pris comme estimation de la valeur maximale du débit total déjà planifié dans le milieu de transmission 12 dans le créneau temporel requis. Il n'est en effet pas utile de déterminer la valeur maximale exacte du débit total puisqu'elle sera de toute façon supérieure à ce résultat, et donc a fortiori supérieure à la capacité maximale du milieu de transmission 12. Enfin, on passe également directement à l'étape 118 sans passer par les étapes 114 et 116 si, lors de l'étape de test 112, on constate que le résultat calculé à l'étape 110 est supérieur à la capacité maximale du milieu de transmission 12. Dans ce cas également, on peut considérer que ce résultat est pris comme estimation de la valeur maximale du débit total déjà planifié dans le milieu de transmission 12 dans le créneau temporel requis. Lors de l'étape 118 de fin de procédé, on prend une décision sur la requête de diffusion R. Si on est directement passé à cette étape 118 à l'issue de l'étape de test 102 ou 112, on refuse la requête et on ne planifie pas la diffusion du contenu requise. En revanche, si on est passé à l'étape 118 à l'issue de l'étape de test 116, cela signifie que la valeur maximale du débit total déjà planifié, qui est égale à l'une des valeurs calculées lors des étapes 101 ou 110, ajoutée à la valeur du débit requis, est toujours inférieure à la capacité du milieu de transmission 12 dans le créneau temporel requis. Dans ce cas, on accepte la requête et on planifie la diffusion requise dans le créneau temporel requis. Il apparaît clairement qu'un procédé de planification de diffusion de contenus selon l'invention permet de prendre une décision de rejet ou d'acceptation d'une requête de diffusion d'un contenu sur la base d'une estimation convenable de la valeur maximale d'un débit total déjà planifié dans le milieu de transmission, tout en sollicitant le moins possible les capacités de calcul du serveur de planification. La pertinence de la décision n'est pas affectée par la simplicité du calcul. REVENDICATIONS 1. Procédé de planification de diffusions de contenus dans un milieu (12) de transmission de données, comportant les étapes suivantes: - on reçoit (100) une requête de diffusion d'un contenu, la diffusion étant à planifier dans ce milieu de transmission, la requête comportant des données permettant de déterminer un créneau temporel requis et un débit constant requis pour cette diffusion; - on estime la valeur maximale d'un débit total déjà planifié dans le milieu de transmission dans le créneau temporel requis, par le calcul (101, 110) d'au moins une valeur prise par ce débit total déjà planifié à au moins un instant compris dans ce créneau temporel requis, caractérisé en ce que l'instant auquel on calcule le débit total déjà planifié est: - l'instant marquant le début du créneau temporel requis, ou - un instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission. 2. Procédé de planification de diffusions de contenus selon la revendication 1, dans lequel on calcule (101, 110) le débit total déjà planifié à l'instant marquant le début du créneau temporel requis et à chaque instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission. 3. Procédé de planification de diffusions de contenus selon la revendication 1 ou 2, dans lequel on vérifie (102, 112) ensuite que la valeur maximale estimée du débit total déjà planifié ajoutée au débit requis est inférieure à une capacité maximale du milieu de transmission. 4. Procédé de planification de diffusions de contenus selon l'une quelconque des revendications 1 à 3, dans lequel la requête comporte des données indiquant les instants marquant le début et la fin du créneau temporel requis, et le débit requis pour cette diffusion. 5. Support de données lisibles par un ordinateur, comportant des instructions pour l'exécution d'un procédé de planification de diffusions de contenus selon l'une quelconque des revendications 1 à 4. 6. Dispositif (16) de planification de diffusions de contenus dans un milieu (12) de transmission de données, comportant: - des moyens (24) de réception d'une requête de diffusion d'un contenu, la diffusion étant à planifier dans ce milieu de transmission, - des moyens (26) de détermination d'un créneau temporel requis et d'un débit constant requis pour cette diffusion à partir de données contenues dans la requête; - des moyens (28) d'estimation de la valeur maximale d'un débit total déjà planifié dans le milieu de transmission dans le créneau temporel requis, par le calcul d'au moins une valeur prise par ce débit total déjà planifié à au moins un instant compris dans ce créneau temporel requis, caractérisé en ce que les moyens d'estimation comportent des moyens de calcul du débit total déjà planifié : - à l'instant marquant le début du créneau temporel requis, ou - à un instant marquant le début d'un créneau temporel de diffusion d'un contenu déjà planifiée dans le milieu de transmission. 7. Dispositif (16) de planification de diffusions de contenus selon la revendication 6, comportant des moyens (32) de vérification que la valeur maximale estimée du débit total déjà planifié ajoutée au débit requis est inférieure à une capacité maximale du milieu de transmission.