{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T06:58:34Z","timestamp":1760425114664,"version":"3.41.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2008TFBWL4"],"award-info":[{"award-number":["2008TFBWL4"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Advanced tracking system in intermodel freight tarnsprotation","award":["RBIP06BZW8"],"award-info":[{"award-number":["RBIP06BZW8"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>\n            Most routing protocols guarantee convergence to a stable routing state. That is, in the absence of topology or configuration changes, each router will eventually find a stable route to any destination. However, this is not the case for policy-based routing protocols, for example, the BGP protocol used as a\n            <jats:italic>de facto<\/jats:italic>\n            standard for interdomain routing.\n          <\/jats:p>\n          <jats:p>The interaction of not-so-complex BGP configurations can cause permanent oscillations of routing. Several models and algorithms have been proposed in the literature to study routing oscillations. This article surveys state-of-the-art contributions in this field, with a special emphasis on algorithmic and combinatorial aspects.<\/jats:p>","DOI":"10.1145\/2333112.2333121","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T22:21:06Z","timestamp":1347402066000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On the stability of interdomain routing"],"prefix":"10.1145","volume":"44","author":[{"given":"Luca","family":"Cittadini","sequence":"first","affiliation":[{"name":"Roma Tre University, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe Di","family":"Battista","sequence":"additional","affiliation":[{"name":"Roma Tre University, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massimo","family":"Rimondini","sequence":"additional","affiliation":[{"name":"Roma Tre University, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,9,7]]},"reference":[{"volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS).","author":"Ahronovitz E.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Alaettinoglu C. Villamizar C. Gerich E. Kessens D. Meyer D. Bates T. Karrenberg D. and Terpstra M. 1999. Routing Policy Specification Language (RPSL). IETF RFC 2622.   Alaettinoglu C. Villamizar C. Gerich E. Kessens D. Meyer D. Bates T. Karrenberg D. and Terpstra M. 1999. Routing Policy Specification Language (RPSL). IETF RFC 2622.","DOI":"10.17487\/rfc2622"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633048"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Bates T. Chandra R. and Chen E. 2000. BGP route reflection\u2014An alternative to full mesh IBGP. IETF RFC 2796.   Bates T. Chandra R. and Chen E. 2000. BGP route reflection\u2014An alternative to full mesh IBGP. IETF RFC 2796.","DOI":"10.17487\/rfc2796"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Bremler-Barr A.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159957"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2008.080921"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1403007.1403022"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Chau C.-K.","key":"e_1_2_1_9_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Chiesa M.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2010.5762760"},{"key":"e_1_2_1_12_1","unstructured":"Cittadini L. Di Battista G. and Rimondini M. 2008a. How stable is stable in interdomain routing: Efficiently detectable oscillation-free configurations. Tech. rep. RT-DIA-132-2008 Dipartimento di Informatica e Automazione Universit\u00e0 degli Studi Roma Tre.  Cittadini L. Di Battista G. and Rimondini M. 2008a. How stable is stable in interdomain routing: Efficiently detectable oscillation-free configurations. Tech. rep. RT-DIA-132-2008 Dipartimento di Informatica e Automazione Universit\u00e0 degli Studi Roma Tre."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92248-3_1"},{"volume-title":"Proceedings of the Annual International Conference on Network Protocols (ICNP).","author":"Cittadini L.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1688933.1689011"},{"volume-title":"Proceedings of the International Symposium on Self-Stabilizing Systems.","author":"Cobb J. A.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.892878"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Ee C. T. Ramachandran V. Chun B.-G. Lakshminarayanan K. and Shenker S. 2007. Resolving inter-domain policy disputes. Tech. rep. UCB\/EECS-2007-27 EECS Department University of California Berkeley.  Ee C. T. Ramachandran V. Chun B.-G. Lakshminarayanan K. and Shenker S. 2007. Resolving inter-domain policy disputes. Tech. rep. UCB\/EECS-2007-27 EECS Department University of California Berkeley.","DOI":"10.1145\/1282380.1282399"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Elmokashfi A.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the ACM CoNEXT Conference.","author":"Elmokashfi A.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Fabrikant A.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Fabrikant A.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the Workshop on Hot Topics in Networks (HotNets).","author":"Feamster N.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","unstructured":"Feamster N. Johari R. and Balakrishnan H. 2005. Stable policy routing with provider independence. Tech. rep. MIT-LCS-TR-981 MIT.  Feamster N. Johari R. and Balakrishnan H. 2005. Stable policy routing with provider independence. Tech. rep. MIT-LCS-TR-981 MIT."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.896531"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0134-7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Feigenbaum J. Schapira M. and Shenker S. 2007. Distributed algorithmic mechanism design. In Algorithmic Game Theory N. Nisan T. Roughgarden E. Tardos and V. V. Vazirani Eds. Cambridge University Press New York NY 363--384.  Feigenbaum J. Schapira M. and Shenker S. 2007. Distributed algorithmic mechanism design. In Algorithmic Game Theory N. Nisan T. Roughgarden E. Tardos and V. V. Vazirani Eds. Cambridge University Press New York NY 363--384.","DOI":"10.1017\/CBO9780511800481.016"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Gao L.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/339331.339426"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592583"},{"volume-title":"Proceedings of the International Conference on Communication Systems and Networks (COMSNETS).","year":"2010","author":"Griffin T. G.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Griffin T. and Huston G. 2005. BGP wedgies. IETF RFC 4264.  Griffin T. and Huston G. 2005. BGP wedgies. IETF RFC 4264.","DOI":"10.17487\/rfc4264"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863964"},{"volume-title":"Proceedings of the Annual International Conference on Network Protocols (ICNP).","author":"Griffin T. G.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.993304"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080091.1080094"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316231"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633028"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Griffin T. G.","key":"e_1_2_1_39_1"},{"volume-title":"Proceedings of the Annual International Conference on Network Protocols (ICNP).","author":"Griffin T. G.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2010.5762759"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Haxell P. E.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","unstructured":"Huston G. 2011. BGP routing table analysis reports. http:\/\/bgp.potaroo.net\/.  Huston G. 2011. BGP routing table analysis reports. http:\/\/bgp.potaroo.net\/."},{"volume-title":"Proceedings of the Annual International Conference on Network Protocols (ICNP).","author":"Jaggard A. D.","key":"e_1_2_1_44_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Jaggard A. D.","key":"e_1_2_1_45_1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2006.320220"},{"volume-title":"Proceedings of the Symposium on Innovations in Computer Science (ICS).","author":"Jaggard A. D.","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.839934"},{"volume-title":"Proceedings of the DIMACS\/DyDAn Workshop on Secure Internet Routing.","year":"2008","author":"Kintali S.","key":"e_1_2_1_49_1"},{"volume-title":"Proceedings of the International Conference on Computer Communication Networks (ICCCN).","author":"Klockar T.","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/11922377_9"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374388"},{"volume-title":"Proceedings of the IEEE Conference and Exhibition on Global Telecommunications (GlobeCom).","author":"Luo J.","key":"e_1_2_1_53_1"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633047"},{"volume-title":"Proceedings of the IEEE International Conference on Communications (ICC).","author":"Musunuri R.","key":"e_1_2_1_55_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Pei D.","key":"e_1_2_1_56_1"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2006.03.004"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Rekhter Y. Li T. and Hares S. 2006. A border gateway protocol 4 (BGP-4). IETF RFC 4271.  Rekhter Y. Li T. and Hares S. 2006. A border gateway protocol 4 (BGP-4). IETF RFC 4271.","DOI":"10.17487\/rfc4271"},{"key":"e_1_2_1_59_1","unstructured":"Retana A. and White R. 2011. BGP Custom decision process. draft-retana-bgp-custom-decision-01.  Retana A. and White R. 2011. BGP Custom decision process. draft-retana-bgp-custom-decision-01."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/637201.637232"},{"key":"e_1_2_1_61_1","unstructured":"RIPE NCC. 2011. Routing information service. http:\/\/www.ripe.net\/ris\/.  RIPE NCC. 2011. Routing information service. http:\/\/www.ripe.net\/ris\/."},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Sami R.","key":"e_1_2_1_62_1"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.857111"},{"volume-title":"Proceedings of the International Symposium on the Mathematical Theory of Networks and Systems (MTNS).","author":"Sobrinho J. L.","key":"e_1_2_1_64_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (InfoCom).","author":"Suchara M.","key":"e_1_2_1_65_1"},{"key":"e_1_2_1_66_1","unstructured":"University of Oregon. 2011. Route Views project. http:\/\/www.routeviews.org\/.  University of Oregon. 2011. Route Views project. http:\/\/www.routeviews.org\/."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00108-5"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555375"},{"volume-title":"Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS).","author":"Zhang H.","key":"e_1_2_1_69_1"},{"key":"e_1_2_1_70_1","unstructured":"Zhang R. and Bartell M. 2003. BGP Design and Implementation. Cisco Press Indianapolis IN.   Zhang R. and Bartell M. 2003. BGP Design and Implementation. Cisco Press Indianapolis IN."}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2333112.2333121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2333112.2333121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:06Z","timestamp":1750238466000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2333112.2333121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":70,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2333112.2333121"],"URL":"https:\/\/doi.org\/10.1145\/2333112.2333121","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2009-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}