臺灣博碩士論文加值系統

在製作高速網路交換機時，記憶體存取速度是一個重要的問題。為了減少存取記憶體的負擔，增加排線數目或是將記憶體區塊分開以做平行化讀寫都是解決的方法，但也可能造成控制交換機的困難或是規模化的問題。近來許多的研究投注在具有輸入緩衝器的縱橫式交換機上。每個時槽中，縱橫式交換機的連接樣式都可以對應一個排列矩陣。但是輸入緩衝器交換機可能面臨排列前端 (Head of line) 阻礙以及延遲控制困難的問題。在先前的許多研究中，以特殊的輸入緩衝器機制配合加權配對演算法以及交換機內部的加速可以分別解決上述問題。
在最近的研究中提到，以加權式回合輪流演算法可以不用內部加速而達到速率保證及100% 輸出率，但是它必須選取一個訊框長度。訊框長度過大會造成封包延遲，也需要大的記憶體儲存訊框內的連結樣式。訊框過小會使最小能提供的速率太大。所以此方法對於非一致性的流量無法提供一致性的服務保證。
在這篇論文中，只要流量滿足"非超額認購"條件，我們提出一個可以提供非一致性流量一致性的服務保證的演算法。以一個N×N的交換機來說，確認時程演算法的離線計算複雜度是O(N^4.5)。只要確認好時程演算法，它的線上複雜度是O(logN)，而它的線上記憶體複雜度是O(N^3logN)。我們的方法避免了選取訊框長度的問題，並且交換機可以不用內部加速而達到100% 輸出率。
這篇論文的組織如下：第二章將介紹如何使用布可夫-范紐曼分解。第三章將敘述線上演算法及服務保證的性質。第四章我們觀察一些模擬分析的結果。最後討論一些我們演算法可能的應用作為總結。

Based on a decomposition result by Birkhoff and von Neumann for a doubly substochastic matrix, in this paper we propose a scheduling algorithm that is capable of providing service guarantees for input-buffered crossbar switches. Our service guarantees are uniformly good for all non-uniform traffic, and thus imply 100% throughput. The off-line computational complexity to identify the scheduling algorithm is O(N^4.5) for an N×N switch. Once the algorithm is identified, its on-line computational complexity is O(log N) and its on-line memory complexity is O(N^3log N). Neither framing nor internal speedup is required for our approach.

目 錄
摘 要 ………………………………………………………. i
致 謝 ………………………………………………………. ii
目 錄 ………………………………………………………. iii
第一章 簡 介 ………………………………………………. 1
第二章 雙重隨機矩陣之預備 ………………………………. 2
第三章 演算法的描述與分析 ………………………………. 3
第四章 模擬學習 ……………………………………………. 4
第五章 討 論 ………………………………………………. 5
附 錄 英文稿 ………………………………………………. 6

