Document Open Access Logo

Demand-Aware Network Designs of Bounded Degree

Authors Chen Avin, Kaushik Mondal, Stefan Schmid

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.5.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Chen Avin
Kaushik Mondal
Stefan Schmid

Cite As Get BibTex

Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-Aware Network Designs of Bounded Degree. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.5

Abstract

Traditionally, networks such as datacenter interconnects are designed to optimize worst-case performance under arbitrary traffic patterns. Such network designs can however be far from optimal when considering the actual workloads and traffic patterns which they serve. This insight led to the development of demand-aware datacenter interconnects which can be reconfigured depending on the workload.

Motivated by these trends, this paper initiates the algorithmic study of demand-aware networks (DANs), and in particular the design of bounded-degree networks. The inputs to the network design problem are a discrete communication request distribution, D, defined over communicating pairs from the node set V, and a bound, d, on the maximum degree. In turn, our objective is to design an (undirected) demand-aware network N = (V,E) of bounded-degree d, which provides short routing paths between frequently communicating nodes distributed across N. In particular, the designed network should minimize the expected path length on N (with respect to D), which is a basic measure of the efficiency of the network.

We show that this fundamental network design problem exhibits interesting connections to several classic combinatorial problems and to information theory. We derive a general lower bound based on the entropy of the communication pattern D, and present asymptotically optimal network-aware design algorithms for important distribution families, such as sparse distributions and distributions of locally bounded doubling dimensions.

Subject Classification

Keywords
  • Network design
  • reconfigurable networks
  • datacenter topology
  • peer-topeer computing
  • entropy
  • sparse spanners

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Chen Avin, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. Self-adjusting grid networks to minimize expected path length. In Proc. SIROCCO, pages 36-54, 2013. Google Scholar
  2. Chen Avin, Michael Borokhovich, and Stefan Schmid. OBST: A self-adjusting peer-to-peer overlay based on multiple BSTs. In Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on, pages 1-5. IEEE, 2013. Google Scholar
  3. Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-aware network designs of bounded degree. In arXiv report no. 1705.06024, 2017. Google Scholar
  4. Hubert T-H Chan, Michael Dinitz, Anupam Gupta, et al. Spanners with slack. In ESA, volume 6, pages 196-207. Springer, 2006. Google Scholar
  5. T-H Hubert Chan and Anupam Gupta. Small hop-diameter sparse spanners for doubling metrics. Discrete &Computational Geometry, 41(1):28-44, 2009. Google Scholar
  6. T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. ACM Trans. Algorithms, (4):55:1-55:22, 2016. Google Scholar
  7. Moses Charikar, Mohammad Taghi Hajiaghayi, Howard Karloff, and Satish Rao. l²₂ spreading metrics for vertex ordering problems. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1018-1027. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  8. C. Chen, R. Vitenberg, and H. A. Jacobsen. Scaling construction of low fan-out overlays for topic-based publish/subscribe systems. In 2011 31st International Conference on Distributed Computing Systems, pages 225-236, June 2011. Google Scholar
  9. Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley &Sons, 2012. Google Scholar
  10. Erik D Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Patraşcu. The geometry of binary search trees. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 496-505. SIAM, 2009. Google Scholar
  11. Uriel Feige and James R Lee. An improved approximation ratio for the minimum linear arrangement problem. Information Processing Letters, 101(1):26-29, 2007. Google Scholar
  12. Pierre Fraigniaud, Emmanuelle Lebhar, and Zvi Lotker. A doubling dimension threshold θ (log log n) for augmented graph navigability. In ESA, pages 376-386. Springer, 2006. Google Scholar
  13. Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proc. IEEE FOCS, pages 534-543, 2003. Google Scholar
  14. Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing, 35(5):1148-1184, 2006. Google Scholar
  15. Lawrence H Harper. Optimal assignments of numbers to vertices. Journal of the Society for Industrial and Applied Mathematics, 12(1):131-135, 1964. Google Scholar
  16. Su Jia, Xin Jin, Golnaz Ghasemiesfeh, Jiaxin Ding, and Jie Gao. Competitive analysis for online scheduling in software-defined optical wan. In Proc. IEEE INFOCOM, 2017. Google Scholar
  17. M. Ghobadi et al. Projector: Agile reconfigurable data center interconnect. In Proc. ACM SIGCOMM, pages 216-229, 2016. Google Scholar
  18. Kurt Mehlhorn. Nearly optimal binary search trees. Acta Inf., 5:287-295, 1975. Google Scholar
  19. Adam Meyerson and Brian Tagiku. Minimizing average shortest path distances via shortcut edge addition. In Proc. APPROX/RANDOM, pages 272-285, Berlin, Heidelberg, 2009. Google Scholar
  20. Melih Onus and Andréa W Richa. Minimum maximum-degree publish-subscribe overlay network design. IEEE/ACM Transactions on Networking, 19(5):1331-1343, 2011. Google Scholar
  21. Melih Onus and Andréa W Richa. Parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network design. Computer Networks, 94:307-317, 2016. Google Scholar
  22. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  23. Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex C Snoeren. Inside the social network’s (datacenter) network. In ACM SIGCOMM Computer Communication Review, volume 45, pages 123-137. ACM, 2015. Google Scholar
  24. Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. Splaynet: Towards locally self-adjusting networks. IEEE/ACM Trans. Netw., 24(3):1421-1433, June 2016. Google Scholar
  25. Ankit Singla. Fat-free topologies. In Proc. 15th ACM Workshop on Hot Topics in Networks (HotNets), pages 64-70, 2016. Google Scholar
  26. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, July 1985. Google Scholar
  27. Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proc. ACM STOC, pages 81-90, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact