The Research Of Packet Scheduling Based On Multi-priorities Queues

With the development of Network Technology, various new applications come to exist.These applications often have different QoS requirements on bandwidth and delay. It is a hot research topic how to support these requirements in network. Traffic shaping and packet scheduling are often employed to solve these problems.In this paper, token bucket algorithm is discussed in detail, especially its parameters for traffic shaping. Then Single Rate Three Color Marker and Two Rate Three Color Marker provided by IETF are introduced. Besides, a new token bucket idea combining with scheduler is given.Packet scheduling can provide different QoS guarantees for different businesses. Based on the analysis of associated scheduling algorithms, a PQBEDF(priority queue based on EDF) algorithm(a dynamic priority scheduling algorithm combining time delay)is introduced. And a PQBEDF_R(PQBEDF_Return) algorithm is proposed. In the PQBEDF_R algorithm, a counter is introduced for each queue. The counter is used to count the service times of the queue in the state of the highest priority, and the priority of the queue returns to its initial value according to relevant disciplines. The algorithm can avoid the possibility of priorities being identical for a long period and maintain certain relativities for priorities, so it can provide guaranteed and differentiated services for various kinds of businesses to certain extent. Thus a certain fairness can be achieved. Based on the above study, a PQBEDF_R algorithm with token bucket for shaping is proposed. A token bucket is added for each queue to shape. The packets are scheduled after shaping. According to the need of the scheduler, token bucket is modified. Communication Mechanism between token buckets is proposed and their parameters are dynamically adjusted with the number of packets in their buffers. A model design is provided and analysed for the method combing the token bucket and PQBEDF_R algorithm. As a result, the PQBEDF_R with token bucket can limit the bandwidths of individual flows and be beneficial to the fairness of bandwiths sharing for them. Thus it guarantees the quality of service for various different businesses.Finally, the simulation is implemented with OPNET. Fairness, percent of packet loss, and time delay are analysed for PQBEDF, PQBEDF_R and PQBEDF_R with token bucket, and the theory above is verified.