The Complexity of Restricted Variants of the Stable Paths Problem

• Autorzy: Donnelly K. , Kfour A. , Lapets A.
• Języki publikacji: EN

Abstrakty

EN

Interdomain routing on the Internet is performed using route preference policies specified independently and arbitrarily by each autonomous system (AS) in the network. These policies are used in the border gateway protocol (BGP) by each AS when selecting next-hop choices for routes to each destination. Conflicts between policies used by different ASs can lead to routing instabilities that, potentially, cannot be resolved regardless of how long BGP runs. The stable paths problem (SPP) is an abstract graph theoretic model of the problem of selecting next-hop routes for a destination. A solution to this problem is a set of next-hop choices, one for each AS, that is compatible with the policies of each AS. In a stable solution each AS has selected its best next-hop if the next-hop choices of all neighbors are fixed. BGP can be viewed as a distributed algorithm for solving an SPP instance. In this report we consider a family of restricted variants of SPP, which we call f-SPP. We show that several natural variants of f-SPP are NP-complete. This includes a variant in which each AS is restricted to one of only two policies and each of these two policies is based on a monotonic weight aggregation function. Furthermore, we show that for networks with particular topologies and edge weight distributions, there exist efficient centralized algorithms for solving f-SPP.

Słowa kluczowe

EN

stable paths problem

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 103, nr 1-4
• Strony: 69--87
• Opis fizyczny: Bibliogr. 14 poz., tab., wykr.

Twórcy

autor

Donnelly K.

autor

Kfour A.

autor

Lapets A.

• CS Dept., Boston University, 111 Cummington St., Boston, MA 02215, USA,

Bibliografia

• [1] Donnelly, K., Kfoury, A.: On the Stable Paths Problem and a Restricted Variant, Technical Report BUCSTR- 2008-001, CS Dept., Boston University, January 10 2008.
• [2] Gao, L., Rexford, J.: Stable internet routing without global coordination, IEEE/ACM Trans. Netw., 9(6), 2001, 681-692, ISSN 1063-6692.
• [3] Griffin, T., Shepherd, F. B., Wilfong, G. T.: Policy Disputes in Path-Vector Protocols, Proceedings of the 7th Annual International Conference on Network Protocols, Toronto, Canada, November 1999.
• [4] Griffin, T., Wilfong, G. T.: A Safe Path Vector Protocol, INFOCOM, 2000.
• [5] Griffin, T. G., Shepherd, F. B., Wilfong, G.: The stable paths problem and interdomain routing, IEEE/ACM Trans. Netw., 10(2), 2002, 232-243, ISSN 1063-6692.
• [6] Kahn, A. B.: Topological sorting of large networks, Communications of the ACM, 5(11), 1962, 558-562, ISSN 0001-0782.
• [7] Kfoury, A., Lapets, A.: The NP-completeness of the Restricted Stable Paths Problem with Three Aggregating Functions, Technical Report BUCS-TR-2010-004, CS Dept., Boston University, March 2010.
• [8] Lapets, A.: The complexity of natural extensions of efficiently solvable problems, Technical Report BUCSTR-2010-005, CS Dept., Boston University, March 2010.
• [9] Schapira, M.: The Economics of Internet Protocols, Ph.D. Thesis, Hebrew University of Jerusalem, 2008.
• [10] Sipser, M.: Introduction to the Theory of Computation, International Thomson Publishing, 1996, ISBN 053494728X.
• [11] Tarjan, R. E.: Edge-disjoint spanning trees and depth-first search, Acta Informatica, 6(2), 1976, 171-185, ISSN 0001-5903.
• [12] Valiant, L.: The relative complexity of checking and evaluating, in: Inf. Process. Lett., 5:20-23, 1976.
• [13] Villamizar, C., Chandra, R., Govindan, R.: BGP Route Flap Damping, 1998, RFC 2439.
• [14] Yilmaz, S., Matta, I.: An Adaptive Policy Management Approach to BGP Convergence, Technical Report BUCS-TR-2005-028, CS Dept., Boston University, July 7 2005.