Abstract
As the Internet becomes more virtualized and software-defined, new functionality is introduced in the network core: the distributed resources available in ISP central offices, universal nodes, or datacenter middleboxes can be used to process (e.g., filter, aggregate or duplicate) data. Based on this new networking paradigm, we formulate the Constrained Virtual Steiner Arborescence Problem (CVSAP) which asks for optimal locations to perform in-network processing, in order to jointly minimize processing costs and network traffic while respecting link and node capacities.
We prove that CVSAP cannot be approximated (unless NP ⊆ P), and accordingly, develop the exact algorithm VirtuCast to compute optimal solutions to CVSAP. VirtuCast consists of: (1) a compact single-commodity flow Integer Programming (IP) formulation; (2) a flow decomposition algorithm to reconstruct individual routes from the IP solution. The compactness of the IP formulation allows for computing lower bounds even on large instances quickly, speeding up the algorithm significantly. We rigorously prove VirtuCast’s correctness and show its applicability to solve realistically sized instances close to optimality.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Achterberg, T.: SCIP: Solving Constraint Integer Programs. Mathematical Programming Computation 1(1), 1–41 (2009)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall (1993)
Banchs, A., Effelsberg, W., Tschudin, C., Turau, V.: Multicasting Multimedia Streams with Active Networks. In: Proc. Local Computer Network Conference (LCN). IEEE (1998)
Cai, Z., Lin, G., Xue, G.: Improved Approximation Algorithms for the Capacitated Multicast Routing Problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 136–145. Springer, Heidelberg (2005)
Costa, P., Donnelly, A., Rowstron, A., Shea, G.O.: Camdoop: Exploiting In-network Aggregation for Big Data Applications. In: Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI) (2012)
Costa, P., Migliavacca, M., Pietzuch, P., Wolf, A.L.: NaaS: Network-as-a-Service in the Cloud. In: Proc. USENIX Hot-ICE Workshop (2012)
Cranor, C., Johnson, T., Spataschek, O., Shkapenyuk, V.: Gigascope: A Stream Database for Network Applications. In: Proc. ACM SIGMOD International Conference on Management of Data, pp. 647–651 (2003)
Demaine, E.D., Hajiaghayi, M., Klein, P.N.: Node-weighted steiner tree and group steiner tree in planar graphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 328–340. Springer, Heidelberg (2009)
European Telecommunications Standards Institute. Network Functions Virtualisation - Introductory White Paper. SDN and OpenFlow World Congress, Darmstadt-Germany (2012)
Eyal, I., Keidar, I., Patterson, S., Rom, R.: In-Network Analytics for Ubiquitous Sensing. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 507–521. Springer, Heidelberg (2013)
Fasolo, E., Rossi, M., Widmer, J., Zorzi, M.: In-Network Aggregation Techniques for Wireless Sensor Networks: A Survey. IEEE Wireless Communications 14, 70–87 (2007)
Goemans, M.X., Myung, Y.-S.: A catalog of Steiner tree formulations. Networks 23(1), 19–28 (1993)
Gollowitzer, S., Ljubić, I.: MIP models for Connected Facility Location: A theoretical and computational study. Computers & Operations Research 38(2), 435–449 (2011)
Hermsmeyer, C., Hernandez-Valencia, E., Stoll, D., Tamm, O.: Ethernet aggregation and core network models for effcient and reliable IPTV services. Bell Labs Technical Journal 12(1), 57–76 (2007)
Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 760–769. Society for Industrial and Applied Mathematics (2000)
Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32(3), 207–232 (1998)
Lee, Y., Lu, L., Qiu, Y., Glover, F.: Strong formulations and cutting planes for designing digital data service networks. Telecommunication Systems 2(1), 261–274 (1993)
Lucena, A., Resende, M.G.: Strong lower bounds for the prize collecting Steiner problem in graphs. Discrete Applied Mathematics 141(1), 277–294 (2004)
Molnár, M.: Hierarchies to Solve Constrained Connected Spanning Problems. Technical Report lrimm-00619806, University Montpellier 2, LIRMM (2011)
Narayana, S., Jiang, W., Rexford, J., Chiang, M.: Joint Server Selection and Routing for Geo-Replicated Services. In: Proc. Workshop on Distributed Cloud Computing (DCC) (2013)
Oliveira, C., Pardalos, P.: Streaming Cache Placement. In: Mathematical Aspects of Network Routing Optimization. Springer Optimization and Its Applications, pp. 117–133. Springer, New York (2011)
Park, J.-W., Lim, H., Kim, J.: Virtual-node-based multicast routing and wavelength assignment in sparse-splitting optical networks. Photonic Network Communications 19(2), 182–191 (2010)
Qazi, Z., Tu, C.-C., Chiang, L., Miao, R., Sekar, V., Yu, M.: SIMPLE-fying Middlebox Policy Enforcement Using SDN. In: Proc. ACM SIGCOMM (2013)
Quoitin, B., Van den Schrieck, V., Franois, P., Bonaventure, O.: IGen: Generation of router-level Internet topologies through network design heuristics. In: Proc. 21st International Teletraffic Congress (ITC), pp. 1–8 (2009)
Rost, M., Schmid, S.: CVSAP-Project Website (2013), http://www.net.t-labs.tu-berlin.de/~stefan/cvsap.html
Rost, M., Schmid, S.: The Constrained Virtual Steiner Arborescence Problem: Formal Definition, Single-Commodity Integer Programming Formulation and Computational Evaluation. Technical report, arXiv: 1310.0346 (2013)
Shi, S.: A Proposal for A Scalable Internet Multicast Architecture. Technical Report WUCS-01-03, Washington University (2001)
Voß, S.: Steiner Tree Problems in Telecommunications. In: Handbook of optimization in telecommunications, ch. 18. Spinger Science + Business Media, New York (2006)
Zhang, Z., Zhang, M., Greenberg, A., Hu, Y.C., Mahajan, R., Christian, B.: Optimizing cost and performance in online service provider networks. In: Proc. 7th USENIX Conference on Networked Systems Design and Implementation (NSDI) (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Rost, M., Schmid, S. (2013). VirtuCast: Multicast and Aggregation with In-Network Processing. In: Baldoni, R., Nisse, N., van Steen, M. (eds) Principles of Distributed Systems. OPODIS 2013. Lecture Notes in Computer Science, vol 8304. Springer, Cham. https://doi.org/10.1007/978-3-319-03850-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-03850-6_16
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03849-0
Online ISBN: 978-3-319-03850-6
eBook Packages: Computer ScienceComputer Science (R0)