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

作     者：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 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2004年第90卷第5期

页      面：261-266页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Catalan Research Council of the Generalitat de Catalunya, (2001FI-00659) Spanish MCyT, (TIC2001-1586-C03-01) Comunidad de Madrid, (07T/0022/2003) European Commission, EC, (IST-2001-33116) Generalitat de Catalunya Comisión Interministerial de Ciencia y Tecnología, CICYT, (TIC-2001-4917-E, TIC2002-04498-C05-03) Universidad Rey Juan Carlos, URJC, (PPR-2003-37) 

主　　题：graph algorithms packet-switched interconnection networks interconnection networks adversarial queueing theory greedy scheduling protocols network stability 

摘      要：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.