A Combinatorial Bound on the List Size
A Combinatorial Bound on the List Size
复制标题
DOI：
--
复制
发表时间：
2004-05
期刊：
影响因子：
--
通讯作者：
Yuval Cassuto;Jehoshua Bruck
中科院分区：
文献类型：
--
作者：
Yuval Cassuto;Jehoshua Bruck
在本文中，我们研究了服务器通过单个广播通道向多个被动客户端发送动态数据的场景。我们认为数据由离散的数据包组成，其中每个更新都在一个单独的数据包中发送。根据需要，每个客户端监听通道以获取最新的数据包。这种场景出现在许多实际应用中，例如向无线移动设备分发天气和交通更新，以及通过Internet广播股票价格信息。为了满足一个请求，客户机必须从头到尾至少监听一个数据包。因此，我们考虑设计一个广播调度，使客户端请求和听到新数据包之间的时间最小化，即客户端的等待时间。以前的研究已经解决了这个问题，假设客户机请求随时间均匀分布。但是，在一般情况下，客户机的行为很难预测，服务器可能不知道客户机的行为。在这项工作中，我们考虑了通用调度的设计，以保证任何可能的客户行为的短等待时间。我们定义了通用设置下的动态广播模型，并证明了在该框架下可实现的等待时间的各种结果。
In this paper we study the scenario in which a server sends dynamic data over a single broadcast channel to a number of passive clients. We consider the data to consist of discrete packets, where each update is sent in a separate packet. On demand, each client listens to the channel in order to obtain the most recent data packet. Such scenarios arise in many practical applications such as the distribution of weather and traffic updates to wireless mobile devices and broadcasting stock price information over the Internet. To satisfy a request, a client must listen to at least one packet from beginning to end. We thus consider the design of a broadcast schedule which minimizes the time that passes between a clients request and the time that it hears a new data packet, i.e., the waiting time of the client. Previous studies have addressed this objective, assuming that client requests are distributed uniformly over time. However, in the general setting, the clients behavior is difficult to predict and might not be known to the server. In this work we consider the design of universal schedules that guarantee a short waiting time for any possible client behavior. We define the model of dynamic broadcasting in the universal setting, and prove various results regarding the waiting time achievable in this framework.