摘要
1 引言
宽带综合业务网要求能给不同的应用提供不同的服务质量(QoS),其中分组调度算法作为网络路由器中的一个重要组件起着相当关键的作用.传统的Internet是基于尽力而为(best-effort)模型实现的,该模型采取先来先服务(FCFS)的分组调度算法,这种模型具有实现简单的特点,它在假定所有应用互相协作的情况下工作得非常好.但当网络发生拥塞时,实时应用的服务质量往往得不到保证.同时,连接间的隔离性能也非常差,吞吐量大的连接得到更多的服务,某些不良行为的连接可能造成其他连接的服务质量急剧下降.
Packet scheduling algorithm is one of crucial technologies of routers in high speed networks. In this paper we first discuss the limitation of some existing packet scheduling algorithms,then show the quantitative relationships between the GPS system and its corresponding packet WFQ system. A novel packet scheduling algorithm is proposed. It is proven to have following properties: (1) it ensures fair allocation of bandwidth among all sessions; (2) it provides deterministic delay upper bounds to a session whose traffic is constrained by a leaky bucket; (3) it has a relatively low asymptotic complexity of O(logN); (4)it has a relatively low Worst-case Fair Index(WFI). So it can be deployed in routers of high speed networks.
出处
《计算机科学》
CSCD
北大核心
2001年第11期72-76,共5页
Computer Science
基金
国家九五重点攻关项目基金
信息产业部生产发展基金
