Abstract
In this thesis we study the real-time traffic scheduling problem in high speed ATM networks. One of the most important QoS requirements of real-time traffic is the delay guarantee. A real-time cell is regarded as lost if expiring its deadline. The QoS requirement of different cell loss priority is also considered in the scheduling problem. The scheduling operation is performed at the ATM multiplexers and at the output buffers of ATM switches. A good scheduling algorithm should serve as more cells as possible and handle the cell loss according to their priorities. One of the major performance measures of a scheduling algorithm is the weighted loss rate. The real-time traffic scheduling algorithm M-HEUR has been proposed. The M-HEUR algorithm has been shown to be near optimal in minimzing the weighted cell loss rate.But the M-HEUR algorithm has the Out-of- sequence problem and high computational complexity. In this thesis, we propose an improved M-HEUR (IMH) scheduling algorithm to solve the out-of-sequence problem. Furthermore, we propose an IMH-N scheduling algorithm. Its computational complexity is reduced from O(NB) to O(N+B) where N is the multiplexing number of input links, and B is the size of the buffer.