The Stability of a Flow Merge Point with Non-Interleaving Cut-Through Scheduling Disciplines

Cut-through switching has been used as a way to reduce network latency. In particular, with ATM, packets are broken up into fixed length cells, and each cell is forwarded without having to wait for the remaining cells of the packet. However, with the recent interest in VC-merging, packets from multiple virtual circuits are merged into a single virtual circuit on an output link. In this case, it is critical to retain the fundamental characteristic of ATM to not interleave cells of a packet with that of another. VC-merging arises often, as in the case of a multipoint-to-multipoint or multipoint-to-point connection. We examine the stability of policies for cut-through switching when VCs are merged. We consider a queueing model of a single VC merge point employing cut-through switching. We show that, if subunits of packets cannot be interleaved on the output link, a simple round-robin polling service discipline may make the merge point unstable. Instability means that the input queues have a tendency to build up infinitely even though the total input data rate is less than the output link capacity.