---
_id: '11926'
abstract:
- lang: eng
  text: "We present the first polylog-competitive online algorithm for the general
    multicast problem in the throughput model. The ratio of the number of requests
    accepted by the optimum offline alaorithm to the exoected number of reauests accepted
    by our algorithm is O(jlog n + log log M)(log n + log M) log n), where M is the
    number of multicast groups and n is the number of nodes in the nraoh. We show
    that this is close to optimum by presenting-an*R(log nlog M) lower\r\nbound on
    this ratio for anv randomized online algorithm against an oblivious adversary,
    when M is much lar&r 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 nrevious comnetitive aleorithms in the throughput
    modei, our cost is-not a direct function of the edne load. The new cost definition
    allows us to decouple the effects of routing and admission decisions of different
    multicast groups.  "
article_processing_charge: No
author:
- first_name: Ashish
  full_name: Goel, Ashish
  last_name: Goel
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Serge
  full_name: Plotkin, Serge
  last_name: Plotkin
citation:
  ama: 'Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm
    for multicast routing and admission control. In: <i>9th Annual ACM SIAM Symposium
    on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 1998:97-106.'
  apa: 'Goel, A., Henzinger, M. H., &#38; Plotkin, S. (1998). An online throughput-competitive
    algorithm for multicast routing and admission control. In <i>9th Annual ACM SIAM
    Symposium on Discrete Algorithms</i> (pp. 97–106). San Francisco, CA, United States:
    Society for Industrial and Applied Mathematics.'
  chicago: Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive
    Algorithm for Multicast Routing and Admission Control.” In <i>9th Annual ACM SIAM
    Symposium on Discrete Algorithms</i>, 97–106. Society for Industrial and Applied
    Mathematics, 1998.
  ieee: A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive
    algorithm for multicast routing and admission control,” in <i>9th Annual ACM SIAM
    Symposium on Discrete Algorithms</i>, San Francisco, CA, United States, 1998,
    pp. 97–106.
  ista: 'Goel A, Henzinger MH, Plotkin S. 1998. An online throughput-competitive algorithm
    for multicast routing and admission control. 9th Annual ACM SIAM Symposium on
    Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 97–106.'
  mla: Goel, Ashish, et al. “An Online Throughput-Competitive Algorithm for Multicast
    Routing and Admission Control.” <i>9th Annual ACM SIAM Symposium on Discrete Algorithms</i>,
    Society for Industrial and Applied Mathematics, 1998, pp. 97–106.
  short: A. Goel, M.H. Henzinger, S. Plotkin, in:, 9th Annual ACM SIAM Symposium on
    Discrete Algorithms, Society for Industrial and Applied Mathematics, 1998, pp.
    97–106.
conference:
  end_date: 1998-01-27
  location: San Francisco, CA, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 1998-01-25
date_created: 2022-08-19T06:22:30Z
date_published: 1998-01-01T00:00:00Z
date_updated: 2023-02-21T16:27:22Z
day: '01'
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 97-106
publication: 9th Annual ACM SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '0898714109'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
  record:
  - id: '11763'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: An online throughput-competitive algorithm for multicast routing and admission
  control
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1998'
...