aodv_mcast.cc

MAODV代码和安装程序 hen nan找啊

#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