| A nearly optimal packet scheduling algorithm for input queued switches with deadline guarantees | |
| Zhang, Baoxian1; Wan, Xili2; Luo, Junzhou3; Shen, Xiaojun2 | |
| 刊名 | Ieee transactions on computers
 |
| 2015-06-01 | |
| 卷号 | 64期号:6页码:1548-1563 |
| 关键词 | Input-queued switch Packet scheduling Quality of service Deadline guarantee Minimum cost maximum flow Real time scheduling |
| ISSN号 | 0018-9340 |
| DOI | 10.1109/tc.2014.2329695 |
| 通讯作者 | Zhang, baoxian(bxzhang@ucas.ac.cn) |
| 英文摘要 | Deadline guaranteed packet scheduling for switches is a fundamental issue for providing guaranteed qos in digital networks. it is a historically difficult np-hard problem if three or more deadlines are involved. all existing algorithms have too low through put to be used in practice. a key reason is they use packet deadlines as default priorities to decide which packets to drop whenever conflicts occur. although such a priority structure can ease the scheduling by focusing on one deadline at a time, it hurts the throughput greatly. since deadlines do not necessarily represent the actual importance of packets, we can greatly improve the throughput if deadline induced priority is not enforced. this paper first presents an algorithm that guarantees the maximum throughput for the case where only two different deadlines are allowed. then, an algorithm called iterative scheduling with no priority (isnop) is proposed for the general case where k>2 different deadlines may occur. not only does this algorithm have dramatically better average performance than all existing algorithms, but also guarantees approximation ratio of 2. isnop would provide a good practical solution for the historically difficult packet scheduling problem. |
| WOS关键词 | TIME-SLOT ASSIGNMENT ; CONSTRAINTS ; FRAMEWORK ; NETWORKS |
| WOS研究方向 | Computer Science ; Engineering |
| WOS类目 | Computer Science, Hardware & Architecture ; Engineering, Electrical & Electronic |
| 语种 | 英语 |
| 出版者 | IEEE COMPUTER SOC |
| WOS记录号 | WOS:000354414500004 |
| 内容类型 | 期刊论文 |
| URI标识 | http://www.corc.org.cn/handle/1471x/2376532 |
| 专题 | 中国科学院大学 |
| 通讯作者 | Zhang, Baoxian |
| 作者单位 | 1.Univ Chinese Acad Sci, Res Ctr Ubiquitous Sensor Networks, Beijing 100049, Peoples R China 2.Univ Missouri Kansas City, Sch Comp & Engn, Kansas City, MO 64110 USA 3.Southeast Univ, Sch Comp Sci & Engn, Nanjing 210096, Jiangsu, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhang, Baoxian,Wan, Xili,Luo, Junzhou,et al. A nearly optimal packet scheduling algorithm for input queued switches with deadline guarantees[J]. Ieee transactions on computers,2015,64(6):1548-1563. |
| APA | Zhang, Baoxian,Wan, Xili,Luo, Junzhou,&Shen, Xiaojun.(2015).A nearly optimal packet scheduling algorithm for input queued switches with deadline guarantees.Ieee transactions on computers,64(6),1548-1563. |
| MLA | Zhang, Baoxian,et al."A nearly optimal packet scheduling algorithm for input queued switches with deadline guarantees".Ieee transactions on computers 64.6(2015):1548-1563. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论