MNCM a new class of efficient scheduling algorithms for input-buffered switches with no speedup

被引:0
作者
Tabatabaee, V [1 ]
Tassiulas, L [1 ]
机构
[1] Univ Maryland, Dept Elect & Comp Engn, College Pk, MD 20742 USA
来源
IEEE INFOCOM 2003: THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-3, PROCEEDINGS | 2003年
关键词
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, we use fluid model techniques to establish some new results for the throughput of input-buffered switches. In particular, we introduce a new class of deterministic maximal size matching algorithms that achieves 100% throughput. Dai and Prabhakar [3] has shown that any maximal size matching algorithm with speedup of 2 achieves 100% throughput. We introduce a class of maximal size matching algorithms that we call them maximum node containing matching (MNCM) algorithms, and prove that they have 100% throughput with no speedup. We also introduce a new weighted matching algorithm, maximum first matching (MFM) with complexity O(N-2.5) that belongs to MNCM. MFM, to the best of our knowledge, is the lowest complexity deterministic algorithm that delivers 100% throughput. The only assumption on the input traffics is that they satisfy the strong law of large numbers. Besides throughput, average delay is the other key performance metric for the input-buffered schedulers. We use simulation results to compare and study the delay performance of MFM. The simulation results demonstrate promising delay performance for MFM.
引用
收藏
页码:1406 / 1413
页数:8
相关论文
共 7 条
[1]   THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].
EDMONDS, J ;
KARP, RM .
JOURNAL OF THE ACM, 1972, 19 (02) :248-&
[2]  
Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019
[3]   INPUT VERSUS OUTPUT QUEUING ON A SPACE-DIVISION PACKET SWITCH [J].
KAROL, MJ ;
HLUCHYJ, MG ;
MORGAN, SP .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1987, 35 (12) :1347-1356
[4]   The iSLIP scheduling algorithm for input-queued switches [J].
McKeown, N .
IEEE-ACM TRANSACTIONS ON NETWORKING, 1999, 7 (02) :188-201
[5]   QoS provisioning and tracking fluid policies in input queueing switches [J].
Tabatabaee, V ;
Georgiadis, L ;
Tassiulas, L .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2001, 9 (05) :605-617
[6]   STABILITY PROPERTIES OF CONSTRAINED QUEUING-SYSTEMS AND SCHEDULING POLICIES FOR MAXIMUM THROUGHPUT IN MULTIHOP RADIO NETWORKS [J].
TASSIULAS, L ;
EPHREMIDES, A .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1992, 37 (12) :1936-1948
[7]  
[No title captured]