BANDWIDTH-SENSITIVE ROUTING: FROM INDIVIDUALISM TO COLLECTIVISM

Abstract

The routing metric is the measure by which a routing protocol chooses paths between pairs of source and destination nodes in the network. Routing metric has a significant impact on the network resource utilization. The most well-known intradomain routing disciplines in today's Internet are the minimum hop count routing (e.g., Routing Information Protocol (RIP)) and the shortest path routing (e.g., Open Shortest Path First (OSPF) and intermediate system to system (IS-IS)). In the former case, the routing metric is the number of hops over the path and in the latter one, the metric is evaluated with respect to an additive link weight function. In this article, we study the impact of these two types of metrics on routing of bandwidth-sensitive traffic in the network. We first argue that the main characteristics of a bandwidth-sensitive routing problem can be captured elegantly through transforming the problem from the networking domain into the sociology area. This model reveals that the minimum hop count is indeed a dominant Individualist view of resource management in the Internet, whereas the shortest-path metric has a collectivist trend. We then propose a novel hybrid metric, which combines the benefit of both sociological systems. Through extensive simulations, we show that our proposed scheme yields much better results, with respect to the number of admitted requests and delay of paths, compared with other well-known counterparts.

KEYWORDS:

• collectivism
• hop count
• individualism
• routing metric
• shortest path routing
• sociology

Notes

¹In other words, flows like to have shorter paths (with a smaller hop count), whereas the network operator prefers wider paths (with a higher available bandwidth).

²Actually, this greedy algorithm first removes all infeasible links from the topology and then chooses the minimum hop count path (if there is any) as the path of each flow.

³Note that the capitalist minimum hop count algorithm tries to optimize the individual values at the cost of worsening the social value, whereas the socialist load balanced routing has a reverse trend.