source: source/ariba/overlay/modules/chord/detail/chord_routing_table.hpp@ 12438

Last change on this file since 12438 was 12060, checked in by hock@…, 11 years ago

Reintegrate branch: 20130111-hock-message_classes

improvements:

  • new message classes (reboost, zero-copy)
  • "fast path" for direct links (skip overlay layer)
  • link-properties accessible from the application
  • SystemQueue can call boost::bind functions
  • protlib compatibility removed (32bit overhead saved in every message)
  • addressing2
  • AddressDiscovery discoveres only addresses on which we're actually listening
  • ariba serialization usage reduced (sill used in OverlayMsg)
  • Node::connect, easier and cleaner interface to start-up ariba from the application
  • ariba configs via JSON, XML, etc (boost::property_tree)
  • keep-alive overhead greatly reduced
  • (relayed) overlay links can actually be closed now
  • lost messages are detected in most cases
  • notification to the application when link is transformed into direct-link
  • overlay routing: send message to second best hop if it would be dropped otherwise
  • SequenceNumbers (only mechanisms, so for: upward compatibility)
  • various small fixes


regressions:

  • bluetooth is not yet working again
  • bootstrap modules deactivated
  • liblog4xx is not working (use cout-logging)

This patch brings great performance and stability improvements at cost of backward compatibility.
Also bluetooth and the bootstrap modules have not been ported to the new interfaces, yet.

