高速交換機之服務品質保證排程交換技術

Abstract

隨著網路流量的快速增加，高速交換機是未來寬頻網路的一個重要元件，而設計高容量交換機最重要的課題就是合適的交換架構。此外，未來寬頻網路也必需具備提供即時性服務（如語音、音樂、影像等等）的能力，其中的關鍵技術就是如何有效地排程這些各式各樣的訊務。因此，本論文主要研究這兩個關鍵技術：交換架構與訊務排程。 為了設計大容量交換機，我們必須在效率以及實現這兩方面同時考量。近來有研究人員提出將縱橫式交換架構加速的方式，以消除前端壅塞的現象，而因為加速的關係，在輸出埠也需要緩衝器，所以形成一個混何輸入/輸出佇列的架構，為了增加交換系統的效能，如何有效地使用加速的縱橫式架構是一個關鍵。在本論文中，我們提出了一個新的輸入/輸出配對方法，稱為Least Cushion First/Most Urgent First (LCF/MUF) 演算法，並證明它在加速兩倍的情況下，可以完全仿效採用任何排程方法的輸出佇列交換系統。另外，我們也實現利用我們的配對法來仿效一個採用絕對優先權排程法的輸出佇列交換系統。 在本論文中，我們也提出了一個新的排程方法，稱為Delay-Bound Monotonic with Average Rate Reservation (DM/ARR)。我們除了推導出它相對應的允入控制，並證明了它具有最小輸出叢聚的特性，在數值的比較上，也可看出它可以接受的連線各數與最佳的Earliest Deadline First排程法相距不遠。此外，封包版本的排程器在論文中也有討論到。 最後我們探討了訊務整型單調排程器的允入控制，將VBR訊務的特性考慮進來，推導在每個節點上的允入控制，並且設計出快速允入控制程序，由實驗例子上看出我們的允入控制可以接受更多的訊務連線。

High-speed switch is an essential component for future broadband network to handle rapidly growing traffic. To design a switch of a very high capacity, it is important to choose a proper switch architecture. Besides, supporting real-time applications such as voice, audio, and video is an important and necessary feature of future broadband networks. To support these real-time connections, a proper service scheduling algorithm is indispensable to efficiently handle the aggregate traffic from multiple connections. Hence, in this thesis, we focus on the two important issues: switch architecture and traffic scheduling. From the viewpoints of efficiency and implementation, combined input output queued (CIOQ) architecture such as crossbar with speedup has recently been proposed to build a large capacity switch for broadband integrated services networks. In this thesis, we propose a new matching algorithm called the least cushion first/most urgent first (LCF/MUF) algorithm and formally prove that a CIOQ switch with a speedup factor of 2 can exactly emulate an OQ switch which adopts any service discipline for cell transmission. A potential implementation of our proposed matching algorithm for strict priority service discipline is also presented. A new traffic scheduling algorithm, called the Delay-Bound Monotonic with Average Rate Reservation (DM/ARR), is also proposed in this thesis. We derive its corresponding admission criterion and prove that, among all possible scheduling algorithms that satisfy the delay bound requirements of established connections, DM/ARR results in the minimum output burstiness. Numerical results show that the admission region of the DM/ARR algorithm is close to that of the earliest deadline first algorithm. A packetized version is studied for ATM networks. We also study the admission issue for the traffic-shaped rate monotonic scheduler which consists of traffic shapers and a rate monotonic scheduler. Traffic from each connection is shaped before entering the rate monotonic scheduler. We present an efficient admission criterion for bursty or VBR sources that are regulated with the leaky bucket regulators. Our admission criterion takes into consideration of traffic characteristics. Based on the admission criterion, we develop a fast admission control procedure. Numerical results show that, compared with the conservative criterion which assumes periodic cell arrivals, system utilization can be largely improved using our admission criterion.