具優先權之網路自私路由

Prioritized Selfish Routing

林世鵬(Shih-Peng Lin)

指導教授 ： 王大為 ； 呂學一

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

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

摘要

在本論文中, 我們定義並研究了一種新的自私路由模型。在原來的模型中, 我們被給予一個網路, 以及欲流過此網路的交通流量。模型中的交通流量是由非常多的使用者所聚集起來的, 而且這些使用者不會彼此合作, 每個使用者都想找出能通過這個網路時間最短的路徑。在這個情況下, 根據賽局理論, 這些使用者流過網路的方式最終會達到一個平衡點, 稱為「納什平衡點」; 然而, 這個平衡點的系統效能會比套用最佳解時的系統效能為差。但我們觀察到, 若使交通流量能套用常見的「優先權」觀念, 使得某些使用者在移動時能感受到較短的時間, 我們證明其系統效能會有顯著的提升。

我們在此論文中證明了具優先權的納什平衡點之系統效能會較無優先權時的平衡點好, 也證明了具優先權納什平衡點的系統效能甚至會超過無優先權時的最佳解, 如果沒有超過, 具優先權平衡點的效能至少也與無優先權最佳解的效能相等。我們也給予了具優先權納什平衡點對系統效能的改進在對於不同網路時間設定時的上界, 此結果代表著具優先權納什點所最大能改善系統效能的程度與最佳解的程度是相同的。

關鍵字

自私路由 ； 納什平衡 ； 計算賽局理論

並列摘要

In this work, we introduce and study a prioritized model of selfish routing. In the original model, there is a network in which the latency experienced by the users in the network on an edge is a function of the edge congestion, and each user will route itself on a minimum latency path without coordination. It is well known that the outcome of the selfish routing does not optimize the system performance. However, the performance can be improved by prioritizing the users. That is, some users are given high priority, and the remaining are given low priority. While the high users are traveling through the network, they will not be inflenced by the low priority ones. But when the low priority users are routing, they will be effected by both kinds of users.

We show that such a prioritized model performs better than the nonprioritized one. While comparing to the optimal solution, we show that the performance of the prioritized model will not be worse. We also study the maximum possible benefit achievable by the prioritized model, which is 1/4 times the nonprioritized one in networks with linear latency functions, and could be arbitrarily small in the general case. The latter results show the coincidence between the best achievable performance of the prioritized model and the optimal solution in the original model.

並列關鍵字

selfish routing ； Nash equilibrium ； algorithmic game theory

參考文獻

[1] H. Z. Aashtiani and T. L. Magnanti. Equilibria on a congested transportation network. SIAM Journal on Algebraic and Discrete Methods, 2(3):213–226, 1981.

[3] R. Cocchi, S. Shenker, D. Estrin, and L. Zhang. Pricing in computer networks: motivation, formulation, and example. IEEE/ACM Transactions on Networking, 1(6):614–627, 1993.

[5] S. C. Dafermos. Traffic equilibrium and variational inequalities. Transportation Science, 14(1):42–54, 1980.

[7] P. Dubey. Inefficiency of nash equilibria. Mathematics of Operations Researc, 11(1):1–8, 1986.

[8] M. Florian. Nonlinear cost network models in transportation analysis. Mathematical Programming Study, 26:167–196, 1986.