检索结果-内蒙古大学图书馆

Stability bounds in networks with dynamic link capacities

INFORMATION PROCESSING LETTERS 2008年第2期109卷 151-154页

作者： Cholvi, V. Univ Jaume 1 Dept Lenguajes & Sistemas Informat Castellon de La Plana 12071 Spain

We address the problem of stability in networks where the link capacities can change dynamically. We show that every network running a greedy scheduling policy is universally stable at any injection rate r < 1/(Cd), where d is the largest number of links crossed by any packet and C is the maximum link capacity. We also show that system-wide time priority scheduling policies are universally stable at any injection rate r < 1/(C(d - 1)). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Packet switched networks Network stability Interconnection networks Adversarial queueing theory greedy scheduling protocols Performance evaluation

来源：评论

学校读者我要写书评

暂无评论

The complexity of deciding stability under FFS in the Adversarial Queueing model

引用

INFORMATION PROCESSING LETTERS 2004年第5期90卷 261-266页

作者： Alvarez, C Blesa, M Díaz, J Fernández, A Serna, M Univ Politecn Catalunya Dept Llenguatges & Sist Informat E-08034 Barcelona Spain Univ Rey Juan Carlos Grp Sist & Commun E-28933 Madrid Spain

We address the problem of deciding whether a given network is stable in the Adversarial Queueing Model when considering farthest-from-source (FFS) as the queueing policy to schedule the packets through its links. We show a characterisation of the networks which are stable under FFS in terms of a family of forbidden subgraphs. We show that the set of networks stable under FFS coincide with the set of universally stable networks. Since universal stability of networks can be checked in polynomial time, we obtain that stability under FFS can also be decided in polynomial time. (C) 2004 Elsevier B.V. All rights reserved.

关键词： graph algorithms packet-switched interconnection networks interconnection networks adversarial queueing theory greedy scheduling protocols network stability

来源：评论

学校读者我要写书评

暂无评论

A characterization of universal stability in the adversarial queuing model

引用

SIAM JOURNAL ON COMPUTING 2004年第1期34卷 41-66页

作者： Alvarez, C Blesa, M Serna, M Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat E-08034 Barcelona Spain

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 NTG-lis (Nearest To Go-Longest In System) protocol.

关键词： interconnection networks adversarial queueing theory greedy scheduling protocols network stability graph algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：