Demand-Oblivious Routing: Distributed vs. Centralized Approaches

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"]}