Contention Resolution with Message Deadlines
Contention Resolution with Message Deadlines
复制标题
DOI：
10.1145/3350755.3400239
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Kunal Agrawal;M. A. Bender;Jeremy T. Fineman;Seth Gilbert;Maxwell Young
中科院分区：
文献类型：
--
作者：
Kunal Agrawal;M. A. Bender;Jeremy T. Fineman;Seth Gilbert;Maxwell Young
在竞争解决问题中，多个参与者竞争对共享资源的访问。争用解决在无线网络中使用，其中消息必须在共享通信信道上传输。当同时传输两个或多个消息时，会发生冲突，并且没有一个传输成功。竞争解决的理论工作集中在有效地解决冲突，以获得吞吐量保证。然而，在现代网络中，并非所有流量都得到平等对待。相反，消息通常根据优先级的概念来处理。虽然吞吐量仍然是一个重要的指标，但它无法捕捉这种日益常见的流量优先级排序场景。出于这种考虑，我们设计了一个竞争解决算法的消息有交付期限。单位长度的消息随时间动态到达，每个消息都有相应的传递截止日期，该截止日期划分了消息必须成功传输的时间窗口。我们认为输入有一个可行的时间表，即使消息大小增加了一个常数因子。在这种情况下，我们提供了一个算法，保证每个消息成功的最后期限，在其窗口大小的概率很高。
In the contention-resolution problem, multiple players contend for access to a shared resource. Contention resolution is used in wireless networks, where messages must be transmitted on a shared communication channel. When two or more messages are transmitted at the same time, a collision occurs, and none of the transmissions succeed. Much of the theoretical work on contention resolution has focused on efficiently resolving collisions in order to obtain throughput guarantees. However, in modern-day networks, not all traffic is treated equally. Instead, messages are often handled according to a notion of priority. While throughput remains an important metric, it fails to capture this increasingly-common scenario of traffic prioritization. Motivated by this concern, we design a contention-resolution algorithm where messages have delivery deadlines. Unit-length messages dynamically arrive over time, each with a corresponding delivery deadline that demarcates a window of time wherein the message must be transmitted successfully. We consider inputs that have a feasible schedule, even if message sizes increase by a constant factor. In this setting, we provide an algorithm which guarantees that each message succeeds by its deadline with high probability in its window size.