fnss.topologies.simplemodels.chord_topology

chord_topology(m, r=1)[source]

Return a Chord topology, as described in [1]:

Chord is a Distributed Hash Table (DHT) providing guaranteed correctness. In Chord, both nodes and keys are identified by sequences of m bits. Keys can be resolved in at most log(n) steps (with n being the number of nodes) as long as each node maintains a routing table o n entries.

In this implementation, it is possible only to generate topologies with a number of nodes n = 2^m. where m is the length (in bits) of the keys used by Chord and also corresponds the the size of the finger table kept by each node.

The r argument is the number of nearest successors which can be optionally kept at each node to guarantee correctness in case of node failures.

Parameters:
m : int

The length of keys (in bits), which also corresponds to the length of the finger table of each node

r : int, optional

The length of the nearest successors table
Returns:
G : DirectedTopology

A Chord topology

References

[1](1, 2) I. Stoica, R. Morris, D. Karger, M. Frans Kaashoek, H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. Proceedings of the ACM SIGCOMM 2001 conference on Data communication (SIGCOMM ‘09). ACM, New York, NY, USA.