1996 · 61 citations · 27 references
ComputingComputer ScienceComputer SystemsComputer NetworksMarkov Decision ProcessesQueuing TheoryNetwork Performance AnalysisQueueing NetworksQueueing SystemsQueueing TheoryRoutingRouting AlgorithmsAdmission ControlAdmission Control PoliciesBandwidthCircuit RoutingPoisson Point ProcessesPoisson Process ModelsTraffic AnalysisVirtual Circuits
Emerging high speed networks will carry traffic for services such as video-on-demand and video teleconferencing -- that require resource reservation along the path on which the traffic is sent. High bandwidth-delay product of these networks prevents circuit rerouting, i.e. once a circuit is routed on a certain path, the bandwidth taken by this circuit remains unavailable for the duration (holding time) of this circuit. As a result, such networks will need effective routing and admission control strategies. Recently developed online routing and admission control strategies have logarithmic competitive ratios with respect to the admission ratio (the fraction of admitted circuits). Such guarantees on performance are rather weak in the most interesting case where the rejection ratio of the optimum algorithm is very small or even 0. Unfortunately, these guarantees can not be improved in the context of the considered models, making it impossible to use these models to identify algorithms th...
27
Anna R. Karlin, Mark S. Manasse, Larry Rudolph et al. · Algorithmica · 1988 · 612 citations
The maximum concurrent flow problem
Farhad Shahrokhi, David W. Matula · Journal of the ACM · 1990 · 437 citations · Full text
Natural Sciences, Computer Engineering, Computer Science +17