Patent EP-1690159-A2 (EP)
Title: Ordonnancement de paquets a unidiffusion de maniere non bloquante et deterministe
Inventor: KONDA VENKAT
IPC: G06F/
Filed: 2004-10-29
Abstract: L'invention concerne un système destiné à ordonnancer des paquets à unidiffusion à travers un réseau d'interconnexion, et comprenant r1 ports d'entrée, chaque port d'entrée possédant r2 files d'attente d'entrée, et r2 ports de sortie, chaque port de sortie possédant r1 files d'attente de sortie, le réseau d'interconnexion présentant une accélération d'au moins (I) avec s sous-réseaux, chaque sous-réseau comprenant au moins un premier lien interne connecté à chaque port d'entrée pour un total d'au moins r1 premiers liens internes, chaque sous-réseau comprenant en outre au moins un second lien interne connecté à chaque port de sortie pour un total d'au moins r2 seconds liens internes. Selon l'invention, ce système est mis en oeuvre de manière strictement non bloquante par réalisation d'un ordonnancement, au maximum r1 paquets dans chaque temps de commutation étant commutés dans au maximum r2 temps de commutation lorsque r1 ≤ r2, et au maximum r2 paquets dans chaque temps de commutation étant commutés dans au maximum r1 temps de commutation lorsque r2 ≤ r1, de manière déterministe et sans qu'il soit nécessaire de segmenter et réassembler les paquets. Le système peut également être mis en oeuvre avec un débit de 100 % de manière conservative et équitable mais aussi déterministe, ce qui permet d'éviter la congestion des ports de sortie. Ledit système n'exécute qu'une seule itération pour l'arbitrage, avec une accélération mathématique minimale dans le réseau d'interconnexion. Il fonctionne sans aucun problème de reclassement de paquets, sans mise en tampon interne de paquets dans le réseau d'interconnexion, et donc vraiment en mode 'à la volée' et distribué. Dans un mode de réalisation, le système est mis en oeuvre de manière strictement non bloquante avec seulement un sous-réseau et avec une vitesse de commutation double à travers le sous-réseau. Dans un autre mode de réalisation, le système est mis en oeuvre de manière non bloquante réarrangeable avec une accélération d'au moins (II) dans le réseau d'interconnexion. Selon l'invention, lorsque le nombre de ports d'entrée r1 est égal au nombre de ports de sortie r2, et lorsque r1 = r2 = r, le réseau d'interconnexion présentant une accélération d'au moins (III) est mis en oeuvre de manière strictement non bloquante et déterministe par réalisation d'un ordonnancement, au maximum r paquets dans chaque temps de commutation étant commutés dans au maximum r temps de commutation. En outre, avec une accélération d'au moins (IV) dans le réseau d'interconnexion, le système est mis en oeuvre de manière non bloquante réarrangeable et déterministe. Ce système offre également une bande passante et une latence garanties de bout en bout pour les paquets entre les ports d'entrée et les ports de sortie. Dans tous les modes de réalisation, le réseau d'interconnexion peut être un réseau crossbar, un réseau à mémoire partagée, un réseau de Clos, un réseau hypercubique ou n'importe quel réseau ou réseau de réseaux d'interconnexion non bloquant au niveau interne.