aodv.txt

aodv路由协议源码及简单注释 格式没有转换

/usr/src/other/ns-allinone-2.27/ns_orig/aodv/aodv.cc

00032 

00033 //#include <ip.h>

00034 

00035 #include <aodv/aodv.h>

00036 #include <aodv/aodv_packet.h>

00037 #include <random.h>

00038 #include <cmu-trace.h>

00039 //#include <energy-model.h>

00040 

00041 #define max(a,b)        ( (a) > (b) ? (a) : (b) )

00042 #define CURRENT_TIME    Scheduler::instance().clock()

00043 

00044 //#define DEBUG

00045 //#define ERROR

00046 

00047 #ifdef DEBUG

00048 static int extra_route_reply = 0;

00049 static int limit_route_request = 0;

00050 static int route_request = 0;

00051 #endif

00052 

00053 

00054 /*

00055   TCL Hooks

00056 */

00057 

00058 

00059 int hdr_aodv::offset_;

00060 static class AODVHeaderClass : public PacketHeaderClass {

00061 public:

00062         AODVHeaderClass() : PacketHeaderClass("PacketHeader/AODV",

00063                                               sizeof(hdr_all_aodv)) {

00064           bind_offset(&hdr_aodv::offset_);

00065         } 

00066 } class_rtProtoAODV_hdr;

00067 

00068 static class AODVclass : public TclClass {

00069 public:

00070         AODVclass() : TclClass("Agent/AODV") {}

00071         TclObject* create(int argc, const char*const* argv) {

00072           assert(argc == 5);

00073           //return (new AODV((nsaddr_t) atoi(argv[4])));

00074           return (new AODV((nsaddr_t) Address::instance().str2addr(argv[4])));

00075         }

00076 } class_rtProtoAODV;

00077 

00078 

00079 int

00080 AODV::command(int argc, const char*const* argv) {

00081   if(argc == 2) {

00082   Tcl& tcl = Tcl::instance();

00083     

00084     if(strncasecmp(argv[1], "id", 2) == 0) {

00085       tcl.resultf("%d", index);

00086       return TCL_OK;

00087     }

00088     

00089     if(strncasecmp(argv[1], "start", 2) == 0) {   //初始化了所有的timer,除了localrepair

00090       btimer.handle((Event*) 0);

00091 

00092 #ifndef AODV_LINK_LAYER_DETECTION

00093       htimer.handle((Event*) 0);

00094       ntimer.handle((Event*) 0);

00095 #endif // LINK LAYER DETECTION

00096 

00097       rtimer.handle((Event*) 0);

00098       return TCL_OK;

00099      }               

00100   }

00101   else if(argc == 3) {

00102     if(strcmp(argv[1], "index") == 0) {

00103       index = atoi(argv[2]);

00104       return TCL_OK;

00105     }

00106 

00107     else if(strcmp(argv[1], "log-target") == 0 || strcmp(argv[1], "tracetarget") == 0) {

00108       logtarget = (Trace*) TclObject::lookup(argv[2]);

00109       if(logtarget == 0)

00110         return TCL_ERROR;

00111       return TCL_OK;

00112     }

00113     else if(strcmp(argv[1], "drop-target") == 0) {

00114     int stat = rqueue.command(argc,argv);

00115       if (stat != TCL_OK) return stat;

00116       return Agent::command(argc, argv);

00117     }

00118     else if(strcmp(argv[1], "if-queue") == 0) {

00119     ifqueue = (PriQueue*) TclObject::lookup(argv[2]);

00120       

00121       if(ifqueue == 0)

00122         return TCL_ERROR;

00123       return TCL_OK;

00124     }

00125     else if (strcmp(argv[1], "port-dmux") == 0) {
 
返回页顶      
00126         dmux_ = (PortClassifier *)TclObject::lookup(argv[2]);

00127         if (dmux_ == 0) {

00128                 fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__,

00129                 argv[1], argv[2]);

00130                 return TCL_ERROR;

00131         }

00132         return TCL_OK;

00133     }

00134   }

00135   return Agent::command(argc, argv);

00136 }

00137 

00138 /* 

00139    Constructor

00140 */

00141 

00142 AODV::AODV(nsaddr_t id) : Agent(PT_AODV),

00143                           btimer(this), htimer(this), ntimer(this), 

