Demand-Oblivious Routing: Distributed vs. Centralized Approaches. Rétvári, G. & Németh, G. In IEEE INFOCOM 2010, March, 2010. doi abstract bibtex Until recent years, it was more or less undisputed common-sense that an accurate view on traffic demands is indispensable for optimizing the flow of traffic through a network. Lately, this premise has been questioned sharply: it was shown that setting just a single routing, the so called demand-oblivious routing, is sufficient to accommodate any admissible traffic matrix in the network with moderate link overload, so no prior information on demands is absolutely necessary for efficient traffic engineering. Demand-oblivious routing lends itself to distributed implementations, so it scales well. In this paper, we generalize demand-oblivious routing in a new way: we show that, in contrast to the distributed case, centralized demand-oblivious routing can eliminate link overload completely. What is more, our centralized scheme allows for optimizing the routes with respect to arbitrary linear or quadratic objective function. We realize, however, that a centralized scheme can become prohibitively complex, therefore, we propose a hybrid distributed-centralized algorithm, which, according to our simulations, strikes a good balance between efficiency, scalability and complexity.
@INPROCEEDINGS{hybrid_obl_infocom2010,
author = {G. R\'etv\'ari and G. N\'emeth},
month = {March},
title = {Demand-Oblivious Routing: Distributed vs. Centralized Approaches},
booktitle = {IEEE INFOCOM 2010},
year = {2010},
location = {San Diego, CA, USA},
paper = {http://lendulet.tmit.bme.hu/~retvari/publications/infocom_2010.pdf},
slides = {http://lendulet.tmit.bme.hu/~retvari/publications/infocom_2010.slides.pdf},
doi = {10.1109/INFCOM.2010.5461925},
abstract = {Until recent years, it was more or less undisputed
common-sense that an accurate view on traffic demands is
indispensable for optimizing the flow of traffic through a
network. Lately, this premise has been questioned sharply:
it was shown that setting just a single routing, the so
called demand-oblivious routing, is sufficient to
accommodate any admissible traffic matrix in the network
with moderate link overload, so no prior information on
demands is absolutely necessary for efficient traffic
engineering. Demand-oblivious routing lends itself to
distributed implementations, so it scales well. In this
paper, we generalize demand-oblivious routing in a new way:
we show that, in contrast to the distributed case,
centralized demand-oblivious routing can eliminate link
overload completely. What is more, our centralized scheme
allows for optimizing the routes with respect to arbitrary
linear or quadratic objective function. We realize,
however, that a centralized scheme can become prohibitively
complex, therefore, we propose a hybrid
distributed-centralized algorithm, which, according to our
simulations, strikes a good balance between efficiency,
scalability and complexity.}
}
Downloads: 0
{"_id":"yhKoDZoJhjMjKbWWQ","bibbaseid":"rtvri-nmeth-demandobliviousroutingdistributedvscentralizedapproaches-2010","downloads":0,"creationDate":"2017-09-29T21:08:10.508Z","title":"Demand-Oblivious Routing: Distributed vs. Centralized Approaches","author_short":["Rétvári, G.","Németh, G."],"year":2010,"bibtype":"inproceedings","biburl":"http://lendulet.tmit.bme.hu/~retvari/tmp/publications.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["G."],"propositions":[],"lastnames":["Rétvári"],"suffixes":[]},{"firstnames":["G."],"propositions":[],"lastnames":["Németh"],"suffixes":[]}],"month":"March","title":"Demand-Oblivious Routing: Distributed vs. Centralized Approaches","booktitle":"IEEE INFOCOM 2010","year":"2010","location":"San Diego, CA, USA","paper":"http://lendulet.tmit.bme.hu/~retvari/publications/infocom_2010.pdf","slides":"http://lendulet.tmit.bme.hu/~retvari/publications/infocom_2010.slides.pdf","doi":"10.1109/INFCOM.2010.5461925","abstract":"Until recent years, it was more or less undisputed common-sense that an accurate view on traffic demands is indispensable for optimizing the flow of traffic through a network. Lately, this premise has been questioned sharply: it was shown that setting just a single routing, the so called demand-oblivious routing, is sufficient to accommodate any admissible traffic matrix in the network with moderate link overload, so no prior information on demands is absolutely necessary for efficient traffic engineering. Demand-oblivious routing lends itself to distributed implementations, so it scales well. In this paper, we generalize demand-oblivious routing in a new way: we show that, in contrast to the distributed case, centralized demand-oblivious routing can eliminate link overload completely. What is more, our centralized scheme allows for optimizing the routes with respect to arbitrary linear or quadratic objective function. We realize, however, that a centralized scheme can become prohibitively complex, therefore, we propose a hybrid distributed-centralized algorithm, which, according to our simulations, strikes a good balance between efficiency, scalability and complexity.","bibtex":"@INPROCEEDINGS{hybrid_obl_infocom2010,\n author = {G. R\\'etv\\'ari and G. N\\'emeth},\n month = {March},\n title = {Demand-Oblivious Routing: Distributed vs. Centralized Approaches},\n booktitle = {IEEE INFOCOM 2010},\n year = {2010},\n location = {San Diego, CA, USA},\n paper = {http://lendulet.tmit.bme.hu/~retvari/publications/infocom_2010.pdf},\n slides = {http://lendulet.tmit.bme.hu/~retvari/publications/infocom_2010.slides.pdf},\n doi = {10.1109/INFCOM.2010.5461925},\n abstract = {Until recent years, it was more or less undisputed\n common-sense that an accurate view on traffic demands is\n indispensable for optimizing the flow of traffic through a\n network. Lately, this premise has been questioned sharply:\n it was shown that setting just a single routing, the so\n called demand-oblivious routing, is sufficient to\n accommodate any admissible traffic matrix in the network\n with moderate link overload, so no prior information on\n demands is absolutely necessary for efficient traffic\n engineering. Demand-oblivious routing lends itself to\n distributed implementations, so it scales well. In this\n paper, we generalize demand-oblivious routing in a new way:\n we show that, in contrast to the distributed case,\n centralized demand-oblivious routing can eliminate link\n overload completely. What is more, our centralized scheme\n allows for optimizing the routes with respect to arbitrary\n linear or quadratic objective function. We realize,\n however, that a centralized scheme can become prohibitively\n complex, therefore, we propose a hybrid\n distributed-centralized algorithm, which, according to our\n simulations, strikes a good balance between efficiency,\n scalability and complexity.}\n}\n\n","author_short":["Rétvári, G.","Németh, G."],"key":"hybrid_obl_infocom2010","id":"hybrid_obl_infocom2010","bibbaseid":"rtvri-nmeth-demandobliviousroutingdistributedvscentralizedapproaches-2010","role":"author","urls":{},"downloads":0},"search_terms":["demand","oblivious","routing","distributed","centralized","approaches","rétvári","németh"],"keywords":[],"authorIDs":[],"dataSources":["Byw3wEC6P9WCPMPit"]}