application-chord.h

Go to the documentation of this file.

/*
 *  $Id: application-chord.h 502 2006-08-14 15:30:40Z dheeraj $
 *
 *  application-chord.h by Dr. Sven Krasser
 *
 *  An implementation of the Chord distributed hash table for GTNetS based on
 *  Stoica et al. "Chord: A Scalable Peer-to-peer Lookup Service for Internet
 *  Applications," ACM SIGCOMM 2001, San Deigo, CA, August 2001, pp. 149-160.
 *
 *  For more information see
 *  http://www.ece.gatech.edu/research/labs/nsa/gtnets/chord.shtml
 *
 */

// GENERAL PUBLIC LICENSE AGREEMENT
//
// PLEASE READ THIS DOCUMENT CAREFULLY BEFORE UTILIZING THE PROGRAM
//
// BY UTILIZING THIS PROGRAM, YOU AGREE TO BECOME BOUND BY THE TERMS OF
// THIS LICENSE.  IF YOU DO NOT AGREE TO THE TERMS OF THIS LICENSE, DO
// NOT USE THIS PROGRAM OR ANY PORTION THEREOF IN ANY FORM OR MANNER.
//
// This Program is licensed, not sold to you by GEORGIA TECH RESEARCH
// CORPORATION ("GTRC"), owner of all code and accompanying documentation
// (hereinafter "Program"), for use only under the terms of this License,
// and GTRC reserves any rights not expressly granted to you.
//
// 1.  This License allows you to:
//
// (a) make copies and distribute copies of the Program's source code
// provide that any such copy clearly displays any and all appropriate
// copyright notices and disclaimer of warranty as set forth in Article 5
// and 6 of this License.  All notices that refer to this License and to
// the absence of any warranty must be kept intact at all times.  A copy
// of this License must accompany any and all copies of the Program
// distributed to third parties.
//
// A fee may be charged to cover the cost associated with the physical
// act of transferring a copy to a third party.  At no time shall the
// program be sold for commercial gain either alone or incorporated with
// other program(s) without entering into a separate agreement with GTRC.
//
//
// (b) modify the original copy or copies of the Program or any portion
// thereof ("Modification(s)").  Modifications may be copied and
// distributed under the terms and conditions as set forth above,
// provided the following conditions are met:
//
//     i) any and all modified files must be affixed with prominent
// notices that you have changed the files and the date that the changes
// occurred.
//
//     ii) any work that you distribute, publish, or make available, that
// in whole or in part contains portions of the Program or derivative
// work thereof, must be licensed at no charge to all third parties under
// the terms of this License.
//
//    iii) if the modified program normally reads commands interactively
// when run, you must cause it, when started running for such interactive
// use in the most ordinary way, to display and/or print an announcement
// with all appropriate copyright notices and disclaimer of warranty as
// set forth in Article 5 and 6 of this License to be clearly displayed.
// In addition, you must provide reasonable access to this License to the
// user.
//
// Any portion of a Modification that can be reasonably considered
// independent of the Program and separate work in and of itself is not
// subject to the terms and conditions set forth in this License as long
// as it is not distributed with the Program or any portion thereof.
//
//
// 2. This License further allows you to copy and distribute the Program
//    or a work based on it, as set forth in Article 1 Section b in
//    object code or executable form under the terms of Article 1 above
//    provided that you also either:
//
//    i) accompany it with complete corresponding machine-readable source
// code, which must be distributed under the terms of Article 1, on a
// medium customarily used for software interchange; or,
//
//   ii) accompany it with a written offer, valid for no less than three
// (3) years from the time of distribution, to give any third party, for
// no consideration greater than the cost of physical transfer, a
// complete machine-readable copy of the corresponding source code, to be
// distributed under the terms of Article 1 on a medium customarily used
// for software interchange; or,
//
//
// 3.  Export Law Assurance.
//
// You agree that the Software will not be shipped, transferred or
// exported, directly into any country prohibited by the United States
// Export Administration Act and the regulations thereunder nor will be
// used for any purpose prohibited by the Act.
//
// 4.  Termination.
//
// If at anytime you are unable to comply with any portion of this
// License you must immediately cease use of the Program and all
// distribution activities involving the Program or any portion thereof.
//
//
// 5.  Disclaimer of Warranties and Limitation on Liability.
//
// YOU ACCEPT THE PROGRAM ON AN "AS IS" BASIS.  GTRC MAKES NO WARRANTY
// THAT ALL ERRORS CAN BE OR HAVE BEEN ELIMINATED FROM PROGRAM.  GTRC
// SHALL NOT BE RESPONSIBLE FOR LOSSES OF ANY KIND RESULTING FROM THE USE
// OF PROGRAM AND ITS ACCOMPANYING DOCUMENT(S), AND CAN IN NO WAY PROVIDE
// COMPENSATION FOR ANY LOSSES SUSTAINED, INCLUDING BUT NOT LIMITED TO
// ANY OBLIGATION, LIABILITY, RIGHT, CLAIM OR REMEDY FOR TORT, OR FOR ANY
// ACTUAL OR ALLEGED INFRINGEMENT OF PATENTS, COPYRIGHTS, TRADE SECRETS,
// OR SIMILAR RIGHTS OF THIRD PARTIES, NOR ANY BUSINESS EXPENSE, MACHINE
// DOWNTIME OR DAMAGES CAUSED TO YOU BY ANY DEFICIENCY, DEFECT OR ERROR
// IN PROGRAM OR MALFUNCTION THEREOF, NOR ANY INCIDENTAL OR CONSEQUENTIAL
// DAMAGES, HOWEVER CAUSED.  GTRC DISCLAIMS ALL WARRANTIES, BOTH EXPRESS
// AND IMPLIED RESPECTING THE USE AND OPERATION OF PROGRAM AND ITS
// ACCOMPANYING DOCUMENTATION, INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR PARTICULAR PURPOSE AND ANY IMPLIED
// WARRANTY ARISING FROM COURSE OF PERFORMANCE, COURSE OF DEALING OR
// USAGE OF TRADE.  GTRC MAKES NO WARRANTY THAT PROGRAM IS ADEQUATELY OR
// COMPLETELY DESCRIBED IN, OR BEHAVES IN ACCORDANCE WITH ANY
// ACCOMPANYING DOCUMENTATION.  THE USER OF PROGRAM IS EXPECTED TO MAKE
// THE FINAL EVALUATION OF PROGRAM'S USEFULNESS IN USER'S OWN
// ENVIRONMENT.
//
// GTRC represents that, to the best of its knowledge, the software
// furnished hereunder does not infringe any copyright or patent.
//
// GTRC shall have no obligation for support or maintenance of Program.
//
// 6.  Copyright Notice.
//
// THE SOFTWARE AND ACCOMPANYING DOCUMENTATION ARE COPYRIGHTED WITH ALL
// RIGHTS RESERVED BY GTRC.  UNDER UNITED STATES COPYRIGHT LAWS, THE
// SOFTWARE AND ITS ACCOMPANYING DOCUMENTATION MAY NOT BE COPIED EXCEPT
// AS GRANTED HEREIN.
//
// You acknowledge that GTRC is the sole owner of Program, including all
// copyrights subsisting therein.  Any and all copies or partial copies
// of Program made by you shall bear the copyright notice set forth below
// and affixed to the original version or such other notice as GTRC shall
// designate.  Such notice shall also be affixed to all improvements or
// enhancements of Program made by you or portions thereof in such a
// manner and location as to give reasonable notice of GTRC's copyright
// as set forth in Article 1.
//
// Said copyright notice shall read as follows:
//
// Copyright 2004
// Dr. George F. Riley
// Georgia Tech Research Corporation
// Atlanta, Georgia 30332-0415
// All Rights Reserved


