Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. An online throughput-competitive algorithm for multicast routing and admission control
 
research article

An online throughput-competitive algorithm for multicast routing and admission control

Goel, Ashish
•
Henzinger, Monika R.  
•
Plotkin, Serge
2005
Journal of Algorithms

We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of requests accepted by our algorithm is O((logn+loglogM) (logn+logM)logn), where M is the number of multicast groups and n is the number of nodes in the graph. We show that this is close to optimum by presenting an 0(lognlogM) lower bound on this ratio for any randomized online algorithm against an oblivious adversary, when M is much larger than the link capacities. Our lower bound applies even in the restricted case where the link capacities are much larger than bandwidth requested by a single multicast. We also present a simple proof showing that it is impossible to be competitive against an adaptive online adversary. As in the previous online routing algorithms, our algorithm uses edge-costs when deciding on which is the best path to use. In contrast to the previous competitive algorithms in the throughput model, our cost is not a direct function of the edge load. The new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

GoelHP05.pdf

Access type

openaccess

Size

166.82 KB

Format

Adobe PDF

Checksum (MD5)

164609131cda1b0167630d5e679402c6

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés