在網際網路下自治系統層級的路徑特性分析研究

Characterization of Internet AS-Level Paths

蔡明倉(Ming-Tsang Tsai)

指導教授 ： 朱浩華

共同指導教授 ： 黃寶儀(Polly Huang)

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.00040

摘要

網際網路路徑的特徵化是重要的，因為它可以幫助網路研究員更加瞭解封包是如何在網路上傳送的，以及讓他們可以更具信心地在真實網路路徑產生的情況下，加以評估所提出來的機制。先前的研究中指出，以路徑長度的觀點來研究大規模的網路路徑行為時，最短路徑是一個合理且簡單的模型。然而，最短路徑路由是否適合一般性的網路模擬，仍是一個公開的問題。
藉由此問題所引發的動機，我們分析網際網路在自治系統層級的路徑，並且發現，即使最短路徑與自治系統層級的路徑長度很相似，但是它們所經過的自治系統層級的連結是不一樣的。進一步的測試顯示，它們會造成不同的網路流量分佈，而且無論代表性的最短路徑與最短決策路徑如何被選擇，此種差異性會一直持續著。我們發現，無論是最短路徑路由或是最短決策路徑路由都無法正確地符合自治系統層級的路徑所造成的網路流量分佈。
為了幫助真實網路路徑的產生，我們提出一個「偏好比率、隨機移動」的模型。此模型是利用 BGP table 來取得偏好比率，藉此選擇路徑的下一步。評估的結果顯示，此模型可以有效地特徵化網際網路在自治系統層級的路徑。

關鍵字

網路 ； 自治系統 ； 路由

並列摘要

Characterization of Internet paths is important because it helps network operators and researchers better understand how packets travel over the Internet, and allows them to evaluate proposed mechanisms with confidence under realistic network path generating conditions. Some researchers have concluded that shortest path routes are reasonable for studying large-scale behavior of network paths in terms of path length. However, whether shortest path routing is suitable for general network simulations remains an open question.

Motivated by this question, we analyze Internet AS-level paths and find that, although shortest paths and Internet AS-level paths are similar in length, they are very different in the AS-level links traversed. Further examination of the distribution of traffic by shortest paths and Internet AS-level paths shows that the difference persists irrespective of whether representative shortest paths or shortest policy paths are chosen. We find that neither shortest path routing nor shortest policy path routing accurately capture the distribution of traffic generated by Internet AS-level paths.

To facilitate the generation of realistic Internet AS-level paths, we propose a preference-ratio random-walk model that leverages BGP routing tables to obtain preference ratios for the selection of subsequent hops. The results of our evaluations show that the proposed model can characterize Internet AS-level paths effectively.

並列關鍵字

Network ； Automonous System ； Routing

參考文獻

[2] H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin, “The

impact of routing policy on internet paths,” the IEEE INFOCOM, pp.

736–742, April 2001.

[3] L. Gao and F. Wang, “The extent of as path inflation by routing policies,”

[4] N. Spring, R. Mahajan, and T. Anderson, “Quantifying the causes of