#include <aodv/aodv.h>#include <aodv/aodv_packet.h>#include <ip.h>#include <random.h>#include <cmu-trace.h>#define max(a,b)        ( (a) > (b) ? (a) : (b) )/****************************************************************/// Timer to keep fresh packet ids/****************************************************************/void PacketTimer::handle(Event *e){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    agent->pid_purge();    Scheduler::instance().schedule(this, &intr, BCAST_ID_SAVE);}void AODV::pid_insert(nsaddr_t addr, u_int32_t pid){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    PacketID *b = new PacketID(addr, pid);    assert(b);    b->expire = CURRENT_TIME + BCAST_ID_SAVE;    LIST_INSERT_HEAD(&pihead, b, plink);}bool AODV::pid_lookup(nsaddr_t addr, u_int32_t pid){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    PacketID *b = pihead.lh_first;    for( ; b; b = b->plink.le_next) {        if ((b->src == addr) && (b->id == pid))            return true;    }    return false;}void AODV::pid_purge(){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    PacketID *b = pihead.lh_first;    PacketID *bn;    double now = CURRENT_TIME;    for(; b; b = bn) {        bn = b->plink.le_next;        if(b->expire <= now) {            LIST_REMOVE(b,plink);            delete b;        }    }}/**************************************************************/// periodically checking if there is any branch should be pruned/**************************************************************/void PruneTimer::handle(Event* e){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    Packet *p = (Packet *)e;    struct hdr_ip *ih = HDR_IP(p);    agent->mt_prune(ih->daddr());    Packet::free(p);}void AODV::mt_prune(nsaddr_t dst){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    aodv_mt_entry *mt = mtable.mt_lookup(dst);    if (mt && mt->mt_node_status == ON_TREE && mt->mt_nexthops.downstream() == NULL){        if (mt->mt_keep_on_tree_timeout > CURRENT_TIME) setPruneTimer(mt);        else {                aodv_nh_entry *nh = mt->mt_nexthops.upstream();            if (nh){                sendMACT(mt->mt_dst, MACT_P, 0, nh->next_hop);                mt->mt_nexthops.remove(nh);            }            downMT(mt);        }    }}/**************************************************************/// periodically broadcasting group hello throughout the network/*************************************************************/void GroupHelloTimer::handle(Event* e){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    agent->sendMGRPH();    Scheduler::instance().schedule(this, &intr,        0.9*GROUP_HELLO_INTERVAL + 0.2*GROUP_HELLO_INTERVAL*Random::uniform());}void AODV::sendMGRPH(){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    aodv_mt_entry *mt;    for( mt = mtable.head(); mt; mt = mt->mt_link.le_next){        if (mt->mt_grp_leader_addr == index &&  mt->mt_grp_merge_timeout <= CURRENT_TIME){             if (mt->mt_hops_grp_leader != 0){                printf("******ERROR: %.9f in %s, node %i is group leader for group %d, BUT HOP COUNT IS NOT 0!\n",                    CURRENT_TIME, __FUNCTION__, index, mt->mt_dst);                exit(1);            }            if (mt->mt_nexthops.upstream() != NULL){                printf("******ERROR: %.9f in %s,  node %i is group leader for group %d, BUT IT HAS UPSTEAM!\n",                    CURRENT_TIME, __FUNCTION__, index, mt->mt_dst);                exit(1);            }            Packet *p = Packet::alloc();            struct hdr_cmn *ch = HDR_CMN(p);            struct hdr_ip *ih = HDR_IP(p);            struct hdr_aodv_grph *gh = HDR_AODV_GRPH(p);            gh->gh_type = AODVTYPE_GRPH;            gh->gh_flags = GRPH_NO_FLAG;            gh->gh_hop_count = 0;            gh->gh_grp_leader_addr = index;            gh->gh_multi_grp_addr = mt->mt_dst;            mt->mt_seqno ++;            gh->gh_grp_seqno = mt->mt_seqno;            ch->ptype() = PT_AODV;            ch->size() = IP_HDR_LEN + gh->size();            ch->iface() = -2;            ch->error() = 0;            ch->addr_type() = NS_AF_NONE;            ch->prev_hop_ = index;            ch->next_hop_ = MAC_BROADCAST;            ch->direction() = hdr_cmn::DOWN;		            ih->saddr() = index;            ih->daddr() = IP_BROADCAST;            ih->sport() = RT_PORT;            ih->dport() = RT_PORT;            ih->ttl_ = NETWORK_DIAMETER;                        id_insert(gh->gh_multi_grp_addr + gh->gh_grp_leader_addr, gh->gh_grp_seqno);            controlNextHello();            Scheduler::instance().schedule(target_, p, 0.01 * Random::uniform());        }    }}/******************************************************************/// receive GROUP HELLO and rebroadcast// in order to find partitioned tree/*****************************************************************/void AODV::recvMGRPH(Packet *p){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    struct hdr_aodv_grph *gh = HDR_AODV_GRPH(p);    struct hdr_ip *ih = HDR_IP(p);    struct hdr_cmn *ch = HDR_CMN(p);    // exclude GRPH_U    if (gh->gh_flags == GRPH_U){recvMGRPH_U(p); return;}    // hop count +1    gh->gh_hop_count ++;    // 1. not-on-tree node forward the msg    // 2. tree member:    //  2.1 if not knowing grp leader, discard the msg    //  2.2 if with same grp leader, must receive the msg from its upstream, then forward it;     //      otherwise, discard it    //  2.2 if with different grp leader:    //    a) if with bigger grp leader, discard the msg    //    b) if with smaller grp leader, initiate Reqeust, discard the msg    //       RREQ_R to its own grp leader if it has valid upstream    //       RREQ_JR if it is the grp leader and has not permitted other node to request merge    aodv_mt_entry *mt = mtable.mt_lookup(gh->gh_multi_grp_addr);    if (mt == NULL || mt->mt_node_status == NOT_ON_TREE ||        mt->mt_grp_leader_addr == INFINITY8 ||        mt->mt_grp_leader_addr != gh->gh_grp_leader_addr){                // only handle the first received msg        if (id_lookup(gh->gh_multi_grp_addr + gh->gh_grp_leader_addr, gh->gh_grp_seqno))            { Packet::free(p);  return;}        id_insert(gh->gh_multi_grp_addr + gh->gh_grp_leader_addr, gh->gh_grp_seqno);        // update grp leader table entry        aodv_glt_entry *glt = gltable.glt_lookup(gh->gh_multi_grp_addr);        if (glt == NULL) glt = gltable.glt_add(gh->gh_multi_grp_addr);        if ((glt->glt_expire <= CURRENT_TIME)            || (glt->glt_grp_leader_addr < gh->gh_grp_leader_addr)        ){            glt->glt_grp_leader_addr = gh->gh_grp_leader_addr;            glt->glt_next_hop = ch->prev_hop_;            glt->glt_expire = CURRENT_TIME + GROUP_HELLO_INTERVAL;        }                if (mt == NULL || mt->mt_node_status == NOT_ON_TREE){            gh->gh_flags == GRPH_M;            mt_forward(p, DELAY);        }        else if (mt->mt_grp_leader_addr == INFINITY8) Packet::free(p);        else {            if (mt->mt_grp_leader_addr < gh->gh_grp_leader_addr &&                glt->glt_grp_leader_addr == gh->gh_grp_leader_addr){                if (mt->mt_grp_leader_addr == index){                    if (mt->mt_grp_merge_timeout < CURRENT_TIME){                        mt->mt_grp_merge_permission = index;                        mt->mt_grp_merge_timeout = CURRENT_TIME + GROUP_HELLO_INTERVAL;                        sendMRQ(mt, RREQ_JR);                    }                }                else if (mt->mt_nexthops.upstream()){                    sendMRQ(mt, RREQ_R);                }            }            Packet::free(p);        }    }                else { // tree member and mt->mt_grp_leader_addr == gh->gh_grp_leader_addr        aodv_nh_entry *nh = mt->mt_nexthops.upstream();        nsaddr_t up_node;        if (gh->gh_flags == GRPH_NO_FLAG &&             nh && nh->next_hop == ch->prev_hop_ &&            mt->mt_seqno <= gh->gh_grp_seqno){            // only handle the first received msg            if (id_lookup(gh->gh_multi_grp_addr + gh->gh_grp_leader_addr, gh->gh_grp_seqno))                { Packet::free(p);  return;}            id_insert(gh->gh_multi_grp_addr + gh->gh_grp_leader_addr, gh->gh_grp_seqno);            // update grp leader table entry            aodv_glt_entry *glt = gltable.glt_lookup(gh->gh_multi_grp_addr);            if (glt == NULL) glt = gltable.glt_add(gh->gh_multi_grp_addr);            if ((glt->glt_expire <= CURRENT_TIME)                  || (glt->glt_grp_leader_addr < gh->gh_grp_leader_addr)            ){                glt->glt_grp_leader_addr = gh->gh_grp_leader_addr;                glt->glt_next_hop = ch->prev_hop_;                glt->glt_expire = CURRENT_TIME + GROUP_HELLO_INTERVAL;            }                        mt->mt_seqno = gh->gh_grp_seqno;            mt->mt_hops_grp_leader = gh->gh_hop_count;            mt_forward(p, DELAY);        }        else Packet::free(p);    }}/******************************************************************/// when there is a change about group leader info,// the corresponding node must send out GRPH_U to its downstream nodes/*****************************************************************/void AODV::sendMGRPH_U(aodv_mt_entry *mt, nsaddr_t next_hop){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    // before entering, make sure the node has valid upstream node or it is the grp leader        Packet *p = Packet::alloc();    struct hdr_cmn *ch = HDR_CMN(p);    struct hdr_ip *ih = HDR_IP(p);    struct hdr_aodv_grph *gh = HDR_AODV_GRPH(p);    gh->gh_type = AODVTYPE_GRPH;    gh->gh_flags = GRPH_U;    gh->gh_hop_count = mt->mt_hops_grp_leader;    gh->gh_grp_leader_addr = mt->mt_grp_leader_addr;    gh->gh_multi_grp_addr = mt->mt_dst;    gh->gh_grp_seqno = mt->mt_seqno;    ch->ptype() = PT_AODV;    ch->size() = IP_HDR_LEN + gh->size();    ch->iface() = -2;    ch->error() = 0;    ch->addr_type() = NS_AF_NONE;    ch->prev_hop_ = index;    ch->next_hop_ = MAC_BROADCAST;    ch->direction() = hdr_cmn::DOWN;		    ih->saddr() = index;    ih->daddr() = mt->mt_dst;    ih->sport() = RT_PORT;    ih->dport() = RT_PORT;    ih->ttl_ = NETWORK_DIAMETER;    if (next_hop == INFINITY8){        u_int8_t size = mt->mt_nexthops.size();        if ((mt->mt_grp_leader_addr == index && size == 1)||            (mt->mt_grp_leader_addr != index && size == 2)){            aodv_nh_entry *nh = mt->mt_nexthops.downstream();            ch->next_hop_ = nh->next_hop;            ch->addr_type() = NS_AF_INET;        }        else controlNextHello();    }    else {         ch->next_hop_ = next_hop;         ch->addr_type() = NS_AF_INET;    }              Scheduler::instance().schedule(target_, p, 0.01 * Random::uniform());}/******************************************************************/// receive GRPH_U and rebroadcast// only propagate from upstream to downstream/*****************************************************************/void AODV::recvMGRPH_U(Packet *p){#ifdef DEBUG    fprintf(stdout,"%s, node %i at %.9f\n", __FUNCTION__, index, CURRENT_TIME);#endif    struct hdr_aodv_grph *gh = HDR_AODV_GRPH(p);    struct hdr_ip *ih = HDR_IP(p);    struct hdr_cmn *ch = HDR_CMN(p);    // hop count +1    gh->gh_hop_count ++;    // must be on tree node and receive msg from its upstream    aodv_mt_entry *mt = mtable.mt_lookup(gh->gh_multi_grp_addr);    if (mt == NULL || mt->mt_node_status == NOT_ON_TREE)        { Packet::free(p); return; }    aodv_nh_entry *nh = mt->mt_nexthops.lookup(ch->prev_hop_);    if (nh == NULL || nh->enabled_flag != NH_ENABLE || nh->link_direction != NH_UPSTREAM){        if (nh && nh->enabled_flag != NH_ENABLE) mt->mt_nexthops.remove(nh);        Packet::free(p);        return;    }    // if the recorded mt is good, no need to forward further    if (mt->mt_grp_leader_addr == gh->gh_grp_leader_addr &&        (mt->mt_seqno > gh->gh_grp_seqno ||         (mt->mt_seqno == gh->gh_grp_seqno &&          mt->mt_hops_grp_leader == gh->gh_hop_count))){        Packet::free(p);        return;    }    // severe error    if (index == gh->gh_grp_leader_addr){        printf("ERROR: %.9f in %s, grp leader %d receives msg from its own upstream %d\n",                CURRENT_TIME, __FUNCTION__, index, ch->prev_hop_);        Packet::free(p);        exit(1);    }    // severe warning