Greedy online algorithms for routing permanent virtual circuits

Title:
Greedy online algorithms for routing permanent virtual circuits
Authors:
Havill, Jessen T.; Mao, Weizhen
Citation:
Havill, J. T., & Mao, W. (1999). Greedy online algorithms for routing permanent virtual circuits. Networks, 34(2), 136-153.
Publisher:
Networks
DATE ISSUED:
Sep-1999
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/5001; http://hdl.handle.net/2374
Type:
Article
Language:
en_US
Description:
We analyze the competitive ratio of two greedy online algorithms for routing permanent virtual circuits in a network with arbitrary topology and uniform capacity links. We show that the competitive ratio of the first algorithm, with respect to network congestion, is in $\Omega(\sqrt{{\cal D}m})$ and $O(\sqrt{{\cal DL}m}),$ where m is the number of links in the network, 𝒟��� is the maximum ratio, over all requests, of the length of the longest path for the request to the length of the shortest path for the request, and ℒ︁ is the ratio of the maximum‐to‐minimum bandwidth requirement. We show that the competitive ratio of the second greedy algorithm is in Ω( d + log( n − d )) and min{ O ( d log n ), $O(\sqrt{{\cal DL}m})\}$ when the optimal route assignment is pairwise edge disjoint, where n is the number of network nodes and d is the length of the longest path that can be assigned to a request. It is known that the optimal competitive ratio for this problem is Θ(log n ). Aspnes et al. designed a Θ(log n ) competitive online algorithm that computes an exponential function of current congestion to make each decision. The greedy online algorithms, although not optimal, make each decision more quickly and still have good competitive ratios in many nontrivial situations. e
ISSN:
00283045
Appears in Collections:
Faculty Publications

Full metadata record

DC FieldValue Language
dc.contributor.authorHavill, Jessen T.en
dc.contributor.authorMao, Weizhenen
dc.date.accessioned2013-01-02T16:15:47Zen
dc.date.accessioned2013-12-18T21:04:53Z-
dc.date.available2013-01-02T16:15:47Zen
dc.date.available2013-12-18T21:04:53Z-
dc.date.created1999-09en
dc.date.issued1999-09en
dc.identifier.citationHavill, J. T., & Mao, W. (1999). Greedy online algorithms for routing permanent virtual circuits. Networks, 34(2), 136-153.en_US
dc.identifier.issn00283045en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/5001en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionWe analyze the competitive ratio of two greedy online algorithms for routing permanent virtual circuits in a network with arbitrary topology and uniform capacity links. We show that the competitive ratio of the first algorithm, with respect to network congestion, is in $\Omega(\sqrt{{\cal D}m})$ and $O(\sqrt{{\cal DL}m}),$ where m is the number of links in the network, 𝒟��� is the maximum ratio, over all requests, of the length of the longest path for the request to the length of the shortest path for the request, and ℒ︁ is the ratio of the maximum‐to‐minimum bandwidth requirement. We show that the competitive ratio of the second greedy algorithm is in Ω( d + log( n − d )) and min{ O ( d log n ), $O(\sqrt{{\cal DL}m})\}$ when the optimal route assignment is pairwise edge disjoint, where n is the number of network nodes and d is the length of the longest path that can be assigned to a request. It is known that the optimal competitive ratio for this problem is Θ(log n ). Aspnes et al. designed a Θ(log n ) competitive online algorithm that computes an exponential function of current congestion to make each decision. The greedy online algorithms, although not optimal, make each decision more quickly and still have good competitive ratios in many nontrivial situations. een_US
dc.language.isoen_USen_US
dc.publisherNetworksen_US
dc.relation.ispartofFaculty Publicationsen_US
dc.titleGreedy online algorithms for routing permanent virtual circuitsen_US
dc.typeArticleen_US
dc.contributor.institutionDenison Universityen_US
dc.date.digitized2013-01-02en
dc.contributor.repositoryDenison Resource Commonsen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.