# Greedy online algorithms for routing permanent virtual circuits

- Title:
- Greedy online algorithms for routing permanent virtual circuits
- Authors:
- Citation:
- Havill, J. T., & Mao, W. (1999). Greedy online algorithms for routing permanent virtual circuits. Networks, 34(2), 136-153.
- Publisher:
- 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 Field | Value | Language |
---|---|---|

dc.contributor.author | Havill, Jessen T. | en |

dc.contributor.author | Mao, Weizhen | en |

dc.date.accessioned | 2013-01-02T16:15:47Z | en |

dc.date.accessioned | 2013-12-18T21:04:53Z | - |

dc.date.available | 2013-01-02T16:15:47Z | en |

dc.date.available | 2013-12-18T21:04:53Z | - |

dc.date.created | 1999-09 | en |

dc.date.issued | 1999-09 | en |

dc.identifier.citation | Havill, J. T., & Mao, W. (1999). Greedy online algorithms for routing permanent virtual circuits. Networks, 34(2), 136-153. | en_US |

dc.identifier.issn | 00283045 | en |

dc.identifier.uri | http://hdl.handle.net/2374.DEN/5001 | en |

dc.identifier.uri | http://hdl.handle.net/2374 | - |

dc.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 | en_US |

dc.language.iso | en_US | en_US |

dc.publisher | Networks | en_US |

dc.relation.ispartof | Faculty Publications | en_US |

dc.title | Greedy online algorithms for routing permanent virtual circuits | en_US |

dc.type | Article | en_US |

dc.contributor.institution | Denison University | en_US |

dc.date.digitized | 2013-01-02 | en |

dc.contributor.repository | Denison Resource Commons | en_US |

All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.