close Warning: Can't use blame annotator: 
No changeset 2259 in the repository

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

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