### On-line routing of virtual circuits with applications to load balancing and machine schedulingOn-line routing of virtual circuits with applications to load balancing and machine scheduling

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

Source: ACM Digital Library