source: source/ariba/overlay/modules/chord/Chord.h@ 12771

// [License]
// The Ariba-Underlay Copyright
//
// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)
//
// Institute of Telematics
// UniversitÀt Karlsruhe (TH)
// Zirkel 2, 76128 Karlsruhe
// Germany
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ARIBA PROJECT OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// The views and conclusions contained in the software and documentation
// are those of the authors and should not be interpreted as representing
// official policies, either expressed or implied, of the Institute of
// Telematics.
// [License]

#ifndef CHORD_H_
#define CHORD_H_

#include "ariba/utility/system/Timer.h"
#include "ariba/utility/logging/Logging.h"
#include "ariba/communication/EndpointDescriptor.h"
#include "../OverlayInterface.h"
#include <vector>
#include <stdexcept>

class chord_routing_table;

namespace ariba {
namespace overlay {

class OverlayMsg;

using ariba::communication::EndpointDescriptor;
using ariba::utility::Timer;

using namespace std;

/**
 * This class implements a structured overlay inspired by chord.
 * It differs to the original form of chord in the following manner:
 *
 * (1) The graph is bidirectional
 * (2) Stabilization is done in a reactive manner
 *
 * It therefore can be considered as a kind of Chorded-Kademlia :)
 *
 * The resulting overlay graph has a diameter of O(log N).
 *
 * @author Sebastian Mies <mies@tm.uka.de>
 */
class Chord : public OverlayInterface, protected Timer {
        use_logging_h( Chord );
private:
        chord_routing_table* table;
        int orphan_removal_counter;
        int stabilize_counter;
        int stabilize_finger;
        vector<LinkID> bootstrapLinks;
        vector<NodeID> pending;
        vector<NodeID> discovery;
        int discovery_count;

        // helper: sets up a link using the "base overlay"
        LinkID setup( const EndpointDescriptor& endp,
                const NodeID& node = NodeID::UNSPECIFIED );

        // helper: sends a message over a link using the "base overlay"
        void send( OverlayMsg* msg, const LinkID& link );

        // helper: sends a message to a node using the "base overlay"
        void send_node( OverlayMsg* message, const NodeID& remote );
                
        // stabilization: sends a discovery message to the specified neighborhood
        void send_discovery_to( const NodeID& destination, int ttl = 3 );

        void discover_neighbors( const LinkID& lnk );

        void showLinks();

public:
        Chord(BaseOverlay& _baseoverlay, const NodeID& _nodeid,
                        OverlayStructureEvents* _eventsReceiver, const OverlayParameterSet& param);
        virtual ~Chord();

        /// @see OverlayInterface.h
        virtual const LinkID& getNextLinkId( const NodeID& id ) const;
        
    /// @see OverlayInterface.h
    /// NOTE: This implementation excepts num == 2
    virtual std::vector<const LinkID*> getSortedLinkIdsTowardsNode(
        const NodeID& id, int num = 0 ) const;

        /// @see OverlayInterface.h
        virtual const NodeID& getNextNodeId( const NodeID& id ) const;

        /// @see OverlayInterface.h
        virtual void createOverlay();

        /// @see OverlayInterface.h
        virtual void deleteOverlay();

        /// @see OverlayInterface.h
        virtual void joinOverlay(
                const EndpointDescriptor& boot = EndpointDescriptor::UNSPECIFIED()
        );

        /// @see OverlayInterface.h
        virtual void leaveOverlay();

        /// @see OverlayInterface.h
        virtual const EndpointDescriptor& resolveNode( const NodeID& node );

        /// @see OverlayInterface.h
        virtual bool isClosestNodeTo( const NodeID& node );

        /// @see OverlayInterface.h
        virtual NodeList getKnownNodes(bool deep = true) const;

        /// @see CommunicationListener.h or @see OverlayInterface.h
        virtual void onLinkUp(const LinkID& lnk, const NodeID& remote);

        /// @see CommunicationListener.h or @see OverlayInterface.h
        virtual void onLinkDown(const LinkID& lnk, const NodeID& remote);

        /// @see CommunicationListener.h or @see OverlayInterface.h
        virtual void onMessage(OverlayMsg* msg,
                reboost::shared_buffer_t sub_msg,
                const NodeID& remote,
                        const LinkID& lnk = LinkID::UNSPECIFIED);

        /// @see OverlayInterface.h
        virtual std::string debugInformation() const;

        /// @see Timer.h
        virtual void eventFunction();

};

}}

#endif /* CHORD_H_ */