source: source/ariba/overlay/modules/chord/Chord.cpp@ 5748

Last change on this file since 5748 was 5748, checked in by mies, 15 years ago
File size: 15.2 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#include "ariba/overlay/BaseOverlay.h"
40
41#include "Chord.h"
42#include "messages/ChordMessage.h"
43#include "messages/Discovery.h"
44
45#include "detail/chord_routing_table.hpp"
46
47namespace ariba {
48namespace overlay {
49
50typedef chord_routing_table::item route_item;
51
52use_logging_cpp( Chord );
53
54Chord::Chord(BaseOverlay& _baseoverlay, const NodeID& _nodeid,
55 OverlayStructureEvents* _eventsReceiver, const OverlayParameterSet& param) :
56 OverlayInterface(_baseoverlay, _nodeid, _eventsReceiver, param) {
57
58 // create routing table
59 this->table = new chord_routing_table(_nodeid, 4);
60 orphan_removal_counter = 0;
61 discovery_count = 0;
62 stabilize_counter = 0;
63 stabilize_finger = 0;
64}
65
66Chord::~Chord() {
67
68 // delete routing table
69 delete table;
70}
71
72/// helper: sets up a link using the base overlay
73LinkID Chord::setup(const EndpointDescriptor& endp, const NodeID& node, const NodeID& remoteRelay ) {
74 logging_debug("Request to setup link to " << endp.toString() );
75
76 // check if we already have a connection
77 for (int i=0; i<table->size(); i++)
78 if ((*table)[i]->id == node && !((*table)[i]->info.isUnspecified()))
79 return LinkID::UNSPECIFIED;
80
81 // check if we are already trying to establish a link
82 for (size_t i=0; i<pending.size(); i++)
83 if ( pending[i] == node ) {
84 logging_debug("Already trying to establish a link to node " << node.toString() );
85 return LinkID::UNSPECIFIED;
86 }
87
88 // adding node to list of pending connections
89 pending.push_back( node );
90
91 // establish link via base overlay
92 return baseoverlay.establishLink(endp, node, OverlayInterface::OVERLAY_SERVICE_ID, remoteRelay );
93}
94
95/// helper: sends a message using the "base overlay"
96seqnum_t Chord::send(Message* msg, const LinkID& link) {
97 if (link.isUnspecified()) return 0;
98 return baseoverlay.sendMessage(msg, link);
99}
100
101/// sends a discovery message
102void Chord::send_discovery_to(const NodeID& destination, int ttl) {
103 if ( table->size() == 0 ) return;
104
105 ChordMessage cmsg(ChordMessage::discovery, nodeid, destination);
106 Discovery dmsg;
107 dmsg.setSourceEndpoint(&baseoverlay.getEndpointDescriptor());
108 dmsg.setSourceRelay(baseoverlay.getRelayNode(destination));
109 dmsg.setFollowType(Discovery::normal);
110 dmsg.setTTL((uint8_t) ttl);
111 cmsg.encapsulate(&dmsg);
112
113 // get next hop
114 const route_item* item = table->get_next_hop(destination);
115 if (item!=NULL && !item->info.isUnspecified()) send(&cmsg, item->info);
116}
117
118void Chord::discover_neighbors( const LinkID& lnk ) {
119 {
120 // send successor discovery
121 ChordMessage cmsg(ChordMessage::discovery, nodeid, nodeid);
122 Discovery dmsg;
123 dmsg.setSourceEndpoint(&baseoverlay.getEndpointDescriptor());
124 dmsg.setSourceRelay(baseoverlay.getRelayNode(nodeid));
125 dmsg.setFollowType(Discovery::successor);
126 dmsg.setTTL((uint8_t)3);
127 cmsg.encapsulate(&dmsg);
128 send(&cmsg, lnk);
129 }
130 {
131 // send predecessor discovery
132 ChordMessage cmsg(ChordMessage::discovery, nodeid, nodeid);
133 Discovery dmsg;
134 dmsg.setSourceEndpoint(&baseoverlay.getEndpointDescriptor());
135 dmsg.setSourceRelay(baseoverlay.getRelayNode(nodeid));
136 dmsg.setFollowType(Discovery::predecessor);
137 dmsg.setTTL((uint8_t)3);
138 cmsg.encapsulate(&dmsg);
139 send(&cmsg, lnk);
140 }
141}
142
143
144void Chord::createOverlay() {
145}
146
147void Chord::deleteOverlay() {
148
149}
150
151void Chord::joinOverlay(const EndpointDescriptor& boot) {
152 logging_info( "joining Chord overlay structure through end-point " <<
153 (boot.isUnspecified() ? "local" : boot.toString()) );
154
155 // initiator? no->setup first link
156 if (!boot.isUnspecified())
157 bootstrapLinks.push_back( setup(boot) );
158
159 // timer for stabilization management
160 Timer::setInterval(1000);
161 Timer::start();
162}
163
164void Chord::leaveOverlay() {
165 Timer::stop();
166 for (size_t i = 0; i < table->size(); i++) {
167 route_item* it = (*table)[i];
168 ChordMessage msg(ChordMessage::leave, nodeid, it->id);
169 send(&msg,it->info);
170 }
171}
172
173const EndpointDescriptor& Chord::resolveNode(const NodeID& node) {
174 const route_item* item = table->get(node);
175 if (item == NULL || item->info.isUnspecified()) return EndpointDescriptor::UNSPECIFIED();
176 return baseoverlay.getEndpointDescriptor(item->info);
177}
178
179void Chord::routeMessage(const NodeID& destnode, Message* msg) {
180 // get next hop
181 const route_item* item = table->get_next_hop(destnode);
182
183 // message for this node? yes-> delegate to base overlay
184 if (item->id == nodeid || destnode == nodeid)
185 baseoverlay.incomingRouteMessage( msg, LinkID::UNSPECIFIED, nodeid );
186
187 else { // no-> send to next hop
188 ChordMessage cmsg(ChordMessage::route, nodeid, destnode);
189 cmsg.encapsulate(msg);
190 send(&cmsg, item->info);
191 }
192}
193
194/// @see OverlayInterface.h
195void Chord::routeMessage(const NodeID& node, const LinkID& link, Message* msg) {
196 logging_debug("Redirect over Chord to node id=" << node.toString()
197 << " link id=" << link.toString() );
198 ChordMessage cmsg(ChordMessage::route, nodeid, node);
199 cmsg.encapsulate(msg);
200 send(&cmsg, link);
201}
202
203/// @see OverlayInterface.h
204const LinkID& Chord::getNextLinkId( const NodeID& id ) const {
205 // get next hop
206 const route_item* item = table->get_next_hop(id);
207
208 // returns a unspecified id when this is itself
209 if (item == NULL || item->id == nodeid)
210 return LinkID::UNSPECIFIED;
211
212 /// return routing info
213 return item->info;
214}
215
216OverlayInterface::NodeList Chord::getKnownNodes(bool deep) const {
217 OverlayInterface::NodeList nodelist;
218
219 if( deep ){
220 // all nodes that I know, fingers, succ/pred
221 for (size_t i = 0; i < table->size(); i++){
222 if (/*(*table)[i]->ref_count != 0
223 &&*/ !(*table)[i]->info.isUnspecified())
224 nodelist.push_back((*table)[i]->id);
225 }
226 } else {
227 // only succ and pred
228 if( table->get_predesessor() != NULL ){
229 nodelist.push_back( *(table->get_predesessor()) );
230 }
231 if( table->get_successor() != NULL ){
232 OverlayInterface::NodeList::iterator i =
233 std::find( nodelist.begin(), nodelist.end(), *(table->get_successor()) );
234 if( i == nodelist.end() )
235 nodelist.push_back( *(table->get_successor()) );
236 }
237 }
238
239 return nodelist;
240}
241
242/// @see CommunicationListener.h
243/// @see OverlayInterface.h
244void Chord::onLinkUp(const LinkID& lnk, const NodeID& remote) {
245 logging_debug("link_up: link=" << lnk.toString() << " remote=" <<
246 remote.toString() );
247 for (vector<NodeID>::iterator i=pending.begin(); i!=pending.end(); i++)
248 if (*i == remote) {
249 pending.erase(i);
250 break;
251 }
252 route_item* item = table->insert(remote);
253
254 // item added to routing table?
255 if (item != NULL) { // yes-> add to routing table
256 logging_info("new routing neighbor: " << remote.toString()
257 << " with link " << lnk.toString());
258 // replace with new link
259 if (!item->info.isUnspecified())
260 baseoverlay.dropLink(item->info);
261 item->info = lnk;
262 } else { // no-> add orphan entry to routing table
263 logging_info("new orphan: " << remote.toString()
264 << " with link " << lnk.toString());
265 table->insert_orphan(remote)->info = lnk;
266 }
267
268 discover_neighbors( lnk );
269 send_discovery_to(remote);
270
271 vector<LinkID>::iterator it = std::find(bootstrapLinks.begin(), bootstrapLinks.end(), lnk);
272 if( it != bootstrapLinks.end() ) {
273 discover_neighbors( lnk );
274 bootstrapLinks.erase( it );
275 }
276}
277
278/// @see CommunicationListener.h or @see OverlayInterface.h
279void Chord::onLinkDown(const LinkID& lnk, const NodeID& remote) {
280 logging_debug("link_down: link=" << lnk.toString() << " remote=" <<
281 remote.toString() );
282
283 // remove link from routing table
284 route_item* item = table->get(remote);
285 if (item!=NULL) item->info = LinkID::UNSPECIFIED;
286 table->remove(remote);
287}
288
289/// @see CommunicationListener.h
290/// @see OverlayInterface.h
291void Chord::onMessage(const DataMessage& msg, const NodeID& remote,
292 const LinkID& link) {
293
294 // decode message
295 typedef ChordMessage M;
296 M* m = msg.getMessage()->convert<ChordMessage> ();
297 if (m == NULL) return;
298
299 // handle messages
300 switch (m->getType()) {
301
302 // invalid message
303 case M::invalid:
304 break;
305
306 // route message with payload
307 case M::route: {
308 // find next hop
309 const route_item* item = table->get_next_hop(m->getDestination());
310
311 // next hop == myself?
312 if (m->getDestination() == nodeid) { // yes-> route to base overlay
313 logging_debug("Send message to baseoverlay");
314 baseoverlay.incomingRouteMessage( m, item->info, remote );
315 }
316 // no-> route to next hop
317 else {
318 logging_debug("Route chord message to "
319 << item->id.toString() << " (destination=" << m->getDestination() << ")");
320 send(m, item->info);
321 }
322 break;
323 }
324
325 // discovery request
326 case M::discovery: {
327 // decapsulate message
328 Discovery* dmsg = m->decapsulate<Discovery> ();
329 logging_debug("received discovery message with"
330 << " src=" << m->getSource().toString()
331 << " dst=" << m->getDestination().toString()
332 << " ttl=" << (int)dmsg->getTTL()
333 << " type=" << (int)dmsg->getFollowType()
334 );
335
336 // check if source node can be added to routing table and setup link
337 if (m->getSource() != nodeid && table->is_insertable(m->getSource()))
338 setup(*dmsg->getSourceEndpoint(), m->getSource(), dmsg->getSourceRelay() );
339
340 // delegate discovery message
341 switch (dmsg->getFollowType()) {
342
343 // normal: route discovery message like every other message
344 case Discovery::normal: {
345 // closest node? yes-> split to follow successor and predecessor
346 if (table->is_closest_to(m->getDestination())
347 || (table->get_successor()!=NULL && *table->get_successor() == m->getDestination())
348 || (table->get_predesessor()!=NULL && *table->get_predesessor() == m->getDestination())
349 ) {
350
351 if (table->get_successor() != NULL) {
352 // send successor message
353 ChordMessage cmsg_s(*m);
354 Discovery dmsg_s(*dmsg);
355 dmsg_s.setFollowType(Discovery::successor);
356 cmsg_s.encapsulate(&dmsg_s);
357 route_item* succ_item = table->get(*table->get_successor());
358 logging_debug("Discovery split: routing discovery message to successor "
359 << succ_item->id.toString() );
360 send(&cmsg_s, succ_item->info);
361 }
362
363 // send predecessor message
364 if (table->get_predesessor() != NULL) {
365 ChordMessage cmsg_p(*m);
366 Discovery dmsg_p(*dmsg);
367 dmsg_p.setFollowType(Discovery::predecessor);
368 cmsg_p.encapsulate(&dmsg_p);
369 route_item* pred_item = table->get(
370 *table->get_predesessor());
371 logging_debug("Discovery split: routing discovery message to predecessor "
372 << pred_item->id.toString() );
373 send(&cmsg_p, pred_item->info);
374 }
375 }
376 // no-> route message
377 else {
378 // find next hop
379 const route_item* item = table->get_next_hop(m->getDestination());
380 if (item == NULL || item->id == nodeid) break;
381 logging_debug("routing discovery message to " <<
382 item->id.toString() );
383 send(m, item->info);
384 }
385 break;
386 }
387
388 // successor mode: follow the successor until TTL is zero
389 case Discovery::successor:
390 case Discovery::predecessor: {
391 // time to live ended? yes-> stop routing
392 if (dmsg->getTTL() == 0 || dmsg->getTTL() > 10) break;
393
394 // decrease time-to-live
395 dmsg->setTTL(dmsg->getTTL() - 1);
396
397 const route_item* item = NULL;
398 if (dmsg->getFollowType() == Discovery::successor &&
399 table->get_successor() != NULL) {
400 item = table->get(*table->get_successor());
401 } else {
402 if (table->get_predesessor()!=NULL)
403 item = table->get(*table->get_predesessor());
404 }
405 if (item == NULL) break;
406 logging_debug("routing discovery message to succ/pred "
407 << item->id.toString() );
408 ChordMessage cmsg(*m);
409 Discovery dmsg_p(*dmsg);
410 cmsg.encapsulate(&dmsg_p);
411 send(&cmsg, item->info);
412 break;
413 }}
414 delete dmsg;
415 break;
416 }
417
418 // leave
419 case M::leave: {
420 if (link!=LinkID::UNSPECIFIED) {
421 route_item* item = table->get(remote);
422 if (item!=NULL) item->info = LinkID::UNSPECIFIED;
423 table->remove(remote);
424 baseoverlay.dropLink(link);
425 }
426 break;
427 }
428 }
429 delete m;
430}
431
432void Chord::eventFunction() {
433 stabilize_counter++;
434 if (stabilize_counter < 0 || stabilize_counter == 4) {
435
436 // reset counter
437 stabilize_counter = 0;
438
439 // clear pending connections
440 pending.clear();
441
442 // get number of real neighbors
443 size_t numNeighbors = 0;
444 for (size_t i = 0; i < table->size(); i++) {
445 route_item* it = (*table)[i];
446 if (it->ref_count != 0 && !it->info.isUnspecified()) numNeighbors++;
447 }
448 logging_info("Running stabilization: #links="
449 << table->size() << " #neighbors=" << numNeighbors );
450
451 // sending discovery
452 logging_debug("Sending discovery message to my neighbors and fingers");
453 stabilize_finger = ((stabilize_finger+1) % table->get_finger_table_size() );
454 const NodeID disc1 = nodeid;
455 const NodeID disc2 = table->get_finger_table(stabilize_finger).get_compare().get_center();
456 send_discovery_to(disc1);
457 if (disc1 != disc2)
458 send_discovery_to(disc2);
459
460 for (int i=0; i<table->size(); i++) {
461 LinkID id = (*table)[i]->info;
462 if (!id.isUnspecified()) discover_neighbors(id);
463 }
464
465 // remove orphan links
466 orphan_removal_counter++;
467 if (orphan_removal_counter <0 || orphan_removal_counter >= 4) {
468 logging_info("Running orphan removal");
469 orphan_removal_counter = 0;
470 for (size_t i = 0; i < table->size(); i++) {
471 route_item* it = (*table)[i];
472 if (it->ref_count == 0 && !it->info.isUnspecified()) {
473 logging_info("Dropping orphaned link " << it->info.toString() << " to " << it->id.toString());
474 table->insert(it->id);
475 if (it->ref_count==0) {
476 baseoverlay.dropLink(it->info);
477 it->info = LinkID::UNSPECIFIED;
478 }
479 }
480 }
481 }
482 }
483 logging_info("--- chord routing information ----------------------------------");
484 logging_info("predecessor: " << (table->get_predesessor()==NULL? "<none>" :
485 table->get_predesessor()->toString()) );
486 logging_info("node_id : " << nodeid.toString() );
487 logging_info("successor : " << (table->get_successor()==NULL? "<none>" :
488 table->get_successor()->toString()));
489 logging_info("----------------------------------------------------------------");
490}
491
492}} // namespace ariba, overlay
Note: See TracBrowser for help on using the repository browser.