# chord.py   [plain text]

```# Twisted, the Framework of Your Internet
# Copyright (C) 2001 Matthew W. Lefkowitz
#
# This library is free software; you can redistribute it and/or
# modify it under the terms of version 2.1 of the GNU Lesser General Public
#
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with this library; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

# TODO:
# failure detection
# successor list
# HyperChord

import random
import sha
import socket
import struct

NBIT = 160    # Size (in bits) of Chord identifiers
vNodes = 1    # sure hope you dont want more than 256.

def between(n, a, b):
"""Check if n in interval(a, b) on the circle."""
if   a == b: return n != a			# n is the only node not in (n, n)
elif a < b: return n > a and n < b
else: return n > a or n < b

def betweenL(n, a, b):
"""Check if n in interval[a, b) on the circle."""
if a == b and n == a: return 1
elif a < b: return n >= a and n < b
else: return n >= a or n < b

def betweenR(n, a, b):
"""Check if n in interval(a, b] on the circle."""
if a == b and n == a: return 1
elif a < b: return n > a and n <= b
else: return n > a or n <= b

class Node(pb.Copyable, pb.Perspective):
"""A node in a Chord network."""

def __init__(self, address, perspectiveName, identityName, port=pb.portno):
global vNodes
pb.Perspective.__init__(self, perspectiveName, identityName)
self.id = sha.new(socket.inet_aton(address) + struct.pack('!h', port) + chr(vNodes)).digest()
vNodes = vNodes + 1
self.finger = [None] * (NBIT+1)
self.lastFixed = 1  # Needed for fixFingers
self.pred = None

def getStateToCopyFor(self, persp):

def __repr__(self):
return "<Node " + `self.id` + ">"

def join(self, n2):
"""Intialize finger tables of local node.
n2 is a node already on the network or None if we're the first."""
if n2:
for i in range(1, NBIT):
if betweenL(self.id, self.start(i+1),
self.finger[i].id):
self.finger[i+1] = self.finger[i]
else:
else:
self.finger[1] = None
self.pred = None

def _setFingerCallback(self, x, i):
#CRUM! DEFEATED BY DISTANCE
self.finger[i] = x

def _setPredCallback(self, n):
#ALSO TOO FAR!
self.pred = n

def perspective_getSuccessor(self):
return self.finger[1]

def perspective_getPredecessor(self):
return self.pred

def perspective_findSuccessor(self, id):

def findSuccessor_1(self, n2):

else:

def findPredecessor(self, id):
if self.finger[1] is None:
return self
n2 = self
return self.findPredecessor_1(n2, id)

def findPredecessor_1(self, n2, id):

def findPredecessor_2(self, n3, n2, id):
if not betweenR(id, n2.id, n3.id):
else:
return n2

def perspective_closestPrecedingFinger(self, id):
for i in xrange(NBIT, 0, -1):
if not self.finger[i]: continue
if between(self.finger[i].id, self.id, id):

def getSelf(self):
# necessary to produce proper Copyable behaviour
return self

def stabilise(self):
"""Verify our immediate successor and tell them about us.
Called periodically."""

def stabilise_1(self, p):
self.perspective_notify(p)

def fixFingers(self):
"""Refresh a random finger table entry.
Called periodically."""
i = random.randrange(1, len(self.finger)+1)
self.finger[i] = self.findSuccessor(self.start(i))

"""n thinks it might be our predecessor."""

def notify(self, n):
if (self.pred is self or self.pred is None or
between(n.id, self.pred.id, self.id)):
self.pred = n
if self.finger[1] is None or between(n.id, self.id, self.finger[1].id):
self.finger[1] = n
for i in xrange(2, len(self.finger)):
if self.finger[i] is None or betweenL(n.id, self.start(i), self.finger[i].id):
self.finger[i] = n

def start(self, k):
assert 1 <= k <= NBIT
r = (self.id + 2L**(k-1)) % 2L**NBIT
if r == 0:
return 2L**NBIT
else:
return r

class ChordService(pb.Service):
def __init__(self, address, port, serviceName, application=None):
pb.Service.__init__(self, serviceName, application)