Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2020, Vol. 14 Issue (1) : 130-145    https://doi.org/10.1007/s11704-018-7429-x
RESEARCH ARTICLE
Uncertain multicast under dynamic behaviors
Yudong QIN, Deke GUO(), Zhiyao HU, Bangbang REN
Science and Technology on Information System Engineering Laboratory, National University of Defense Technology, Changsha 410073, China
 Download: PDF(575 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Deke GUO   
Just Accepted Date: 26 March 2018   Online First Date: 07 September 2018    Issue Date: 24 September 2019
 Cite this article:   
Yudong QIN,Deke GUO,Zhiyao HU, et al. Uncertain multicast under dynamic behaviors[J]. Front. Comput. Sci., 2020, 14(1): 130-145.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-7429-x
https://academic.hep.com.cn/fcs/EN/Y2020/V14/I1/130
1 A A Mahimkar, Z Ge, A Shaikh, J Wang, J Yates, Y Zhang. Towards automated performance diagnosis in a large IPTV network. In: Proceedings of ACM SIGCOMM Conference on Data Communication. 2009, 231–242
https://doi.org/10.1145/1592568.1592596
2 D Li, Y Li, J Wu, S Su, J Yu. ESM: efficient and scalable data center multicast routing. IEEE/ACM Transactions on Networking, 2012, 20(3): 944–955
https://doi.org/10.1109/TNET.2011.2169985
3 D Li, M Xu, Y Liu, X Xie, Y Cui, J Wang. Reliable multicast in data center networks. IEEE Transactions on Computers, 2014, 63(8): 2011–2024
https://doi.org/10.1109/TC.2013.91
4 G Robins, A Zelikovsky. Tighter bounds for graph steiner tree approximation. Siam Journal on Discrete Mathematics, 2005, 19(1): 122–134
https://doi.org/10.1137/S0895480101393155
5 S Ghemawat, H Gobioff, S T Leung. The Google file system. ACM Sigops Operating Systems Review, 2003, 37(5): 29–43
https://doi.org/10.1145/1165389.945450
6 B G Chun, P Wu, H Weatherspoon, J Kubiatowicz. ChunkCast: an anycast service for large content distribution. In: Proceedings of Peer-to- Peer Systems. 2006
7 M F Habib, M Tornatore, M D Leenheer, F Dikbiyik, B Mukherjee. A disaster-resilient multi-content optical datacenter network architecture. In: Proceedings of the International Conference on Transparent Optical Networks. 2011, 29(1): 1–4
https://doi.org/10.1109/ICTON.2011.5970928
8 Z Hu, D Guo, J Xie, B Ren. Multicast routing with uncertain sources in software-defined network. In: Proceedings of the International Symposium on Quality of Service. 2016, 1–6
https://doi.org/10.1109/IWQoS.2016.7590417
9 Y K Dalal, R M Metcalfe. Reverse path forwarding of broadcast packets. Communications of the ACM, 1978, 21(12): 1040–1048
https://doi.org/10.1145/359657.359665
10 T Ballardie, P Francis, J Crowcroft. Core based trees (CBT). ACM Sigcomm Computer Communication Review, 1993, 23(4): 85–95
https://doi.org/10.1145/167954.166246
11 n Waxma, M Bernard. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 2002, 6(9): 1617–1622
https://doi.org/10.1109/49.12889
12 S P Hong, H Lee, B H Park. 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 G Feng, T P Yum. Efficient multicast routing with delay constraints. International Journal of Communication Systems, 2015, 12(3): 181–195
https://doi.org/10.1002/(SICI)1099-1131(199905/06)12:3<181::AID-DAC394>3.0.CO;2-Y
14 C Mohan, D Haderle, B Lindsay, H Pirahesh, P Schwarz. 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
https://doi.org/10.1145/128765.128770
15 S Raghavan, G Manimaran, R M C Siva. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees. IEEE/ACM Transactions on Networking, 1999, 7(4): 514–529
https://doi.org/10.1109/90.793020
16 M Doar, I Leslie. How bad is naive multicast routing? In: Proceedings of Joint Conference of the IEEE Computer and Communications Societies. 1993, 82–89
https://doi.org/10.1109/INFCOM.1993.253246
17 F Bauer, A Varma. Degree-constrained multicasting in point-to-point networks. In: Proceedings of Joint Conference of the IEEE Computer and Communication Societies. 1995, 369
https://doi.org/10.1109/INFCOM.1995.515897
18 F Bauer, A Varma. Distributed algorithms for multicast path setup in data networks. IEEE/ACM Transactions on Networking, 1996, 4(2): 181–191
https://doi.org/10.1109/90.490746
19 V P Kompella, J C Pasquale, G C Polyzos. Multicast routing for multimedia communication. IEEE/ACMTransactions on Networking, 1993, 1(3): 286–292
https://doi.org/10.1109/90.234851
[1] Xingshen SONG, Yuexiang YANG, Yu JIANG, Kun JIANG. Optimizing partitioning strategies for faster inverted index compression[J]. Front. Comput. Sci., 2019, 13(2): 343-356.
[2] Peng ZHANG. Unbalanced graph cuts with minimum capacity[J]. Front. Comput. Sci., 2014, 8(4): 676-683.
[3] Deying LI, Qinghua ZHU, Jiannong CAO, . Approximation algorithm for constructing data aggregation trees for wireless sensor networks[J]. Front. Comput. Sci., 2009, 3(4): 524-534.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed