Uncertain multicast under dynamic behaviors

Abstract

Multicast transfer can efficiently save the bandwidth consumption and reduce the load on the source node than a series of independent unicast transfers. Nowadays, many applications employ the content replica strategy to improve the robustness and efficiency; hence each file and its replicas are usually distributed among multiple sources. In such scenarios, the traditional deterministic multicast develops into the Uncertain multicast, which has more flexibility in the source selection. In this paper, we focus on building and maintaining a minimal cost forest (MCF) for any uncertain multicast, whose group members (source nodes and destination nodes) may join or leave after constructing a MCF. We formulate this dynamic minimal cost forest (DMCF) problem as a mixed integer programming model. We then design three dedicated methods to approximate the optimal solution. Among them, our a-MCF aims to efficiently construct an MCF for any given uncertain multicast, without dynamic behaviors of multicast group members. The d-MCF method motivates to slightly update the existing MCF via local modifications once appearing a dynamic behavior. It can achieve the balance between the minimal cost and the minimal modifications to the existing forest. The last r-MCF is a supplement method to the d-MCF method, since many rounds of local modifications maymake the resultant forest far away from the optimal forest. Accordingly, our r-MCF method monitors the accumulated degradation and triggers the rearrangement process to reconstruct an new MCF when necessary. The comprehensive evaluation results demonstrate that our methods can well tackle the proposed DMCF problem.

Keywords

uncertain multicast / dynamic behaviors / routing forest / approximation algorithm / Steiner tree

References

[1] Mahimkar A A, Ge Z, Shaikh A, Wang J, Yates J, Zhang Y. Towards automated performance diagnosis in a large IPTV network. In: Proceedings of ACM SIGCOMM Conference on Data Communication. 2009, 231–242

[2] Li D, Li Y, Wu J, Su S, Yu J. ESM: efficient and scalable data center multicast routing. IEEE/ACM Transactions on Networking, 2012, 20(3): 944–955

[3] Li D, Xu M, Liu Y, Xie X, Cui Y, Wang J. Reliable multicast in data center networks. IEEE Transactions on Computers, 2014, 63(8): 2011–2024

[4] Robins G, Zelikovsky A. Tighter bounds for graph steiner tree approximation. Siam Journal on Discrete Mathematics, 2005, 19(1): 122–134

[5] Ghemawat S, Gobioff H, Leung S T. The Google file system. ACM Sigops Operating Systems Review, 2003, 37(5): 29–43

[6] Chun B G, Wu P, Weatherspoon H, Kubiatowicz J. ChunkCast: an anycast service for large content distribution. In: Proceedings of Peer-to- Peer Systems. 2006

[7] Habib M F, Tornatore M, Leenheer M D, Dikbiyik F, Mukherjee B. A disaster-resilient multi-content optical datacenter network architecture. In: Proceedings of the International Conference on Transparent Optical Networks. 2011, 29(1): 1–4

[8] Hu Z, Guo D, Xie J, Ren B. Multicast routing with uncertain sources in software-defined network. In: Proceedings of the International Symposium on Quality of Service. 2016, 1–6

[9] Dalal Y K, Metcalfe R M. Reverse path forwarding of broadcast packets. Communications of the ACM, 1978, 21(12): 1040–1048

[10] Ballardie T, Francis P, Crowcroft J. Core based trees (CBT). ACM Sigcomm Computer Communication Review, 1993, 23(4): 85–95

[11] Waxma n, Bernard M. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 2002, 6(9): 1617–1622

[12] Hong S P, Lee H, Park B H. An efficient multicast routing algorithm for delay-sensitive applications with dynamic membership. In: Proceedings of Joint Conference of the IEEE Computer and Communications Societies. 1998, 1433–1440

[13] Feng G, Yum T P. Efficient multicast routing with delay constraints. International Journal of Communication Systems, 2015, 12(3): 181–195

[14] Mohan C, Haderle D, Lindsay B, Pirahesh H, Schwarz P. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Transactions on Database Systems, 1992, 17(1): 94–162

[15] Raghavan S, Manimaran G, Siva R M C. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees. IEEE/ACM Transactions on Networking, 1999, 7(4): 514–529

[16] Doar M, Leslie I. How bad is naive multicast routing? In: Proceedings of Joint Conference of the IEEE Computer and Communications Societies. 1993, 82–89

[17] Bauer F, Varma A. Degree-constrained multicasting in point-to-point networks. In: Proceedings of Joint Conference of the IEEE Computer and Communication Societies. 1995, 369

[18] Bauer F, Varma A. Distributed algorithms for multicast path setup in data networks. IEEE/ACM Transactions on Networking, 1996, 4(2): 181–191

[19] Kompella V P, Pasquale J C, Polyzos G C. Multicast routing for multimedia communication. IEEE/ACMTransactions on Networking, 1993, 1(3): 286–292

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature