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 = 2 ) :
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 if (find_item(value)!=NULL) return false;
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 ) {
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
00256 if (curr->ref_count==0) continue;
00257
00258
00259 if (best_item==NULL) {
00260 best_item = curr;
00261 continue;
00262 } else {
00263 if (distance(value, curr->id)<distance(value, best_item->id))
00264 best_item = curr;
00265 }
00266 }
00267 return best_item;
00268 }
00269
00270 const nodeid_t* get_successor() {
00271 if (succ.size()==NULL) return NULL;
00272 return &succ.front();
00273 }
00274
00275 const nodeid_t* get_predesessor() {
00276 if (pred.size()==NULL) return NULL;
00277 return &pred.front();
00278 }
00279
00280
00281 bool is_closest_to( const nodeid_t& value ) {
00282 ring_distance distance;
00283 nodeid_t delta = distance(value, id);
00284 if (get_successor() != NULL &&
00285 delta > distance(value, *get_successor() ) ) return false;
00286 if (get_predesessor() != NULL &&
00287 delta > distance(value, *get_predesessor() ) ) return false;
00288 return true;
00289 }
00290
00292 vector<item>& get_table() {
00293 return table;
00294 }
00295
00297 const item* get_removed_item() const {
00298 return item_removed_flag ? &item_removed : NULL;
00299 }
00300
00302 const succ_table& get_succ_table() const {
00303 return succ;
00304 }
00305
00307 const pred_table& get_pred_table() const {
00308 return pred;
00309 }
00310
00312 finger_table& get_finger_table( size_t index ) {
00313 return *finger[index];
00314 }
00315
00317 size_t get_finger_table_size() const {
00318 return max_fingers*2;
00319 }
00320 };
00321
00323 std::ostream& operator<<(std::ostream& s, const chord_routing_table& t) {
00324 s << "[pred=" << t.get_pred_table() << " succ=" << t.get_succ_table()
00325 << "]";
00326 return s;
00327 }
00328
00329 #endif