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

Last change on this file since 3690 was 3690, checked in by mies, 16 years ago

Merged 20090512-mies-connectors changes r3472:r3689 into trunk.

File size: 8.4 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 int max_fingers = 32;
95
96 // the own node id
97 nodeid_t id;
98
99 // successor and predecessor tables
100 succ_table succ;
101 pred_table pred;
102 finger_table* finger[max_fingers*2];
103
104 // main routing table
105 route_table table;
106
107 // some internal flags
108 item* item_added;
109 item item_removed;
110 bool item_removed_flag;
111 bool simulate;
112
113 // finds an item inside the routing table
114 item* find_item(const nodeid_t& id) {
115 BOOST_FOREACH( item& i, table )
116 if ( i.id == id ) return &i;
117 return NULL;
118 }
119
120 /// Adds a item to the routing table
121 item* add_item( const nodeid_t& id ) {
122 item i;
123 i.id = id;
124 i.ref_count = 1;
125 table.push_back(i);
126 item_added = &table.back();
127 return item_added;
128 }
129
130 /// Removes an item from the routing table
131 bool remove_item( const nodeid_t& id ) {
132 for (route_table::iterator i = table.begin(); i!=table.end(); i++) {
133 if ( (*i).id == id ) {
134 (*i).ref_count--;
135 if ((*i).ref_count == 0) {
136 item_removed = *i;
137 item_removed_flag = true;
138 return true;
139 }
140 break;
141 }
142 }
143 return false;
144 }
145
146public:
147
148 // handles events from minimizers
149 template<class Table>
150 void on_table( table_listener::type_ type, const Table& tab, typename Table::iterator pos ) {
151 switch (type) {
152 case table_listener::insert: {
153 item* i = find_item( *pos );
154 if (i == NULL) i = add_item( *pos ); else i->ref_count++;
155 break;
156 }
157 case table_listener::remove: {
158 remove_item(*pos);
159 break;
160 }
161 case table_listener::update:
162 break;
163 }
164 }
165
166
167public:
168 /// constructs the reactive chord routing table
169 explicit chord_routing_table( const nodeid_t& id, int redundancy = 2 ) :
170 id(id), succ( redundancy, succ_compare_type(this->id), *this ),
171 pred( redundancy, pred_compare_type(this->id), *this ) {
172
173 // create finger tables
174 nodeid_t nid = Identifier(2);
175 for (size_t i=0; i<max_fingers; i++) {
176 finger[i*2+0] =
177 new finger_table( redundancy,
178 finger_compare_type(this->id - nid), *this);
179 finger[i*2+1] =
180 new finger_table( redundancy,
181 finger_compare_type(this->id + nid), *this);
182 nid = nid << 1;
183 }
184 }
185
186 /// check whether a node could fit the routing table
187 bool is_insertable( const nodeid_t& value ) {
188 if (find_item(value)!=NULL) return false;
189 bool is_insertable_ = false;
190 is_insertable_ |= succ.insertable(value);
191 is_insertable_ |= pred.insertable(value);
192 for (size_t i=0; i<max_fingers*2; i++)
193 is_insertable_ |= finger[i]->insertable(value);
194 return is_insertable_;
195 }
196
197 /// searches an item
198 item* get( const nodeid_t& value ) {
199 return find_item(value);
200 }
201
202 inline item* operator[] ( size_t index ) {
203 return &table[index];
204 }
205
206 inline size_t size() const {
207 return table.size();
208 }
209
210 /// adds a node
211 item* insert( const nodeid_t& value ) {
212 if (value==id) return NULL;
213 item_added = NULL;
214 item_removed_flag = false;
215 succ.insert(value);
216 pred.insert(value);
217 for (size_t i=0; i<max_fingers*2; i++) finger[i]->insert(value);
218 return item_added;
219 }
220
221 /// adds an orphan
222 item* insert_orphan( const nodeid_t& value ) {
223 item* it = find_item(value);
224 if (it!=NULL) return it;
225 item i;
226 i.id = id;
227 i.ref_count = 0;
228 table.push_back(i);
229 return &table.back();
230 }
231
232 /// removes an node
233 const item* remove( const nodeid_t& value ) {
234 item_removed_flag = false;
235 succ.remove(value);
236 pred.remove(value);
237 for (size_t i=0; i<max_fingers*2; i++) finger[i]->remove(value);
238 if (!item_removed_flag) remove_orphan(value);
239 return item_removed_flag ? &item_removed : NULL;
240 }
241
242 /// removes an orphan
243 item* remove_orphan( const nodeid_t& value ) {
244 item_removed_flag = false;
245 remove_item(value);
246 return item_removed_flag ? &item_removed : NULL;
247 }
248
249 /// returns the next hop
250 const item* get_next_hop( const nodeid_t& value ) {
251 ring_distance distance;
252 item* best_item = NULL;
253 for (size_t i=0; i<table.size(); i++) {
254 item* curr = &table[i];
255 // not not include orphans into routing!
256 if (curr->ref_count==0) continue;
257
258 // check if we found a better item
259 if (best_item==NULL) {
260 best_item = curr;
261 continue;
262 } else {
263 if (distance(value, curr->id)<distance(value, best_item->id))
264 best_item = curr;
265 }
266 }
267 return best_item;
268 }
269
270 const nodeid_t* get_successor() {
271 if (succ.size()==NULL) return NULL;
272 return &succ.front();
273 }
274
275 const nodeid_t* get_predesessor() {
276 if (pred.size()==NULL) return NULL;
277 return &pred.front();
278 }
279
280
281 bool is_closest_to( const nodeid_t& value ) {
282 ring_distance distance;
283 nodeid_t delta = distance(value, id);
284 if (get_successor() != NULL &&
285 delta > distance(value, *get_successor() ) ) return false;
286 if (get_predesessor() != NULL &&
287 delta > distance(value, *get_predesessor() ) ) return false;
288 return true;
289 }
290
291 /// returns the whole routing table
292 vector<item>& get_table() {
293 return table;
294 }
295
296 /// returns the last removed item
297 const item* get_removed_item() const {
298 return item_removed_flag ? &item_removed : NULL;
299 }
300
301 /// return successor table
302 const succ_table& get_succ_table() const {
303 return succ;
304 }
305
306 /// return predecessor table
307 const pred_table& get_pred_table() const {
308 return pred;
309 }
310
311 /// return finger table
312 finger_table& get_finger_table( size_t index ) {
313 return *finger[index];
314 }
315
316 /// return number of finger tables
317 size_t get_finger_table_size() const {
318 return max_fingers*2;
319 }
320};
321
322/// output routing table
323std::ostream& operator<<(std::ostream& s, const chord_routing_table& t) {
324 s << "[pred=" << t.get_pred_table() << " succ=" << t.get_succ_table()
325 << "]";
326 return s;
327}
328
329#endif /* CHORD_ROUTING_TABLE_HPP_ */
Note: See TracBrowser for help on using the repository browser.