大型網路狀態取決路由：提升最短路徑路由的個案研究

Abstract

在普通網路上，我們關注於使用馬可夫決策過程(Markov Decision Process)和最大流量演算法，來找到一種路由的方式作為提升原本的最短路徑路由的效能，並且同時提供在大型網路上的可行性。本篇論文中，我們研究並列舉了不同觀念下的其他路由方法。我們的方法則是將系統模擬成可意識到資源需求的馬可夫決策過程，並將路由資訊粗化的觀念同時加入於其中。因此依據最近一個粗化過的路由訊息，這個方法能夠決定每個服務連結該走的路徑。接著模擬網路時，是針對不同的波松分布的，找一個特殊的網路來作例子。最後與最短路徑路由比較，我們的方法能夠達到減低網路上流量阻塞的機率，並且減低了在作路由時的過度通訊花費。

We have an interest in using Markov decision theory and Maxflow algorithm to find a policy for boosting shortest-path routing and providing network scalability. In this thesis, we study and list other routing strategies with different concepts. Our problem is modeled as a Markov decision process with an awareness of resource requirements and a certain extent of aggregation is added at the same time. This policy determines the route of each connection based on the latest aggregated information. A case study of a network is simulated with different Possion traffic rates according above assumptions. Finally we arrive at the goal of reducing the blocking probability of the network and the communication overhead can also be endured.