e are given a network where each edge has an associated capacity or bandwidth. Requests for connections arrive online; each request specifies the source and sink and the requested bandwidth. This paper presents an algorithm for routing of messages. At the time of arrival of each request, if its bandwidth is bigger than associated bound, then the request is rejected. Otherwise, the algorithm assigns it a path to send the message. We define a new routing objective, which is called the average relative load on edges. Our objective is different from the previously studied objective
