IterativeLookup.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 __ITERATIVE_LOOKUP_H
#define __ITERATIVE_LOOKUP_H

#include <vector>
#include <oversim_mapset.h>

#include <IterativeLookupConfiguration.h>
#include <AbstractLookup.h>
#include <RpcListener.h>

#include <NodeVector.h>
#include <Comparator.h>

class NodeHandle;
class OverlayKey;
class LookupListener;
class IterativeLookup;
class IterativePathLookup;
class BaseOverlay;

static const double LOOKUP_TIMEOUT = 10.0;

class LookupEntry {
public:
    NodeHandle handle;
    NodeHandle source;
    bool alreadyUsed;

    LookupEntry(const NodeHandle& handle, const NodeHandle& source,
                bool alreadyUsed) : handle(handle), source(source),
                                    alreadyUsed(alreadyUsed) {};

    LookupEntry() : handle(NodeHandle::UNSPECIFIED_NODE),
                    source(NodeHandle::UNSPECIFIED_NODE), alreadyUsed(false) {};


};

typedef BaseKeySortedVector< LookupEntry > LookupVector;

template <>
struct KeyExtractor<LookupEntry> {
    static const OverlayKey& key(const LookupEntry& nodes)
    {
        return nodes.handle.getKey();
    };
};

class IterativeLookup : public RpcListener,
                        public AbstractLookup,
                        public Comparator<OverlayKey>
{
    friend class IterativePathLookup;
    friend class BaseOverlay;

protected:
    virtual IterativePathLookup* createPathLookup();

    virtual FindNodeCall* createFindNodeCall(cPacket *findNodeExt = NULL);

    //-------------------------------------------------------------------------
    //- Base configuration and state ------------------------------------------
    //-------------------------------------------------------------------------
protected:
    OverlayKey key;                 
    BaseOverlay* overlay;           
    LookupListener* listener;       
    std::vector<IterativePathLookup*> paths;  
    RoutingType routingType;        
    IterativeLookupConfiguration config; 
    cPacket* firstCallExt;          
    uint32_t finishedPaths;             
    uint32_t successfulPaths;           
    uint32_t accumulatedHops;           
    bool finished;                  
    bool success;                   
    bool running;                   
    int retries;                    
    bool appLookup;
    SimTime startTime;              
public://virtual methods: comparator induced by distance in BaseOverlay
    virtual int compare(const OverlayKey& lhs,
                        const OverlayKey& rhs/*,
                        bool useAlternativeMetric = false*/) const;

    //-------------------------------------------------------------------------
    //- Siblings and visited nodes management---------------------------------
    //-------------------------------------------------------------------------
protected://fields
    NodeVector siblings;           
    TransportAddress::Set visited; 
    TransportAddress::Set dead;    
    TransportAddress::Set pinged;  
    typedef std::map<int,int> PendingPings;
    typedef std::set<NodeHandle> MajoritySiblings;
    MajoritySiblings majoritySiblings; 
    int numSiblings;               
    int hopCountMax;               
    PendingPings pendingPings;              
protected://methods
    bool addSibling(const NodeHandle& handle, bool assured = false);

    void setVisited(const TransportAddress& addr, bool visitedFlag = true);

    bool getVisited( const TransportAddress& addr);

    void setPinged(const TransportAddress& addr);

    bool getPinged(const TransportAddress& addr);

    void setDead(const TransportAddress& addr);

    bool getDead(const TransportAddress& addr);

    //-------------------------------------------------------------------------
    //- Parallel RPC distribution ---------------------------------------------
    //-------------------------------------------------------------------------
protected://fields and classes: rpc distribution

    class RpcInfo
    {
    public:
        //RpcInfo() { vrpcId = 0; proxVectorId = 0; path = NULL; };
        //~RpcInfo() { path = NULL;};
        int vrpcId;
        uint8_t proxVectorId;
        IterativePathLookup* path;
    };

    class RpcInfoVector : public std::vector<RpcInfo>
    {
    public:
        uint32_t nonce;
    };

    typedef UNORDERED_MAP<TransportAddress, RpcInfoVector, TransportAddress::hashFcn> RpcInfoMap;
    RpcInfoMap rpcs;

protected://methods: rpcListener
    virtual void handleRpcResponse(BaseResponseMessage* msg,
                           cPolymorphic* context,
                           int rpcId, simtime_t rtt);

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

protected://methods: rpc distribution

    void sendRpc(const NodeHandle& handle, FindNodeCall* call,
                 IterativePathLookup* listener, int rpcId);

    //-------------------------------------------------------------------------
    //- Construction & Destruction --------------------------------------------
    //-------------------------------------------------------------------------
public://construction & destruction
    IterativeLookup(BaseOverlay* overlay, RoutingType routingType,
               const IterativeLookupConfiguration& config,
               const cPacket* findNodeExt = NULL, bool appLookup = false);

    virtual ~IterativeLookup();

protected:
    virtual void start();
    void stop();
    void checkStop();

    //-------------------------------------------------------------------------
    //- AbstractLookup implementation -----------------------------------------
    //-------------------------------------------------------------------------
public://methods
    void lookup(const OverlayKey& key, int numSiblings = 1,
                int hopCountMax = 0, int retries = 0,
                LookupListener* listener = NULL);

    const NodeVector& getResult() const;

    bool isValid() const;
    void abortLookup();

    uint32_t getAccumulatedHops() const;
};

class IterativePathLookup
{
    friend class IterativeLookup;

protected://fields:
    IterativeLookup* lookup;
    BaseOverlay* overlay;

protected://fields: state
    int  hops;
    int  step;
    int  pendingRpcs;
    bool finished;
    bool success;
    LookupVector nextHops;
    std::map<TransportAddress, NodeHandle> oldNextHops;

protected://methods: rpc handling
    bool accepts(int rpcId);
    void handleResponse(FindNodeResponse* msg);
    void handleTimeout(BaseCallMessage* msg, const TransportAddress& dest,
                       int rpcId);
    void handleFailedNodeResponse(const NodeHandle& src,
                                  cPacket* findNodeExt, bool retry);

private:
    void sendRpc(int num, cPacket* FindNodeExt = NULL);

    void sendNewRpcAfterTimeout(cPacket* findNodeExt);

protected:
    IterativePathLookup(IterativeLookup* lookup);

    virtual ~IterativePathLookup();

    int add(const NodeHandle& handle,
            const NodeHandle& source = NodeHandle::UNSPECIFIED_NODE);
};

#endif