|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|