| 摘要 |
A system for scheduling unicast packets through an interconnection network having a plurality of input ports, a plurality of output ports, and a plurality of input queues, comprising unicast packets, at each input port is operated in nonblocking manner in accordance with the invention by scheduling at most as many packets equal to the number of input queues from each input port to each output port. The system is operated at 100% throughput, work conserving, fair, and yet deterministically thereby never congesting the output ports. The system performs arbitration in only one iteration, 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 another embodiment each output port also comprises a plurality of output queues and each packet is transferred to an output queue in the destined output port in nonblocking and deterministic manner and without the requirement of segmentation and reassembly of packets even when the packets are of variable size. In one embodiment the scheduling is performed in strictly nonblocking manner with a speedup of at least two in the interconnection network. In another embodiment the scheduling is performed in rearrangeably nonblocking manner with a speedup of at least one in the interconnection network. The system also offers end to end guaranteed bandwidth and latency for packets from input ports to output ports. In all the embodiments, the interconnection network may be a crossbar network, shared memory network, clos network, hypercube network, or any internally nonblocking interconnection network or network of networks.
|
