A Characterization of Universal Stability in the Adversarial Queuing Model
A Characterization of Universal Stability in the Adversarial Queuing Model
复制标题
对抗性排队模型中普遍稳定性的表征
DOI：
10.1137/s0097539703435522
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
M. Serna
中科院分区：
文献类型：
--
作者：
Carme Àlvarez;M. Blesa;M. Serna
我们研究静态数据包路由的对抗排队模型中有向图和无向图的普遍稳定性。在此设置中，数据包被注入某个边缘，并且在离开系统之前必须遍历预定义的路径。对允许的数据包轨迹的限制提供了一种分析不同数据包轨迹下稳定性的方法。我们考虑五个数据包轨迹，两个用于有向图，三个用于无向图，并提供多项式时间算法来在考虑每个数据包轨迹时测试通用稳定性。在每种情况下，我们都根据一组禁止子图获得了普遍稳定性性质的不同特征。因此，我们表明允许的数据包轨迹的变化会导致不等效的特征。
利用这些特征，我们还能够提供多项式时间算法，用于在 \NTGLIS（最近到系统中最长的时间）协议下测试稳定性。
We study universal stability of directed and undirected graphs in the adversarial queuing model for static packet routing. In this setting, packets are injected in some edge and have to traverse a predefined path before leaving the system. Restrictions on the allowed packet trajectory provide a way to analyze stability under different packet trajectories. We consider five packet trajectories, two for directed graphs and three for undirected graphs, and provide polynomial time algorithms for testing universal stability when considering each of them. In each case we obtain a different characterization of the universal stability property in terms of a set of forbidden subgraphs. Thus we show that variations of the allowed packet trajectory lead to nonequivalent characterizations.
Using those characterizations we are also able to provide polynomial time algorithms for testing stability under the \NTGLIS (Nearest To Go-Longest In System) protocol.