+1 Recommend
1 collections
      • Record: found
      • Abstract: found
      • Article: found

      Minimum-Cost Forest for Uncertain Multicast with Delay Constraints

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          The use of multicast transmission can efficiently reduce the consumption of network resources by jointly serving multiple destinations with a single source node. Currently, many multicast applications impose the constraint wherein multicast flows must be processed by a series of Virtual Network Functions (VNFs) before reaching their destinations. Given a multicast transmission, there are usually multiple server nodes, each of which is able to host all the required VNFs. Thus, the multicast flow should be initially steered to one or a few selected server nodes that act as pseudo sources, and the destinations will then retrieve new flow from any of these pseudo sources. In this paper, we model this kind of multicast as an uncertain multicast with multiple pseudo sources, whose routing structure is usually a forest consisting of multiple isolated trees. We then characterize and construct the Delay-guaranteed Minimum Cost Forest (D-MCF) such that each path from the source to the destination satisfies the end-to-end delay constraint. To tackle this NP-hard problem, we design two efficient methods, the Partition Algorithm (PA) and the Combination Algorithm (CA), to approximate the optimal solution. Theoretical analyses and evaluations indicate that these two methods can generate the desired routing forest for any multicast transfer. Moreover, the PA method achieves a better balance between performance and time consumption than the CA method. The evaluation results show that PA- ( Ω + 20 ) can reduce total cost by 49.02 % while consuming 12.59 % more time, thus significantly outperforming the CA- ( Ω + 20 ) method.

          Related collections

          Author and article information

          Tsinghua Science and Technology
          Tsinghua Science and Technology
          Tsinghua University Press (Xueyan Building, Tsinghua University, Beijing 100084, China )
          05 April 2019
          : 24
          : 2
          : 147-159
          ∙ Bangbang Ren, Geyao Cheng, and Deke Guo are with the College of Systems Engineering, National University of Denfense Technology, Changsha 410072, China. E-mail: renbangbang11@nudt.edu.cn, dekeguo@nudt.edu.cn.
          Author notes
          * To whom correspondence should be addressed. E-mail: chenggeyao13@ 123456nudt.edu.cn .

          Bangbang Ren received the BS and MS degrees from National University of Defense Technology (NUDT) in 2015 and 2017, respectively. He is currently a PhD student in NUDT. His research interests include software-defined network, data center network, and network function virtualization.

          Geyao Cheng received the BS degree from National University of Defense Technology in 2016. She is currently working towards the MS degree at National University of Defense Technology. Her research interests include datacenter network, mobile computing, and crowdsensing.

          Deke Guo received the BS degree from Beijing University of Aeronautics and Astronautics in 2001, and the PhD degree from National University of Defense Technology in 2008. He is currently a professor in the College of Systems Engineering at National University of Defense Technology. His research interests include distributed systems, software-defined networking, data center networking, wireless and mobile systems, and interconnection networks. He is a senior member of the IEEE and a member of the ACM.

          Self URI: Publisher


          Comment on this article