|
Wiselib
|
wiselib.testing/algorithms/routing/olsr/olsr_routing.h
Go to the documentation of this file.
00001 /*************************************************************************** 00002 ** This file is part of the generic algorithm library Wiselib. ** 00003 ** Copyright (C) 2008,2009 by the Wisebed (www.wisebed.eu) project. ** 00004 ** ** 00005 ** The Wiselib is free software: you can redistribute it and/or modify ** 00006 ** it under the terms of the GNU Lesser General Public License as ** 00007 ** published by the Free Software Foundation, either version 3 of the ** 00008 ** License, or (at your option) any later version. ** 00009 ** ** 00010 ** The Wiselib is distributed in the hope that it will be useful, ** 00011 ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** 00012 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** 00013 ** GNU Lesser General Public License for more details. ** 00014 ** ** 00015 ** You should have received a copy of the GNU Lesser General Public ** 00016 ** License along with the Wiselib. ** 00017 ** If not, see <http://www.gnu.org/licenses/>. ** 00018 ***************************************************************************/ 00019 #ifndef __ALGORITHMS_ROUTING_OLSR_ROUTING_H__ 00020 #define __ALGORITHMS_ROUTING_OLSR_ROUTING_H__ 00021 00022 #include "routing_base.h" 00023 #include "olsr_routing_types.h" 00024 #include "olsr_routing_msg.h" 00025 #include "olsr_broadcast_hello_msg.h" 00026 #include "olsr_broadcast_tc_msg.h" 00027 #include <string.h> 00028 #include <time.h> 00029 #include <cstdlib> 00030 #include <math.h> 00031 #include <vector> 00032 #include <map> 00033 #include <set> 00034 #include <iterator> 00035 00036 //#define DEBUG_OLSRROUTING 00037 00038 /**********************************************************************************/ 00039 // Useful Macros / 00040 /**********************************************************************************/ 00041 00042 #ifndef NULL 00043 #define NULL 0 00044 #endif 00045 00046 #ifndef MIN 00047 #define MIN(a, b) (((a) < (b)) ? (a) : (b)) 00048 #endif 00049 00050 #ifndef MAX 00051 #define MAX(a, b) (((a) > (b)) ? (a) : (b)) 00052 #endif 00053 00054 /********** Intervals **********/ 00055 #define OLSR_HELLO_INTERVAL 2 00056 #define OLSR_TC_INTERVAL 5 00057 #define OLSR_REFRESH_INTERVAL 2 00058 #define OLSR_NEIGHB_HOLD_TIME 3*OLSR_REFRESH_INTERVAL 00059 #define OLSR_TOP_HOLD_TIME 3*OLSR_TC_INTERVAL 00060 #define OLSR_DUP_HOLD_TIME 30 00061 00062 #define OLSR_UNSPEC_LINK 0 00063 #define OLSR_ASYM_LINK 1 00064 #define OLSR_SYM_LINK 2 00065 #define OLSR_LOST_LINK 3 00066 00067 #define OLSR_NOT_NEIGH 0 00068 #define OLSR_SYM_NEIGH 1 00069 #define OLSR_MPR_NEIGH 2 00070 00071 #define OLSR_WILL_NEVER 0 00072 #define OLSR_WILL_LOW 1 00073 #define OLSR_WILL_DEFAULT 3 00074 #define OLSR_WILL_HIGH 6 00075 #define OLSR_WILL_ALWAYS 7 00076 00077 #define OLSR_MAX_HELLOS 12 // Maximum number of hello_msg per Hello message (4 link types * 3 neighbor types) 00078 #define OLSR_MAX_ADDRS 64 // Maximum number of Neighbor_Addr per hello_msg 00079 00080 #define OLSR_MSG_HDR_SIZE 12 // Size (in bytes) of message header 00081 #define OLSR_HELLO_HDR_SIZE 1 // Size (in bytes) of hello header 00082 #define OLSR_HELLO_MSG_HDR_SIZE 3 // Size (in bytes) of hello_msg header 00083 #define OLSR_TC_HDR_SIZE 2 // Size (in bytes) of tc header 00084 00085 #define OLSR_MAX_SEQ_NUM 65535 00086 #define OLSR_STATUS_NOT_SYM 0 // Used to set status of an OLSR_nb_tuple as "not symmetric". 00087 #define OLSR_STATUS_SYM 1 // Used to set status of an OLSR_nb_tuple as "symmetric". 00088 00089 #define OLSR_C 0.0625 // Scaling factor used in RFC 3626. 00090 00091 /****************************************************************************************/ 00092 /****************************************************************************************/ 00093 00094 namespace wiselib 00095 { 00096 00105 template<typename OsModel_P, 00106 typename RoutingTable_P, 00107 typename Clock_P, 00108 typename Radio_P = typename OsModel_P::Radio, 00109 typename Debug_P = typename OsModel_P::Debug> 00110 class OlsrRouting 00111 : public RoutingBase<OsModel_P, Radio_P> 00112 { 00113 public: 00114 typedef OsModel_P OsModel; 00115 typedef RoutingTable_P RoutingTable; 00116 typedef Radio_P Radio; 00117 typedef Debug_P Debug; 00118 typedef Clock_P Clock; 00119 00120 typedef typename OsModel_P::Timer Timer; 00121 00122 typedef typename RoutingTable::iterator RoutingTableIterator; 00123 typedef typename RoutingTable::value_type RoutingTableValue; 00124 typedef typename RoutingTable::mapped_type RoutingTableEntry; 00125 00126 typedef OlsrRouting<OsModel, RoutingTable, Clock, Radio, Debug> self_type; 00127 00128 typedef typename OsModel::Os Os; 00129 00130 typedef typename Radio::node_id_t node_id_t; 00131 typedef typename Radio::size_t size_t; 00132 typedef typename Radio::block_data_t block_data_t; 00133 typedef typename Clock::time_t time_t; 00134 00135 typedef typename Timer::millis_t millis_t; 00136 00137 typedef OlsrRoutingMessage<OsModel, Radio> RoutingMessage; 00138 typedef OlsrBroadcastHelloMessage<OsModel, Radio, RoutingTableValue> BroadcastHelloMessage; 00139 typedef OlsrBroadcastTcMessage<OsModel, Radio, RoutingTableValue> BroadcastTcMessage; 00140 00141 OlsrRouting(); 00142 ~OlsrRouting(); 00143 00144 //@name Routing Control 00145 void enable( void ); 00146 void disable( void ); 00147 00148 //@name Routing Functionality 00149 void send( node_id_t receiver, size_t len, block_data_t *data ); 00150 00151 inline void set_os( Os* os ) 00152 { os_ = os; }; 00153 00154 inline Os* os() 00155 { return os_; }; 00156 00157 /****************************************************************************************/ 00158 // Data Structure in OLSR / 00159 /****************************************************************************************/ 00160 00161 typedef struct OLSR_rt_entry { // A Routing table entry 00162 00163 node_id_t dest_addr_; // Address of the destination node. 00164 node_id_t next_addr_; // Address of the next hop. 00165 uint32_t dist_; // Distance in hops to the destination. 00166 00167 inline node_id_t& dest_addr() { return dest_addr_; } 00168 inline node_id_t& next_addr() { return next_addr_; } 00169 inline uint32_t& dist() { return dist_; } 00170 00171 } OLSR_rt_entry; 00172 00173 00174 typedef struct OLSR_link_tuple { // A Link Tuple. 00175 00176 node_id_t local_node_addr_; // Address of the local node. 00177 node_id_t nb_node_addr_; // Address of the neighbor node. 00178 double sym_time_; // The link is considered bidirectional until this time. 00179 double asym_time_; // The link is considered unidirectional until this time. 00180 double lost_time_; // The link is considered lost until this time (used for link layer notification). 00181 double time_; // Time at which this tuple expires and must be removed. 00182 00183 inline node_id_t& local_node_addr() { return local_node_addr_; } 00184 inline node_id_t& nb_node_addr() { return nb_node_addr_; } 00185 inline double& sym_time() { return sym_time_; } 00186 inline double& asym_time() { return asym_time_; } 00187 inline double& lost_time() { return lost_time_; } 00188 inline double& time() { return time_; } 00189 00190 } OLSR_link_tuple; 00191 00192 00193 typedef struct OLSR_nb_tuple { // A Neighbor Tuple. 00194 00195 node_id_t nb_node_addr_; // Address of the neighbor node. 00196 uint8_t status_; // Neighbor Type and Link Type at the four less significant digits. 00197 uint8_t willingness_; // A value between 0 and 7 specifying the node's willingness to carry traffic on behalf of other nodes. 00198 00199 inline node_id_t& nb_node_addr() { return nb_node_addr_; } 00200 inline uint8_t& status() { return status_; } 00201 inline uint8_t& willingness() { return willingness_; } 00202 00203 } OLSR_nb_tuple; 00204 00205 00206 typedef struct OLSR_nb2hop_tuple { // A 2-hop Tuple. 00207 00208 node_id_t nb_node_addr_; // Address of the neighbor node. 00209 node_id_t nb2hop_addr_; // Address of a 2-hop neighbor with a symmetric link to nb_node_addr. 00210 double time_; // Time at which this tuple expires and must be removed. 00211 00212 inline node_id_t& nb_node_addr() { return nb_node_addr_; } 00213 inline node_id_t& nb2hop_addr() { return nb2hop_addr_; } 00214 inline double& time() { return time_; } 00215 00216 } OLSR_nb2hop_tuple; 00217 00218 00219 typedef struct OLSR_mprsel_tuple { // An MPR-Selector Tuple. 00220 00221 node_id_t node_addr_; // Address of a node which have selected this node as a MPR. 00222 double time_; // Time at which this tuple expires and must be removed. 00223 00224 inline node_id_t& node_addr() { return node_addr_; } 00225 inline double& time() { return time_; } 00226 00227 } OLSR_mprsel_tuple; 00228 00229 00230 typedef struct OLSR_dup_tuple { // A Duplicate Tuple. 00231 00232 node_id_t addr_; // Originator address of the message. 00233 uint16_t seq_num_; // Message sequence number. 00234 bool retransmitted_; // Indicates whether the message has been retransmitted or not. 00235 double time_; // Time at which this tuple expires and must be removed. 00236 00237 inline node_id_t& addr() { return addr_; } 00238 inline uint16_t& seq_num() { return seq_num_; } 00239 inline bool& retransmitted() { return retransmitted_; } 00240 inline double& time() { return time_; } 00241 00242 } OLSR_dup_tuple; 00243 00244 00245 typedef struct OLSR_topology_tuple { // A Topology Tuple. 00246 00247 node_id_t dest_addr_; // Address of the destination. 00248 node_id_t last_addr_; // Address of a node which is a neighbor of the destination. 00249 uint16_t seq_; // Sequence number. 00250 double time_; // Time at which this tuple expires and must be removed. 00251 00252 inline node_id_t& dest_addr() { return dest_addr_; } 00253 inline node_id_t& last_addr() { return last_addr_; } 00254 inline uint16_t& seq() { return seq_; } 00255 inline double& time() { return time_; } 00256 00257 } OLSR_topology_tuple; 00258 00259 typedef std::vector<OLSR_link_tuple*> linkset_t; 00260 typedef std::vector<OLSR_nb_tuple*> nbset_t; 00261 typedef std::vector<OLSR_nb2hop_tuple*> nb2hopset_t; 00262 typedef std::set<node_id_t> mprset_t; 00263 typedef std::vector<OLSR_mprsel_tuple*> mprselset_t; 00264 typedef std::vector<OLSR_topology_tuple*> topologyset_t; 00265 typedef std::vector<OLSR_dup_tuple*> dupset_t; 00266 00267 linkset_t linkset_; 00268 nbset_t nbset_; 00269 nb2hopset_t nb2hopset_; 00270 mprset_t mprset_; 00271 mprselset_t mprselset_; 00272 topologyset_t topologyset_; 00273 dupset_t dupset_; 00274 00275 00276 /**********************************************************************/ 00277 // Messages in OLSR / 00278 /**********************************************************************/ 00279 typedef struct OLSR_hello_msg { // OLSR_hello_msg (inside OLSR_hello). 00280 00281 uint8_t link_code_; 00282 uint16_t link_msg_size_; 00283 node_id_t nb_addrs_[OLSR_MAX_ADDRS]; 00284 int nb_addrs_count_; 00285 00286 inline uint8_t& link_code() { return link_code_; } 00287 inline uint16_t& link_msg_size() { return link_msg_size_; } 00288 inline node_id_t& neighbor_addr_list(int i) { return nb_addrs_[i]; } 00289 inline int neighbor_addr_count() { return nb_addrs_count_;} 00290 00291 inline uint32_t size() // size of each OLSR_hello_msg 00292 { 00293 return OLSR_HELLO_MSG_HDR_SIZE + nb_addrs_count_ * 4; 00294 } 00295 00296 inline uint32_t size_pnt() 00297 { 00298 uint32_t a = OLSR_HELLO_MSG_HDR_SIZE+nb_addrs_count_*4; 00299 00300 return a; 00301 } 00302 00303 } OLSR_hello_msg; 00304 00305 00306 typedef struct OLSR_hello { // OLSR_hello 00307 uint8_t htime_; 00308 uint8_t willingness_; 00309 OLSR_hello_msg hello_body_[OLSR_MAX_HELLOS]; 00310 int hello_msg_count_; 00311 00312 inline uint8_t& htime() { return htime_; } 00313 inline uint8_t& willingness() { return willingness_; } 00314 inline OLSR_hello_msg& hello_msg(int i) { return hello_body_[i]; } 00315 inline int hello_msg_count() { return hello_msg_count_;} 00316 00317 inline uint32_t size() // size of OLSR_hello ( including all OLSR_hello_msg ) 00318 { 00319 uint32_t sz = OLSR_HELLO_HDR_SIZE; 00320 00321 for (int i = 0; i < hello_msg_count_; i++) 00322 sz += hello_msg(i).size(); 00323 00324 return sz; 00325 } 00326 00327 } OLSR_hello; 00328 00329 00330 00331 typedef struct OLSR_tc { // OLSR_tc 00332 00333 uint16_t ansn_; 00334 node_id_t adv_nb_addrs_[OLSR_MAX_ADDRS]; 00335 int adv_nb_addrs_count_; 00336 00337 inline uint16_t& ansn() { return ansn_; } 00338 inline node_id_t& adv_neighbor_addr_list(int i) { return adv_nb_addrs_[i]; } 00339 inline int adv_neighbor_addrs_count() { return adv_nb_addrs_count_;} 00340 00341 inline uint32_t size() // size of OLSR_tc 00342 { 00343 return OLSR_TC_HDR_SIZE + adv_nb_addrs_count_*4; 00344 } 00345 00346 } OLSR_tc; 00347 00348 00349 typedef struct OLSR_msg { // OLSR_msg 00350 00351 uint8_t msg_id_; // Message type. 00352 uint8_t vtime_; // Validity time. 00353 uint16_t msg_size_; // Message size (in bytes). 00354 node_id_t orig_addr_; // Address of the node which generated this message. 00355 uint8_t ttl_; // Time to live (in hops). 00356 uint8_t hop_count_; // Number of hops which the message has taken. 00357 uint16_t msg_seq_num_; // Message sequence number. 00358 00359 union { OLSR_hello hello_; 00360 OLSR_tc tc_; 00361 } msg_body_; // Message body. 00362 00363 inline uint8_t& msg_id() { return msg_id_; } 00364 inline uint8_t& vtime() { return vtime_; } 00365 inline uint16_t& msg_size() { return msg_size_; } 00366 inline node_id_t& originator_addr() { return orig_addr_; } 00367 inline uint8_t& ttl() { return ttl_; } 00368 inline uint8_t& hop_count() { return hop_count_; } 00369 inline uint16_t& msg_seq_num() { return msg_seq_num_; } 00370 00371 inline OLSR_hello& hello() { return msg_body_.hello_; } 00372 inline OLSR_tc& tc() { return msg_body_.tc_; } 00373 00374 inline uint32_t size() // size of OLSR_msg 00375 { 00376 uint32_t sz = OLSR_MSG_HDR_SIZE; 00377 if (msg_id() == HELLO) 00378 sz += hello().size(); 00379 else if (msg_id() == TC) 00380 sz += tc().size(); 00381 return sz; 00382 } 00383 00384 } OLSR_msg; 00385 00386 00387 /**********************************************************************/ 00388 // OLSR function & Node states' manipulation / 00389 /**********************************************************************/ 00390 inline linkset_t& linkset() { return linkset_; } 00391 inline nbset_t& nbset() { return nbset_; } 00392 inline nb2hopset_t& nb2hopset() { return nb2hopset_; } 00393 inline mprset_t& mprset() { return mprset_; } 00394 inline mprselset_t& mprselset() { return mprselset_; } 00395 inline topologyset_t& topologyset() { return topologyset_; } 00396 inline dupset_t& dupset() { return dupset_; } 00397 00398 void nb_loss(OLSR_link_tuple* tuple); // Case of Neighbor loss 00399 00400 void routing_table_computation(); // Compute the Routing Table 00401 int degree(OLSR_nb_tuple*); // This function is used for calculating the MPR Set 00402 bool route_exists(node_id_t destination); // Check whether there is an entry in the local routing table for the destination in the received message 00403 00404 void mpr_computation(); // Neighbor Detection & Calculation of the MPR nodes 00405 bool find_mpr_addr(node_id_t); // based on the 1-hop & 2-hop neighbor information 00406 void insert_mpr_addr(node_id_t); 00407 void clear_mprset(); 00408 00409 void process_hello(BroadcastHelloMessage&, node_id_t); // HELLO processing 00410 void process_tc(BroadcastTcMessage&, node_id_t); // TC processing 00411 void process_data(RoutingMessage&, node_id_t); // DATA processing 00412 void forward_hello(node_id_t, BroadcastHelloMessage&, OLSR_dup_tuple*); // HELLO forwarding 00413 void forward_tc(node_id_t, BroadcastTcMessage&, OLSR_dup_tuple*); // TC forwarding 00414 00415 void broadcast_hello(); // Hello generation & broadcast 00416 void broadcast_tc(); // TC generation & broadcast 00417 00418 void link_sensing(BroadcastHelloMessage&, node_id_t); 00419 void populate_nbset(BroadcastHelloMessage&); // Updates the Neighbor Set according to the information contained in a new received HELLO message 00420 void populate_nb2hopset(BroadcastHelloMessage&); // Neighbor Detection & Updating of the 2-hop_Neighbor_Tuple based on the update of the Link_Tuple 00421 void populate_mprselset(BroadcastHelloMessage&); // Neighbor Detection & Calculation of the MPR Selector set for the MPR nodes based on the 1-hop & 2-hop neighbor information 00422 00423 void add_dup_tuple(OLSR_dup_tuple*); 00424 void rm_dup_tuple(OLSR_dup_tuple*); 00425 OLSR_dup_tuple* find_dup_tuple(node_id_t, uint16_t); 00426 void erase_dup_tuple(OLSR_dup_tuple*); 00427 void insert_dup_tuple(OLSR_dup_tuple*); 00428 00429 void add_link_tuple(OLSR_link_tuple*, uint8_t); // Link Set manipulation 00430 void rm_link_tuple(OLSR_link_tuple*); 00431 void updated_link_tuple(OLSR_link_tuple*); // Update a Link_Tuple, also update the corresponding neighbor tuple if it is needed 00432 OLSR_link_tuple* find_link_tuple(node_id_t); 00433 OLSR_link_tuple* find_sym_link_tuple(node_id_t, double); 00434 void erase_link_tuple(OLSR_link_tuple*); 00435 void insert_link_tuple(OLSR_link_tuple*); 00436 00437 void add_nb_tuple(OLSR_nb_tuple*); 00438 void rm_nb_tuple(OLSR_nb_tuple*); 00439 OLSR_nb_tuple* find_nb_tuple(node_id_t); 00440 OLSR_nb_tuple* find_nb_tuple(node_id_t, uint8_t); 00441 OLSR_nb_tuple* find_sym_nb_tuple(node_id_t); 00442 void erase_nb_tuple(OLSR_nb_tuple*); 00443 void insert_nb_tuple(OLSR_nb_tuple*); 00444 00445 void add_nb2hop_tuple(OLSR_nb2hop_tuple*); 00446 void rm_nb2hop_tuple(OLSR_nb2hop_tuple*); 00447 OLSR_nb2hop_tuple* find_nb2hop_tuple(node_id_t, node_id_t); 00448 void erase_nb2hop_tuple(OLSR_nb2hop_tuple*); 00449 void erase_nb2hop_tuples(node_id_t); 00450 void erase_nb2hop_tuples(node_id_t, node_id_t); 00451 void insert_nb2hop_tuple(OLSR_nb2hop_tuple*); 00452 00453 void add_mprsel_tuple(OLSR_mprsel_tuple*); 00454 void rm_mprsel_tuple(OLSR_mprsel_tuple*); 00455 OLSR_mprsel_tuple* find_mprsel_tuple(node_id_t); 00456 void erase_mprsel_tuple(OLSR_mprsel_tuple*); // Called by rm_mprsel_tuple() 00457 void erase_mprsel_tuples(node_id_t); 00458 void insert_mprsel_tuple(OLSR_mprsel_tuple*); // Called by add_mprsel_tuple() 00459 00460 void add_topology_tuple(OLSR_topology_tuple*); 00461 void rm_topology_tuple(OLSR_topology_tuple*); 00462 OLSR_topology_tuple* find_topology_tuple(node_id_t, node_id_t); 00463 OLSR_topology_tuple* find_newer_topology_tuple(node_id_t, uint16_t); 00464 void erase_topology_tuple(OLSR_topology_tuple*); // Called by rm_topology_tuple() 00465 void erase_older_topology_tuples(node_id_t, uint16_t); 00466 void insert_topology_tuple(OLSR_topology_tuple*); // Called by add_topology_tuple() 00467 00468 static double emf_to_seconds(uint8_t); 00469 static uint8_t seconds_to_emf(double); 00470 00471 inline uint16_t msg_seq() // Increments message sequence number and returns the new value. 00472 { 00473 msg_seq_ = (msg_seq_ + 1)%(OLSR_MAX_SEQ_NUM + 1); 00474 return msg_seq_; 00475 } 00476 00477 inline int willingness() 00478 { 00479 return OLSR_WILL_DEFAULT; 00480 } 00481 00482 00483 private: 00484 //int random_limit=1; 00485 //double random(random_limit); 00486 void timer_elapsed( void *userdata ); // Methods called by Timer 00487 00488 void timer_expire_link_tuple( OLSR_link_tuple* ); // Link_tuple expiration 00489 void timer_expire_nb2hop_tuple( OLSR_nb2hop_tuple* ); // Nb2hop_tuple expiration 00490 void timer_expire_topology_tuple( OLSR_topology_tuple* ); // Topology_tuple expiration 00491 void timer_expire_mprsel_tuple( OLSR_mprsel_tuple* ); // Mprsel_tuple expiration 00492 void timer_expire_dup_tuple( OLSR_dup_tuple* ); // Dup_tuple expiration 00493 00494 void receive( node_id_t from, size_t len, block_data_t *data ); //@name Methods called by RadioModel 00495 void print_routing_table( RoutingTable rt ); 00496 00497 millis_t startup_time_; 00498 millis_t work_period_; 00499 millis_t delay_; // delay for the retransmission of a message 00500 00501 //millis_t link_tuple_expire_; // expiration of link_tuple 00502 //millis_t nb_tuple_expire_; // expiration of nb_tuple 00503 //millis_t nb2hop_tuple_expire_; // expiration of nb2hop_tuple 00504 //millis_t topology_tuple_expire_; // expiration of link_tuple 00505 //millis_t mprsel_tuple_expire_; // expiration of mprsel_tuple 00506 //millis_t dup_tuple_expire_; // expiration of dup_tuple 00507 00508 int nb_addrs_count_before[OLSR_MAX_HELLOS]; 00509 00510 short seconds_hello; 00511 short seconds_tc; 00512 00513 Os *os_; 00514 00515 RoutingTable routing_table_; // Routing table 00516 00517 00518 uint16_t msg_seq_; 00519 uint16_t ansn_; 00520 }; 00521 00522 // ----------------------------------------------------------------------- 00523 // ----------------------------------------------------------------------- 00524 // ----------------------------------------------------------------------- 00525 template<typename OsModel_P, 00526 typename RoutingTable_P, 00527 typename Clock_P, 00528 typename Radio_P, 00529 typename Debug_P> 00530 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00531 OlsrRouting() 00532 : startup_time_ ( 2000 ), 00533 work_period_ ( 5000 ), 00534 delay_ ( rand()%50 ), 00535 os_( 0 ) 00536 { 00537 00538 00539 00540 msg_seq_ = OLSR_MAX_SEQ_NUM; // Message sequence number counter 00541 ansn_ = OLSR_MAX_SEQ_NUM; // Advertised Neighbor Set sequence number. 00542 }; 00543 // ----------------------------------------------------------------------- 00544 template<typename OsModel_P, 00545 typename RoutingTable_P, 00546 typename Clock_P, 00547 typename Radio_P, 00548 typename Debug_P> 00549 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00550 ~OlsrRouting() 00551 { 00552 #ifdef DEBUG_OLSRROUTING 00553 Debug::debug( os(), "OlsrRouting: Destroyed\n" ); 00554 #endif 00555 }; 00556 // ----------------------------------------------------------------------- 00557 template<typename OsModel_P, 00558 typename RoutingTable_P, 00559 typename Clock_P, 00560 typename Radio_P, 00561 typename Debug_P> 00562 void 00563 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00564 enable( void ) 00565 { 00566 #ifdef DEBUG_OLSRROUTING 00567 Debug::debug( os(), "OlsrRouting: Boot for %i\n", Radio::id( os() ) ); 00568 #endif 00569 00570 seconds_tc = 0; 00571 seconds_hello = 0; 00572 00573 Radio::enable( os() ); 00574 Radio::template reg_recv_callback<self_type, &self_type::receive>( os(), this ); 00575 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), startup_time_, this, 0 ); 00576 } 00577 // ----------------------------------------------------------------------- 00578 template<typename OsModel_P, 00579 typename RoutingTable_P, 00580 typename Clock_P, 00581 typename Radio_P, 00582 typename Debug_P> 00583 void 00584 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00585 disable( void ) 00586 { 00587 #ifdef DEBUG_OLSRROUTING 00588 Debug::debug( os(), "OlsrRouting: Disable\n" ); 00589 #endif 00590 } 00591 // ----------------------------------------------------------------------- 00592 template<typename OsModel_P, 00593 typename RoutingTable_P, 00594 typename Clock_P, 00595 typename Radio_P, 00596 typename Debug_P> 00597 void 00598 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P,Radio_P, Debug_P>:: 00599 send( node_id_t destination, size_t len, block_data_t *data ) // Send the DATA message according to the routing table entry 00600 { 00601 Debug::debug( os(), "OlsrRouting: START TO SEND DATA.\n" ); 00602 RoutingTableIterator it = routing_table_.find( destination ); 00603 if ( it != routing_table_.end() && it->second.next_addr != Radio::NULL_NODE_ID ) 00604 { 00605 RoutingMessage message; 00606 message.set_msg_id( DATA ); 00607 message.set_source( Radio::id(os()) ); 00608 message.set_destination( destination ); 00609 message.set_payload( len, data ); 00610 Radio::send( os(), it->second.next_addr, message.buffer_size(), (uint8_t*)&message ); 00611 00612 #ifdef DEBUG_OLSRROUTING 00613 Debug::debug( os(), "OlsrRouting: Send DATA to %i over %i.\n", message.destination(), it->second.next_addr ); 00614 #endif 00615 } 00616 #ifdef DEBUG_OLSRROUTING 00617 else 00618 Debug::debug( os(), "OlsrRouting: Send failed. Route to Destination not known.\n" ); 00619 #endif 00620 } 00621 00622 // ---------------------------------------------------------------------- 00623 template<typename OsModel_P, 00624 typename RoutingTable_P, 00625 typename Clock_P, 00626 typename Radio_P, 00627 typename Debug_P> 00628 void 00629 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00630 broadcast_hello() 00631 { 00632 OLSR_msg msg; 00633 BroadcastHelloMessage hellomessage; 00634 00635 time_t now = Clock::time( os() ); 00636 00637 hellomessage.set_msg_id( HELLO ); 00638 hellomessage.set_vtime( seconds_to_emf(OLSR_NEIGHB_HOLD_TIME) ); 00639 hellomessage.set_originator_addr( Radio::id(os()) ); 00640 hellomessage.set_ttl(1); 00641 hellomessage.set_hop_count(0); 00642 hellomessage.set_msg_seq_num( msg_seq() ); 00643 hellomessage.set_htime( seconds_to_emf(OLSR_HELLO_INTERVAL) ); 00644 hellomessage.set_willingness( willingness() ); 00645 00646 msg.hello().hello_msg_count_ = 0; 00647 msg.msg_id() = HELLO; 00648 00649 std::map< uint8_t, int> linkcodes_count; // <link_code, link_code_cnt> 00650 00651 if (!linkset().size()) 00652 { 00653 Debug::debug( os(), "Empty HELLO!!!!!! \n"); 00654 } 00655 00656 for (typename linkset_t::iterator it = linkset().begin(); it != linkset().end(); it++) 00657 { 00658 OLSR_link_tuple* link_tuple = *it; 00659 00660 if (link_tuple->local_node_addr() == Radio::id(os()) && link_tuple->time() >= now )// for each tuple in the LINK_SET, produce a LINK_CODE and 00661 // generate a hello_msg corresponding to this LINK_CODE 00662 { 00663 uint8_t link_type, nb_type, link_code; 00664 00665 // Establishes LINK_TYPE for this entry 00666 if (link_tuple->lost_time() >= now) 00667 link_type = OLSR_LOST_LINK; // LINK_TYPE = LOST_LINK 00668 else if (link_tuple->sym_time() >= now) 00669 link_type = OLSR_SYM_LINK; // LINK_TYPE = SYM_LINK 00670 else if (link_tuple->asym_time() >= now) 00671 link_type = OLSR_ASYM_LINK; // LINK_TYPE = ASYM_LINK 00672 else 00673 link_type = OLSR_LOST_LINK; // LINK_TYPE = LOST_LINK 00674 00675 // Establishes NEIGHBOR_TYPE for this entry 00676 if (find_mpr_addr(link_tuple->nb_node_addr())) 00677 nb_type = OLSR_MPR_NEIGH; // NB_TYPE = MPR_NEIGH 00678 else { 00679 bool ok = false; 00680 for (typename nbset_t::iterator nb_it = nbset().begin(); nb_it != nbset().end(); nb_it++) 00681 { 00682 OLSR_nb_tuple* nb_tuple = *nb_it; 00683 if (nb_tuple->nb_node_addr() == link_tuple->nb_node_addr()) 00684 { 00685 if (nb_tuple->status() == OLSR_STATUS_SYM) 00686 nb_type = OLSR_SYM_NEIGH; // NB_TYPE = SYM_NEIGH 00687 else if (nb_tuple->status() == OLSR_STATUS_NOT_SYM) 00688 nb_type = OLSR_NOT_NEIGH; // NB_TYPE = NOT_NEIGH 00689 else 00690 { 00691 fprintf(stderr, "There is a neighbor tuple with an unknown status!\n"); 00692 exit(1); 00693 } 00694 ok = true; 00695 break; 00696 } 00697 } 00698 00699 if (!ok) 00700 { 00701 fprintf(stderr, "Link tuple has no corresponding Neighbor tuple\n"); 00702 exit(1); 00703 } 00704 } 00705 00706 link_code = (link_type & 0x03) | ((nb_type << 2) & 0x0f); // LINK_CODE = LINK_TYPE + NB_TYPE, for this link_tuple entry 00707 00708 00709 // For each LINK_CODE, generate a hello_msg 00710 int count = msg.hello().hello_msg_count_; // count = #_hello_msg in OLSR_hello = hello_msg_count_, initially 0 00711 for ( int p = 0; p < count; p++ ) 00712 { 00713 nb_addrs_count_before[count] += msg.hello().hello_msg(p).neighbor_addr_count(); 00714 } 00715 00716 typename std::map<uint8_t, int>::iterator pos = linkcodes_count.find(link_code); 00717 00718 if (pos == linkcodes_count.end()) // No such LINK_CODE 00719 { 00720 linkcodes_count[link_code] = count; // linkcodes_count[link_code, link_code_cnt] 00721 assert(count >= 0 && count < OLSR_MAX_HELLOS); 00722 00723 msg.hello().hello_msg(count).nb_addrs_count_ = 0; 00724 hellomessage.set_link_code(count, nb_addrs_count_before[count], link_code); // Set the link_code of hello_msg[count] 00725 msg.hello().hello_msg_count_++; 00726 } 00727 else // there is already existing item in the linkcodes_count with certain link_code 00728 count = (*pos).second; // count is set with number of OLSR_hello_msg with the given link_code 00729 00730 int i = msg.hello().hello_msg(count).nb_addrs_count_; 00731 msg.hello().hello_msg(count).nb_addrs_count_++; 00732 00733 assert(count >= 0 && count < OLSR_MAX_HELLOS); 00734 assert(i >= 0 && i < OLSR_MAX_ADDRS); 00735 00736 uint32_t pnt = NULL; 00737 pnt= msg.hello().hello_msg(count).size_pnt(); 00738 00739 node_id_t* pnt2 = NULL; 00740 pnt2 = &(link_tuple->nb_node_addr()); 00741 00742 hellomessage.set_neighbor_addr_list(count, nb_addrs_count_before[count], i, pnt2); // Set the neighbor_addr_list[i] of hello_msg[count] 00743 hellomessage.set_link_msg_size(count, nb_addrs_count_before[count], &pnt ); // Set the link_msg_size of hello_msg[count] 00744 hellomessage.set_neighbor_addr_count(count, nb_addrs_count_before[count], msg.hello().hello_msg(count).nb_addrs_count_); // Set the neighbor_addr_count of hello[count] 00745 00746 } 00747 } 00748 00749 hellomessage.set_msg_size( msg.size() ); 00750 hellomessage.set_hello_msgs_count( msg.hello().hello_msg_count_ ); 00751 00752 Radio::send( os(), Radio::BROADCAST_ADDRESS, hellomessage.buffer_size(), (uint8_t*)&hellomessage); 00753 Debug::debug( os(), "%i send HELLO with %i hello_msg! \n", Radio::id(os()), msg.hello().hello_msg_count_ ); 00754 } 00755 // ---------------------------------------------------------------------- 00756 template<typename OsModel_P, 00757 typename RoutingTable_P, 00758 typename Clock_P, 00759 typename Radio_P, 00760 typename Debug_P> 00761 void 00762 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00763 broadcast_tc() 00764 { 00765 OLSR_msg msg; 00766 BroadcastTcMessage tcmessage; 00767 00768 msg.msg_id() = TC; 00769 msg.vtime() = seconds_to_emf(OLSR_TOP_HOLD_TIME); 00770 msg.originator_addr() = Radio::id(os()); 00771 msg.ttl() = 255; 00772 msg.hop_count() = 0; 00773 msg.msg_seq_num() = msg_seq(); 00774 msg.tc().ansn() = ansn_; 00775 msg.tc().adv_nb_addrs_count_ = 0; 00776 00777 tcmessage.set_msg_id( TC ); 00778 tcmessage.set_vtime( seconds_to_emf(OLSR_TOP_HOLD_TIME) ); 00779 tcmessage.set_originator_addr( Radio::id(os()) ); 00780 tcmessage.set_ttl( 255 ); 00781 tcmessage.set_hop_count( 0 ); 00782 tcmessage.set_msg_seq_num( msg_seq() ); 00783 tcmessage.set_ansn( ansn_ ); 00784 00785 if (!mprselset().size()) 00786 { 00787 Debug::debug( os(), "Empty TC!!!!!! \n"); 00788 } 00789 00790 for (typename mprselset_t::iterator it = mprselset().begin(); it != mprselset().end(); it++) // TC message contains the MPR Selector nodes of this MPR node 00791 { 00792 OLSR_mprsel_tuple* mprsel_tuple = *it; 00793 int count = msg.tc().adv_nb_addrs_count_; 00794 00795 assert(count >= 0 && count < OLSR_MAX_ADDRS); 00796 msg.tc().adv_neighbor_addr_list(count) = mprsel_tuple->node_addr(); // each MPR selector nodes' address will be included in the TC message 00797 msg.tc().adv_nb_addrs_count_++; 00798 00799 Debug::debug( os(), "Put node %i into TC message \n", &(mprsel_tuple->node_addr()) ); 00800 tcmessage.set_adv_neighbor_addr_list( count, &(mprsel_tuple->node_addr()) ); 00801 } 00802 00803 tcmessage.set_msg_size( msg.size() ); 00804 00805 Radio::send( os(), Radio::BROADCAST_ADDRESS, msg.size(), (uint8_t*)&tcmessage ); 00806 00807 Debug::debug( os(), "%i send TC with %i NB address! \n", Radio::id(os()), msg.tc().adv_nb_addrs_count_ ); 00808 } 00809 // ----------------------------------------------------------------------- 00810 template<typename OsModel_P, 00811 typename RoutingTable_P, 00812 typename Clock_P, 00813 typename Radio_P, 00814 typename Debug_P> 00815 void 00816 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00817 timer_elapsed( void* userdata ) 00818 { 00819 seconds_hello++; 00820 seconds_tc++; 00821 00822 if ( seconds_hello == OLSR_HELLO_INTERVAL) 00823 { 00824 broadcast_hello(); 00825 seconds_hello = 0; 00826 } 00827 00828 if ( seconds_tc == OLSR_TC_INTERVAL) 00829 { 00830 broadcast_tc(); 00831 seconds_tc = 0; 00832 } 00833 00834 print_routing_table( routing_table_ ); 00835 00836 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), work_period_, this, 0 ); 00837 } 00838 00839 // ----------------------------------------------------------------------- 00840 template<typename OsModel_P, 00841 typename RoutingTable_P, 00842 typename Clock_P, 00843 typename Radio_P, 00844 typename Debug_P> 00845 void 00846 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00847 timer_expire_link_tuple( OLSR_link_tuple* tuple )// Removes link_tuple if expired. 00848 // Else if symmetric time has expired then it is assumed a neighbor loss, the timer is rescheduled to expire at tuple_->time(). 00849 // Otherwise the timer is rescheduled to expire at the minimum between tuple_->time() and tuple_->sym_time(). 00850 { 00851 time_t now = Clock::time( os() ); 00852 00853 if (tuple->time() < now) 00854 { 00855 rm_link_tuple(tuple); 00856 delete tuple; 00857 delete this; 00858 } 00859 else if (tuple->sym_time() < now) 00860 { 00861 nb_loss(tuple); 00862 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), ( (tuple->time()) - now ), this, 0 ); 00863 } 00864 else 00865 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), ( MIN( tuple->time(), tuple->sym_time()) - now ), this, 0 ); 00866 00867 } 00868 00869 // ----------------------------------------------------------------------- 00870 /*template<typename OsModel_P, 00871 typename RoutingTable_P, 00872 typename Clock_P, 00873 typename Radio_P, 00874 typename Debug_P> 00875 void 00876 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00877 timer_expire_nb_tuple( OLSR_nb_tuple* tuple ) 00878 { 00879 time_t now = Clock::time( os() ); 00880 00881 if (tuple.time() < now) 00882 { 00883 rm_nb_tuple(tuple); 00884 delete tuple; 00885 delete this; 00886 } 00887 00888 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), nb_tuple_expire_, this, 0 ); 00889 } 00890 */ 00891 // ----------------------------------------------------------------------- 00892 template<typename OsModel_P, 00893 typename RoutingTable_P, 00894 typename Clock_P, 00895 typename Radio_P, 00896 typename Debug_P> 00897 void 00898 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00899 timer_expire_nb2hop_tuple( OLSR_nb2hop_tuple* tuple ) 00900 { 00901 time_t now = Clock::time( os() ); 00902 00903 if (tuple->time() < now) 00904 { 00905 rm_nb2hop_tuple(tuple); 00906 delete tuple; 00907 delete this; 00908 } 00909 else 00910 { 00911 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), ( (tuple->time()) - now ), this, 0 ); 00912 } 00913 00914 00915 } 00916 00917 // ----------------------------------------------------------------------- 00918 template<typename OsModel_P, 00919 typename RoutingTable_P, 00920 typename Clock_P, 00921 typename Radio_P, 00922 typename Debug_P> 00923 void 00924 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00925 timer_expire_topology_tuple( OLSR_topology_tuple* tuple ) 00926 { 00927 time_t now = Clock::time( os() ); 00928 00929 if (tuple->time() < now) 00930 { 00931 rm_topology_tuple(tuple); 00932 delete tuple; 00933 delete this; 00934 } 00935 else 00936 { 00937 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), ( (tuple->time()) - now ), this, 0 ); 00938 } 00939 } 00940 00941 // ----------------------------------------------------------------------- 00942 template<typename OsModel_P, 00943 typename RoutingTable_P, 00944 typename Clock_P, 00945 typename Radio_P, 00946 typename Debug_P> 00947 void 00948 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00949 timer_expire_mprsel_tuple( OLSR_mprsel_tuple* tuple ) 00950 { 00951 //time_t now = Clock::time( os() ); 00952 double now = Clock::time( os() ); 00953 00954 if (tuple->time() < now) 00955 { 00956 rm_mprsel_tuple(tuple); 00957 delete tuple; 00958 delete this; 00959 } 00960 else 00961 { 00962 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), ( (tuple->time()) - now ), this, 0 ); 00963 } 00964 } 00965 00966 // ----------------------------------------------------------------------- 00967 template<typename OsModel_P, 00968 typename RoutingTable_P, 00969 typename Clock_P, 00970 typename Radio_P, 00971 typename Debug_P> 00972 void 00973 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00974 timer_expire_dup_tuple( OLSR_dup_tuple* tuple ) 00975 { 00976 time_t now = Clock::time( os() ); 00977 00978 if (tuple->time() < now) 00979 { 00980 rm_dup_tuple(tuple); 00981 delete tuple; 00982 delete this; 00983 } 00984 else 00985 { 00986 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), ( (tuple->time()) - now ), this, 0 ); 00987 } 00988 } 00989 // ----------------------------------------------------------------------- 00990 template<typename OsModel_P, 00991 typename RoutingTable_P, 00992 typename Clock_P, 00993 typename Radio_P, 00994 typename Debug_P> 00995 void 00996 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 00997 receive( node_id_t from, size_t len, block_data_t *data ) 00998 { 00999 if ( from == Radio::id(os()) ) // Coming back to myself, Radio::id(os()) is the id of this receiving node 01000 return; 01001 01002 uint8_t msg_id = *data; 01003 01004 switch (msg_id) 01005 { 01006 case HELLO: // HELLO 01007 { 01008 BroadcastHelloMessage *message = (BroadcastHelloMessage*)data; 01009 OLSR_dup_tuple *duplicated = find_dup_tuple( message->originator_addr(), message->msg_seq_num() ); 01010 01011 if (duplicated == NULL) 01012 { 01013 process_hello(*message, from); 01014 } 01015 else 01016 { 01017 forward_hello(from, *message, duplicated); 01018 } 01019 01020 break; 01021 } 01022 case TC: // TC 01023 { 01024 BroadcastTcMessage *message = (BroadcastTcMessage*) data; 01025 OLSR_dup_tuple *duplicated = find_dup_tuple( message->originator_addr(), message->msg_seq_num() ); 01026 01027 if (duplicated == NULL) 01028 { 01029 process_tc(*message, from); 01030 } 01031 else 01032 { 01033 forward_tc(from, *message, duplicated); 01034 } 01035 01036 break; 01037 } 01038 case DATA: // DATA 01039 { 01040 RoutingMessage *message = (RoutingMessage*) data; 01041 process_data(*message, from); 01042 01043 break; 01044 } 01045 default: 01046 { 01047 Debug::debug(os(), "%i received UNRECOGNIZED message type [%i]\n", Radio::id(os()), msg_id); 01048 } 01049 } 01050 01051 routing_table_computation(); // After processing all OLSR messages, recompute routing table 01052 01053 } 01054 01055 // ----------------------------------------------------------------------- 01056 // brief Processes a HELLO message following RFC 3626 specification. 01057 // Link sensing & population of the Neighbor Set & population of 2-hop Neighbor Set & population of MPR Selector Set 01058 01059 // param msg the OLSR hello message 01060 // param sender the address of the node where the message was sent 01061 01062 template<typename OsModel_P, 01063 typename RoutingTable_P, 01064 typename Clock_P, 01065 typename Radio_P, 01066 typename Debug_P> 01067 void 01068 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01069 process_hello(BroadcastHelloMessage& message, node_id_t sender) 01070 { 01071 Debug::debug(os(), "%i received HELLO FROM %i of SIZE %i with %i HELLO_MSG \n", Radio::id(os()), message.originator_addr(), message.msg_size(), message.hello_msgs_count() ); 01072 01073 link_sensing(message, sender); 01074 populate_nbset(message); 01075 populate_nb2hopset(message); 01076 mpr_computation(); 01077 populate_mprselset(message); 01078 } 01079 01080 // ----------------------------------------------------------------------- 01081 // brief Updates Link Set according to a new received HELLO message (following RFC 3626 specification). Neighbor Set is also updated if needed 01082 01083 // param msg the OLSR message which contains the HELLO message 01084 // param sender the address of the node where the message was sent 01085 01086 template<typename OsModel_P, 01087 typename RoutingTable_P, 01088 typename Clock_P, 01089 typename Radio_P, 01090 typename Debug_P> 01091 void 01092 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01093 link_sensing(BroadcastHelloMessage& message, node_id_t sender) 01094 { 01095 01096 #ifdef DEBUG_OLSRROUTING 01097 Debug::debug(os(), "Link Sensing receiving Hello with %i hello_msgn inside!!!\n", message.hello_msgs_count() ); 01098 #endif 01099 01100 time_t now = Clock::time( os() ); 01101 01102 // Construct OLSR_hello from BroadcastHelloMessage& message 01103 OLSR_hello hello; 01104 hello.htime_ = message.htime(); 01105 hello.willingness_ = message.willingness(); 01106 hello.hello_msg_count_ = message.hello_msgs_count(); 01107 for (int i = 0; i < hello.hello_msg_count_; i++ ) 01108 { 01109 hello.hello_body_[i].link_code_ = message.link_code(i, nb_addrs_count_before[i]); 01110 hello.hello_body_[i].link_msg_size_ = message.link_msg_size(i, nb_addrs_count_before[i]); 01111 hello.hello_body_[i].nb_addrs_count_ = message.neighbor_addr_count(i, nb_addrs_count_before[i]); 01112 for ( int j = 1; j < message.neighbor_addr_count(i, nb_addrs_count_before[i]); j++ ) 01113 { 01114 hello.hello_body_[i].nb_addrs_[j] = message.neighbor_addr_list(i, j, nb_addrs_count_before[i]); 01115 } 01116 01117 } 01118 01119 bool updated = false; 01120 bool created = false; 01121 01122 OLSR_link_tuple* link_tuple = find_link_tuple(sender); 01123 if (link_tuple == NULL) { // Create a new tuple 01124 01125 link_tuple = new OLSR_link_tuple; 01126 link_tuple->nb_node_addr() = sender; 01127 link_tuple->local_node_addr() = Radio::id(os()); 01128 link_tuple->sym_time() = now - 1; 01129 link_tuple->lost_time() = 0.0; 01130 link_tuple->time() = now + emf_to_seconds(message.vtime()); 01131 #ifdef DEBUG_OLSRROUTING 01132 Debug::debug(os(), "Adding new link_tuple!!! \n"); 01133 #endif 01134 add_link_tuple(link_tuple, hello.willingness()); 01135 created = true; 01136 } 01137 else // Update an existing tuple 01138 { 01139 #ifdef DEBUG_OLSRROUTING 01140 Debug::debug(os(), "Update an existing tuple!!! \n"); 01141 #endif 01142 updated = true; 01143 } 01144 01145 link_tuple->asym_time() = now + emf_to_seconds(message.vtime()); 01146 01147 assert(hello.hello_msg_count_ >= 0 && hello.hello_msg_count_ <= OLSR_MAX_HELLOS); 01148 for (int i = 0; i < hello.hello_msg_count_; i++) // for each the OLSR_hello_msg inside OLSR_hello 01149 { 01150 OLSR_hello_msg& hello_msg = hello.hello_msg(i); 01151 int lt = hello_msg.link_code() & 0x03; 01152 int nt = hello_msg.link_code() >> 2; 01153 // We must not process invalid advertised links 01154 if ((lt == OLSR_SYM_LINK && nt == OLSR_NOT_NEIGH) || (nt != OLSR_SYM_NEIGH && nt != OLSR_MPR_NEIGH && nt != OLSR_NOT_NEIGH)) 01155 continue; 01156 01157 assert(hello_msg.nb_addrs_count_ >= 0 && hello_msg.nb_addrs_count_ <= OLSR_MAX_ADDRS); 01158 for (int j = 0; j < hello_msg.nb_addrs_count_; j++) // for each the Neighbor_Interface_Address inside a OLSR_hello_msg 01159 { 01160 if (hello_msg.neighbor_addr_list(j) == Radio::id(os())) 01161 { 01162 if (lt == OLSR_LOST_LINK) 01163 { 01164 link_tuple->sym_time() = now - 1; 01165 updated = true; 01166 } 01167 else if (lt == OLSR_SYM_LINK || lt == OLSR_ASYM_LINK) 01168 { 01169 link_tuple->sym_time() = now + emf_to_seconds(message.vtime()); 01170 link_tuple->time() = link_tuple->sym_time() + OLSR_NEIGHB_HOLD_TIME; 01171 link_tuple->lost_time() = 0.0; 01172 updated = true; 01173 } 01174 break; 01175 } 01176 } 01177 } 01178 01179 link_tuple->time() = MAX(link_tuple->time(), link_tuple->asym_time()); 01180 01181 if (updated) // whenever the link tuple is updated, the corresponding neighbor tuple also needs update 01182 updated_link_tuple(link_tuple); 01183 01184 // Schedules link tuple deletion 01185 timer_expire_link_tuple(link_tuple); 01186 01187 } 01188 01189 // ----------------------------------------------------------------------- 01190 // brief Updates the Neighbor Set according to the information contained in a new received HELLO message (following RFC 3626). 01191 // basically the "nb_tuple->status" will be updated 01192 01193 // param msg the %OLSR message which contains the HELLO message. 01194 01195 template<typename OsModel_P, 01196 typename RoutingTable_P, 01197 typename Clock_P, 01198 typename Radio_P, 01199 typename Debug_P> 01200 void 01201 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01202 populate_nbset(BroadcastHelloMessage& message) 01203 { 01204 OLSR_nb_tuple* nb_tuple = find_nb_tuple(message.originator_addr()); 01205 if (nb_tuple != NULL) 01206 nb_tuple->willingness() = message.willingness(); 01207 } 01208 01209 // ----------------------------------------------------------------------- 01210 // brief Updates the 2-hop Neighbor Set according to the information contained in a new received HELLO message (following RFC 3626). 01211 01212 // param msg the %OLSR message which contains the HELLO message. 01213 01214 template<typename OsModel_P, 01215 typename RoutingTable_P, 01216 typename Clock_P, 01217 typename Radio_P, 01218 typename Debug_P> 01219 void 01220 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01221 populate_nb2hopset(BroadcastHelloMessage& message) 01222 { 01223 time_t now = Clock::time( os() ); 01224 01225 // Construct OLSR_hello from BroadcastHelloMessage& message 01226 OLSR_hello hello; 01227 hello.htime_ = message.htime(); 01228 hello.willingness_ = message.willingness(); 01229 hello.hello_msg_count_ = message.hello_msgs_count(); 01230 01231 for (int i = 0; i < hello.hello_msg_count_; i++ ) 01232 { 01233 hello.hello_body_[i].link_code_ = message.link_code(i, nb_addrs_count_before[i]); 01234 hello.hello_body_[i].link_msg_size_ = message.link_msg_size(i, nb_addrs_count_before[i]); 01235 hello.hello_body_[i].nb_addrs_count_ = message.neighbor_addr_count(i, nb_addrs_count_before[i]); 01236 for ( int j = 1; j < message.neighbor_addr_count(i, nb_addrs_count_before[i]); j++ ) 01237 { 01238 hello.hello_body_[i].nb_addrs_[j] = message.neighbor_addr_list(i, j, nb_addrs_count_before[i]); 01239 } 01240 01241 } 01242 01243 01244 01245 for (typename linkset_t::iterator it_lt = linkset().begin(); it_lt != linkset().end(); it_lt++) 01246 { 01247 OLSR_link_tuple* link_tuple = *it_lt; 01248 01249 if (link_tuple->nb_node_addr() == message.originator_addr()) 01250 { 01251 if (link_tuple->sym_time() >= now) 01252 { 01253 assert(hello.hello_msg_count_ >= 0 && hello.hello_msg_count_ <= OLSR_MAX_HELLOS); 01254 for (int i = 0; i < hello.hello_msg_count_; i++) // hello_msg_count_ is the number of the "hello_msg" included inside each "hello" 01255 { 01256 OLSR_hello_msg& hello_msg = hello.hello_msg(i); 01257 01258 int nt = hello_msg.link_code() >> 2; // nt = node_type 01259 01260 assert(hello_msg.nb_addrs_count_ >= 0 && hello_msg.nb_addrs_count_ <= OLSR_MAX_ADDRS); 01261 for (int j = 0; j < hello_msg.nb_addrs_count_; j++) // hello_msg.count is the number of the "Neighbor_Interface_Address" inside each "hello_msg" 01262 // the "Neighbor_Interface_Address" is actually the 2-hop neighbor address 01263 { 01264 node_id_t nb2hop_addr = hello_msg.neighbor_addr_list(j); 01265 if (nt == OLSR_SYM_NEIGH || nt == OLSR_MPR_NEIGH) 01266 { 01267 // if the main address of the 2-hop neighbor address = main address of the receiving node: silently discard the 2-hop neighbor address 01268 if (nb2hop_addr != Radio::id(os())) 01269 { 01270 // Otherwise, a 2-hop tuple is created 01271 OLSR_nb2hop_tuple* nb2hop_tuple = find_nb2hop_tuple(message.originator_addr(), nb2hop_addr); 01272 if (nb2hop_tuple == NULL) 01273 { 01274 nb2hop_tuple = new OLSR_nb2hop_tuple; 01275 nb2hop_tuple->nb_node_addr() = message.originator_addr(); 01276 nb2hop_tuple->nb2hop_addr() = nb2hop_addr; 01277 add_nb2hop_tuple(nb2hop_tuple); 01278 nb2hop_tuple->time() = now + emf_to_seconds(message.vtime()); 01279 01280 // Schedules nb2hop tuple deletion 01281 timer_expire_nb2hop_tuple(nb2hop_tuple); 01282 01283 } 01284 else 01285 { 01286 nb2hop_tuple->time() = now + emf_to_seconds(message.vtime()); 01287 } 01288 01289 } 01290 } 01291 else if (nt == OLSR_NOT_NEIGH) 01292 { 01293 // For each 2-hop node listed in the HELLO message with Neighbor Type equal to NOT_NEIGH all 2-hop tuples where: N_neighbor_node_addr == Originator 01294 // Address AND N_2hop_addr == main address of the 2-hop neighbor are deleted. 01295 erase_nb2hop_tuples(message.originator_addr(), nb2hop_addr); 01296 } 01297 } 01298 } 01299 } 01300 } 01301 } 01302 } 01303 01304 // ----------------------------------------------------------------------- 01305 // brief Compute MPR set of a node following RFC 3626 hints. 01306 01307 template<typename OsModel_P, 01308 typename RoutingTable_P, 01309 typename Clock_P, 01310 typename Radio_P, 01311 typename Debug_P> 01312 void 01313 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01314 mpr_computation() 01315 { 01316 time_t now = Clock::time( os() ); 01317 01318 clear_mprset(); 01319 nbset_t N; 01320 nb2hopset_t N2; 01321 01322 // N is the subset of neighbors of the node, which are neighbor "of the interface I" 01323 for (typename nbset_t::iterator it = nbset().begin(); it != nbset().end(); it++) 01324 if ((*it)->status() == OLSR_STATUS_SYM) // I think that we need this check 01325 N.push_back(*it); 01326 01327 // N2 is the set of 2-hop neighbors reachable from "the interface I", excluding: 01328 01329 // (i) the nodes only reachable by members of N with willingness WILL_NEVER 01330 // (ii) the node performing the computation 01331 // (iii) all the symmetric neighbors: the nodes for which there exists a symmetric link to this node on some interface. 01332 01333 for (typename nb2hopset_t::iterator it = nb2hopset().begin(); it != nb2hopset().end(); it++) { 01334 OLSR_nb2hop_tuple* nb2hop_tuple = *it; 01335 bool ok = true; 01336 OLSR_nb_tuple* nb_tuple = find_sym_nb_tuple(nb2hop_tuple->nb_node_addr()); 01337 if (nb_tuple == NULL) 01338 ok = false; 01339 else { 01340 nb_tuple = find_nb_tuple(nb2hop_tuple->nb_node_addr(), OLSR_WILL_NEVER); 01341 if (nb_tuple != NULL) 01342 ok = false; 01343 else { 01344 nb_tuple = find_sym_nb_tuple(nb2hop_tuple->nb2hop_addr()); 01345 if (nb_tuple != NULL) 01346 ok = false; 01347 } 01348 } 01349 01350 if (ok) 01351 N2.push_back(nb2hop_tuple); 01352 } 01353 01354 // 1. Start with an MPR set made of all members of N with N_willingness equal to WILL_ALWAYS 01355 for (typename nbset_t::iterator it = N.begin(); it != N.end(); it++) { 01356 OLSR_nb_tuple* nb_tuple = *it; 01357 if (nb_tuple->willingness() == OLSR_WILL_ALWAYS) 01358 insert_mpr_addr(nb_tuple->nb_node_addr()); 01359 } 01360 01361 // 2. Calculate D(y), where y is a member of N, for all nodes in N. 01362 // We will do this later. 01363 01364 // 3. Add to the MPR set those nodes in N, which are the *only* nodes to provide reachability to a node in N2. 01365 // Remove the nodes from N2 which are now covered by a node in the MPR set. 01366 mprset_t foundset; 01367 std::set<node_id_t> deleted_addrs; 01368 for (typename nb2hopset_t::iterator it = N2.begin(); it != N2.end(); it++) 01369 { 01370 OLSR_nb2hop_tuple* nb2hop_tuple1 = *it; 01371 01372 typename mprset_t::iterator pos = foundset.find(nb2hop_tuple1->nb2hop_addr()); 01373 if (pos != foundset.end()) 01374 continue; 01375 01376 bool found = false; 01377 for (typename nbset_t::iterator it2 = N.begin();it2 != N.end();it2++) { 01378 if ((*it2)->nb_node_addr() == nb2hop_tuple1->nb_node_addr()) { 01379 found = true; 01380 break; 01381 } 01382 } 01383 if (!found) 01384 continue; 01385 01386 found = false; 01387 for (typename nb2hopset_t::iterator it2 = it + 1; it2 != N2.end(); it2++) { 01388 OLSR_nb2hop_tuple* nb2hop_tuple2 = *it2; 01389 if (nb2hop_tuple1->nb2hop_addr() == nb2hop_tuple2->nb2hop_addr()) { 01390 foundset.insert(nb2hop_tuple1->nb2hop_addr()); 01391 found = true; 01392 break; 01393 } 01394 } 01395 if (!found) { 01396 insert_mpr_addr(nb2hop_tuple1->nb_node_addr()); 01397 01398 for (typename nb2hopset_t::iterator it2 = it + 1; it2 != N2.end(); it2++) { 01399 OLSR_nb2hop_tuple* nb2hop_tuple2 = *it2; 01400 if (nb2hop_tuple1->nb_node_addr() == nb2hop_tuple2->nb_node_addr()) { 01401 deleted_addrs.insert(nb2hop_tuple2->nb2hop_addr()); 01402 it2 = N2.erase(it2); 01403 it2--; 01404 } 01405 } 01406 it = N2.erase(it); 01407 it--; 01408 } 01409 01410 for (typename std::set<node_id_t>::iterator it2 = deleted_addrs.begin(); it2 != deleted_addrs.end(); it2++) 01411 { 01412 for (typename nb2hopset_t::iterator it3 = N2.begin(); 01413 it3 != N2.end(); 01414 it3++) { 01415 if ((*it3)->nb2hop_addr() == *it2) { 01416 it3 = N2.erase(it3); 01417 it3--; 01418 // I have to reset the external iterator because it 01419 // may have been invalidated by the latter deletion 01420 it = N2.begin(); 01421 it--; 01422 } 01423 } 01424 } 01425 deleted_addrs.clear(); 01426 } 01427 01428 // 4. While there exist nodes in N2 which are not covered by at 01429 // least one node in the MPR set: 01430 while (N2.begin() != N2.end()) { 01431 // 4.1. For each node in N, calculate the reachability, i.e., the 01432 // number of nodes in N2 which are not yet covered by at 01433 // least one node in the MPR set, and which are reachable 01434 // through this 1-hop neighbor 01435 std::map<int, std::vector<OLSR_nb_tuple*> > reachability; 01436 std::set<int> rs; 01437 for (typename nbset_t::iterator it = N.begin(); it != N.end(); it++) { 01438 OLSR_nb_tuple* nb_tuple = *it; 01439 int r = 0; 01440 for (typename nb2hopset_t::iterator it2 = N2.begin(); it2 != N2.end(); it2++) { 01441 OLSR_nb2hop_tuple* nb2hop_tuple = *it2; 01442 if (nb_tuple->nb_node_addr() == nb2hop_tuple->nb_node_addr()) 01443 r++; 01444 } 01445 rs.insert(r); 01446 reachability[r].push_back(nb_tuple); 01447 } 01448 01449 // 4.2. Select as a MPR the node with highest N_willingness among 01450 // the nodes in N with non-zero reachability. In case of 01451 // multiple choice select the node which provides 01452 // reachability to the maximum number of nodes in N2. In 01453 // case of multiple nodes providing the same amount of 01454 // reachability, select the node as MPR whose D(y) is 01455 // greater. Remove the nodes from N2 which are now covered 01456 // by a node in the MPR set. 01457 OLSR_nb_tuple* max = NULL; 01458 int max_r = 0; 01459 for (std::set<int>::iterator it = rs.begin(); it != rs.end(); it++) { 01460 int r = *it; 01461 if (r > 0) { 01462 for (typename std::vector<OLSR_nb_tuple*>::iterator it2 = reachability[r].begin(); 01463 it2 != reachability[r].end(); 01464 it2++) { 01465 OLSR_nb_tuple* nb_tuple = *it2; 01466 if (max == NULL || nb_tuple->willingness() > max->willingness()) { 01467 max = nb_tuple; 01468 max_r = r; 01469 } 01470 else if (nb_tuple->willingness() == max->willingness()) { 01471 if (r > max_r) { 01472 max = nb_tuple; 01473 max_r = r; 01474 } 01475 else if (r == max_r) { 01476 if (degree(nb_tuple) > degree(max)) { 01477 max = nb_tuple; 01478 max_r = r; 01479 } 01480 } 01481 } 01482 } 01483 } 01484 } 01485 if (max != NULL) { 01486 insert_mpr_addr(max->nb_node_addr()); 01487 std::set<node_id_t> nb2hop_addrs; 01488 for (typename nb2hopset_t::iterator it = N2.begin(); it != N2.end(); it++) { 01489 OLSR_nb2hop_tuple* nb2hop_tuple = *it; 01490 if (nb2hop_tuple->nb_node_addr() == max->nb_node_addr()) { 01491 nb2hop_addrs.insert(nb2hop_tuple->nb2hop_addr()); 01492 it = N2.erase(it); 01493 it--; 01494 } 01495 } 01496 for (typename nb2hopset_t::iterator it = N2.begin(); it != N2.end(); it++) { 01497 OLSR_nb2hop_tuple* nb2hop_tuple = *it; 01498 typename std::set<node_id_t>::iterator it2 = nb2hop_addrs.find(nb2hop_tuple->nb2hop_addr()); 01499 if (it2 != nb2hop_addrs.end()) { 01500 it = N2.erase(it); 01501 it--; 01502 } 01503 } 01504 } 01505 } 01506 } 01507 01508 // ----------------------------------------------------------------------- 01509 template<typename OsModel_P, 01510 typename RoutingTable_P, 01511 typename Clock_P, 01512 typename Radio_P, 01513 typename Debug_P> 01514 bool 01515 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01516 find_mpr_addr(node_id_t addr) 01517 { 01518 typename mprset_t::iterator it = mprset_.find(addr); 01519 return (it != mprset_.end()); 01520 } 01521 // ----------------------------------------------------------------------- 01522 template<typename OsModel_P, 01523 typename RoutingTable_P, 01524 typename Clock_P, 01525 typename Radio_P, 01526 typename Debug_P> 01527 void 01528 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01529 insert_mpr_addr(node_id_t addr) 01530 { 01531 mprset_.insert(addr); 01532 } 01533 // ----------------------------------------------------------------------- 01534 template<typename OsModel_P, 01535 typename RoutingTable_P, 01536 typename Clock_P, 01537 typename Radio_P, 01538 typename Debug_P> 01539 void 01540 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01541 clear_mprset() 01542 { 01543 mprset_.clear(); 01544 } 01545 // ----------------------------------------------------------------------- 01546 01547 01548 // brief Updates the MPR Selector Set according to the information contained in a new received HELLO message (following RFC 3626). 01549 01550 // param msg the %OLSR message which contains the HELLO message. 01551 01552 template<typename OsModel_P, 01553 typename RoutingTable_P, 01554 typename Clock_P, 01555 typename Radio_P, 01556 typename Debug_P> 01557 void 01558 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01559 populate_mprselset(BroadcastHelloMessage& message) 01560 { 01561 time_t now = Clock::time( os() ); 01562 01563 Debug::debug(os(), "Receive Hello message from %i with %i hello_msg, inside populate_mprselset \n", message.originator_addr(), message.hello_msgs_count() ); 01564 01565 // Construct OLSR_hello from BroadcastHelloMessage& message 01566 OLSR_hello hello; 01567 hello.htime_ = message.htime(); 01568 hello.willingness_ = message.willingness(); 01569 hello.hello_msg_count_ = message.hello_msgs_count(); 01570 01571 for (int i = 0; i < hello.hello_msg_count_; i++ ) 01572 { 01573 hello.hello_body_[i].link_code_ = message.link_code(i, nb_addrs_count_before[i]); 01574 hello.hello_body_[i].link_msg_size_ = message.link_msg_size(i, nb_addrs_count_before[i]); 01575 hello.hello_body_[i].nb_addrs_count_ = message.neighbor_addr_count(i, nb_addrs_count_before[i]); 01576 for ( int j = 1; j < message.neighbor_addr_count(i, nb_addrs_count_before[i]); j++ ) 01577 { 01578 hello.hello_body_[i].nb_addrs_[j] = message.neighbor_addr_list(i, j, nb_addrs_count_before[i]); 01579 } 01580 01581 } 01582 01583 01584 assert(hello.hello_msg_count_ >= 0 && hello.hello_msg_count_ <= OLSR_MAX_HELLOS); 01585 for (int i = 0; i < hello.hello_msg_count_; i++) 01586 { 01587 OLSR_hello_msg& hello_msg = hello.hello_msg(i); 01588 int nt = hello_msg.link_code() >> 2; 01589 if (nt == OLSR_MPR_NEIGH) 01590 { 01591 assert(hello_msg.nb_addrs_count_ >= 0 && hello_msg.nb_addrs_count_ <= OLSR_MAX_ADDRS); 01592 for (int j = 0; j < hello_msg.nb_addrs_count_; j++) 01593 { 01594 if (hello_msg.neighbor_addr_list(j) == Radio::id(os())) 01595 { 01596 // Create a new entry into the mpr selector set 01597 OLSR_mprsel_tuple* mprsel_tuple = find_mprsel_tuple(message.originator_addr()); 01598 if (mprsel_tuple == NULL) 01599 { 01600 mprsel_tuple = new OLSR_mprsel_tuple; 01601 mprsel_tuple->node_addr() = message.originator_addr(); 01602 mprsel_tuple->time() = now + emf_to_seconds(message.vtime()); 01603 add_mprsel_tuple(mprsel_tuple); 01604 01605 // Schedules mpr selector tuple deletion 01606 timer_expire_mprsel_tuple(mprsel_tuple); 01607 01608 } 01609 else 01610 mprsel_tuple->time() = now + emf_to_seconds(message.vtime()); 01611 } 01612 } 01613 } 01614 } 01615 } 01616 01617 // ----------------------------------------------------------------------- 01618 01619 // brief OLSR's default forwarding algorithm. 01620 01621 //param msg the OLSR message which must be forwarded. 01622 //param dup_tuple NULL if the message has never been considered for forwarding, or a duplicate tuple in other case. 01623 01624 template<typename OsModel_P, 01625 typename RoutingTable_P, 01626 typename Clock_P, 01627 typename Radio_P, 01628 typename Debug_P> 01629 void 01630 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01631 forward_hello(node_id_t from, BroadcastHelloMessage& message, OLSR_dup_tuple* dup_tuple) 01632 { 01633 time_t now = Clock::time( os() ); 01634 01635 OLSR_link_tuple* link_tuple = find_sym_link_tuple(from, now); // If the sender address is not in the symmetric 1-hop neighborhood the message must not be forwarded 01636 if (link_tuple == NULL) 01637 return; 01638 01639 if (dup_tuple != NULL && dup_tuple->retransmitted()) // If the message has already been considered for forwarding, it must not be retransmitted again 01640 { 01641 #ifdef DEBUG_OLSRROUTING 01642 Debug::debug(os(), "%f: Node %d does not forward a message received from %d because it is duplicated\n", Clock::time( os() ), Radio::id( os() ), dup_tuple->addr() ); 01643 #endif 01644 01645 return; 01646 } 01647 01648 bool retransmitted = false; // If sender_address is an address of a MPR selector of this node and ttl > 1, the message must be retransmitted 01649 if (message.ttl() > 1) 01650 { 01651 OLSR_mprsel_tuple* mprsel_tuple = find_mprsel_tuple(from); 01652 if (mprsel_tuple != NULL) // the sender address is an address of a MPR selector of this local node 01653 { 01654 message.set_ttl( message.ttl() - 1 ); 01655 message.set_hop_count( message.hop_count() + 1 ); 01656 01657 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), delay_, this, 0 ); // introduce a random delay before retransmit the message 01658 Radio::send( os(), Radio::BROADCAST_ADDRESS, message.buffer_size(), (uint8_t*)&message); 01659 retransmitted = true; 01660 } 01661 } 01662 01663 if (dup_tuple != NULL) // Update duplicate tuple 01664 { 01665 dup_tuple->time() = now + OLSR_DUP_HOLD_TIME; 01666 dup_tuple->retransmitted() = retransmitted; 01667 } 01668 else // or create a new one 01669 { 01670 OLSR_dup_tuple* new_dup = new OLSR_dup_tuple; 01671 new_dup->addr() = message.originator_addr(); 01672 new_dup->seq_num() = message.msg_seq_num(); 01673 new_dup->time() = now + OLSR_DUP_HOLD_TIME; 01674 new_dup->retransmitted() = retransmitted; 01675 add_dup_tuple(new_dup); 01676 01677 // Schedules dup tuple deletion 01678 timer_expire_dup_tuple(new_dup); 01679 } 01680 } 01681 // ----------------------------------------------------------------------- 01682 01683 // brief OLSR's default forwarding algorithm. 01684 01685 //param msg the OLSR message which must be forwarded. 01686 //param dup_tuple NULL if the message has never been considered for forwarding, or a duplicate tuple in other case. 01687 01688 template<typename OsModel_P, 01689 typename RoutingTable_P, 01690 typename Clock_P, 01691 typename Radio_P, 01692 typename Debug_P> 01693 void 01694 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01695 forward_tc(node_id_t from, BroadcastTcMessage& message, OLSR_dup_tuple* dup_tuple) 01696 { 01697 time_t now = Clock::time( os() ); 01698 01699 OLSR_link_tuple* link_tuple = find_sym_link_tuple(from, now); // If the sender address is not in the symmetric 1-hop neighborhood the message must not be forwarded 01700 if (link_tuple == NULL) 01701 return; 01702 01703 if (dup_tuple != NULL && dup_tuple->retransmitted()) // If the message has already been considered for forwarding, it must not be retransmitted again 01704 { 01705 #ifdef DEBUG_OLSRROUTING 01706 Debug::debug(os(), "%f: Node %d does not forward a message received from %d because it is duplicated\n", Clock::time( os() ), Radio::id( os() ), dup_tuple->addr() ); 01707 #endif 01708 01709 return; 01710 } 01711 01712 bool retransmitted = false; // If sender_address is an address of a MPR selector of this node and ttl > 1, the message must be retransmitted 01713 if (message.ttl() > 1) 01714 { 01715 OLSR_mprsel_tuple* mprsel_tuple = find_mprsel_tuple(from); 01716 if (mprsel_tuple != NULL) // the sender address is an address of a MPR selector of this local node 01717 { 01718 message.set_ttl( message.ttl() - 1 ); 01719 message.set_hop_count( message.hop_count() + 1 ); 01720 01721 Timer::template set_timer<self_type, &self_type::timer_elapsed>( os(), delay_, this, 0 ); // introduce a random delay before retransmit the message 01722 Radio::send( os(), Radio::BROADCAST_ADDRESS, message.buffer_size(), (uint8_t*)&message); 01723 retransmitted = true; 01724 } 01725 } 01726 01727 if (dup_tuple != NULL) // Update duplicate tuple 01728 { 01729 dup_tuple->time() = now + OLSR_DUP_HOLD_TIME; 01730 dup_tuple->retransmitted() = retransmitted; 01731 } 01732 else // or create a new one 01733 { 01734 OLSR_dup_tuple* new_dup = new OLSR_dup_tuple; 01735 new_dup->addr() = message.originator_addr(); 01736 new_dup->seq_num() = message.msg_seq_num(); 01737 new_dup->time() = now + OLSR_DUP_HOLD_TIME; 01738 new_dup->retransmitted() = retransmitted; 01739 add_dup_tuple(new_dup); 01740 01741 // Schedules dup tuple deletion 01742 timer_expire_dup_tuple(new_dup); 01743 } 01744 } 01745 01746 // ----------------------------------------------------------------------- 01747 // brief Processes a TC message following RFC 3626 specification, The Topology Set is updated (if needed) with the information of the received TC message. 01748 01749 // param msg the OLSR message which contains the TC message. 01750 // param sender the address of the node where the message was sent from. 01751 01752 template<typename OsModel_P, 01753 typename RoutingTable_P, 01754 typename Clock_P, 01755 typename Radio_P, 01756 typename Debug_P> 01757 void 01758 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01759 process_tc(BroadcastTcMessage& message, node_id_t sender) 01760 { 01761 Debug::debug(os(), "%i received TC from %i of size %i \n", Radio::id(os()), message.originator_addr(), message.msg_size() ); 01762 //Debug::debug(os(), "%i received TC from %i \n", Radio::id(os()), message.originator_addr()); 01763 01764 time_t now = Clock::time( os() ); 01765 01766 // Construct OLSR_tc from BroadcastTcMessage& message 01767 OLSR_tc tc; 01768 tc.ansn_ = message.ansn(); 01769 tc.adv_nb_addrs_count_ = message.adv_neighbor_addr_list_size(); 01770 for ( int i = 1; i < message.adv_neighbor_addr_list_size(); i++ ) 01771 { 01772 tc.adv_nb_addrs_[i] = message.adv_neighbor_addr_list(i); 01773 } 01774 01775 01776 // 1. If the sender of this message is not in the symmetric 1-hop neighborhood of this node, the message MUST be discarded. 01777 OLSR_link_tuple* link_tuple = find_sym_link_tuple(sender, now); 01778 if (link_tuple == NULL) 01779 return; 01780 01781 // 2. If there exist some tuple in the topology set where: 01782 // T_last_addr == originator address AND T_seq > ANSN, then further processing of this TC message MUST NOT be performed. 01783 OLSR_topology_tuple* topology_tuple = find_newer_topology_tuple(message.originator_addr(), tc.ansn()); 01784 if (topology_tuple != NULL) 01785 return; 01786 01787 // 3. All tuples in the topology set where: 01788 // T_last_addr == originator address AND T_seq < ANSN, MUST be removed from the topology set. 01789 erase_older_topology_tuples(message.originator_addr(), tc.ansn()); 01790 01791 // 4. For each of the advertised neighbor main address received in the TC message: 01792 for (int i = 0; i < tc.adv_nb_addrs_count_; i++) 01793 { 01794 assert(i >= 0 && i < OLSR_MAX_ADDRS); 01795 node_id_t addr = tc.adv_neighbor_addr_list(i); 01796 01797 // 4.1. If there exist some tuple in the topology set where: 01798 // T_dest_addr == advertised neighbor main address, AND T_last_addr == originator address, 01799 // then the holding time of that tuple MUST be set to: T_time = current time + validity time. 01800 01801 OLSR_topology_tuple* topology_tuple = find_topology_tuple(addr, message.originator_addr()); 01802 if (topology_tuple != NULL) 01803 topology_tuple->time() = now + emf_to_seconds(message.vtime()); 01804 01805 // 4.2. Otherwise, a new tuple MUST be recorded in the topology set where: 01806 // T_dest_addr = advertised neighbor main address, 01807 // T_last_addr = originator address, 01808 // T_seq = ANSN, 01809 // T_time = current time + validity time. 01810 else 01811 { 01812 OLSR_topology_tuple* topology_tuple = new OLSR_topology_tuple; 01813 topology_tuple->dest_addr() = addr; 01814 topology_tuple->last_addr() = message.originator_addr(); 01815 topology_tuple->seq() = tc.ansn(); 01816 topology_tuple->time() = now + emf_to_seconds(message.vtime()); 01817 add_topology_tuple(topology_tuple); 01818 01819 // Schedules topology tuple deletion 01820 timer_expire_topology_tuple(topology_tuple); 01821 } 01822 } 01823 } 01824 01825 // ----------------------------------------------------------------------- 01826 // param msg the OLSR message which contains the TC message. 01827 // param sender the address of the node where the message was sent from. 01828 01829 template<typename OsModel_P, 01830 typename RoutingTable_P, 01831 typename Clock_P, 01832 typename Radio_P, 01833 typename Debug_P> 01834 void 01835 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01836 process_data(RoutingMessage& msg, node_id_t sender) 01837 { 01838 Debug::debug(os(), "%i received DATA from %i \n", Radio::id(os()), msg.source()); 01839 01840 if (msg.destination() == Radio::id(os())) // Got the destination 01841 { 01842 Debug::debug(os(), "%i got his DATA from %i \n", Radio::id(os()), msg.source()); 01843 } 01844 else if (route_exists(msg.destination())) // Check any route to destination in the local routing table 01845 { 01846 Debug::debug(os(), "%i forwards DATA for %i. next hop [%i] %i hops away \n", 01847 Radio::id(os()), msg.destination(), routing_table_[msg.destination()].next_addr, routing_table_[msg.destination()].hops); 01848 01849 Radio::send(os(), routing_table_[msg.destination()].next_addr, msg.buffer_size(), (uint8_t*) & msg); //Forward message to next hop in the routing table entry 01850 //routing_table_[msg.destination()].lifetime = ROUTE_TIMEOUT; 01851 } 01852 else 01853 { 01854 Debug::debug(os(), "%i ERROR: no route for \n", Radio::id(os()), msg.destination()); 01855 01856 } 01857 } 01858 01859 // ----------------------------------------------------------------------- 01860 // brief Creates the routing table of the node following RFC 3626 hints. 01861 01862 // The routing table is updated in case of: 01863 // -- neighbor appearance or loss 01864 // -- 2-hop tuple is created or removed 01865 // -- topology tuple is created or removed 01866 // -- multiple interface association information changes 01867 01868 template<typename OsModel_P, 01869 typename RoutingTable_P, 01870 typename Clock_P, 01871 typename Radio_P, 01872 typename Debug_P> 01873 void 01874 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01875 routing_table_computation() 01876 { 01877 routing_table_.clear(); // 1. All the entries from the routing table are removed. 01878 01879 for (typename nbset_t::iterator it = nbset().begin(); it != nbset().end(); it++) // 2. New routing entries are added starting with the symmetric neighbors (h=1) as the destination nodes. 01880 { 01881 OLSR_nb_tuple* nb_tuple = *it; 01882 01883 if (nb_tuple->status() == OLSR_STATUS_SYM) 01884 { 01885 bool nb_node_addr = false; 01886 OLSR_link_tuple* lt = NULL; 01887 01888 for (typename linkset_t::iterator it2 = linkset().begin(); it2 != linkset().end(); it2++) 01889 { 01890 OLSR_link_tuple* link_tuple = *it2; 01891 if (link_tuple->nb_node_addr() == nb_tuple->nb_node_addr() && link_tuple->time() >= Clock::time( os() )) 01892 { 01893 lt = link_tuple; 01894 01895 #ifdef DEBUG_OLSRROUTING 01896 Debug::debug( os(), "OlsrRouting: Add %i because not known\n", link_tuple->nb_node_addr() ); 01897 #endif 01898 routing_table_[link_tuple->nb_node_addr()] = RoutingTableEntry(link_tuple->nb_node_addr(), link_tuple->nb_node_addr(), 1); //insert 01899 01900 if (link_tuple->nb_node_addr() == nb_tuple->nb_node_addr()) 01901 nb_node_addr = true; 01902 } 01903 } 01904 01905 if (!nb_node_addr && lt != NULL) 01906 { 01907 #ifdef DEBUG_OLSRROUTING 01908 Debug::debug( os(), "OlsrRouting: Add %i because not known\n", nb_tuple->nb_node_addr() ); 01909 #endif 01910 routing_table_[nb_tuple->nb_node_addr()] = RoutingTableEntry(nb_tuple->nb_node_addr(), lt->nb_node_addr(), 1); //insert 01911 } 01912 } 01913 } 01914 01915 // N2 is the set of 2-hop neighbors reachable from this node, excluding: 01916 01917 // (i) the nodes only reachable by members of N with willingness WILL_NEVER 01918 // (ii) the node performing the computation 01919 // (iii) all the symmetric neighbors: the nodes for which there exists a symmetric link to this node on some interface. 01920 for (typename nb2hopset_t::iterator it = nb2hopset().begin(); it != nb2hopset().end(); it++) 01921 { 01922 OLSR_nb2hop_tuple* nb2hop_tuple = *it; 01923 bool ok = true; 01924 OLSR_nb_tuple* nb_tuple = find_sym_nb_tuple(nb2hop_tuple->nb_node_addr()); 01925 if (nb_tuple == NULL) 01926 ok = false; 01927 else 01928 { 01929 nb_tuple = find_nb_tuple(nb2hop_tuple->nb_node_addr(), OLSR_WILL_NEVER); 01930 if (nb_tuple != NULL) 01931 ok = false; 01932 else 01933 { 01934 nb_tuple = find_sym_nb_tuple(nb2hop_tuple->nb2hop_addr()); 01935 if (nb_tuple != NULL) 01936 ok = false; 01937 } 01938 } 01939 01940 // Successfully find an entry in Nb_Tuple with willingness != NEVER 01941 // 3. For each node in N2 create a new entry in the routing table 01942 if (ok) { 01943 RoutingTableIterator it = routing_table_.find(nb2hop_tuple->nb_node_addr()); 01944 assert(it != NULL); 01945 01946 #ifdef DEBUG_OLSRROUTING 01947 Debug::debug( os(), "OlsrRouting: Add %i because not known\n", nb2hop_tuple->nb2hop_addr() ); 01948 #endif 01949 routing_table_[nb2hop_tuple->nb2hop_addr()] = RoutingTableEntry(nb2hop_tuple->nb2hop_addr(), it->second.next_addr, 2); //insert 01950 } 01951 } 01952 01953 for (uint32_t h = 2; ; h++) 01954 { 01955 bool added = false; 01956 01957 // 4.1. For each topology entry in the topology table, if its T_dest_addr does not correspond to R_dest_addr of any 01958 // route entry in the routing table AND its T_last_addr corresponds to R_dest_addr of a route entry whose R_dist 01959 // is equal to h, then a new route entry MUST be recorded in the routing table (if it does not already exist) 01960 for (typename topologyset_t::iterator it = topologyset().begin(); it != topologyset().end(); it++) 01961 { 01962 OLSR_topology_tuple* topology_tuple = *it; 01963 RoutingTableIterator it1 = routing_table_.find(topology_tuple->dest_addr()); 01964 RoutingTableIterator it2 = routing_table_.find(topology_tuple->last_addr()); 01965 if (it1 == routing_table_.end() && it2 != routing_table_.end() && it2->second.dest_addr == h) 01966 { 01967 #ifdef DEBUG_OLSRROUTING 01968 Debug::debug( os(), "OlsrRouting: Add %i because not known\n", topology_tuple->dest_addr() ); 01969 #endif 01970 routing_table_[topology_tuple->dest_addr()] = RoutingTableEntry(topology_tuple->dest_addr(), it2->second.next_addr, h+1); //insert 01971 01972 added = true; 01973 } 01974 } 01975 01976 if (!added) 01977 break; 01978 } 01979 } 01980 01981 // ----------------------------------------------------------------------- 01982 01983 template<typename OsModel_P, 01984 typename RoutingTable_P, 01985 typename Clock_P, 01986 typename Radio_P, 01987 typename Debug_P> 01988 void 01989 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 01990 add_dup_tuple(OLSR_dup_tuple* tuple) 01991 { 01992 insert_dup_tuple(tuple); 01993 } 01994 // ----------------------------------------------------------------------- 01995 template<typename OsModel_P, 01996 typename RoutingTable_P, 01997 typename Clock_P, 01998 typename Radio_P, 01999 typename Debug_P> 02000 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_dup_tuple* 02001 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02002 find_dup_tuple(node_id_t addr, uint16_t seq_num) 02003 { 02004 for (typename dupset_t::iterator it = dupset_.begin(); it != dupset_.end(); it++) 02005 { 02006 OLSR_dup_tuple* tuple = *it; 02007 if (tuple->addr() == addr && tuple->seq_num() == seq_num) 02008 return tuple; 02009 } 02010 02011 return NULL; 02012 } 02013 02014 // ----------------------------------------------------------------------- 02015 template<typename OsModel_P, 02016 typename RoutingTable_P, 02017 typename Clock_P, 02018 typename Radio_P, 02019 typename Debug_P> 02020 void 02021 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02022 rm_dup_tuple(OLSR_dup_tuple* tuple) 02023 { 02024 erase_dup_tuple(tuple); 02025 } 02026 // ----------------------------------------------------------------------- 02027 02028 template<typename OsModel_P, 02029 typename RoutingTable_P, 02030 typename Clock_P, 02031 typename Radio_P, 02032 typename Debug_P> 02033 void 02034 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02035 erase_dup_tuple(OLSR_dup_tuple* tuple) 02036 { 02037 for (typename dupset_t::iterator it = dupset_.begin(); it != dupset_.end(); it++) 02038 { 02039 if (*it == tuple) 02040 { 02041 dupset_.erase(it); 02042 break; 02043 } 02044 } 02045 } 02046 02047 // ----------------------------------------------------------------------- 02048 02049 template<typename OsModel_P, 02050 typename RoutingTable_P, 02051 typename Clock_P, 02052 typename Radio_P, 02053 typename Debug_P> 02054 void 02055 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02056 insert_dup_tuple(OLSR_dup_tuple* tuple) 02057 { 02058 dupset_.push_back(tuple); 02059 } 02060 02061 // ----------------------------------------------------------------------- 02062 // brief Adds a link tuple to the Link Set (and an associated neighbor tuple to the Neighbor Set). 02063 // param tuple the link tuple to be added. 02064 // param willingness willingness of the node which is going to be inserted in the Neighbor Set. 02065 02066 template<typename OsModel_P, 02067 typename RoutingTable_P, 02068 typename Clock_P, 02069 typename Radio_P, 02070 typename Debug_P> 02071 void 02072 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02073 add_link_tuple(OLSR_link_tuple* tuple, uint8_t willingness) 02074 { 02075 time_t now = Clock::time( os() ); 02076 02077 #ifdef DEBUG_OLSRROUTING 02078 Debug::debug(os(), "%f: Node %d adds link tuple: nb_addr = %d\n", now, Radio::id(os()), tuple->nb_node_addr()); 02079 #endif 02080 02081 insert_link_tuple(tuple); 02082 // Creates associated neighbor tuple 02083 OLSR_nb_tuple* nb_tuple = new OLSR_nb_tuple; 02084 nb_tuple->nb_node_addr() = tuple->nb_node_addr(); 02085 nb_tuple->willingness() = willingness; 02086 if (tuple->sym_time() >= now) 02087 nb_tuple->status() = OLSR_STATUS_SYM; 02088 else 02089 nb_tuple->status() = OLSR_STATUS_NOT_SYM; 02090 add_nb_tuple(nb_tuple); 02091 } 02092 // ----------------------------------------------------------------------- 02093 // brief Removes a link tuple from the Link Set. 02094 // param tuple the link tuple to be removed. 02095 02096 template<typename OsModel_P, 02097 typename RoutingTable_P, 02098 typename Clock_P, 02099 typename Radio_P, 02100 typename Debug_P> 02101 void 02102 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02103 rm_link_tuple(OLSR_link_tuple* tuple) 02104 { 02105 node_id_t nb_addr = tuple->nb_node_addr(); 02106 time_t now = Clock::time( os() ); 02107 02108 #ifdef DEBUG_OLSRROUTING 02109 Debug::debug(os(), "%f: Node %d removes neighbor tuple: nb_addr = %d\n", now, Radio::id(os()), nb_addr); 02110 #endif 02111 02112 erase_link_tuple(tuple); 02113 02114 OLSR_nb_tuple* nb_tuple = find_nb_tuple(nb_addr); 02115 erase_nb_tuple(nb_tuple); 02116 delete nb_tuple; 02117 } 02118 // ----------------------------------------------------------------------- 02119 // brief This function is invoked when a link tuple is updated. Its aim is to also update the corresponding neighbor tuple if it is needed. 02120 // param tuple the link tuple which has been updated. 02121 02122 template<typename OsModel_P, 02123 typename RoutingTable_P, 02124 typename Clock_P, 02125 typename Radio_P, 02126 typename Debug_P> 02127 void 02128 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02129 updated_link_tuple(OLSR_link_tuple* tuple) 02130 { 02131 time_t now = Clock::time( os() ); 02132 02133 // Each time a link tuple changes, the associated neighbor tuple must be recomputed, basically the "nb_tuple->status" should be updated 02134 OLSR_nb_tuple* nb_tuple = find_nb_tuple(tuple->nb_node_addr()); 02135 if (nb_tuple != NULL) { 02136 if (tuple->lost_time() >= now) 02137 nb_tuple->status() = OLSR_STATUS_NOT_SYM; 02138 else if (tuple->sym_time() >= now) 02139 nb_tuple->status() = OLSR_STATUS_SYM; 02140 else 02141 nb_tuple->status() = OLSR_STATUS_NOT_SYM; 02142 } 02143 02144 #ifdef DEBUG_OLSRROUTING 02145 Debug::debug(os(), "%f: Node %d has updated link tuple: nb_addr = %d status = %s\n", now, Radio::id(os()), tuple->nb_node_addr(), 02146 ((nb_tuple->status() == OLSR_STATUS_SYM) ? "sym" : "not_sym")); 02147 #endif 02148 } 02149 // ----------------------------------------------------------------------- 02150 02151 template<typename OsModel_P, 02152 typename RoutingTable_P, 02153 typename Clock_P, 02154 typename Radio_P, 02155 typename Debug_P> 02156 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_link_tuple * 02157 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02158 find_link_tuple(node_id_t node_addr) 02159 { 02160 for (typename linkset_t::iterator it = linkset_.begin(); it != linkset_.end(); it++) 02161 { 02162 OLSR_link_tuple* tuple = *it; 02163 if (tuple->nb_node_addr() == node_addr) 02164 { 02165 #ifdef DEBUG_OLSRROUTING 02166 Debug::debug(os(), "Find existing tuple!!!\n"); 02167 #endif 02168 return tuple; 02169 } 02170 else 02171 { 02172 #ifdef DEBUG_OLSRROUTING 02173 Debug::debug(os(), "NO existing tuple!!!\n"); 02174 #endif 02175 return NULL; 02176 } 02177 } 02178 } 02179 02180 // ----------------------------------------------------------------------- 02181 02182 template<typename OsModel_P, 02183 typename RoutingTable_P, 02184 typename Clock_P, 02185 typename Radio_P, 02186 typename Debug_P> 02187 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_link_tuple * 02188 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02189 find_sym_link_tuple(node_id_t node_addr, double now) 02190 { 02191 02192 for (typename linkset_t::iterator it = linkset_.begin(); it != linkset_.end(); it++) 02193 { 02194 OLSR_link_tuple* tuple = *it; 02195 if (tuple->nb_node_addr() == node_addr) 02196 { 02197 if (tuple->sym_time() > now) 02198 return tuple; 02199 else 02200 break; 02201 } 02202 } 02203 return NULL; 02204 } 02205 02206 // ----------------------------------------------------------------------- 02207 02208 template<typename OsModel_P, 02209 typename RoutingTable_P, 02210 typename Clock_P, 02211 typename Radio_P, 02212 typename Debug_P> 02213 void 02214 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02215 erase_link_tuple(OLSR_link_tuple* tuple) 02216 { 02217 for (typename linkset_t::iterator it = linkset_.begin(); it != linkset_.end(); it++) 02218 { 02219 if (*it == tuple) 02220 { 02221 linkset_.erase(it); 02222 break; 02223 } 02224 } 02225 } 02226 02227 // ----------------------------------------------------------------------- 02228 02229 template<typename OsModel_P, 02230 typename RoutingTable_P, 02231 typename Clock_P, 02232 typename Radio_P, 02233 typename Debug_P> 02234 void 02235 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02236 insert_link_tuple(OLSR_link_tuple* tuple) 02237 { 02238 linkset_.push_back(tuple); 02239 } 02240 // ----------------------------------------------------------------------- 02241 02242 02243 // brief Adds a neighbor tuple to the Neighbor Set. 02244 // param tuple the neighbor tuple to be added. 02245 02246 template<typename OsModel_P, 02247 typename RoutingTable_P, 02248 typename Clock_P, 02249 typename Radio_P, 02250 typename Debug_P> 02251 void 02252 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02253 add_nb_tuple(OLSR_nb_tuple* tuple) 02254 { 02255 #ifdef DEBUG_OLSRROUTING 02256 Debug::debug(os(), "%f: Node %d adds neighbor tuple: nb_addr = %d status = %s\n", Clock::time( os() ), Radio::id(os()), tuple->nb_node_addr(), 02257 ((tuple->status() == OLSR_STATUS_SYM) ? "sym" : "not_sym")); 02258 #endif 02259 02260 insert_nb_tuple(tuple); 02261 } 02262 // ----------------------------------------------------------------------- 02263 // brief Removes a neighbor tuple from the Neighbor Set. 02264 // param tuple the neighbor tuple to be removed. 02265 02266 template<typename OsModel_P, 02267 typename RoutingTable_P, 02268 typename Clock_P, 02269 typename Radio_P, 02270 typename Debug_P> 02271 void 02272 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02273 rm_nb_tuple(OLSR_nb_tuple* tuple) 02274 { 02275 #ifdef DEBUG_OLSRROUTING 02276 Debug::debug( "%f: Node %d removes neighbor tuple: nb_addr = %d status = %s\n", Clock::time( os() ), 02277 Radio::id(os()), 02278 tuple->nb_node_addr(), 02279 ((tuple->status() == OLSR_STATUS_SYM) ? "sym" : "not_sym") ); 02280 #endif 02281 02282 erase_nb_tuple(tuple); 02283 } 02284 // ----------------------------------------------------------------------- 02285 template<typename OsModel_P, 02286 typename RoutingTable_P, 02287 typename Clock_P, 02288 typename Radio_P, 02289 typename Debug_P> 02290 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_nb_tuple * 02291 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02292 find_nb_tuple(node_id_t node_addr) // find a neighbor with NO SPECIFIC requirement 02293 { 02294 for (typename nbset_t::iterator it = nbset_.begin(); it != nbset_.end(); it++) 02295 { 02296 OLSR_nb_tuple* tuple = *it; 02297 if (tuple->nb_node_addr() == node_addr) 02298 return tuple; 02299 } 02300 return NULL; 02301 } 02302 02303 // ----------------------------------------------------------------------- 02304 template<typename OsModel_P, 02305 typename RoutingTable_P, 02306 typename Clock_P, 02307 typename Radio_P, 02308 typename Debug_P> 02309 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_nb_tuple* 02310 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02311 find_nb_tuple(node_id_t node_addr, uint8_t willingness) // find a neighbor with certain WILLNESS requirement 02312 { 02313 for (typename nbset_t::iterator it = nbset_.begin(); it != nbset_.end(); it++) 02314 { 02315 OLSR_nb_tuple* tuple = *it; 02316 if (tuple->nb_node_addr() == node_addr && tuple->willingness() == willingness) 02317 return tuple; 02318 } 02319 return NULL; 02320 } 02321 02322 // ----------------------------------------------------------------------- 02323 template<typename OsModel_P, 02324 typename RoutingTable_P, 02325 typename Clock_P, 02326 typename Radio_P, 02327 typename Debug_P> 02328 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_nb_tuple* 02329 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02330 find_sym_nb_tuple(node_id_t node_addr) // find a neighbor with certain SYMMETRIC requirement 02331 { 02332 for (typename nbset_t::iterator it = nbset_.begin(); it != nbset_.end(); it++) 02333 { 02334 OLSR_nb_tuple* tuple = *it; 02335 if (tuple->nb_node_addr() == node_addr && tuple->status() == OLSR_STATUS_SYM) 02336 return tuple; 02337 } 02338 return NULL; 02339 } 02340 02341 // ----------------------------------------------------------------------- 02342 template<typename OsModel_P, 02343 typename RoutingTable_P, 02344 typename Clock_P, 02345 typename Radio_P, 02346 typename Debug_P> 02347 void 02348 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02349 erase_nb_tuple(OLSR_nb_tuple* tuple) 02350 { 02351 for (typename nbset_t::iterator it = nbset_.begin(); it != nbset_.end(); it++) 02352 { 02353 if (*it == tuple) { 02354 nbset_.erase(it); 02355 break; 02356 } 02357 } 02358 } 02359 02360 // ----------------------------------------------------------------------- 02361 template<typename OsModel_P, 02362 typename RoutingTable_P, 02363 typename Clock_P, 02364 typename Radio_P, 02365 typename Debug_P> 02366 void 02367 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02368 insert_nb_tuple(OLSR_nb_tuple* tuple) 02369 { 02370 nbset_.push_back(tuple); 02371 } 02372 02373 // ----------------------------------------------------------------------- 02374 02375 // brief Adds a 2-hop neighbor tuple to the 2-hop Neighbor Set. 02376 // param tuple the 2-hop neighbor tuple to be added. 02377 02378 template<typename OsModel_P, 02379 typename RoutingTable_P, 02380 typename Clock_P, 02381 typename Radio_P, 02382 typename Debug_P> 02383 void 02384 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02385 add_nb2hop_tuple(OLSR_nb2hop_tuple* tuple) 02386 { 02387 #ifdef DEBUG_OLSRROUTING 02388 Debug::debug(os(), "%f: Node %d adds 2-hop neighbor tuple: nb_addr = %d nb2hop_addr = %d\n", Clock::time( os() ), Radio::id(os()), 02389 tuple->nb_node_addr(), tuple->nb2hop_addr()); 02390 #endif 02391 02392 insert_nb2hop_tuple(tuple); 02393 } 02394 // ----------------------------------------------------------------------- 02395 // brief Removes a 2-hop neighbor tuple from the 2-hop Neighbor Set. 02396 // param tuple the 2-hop neighbor tuple to be removed. 02397 02398 template<typename OsModel_P, 02399 typename RoutingTable_P, 02400 typename Clock_P, 02401 typename Radio_P, 02402 typename Debug_P> 02403 void 02404 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02405 rm_nb2hop_tuple(OLSR_nb2hop_tuple* tuple) { 02406 #ifdef DEBUG_OLSRROUTING 02407 Debug::debug(os(), "%f: Node %d removes 2-hop neighbor tuple: nb_addr = %d nb2hop_addr = %d\n", Clock::time( os() ), Radio::id(os()), 02408 tuple->nb_node_addr(), tuple->nb2hop_addr()); 02409 #endif 02410 02411 erase_nb2hop_tuple(tuple); 02412 } 02413 // ----------------------------------------------------------------------- 02414 02415 template<typename OsModel_P, 02416 typename RoutingTable_P, 02417 typename Clock_P, 02418 typename Radio_P, 02419 typename Debug_P> 02420 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_nb2hop_tuple * 02421 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02422 find_nb2hop_tuple(node_id_t nb_node_addr, node_id_t nb2hop_addr) 02423 { 02424 for (typename nb2hopset_t::iterator it = nb2hopset_.begin(); it != nb2hopset_.end(); it++) 02425 { 02426 OLSR_nb2hop_tuple* tuple = *it; 02427 if (tuple->nb_node_addr() == nb_node_addr && tuple->nb2hop_addr() == nb2hop_addr) 02428 return tuple; 02429 } 02430 return NULL; 02431 } 02432 02433 // ----------------------------------------------------------------------- 02434 02435 template<typename OsModel_P, 02436 typename RoutingTable_P, 02437 typename Clock_P, 02438 typename Radio_P, 02439 typename Debug_P> 02440 void 02441 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02442 erase_nb2hop_tuple(OLSR_nb2hop_tuple* tuple) 02443 { 02444 for (typename nb2hopset_t::iterator it = nb2hopset_.begin(); it != nb2hopset_.end(); it++) 02445 { 02446 if (*it == tuple) 02447 { 02448 nb2hopset_.erase(it); 02449 break; 02450 } 02451 } 02452 } 02453 // ----------------------------------------------------------------------- 02454 02455 template<typename OsModel_P, 02456 typename RoutingTable_P, 02457 typename Clock_P, 02458 typename Radio_P, 02459 typename Debug_P> 02460 void 02461 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02462 erase_nb2hop_tuples(node_id_t nb_node_addr) 02463 { 02464 for (typename nb2hopset_t::iterator it = nb2hopset_.begin(); it != nb2hopset_.end(); it++) 02465 { 02466 OLSR_nb2hop_tuple* tuple = *it; 02467 if (tuple->nb_node_addr() == nb_node_addr) 02468 { 02469 it = nb2hopset_.erase(it); 02470 it--; 02471 } 02472 } 02473 } 02474 // ----------------------------------------------------------------------- 02475 02476 template<typename OsModel_P, 02477 typename RoutingTable_P, 02478 typename Clock_P, 02479 typename Radio_P, 02480 typename Debug_P> 02481 void 02482 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02483 erase_nb2hop_tuples(node_id_t nb_node_addr, node_id_t nb2hop_addr) 02484 { 02485 for (typename nb2hopset_t::iterator it = nb2hopset_.begin(); it != nb2hopset_.end(); it++) 02486 { 02487 OLSR_nb2hop_tuple* tuple = *it; 02488 if (tuple->nb_node_addr() == nb_node_addr && tuple->nb2hop_addr() == nb2hop_addr) 02489 { 02490 it = nb2hopset_.erase(it); 02491 it--; 02492 } 02493 } 02494 } 02495 // ----------------------------------------------------------------------- 02496 02497 template<typename OsModel_P, 02498 typename RoutingTable_P, 02499 typename Clock_P, 02500 typename Radio_P, 02501 typename Debug_P> 02502 void 02503 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02504 insert_nb2hop_tuple(OLSR_nb2hop_tuple* tuple) 02505 { 02506 nb2hopset_.push_back(tuple); 02507 } 02508 02509 // ----------------------------------------------------------------------- 02510 // brief Adds an MPR selector tuple to the MPR Selector Set, Advertised Neighbor Sequence Number (ANSN) is also updated. 02511 // param tuple the MPR selector tuple to be added. 02512 02513 template<typename OsModel_P, 02514 typename RoutingTable_P, 02515 typename Clock_P, 02516 typename Radio_P, 02517 typename Debug_P> 02518 void 02519 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02520 add_mprsel_tuple(OLSR_mprsel_tuple* tuple) { 02521 #ifdef DEBUG_OLSRROUTING 02522 Debug::debug(os(), "%f: Node %d adds MPR selector tuple: nb_addr = %d\n", Clock::time( os() ), Radio::id(os()), tuple->node_addr() ); 02523 #endif 02524 02525 insert_mprsel_tuple(tuple); 02526 ansn_ = (ansn_ + 1)%(OLSR_MAX_SEQ_NUM + 1); 02527 } 02528 // ----------------------------------------------------------------------- 02529 // brief Removes an MPR selector tuple from the MPR Selector Set, Advertised Neighbor Sequence Number (ANSN) is also updated. 02530 // param tuple the MPR selector tuple to be removed. 02531 02532 template<typename OsModel_P, 02533 typename RoutingTable_P, 02534 typename Clock_P, 02535 typename Radio_P, 02536 typename Debug_P> 02537 void 02538 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02539 rm_mprsel_tuple(OLSR_mprsel_tuple* tuple) { 02540 #ifdef DEBUG_OLSRROUTING 02541 Debug::debug(os(), "%f: Node %d removes MPR selector tuple: nb_addr = %d\n", Clock::time( os() ), Radio::id(os()), tuple->node_addr() ); 02542 #endif 02543 02544 erase_mprsel_tuple(tuple); 02545 ansn_ = (ansn_ + 1)%(OLSR_MAX_SEQ_NUM + 1); 02546 } 02547 // ----------------------------------------------------------------------- 02548 02549 template<typename OsModel_P, 02550 typename RoutingTable_P, 02551 typename Clock_P, 02552 typename Radio_P, 02553 typename Debug_P> 02554 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_mprsel_tuple * 02555 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02556 find_mprsel_tuple(node_id_t node_addr) { 02557 for (typename mprselset_t::iterator it = mprselset_.begin(); it != mprselset_.end(); it++) 02558 { 02559 OLSR_mprsel_tuple* tuple = *it; 02560 if (tuple->node_addr() == node_addr) 02561 return tuple; 02562 } 02563 return NULL; 02564 } 02565 // ----------------------------------------------------------------------- 02566 template<typename OsModel_P, 02567 typename RoutingTable_P, 02568 typename Clock_P, 02569 typename Radio_P, 02570 typename Debug_P> 02571 void 02572 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02573 erase_mprsel_tuple(OLSR_mprsel_tuple* tuple) 02574 { 02575 for (typename mprselset_t::iterator it = mprselset_.begin(); it != mprselset_.end(); it++) 02576 { 02577 if (*it == tuple) 02578 { 02579 mprselset_.erase(it); 02580 break; 02581 } 02582 } 02583 } 02584 // ----------------------------------------------------------------------- 02585 template<typename OsModel_P, 02586 typename RoutingTable_P, 02587 typename Clock_P, 02588 typename Radio_P, 02589 typename Debug_P> 02590 void 02591 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02592 erase_mprsel_tuples(node_id_t node_addr) 02593 { 02594 for (typename mprselset_t::iterator it = mprselset_.begin(); it != mprselset_.end(); it++) 02595 { 02596 OLSR_mprsel_tuple* tuple = *it; 02597 if (tuple->node_addr() == node_addr) { 02598 it = mprselset_.erase(it); 02599 it--; 02600 } 02601 } 02602 } 02603 // ----------------------------------------------------------------------- 02604 template<typename OsModel_P, 02605 typename RoutingTable_P, 02606 typename Clock_P, 02607 typename Radio_P, 02608 typename Debug_P> 02609 void 02610 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02611 insert_mprsel_tuple(OLSR_mprsel_tuple* tuple) 02612 { 02613 mprselset_.push_back(tuple); 02614 } 02615 02616 // ----------------------------------------------------------------------- 02617 // brief Adds a topology tuple to the Topology Set. 02618 02619 // param tuple the topology tuple to be added. 02620 02621 template<typename OsModel_P, 02622 typename RoutingTable_P, 02623 typename Clock_P, 02624 typename Radio_P, 02625 typename Debug_P> 02626 void 02627 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02628 add_topology_tuple(OLSR_topology_tuple* tuple) 02629 { 02630 #ifdef DEBUG_OLSRROUTING 02631 Debug::debug(os(), "%f: Node %d adds topology tuple: dest_addr = %d last_addr = %d seq = %d\n", 02632 Clock::time( os() ), 02633 Radio::id(os()), 02634 tuple->dest_addr(), 02635 tuple->last_addr(), 02636 tuple->seq() ); 02637 #endif 02638 02639 insert_topology_tuple(tuple); 02640 } 02641 // ----------------------------------------------------------------------- 02642 // brief Removes a topology tuple from the Topology Set. 02643 02644 // param tuple the topology tuple to be removed. 02645 02646 template<typename OsModel_P, 02647 typename RoutingTable_P, 02648 typename Clock_P, 02649 typename Radio_P, 02650 typename Debug_P> 02651 void 02652 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02653 rm_topology_tuple(OLSR_topology_tuple* tuple) 02654 { 02655 #ifdef DEBUG_OLSRROUTING 02656 Debug::debug(os(), "%f: Node %d removes topology tuple: dest_addr = %d last_addr = %d seq = %d\n", 02657 Clock::time( os() ), 02658 Radio::id(os()), 02659 tuple->dest_addr(), 02660 tuple->last_addr(), 02661 tuple->seq() ); 02662 #endif 02663 02664 erase_topology_tuple(tuple); 02665 } 02666 // ----------------------------------------------------------------------- 02667 02668 template<typename OsModel_P, 02669 typename RoutingTable_P, 02670 typename Clock_P, 02671 typename Radio_P, 02672 typename Debug_P> 02673 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_topology_tuple * 02674 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02675 find_topology_tuple(node_id_t dest_addr, node_id_t last_addr) 02676 { 02677 for (typename topologyset_t::iterator it = topologyset_.begin(); it != topologyset_.end(); it++) 02678 { 02679 OLSR_topology_tuple* tuple = *it; 02680 if (tuple->dest_addr() == dest_addr && tuple->last_addr() == last_addr) 02681 return tuple; 02682 } 02683 return NULL; 02684 } 02685 // ----------------------------------------------------------------------- 02686 02687 template<typename OsModel_P, 02688 typename RoutingTable_P, 02689 typename Clock_P, 02690 typename Radio_P, 02691 typename Debug_P> 02692 class OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>::OLSR_topology_tuple * 02693 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02694 find_newer_topology_tuple(node_id_t last_addr, u_int16_t ansn) 02695 { 02696 for (typename topologyset_t::iterator it = topologyset_.begin(); it != topologyset_.end(); it++) 02697 { 02698 OLSR_topology_tuple* tuple = *it; 02699 if (tuple->last_addr() == last_addr && tuple->seq() > ansn) 02700 return tuple; 02701 } 02702 return NULL; 02703 } 02704 // ----------------------------------------------------------------------- 02705 template<typename OsModel_P, 02706 typename RoutingTable_P, 02707 typename Clock_P, 02708 typename Radio_P, 02709 typename Debug_P> 02710 void 02711 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02712 erase_topology_tuple(OLSR_topology_tuple* tuple) 02713 { 02714 for (typename topologyset_t::iterator it = topologyset_.begin(); it != topologyset_.end(); it++) 02715 { 02716 if (*it == tuple) 02717 { 02718 topologyset_.erase(it); 02719 break; 02720 } 02721 } 02722 } 02723 // ----------------------------------------------------------------------- 02724 template<typename OsModel_P, 02725 typename RoutingTable_P, 02726 typename Clock_P, 02727 typename Radio_P, 02728 typename Debug_P> 02729 void 02730 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02731 erase_older_topology_tuples(node_id_t last_addr, uint16_t ansn) 02732 { 02733 for (typename topologyset_t::iterator it = topologyset_.begin(); it != topologyset_.end(); it++) 02734 { 02735 OLSR_topology_tuple* tuple = *it; 02736 if (tuple->last_addr() == last_addr && tuple->seq() < ansn) 02737 { 02738 it = topologyset_.erase(it); 02739 it--; 02740 } 02741 } 02742 } 02743 // ----------------------------------------------------------------------- 02744 template<typename OsModel_P, 02745 typename RoutingTable_P, 02746 typename Clock_P, 02747 typename Radio_P, 02748 typename Debug_P> 02749 void 02750 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02751 insert_topology_tuple(OLSR_topology_tuple* tuple) 02752 { 02753 topologyset_.push_back(tuple); 02754 } 02755 // ----------------------------------------------------------------------- 02756 template<typename OsModel_P, 02757 typename RoutingTable_P, 02758 typename Clock_P, 02759 typename Radio_P, 02760 typename Debug_P> 02761 bool 02762 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02763 route_exists(node_id_t destination) 02764 { 02765 RoutingTableIterator it = routing_table_.find(destination); 02766 if (it != routing_table_.end()) 02767 { 02768 return true; 02769 } 02770 else 02771 return false; 02772 } 02773 02774 // ----------------------------------------------------------------------- 02775 template<typename OsModel_P, 02776 typename RoutingTable_P, 02777 typename Clock_P, 02778 typename Radio_P, 02779 typename Debug_P> 02780 void 02781 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02782 print_routing_table( RoutingTable rt ) 02783 { 02784 #ifdef DEBUG_OLSRROUTING 02785 int i = 0; 02786 Debug::debug( os(), "OlsrRouting: Routing Table:\n" ); 02787 Debug::debug( os(), "+++++++++++++++++++++++++++++++++++++++++++++++++\n" ); 02788 02789 if (!rt.size()) 02790 { 02791 Debug::debug( os(), "| Routing Table is empty!!! |\n" ); 02792 } 02793 else 02794 { 02795 for ( RoutingTableIterator it = rt.begin(); it != rt.end(); ++it ) 02796 { 02797 Debug::debug( os(), "| RoutingTable[%i]: Dest %i SendTo %i Hops %i |\n", i++, it->first, it->second.next_addr, it->second.hops ); 02798 } 02799 } 02800 02801 Debug::debug( os(), "+++++++++++++++++++++++++++++++++++++++++++++++++\n" ); 02802 #endif 02803 } 02804 02805 // ----------------------------------------------------------------------- 02806 template<typename OsModel_P, 02807 typename RoutingTable_P, 02808 typename Clock_P, 02809 typename Radio_P, 02810 typename Debug_P> 02811 int 02812 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02813 degree(OLSR_nb_tuple* tuple) 02814 { 02815 int degree = 0; 02816 for (typename nb2hopset_t::iterator it = nb2hopset().begin(); it != nb2hopset().end(); it++) 02817 { 02818 OLSR_nb2hop_tuple* nb2hop_tuple = *it; 02819 if (nb2hop_tuple->nb_node_addr() == tuple->nb_node_addr()) 02820 { 02821 OLSR_nb_tuple* nb_tuple = find_nb_tuple(nb2hop_tuple->nb_node_addr()); 02822 if (nb_tuple == NULL) 02823 degree++; 02824 } 02825 } 02826 02827 return degree; 02828 } 02829 02830 // ----------------------------------------------------------------------- 02831 template<typename OsModel_P, 02832 typename RoutingTable_P, 02833 typename Clock_P, 02834 typename Radio_P, 02835 typename Debug_P> 02836 double 02837 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02838 emf_to_seconds(uint8_t olsr_format) 02839 { 02840 // This implementation has been taken from unik-olsrd-0.4.5 (mantissa.c), licensed under the GNU Public License (GPL) 02841 int a = olsr_format >> 4; 02842 int b = olsr_format - a*16; 02843 return (double)(OLSR_C*(1+(double)a/16)*(double)pow(2,b)); 02844 } 02845 02846 // ----------------------------------------------------------------------- 02847 template<typename OsModel_P, 02848 typename RoutingTable_P, 02849 typename Clock_P, 02850 typename Radio_P, 02851 typename Debug_P> 02852 uint8_t 02853 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02854 seconds_to_emf(double seconds) 02855 { 02856 // This implementation has been taken from unik-olsrd-0.4.5 (mantissa.c), licensed under the GNU Public License (GPL) 02857 int a, b = 0; 02858 while (seconds/OLSR_C >= pow((double)2, (double)b)) 02859 b++; 02860 b--; 02861 02862 if (b < 0) { 02863 a = 1; 02864 b = 0; 02865 } 02866 else if (b > 15) { 02867 a = 15; 02868 b = 15; 02869 } 02870 else { 02871 a = (int)(16*((double)seconds/(OLSR_C*(double)pow(2, b))-1)); 02872 while (a >= 16) { 02873 a -= 16; 02874 b++; 02875 } 02876 } 02877 02878 return (uint8_t)(a*16+b); 02879 } 02880 02881 // ----------------------------------------------------------------------- 02882 template<typename OsModel_P, 02883 typename RoutingTable_P, 02884 typename Clock_P, 02885 typename Radio_P, 02886 typename Debug_P> 02887 void 02888 OlsrRouting<OsModel_P, RoutingTable_P, Clock_P, Radio_P, Debug_P>:: 02889 nb_loss(OLSR_link_tuple* tuple) 02890 { 02891 #ifdef DEBUG_OLSRROUTING 02892 Debug::debug(os(), "%f: Node %d detects neighbor %d loss\n", Clock::time( os() ), Radio::id(os()), tuple->nb_node_addr()); 02893 #endif 02894 02895 updated_link_tuple(tuple); 02896 erase_nb2hop_tuples(tuple->nb_node_addr()); 02897 erase_mprsel_tuples(tuple->nb_node_addr()); 02898 02899 mpr_computation(); 02900 routing_table_computation(); 02901 } 02902 02903 // ----------------------------------------------------------------------- 02904 02905 02906 } 02907 #endif