#ifndef __APPLICATION_CHORD_H__
#define __APPLICATION_CHORD_H__

#include <iostream>

#include "udp.h"
#include "application.h"
#include "node.h"
#include "pdu.h"
#include "common-defs.h"
#include "sha1.h"
#include "object.h"
#include "chord-stats.h"
#include "chord-vis.h"

#include "sys/types.h"

#define CHORD_STD_PORT 30000      // default UDP port to which to bind
#define CHORD_MAX_XMIT_ATTEMPTS 3 // number of times to try to transmit a message


//#define CHORD_DEBUG

#ifdef CHORD_DEBUG
#define CDBG(cmd) cmd
#define CDBGPR(str) cout << Simulator::Now() << ": " str << endl
#else
#define CDBG(cmd)
#define CDBGPR(str)
#endif

#define STATSLOG(msg) \
        if(stats) \
                *stats << Simulator::Now() << " " << msg << "\n"

typedef enum { REQUEST, RESPONSE } ChordMsgType_t;
typedef enum { FIND_SUCCESSOR, NOTIFY, GET_PREDECESSOR, CHECK_PREDECESSOR } ChordMsg_t;
typedef unsigned long ChordResolverId_t;

class Chord;
class ChordPDU;
class ChordJoinResolver;
class ChordFingerResolver;

