On Selfish Routing in Internet-Like Environment

Lili Qiu, Yang Richard Yang, Yin Zhang and Scott Shenker

SIGCOMM 2003

Summary and Critique by Cheng Huang:

Summary

This work seeks to investigate the impact of selfish routing in network environment like today's Internet. It does extensive simulations to cover various selfish source routing, overlay routing via various network topologies. It also investigates the impact of multiple overlays and the interaction between selfish overlay routing and traffic engineering. The main conclusion is that selfish routing is close to optimal in Internet-like environment, which is far from theoretical worst case results.

Critique

Most simulation results are demonstrated using two metrics: 1) average latency and 2) maximum link utilization. These two metrics, however, seem not be well related. For instance, in Fig 2 and Fig 5, when utilization exceeds 100%, the average latency doesn't show rapid increment. This might because the maximum link utilization only indicates the most congested link, but then this seems not to be a good metric to use, because it doesn't reflect the overall network conditions.

Also, because of this maximum link utilization metric, it seems that traffic demands in most simulations are not high enough (LSF too small?) to make the network highly loaded. In another word, we see the performance of selfish routing is very close to optimal might only because the overall network is operating at light load. This might not be the case when the network has highly loaded traffic demands.

There are some other points might need some explanations:

Fig 5(b) shows inconsistent results compared to Fig 5(a) and (c). In (b), the maximum link utilizations of selfish source and optimal routing are far from 100% at LSF = 0.2, while in (a) and (c), those are close to 100%.

What makes the authors conclude that "both batency and network cost/utilization are not very sensitive to latency functions", if we compare M/M/1 to BPR in Figure 7?

From all results, OSPF with random-weight assignment yields poor performance. What is the reason to have this scheme? Is it only for comparison purpose?

What is the overlay coverage in Sec 8 and does it matter in this context?

Finally, none of the results show any error margin. Given the small difference compared to optimal schemes, I am curious to see if simulation errors play any role in final conclusions.