Thumbnail
Access Restriction
Subscribed

Author Aspnes, James ♦ Azar, Yossi ♦ Fiat, Amos ♦ Plotkin, Serge ♦ Waarts, Orli
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1997
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword High-speed networks ♦ On-line algorithms ♦ Optimization ♦ Routing
Abstract In this paper we study the problem of on-line allocation of routes to virtual circuits (both $\textit{point-to-point}$ and $\textit{multicast})$ where the goal is to route all requests while minimizing the required bandwidth. We concentrate on the case of $\textit{Permanent}$ virtual circuits (i.e., once a circuit is established it exists forever), and describe an algorithm that achieves on $\textit{O}$ (log $\textit{n})$ competitive ratio with respect to maximum congestin, where $\textit{n}is$ the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an $\textit{O}$ (log $\textit{n})$ factor. We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which ***(log $\textit{n})$ increase in bandwidth is necessary in directed networks.We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases the machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. for the $\textit{unrelated}$ case (with $\textit{n}machines),$ we describe a new method that yields $\textit{O}(log\textit{n})-competitive$ algorithm. This stands in contrast to the natural greed approach, whose competitive ratio is exactly $\textit{n}.$ show that this result is tight, that is, for any on-line algorithm there exists a scenario in which ***(log $\textit{n})$ increase in bandwidth is necessary in directed networks.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1997-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 44
Issue Number 3
Page Count 19
Starting Page 486
Ending Page 504


Open content in new tab

   Open content in new tab
Source: ACM Digital Library