00144                           rtimer(this), lrtimer(this), rqueue() {

00145  

00146                 

00147   index = id;

00148   seqno = 2;

00149   bid = 1;

00150 

00151   LIST_INIT(&nbhead);   //初始化neighbor list

00152   LIST_INIT(&bihead);   //初始化broadcast id list

00153 

00154   logtarget = 0;

00155   ifqueue = 0;

00156 }

00157 

00158 /*

00159   Timers

00160 */

00161 

00162 void

00163 BroadcastTimer::handle(Event*) {

00164   agent->id_purge();

00165   Scheduler::instance().schedule(this, &intr, BCAST_ID_SAVE);

00166 }

00167 

00168 void

00169 HelloTimer::handle(Event*) {

00170    agent->sendHello();

00171    double interval = MinHelloInterval + 

00172                  ((MaxHelloInterval - MinHelloInterval) * Random::uniform());

00173    assert(interval >= 0);

00174    Scheduler::instance().schedule(this, &intr, interval);

00175 }

00176 

00177 void

00178 NeighborTimer::handle(Event*) {

00179   agent->nb_purge();

00180   Scheduler::instance().schedule(this, &intr, HELLO_INTERVAL);

00181 }

00182 

00183 void

00184 RouteCacheTimer::handle(Event*) {

00185   agent->rt_purge();

00186 #define FREQUENCY 0.5 // sec

00187   Scheduler::instance().schedule(this, &intr, FREQUENCY);

00188 }

00189 

00190 void

00191 LocalRepairTimer::handle(Event* p)  {  // SRD: 5/4/99

00192 aodv_rt_entry *rt;

00193 struct hdr_ip *ih = HDR_IP( (Packet *)p);

00194 

00195    /* you get here after the timeout in a local repair attempt */

00196    /*   fprintf(stderr, "%s\n", __FUNCTION__); */

00197 

00198 

00199     rt = agent->rtable.rt_lookup(ih->daddr());   //看routing table里有没有到目标节点的路由

00200         

00201     if (rt && rt->rt_flags != RTF_UP) {    //有且有效，也就是说路由等待repair

00202     // route is yet to be repaired

00203     // I will be conservative and bring down the route

00204     // and send route errors upstream.

00205     /* The following assert fails, not sure why */

00206     /* assert (rt->rt_flags == RTF_IN_REPAIR); */

00207                 

00208       //rt->rt_seqno++;              

00209       agent->rt_down(rt);      //调用rt_down(aodv_rt_entry *rt)函数，用以标志这条路由break down

00210       // send RERR

00211 #ifdef DEBUG

00212       fprintf(stderr,"Node %d: Dst - %d, failed local repair\n",index, rt->rt_dst);

00213 #endif      

00214     }

00215     Packet::free((Packet *)p);

00216 }

00217 

00218 

00219 /*

00220    Broadcast ID Management  Functions

00221 */

00222 

00223 

00224 void

00225 AODV::id_insert(nsaddr_t id, u_int32_t bid) {

00226 BroadcastID *b = new BroadcastID(id, bid);

00227 

00228  assert(b);

00229  b->expire = CURRENT_TIME + BCAST_ID_SAVE;

00230  LIST_INSERT_HEAD(&bihead, b, link);            //把新的id放在broadcast id list的头上

00231 }

00232 

00233 /* SRD */

00234 bool

00235 AODV::id_lookup(nsaddr_t id, u_int32_t bid) {

00236 BroadcastID *b = bihead.lh_first;

00237  

00238  // Search the list for a match of source and bid

00239  for( ; b; b = b->link.le_next) {

00240    if ((b->src == id) && (b->id == bid))    //看list里source的地址与id能不能对应？

00241      return true;     

00242  }

00243  return false;

00244 }

00245 

00246 void

00247 AODV::id_purge() {        //丢掉所有已经过期的id

00248 BroadcastID *b = bihead.lh_first;

00249 BroadcastID *bn;

00250 double now = CURRENT_TIME;

00251 

00252  for(; b; b = bn) {

00253    bn = b->link.le_next;

00254    if(b->expire <= now) {    //表示已经过期

00255      LIST_REMOVE(b,link);

00256      delete b;

00257    }

00258  }

00259 }

00260 

00261 /*

00262   Helper Functions    //不懂

00263 */

00264 

00265 double

