• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computer Communications >Working Set Theorems for Routing in Self-Adjusting Skip List Networks
【24h】

Working Set Theorems for Routing in Self-Adjusting Skip List Networks

机译：自调整跳过列表网络中用于路由的工作集定理

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper explores the design of dynamic network topologies which adjust to the workload they serve, in a demand-aware and online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. However, such reconfigurations also come at a cost, introducing a need for online algorithms which strike an optimal balance between the benefits and costs of reconfigurations.This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on a distributed implementation of skip lists (which serves as the topology) and provide additional interesting properties such as local routing. Our first contribution is SASL2, which is a randomized and sequential SAN algorithm that achieves the working set property. Then we show how SASL2 can be converted to a distributed algorithm that handles concurrent communication requests and maintains SASL2’s properties. Finally, we present deterministic SAN algorithms.
机译：本文探讨了动态网络拓扑的设计，该拓扑以需求感知和在线方式适应其服务的工作负载。这样的自调节网络（SAN）通过新兴的光学技术来实现，并且可以在例如数据中心中找到。通过将频繁通信的节点从拓扑上移近，SAN可用于降低路由成本。但是，这样的重新配置也要付出一定的代价，这就需要在线算法，以便在重新配置的收益和成本之间找到最佳的平衡。本文介绍了首次提供可证明的工作集保证的SAN：SAN之间的路由成本：节点对与这些节点最近一次通信的最近程度成正比。我们的SAN依赖于跳过列表的分布式实现（用作拓扑），并提供其他有趣的属性，例如本地路由。我们的第一项贡献是SASL 2 ，这是一种随机且顺序的SAN算法，可实现工作集属性。然后我们展示SASL 2 可以转换为处理并发通信请求并维护SASL的分布式算法 2 的属性。最后，我们介绍了确定性SAN算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号