class ChordEvent : public Event {
        public:
                typedef enum { FIX_FINGERS = 100, STABILIZE, CREATE, JOIN,
                        CHECK_PREDECESSOR, TIMEOUT, IGNORE_MSG_ON, IGNORE_MSG_OFF,
                        DIE } ChordEvent_t;
                ChordEvent() { }
                ChordEvent(Event_t e) : Event(e) { }
                
                ChordMsg_t msg; // For TIMEOUT: What message triggered it
};

class ChordResolverEvent : public Event {
        public:
                typedef enum { TIMEOUT } ChordResolverEvent_t;
                ChordResolverEvent() { }
                ChordResolverEvent(Event_t e) : Event(e) { }
};


class ChordId {
        public:
                ChordId();
                ChordId(unsigned b); // ChordId with b-th bit set to 1;
                ChordId(unsigned, unsigned, unsigned, unsigned, unsigned);
                
                void Init();
                
                bool operator==(ChordId cid);
                bool operator!=(ChordId cid);
                bool operator>=(ChordId cid);
                bool operator<=(ChordId cid);
                bool operator>(ChordId cid);
                bool operator<(ChordId cid);
                ChordId operator+(ChordId cid);
                
                friend ostream& operator<<(ostream &os, ChordId cid);

                // These methods take into account that the Chord ring is not
                // continuous at Id zero. Assumptions are that a lies ccw from a
                // and that the interval extends cw from a to b.
                // OO = left open, right open
                // OC = left open, right closed (right value is part of interval)
                

                bool InIntervalOC(ChordId a, ChordId b);
                bool InIntervalOO(ChordId a, ChordId b);

                void SetId(unsigned, unsigned, unsigned, unsigned, unsigned);
                static void SetBitLength(unsigned char mb) { m = mb; };
                static unsigned char GetBitLength() { return m; }
                ChordId MaskBits(unsigned char mb);
                ChordId MaskBits() { return MaskBits(m); }

                unsigned id[5]; 
                                // Each element has 32 bits
                
        protected:
                // The bitlength has been changed to be static:
                static unsigned char m;
                
};



class ChordFinger {
        public:
                ChordFinger() : ip(0) {}
                ChordFinger(ChordId aid, IPAddr_t aip, PortId_t ap) { id = aid; ip = aip; port = ap; }

                ChordId GetId() { return id; }
                IPAddr_t GetIP() { return ip; }
                PortId_t GetPort() { return port; }
                bool IsUnset() { return ip == 0; }
                bool IsSet() { return ip != 0; }
                void Clear() { ip = 0; }
                
                friend ostream& operator<<(ostream &os, ChordFinger f);
                
                ChordId id;
                IPAddr_t ip;
                PortId_t port;
};


class ChordFingerTable : public Object {
        public:
                ChordFingerTable();
                ChordFingerTable(unsigned int size);
                ~ChordFingerTable();
                                

                ChordFinger GetFinger(unsigned int index) { return table[index - 1]; }
                void SetFinger(unsigned int index, ChordFinger finger) {
                        CDBGPR(<< "changing finger " << index << " in table " << Name()
                               << " to " << finger);
                        STATSLOG("finger " << index << " " << cid << " " << finger.GetId());
                        table[index - 1] = finger;
                }

                // finger[1] is the successor (stored in table[0])
                ChordFinger GetSuccessor() { return table[0]; }
                void SetSuccessor(ChordFinger finger) {
                        CDBGPR(<< "changing successor in table " << Name()
                               << " to " << finger);
                        STATSLOG("finger 1 " << cid << " " << finger.GetId());
                        table[0] = finger;
                }
                
                void SetSize(unsigned int);
                
                void Print();
                
