Routing in large networks: quality without certainty

Pawel Gburzynski
Department of Computing Science
University of Alberta
Edmonton, Alberta, CANADA T6G 2H1


The growing diversification of networking applications with specific and stringent quality of service (QoS) requirements pose new problems for routing algorithms in wide area networks. Traditionally those algorithms have focused on finding the shortest path between the source and destination, viewing the issues of resource availability along this path as secondary. It is possible, however, that while the statically preferred path is temporarily congested, an alternative path (perhaps longer than the preferred one) has enough resources to accommodate a new connection.

To base its route selection on the dynamic availability of resources in the network, a routing node should be aware of the dynamic state of links, possibly located several hops away. This calls for a periodic exchange of link state information, which creates extra traffic in the network. One problem with QoS routing is therefore the tradeoff between the accuracy of the link state information and the overhead incurred by exchanging that information. As the overhead must be kept at a negligible fraction of the total network bandwidth, the link information is bound to merely approximate the true state of the links.

In our talk, we will discuss this tradeoff in the context of our multiple-path routing approach that admits inaccuracies in the link state information available to the routing nodes. We will present a few path selection algorithms together with strategies for collecting link state information and discuss their merits in application to realistic network configurations.

You can listen and learn how to pronounce speaker's name.

Colloquia Series page.