The stability of a flow merge point with non-interleaving cut-through scheduling disciplines

Alexander L. Stolyar, K. K. Ramakrishnan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 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. We prove that the round-robin discipline is stable if the merge point is symmetric in that packet rates on all input VCs are equal (or at least "almost equal"). We also prove that two simple modifications of the round-robin discipline make the merge point always stable. Simulation results of one of the modifications show improved performance over "pure" cut-through and store-and-forward, at least in some cases.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM'99
Subtitle of host publicationThe Conference on Computer Communications - 18th Annual Joint Conference of the IEEE Computer and Communications Societies: The Future is Now
Pages1231-1238
Number of pages8
DOIs
StatePublished - Dec 1 1999
Externally publishedYes
Event18th Annual Joint Conference of the IEEE Computer and Communications Societies: The Future is Now, IEEE INFOCOM'99 - New York, NY, United States
Duration: Mar 21 1991Mar 25 1991

Publication series

NameProceedings - IEEE INFOCOM
Volume3
ISSN (Print)0743-166X

Other

Other18th Annual Joint Conference of the IEEE Computer and Communications Societies: The Future is Now, IEEE INFOCOM'99
CountryUnited States
CityNew York, NY
Period3/21/913/25/91

    Fingerprint

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this

Stolyar, A. L., & Ramakrishnan, K. K. (1999). The stability of a flow merge point with non-interleaving cut-through scheduling disciplines. In Proceedings - IEEE INFOCOM'99: The Conference on Computer Communications - 18th Annual Joint Conference of the IEEE Computer and Communications Societies: The Future is Now (pp. 1231-1238). [752140] (Proceedings - IEEE INFOCOM; Vol. 3). https://doi.org/10.1109/INFCOM.1999.752140