An Overlay-based
Virtual Network Substrate
SpoVNet

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

Last change on this file since 10700 was 10572, checked in by Michael Tänzer, 8 years ago

Fix DHT: messages got lost if not communicating over a direct link.

Also:

  • Fix mem leak
  • Code clean up
File size: 4.8 KB
Line 
1// [License]
2// The Ariba-Underlay Copyright
3//
4// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)
5//
6// Institute of Telematics
7// UniversitÀt Karlsruhe (TH)
8// Zirkel 2, 76128 Karlsruhe
9// Germany
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND
22// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ARIBA PROJECT OR
25// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32//
33// The views and conclusions contained in the software and documentation
34// are those of the authors and should not be interpreted as representing
35// official policies, either expressed or implied, of the Institute of
36// Telematics.
37// [License]
38
39#ifndef CHORD_H_
40#define CHORD_H_
41
42#include "ariba/utility/system/Timer.h"
43#include "ariba/utility/logging/Logging.h"
44#include "ariba/communication/EndpointDescriptor.h"
45#include "../OverlayInterface.h"
46#include <vector>
47
48class chord_routing_table;
49
50namespace ariba {
51namespace overlay {
52
53class OverlayMsg;
54
55using ariba::communication::EndpointDescriptor;
56using ariba::utility::Timer;
57
58using namespace std;
59
60/**
61 * This class implements a structured overlay inspired by chord.
62 * It differs to the original form of chord in the following manner:
63 *
64 * (1) The graph is bidirectional
65 * (2) Stabilization is done in a reactive manner
66 *
67 * It therefore can be considered as a kind of Chorded-Kademlia :)
68 *
69 * The resulting overlay graph has a diameter of O(log N).
70 *
71 * @author Sebastian Mies <mies@tm.uka.de>
72 */
73class Chord : public OverlayInterface, protected Timer {
74        use_logging_h( Chord );
75private:
76        chord_routing_table* table;
77        int orphan_removal_counter;
78        int stabilize_counter;
79        int stabilize_finger;
80        vector<LinkID> bootstrapLinks;
81        vector<NodeID> pending;
82        vector<NodeID> discovery;
83        int discovery_count;
84
85        // helper: sets up a link using the "base overlay"
86        LinkID setup( const EndpointDescriptor& endp,
87                const NodeID& node = NodeID::UNSPECIFIED );
88
89        // helper: sends a message using the "base overlay"
90        seqnum_t send( OverlayMsg* msg, const LinkID& link );
91
92        // stabilization: sends a discovery message to the specified neighborhood
93        void send_discovery_to( const NodeID& destination, int ttl = 3 );
94
95        void discover_neighbors( const LinkID& lnk );
96
97        void showLinks();
98
99public:
100        Chord(BaseOverlay& _baseoverlay, const NodeID& _nodeid,
101                        OverlayStructureEvents* _eventsReceiver, const OverlayParameterSet& param);
102        virtual ~Chord();
103
104        /// @see OverlayInterface.h
105        virtual const LinkID& getNextLinkId( const NodeID& id ) const;
106       
107        /// @see OverlayInterface.h
108        virtual const NodeID& getNextNodeId( const NodeID& id ) const;
109
110        /// @see OverlayInterface.h
111        virtual void createOverlay();
112
113        /// @see OverlayInterface.h
114        virtual void deleteOverlay();
115
116        /// @see OverlayInterface.h
117        virtual void joinOverlay(
118                const EndpointDescriptor& boot = EndpointDescriptor::UNSPECIFIED()
119        );
120
121        /// @see OverlayInterface.h
122        virtual void leaveOverlay();
123
124        /// @see OverlayInterface.h
125        virtual const EndpointDescriptor& resolveNode( const NodeID& node );
126
127        /// @see OverlayInterface.h
128        virtual bool isClosestNodeTo( const NodeID& node );
129
130        /// @see OverlayInterface.h
131        virtual NodeList getKnownNodes(bool deep = true) const;
132
133        /// @see CommunicationListener.h or @see OverlayInterface.h
134        virtual void onLinkUp(const LinkID& lnk, const NodeID& remote);
135
136        /// @see CommunicationListener.h or @see OverlayInterface.h
137        virtual void onLinkDown(const LinkID& lnk, const NodeID& remote);
138
139        /// @see CommunicationListener.h or @see OverlayInterface.h
140        virtual void onMessage(const DataMessage& msg, const NodeID& remote,
141                        const LinkID& lnk = LinkID::UNSPECIFIED);
142
143        /// @see OverlayInterface.h
144        virtual std::string debugInformation() const;
145
146        /// @see Timer.h
147        virtual void eventFunction();
148
149};
150
151}}
152
153#endif /* CHORD_H_ */
Note: See TracBrowser for help on using the repository browser.