R. Agrawal and R. Rajan, "Performance bounds for
guaranteed and adaptive services," IBM RC 20649, 1996. Also
in Proc. 34th Allerton Conf. on Comm., Cont. \& Comp.,
Monticello, IL, Oct. 1996.
T. Anderson, S. Owicki, J. Saxes and C. Thacker,
"High speed switch scheduling for local area networks," ACM
Trans. on Computer Systems, Vol. 11, pp. 319-352, 1993.
C. Berge, The Theory of Graphs and Its Applications
(translated by A. Doig). New York: Wiely, 1962.
G. Birkhoff, "Tres observaciones sobre el algebra lineal,"
Univ. Nac. Tucum\'an Rev. Ser. A, Vol. 5, pp. 147-151, 1946.
C.S. Chang, "Stability, queue length and delay of deterministic and stochastic queueing networks," IEEE Transactions on
Automatic Control, Vol.39, pp. 913-931, 1994.
C.S. Chang, "On deterministic traffic regulation
and service guarantees: a systematic approach by filtering," IEEE Transactions on Information Theory}, Vol. 44, pp.1097-1110,
1998.
A. Charny, P. Krishna, N. Patel and R. Simcoe, "Algorithms for providing bandwidth and delay guarantees in input-buffered crossbars with speedup," IEEE IWQoS'98, pp. 235-244, Napa, California, 1998.
S.-T. Chuang, A. Goel, N. McKeown and B. Prabhkar, "Matching output queueing with a combined input output queued
switch," Computer Systems Technical Report CSL-TR-97-738,
1997. Available from http://tiny-tera.stanford.edu/~nickm/papers.html.
C. Clos, "A study of nonblocking switching networks,"
BSTJ, Vol. 32, pp. 406, 424, 1953.
R.L.Cruz, "A calculus for network delay, Part I: Network elements in isolation," IEEE Transactions on Information Theory, Vol. 37, pp. 114-131, 1991.
R.L. Cruz, Lecture Notes on Quality of Service Guarantees, 1998.
A. Demers, S. Keshav, and S. Shenkar, "Analysis and simulation of a fair queueing algorithm," in Proc. SIGCOMM'89, pp. 1-12, Austin, TX, Sept. 1989.
L. Dulmage and I. Halperin, "On a theorem of Frobenius-Konig
and J. von Neumann's game of hide and seek,Trans. Roy. Soc.
Canada III(3), Vol. 49, pp. 23-29, 1955.
J. Hui, Switching and Traffic Theory for Integrated Broadband Networks. Boston: Kluwer Academic Publishers, 1990.
A. Hung, G. Kesidis and N. Mckeown, "ATM input-buffered
switches with guaranteed-rate property," Proc. IEEE
ISCC'98 , Athens, pp. 331-335, 1998.
P. Krishna, N.S. Patel, A. Charny and R. Simcoe, "On the speedup required for work-conserving crossbar switches," IEEE IWQoS'98}, pp. 225-234, Napa, California, 1998.
J.Y. Le Boudec, "Application of network calculus to guaranteed
service networks," IEEE Transactions on Information Theory,
Vol. 44, pp. 1087-1096, 1998.
T.T. Lee and C.H. Lam, "Path switching-a quasi-static routing
scheme for large scale ATM packet switches," IEEE Journal on
Selected Areas of Communications, Vol. 15, pp. 914-924, 1997.
A.W. Marshall and I. Olkin, Inequalities: Theory of
Majorization and Its Applications. New York: Academic Press,
1979.
N. McKeown, V. Anantharam and J. Walrand, "Achieving 100% throughput in an input-queued switch," Proc. IEEE INFOCOM'96, pp. 296-302, 1996.
A. Mekkittikul and N. McKeown, "A practical scheduling algorithm to achieve 100% throughput in input-queued switches," Proc. IEEE INFOCOM'98}.
L. Mirsty, Transversal Theory. New York: Academic Press, 1971.
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithm and Complexity. New Jersey:
Prentice-Hall, 1982.
A.K. Parekh and R.G. Gallager, "A generalized processor sharing approach to flow control in integrated service networks: the single-node case," IEEE/ACM Transactions on Networking, Vol. 1, pp. 344-357, 1993.
H. Sariowan, R.L. Cruz and G.C. Polyzos, "SCED: a generalized scheduling policy for guaranteeing quality-of-service,"submitted to IEEE/ACM Transactions on Networking.
M. Schwartz, Broadband Integrated Networks. New Jersey: Prentice Hall, 1996.
D. Stiliadis and A. Varma, "Providing bandwidth guarantees
in an input-buffered crossbar switch," Proc. IEEE INFOCOM'95, pp. 960-968, 1995.
L. Massoulie and J. Robert, "Bandwidth sharing:
objectives and algorithms," Proc. IEEE INFOCOM'99, 1999.
I. Stoica and H. Zhang, "Exact emulation of an output queueing switch by a combined input output queueing switch," IEEE IWQoS'98, pp. 218-224, Napa, California, 1998.
J. von Neumann, "A certain zero-sum two-person game
equivalent to the optimal assignment problem, " Contributions to the Theory of Games, Vol. 2, pp. 5-12, Princeton
University Press, Princeton, New Jersey, 1953.
D. Bertsekas and R. Gallager, Data Networks. Prentice Hall, 1992.