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_ */