00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef CHORD_ROUTING_TABLE_HPP_
00039 #define CHORD_ROUTING_TABLE_HPP_
00040
00041 #include <vector>
00042 #include <iostream>
00043
00044 #include <boost/foreach.hpp>
00045
00046 #include "distances.hpp"
00047 #include "comparators.hpp"
00048 #include "minimizer_table.hpp"
00049
00050 #include "ariba/Identifiers.h"
00051
00052 using namespace ariba;
00053
00054 using namespace distances;
00055 using namespace comparators;
00056 using namespace std;
00057
00058
00059 typedef ariba::NodeID nodeid_t;
00060 typedef ariba::LinkID routeinfo_t;
00061
00067 class chord_routing_table {
00068 private:
00069 typedef chord_routing_table self;
00070 typedef distance_compare<nodeid_t&, nodeid_t, ring_succ_distance>
00071 succ_compare_type;
00072 typedef distance_compare<nodeid_t&, nodeid_t, ring_pred_distance>
00073 pred_compare_type;
00074 typedef distance_compare<nodeid_t, nodeid_t, ring_distance>
00075 finger_compare_type;
00076
00077 public:
00078 typedef minimizer_table<nodeid_t, succ_compare_type, self> succ_table;
00079 typedef minimizer_table<nodeid_t, pred_compare_type, self> pred_table;
00080 typedef minimizer_table<nodeid_t, finger_compare_type, self> finger_table;
00081
00082
00083 class item {
00084 public:
00085 uint8_t ref_count;
00086 nodeid_t id;
00087 routeinfo_t info;
00088 };
00089 typedef vector<item> route_table;
00090
00091
00092 private:
00093
00094 static const size_t max_fingers = 32;
00095
00096
00097 nodeid_t id;
00098
00099
00100 succ_table succ;
00101 pred_table pred;
00102 finger_table* finger[max_fingers*2];
00103
00104
00105 route_table table;
00106
00107
00108 item* item_added;
00109 item item_removed;
00110 bool item_removed_flag;
00111 bool simulate;
00112
00113
00114 item* find_item(const nodeid_t& id) {
00115 BOOST_FOREACH( item& i, table )
00116 if ( i.id == id ) return &i;
00117 return NULL;
00118 }
00119
00121 item* add_item( const nodeid_t& id ) {
00122 item i;
00123 i.id = id;
00124 i.ref_count = 1;
00125 table.push_back(i);
00126 item_added = &table.back();
00127 return item_added;
00128 }
00129
00131 bool remove_item( const nodeid_t& id ) {
00132 for (route_table::iterator i = table.begin(); i!=table.end(); i++) {
00133 if ( (*i).id == id ) {
00134 (*i).ref_count--;
00135 if ((*i).ref_count == 0) {
00136 item_removed = *i;
00137 item_removed_flag = true;
00138 return true;
00139 }
00140 break;
00141 }
00142 }
00143 return false;
00144 }
00145
00146 public:
00147
00148
00149 template<class Table>
00150 void on_table( table_listener::type_ type, const Table& tab, typename Table::iterator pos ) {
00151 switch (type) {
00152 case table_listener::insert: {
00153 item* i = find_item( *pos );
00154 if (i == NULL) i = add_item( *pos ); else i->ref_count++;
00155 break;
00156 }
00157 case table_listener::remove: {
00158 remove_item(*pos);
00159 break;
00160 }
00161 case table_listener::update:
00162 break;
00163 }
00164 }
00165
00166
00167 public:
00169 explicit chord_routing_table( const nodeid_t& id, int redundancy = 4 ) :
00170 id(id), succ( redundancy, succ_compare_type(this->id), *this ),
00171 pred( redundancy, pred_compare_type(this->id), *this ) {
00172
00173
00174 nodeid_t nid = Identifier(2);
00175 for (size_t i=0; i<max_fingers; i++) {
00176 finger[i*2+0] =
00177 new finger_table( redundancy,
00178 finger_compare_type(this->id - nid), *this);
00179 finger[i*2+1] =
00180 new finger_table( redundancy,
00181 finger_compare_type(this->id + nid), *this);
00182 nid = nid << 1;
00183 }
00184 }
00185
00186 virtual ~chord_routing_table() {
00187 BOOST_FOREACH( finger_table* f, this->finger){
00188 delete f;
00189 }
00190 }
00191
00193 bool is_insertable( const nodeid_t& value ) {
00194
00195 bool is_insertable_ = false;
00196 is_insertable_ |= succ.insertable(value);
00197 is_insertable_ |= pred.insertable(value);
00198 for (size_t i=0; i<max_fingers*2; i++)
00199 is_insertable_ |= finger[i]->insertable(value);
00200 return is_insertable_;
00201 }
00202
00204 item* get( const nodeid_t& value ) {
00205 return find_item(value);
00206 }
00207
00208 inline item* operator[] ( size_t index ) {
00209 return &table[index];
00210 }
00211
00212 inline size_t size() const {
00213 return table.size();
00214 }
00215
00217 item* insert( const nodeid_t& value ) {
00218 if (value==id) return NULL;
00219 item_added = NULL;
00220 item_removed_flag = false;
00221 succ.insert(value);
00222 pred.insert(value);
00223 for (size_t i=0; i<max_fingers*2; i++) finger[i]->insert(value);
00224 return item_added;
00225 }
00226
00228 item* insert_orphan( const nodeid_t& value ) {
00229 item* it = find_item(value);
00230 if (it!=NULL) return it;
00231 item i;
00232 i.id = id;
00233 i.ref_count = 0;
00234 table.push_back(i);
00235 return &table.back();
00236 }
00237
00239 const item* remove( const nodeid_t& value ) {
00240 item_removed_flag = false;
00241 succ.remove(value);
00242 pred.remove(value);
00243 for (size_t i=0; i<max_fingers*2; i++) finger[i]->remove(value);
00244 if (!item_removed_flag) remove_orphan(value);
00245 return item_removed_flag ? &item_removed : NULL;
00246 }
00247
00249 item* remove_orphan( const nodeid_t& value ) {
00250 item_removed_flag = false;
00251 remove_item(value);
00252 return item_removed_flag ? &item_removed : NULL;
00253 }
00254
00256 const item* get_next_hop( const nodeid_t& value, bool nts = false) {
00257 ring_distance distance;
00258 item* best_item = NULL;
00259 for (size_t i=0; i<table.size(); i++) {
00260 item* curr = &table[i];
00261 if (nts && curr->id == value) continue;
00262
00263
00264 if (curr->ref_count==0) continue;
00265
00266
00267 if (best_item==NULL) {
00268 best_item = curr;
00269 continue;
00270 } else {
00271 if (distance(value, curr->id)<distance(value, best_item->id))
00272 best_item = curr;
00273 }
00274 }
00275 if (best_item != NULL && distance(value, id)<distance(value, best_item->id))
00276 return NULL;
00277 return best_item;
00278 }
00279
00280 const nodeid_t* get_successor() {
00281 if (succ.size()==NULL) return NULL;
00282 return &succ.front();
00283 }
00284
00285 const nodeid_t* get_predesessor() {
00286 if (pred.size()==NULL) return NULL;
00287 return &pred.front();
00288 }
00289
00290 bool is_closest_to( const nodeid_t& value ) {
00291 ring_distance distance;
00292 nodeid_t delta = distance(value, id);
00293 if (get_successor() != NULL &&
00294 delta > distance(value, *get_successor() ) ) return false;
00295 if (get_predesessor() != NULL &&
00296 delta > distance(value, *get_predesessor() ) ) return false;
00297 return true;
00298 }
00299
00301 vector<item>& get_table() {
00302 return table;
00303 }
00304
00306 const item* get_removed_item() const {
00307 return item_removed_flag ? &item_removed : NULL;
00308 }
00309
00311 const succ_table& get_succ_table() const {
00312 return succ;
00313 }
00314
00316 const pred_table& get_pred_table() const {
00317 return pred;
00318 }
00319
00321 finger_table& get_finger_table( size_t index ) {
00322 return *finger[index];
00323 }
00324
00326 size_t get_finger_table_size() const {
00327 return max_fingers*2;
00328 }
00329 };
00330
00332 std::ostream& operator<<(std::ostream& s, const chord_routing_table& t) {
00333 s << "[pred=" << t.get_pred_table() << " succ=" << t.get_succ_table()
00334 << "]";
00335 return s;
00336 }
00337
00338 #endif