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 on-line routing and admission control strate-Ε½ gies 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 cannot be improved in the context of the considered models, making it impossible to use these models to identify algorithms that are going to perform well in practice. In this paper we develop routing and admission control strategies for a probabilistic model, where the requests for virtual circuits between any two points arrive according to a Poisson process and where the circuit holding times are exponentially distributed. Our model is close to the one that was developed to analyze and tune the Ε½ . currently used strategies for managing traffic in long-distance telephone networks. We strengthen this model by assuming that the rates of the Poisson Ε½ . processes the ''traffic matrix'' are unknown to the algorithm and are chosen by the adversary. Our strategy is competitive with respect to the expected rejection ratio. More precisely, it achieves an expected rejection ratio of at most R* q β , where R* is the optimum expected rejection ratio. The expectations are taken over Ε½ . the distribution of the request sequences, and β s O r log n , where r is the ' maximum fraction of an edge bandwidth that can be requested by a single circuit.