多媒体通信网络中基于优先队列的包调度算法的改进

Improvement of Packet Scheduling Based on Priority Queue in Multimedia Networks

多媒体通信网络的服务质量 (Quality of Service,Qo S)很大程度上依赖于包的调度算法 ,调度算法根据一定的服务原则来决定会话队列中包的优先级及其在输出链路上的发送顺序。本文针对一类以优先队列为基础的包调度算法 ,通过引入临界时间点和临界区间的概念 ,改进堆搜索方式 ,优化队列操作 ,提出了一个分步建堆算法。该算法在通常情况下具有一般堆搜索算法的高效率 ,但在会话突发情况下将建堆操作延迟分步完成 ,增加了建堆操作的动态性和灵活性 。

Quality of service (QoS) in multimedia networks mainly depends on the algorithms of packet scheduling and the packets in session queues are assigned as the priority values and order transmitted in specific sequence according to the service disciplines. This paper focuses on the improvement of the strategy for heap searching and the optimization of the queue operation for a kind of algorithms of packet scheduling based on the priority queue. Then a novel algorithm for constructing heap in multi-steps is proposed. In general case, the improved algorithm has the same efficiency of searching as the common algorithm of heap searching. But in the worst case (session burst), it uses the new strategy to construct the heap, i.e. the process of constructing heap is extended and carried out in many steps. Therefore, a high efficiency of packet searching and utilization ratio of output link is obtained, thanks to the dynamic and flexible way of constructing heap.