Brevet FR2845224A1 — publié le 20040402

i Dispositif ordonnanceur pour un système à ressources partagées asymétriquement La présente invention concerne un ordonnanceur, encore appelé discipline de service, pour un système comportant une pluralité de noeuds partageant une pluralité de ressources telles que des longueurs d'onde. Un tel système est par exemple un réseau en anneau de paquets optiques du type DBORN (Dual Bus Optical Ring Network). L'architecture de l'anneau est organisée autour d'un concentrateur et est constituée d'une pluralité de noeuds tels que des multiplexeurs d'insertion/extraction de 10 paquets optiques du type OPADM (Optical Packet Add/Drop Multiplexer), chaque noeud étant en communication avec le concentrateur. Ce réseau contient un bus d'écriture correspondant à une pluralité de longueurs d'onde dites montantes et un bus de lecture correspondant à une pluralité de longueurs d'onde descendantes. Les longeurs d'onde montantes et 15 descendantes qui sont le plus souvent multiplexées sur une même fibre, sont utilisées et donc partagées par les noeuds du réseau pour émettre et recevoir des paquets vers et depuis le concentrateur. Une pluralité de noeuds partage donc une même ressource telle qu'une longueur d'onde pour recevoir des paquets envoyés par le concentrateur assimilable à un noeud source. Cependant, pour tenir compte des spécificités de chacun de noeuds, tous les noeuds ne partagent pas nécessairement une même ressource. Ainsi, il se peut qu'une ressource soit partagée par une partie seulement des noeuds du réseau. Chacun des noeuds ne partageant pas les mêmes ressources que 25 les autres noeuds dans les mêmes proportions, on parle alors de ressources partagées asymétriquement. Une des fonctions des réseaux concerne la discipline de service c'est à dire le fait de déterminer, parmi une pluralité de files d'attente ou buffers, quel est le paquet associé à une file d'attente particulière qui doit être envoyé sur un noeud. Cette détermination est réalisée par un dispositif appelé ordonnanceur. La présente invention a pour objet un dispositif ordonnanceur, dit encore discipline de service, pour un système comportant une pluralité de 5 noeuds partageant asymétriquement une pluralité de ressources telles que des longueurs d'onde. La présente invention propose à cet effet un dispositif ordonnanceur pour ordonnancer la transmission de données à partir d'une pluralité de files d'attente d'un noeud source vers une pluralité de noeuds de destination via 10 une pluralité de ports de sortie dudit noeud source, chacun desdits ports de sortie étant associés à une ressource, les données étant transmises via ladite ressource vers un noeud de destination, chacun desdits noeuds recevant des données de tout ou partie de ladite pluralité de ressources, ledit dispositif ordonnanceur étant caractérisé en ce qu'il comporte une pluralité 15 de serveurs, chacun desdits serveurs étant associé respectivement à une ressource de ladite pluralité de ressources et chacun desdits serveurs comportant des moyens d'ordonnancement, lesdits moyens d'ordonnancement étant indépendants pour chacun desdits serveurs. Grâce à l'invention, chaque serveur fonctionne indépendamment des 20 autres serveurs et peut prendre en compte les spécificités de la ressource à laquelle il est associé et notamment le fait qu'une ressource ne soit pas partagée de façon uniforme par tous les noeuds de destination, chaque noeud utilisant ladite ressource suivant un certain coefficient de pondération. Ce coefficient de pondération peut être nul si le noeud n'utilise pas ladite 25 ressource. Il peut également être lui-même pondéré selon l'importance que prend ladite ressource pour le noeud de destination. Ainsi une ressource utilisée par un premier noeud et un deuxième noeud ne sera pas partagé de la même façon entre le premier noeud et le deuxième noeud si le premier noeud utilise davantage d'autres ressources que le deuxième noeud. Chaque 30 serveur peut par exemple prendre en considération une double pondération: une première pondération donnant une information sur l'utilisation de la ressource par le noeud et traduisant l'asymétrie du système et une deuxième pondération donnant une information sur le ratio d'utilisation de la ressource par le noeud en fonction du trafic à destination dudit noeud par rapport au trafic total. Selon un premier mode de réalisation, lesdits moyens d'ordonnancement comportent des moyens d'ordonnancement cyclique du type Round Robin. Les moyens d'ordonnancement Round Robin parcourent 10 séquentiellement et cycliquement des files d'attente de type FIFO (First In First Out) et servent la première file prête ou non vide. Si la file d'attente est vide, les moyens d'ordonnancement passent à la suivante. Certaines files peuvent être privilégiées en définissant un poids correspondant par exemple au nombre d'éléments ou paquets que peut prendre l'ordonnanceur en tête 15 de la file d'attente; on parle alors de Weighted Round Robin WRR. Selon un deuxième mode de réalisation, lesdits moyens d'ordonnancement comportent des moyens d'ordonnancement WFR (Weighted Fair Queueing). Cet algorithme donne un traitement prioritaire aux flux de faible 20 volume et permet aux flux de volume important d'utiliser la place qui reste. Pour cela, il trie et regroupe les paquets par flux, puis met ceux-ci en file d'attente suivant le volume de trafic dans chaque flux. Avantageusement, lesdits moyens d'ordonnancement sont dépendants d'un ensemble de pondérations statiques et/ou dynamiques. Les pondérations statiques peuvent par exemple être issues de procédés classiques de partition ou d'allocation des ressources. Les pondérations dynamiques peuvent être calculées sur la base d'informations de contrôle de congestion. Une combinaison de ces deux types de pondérations peut également être envisagée. Selon un mode de réalisation particulièrement avantageux, lesdits moyens d'ordonnancement sont dépendants d'un premier ensemble de pondérations, chacune desdites pondérations traduisant le pourcentage d'allocation de ladite ressource à chacun desdits noeuds de ladite pluralité de noeuds. Ce type de pondération est obtenu par des procédés classiques de partition ou d'allocation des ressources. De manière avantageuse, lesdits moyens d'ordonnancement sont dépendants d'un deuxième ensemble de pondérations, chacune desdites 10 pondérations traduisant le poids relatif du trafic de chacun desdits noeuds par rapport au trafic total. La présente invention a également pour objet un noeud comportant un dispositif ordonnanceur selon l'invention et incluant une pluralité de files d'attente pour l'émission de données vers une pluralité de noeuds de 15 destination et une pluralité de ports de sortie. La présente invention a en outre pour objet un système de transmission de données comportant au moins un noeud source selon l'invention, ledit système comportant: - une pluralité de noeuds de destination, - une pluralité de ressources. D'autres caractéristiques et avantages de la présente invention apparaîtront dans la description suivante d'un mode de réalisation de l'invention, donné à titre illustratif et nullement limitatif. Dans la figure suivante: - la figure unique représente schématiquement un système de transmission incorporant un dispositif ordonnanceur selon l'invention. La figure 1 représente schématiquement un système de transmission tel qu'un réseau en anneau de paquets optiques. Cette représentation est limitée à la description de l'invention, ledit système pouvant comporter de nombreux autres éléments. Le système 10 comporte: - un noeud source 1, - trois noeuds de destination N1, N2 et N3, - quatre ressources OR1, OR2, OR3 et OR4. Les ressources OR", OR2, OR3 et OR4 sont par exemple des longueurs d'onde multiplexées sur une fibre optique selon une technologie DWDM (Dense Wavelength Division Multiplex). Les noeuds N1, N2 et N3 sont par exemple des multiplexeurs OPADM (Optical Packet Add/Drop Multiplexer). Le noeud source 1 est par exemple concentrateur électronique tel qu'un commutateur Ethernet. Le noeud source I comprend - trois files d'attentes ou buffers B, B2 et B3 permettant de stocker des paquets avant de les émettre respectivement vers les noeuds Nl, N2 et N3, - un dispositif ordonnanceur 2 encore appelé discipline de service, - quatre ports de sortie P1, P2, P3 et P4. permettant d'émettre les paquets de données respectivement sur les ressources OR", OR2, OR3 et OR4. Le dispostif ordonnanceur 2 comprend quatre serveurs S1, S2, S3 et S4 associés chacun respectivement aux ressources OR", OR2, OR3 et OR4 et 25 aux ports P1, P2, P3 et P4. Chacun des quatre serveurs S", S2, S3 et S4 détermine quel est le paquet associé à une file d'attente particulière qui doit être envoyé sur un noeud via la ressource associée au serveur. Les ressources OR1 et OR2 sont partagées par les noeuds N1 et N2. 30 La ressource OR3 est partagée par les noeuds N2 et N3. La ressource OR4 est partagée par les noeuds N. et N3. Les ressources ne sont donc pas partagées uniformément par les noeuds N1, N2et N3. Ainsi, une même ressource utilisée par un premier noeud et un 5 deuxième noeud ne peut pas être utilisée de la même façon par le premier noeud utilisant davantage d'autres ressources que le deuxième noeud. Par exemple, le noeud N1 utilise les ressources OR,, OR2 et OR4 tandis que le noeud N3 utilise uniquement les ressources OR3 et OR4. Le noeud N. peut donc utiliser trois ressources pendant que le noeud N3 ne peut 10 en utiliser que deux. Le procédé d'allocation de ressources prend donc en compte cette allocation non uniformément répartie et attribue une pondération à chacun des noeuds correspondant au pourcentage d'allocation de ladite ressource à chacun desdits noeuds de ladite pluralité de noeuds. Cette pondération est 15 notée, de façon générale, Ri, et correspond au ratio alloué au noeud Ni sur la ressource OR. De plus, les noeuds de destination peuvent avoir des poids différents à cause de leurs trafics. Ainsi, en appelant Ti le trafic à destination du noeud Ni, chaque noeud peut être pondéré par un coefficient 20 WV égal à ( Ti / Zi Ti) o Zi T1 désigne la somme des trafics à destination de l'ensemble des noeuds. Ainsi, chacun des serveurs se voit attribuer une série de pondérations, dites méta-pondérations, pour chacun des noeuds en prenant en considération à la fois l'asymétrie du partage des ressources et 25 le trafic différent pour chacun des noeuds. Ces méta-pondérations sont résumées dans le tableau 1 cidessous et correspond au produit de R.. par WV. Serveurs / Noeuds NI N2 N3 s1 W1 xR1 W2xR21 W3xR31 s2 W1 x R12 W2 x R22 W3 x R32 s3 W1 x R13 W2 x R23 W3 x R33 | s4 JW1 x R14 |W2 x R24 |W3 x R34 Tableau 1 Chacun desdits serveurs utilise ces méta-pondérations et procède, 5 de façon indépendante des autres serveurs, à un mécanisme d'ordonnancement du type Round Robin, WRR (Weighted Round Robin) ou WFR (Weighted Fair Queueing) afin de sélectionner la file d'attente et le ou les paquets à émettre. Les serveurs peuvent inclure des moyens logiciels, matériels ou une combinaison des deux. Les pondérations telles qu'elles ont été décrites plus haut peuvent être mises à jour statiquement ou dynamiquement. Une mise à jour dynamique permet une adaptation dynamique de l'ordonnancement en prenant en compte la variation de charge en fonction du temps et de la destination. De plus, l'invention permet de préserver l'ordre des paquets en éliminant le besoin de mécanismes ou procédures complexes et coteuses pour palier à un déséquencement et pour réorganiser les paquets. Pour assurer la préservation de l'ordre des paquets, il suffit que le service des paquets respecte l'ordre établi grâce à un accès parallèle paquet par paquet 20 par les serveurs (et non par bloc). Bien entendu, l'invention n'est pas limitée au mode de réalisation qui vient d'être décrit. Notamment l'invention a été décrite dans le cadre d'un réseau de paquets optiques mais peut être généralisée à tout type de système utilisant 25 des ressources partagées de façon asymétrique tel qu'un système informatique comportant une pluralité d'unités de mémoire (files d'attente) connectées à une pluralité de processeurs (serveurs) via une pluralité de ressources (circuits électroniques) organisées en bus de lecture et d'écriture, le noeud source désignant un composant élémentaire comportant cette 30 pluralité d'unités de mémoire. De même, les mécanismes d'ordonnancement peuvent être différents de ceux décrits. En outre, l'invention a été décrite en relation avec un ensemble de pondérations traduisant le poids relatif du trafic de chacun des noeuds par 5 rapport au trafic total mais d'autres ensembles de pondérations peuvent être utilisés traduisant d'autres paramètres ou caractéristiques de chacun des noeuds, tels que les types de service et/ou d'utilisateur. REVENDICATIONS 1. Dispositif ordonnanceur (2) pour ordonnancer la transmission de données à partir d'une pluralité de files d'attente (B1, B2, B3) d'un noeud source (1) vers une pluralité de noeuds de destination (N1, N2, N3) via 5 une pluralité de ports de sortie (P1, P2, P3, P4) dudit noeud source (1), chacun desdits ports de sortie (P1, P2, P3, P4) étant associés à une ressource (OR1, OR2, OR3, OR4), les données étant transmises via ladite ressource vers un noeud de destination (N1, N2, N3), chacun desdits noeuds recevant des données de tout ou partie de ladite 10 pluralité de ressources (OR1, OR2, OR3, OR4), ledit dispositif ordonnanceur (2) étant caractérisé en ce qu'il comporte une pluralité de serveurs (S1, S2, S3, S4), chacun desdits serveurs étant associé respectivement à une ressource de ladite pluralité de ressources (OR1, OR2, OR3, OR4) et chacun desdits serveurs comportant des moyens 15 d'ordonnancement, lesdits moyens d'ordonnancement étant indépendants pour chacun desdits serveurs. 2. Dispositif ordonnanceur (2) selon la revendication I caractérisé en ce que lesdits moyens d'ordonnancement comportent des moyens d'ordonnancement cyclique du type Round Robin. 3. Dispositif ordonnanceur (2) selon la revendication 1 caractérisé en ce que lesdits moyens d'ordonnancement comportent des moyens d'ordonnancement WFR (Weighted Fair Queueing). 4. Dispositif ordonnanceur (2) selon l'une des revendications précédentes caractérisé en ce que lesdits moyens d'ordonnancement sont 25 dépendants d'un ensemble de pondérations statiques et/ou dynamiques. 5. Dispositif ordonnanceur (2) selon l'une des revendications précédentes caractérisé en ce que lesdits moyens d'ordonnancement sont dépendants d'un premier ensemble de pondérations, chacune desdites pondérations traduisant le pourcentage d'allocation de ladite ressource à chacun desdits noeuds de ladite pluralité de noeuds. 6. Dispositif ordonnanceur (2) selon la revendication précédente caractérisé en ce que lesdits moyens d'ordonnancement sont 5 dépendants d'un deuxième ensemble de pondérations, chacune desdites pondérations traduisant le poids relatif du trafic de chacun desdits noeuds par rapport au trafic total de la pluralité desdits noeuds. 7. Noeud (1) incluant un dispositif ordonnanceur (2) selon l'une des revendications précédentes comportant une pluralité de files d'attente 10 (B1, B2, B3) pour l'émission de données vers une pluralité de noeuds de destination (N1, N2, N3), et une pluralité de ports de sortie (P1, P2, P3, P4) 8. Noeud (1) selon la revendication précédente caractérisé en ce que lesdites données sont des paquets optiques. 9. Système (10) de transmission de données comportant au moins un noeud source (1) selon l'une des revendications 7 ou 8, ledit système (10) comportant: - une pluralité de noeuds de destination (N1, N2, N3), - une pluralité de ressources (OR1, OR2, OR3, OR4).