                void SetId(ChordId i) { cid = i; }
                
        protected:
                void AllocTable();
                
                ChordFinger *table;
                unsigned int table_size;
        
                ChordId cid;
        
                ChordStats *stats;
};



class ChordResolver : public Handler {
        public:
                ChordResolver();

                virtual void FindSuccessor(ChordId);
                virtual void HandleFindSuccessorResponse(ChordPDU*);
                virtual void HandleFoundSuccessor(ChordPDU*);
                virtual void HandleFoundSuccessor(ChordFinger);
                virtual void HandleFailed();
                virtual void Failed(ChordFinger);
                virtual void FoundSuccessor(ChordFinger);
                virtual void AttachChord(Chord* ach) { ch = ach; }
                virtual void SetResolverId(ChordResolverId_t crid) { resolver_id = crid; }
                virtual bool IsBusy() { return busy; }
                virtual ChordResolverId_t GetResolverId() { return resolver_id; }
                virtual void Handle(Event*, Time_t);
                virtual void CancelTimeout();
                
        protected:
                Chord *ch;
                ChordStats *stats;
                ChordResolverId_t resolver_id;  
                
                unsigned long next_seq_no;      
                unsigned long hi_seq_no;        
                
                bool busy;                      
                ChordId resolving_cid;          
                ChordFinger resolving_peer;     
                ChordResolverEvent *timeout_event;
                unsigned short timeout_count;
};



class Chord : public Application {
        public:
                Chord();
                Chord(const Chord&);
                Chord(unsigned short idbitlength);
                ~Chord();
                
                void Init();
                

                virtual void RegisterResolver(ChordResolver*);
                virtual void UnregisterResolver(ChordResolver*);
                                
                virtual void Create();
                virtual void Create(Time_t);
                virtual void Join(IPAddr_t, PortId_t);
                virtual void SetJoinNode(IPAddr_t, PortId_t);
                virtual void Join();
                virtual void Join(Time_t);
                virtual void Join(Time_t, IPAddr_t, PortId_t);
                virtual void Joined(ChordFinger);
                virtual ChordFinger ClosestPrecedingNode(ChordId);
                virtual void SetPort(PortId_t p);
                virtual void PrintFingerTable();
                virtual void SendFindSuccessorResponse(IPAddr_t, PortId_t, ChordId, unsigned long, ChordResolverId_t);
                virtual void SendFindSuccessorRequest(IPAddr_t, PortId_t, ChordId, unsigned long, ChordResolverId_t);
                virtual void SendNotifyResponse(IPAddr_t, PortId_t, unsigned long);
                virtual void SendNotifyRequest(IPAddr_t, PortId_t, unsigned long);
                virtual void SendGetPredecessorResponse(IPAddr_t, PortId_t, unsigned long);
                virtual void SendGetPredecessorRequest(IPAddr_t, PortId_t, unsigned long);
                virtual void SendCheckPredecessorResponse(IPAddr_t, PortId_t, unsigned long);
                virtual void SendCheckPredecessorRequest(IPAddr_t, PortId_t, unsigned long);
                
                // For testing purposes
                virtual void IgnoreMessagesOn() { ignore_messages = true; STATSLOG("ignore_msg on " << my_id); CDBGPR( << my_id << ": Ignoring messages ON."); }
                virtual void IgnoreMessagesOn(Time_t);
                virtual void IgnoreMessagesOff() { ignore_messages = false; STATSLOG("ignore_msg off " << my_id); CDBGPR( << my_id << ": Ignoring messages OFF."); }
                virtual void IgnoreMessagesOff(Time_t);
                virtual void IgnoreMessages(Time_t, Time_t);
                
                virtual void Die();
                virtual void Die(Time_t);
                
                virtual ChordId GetMyId();
                virtual ChordFinger GetMyFinger() { return ChordFinger(GetMyId(), GetMyIP(), port); }
                // Fix me: Would be nice to use the IP address that UDP is actually binding to
                virtual IPAddr_t GetMyIP() { return localNode->GetIPAddr(); }
                virtual UDP* GetUDP() { return udp; }
                
