高速IP路由器中输入排队调度算法综述

被引：9

作者：

庞斌

贺思敏

高文

机构：

[1] 中国科学院计算技术研究所

[2] 中国科学院计算技术研究所北京

[3] 北京

[4] 哈尔滨工业大学计算机科学与工程系

[5] 黑龙江哈尔滨

[6] 中国科学院研究生院

来源：

软件学报 | 2003年 / 05期

关键词：

路由器; 交换结构; 排队策略; 输入排队; 调度算法; 匹配;

D O I：

10.13328/j.cnki.jos.2003.05.021

中图分类号：

TP393.03 [];

学科分类号：

081201 ; 1201 ;

摘要：

高速IP路由器一般采用基于定长信元的交换结构,其可扩展性和性能分别受排队策略和调度算法的影响.基于输入排队策略的路由器具有良好的可扩展性,但需要一个有效的调度算法的支持,才能保证吞吐率和延迟等性能.主要讨论输入排队调度算法,将现有的调度算法分为4类:最大(无权重)匹配、最大权重匹配、稳定婚姻匹配和确定型调度.对每一类算法,从技术特点和性能指标两个方面进行比较和分析.最后给出了输入排队调度算法的发展趋势.

引用

页码：1011 / 1022

页数：12

共 6 条

[1]

Load balanced Birkhoff–von Neumann switches, part II: multi-stage buffering[J] . Cheng-Shang Chang,Duan-Shin Lee,Ching-Ming Lien.Computer Communications . 2002 (6)

[2] Input-queued router architectures exploiting cell-based switching fabrics [J].

Marsan, MA ;

Bianco, A ;

Giaccone, P ;

Leonardi, E ;

Neri, F .

COMPUTER NETWORKS, 2001, 37 (05) :541-559

[3] The iSLIP scheduling algorithm for input-queued switches [J].

McKeown, N .

IEEE-ACM TRANSACTIONS ON NETWORKING, 1999, 7 (02) :188-201

[4] HIGH-SPEED SWITCH SCHEDULING FOR LOCAL-AREA NETWORKS [J].

ANDERSON, TE ;

OWICKI, SS ;

SAXE, JB ;

THACKER, CP .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1993, 11 (04) :319-352

[5]

Frame-Based matching algorithms for input-queued switches .2 Bianco A,Franceschinis M,Ghisolfi S,et al. Proceedings of the IEEE Workshop on High Performance Switching and Routing (HPSR) . 2002

[6]

Scheduling algorithms for input-queued switches: Randomized techniques and experimental evaluation .2 Goudreau MW,Kolliopoulos SG,and Rao SB. Proceedings of IEEE INFOCOM . 2000

← 1 →