File size: 10.3 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 INSTITUTE OF TELEMATICS 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#ifndef CHORD_ROUTING_TABLE_HPP_
39#define CHORD_ROUTING_TABLE_HPP_
40
41#include <vector>
42#include <iostream>
43
44#include <boost/foreach.hpp>
45
46#include "distances.hpp"
47#include "comparators.hpp"
48#include "minimizer_table.hpp"
49
50#include "ariba/Identifiers.h"
51
52using namespace ariba;
53
54using namespace distances;
55using namespace comparators;
56using namespace std;
57
58// placeholders for route info and nodeid type
59typedef ariba::NodeID nodeid_t;
60typedef ariba::LinkID routeinfo_t;
61
62/**
63 * Implementation of a chord routing table.
64*
65 * @author Sebastian Mies <mies@tm.uka.de>
66 */
67class chord_routing_table {
68private:
69 typedef chord_routing_table self;
70 typedef distance_compare<nodeid_t&, nodeid_t, ring_succ_distance>
71 succ_compare_type;
72 typedef distance_compare<nodeid_t&, nodeid_t, ring_pred_distance>
73 pred_compare_type;
74 typedef distance_compare<nodeid_t, nodeid_t, ring_distance>
75 finger_compare_type;
76
77public:
78 typedef minimizer_table<nodeid_t, succ_compare_type, self> succ_table;
79 typedef minimizer_table<nodeid_t, pred_compare_type, self> pred_table;
80 typedef minimizer_table<nodeid_t, finger_compare_type, self> finger_table;
81
82 // a routing table entry
83 class item {
84 public:
85 uint8_t ref_count;
86 nodeid_t id;
87 routeinfo_t info;
88 };
89 typedef vector<item> route_table;
90
91
92private:
93 // maximum number of fingers
94 static const size_t max_fingers = 32;
95
96 // the own node id
97 nodeid_t id;
98
99 // the own node id as routing item
100 item own_id_item;
101
102 // successor and predecessor tables
103 succ_table succ;
104 pred_table pred;
105 finger_table* finger[max_fingers*2];
106
107 // main routing table
108 route_table table;
109
110 // some internal flags
111 item* item_added;
112 item item_removed;
113 bool item_removed_flag;
114 bool simulate;
115
116 // finds an item inside the routing table
117 item* find_item(const nodeid_t& id) {
118 BOOST_FOREACH( item& i, table )
119 if ( i.id == id ) return &i;
120 return NULL;
121 }
122
123 /// Adds a item to the routing table
124 item* add_item( const nodeid_t& id ) {
125 item i;
126 i.id = id;
127 i.ref_count = 1;
128 table.push_back(i);
129 item_added = &table.back();
130 return item_added;
131 }
132
133 /// Removes an item from the routing table
134 bool remove_item( const nodeid_t& id ) {
135 for (route_table::iterator i = table.begin(); i!=table.end(); i++) {
136 if ( (*i).id == id ) {
137 (*i).ref_count--;
138 if ((*i).ref_count == 0) {
139 item_removed = *i;
140 item_removed_flag = true;
141 return true;
142 }
143 break;
144 }
145 }
146 return false;
147 }
148
149public:
150
151 // handles events from minimizers
152 template<class Table>
153 void on_table( table_listener::type_ type, const Table& tab, typename Table::iterator pos ) {
154 switch (type) {
155 case table_listener::insert: {
156 item* i = find_item( *pos );
157 if (i == NULL) i = add_item( *pos ); else i->ref_count++;
158 break;
159 }
160 case table_listener::remove: {
161 remove_item(*pos);
162 break;
163 }
164 case table_listener::update:
165 break;
166 }
167 }
168
169
170public:
171 /// constructs the reactive chord routing table
172 explicit chord_routing_table( const nodeid_t& id, int redundancy = 4 ) :
173 id(id),
174 succ( redundancy, succ_compare_type(this->id), *this ),
175 pred( redundancy, pred_compare_type(this->id), *this )
176 {
177 // init reflexive item
178 own_id_item.id = id;
179 own_id_item.ref_count = 1;
180
181 // create finger tables
182 nodeid_t nid = Identifier(2);
183 for (size_t i=0; i<max_fingers; i++) {
184 finger[i*2+0] =
185 new finger_table( redundancy,
186 finger_compare_type(this->id - nid), *this);
187 finger[i*2+1] =
188 new finger_table( redundancy,
189 finger_compare_type(this->id + nid), *this);
190 nid = nid << 1;
191 }
192 }
193
194 virtual ~chord_routing_table() {
195 BOOST_FOREACH( finger_table* f, this->finger){
196 delete f;
197 }
198 }
199
200 /// check whether a node could fit the routing table
201 bool is_insertable( const nodeid_t& value ) {
202// if (find_item(value)!=NULL) return false;
203 bool is_insertable_ = false;
204 is_insertable_ |= succ.insertable(value);
205 is_insertable_ |= pred.insertable(value);
206 for (size_t i=0; i<max_fingers*2; i++)
207 is_insertable_ |= finger[i]->insertable(value);
208 return is_insertable_;
209 }
210
211 /// searches an item
212 item* get( const nodeid_t& value ) {
213 return find_item(value);
214 }
215
216 inline item* operator[] ( size_t index ) {
217 return &table[index];
218 }
219
220 inline size_t size() const {
221 return table.size();
222 }
223
224 /// adds a node
225 item* insert( const nodeid_t& value ) {
226 if (value==id) return NULL;
227 item_added = NULL;
228 item_removed_flag = false;
229 succ.insert(value);
230 pred.insert(value);
231 for (size_t i=0; i<max_fingers*2; i++) finger[i]->insert(value);
232 return item_added;
233 }
234
235 /// adds an orphan
236 item* insert_orphan( const nodeid_t& value ) {
237 item* it = find_item(value);
238 if (it!=NULL) return it;
239 item i;
240 i.id = id;
241 i.ref_count = 0;
242 table.push_back(i);
243 return &table.back();
244 }
245
246 /// removes an node
247 const item* remove( const nodeid_t& value ) {
248 item_removed_flag = false;
249 succ.remove(value);
250 pred.remove(value);
251 for (size_t i=0; i<max_fingers*2; i++) finger[i]->remove(value);
252 if (!item_removed_flag) remove_orphan(value);
253 return item_removed_flag ? &item_removed : NULL;
254 }
255
256 /// removes an orphan
257 item* remove_orphan( const nodeid_t& value ) {
258 item_removed_flag = false;
259 remove_item(value);
260 return item_removed_flag ? &item_removed : NULL;
261 }
262
263 /// returns the next hop
264 const item* get_next_hop( const nodeid_t& value, bool nts = false) {
265 ring_distance distance;
266 item* best_item = NULL;
267 for (size_t i=0; i<table.size(); i++) {
268 item* curr = &table[i];
269 if (nts && curr->id == value) continue;
270
271 // not not include orphans into routing!
272 if (curr->ref_count==0) continue;
273
274 // check if we found a better item
275 if (best_item==NULL) {
276 best_item = curr;
277 continue;
278 } else {
279 if (distance(value, curr->id)<distance(value, best_item->id))
280 best_item = curr;
281 }
282 }
283
284 if (best_item != NULL && distance(value, id)<distance(value, best_item->id))
285 return NULL;
286 return best_item;
287 }
288
289 std::vector<const item*> get_next_2_hops( const nodeid_t& value)
290 {
291 ring_distance distance;
292 item* best_item = &own_id_item;
293 item* second_best_item = NULL;
294
295 // find best and second best item
296 for (size_t i=0; i<table.size(); i++)
297 {
298 item* curr = &table[i];
299
300 // not not include orphans into routing!
301 if (curr->ref_count==0) continue;
302
303 // check if we found a better item
304 // is best item
305 if ( distance(value, curr->id) < distance(value, best_item->id) )
306 {
307 second_best_item = best_item;
308 best_item = curr;
309 }
310 // is second best item
311 else
312 {
313 if ( second_best_item == NULL )
314 {
315 second_best_item = curr;
316 continue;
317 }
318
319 if ( distance(value, curr->id) < distance(value, second_best_item->id) )
320 {
321 second_best_item = curr;
322 }
323 }
324 }
325
326 // prepare return vector
327 std::vector<const item*> ret;
328 if ( best_item != NULL )
329 {
330 ret.push_back(best_item);
331 }
332 if ( second_best_item != NULL )
333 {
334 ret.push_back(second_best_item);
335 }
336
337 return ret;
338 }
339
340 const nodeid_t* get_successor() {
341 if (succ.size()==0) return NULL;
342 return &succ.front();
343 }
344
345 const nodeid_t* get_predesessor() {
346 if (pred.size()==0) return NULL;
347 return &pred.front();
348 }
349
350 bool is_closest_to( const nodeid_t& value ) {
351 ring_distance distance;
352 nodeid_t delta = distance(value, id);
353 if (get_successor() != NULL &&
354 delta > distance(value, *get_successor() ) ) return false;
355 if (get_predesessor() != NULL &&
356 delta > distance(value, *get_predesessor() ) ) return false;
357 return true;
358 }
359
360 /// returns the whole routing table
361 vector<item>& get_table() {
362 return table;
363 }
364
365 /// returns the last removed item
366 const item* get_removed_item() const {
367 return item_removed_flag ? &item_removed : NULL;
368 }
369
370 /// return successor table
371 const succ_table& get_succ_table() const {
372 return succ;
373 }
374
375 /// return predecessor table
376 const pred_table& get_pred_table() const {
377 return pred;
378 }
379
380 /// return finger table
381 finger_table& get_finger_table( size_t index ) {
382 return *finger[index];
383 }
384
385 /// return number of finger tables
386 size_t get_finger_table_size() const {
387 return max_fingers*2;
388 }
389};
390
391/// output routing table
392std::ostream& operator<<(std::ostream& s, const chord_routing_table& t) {
393 s << "[pred=" << t.get_pred_table() << " succ=" << t.get_succ_table()
394 << "]";
395 return s;
396}
397
398#endif /* CHORD_ROUTING_TABLE_HPP_ */
Note: See TracBrowser for help on using the repository browser.