Markov-Chain Modeling for Multicast Signaling
Xi Zhang, Kang Geun Shin · 2003
Feedback signaling plays a key role in flow control because the traffic source relies on the signaling information to make correct and timely flow-control decisions. However, it is difficult to design an efficient signaling algorithm since a signaling message can tolerate neither error nor latency. Multicast flow-control signaling imposes two additional challenges: scalability and feedback synchronization. Previous research on multicast sig- naling has mainly focused on the development of algorithms without ana- lyzing their delay performance. To remedy this deficiency, we have previ- ously developed a binary-tree model (1) and an independent-marking statis- tical model (2) for multicast-signaling delay analysis. This paper considers a general scenario where the congestion markings at different links are de- pendent — a more accurate but complex case. Specifically, we develop a Markov-chain model defined by the link-marking state on each path in the multicast tree. The Markov chain can not only capture link-marking de- pendencies, but also yield a tractable analytical model. We also develop a Markov-chain dependency-degree model to evaluate all possible Markov- chain dependency degrees without any prior knowledge of it. Using the above two models, we derive the general probability distributions of each path becoming the multicast-tree bottleneck. Also derived are the first and second moments of multicast signaling delays. The proposed Markov chain is also shown to asymptotically reach an equilibrium, and its limiting dis- tribution converges to the marginal link-marking probabilities when the Markov chain is irreducible. Applying the two models, we analyze and contrast the delay scalability of two representative multicast signaling pro- tocols: Soft-Synchronization Protocol (SSP) (1-3) and Hop-By-Hop (HBH) algorithms (4-6).