论文标题
带有梯子需求图的自调整线性网络图
Self-Adjusting Linear Networks with Ladder Demand Graph
论文作者
论文摘要
自我调整网络（SANS）具有通过动态调整工作量（或需求）嵌入（即将通信请求映射到网络拓扑的映射）来适应通信需求的能力。因此，SAN可以通过支付调整嵌入的费用来降低常见通信节点对的路由成本。当需求具有结构，网络可以适应该需求时，这尤其有益。需求可以以需求图的形式表示，该图是由网络节点集（顶点）和成对通信请求集（EDGE）的集合所定义的。因此，可以通过将需求图嵌入网络拓扑来解释需求。当需求图提前（离线）以及揭示边缘边缘（在线）时，这可能会具有挑战性。难度还取决于我们是要构建静态拓扑还是动态（自我调整），从而揭示了需求图的更多部分，从而改善了嵌入。然而，对于这些自我调整的嵌入知之甚少。 在本文中，网络拓扑仅限于一条线，需求图将梯形图，即$ 2^n $网格，包括梯子的所有可能子图。我们提出了一个在线自调整网络，该网络与已知的下限渐近型匹配，并且在请求成本方面为$ 12 $竞争。作为热身结果，我们为周期需求图提供了渐近最佳算法。我们还为一个具有恒定开销的任意需求图提供了一种基于Oracle的算法。
Self-adjusting networks (SANs) have the ability to adapt to communication demand by dynamically adjusting the workload (or demand) embedding, i.e., the mapping of communication requests into the network topology. SANs can thus reduce routing costs for frequently communicating node pairs by paying a cost for adjusting the embedding. This is particularly beneficial when the demand has structure, which the network can adapt to. Demand can be represented in the form of a demand graph, which is defined by the set of network nodes (vertices) and the set of pairwise communication requests (edges). Thus, adapting to the demand can be interpreted by embedding the demand graph to the network topology. This can be challenging both when the demand graph is known in advance (offline) and when it revealed edge-by-edge (online). The difficulty also depends on whether we aim at constructing a static topology or a dynamic (self-adjusting) one that improves the embedding as more parts of the demand graph are revealed. Yet very little is known about these self-adjusting embeddings. In this paper, the network topology is restricted to a line and the demand graph to a ladder graph, i.e., a $2^n$ grid, including all possible subgraphs of the ladder. We present an online self-adjusting network that matches the known lower bound asymptotically and is $12$-competitive in terms of request cost. As a warm up result, we present an asymptotically optimal algorithm for the cycle demand graph. We also present an oracle-based algorithm for an arbitrary demand graph that has a constant overhead.
