Kademlia.h

Go to the documentation of this file.

//
// Copyright (C) 2006 Institut fuer Telematik, Universitaet Karlsruhe (TH)
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program 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 General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//

#ifndef __KADEMLIA_H_
#define __KADEMLIA_H_

#include <deque>
#include <omnetpp.h>

#include <CommonMessages_m.h>
#include <BaseOverlay.h>
#include <GlobalStatistics.h>
#include <NeighborCache.h>

#include "KademliaNodeHandle.h"
#include "KademliaBucket.h"


class Kademlia : public BaseOverlay, public ProxListener
{
protected://fields: kademlia parameters

    uint32_t k; /*< number of redundant graphs */
    uint32_t b; /*< number of bits to consider */
    uint32_t s; /*< number of siblings         */

    uint32_t maxStaleCount; /*< number of timouts until node is removed from
                            routingtable */

    bool exhaustiveRefresh; /*< if true, use exhaustive-iterative lookups to refresh buckets */
    bool pingNewSiblings;
    bool secureMaintenance; 
    bool newMaintenance;

    bool enableReplacementCache; /*< enables the replacement cache to store nodes if a bucket is full */
    bool replacementCachePing; /*< ping the least recently used node in a full bucket, when a node is added to the replacement cache */
    uint replacementCandidates; /*< maximum number of candidates in the replacement cache for each bucket */
    int siblingRefreshNodes; /*< number of redundant nodes for exhaustive sibling table refresh lookups (0 = numRedundantNodes) */
    int bucketRefreshNodes; /*< number of redundant nodes for exhaustive bucket refresh lookups (0 = numRedundantNodes) */

    // R/Kademlia
    bool activePing;
    bool proximityRouting;
    bool proximityNeighborSelection;
    bool altRecMode;

    simtime_t minSiblingTableRefreshInterval;
    simtime_t minBucketRefreshInterval;
    simtime_t siblingPingInterval;

    cMessage* bucketRefreshTimer;
    cMessage* siblingPingTimer;

public:
    Kademlia();

    ~Kademlia();

    void initializeOverlay(int stage);

    void finishOverlay();

    void joinOverlay();

    bool isSiblingFor(const NodeHandle& node,const OverlayKey& key,
                      int numSiblings, bool* err );

    int getMaxNumSiblings();

    int getMaxNumRedundantNodes();

    void handleTimerEvent(cMessage* msg);

    bool handleRpcCall(BaseCallMessage* msg);

    void handleUDPMessage(BaseOverlayMessage* msg);

    virtual void proxCallback(const TransportAddress& node, int rpcId,
                              cPolymorphic *contextPointer, Prox prox);

protected:
    NodeVector* findNode(const OverlayKey& key,
                         int numRedundantNodes,
                         int numSiblings,
                         BaseOverlayMessage* msg);

    void handleRpcResponse(BaseResponseMessage* msg,
                           cPolymorphic* context,
                           int rpcId, simtime_t rtt);

    void handleRpcTimeout(BaseCallMessage* msg, const TransportAddress& dest,
                          cPolymorphic* context, int rpcId,
                          const OverlayKey& destKey);

    void handleBucketRefreshTimerExpired();

    OverlayKey distance(const OverlayKey& x,
                        const OverlayKey& y,
                        bool useAlternative = false) const;

    void updateTooltip();

    virtual void lookupFinished(bool isValid);

    virtual void handleNodeGracefulLeaveNotification();

    friend class KademliaLookupListener;

#ifdef PAIL
    AbstractProxKeyComparator* getProxKeyComparator(const OverlayKey& relativeKey,
                                                    uint8_t bitsPerDigit,
                                                    const AdjustableProxComparator* apc) {
        return new KademliaPRComparator(relativeKey, bitsPerDigit);
    };
#endif
private:
    uint32_t bucketRefreshCount; /*< statistics: total number of bucket refreshes */
    uint32_t siblingTableRefreshCount; /*< statistics: total number of sibling table refreshes */
    uint32_t nodesReplaced;

    KeyDistanceComparator<KeyXorMetric>* comparator;

    KademliaBucket*  siblingTable;
    std::vector<KademliaBucket*> routingTable;
    int numBuckets;

    void routingInit();

    void routingDeinit();

    int routingBucketIndex(const OverlayKey& key, bool firstOnLayer = false);

    KademliaBucket* routingBucket(const OverlayKey& key, bool ensure);

    bool routingAdd(const NodeHandle& handle, bool isAlive,
                    simtime_t rtt = MAXTIME, bool maintenanceLookup = false);

    bool routingTimeout(const OverlayKey& key, bool immediately = false);

    void refillSiblingTable();

    void sendSiblingFindNodeCall(const TransportAddress& dest);

    void setBucketUsage(const OverlayKey& key);

    bool recursiveRoutingHook(const TransportAddress& dest,
                              BaseRouteMessage* msg);

    bool handleFailedNode(const TransportAddress& failed);
};

#endif