                // Application methods
                virtual void Receive(Packet*, L4Protocol*, Seq_t = 0);   // Data received
                virtual void StartApp();           // Called at time specified by Start
                virtual void StopApp();            // Called at time specified by Stop
                virtual void AttachNode(Node*);    // Note which node attached to
                virtual Application* Copy() const { return new Chord(*this); } // Make a copy of the application
                virtual void Handle(Event*, Time_t);
                
                static ChordStats* GetStats();
                static void UseVis(bool b) { use_vis = b; }
                
                unsigned short m;               // Number of bits for IDs
                
                Time_t stabilize_interval;      // Time interval between stabilization
                Time_t fix_fingers_interval;    // Time interval between fixing finger table
                Time_t predecessor_ping_interval;
                ChordFingerTable finger_table;  // The finger table holding routing information
                ChordFinger predecessor;        // The node before this one on the ring
                SHA1 sha1;                      // For hashing
                ChordId my_id;
                ChordFinger my_finger;
                Time_t rpc_timeout;             
                
        protected:
                virtual void Stabilize();
                virtual void HandleGetPredecessorResponse(ChordFinger);
                virtual void Notify();
                virtual void Notify(ChordFinger);
                virtual void NotifyTimeout();
                virtual void CheckPredecessor();
                virtual void CheckPredecessorTimeout();
                virtual void PredecessorDied();
                virtual void FixFinger();
                virtual void FixFinger(unsigned short index);
                virtual void GetPredecessor();
                virtual void GetPredecessorTimeout();
                virtual void InitEvents();
                
                UDP *udp;                       
                Node *localNode;                
                PortId_t port;                  
                ChordResolverId_t next_resolver_id;     
                map<ChordResolverId_t, ChordResolver*> resolver_demux;
                bool running;
                ChordFinger result_finger;
                ChordJoinResolver *join_resolver;
                ChordFingerResolver *finger_resolver;
                bool joined;
                unsigned short next_finger_to_fix;
                unsigned long next_notify_seq_no;
                unsigned long next_get_predecessor_seq_no;
                unsigned long next_check_predecessor_seq_no;
                unsigned long hi_notify_seq_no;
                unsigned long hi_get_predecessor_seq_no;
                unsigned long hi_check_predecessor_seq_no;
                IPAddr_t join_ip;
                PortId_t join_port;
                ChordEvent *stabilize_event;    
                ChordEvent *fix_fingers_event;  
                ChordEvent *check_predecessor_event; 
                ChordEvent *check_predecessor_timeout_event;
                ChordEvent *get_predecessor_timeout_event;
                ChordEvent *notify_timeout_event;
                ChordEvent *join_event;
                ChordEvent *create_event;
                ChordEvent *die_event;
                
                // Timeout counters
                unsigned short check_predecessor_timeout;
                unsigned short get_predecessor_timeout;
                unsigned short notify_timeout;
                
                // Stores the successor to be notified. This is necessary since the
                // successor in the finger table may change, but a resend should
                // still be sent to the original entry.
                ChordFinger succ_notify;
                
                // Same for GET_PREDECESSOR
                ChordFinger succ_get_pred;
                
                bool ignore_messages;
                
                static ChordStats *stats;
                friend class ChordStats;
                static bool use_vis;
};

class ChordJoinResolver : public ChordResolver {
        public:
                ChordJoinResolver() : ChordResolver() { }
                virtual void FoundSuccessor(ChordFinger finger) { ch->Joined(finger); }
};


class ChordFingerResolver : public ChordResolver {
        public:
                ChordFingerResolver() : ChordResolver(), finger_index(1) { }
                ChordFingerResolver(unsigned int index) : ChordResolver() { finger_index = index; }
                virtual void SetIndex(unsigned int index) { finger_index = index; }
                virtual void FoundSuccessor(ChordFinger finger);
                void Failed(ChordFinger failed_peer);
        protected:
                unsigned int finger_index;
};

class ChordPDU : public Data {
        public:
                ChordPDU();
                ChordPDU(Size_t);
                
                Size_t Size() const { return size;}
                PDU* Copy() const { return new ChordPDU(*this); }
                
                ChordMsgType_t type;
                ChordMsg_t msg;
                ChordId id;
                ChordFinger finger;
                unsigned long seq_no;
                ChordResolverId_t resolver;
                bool redirect;
                
                Size_t size;
                
                friend ostream& operator<<(ostream &os, ChordPDU &cp);
};

#endif

---