Dmitri Krioukov

On Cycles in AS Relationships

Xenofontas Dimitropoulos, M. Ángeles Serrano, and Dmitri Krioukov
Appears in: 
CCR July 2008

Several users of our AS relationship inference data asked us why it contained AS relationship cycles, e.g., cases where AS A is a provider of AS B, B is a provider of C, and C is a provider of A, or other cycle types. Having been answering these questions in private communications, we have eventually decided to write down our answers here for future reference.

Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies

Priya Mahadevan, Calvin Hubble, Dmitri Krioukov, Bradley Huffaker, and Amin Vahdat
Appears in: 
CCR October 2007

Researchers involved in designing network services and protocols rely on results from simulation and emulation environments to evaluate correctness, performance and scalability. To better understand the behavior of these applications and to predict their performance when deployed across the Internet, the generated topologies that serve as input to simulated and emulated environments must closely match real network characteristics, not just in terms of graph structure (node interconnectivity) but also with respect to various node and link annotations.

On Compact Routing for the Internet

Dmitri Krioukov, k c claffy, Kevin Fall, and Arthur Brady
Appears in: 
CCR July 2007

The Internet’s routing system is facing stresses due to its poor fundamental scaling properties. Compact routing is a research field that studies fundamental limits of routing scalability and designs algorithms that try to meet these limits. In particular, compact routing research shows that shortest-path routing, forming a core of traditional routing algorithms, cannot guarantee routing table (RT) sizes that on all network topologies grow slower than linearly as functions of the network size.

Public Review By: 
Dina Katabi

Currently network operators are very sensitive to the growth rate of the Internet routing table. Compact routing provides a hopeful direction for solving that problem. However, as the theorists continue to look at improving the bounds on various flavors of the problem, it is important to ask the question of how all this theory applies to the Internet.
This paper is largely a survey paper of past theoretical results in this area. But the reviewers felt that it was appropriate for CCR because it does more than just surveying the past results. It provides a numerical comparison of the various techniques, discusses how they apply to the Internet, and extends a few of the results for the specific case of the Internet.
The paper basically concludes that currently proposed compact routing schemes may prove useful in reducing the routing table size; they however cannot reduce the rate of growth of update traffic to less than linear.
The reviewers were concerned that all of the cited work on compact routing considers only the case of shortest-path routing, which is used on the Internet only for routing within an ISP. Scaling becomes a problem, however, only when considering the case of inter-domain routing (routing between ISP’s), and this fundamentally relies on the use of various non-shortest-path routing polices in order to meet economic incentives. While this does not mean that compact routing will not prove to be a useful technique, it does call into question how much the techniques and bounds in the paper apply to the problem of interdomain Internet routing.
All in all however, the reviewers felt this paper addresses an important timely problem, and provides a valuable discussion of a research direction that may eventually provide a solution to this problem.

The Workshop on Internet Topology (WIT) Report

Dmitri Krioukov, kc claffy, Marina Fomenkov, Fan Chung, Alessandro Vespignani, and Walter Willinger
Appears in: 
CCR January 2007

Internet topology analysis has recently experienced a surge of interest in computer science, physics, and the mathematical sciences. However, researchers from these different disciplines tend to approach the same problem from different angles. As a result, the field of Internet topology analysis and modeling must untangle sets of inconsistent findings, conflicting claims, and contradicting statements.

AS Relationships: Inference and Validation

Xenofontas Dimitropoulos, Dmitri Krioukov, Marina Fomenkov, Bradley Huffaker, Young Hyun, kc claffy, and George Riley
Appears in: 
CCR January 2007

Research on performance, robustness, and evolution of the global Internet is fundamentally handicapped without accurate and thorough knowledge of the nature and structure of the contractual relationships between Autonomous Systems (ASs). In this work we introduce novel heuristics for inferring AS relationships. Our heuristics improve upon previous works in several technical aspects, which we outline in detail and demonstrate with several examples. Seeking to increase the value and reliability of our inference results, we then focus on validation of inferred AS relationships.

Public Review By: 
Ernst Biersack

Inferring AS relationships using publicly available data is a difficult task for which various heuristics have been proposed. This paper revisits the problem, points out shortcomings of existing heuristics, and proposes improvements. The reviewers liked the paper for several reasons:

  • The paper does a nice job in reviewing the state of the art and improves on the existing heuristics.
  • The authors try to asses the quality of their inferences by contacting a small group ASs whom they asked for an explicit validation of the results. However, the sample size may be too small to allow any definite conclusions.
  • The heuristics proposed are implemented and the results of the AS inference made publicly available on a weekly basis. This should provide a basis on which further research can build on
    and compare its results against.

In summary, this paper combines existing and new heuristics for AS inference into a tool, the results of which are made available to the community.

Syndicate content