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 language | English (US) |
---|---|
Title of host publication | 2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 462-468 |
Number of pages | 7 |
ISBN (Electronic) | 9783903176157 |
State | Published - May 16 2019 |
Event | 2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019 - Arlington, United States Duration: Apr 8 2019 → Apr 12 2019 |
Publication series
Name | 2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019 |
---|
Conference
Conference | 2019 IFIP/IEEE Symposium on Integrated Network and Service Management, IM 2019 |
---|---|
Country/Territory | United States |
City | Arlington |
Period | 4/8/19 → 4/12/19 |
Bibliographical note
Publisher Copyright:© 2019 IFIP.
Keywords
- Destination-based
- Integer programming
- Lagrange
- QoS
- Routing
- Sub-gradient