00266 AODV::PerHopTime(aodv_rt_entry *rt) {

00267 int num_non_zero = 0, i;
00268 double total_latency = 0.0;

00269 

00270  if (!rt)

00271    return ((double) NODE_TRAVERSAL_TIME );

00272         

00273  for (i=0; i < MAX_HISTORY; i++) {

00274    if (rt->rt_disc_latency > 0.0) {

00275       num_non_zero++;

00276       total_latency += rt->rt_disc_latency;

00277    }

00278  }

00279  if (num_non_zero > 0)

00280    return(total_latency / (double) num_non_zero);

00281  else

00282    return((double) NODE_TRAVERSAL_TIME);

00283 

00284 }

00285 

00286 /*

00287   Link Failure Management Functions

00288 */

00289 

00290 static void

00291 aodv_rt_failed_callback(Packet *p, void *arg) {

00292   ((AODV*) arg)->rt_ll_failed(p);

00293 }

00294 

00295 /*

00296  * This routine is invoked when the link-layer reports a route failed.

00297  */

00298 void

00299 AODV::rt_ll_failed(Packet *p) {

00300 struct hdr_cmn *ch = HDR_CMN(p);

00301 struct hdr_ip *ih = HDR_IP(p);

00302 aodv_rt_entry *rt;

00303 nsaddr_t broken_nbr = ch->next_hop_;

00304 

00305 #ifndef AODV_LINK_LAYER_DETECTION

00306  drop(p, DROP_RTR_MAC_CALLBACK);

00307 #else 

00308 

00309  /*

00310   * Non-data packets and Broadcast Packets can be dropped.

00311   */

00312   if(! DATA_PACKET(ch->ptype()) ||   //non-data packet是TCP, TELNET,CBR,AUDIO,VIDEO,ACK,SCTP,SCTP_APP1

00313      (u_int32_t) ih->daddr() == IP_BROADCAST) {  //广播包

00314     drop(p, DROP_RTR_MAC_CALLBACK);

00315     return;

00316   }

00317   log_link_broke(p);  //记录路由broke

00318         if((rt = rtable.rt_lookup(ih->daddr())) == 0) {  //找不到路由

00319     drop(p, DROP_RTR_MAC_CALLBACK);   //丢弃

00320     return;

00321   }

00322   log_link_del(ch->next_hop_);  //记录路由被删除

00323 

00324 #ifdef AODV_LOCAL_REPAIR

00325   /* if the broken link is closer to the dest than source, 

00326      attempt a local repair. Otherwise, bring down the route. */

00327 

00328 

00329   if (ch->num_forwards() > rt->rt_hops) {                //forward的次数大，更靠近destination

00330     local_rt_repair(rt, p); // local repair            //call local_rt_repair

00331     // retrieve all the packets in the ifq using this link,

00332     // queue the packets for which local repair is done, 

00333     return;

00334   }

00335   else  

00336 #endif // LOCAL REPAIR  

00337 

00338   {

00339     drop(p, DROP_RTR_MAC_CALLBACK);

00340     // Do the same thing for other packets in the interface queue using the

00341     // broken link -Mahesh

00342 while((p = ifqueue->filter(broken_nbr))) {

00343      drop(p, DROP_RTR_MAC_CALLBACK);

00344     }   

00345     nb_delete(broken_nbr);

00346   }

00347 

00348 #endif // LINK LAYER DETECTION

00349 }

00350 

00351 void

00352 AODV::handle_link_failure(nsaddr_t id) {   //处理link failure

00353 aodv_rt_entry *rt, *rtn;

00354 Packet *rerr = Packet::alloc();

00355 struct hdr_aodv_error *re = HDR_AODV_ERROR(rerr);   //rerr

00356 

00357  re->DestCount = 0;       //先初始化不能到达的目标节点的个数为0

00358  for(rt = rtable.head(); rt; rt = rtn) {  // for each rt entry

00359    rtn = rt->rt_link.le_next;    //指向下一个路由表项

00360    if ((rt->rt_hops != INFINITY2) && (rt->rt_nexthop == id) ) { //如果当前路由还有效，并且下一跳是我自己？

00361      assert (rt->rt_flags == RTF_UP);

00362      assert((rt->rt_seqno%2) == 0);
00363      rt->rt_seqno++;        //强制设为无效

00364      re->unreachable_dst[re->DestCount] = rt->rt_dst;  //更新list的内容

00365      re->unreachable_dst_seqno[re->DestCount] = rt->rt_seqno;

00366 #ifdef DEBUG

00367      fprintf(stderr, "%s(%f): %d\t(%d\t%u\t%d)\n", __FUNCTION__, CURRENT_TIME,

00368                      index, re->unreachable_dst[re->DestCount],

00369                      re->unreachable_dst_seqno[re->DestCount], rt->rt_nexthop);