一种简单的VOQ交换机时延确保分组调度算法

张福阳; 熊庆旭

一种简单的VOQ交换机时延确保分组调度算法

张福阳¹,
熊庆旭²

1.
南昌大学信息工程学院, 南昌 330031
2. 北京航空航天大学电子信息工程学院, 北京 100191

详细信息

作者简介:
张福阳(1966-),男,江西抚州人,副教授,zfuyang@126.com.

中图分类号: TP 393
计量
- 文章访问数: 3330
- HTML全文浏览量: 253
- PDF下载量: 1362
- 被引次数: 0
出版历程
- 收稿日期: 2007-11-15
- 网络出版日期: 2008-11-30

Simple scheduling algorithm for delay guarantee in VOQ architecture switches

Zhang Fuyang¹,
Xiong Qingxu²

1.
School of Information Engineering, Nanchang University, Nanchang 330031,China
2. School of Electronics and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China

摘要

摘要: 采用EDF(Earliest Deadline First)与轮询结合的方法,提出了一种简单的VOQ(Virtual Output Queueing)分组调度算法提供基于流的时延确保.VOQ队列采用EDF的策略裁决分组流的竞争,输入输出端口采用轮询方式匹配.此时VOQ中分组到达至成为头分组的时间以及分组成为头分组至传输到相应输出端口的时间,分别对应于OQ中的分组排队等待时间及服务时间.通过对所得算法详细的理论分析,给出了流时延界及流分组到达的显性关系.更为重要的是,本文的理论结果不仅为设计更为有效的算法奠定了基础,同时为判别不同流的时延要求是否冲突提供了一种新的直接分析的手段.
- 分组调度 /
- 交换机 /
- 时延确保 /
- 虚拟输出排队
Abstract: Combining the earliest deadline first (EDF) policy and round robin manner, a simple scheduling algorithm was proposed to provide flow-based deterministic delay guarantee in virtual output queueing (VOQ) architecture switches.The EDF policy was employed to arbitrate the flow competitions in VOQ queues, and the round robin strategy was used to build input and output matching. In this case, the interval time between a packet arrival and that when it becomes the head cell in the VOQ, and the time from the packet becomes the head cell to it has been conveyed to the correspond output can be regard as the queuing time and service time in OQ architecture, respectively. The relation between the delay bounds and the packet inter-arrival times were derived. More important, the obtained results not only pave the way for design of more efficient algorithms, but also provide a novel approach to estimating that if there exist conflicts among the distinct delay bounds or not.
- packet scheduling /
- switches /
- delay guarantee /
- virtual output queueing

HTML全文

参考文献(1)

[1] 熊庆旭.输入排队结构交换机分组调度研究 [J].通信学报,2005,26(6):118-129 Xiong Qingxu. Research on packet scheduling in input-queued switches [J]. Journal of China Institute of Communications, 2005, 26(6):118-129(in Chinese) [2] Li S, Ansari N. Input-queued switching with QoS guarantees // IEEE INFOCOM -99. New York:IEEE Inc,1999:1152-1159 [3] Hung A, Kesidis G, Mckeown N, et al. ATM input-buffered switches with guaranteed-rate property // IEEE ISCC -98. Athens, Greece:IEEE Inc, 1998:331-335 [4] Rai I A, Alanyali M. Uniform weighted round robin scheduling algorithms for input queued switches // IEEE ICC-01. Helsinki, Finland:IEEE Inc, 2001:2028-2032 [5] Chang C S, Chen W J, Huang H Y, et al. On service guarantees for input buffered crossbar switches: a capacity decomposition approach by Birkhoff and von Neumann // IEEE IWQoS'99. London, England:IEEE Inc, 1999:79-86 [6] Li J,Ansari N. QoS guaranteed input queued scheduling algorithms with low delay // IEEE HPSR'01. Dallas, TX, USA:IEEE Inc, 2001:412-414 [7] Chang C S, Lee D S, Yue C Y, et al. Providing guaranteed rate service in the load balanced Birkhoff-von Neumann switches // IEEE INFOCOM-03. San Francisco, CA, USA:IEEE Inc, 2003:1662-1632 [8] Lee Hyoung-II. A two-stage switch with load balancing scheme maintaining packet sequence [J]. IEEE Communications Letters, 2006, 10(4):290-292 [9] Lee Yong, Lou Jianyu, Luo Junzhou, et al. An efficient packet scheduling algorithm with deadline guarantees for input-queued switches [J]. IEEE/ACM Trans on Networking, 2007, 15(1):212-225 [10] Ferrari D, Verma D C. A scheme for real-time channel establishment in wide-area networks [J]. IEEE J SAC, 1990, 8(3): 368-379 [11] Bonuccelli M A, Clò M C. Scheduling of real-time messages in optical broadcast-and-select networks [J]. IEEE/ ACM Trans Networking, 2001, 9(5): 541-552

施引文献

资源附件(0)

访问统计