LADEQ: A fast lagrangian relaxation based algorithm for destination-based QoS routing

Nitin Varyani, Zhi Li Zhang, Muralidharan Rangachari, David Dai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Quality of Service provisioning in today's overlay networks includes computing routes that simultaneously guarantee multiple QoS metrics like bandwidth, delay, jitter, and packet-loss rate. Lagrange relaxation-based aggregated cost (LARAC) algorithm is among the best centralized algorithms for finding a near optimal solution to the constrained shortest path (CSP) problem for the additive metrics. To take advantage of the LARAC algorithm, we transform the non-linear QoS routing problem into a linear integer programming problem by converting all constraints to additive. We then develop a multi-constrained version of the LARAC algorithm and use sub-gradient optimization to converge to a near optimal solution. As LARAC algorithm needs to solve the routing optimization problem separately for every source and destination pair, this significantly increases the total time complexity. We, therefore, modify the LARAC algorithm to destination-based QoS routing, LADEQ, to reduce the number of routing optimization problems solved. This also reduces the size of the forwarding tables. A trace-driven evaluation shows that as the network size is increased, the time taken by our algorithm, LADEQ, was significantly smaller than the state-of-the-art multi-constrained shortest path (MCSP) algorithms applied to all source and destination pairs.

Original languageEnglish (US)
Title of host publication2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages462-468
Number of pages7
ISBN (Electronic)9783903176157
StatePublished - May 16 2019
Event2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019 - Arlington, United States
Duration: Apr 8 2019Apr 12 2019

Publication series

Name2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019

Conference

Conference2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019
CountryUnited States
CityArlington
Period4/8/194/12/19

Keywords

  • Destination-based
  • Integer programming
  • Lagrange
  • QoS
  • Routing
  • Sub-gradient

Fingerprint Dive into the research topics of 'LADEQ: A fast lagrangian relaxation based algorithm for destination-based QoS routing'. Together they form a unique fingerprint.

  • Cite this

    Varyani, N., Zhang, Z. L., Rangachari, M., & Dai, D. (2019). LADEQ: A fast lagrangian relaxation based algorithm for destination-based QoS routing. In 2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019 (pp. 462-468). [8717862] (2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019). Institute of Electrical and Electronics Engineers Inc..