A First-Principles Approach to Understanding the Internet's Router-level Topology
by Lun Li, David Alderson, Walter Willinger, John Doyle
url show details
Details
| editor: | Raj Yavatkar and Ellen W. Zegura and Jennifer Rexford | | type: | misc | | booktitle: | Proceedings of the {ACM} {SIGCOMM} 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, August 30 - September 3, 2004, Portland, Oregon, {USA} | | year: | 2004 | | pages: | 3--14 | | publisher: | ACM |
|
|
You need to log in to add tags and post comments.
In lieu of a full public review, here are a few discussion questions for this paper.
1. Chicken and egg -- the paper argues that networks are built in a certain way because routers can't have both high fanout and high BW. Perhaps its the other way around - we don't build high fanout/high BW routers because nobody buys them (i.e. nobody builds networks that need them). What do you think?
2. What is a good topology? What properties do you want - fault-tolerance, carrying-capacity, ease of management, easy to filter traffic, etc.? Is HOT a good choice or can we do better?
3. This paper argues that the network is always engineered for performance and that looking at other metrics like "robustness" must always keep performance in mind: metrics based on 'connected clusters' do not capture the real-world implications of performance constraints. What do you think are the fundamental goals of network designers: performance, reliability, managability, scalability? Is there a particular ranking to each one, how might their interplay (or lack of one) suggest better metrics for evaluating topologies?
Finally, here's some recent work on topology generation: http://sysnet.ucsd.edu/~pmahadevan/publications/degcor-sigcomm06.pdf
I think we don't build both high fanout and high bandwidth and people don't buy them because of "price/performance" is so high and we can design a smarter system to deal with this restriction. Using a hard drive as an example, people would love to get a hard drive with very small seek time and high capacity. However, to get much smaller seek time is too costly. So, people work around by using multiple hard drives and try to distribute data uniformly among them, instead. Then, the demand for hard drives with minimum seek time reduces, so people don't build them.
Like most of the real system, the fundamental goals depend on what end users really want and how much they would like to pay. For the Internet, most people want cheap and fast network connection. They will be fine (although they are not happy) when their connections are down for a few hour. So, performance will be the primary goal. On the other hand, the network for emergency alert system has to be much more reliable, so reliability will be the primary goal in this case.
Therefore, I think the good metric would be $$$ based on how much the end users of each particular network would like to spend per unit of each goal. For example, household users might want to spend $10 per 1 Mbps and $0.1 per an hour less downtime per week while the emergency alert system might want to spend $5 per 1 Mbps and $2 per an hour less downtime per week.
It is a very interesting perspective that networks with similar "macroscopic" graph features can exhibit completely different performance and likelihood features, which are practical metrics for measuring network topologies.
However, I am not quite convinced on whether two metrics introduced in this paper properly cover what is needed for network topology evaluation and analysis.
The paper argues that a random network even if it resembles global statistics (high "likelihood") of the real Internet can exhibit bad performance (low "performance"), which means it's unlikely to be actually used by any ISP and thus unrealistic. I liked that they presented some networks that had slightly lower likelihood and higher performance as better models (e.g. HOT), but am still not sure what I'd use e.g. for my class project :)
Figure 6 is impressive.
I think that the paper could include spectral analysis (like the power law paper) into the comparison of different topologies. There is a rich set of features characterizing a topology besides degree distribution.
I think there would usually be a trade-off in any decision/design. So, I agree with Wittawat that acceptable performance with acceptable price seems preferable to high performance with high price.
I think a major argument of the paper is that a random network is not realistic for highly-engineered systems like ISP's networks; however I'm not sure whether the Internet as a whole is that highly-engineered. Also, I don't think the authors claimed that their metrics were comprehensive enough to model the Internet topology.
At a high level, I liked how this paper really complemented the first paper we read in the approach it took to understand internet topology. The first paper took the approach of a hands-off observer, trying to observe patterns in the internet without attempting to really explain or understand them. This paper, on the other hand, tries to characterize internet topology from first principles -- i.e., technological and economic considerations. This definitely led into some more insight into the underlying phenomena, and it was interesting to see comparisons to other topologies as well.
Basically I like this paper. It tells us the fight between performance and likelihood given different topologies with the same degree distribution. After reading this paper, I have the following questions immediately: why don't they use the data of real Internet (or a part of it ) to evaluate the topology, like the throughput and robustness measurements? Given the same degree distribution, which model is more realistic?
Also the HOT topology seems nice in terms of throughput, I think it is hard to build such an Internet due to its requirement of cooperation.
I really liked the way the authors studied the correlation between the internet topology and the physical router technology constraints and the introduction of a feasible region for each router technology. About the "chicken & egg" question in the first comment, my personal feeling is that it is the router limitations that impose constraints on the way we built networks (and not the other way around). I also found section 5 to be quite interesting. It seems that observing only graph theoretic properties (e.g. node degree distribution) of a topology does a relatively poor job of capturing important network features (e.g. performance).
I don't think it's completely cut and dry that performance rules all. If you think about something like Multicast, it's supposed to improve performance by reducing the amount of traffic for one-to-all communication. ISPs should want to deploy it to keep broadcast traffic manageable. As we move towards more on-demand and live streaming content on the Internet, it seems like a no-brainer for improved performance.
Yet, despite almost all routers having support for multicast, nobody turns it on due to economic reasons. In other words, ISPs worry more about accounting and management than performance/efficiency when it comes to Multicast.
To think of it another way: a network engineered to handle multicast traffic might look different than one looking to handle the largest bisection bandwidth. Maybe network topology is designed for performance first, and that has a negative impact on how we design/deploy management, security, and fault-tolerant protocols.