Networked and distributed systems are becoming increasingly flexible. In particular, it has become possible to dynamically migrate communication endpoints [2] in a self-adjusting and demand-aware manner, allowing these networks to adapt to the ongoing traffic pattern. In particular, more frequently communicating nodes can be moved topologically closer to each other, thus, reducing bandwidth taxes [11] and improving performance.
We consider the following problem. The network is a line and the graph built by pairwise requests is G, i.e., the demand graph. The requests between nodes are coming online, i.e. one by one, revealing G. Before performing a request, we can re-adjust the line graph by performing several swaps of two neighbouring nodes and by paying one for each swap. Please, note that it does not matter when we perform adjustments, before or after requests, the total cost will differ by a constant. Then, to serve a request itself, we should follow the path between the corresponding nodes in the line network and pay each time we pass a link, i.e., in total, we pay the distance between the nodes per request. Thus, the total cost of an algorithm consists of two parts: the total cost of adjustments, i.e., swaps, plus the total cost of the requests.
In the previous work [7], the demand graph is also a line. The authors presented an algorithm that serves m = Q^n?} requests at cost O(n2 log n + m) and showed that this complexity is the lower bound. This problem was inspired by Itinerant List Update Problem [14].
Contributions. In this work, we go further: we consider the same line network topology while trying to generalize the demand graph. As a result, we provide three separate results. At first, the generic algorithm for arbitrary demand graphs with the best complexity per request (in a theoretical sense). Secondly, we present an algorithm for the case when the demand graph is a cycle. And, finally, as the main result, we present an algorithm for a generalization of a line demand graph: a 2 x n grid graph, later called the n-ladder graph. Note that this algorithm can be applied to any demand graph that is a subgraph of the n-ladder graph. Most importantly, both algorithms, for a cycle and a ladder graph, match the lower bound for the line demand graph: n2 log n cost for adjustments in total plus O(1) per request being the lower bound.
Our work is an important improvement of the previous work. A solution for the n-ladder grid is the first step towards a more generic problem where the demand graph is a generic grid, n x m. One of the main arising problems is that even an embedding of a tree onto an infinite grid is NP-hard [12], while it is polynomial in our case leading to a reasonably simple algorithm. Moreover, a ladder (and a cycle) has a constant bandwidth, i.e., a minimum value over all embeddings onto a target line graph of a maximal path between the ends of an edge (request). It can be shown that given a demand graph G the best possible complexity per request is the bandwidth. However, the calculation of the bandwidth, in general, is also NP-hard [15].
Related work. Self-adjusting networks (SANs) have been made possible due to novel network technologies [10]. They were introduced from an algorithmic point of view in [5], [16]. Existing works have studied linear networks [7], bounded degree networks [6], skip list networks [4] and skip graphs [13]. Moreover, recent work has also focused in more advanced cost models [1], [9]. The most relevant work to ours [7] studied linear networks with linear demand graphs. Furthermore, [3] studied optimal network topologies, when the demand is known.
Roadmap. Section 2 contains the description of the model in which we are working. Section 3 contains the list of our three results and their high-level proofs. This list contains the generic result, the result for the cycle, and the results for the ladder. In Section 4 we introduce all the necessary notions for our algorithm on the grid. Section 5 presents an algorithm for the ladder. In Section 6, we calculate the complexity of the presented algorithm and show that it achieves the desired cost. Section 9 concludes the paper. Due to space constraints, some technical details are deferred to the appendix. The pseudocode of our algorithm for the ladder appears in Appendix 7.2 and 7.1, while proofs appear in Appendix 8.
In this paper, we presented three results: 1) the upper bound cost on any algorithm for an arbitrary demand graph; 2) an online algorithm with its cost for a cycle demand graph; and, finally, 3) an online algorithm with its cost for a Gridn demand graph. In the last two cases, we presented algorithms that match the lower bound. We think this is the first important step towards the tight bound for more generic graphs such as arbitrary grids that we are going to research in the future work.
