  We consider an online version of the well-studied network utility
maximization problem, where users arrive one by one and an operator makes
irrevocable decisions for each user without knowing the details of future
arrivals. We propose a threshold-based algorithm and analyze its worst-case
performance. We prove that the competitive ratio of the proposed algorithm is
linearly increasing in the number of links in a network and show this
competitive analysis is tight. Extensive trace-driven simulations are conducted
to demonstrate the performance of our proposed algorithm. In addition, since
worst-case scenarios rarely occur in practice, we devise an adaptive
implementation of our algorithm to improve its average-case performance and
validate its effectiveness via simulations.
