H - Electricity – 04 – L
Patent
H - Electricity
04
L
H04L 12/56 (2006.01) H04L 12/46 (2006.01) H04L 29/06 (2006.01)
Patent
CA 2544224
A system for scheduling multicast packets through an interconnection network, comprising r1 input ports with each input port having r2 input queues, r2 output ports with each output port having r1 output queues, and the interconnection network having a speedup of at least s with s subnetworks, and each subnetwork comprising at least one first internal link connected to each input port for a total of at least r1 first internal link, each subnetwork further comprising at least one second internal link connected to each output port for a total of at least r2 second internal links is operated in strictly nonblocking manner in accordance with the invention by scheduling, at most r1 packets in each switching time be switched in at most r2 switching times when r1.subseteq. r2, and at most r2 packets in each switching time to be switched in at most r1 switching times when r2.subseteq.r1, in deterministic manner, and without the requirement of segmentation and reassembly of packets. The scheduling is performed so that each multicast packet is fan-out split through not more than two interconnection networks and not more than two switching times. The system is also operated at 100 % throughout, work conserving, fair, and yet deterministically thereby never congesting the output ports. The system performs only one iteration for arbitration, and with mathematical minimum speedup in the interconnection network. The system operates with absolutely no packet reordering issues, no internal buffering of packets in the interconnection network, and hence in a truly cut-through and distributed manner. In one embodiment, the speedup is implemented with only one interconnection network and with triple switching rate through the interconnection network. In another embodiment, the system is operated in rearrangeably nonblocking manner with a speedup of at least s in the interconnection network. When the number of input ports r1 is equal to the number of output ports r2, and r1 = r2 = r, the interconnection network having a speedup of at least s, is operated in strictly nonblocking and deterministic manner in accordance with the invention by scheduling at most r packets in each switching time to be switched in at most r switching times. And with a speedup of at least s in the interconnection network, the system is operated in rearrangeably nonblocking and deterministic manner. The system also offers end to end guaranteed bandwidth and latency for multicast packets from input ports to output ports. In all the embodiments, the interconnection network may crossbar network, shared memory network, clos network, hypercube network, or any internally nonblocking interconnection network or network of networks.
L'invention concerne un système destiné à ordonnancer des paquets à multidiffusion à travers un réseau d'interconnexion, et comprenant r¿1? ports d'entrée, chaque port d'entrée possédant r¿2? files d'attente d'entrée, et r¿2? ports de sortie, chaque port de sortie possédant r¿1? 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 r¿1? 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 r¿2? 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 r¿1? paquets dans chaque temps de commutation étant commutés dans au maximum r¿2? temps de commutation lorsque r¿1? <= r¿2?, et au maximum r¿2? paquets dans chaque temps de commutation étant commutés dans au maximum r¿1? temps de commutation lorsque r¿2? <= r¿1?, de manière déterministe et sans qu'il soit nécessaire de segmenter et réassembler les paquets. L'ordonnancement est réalisé de sorte que chaque paquet à multidiffusion soit divisé en sortance à travers au maximum deux réseaux d'interconnexion et dans au maximum deux temps de commutation. 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, l'accélération est implémentée avec seulement un réseau d'interconnexion et avec une vitesse de commutation triple à travers le réseau d'interconnexion. 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 r¿1? est égal au nombre de ports de sortie r¿2?, et lorsque r¿1? = r¿2? = 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 de manière déterministe. Ce système offre également une bande passante et une latence garanties de bout en bout pour les paquets à multidiffusion 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.? ¿
Borden Ladner Gervais Llp
Konda Venkat
Teak Technologies Inc.
LandOfFree
Nonblocking and deterministic multicast packet scheduling does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Nonblocking and deterministic multicast packet scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonblocking and deterministic multicast packet scheduling will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1605834