Asynchronous Shared Channel
Asynchronous Shared Channel
复制标题
异步共享通道
DOI：
10.1145/3087801.3087831
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Grzegorz Stachowiak
中科院分区：
文献类型：
--
作者：
G. D. Marco;Grzegorz Stachowiak
在这项工作中，我们解决的问题是否可以有效地利用一个简单的共享信道，也就是说，具有恒定的吞吐量和线性数据包延迟。共享信道（也称为多路访问信道），近50年前在以太网[36]的背景下引入，是通信和分布式计算中最流行和最广泛研究的模型之一。简而言之，许多站能够通过发送和监听共享信道进行通信，并且当且仅当其源站是一次唯一的发送器时，消息才被成功地传递到所有站。尽管在过去的几十年里做了大量的工作，许多基本的问题仍然悬而未决，例如：什么是信道利用率的影响？对竞争者数量的了解/估计有多重要？非自适应协议（即，随机码）是渐近有效的自适应协议？在这项工作中，我们提出了一个广泛的图片的结果回答上述问题的竞争解决的一个基本问题，其中每个竞争站需要成功地广播其消息。我们表明，自适应算法或算法与知识的竞争大小k（即，具有k）知识的随机码甚至对于非常弱的信道也实现了恒定的信道吞吐量和线性消息等待时间，即，反馈限于简单的重复并且没有同步。这种渐近最优性能不能扩展到其他设置-我们证明了，如果不知道争用大小k，就不存在非自适应算法，从而实现吞吐量\omega（（\log\log k）^2/（\log k））和/或允许延迟o（k\log k/（\log\log k）^2）。这意味着，特别地，在没有同步或竞争大小的估计的情况下，具有重叠的编码（甚至是随机的）在共享信道上不是非常有效。我们还提出了一个非自适应算法，没有知识的竞争大小，几乎匹配这两个复杂性。更具体地，即使站在成功传输之后不关闭（并且因此可能在后续中干扰其他站），它也实现延迟O（k\log^2 k）和信道利用率\Omega（1/\log^2 k），并且如果站在确认之后关闭，则可以通过因子\Theta（\log\log k）来改进。尽管缺乏碰撞检测机制，我们的算法也是有效的能源。对于我们的非自适应解决方案，在知道和不知道k的情况下，信道访问（包括传输和重传）的最大数量分别为O（\log k）和O（\log^2 k）whp。关于自适应算法，我们认为，我们的协议的一个简单的修改保持恒定的吞吐量和线性延迟，同时实现O（\log k）的最大数量的通道访问每站whp。
In this work we address the question whether a simple shared channel could be efficiently utilized, that is, with a constant throughput and linear packet latency. A shared channel (also called a multiple access channel), introduced nearly 50 years ago in the context of the Ethernet [36], is among the most popular and widely studied models of communication and distributed computing. In a nutshell, a number of stations is able to communicate by transmitting and listening to a shared channel, and a message is successfully delivered to all stations if and only if its source station is the only transmitter at a time. Despite of a vast amount of work in the last decades, many fundamental questions remain open, such as: What is the impact of asynchrony on channel utilization? How important is the knowledge/estimate of the number of contenders? Could non-adaptive protocols (i.e., random codes) be asymptotically as efficient as adaptive protocols? In this work we present a broad picture of results answering the above mentioned questions for a fundamental problem of contention resolution, in which each of the contending stations needs to broadcast successfully its message. We show that adaptive algorithms or algorithms with the knowledge of contention size k (i.e., random codes with knowledge of k) achieve constant channel throughput and linear message latency even for very weak channels, i.e., with feedback restricted to simple acknowledgments and in the absence of synchronization. This asymptotically optimal performance cannot be extended to other settings --- we prove that there is no non-adaptive algorithm without the knowledge of contention size k achieving throughput \omega((\log\log k)^2/(\log k)) and/or admitting latency o(k\log k/(\log\log k)^2). This means, in particular, that coding (even random) with acknowledgments is not very efficient on a shared channel without synchronization or estimate of contention size. We also present a non-adaptive algorithm with no knowledge of contention size that almost matches these two complexities. More specifically, it achieves latency O(k\log^2 k) and channel utilization \Omega(1/\log^2 k) even if stations do not switch off after successful transmissions (and thus, could disturb other stations in succeeding), and could be improved by factor \Theta(\log\log k) if stations switch off after acknowledgment. Despite the absense of a collision detection mechanism, our algorithms are also efficient in terms of energy. The maximum number of channel accesses (including transmissions and listenings) for our non-adaptive solutions, with and without knowledge of k, is respectively O(\log k) and O(\log^2 k) whp. Regarding the adaptive algorithm, we argue that a simple modification of our protocol preserves constant throughput and linear latency while achieving O(\log k) maximum number of channel accesses per station whp.