Competitive On-Line Switching Policies
Competitive On-Line Switching Policies
复制标题
竞争性在线切换策略
DOI：
10.1007/s00453-003-1014-9
复制
发表时间：
2002
期刊：
影响因子：
1.1
通讯作者：
J. Naor
中科院分区：
文献类型：
--
作者：
A. Bar;Ari Freund;Shimon Landa;J. Naor
考虑以下问题。将n个输入通道连接到单个输出通道的交换机必须通过该通道传递所有传入消息。消息由数据包组成，在每个时隙中，交换机可以将单个数据包从一个输入队列传送到输出通道。为了防止数据包丢失，为每个输入通道保留一个缓冲区。切换策略的目标是最小化最大缓冲区大小。设置是在线的;必须根据当前状态做出决策，而不知道未来的事件。这个通用场景模拟了各种系统（如通信网络、电缆调制解调器系统和流量控制）中的多路复用任务。传统上，研究人员分析了给定策略的性能，假设输入队列中消息的到达率具有某种分布，或者假设服务速率至少是所有输入速率的总和。我们使用竞争分析，避免对输入的任何先验假设。我们展示了O（log n）-竞争的切换策略的问题，并展示了匹配的下界。
Consider the following problem. A switch connecting n input channels to a single output channel must deliver all incoming messages through this channel. Messages are composed of packets , and in each time slot the switch can deliver a single packet from one of the input queues to the output channel. In order to prevent packet loss, a buffer is maintained for each input channel. The goal of a switching policy is to minimize the maximum buffer size. The setting is on-line; decisions must be made based on the current state without knowledge of future events. This general scenario models multiplexing tasks in various systems such as communication networks, cable modem systems, and traffic control. Traditionally, researchers analyzed the performance of a given policy assuming some distribution on the arrival rates of messages at the input queues, or assuming that the service rate is at least the aggregate of all the input rates. We use competitive analysis, avoiding any prior assumptions on the input. We show O(log n )-competitive switching policies for the problem and demonstrate matching lower bounds.