Self-adjusting grid networks to minimize expected path length

DOI10.1007/978-3-319-03578-9_4MaRDI QIDQ2868630zbMATH OpenOpenAlexFDO

Authors Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Lotker

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0196

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Given a network infrastructure (e.g., data-center or on-chip-network) and a distribution on the source-destination requests, the expected path (route) length is an important measure for the performance, efficiency and power consumption of the network. In this work we initiate a study on self-adjusting networks: networks that use local-distributed mechanisms to adjust the position of the nodes (e.g., virtual machines) in the network to best fit the route requests distribution. Finding the optimal placement of nodes is defined as the minimum expected path length (MEPL) problem. This is a generalization of the minimum linear arrangement (MLA) problem where the network infrastructure is a line and the computation is done centrally. In contrast to previous work, we study the distributed version and give efficient and simple approximation algorithms for interesting and practically relevant special cases of the problem. In particular, we consider grid networks in which the distribution of requests is a symmetric product distribution. In this setting, we show that a simple greedy policy of position switching between neighboring nodes to locally minimize an objective function, achieves good approximation ratios. We are able to prove this result using the useful notions of expected rank of the distribution and the expected distance to the center of the graph.

Recommendations

• Self-adjusting grid networks to minimize expected path length
• Demand-aware network designs of bounded degree
• Demand-aware network designs of bounded degree
• How bad is selfish routing?
• Distributed selfish load balancing on networks

Cites work

• A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
• A framework for solving VLSI graph layout problems
• A self-stabilizing and local Delaunay graph construction
• An adaptive routing strategy for packet delivery in complex networks
• Collective dynamics of `small-world' networks
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town?
• Minimum congestion mapping in a cloud
• Optimization by simulated annealing
• Self-adjusting binary search trees
• The complexity of minimizing wire lengths in VLSI layouts
• Topology-aware VM migration in bandwidth oversubscribed datacenter networks

Cited in

(5)

• Dynamically optimal self-adjusting single-source tree networks
• Self-adjusting linear networks
• Self-adjusting grid networks to minimize expected path length
• Self-adjusting grid networks
• Self-adjusting linear networks

This page was built for publication: Self-adjusting grid networks to minimize expected path length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868630)