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 int 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
00187 bool is_insertable( const nodeid_t& value ) {
00188
00189 bool is_insertable_ = false;
00190 is_insertable_ |= succ.insertable(value);
00191 is_insertable_ |= pred.insertable(value);
00192 for (size_t i=0; i<max_fingers*2; i++)
00193 is_insertable_ |= finger[i]->insertable(value);
00194 return is_insertable_;
00195 }
00196
00198 item* get( const nodeid_t& value ) {
00199 return find_item(value);
00200 }
00201
00202 inline item* operator[] ( size_t index ) {
00203 return &table[index];
00204 }
00205
00206 inline size_t size() const {
00207 return table.size();
00208 }
00209
00211 item* insert( const nodeid_t& value ) {
00212 if (value==id) return NULL;
00213 item_added = NULL;
00214 item_removed_flag = false;
00215 succ.insert(value);
00216 pred.insert(value);
00217 for (size_t i=0; i<max_fingers*2; i++) finger[i]->insert(value);
00218 return item_added;
00219 }
00220
00222 item* insert_orphan( const nodeid_t& value ) {
00223 item* it = find_item(value);
00224 if (it!=NULL) return it;
00225 item i;
00226 i.id = id;
00227 i.ref_count = 0;
00228 table.push_back(i);
00229 return &table.back();
00230 }
00231
00233 const item* remove( const nodeid_t& value ) {
00234 item_removed_flag = false;
00235 succ.remove(value);
00236 pred.remove(value);
00237 for (size_t i=0; i<max_fingers*2; i++) finger[i]->remove(value);
00238 if (!item_removed_flag) remove_orphan(value);
00239 return item_removed_flag ? &item_removed : NULL;
00240 }
00241
00243 item* remove_orphan( const nodeid_t& value ) {
00244 item_removed_flag = false;
00245 remove_item(value);
00246 return item_removed_flag ? &item_removed : NULL;
00247 }
00248
00250 const item* get_next_hop( const nodeid_t& value, bool nts = false) {
00251 ring_distance distance;
00252 item* best_item = NULL;
00253 for (size_t i=0; i<table.size(); i++) {
00254 item* curr = &table[i];
00255 if (nts && curr->id == value) continue;
00256
00257
00258 if (curr->ref_count==0) continue;
00259
00260
00261 if (best_item==NULL) {
00262 best_item = curr;
00263 continue;
00264 } else {
00265 if (distance(value, curr->id)<distance(value, best_item->id))
00266 best_item = curr;
00267 }
00268 }
00269 if (best_item != NULL && distance(value, id)<distance(value, best_item->id))
00270 return NULL;
00271 return best_item;
00272 }
00273
00274 const nodeid_t* get_successor() {
00275 if (succ.size()==NULL) return NULL;
00276 return &succ.front();
00277 }
00278
00279 const nodeid_t* get_predesessor() {
00280 if (pred.size()==NULL) return NULL;
00281 return &pred.front();
00282 }
00283
00284 bool is_closest_to( const nodeid_t& value ) {
00285 ring_distance distance;
00286 nodeid_t delta = distance(value, id);
00287 if (get_successor() != NULL &&
00288 delta > distance(value, *get_successor() ) ) return false;
00289 if (get_predesessor() != NULL &&
00290 delta > distance(value, *get_predesessor() ) ) return false;
00291 return true;
00292 }
00293
00295 vector<item>& get_table() {
00296 return table;
00297 }
00298
00300 const item* get_removed_item() const {
00301 return item_removed_flag ? &item_removed : NULL;
00302 }
00303
00305 const succ_table& get_succ_table() const {
00306 return succ;
00307 }
00308
00310 const pred_table& get_pred_table() const {
00311 return pred;
00312 }
00313
00315 finger_table& get_finger_table( size_t index ) {
00316 return *finger[index];
00317 }
00318
00320 size_t get_finger_table_size() const {
00321 return max_fingers*2;
00322 }
00323 };
00324
00326 std::ostream& operator<<(std::ostream& s, const chord_routing_table& t) {
00327 s << "[pred=" << t.get_pred_table() << " succ=" << t.get_succ_table()
00328 << "]";
00329 return s;
00330 }
00331
00332 #endif