Max-Flow Min-Cost Routing in a Future-Internet with Improved QoS Guarantees
| Autor: | Ted H. Szymanski |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Routing protocol
Dynamic Source Routing Equal-cost multi-path routing Computer science Routing table Enhanced Interior Gateway Routing Protocol Wireless Routing Protocol Geographic routing Throughput Routing Information Protocol Computer Science::Networking and Internet Architecture Destination-Sequenced Distance Vector routing Electrical and Electronic Engineering Hierarchical routing Triangular routing Static routing Zone Routing Protocol Adaptive quality of service multi-hop routing Multicast business.industry Quality of service ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS Policy-based routing Path vector protocol Routing domain Link-state routing protocol Linear network coding Multipath routing Unicast business Computer network |
| Zdroj: | IEEE Transactions on Communications. 61:1485-1497 |
| ISSN: | 0090-6778 |
| DOI: | 10.1109/tcomm.2013.020713.110882 |
| Popis: | A Constrained Multicommodity Maximum-Flow-Minimum-Cost routing algorithm is presented. The algorithm computes maximum-flow routings for all smooth unicast traffic demands within the Capacity Region of a network subject to routing cost constraints. The edge cost can be a distance, reliability, congestion or an energy metric. It is shown that every network has a finite Bandwidth-Cost capacity. The Bandwidth-Distance and the Bandwidth-Energy capacities are explored. The routing algorithm requires the formulation of two Linear Programs (LPs). The first LP finds a multicommodity Maximum-Flow, when the flows are constrained to a sub-graph of the network to enforce cost constraints. The second LP minimizes the routing cost, given that the maximum-flow is fixed. A related Constrained Multicast-Max-Flow-Min-Cost algorithm is also presented, to maximize the throughput of a multicast tree using network coding, subject to routing cost constraints. These algorithms have polynomial-time solutions, whereas traditional multipath routing algorithms can be NP-Hard. The addition of routing cost constraints can significantly reduce the size of the LPs, resulting in faster solutions, with lower edge utilizations and with higher energy efficiencies. The application of these algorithms to route aggregated video streams from cloud data centers in a Future-Internet network, with improved throughput, energy-efficiency and QoS guarantees is presented. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|