Linked decompositions of networks and the power of choice in Polya urns

ABSTRACT

A linked decomposition of a graph with n nodes is a set of subgraphs covering the n nodes such that all pairs of subgraphs intersect; we seek linked decompositions such that all subgraphs have about √n vertices, logarithmic diameter, and each vertex of the graph belongs to either one or two subgraphs. A linked decomposition enables many control and management functions to be implemented locally, such as resource sharing, maintenance of distributed directory structures, deadlock-free routing, failure recovery and load balancing, without requiring any node to maintain information about the state of the network outside the subgraphs to which it belongs. Linked decompositions also enable efficient routing, schemes with small routing tables, which we describe in Section 5. Our main contribution is to show that "Internet-like graphs" (e.g. the preferential attachment model proposed by Barabasi et al. [10] and other similar models) have linked decompositions with the parameters described above with high probability; moreover, our experiments show that the Internet topology itself can be so decomposed. Our proof proceeds by analyzing a novel process, which we call Polya urns with the power of choice, which may be of great independent interest. In this new process, we start with n nonempty bins containing O(n) balls total, and each arriving ball is placed in the least loaded of m bins, drawn independently at random with probability proportional to load. Our analysis shows that in our new process, with high probability the bin loads become roughly balanced some time before O(n^2+ε) further balls have arrived and stay roughly balanced, regardless of how the initial O(n) balls were distributed, where ε > 0 can be arbitrarily small, provided m is large enough.

REFERENCES

• 1: NewArch Project: Future-Generation Internet Architecture. http://www.isi.edu/newarch/.
• 2: FIND: Future Internet Network Design. http://find.isi.edu/, 2005.
• 3: GENI: Global Environment for Network Innovations. http://www.geni.net/, 2005.
• 4: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007916]
• 5: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 6: Marta Arias , Lenore J. Cowen , Kofi A. Laing , Rajmohan Rajaraman , Orjeta Taka, Compact routing with name independence, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777442]
• 7: Baruch Awerbuch, Andrew Goldberg, Michael Luby, and Serge Plotkin. Network decompositions and locality in distributed computation. 1989.
• 8: Baruch Awerbuch and David Peleg. Sparse partitions. 1990.
• 9: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195412]
• 10: A. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 11: B. Bollobás and O. Riordan. Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks. Wiley-VCH, Berlin, 2002.
• 12: Matthew Caesar , Tyson Condie , Jayanthkumar Kannan , Karthik Lakshminarayanan , Ion Stoica, ROFL: routing on flat labels, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 13: F. Chung, S. Handjani, and D. Jungreis. Generalizations of polya's urn problem. Annals of Combinatorics, 7:141--153, 2003.
• 14: A. Frieze, A. Flaxman, and T. Fenner. High degree vertices and eigenvalues in the preferential attachment graph. Internet Mathematics, 2:1--20, 2005.
• 15: Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
• 16: D. Krioukov, K. Fall, and X. Yang. Compact routing on internet-like graphs. INFOCOM, 2004.
• 17: D. Krioukov and kc claffy. Toward compact interdomain routing. arXiv:cs.NI/0508021.
• 18: Milena Mihail , Christos Papadimitriou , Amin Saberi, On Certain Connectivity Properties of the Internet Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.28, October 11-14, 2003
• 19: Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1094-1104, October 2001 [doi>10.1109/71.963420]
• 20: David Peleg and Alejandro A. Schaffer. Graph spanners. 1989.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Theory