Child pages
  • Hypergrid

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

The Hypergrid model for Peer-to-Peer (P2P) systems 1 builds a graph topology that enforces low graph diameter and fixed node degree. The Hypergrid graph grows as a simple k-ary tree with nodes on the leaf level of the tree having their k-1 free edges randomly connected to other nodes on the same level in the tree with degree less than k.

Initially graph consists of a single node with no edges. For a new node N to join the graph, it looks for a parent node in the graph which has free edges. A horizontal edge between the parent node and another node, on the same level as that of parent node, is removed. The new node then connects to this parent node and also to k-1 other nodes on the same level in the graph. A typical hypergrid network layout is given above. Image Added

...

Pros &

...

Cons

Applicable to network graphs only. Hypergrid model imposes minimal network growth policies. It focuses on growing a network with the desirable low diameter of small world systems using only local information. It strives for complete decentralization of network growth and is topologically more robust. But the search cost on Hypergrid network models is very high.

...