{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:56Z","timestamp":1750307816645,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>With steady improvement in the reliability and performance of communication devices, routing instabilities now contribute to many of the remaining service degradations and interruptions in modern networks. This has led to a renewed interest in centralized routing systems that, compared to distributed routing, can provide greater control over routing decisions and better visibility of the results. One benefit of centralized control is the opportunity to readily eliminate transient routing loops, which arise frequently after network changes because of inconsistent routing states across devices. Translating this conceptual simplicity into a solution with tolerable message complexity is non-trivial. Addressing this issue is the focus of this paper. We identify when and why avoiding transient loops might require a significant number of messages in a centralized routing system, and demonstrate that this is the case under many common failure scenarios. We also establish that minimizing the number of required messages is NP-hard, and propose a greedy heuristic that we show to perform well under many conditions. The paper's results can facilitate the deployment and evaluation of centralized architectures by leveraging their strengths without incurring unacceptable overhead.<\/jats:p>","DOI":"10.1145\/1384609.1384616","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"63-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Message-efficient dissemination for loop-free centralized routing"],"prefix":"10.1145","volume":"38","author":[{"given":"Haldane","family":"Peterson","sequence":"first","affiliation":[{"name":"University of Minnesota"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soumya","family":"Sen","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaideep","family":"Chandrashekar","sequence":"additional","affiliation":[{"name":"Intel Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lixin","family":"Gao","sequence":"additional","affiliation":[{"name":"University of Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roch","family":"Guerin","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhi-Li","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Minnesota"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. Network\/Interop","author":"Albrightson R.","year":"1994","unstructured":"Albrightson , R. , Garcia-Luna-Aceves , J. , and Boyle , J . EIGRP--A fast routing protocol based on distance vectors . In Proc. Network\/Interop ( Las Vegas, NV , May 1994 ). Albrightson, R., Garcia-Luna-Aceves, J., and Boyle, J. EIGRP--A fast routing protocol based on distance vectors. In Proc. Network\/Interop (Las Vegas, NV, May 1994)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016707.1016709"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.902686"},{"key":"e_1_2_1_4_1","volume-title":"February","author":"Francois P.","year":"2008","unstructured":"Francois , P. , Bonaventure , O. , Shand , M. , Bryant , S. , and Privedi , S . Loop-free convergence using oFIB. Internet draft , February 2008 . Work in progress, revision 02. Francois, P., Bonaventure, O., Shand, M., Bryant, S., and Privedi, S. Loop-free convergence using oFIB. Internet draft, February 2008. Work in progress, revision 02."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2008.080103"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.222913"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1096536.1096541"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/637201.637217"},{"key":"e_1_2_1_9_1","first-page":"94","volume-title":"Ed. PWS Publishing","author":"Hochbaum D. S.","year":"1997","unstructured":"Hochbaum , D. S. Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems. In Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum , Ed. PWS Publishing , 1997 , ch. 3, pp. 94 -- 143 . Hochbaum, D. S. Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems. In Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum, Ed. PWS Publishing, 1997, ch. 3, pp. 94--143."},{"key":"e_1_2_1_10_1","unstructured":"Meyer D. etal University of Oregon Route Views project. http:\/\/www.routeviews.org.  Meyer D. et al. University of Oregon Route Views project. http:\/\/www.routeviews.org."},{"key":"e_1_2_1_11_1","volume-title":"-L. Message-efficient dissemination for loop-free centralized routing. Tech. rep","author":"Peterson H.","year":"2008","unstructured":"Peterson , H. , Sen , S. , Chandrashekhar , J. , Gao , L. , Guerin , R. , and Zhang , Z . -L. Message-efficient dissemination for loop-free centralized routing. Tech. rep ., University of Minnesota Department of Computer Science , 2008 . http:\/\/www-users.cs.umn.edu\/~peterson\/tr-dddd-2008-01.pdf. Peterson, H., Sen, S., Chandrashekhar, J., Gao, L., Guerin, R., and Zhang, Z.-L. Message-efficient dissemination for loop-free centralized routing. Tech. rep., University of Minnesota Department of Computer Science, 2008. http:\/\/www-users.cs.umn.edu\/~peterson\/tr-dddd-2008-01.pdf."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.822655"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1012888.1005723"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of USENIX Symposium on Networked Systems Design and Implementation (NSDI '07)","author":"Yan H.","year":"2007","unstructured":"Yan , H. , Maltz , D. A. , Ng , T. S. E. , Gogineni , H. , Zhang , H. , and Cai , Z . Tesseract: A 4D network control plane . In Proceedings of USENIX Symposium on Networked Systems Design and Implementation (NSDI '07) ( 2007 ). Yan, H., Maltz, D. A., Ng, T. S. E., Gogineni, H., Zhang, H., and Cai, Z. Tesseract: A 4D network control plane. In Proceedings of USENIX Symposium on Networked Systems Design and Implementation (NSDI '07) (2007)."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1384609.1384616","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1384609.1384616","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:42Z","timestamp":1750255062000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1384609.1384616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1145\/1384609.1384616"],"URL":"https:\/\/doi.org\/10.1145\/1384609.1384616","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2008,7]]},"assertion":[{"value":"2008-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}