Research On Packet Scheduling Algorithm And Admission Control Scheme

With rapid development of network technology and extensive popularity of network application, providing QoS guarantee to various traffic has attracted significant attention. QoS depends on two essential mechanism, one is bandwidth allocation, the other is network service discipline. In the packet switching network, packet scheduling algorithms in the routers and switches decide how to serve packets, admission control algorithms decide bandwidth reservation and release. Therefore packet scheduling and admission control algorithms play a key role in QoS guarantee. This dissertation investigates these problems. The major achievements are outlined as follows.1.A new generalized scheduling model named GSS is presented. We prove the well known GPS model belongs to GSS. In the GSS model, system may have surplus service ability during some periods. In such periods some connections can lend their bandwidth to other connections that need more service to improve their QoS. A new fluid scheduling model SPF is proposed for this case. We prove SPF belongs to GSS and it has the same delay property as GPS. The ability of SPF to lend bandwidth is analyzed. It is shown that SPF can lend largest bandwidth among all GSS algorithms and it can lend this bandwidth for the longest time. This property leads to a high bandwidth utilization in SPF system .2. A profound study for the admission control scheme of Virtual Clock algorithm is made. We find the existing scheme can not guarantee the delay property of Virtual Clock. The reason is the existing scheme does not consider the case that connections may be set up or torn down and does not give the rule to release connections' bandwidth. We prove Virtual Clock algorithm is close to SPF model. So the idea of SPF is used to study the admission control scheme of Virtual Clock. Two mechanism is presented. One is based on alive period, the other is its improved scheme. The former mechanism is easy to be implemented, the later improves the bandwidth utilization. It is proved that these two schemes can fully guarantee the delay property of Virtual Clock . The simulation also verifies this result.3.We find free bandwidth is unreasonably used in the PFQ algorithms. So a new scheduling algorithm named FBRS is proposed to resolve this problem. There are two servers in the FBRS system . One is m server which guarantees the delay requirement of each connection, the other is f server used to distribute free bandwidth. FBRS can makeresidual bandwidth be shared on connections' demand, its other performance is also perfect. The delay property of FBRS is best among PFQ algorithms. The fairness of m server and f server achieve the best or near-best performance of PFQ algorithms. The computation complexity of FBRS is very low. In this dissertation, we also present two deduced algorithms. One is a generalized PFQ algorithm, the other can reduce packet lost rate in the system.4.A new round robin algorithm. LFRR is proposed. LFRR can make slots allocated to a connection be evenly distributed in the schedule table. So the delay performance of WRR is improved. In LFRR. connections with same weight are aggregated into a group. The number of groups is much smaller than the number of actual connections. LFRR deals with these groups. When LFRR allocates slots, groups with large weight have high priority to possess slot, instead of choosing minimum value from each connection's time stamp to decide the slot allocation. So the complexity of LFRR is low. A hardware implementation for LFRR is proposed. Parallel comparator and encoder lead to a fast construction of schedule table. Theoretical analysis and simulation show that the delay property of LFRR is much better than that of WRR.