aodv.cc

在Linux下做的QuadTree的程序

void
AODV::recvAODV(Packet *p)
{
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv *ah = HDR_AODV(p);

        assert(ih->sport_ == RT_PORT);
        assert(ih->dport_ == RT_PORT);

        /*
         * Incoming Packets.
         */
        switch(ah->ah_type) {

        case AODVTYPE_HELLO:
                recvHello(p);
                break;

        case AODVTYPE_RREQ:
                recvRequest(p);
                break;

        case AODVTYPE_RREP:
        case AODVTYPE_UREP:
                recvReply(p);
                break;

        default:
                fprintf(stderr, "Invalid AODV type (%x)\n", ah->ah_type);
                exit(1);
        }
}


void
AODV::recvRequest(Packet *p)
{
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
        rt_entry *rt;

        /*
         * Drop if:
         *      - I'm the source
         *      - I recently heard this request.
         */
        if(rq->rq_src == index) {
#ifdef DEBUG
                fprintf(stderr, "%s: got my own REQUEST\n", __FUNCTION__);
#endif
                Packet::free(p);
                return;
        } 

        if(id_lookup(rq->rq_src) >= rq->rq_bcast_id) {
#ifdef DEBUG
                fprintf(stderr, "%s: discarding request\n", __FUNCTION__);
#endif
                Packet::free(p);
                return;
        }

        /*
         * Cache the ID
         */
        id_insert(rq->rq_src, rq->rq_bcast_id);

        rt = rtable.rt_lookup(rq->rq_dst);

        /* 
         * We are either going to forward the REQUEST or generate a
         * REPLY.  Make sure that the REVERSE route is in the Route
         * Cache.
         */
        { 
                rt_entry *rt0;

                rt0 = rtable.rt_lookup(rq->rq_src);
                if(rt0 == 0) {
                        rt0 = rtable.rt_add(rq->rq_src);
                }
                /*
                 * XXX - Am I doing the right thing if a route already exists?
                 */
                rt0->rt_seqno = rq->rq_src_seqno;
                rt0->rt_nexthop = ih->src_;
                rt0->rt_expire = CURRENT_TIME +
                        (rt && rt->rt_seqno > rq->rq_dst_seqno ?
                         ACTIVE_ROUTE_TIMEOUT : REV_ROUTE_LIFE);
                rt0->rt_hops = rq->rq_hop_count;
                rt0->rt_flags = RTF_UP;
        }

        /*
         * Send a Route Reply.
         */

        if(rq->rq_dst == index) {
#ifdef DEBUG
                fprintf(stderr, "%d - %s: destination sending reply\n",
                        index, __FUNCTION__);
#endif
                /*
                 * Actually, this is wrong and skews the route lengths
                 * used to the "high" side since Requests that take
                 * longer to reach the destination are replied to with
                 * a higher sequence number. 04/29/98 - josh
                 */
                seqno += 1;                     // Just to be safe...

                sendReply(rq->rq_src,           // IP Destination
                          1,                    // Hop Count
                          index,                // Dest IP Address
                          seqno,                // Dest Sequence Num
                          MY_ROUTE_TIMEOUT,     // Lifetime
                          rq->rq_timestamp);    // timestamp
                Packet::free(p);
        }
        else if(rt && rt->rt_seqno > rq->rq_dst_seqno) {
                sendReply(rq->rq_src,
                          rt->rt_hops + 1,
                          rq->rq_dst,
                          rt->rt_seqno,
                          (u_int32_t) (rt->rt_expire - CURRENT_TIME),
                          rq->rq_timestamp);
                Packet::free(p);
        }
        /*
         * Forward the  Route Request
         */
        else {
                ih->dst_ = IP_BROADCAST;
                ih->src_ = index;
                rq->rq_hop_count += 1;

                forward((rt_entry*) 0, p, 1 /* Jitter */);
        }
}


#ifdef COMMENT_ONLY
XXX - The forwarding of Route Replies as [not] specified in the draft,
completely breaks if normal IP-forwarding is used because you need to
know the IP Address of the node that you received the Reply from in
order to setup the "forward" route.

Rather than change the packet format as specified in the draft, I put
a "previous hop" field in the Route Reply so we know who sent it to
us.  -jorjeta
#endif


void
AODV::recvReply(Packet *p)
{
        struct hdr_cmn *ch = HDR_CMN(p);
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
        rt_entry *rt;

#ifdef DEBUG
        fprintf(stderr, "%d - %s: received a REPLY\n", index, __FUNCTION__);
#endif
        /*
         *  Got a reply so reset any state the "count" of Route Request
         *  packets sent.
         */
        if((rt = rtable.rt_lookup(rp->rp_dst))) {
                rt->rt_req_cnt = 0;
                rt->rt_req_timeout = 0.0;
        }

        /*
         *  Handle "Route Errors" separately...
         */
        if(rp->rp_hop_count == INFINITY) {
                recvTriggeredReply(p);
                return;
        }

        /*
         *  If I don't have a route to this host...
         */
        if(rt == 0) {
                rt = rtable.rt_add(rp->rp_dst);
        }

        /*
         * Add a forward route table entry...
         */
        if((rt->rt_flags & RTF_UP) == 0 ||              // better route
           (rt->rt_seqno < rp->rp_dst_seqno &&          // shorter route
            rt->rt_hops > rp->rp_hop_count)) {
                rt->rt_seqno = rp->rp_dst_seqno;
                rt->rt_nexthop = ch->prev_hop_;
                rt->rt_expire = rp->rp_lifetime;
                rt->rt_hops = rp->rp_hop_count;
                rt->rt_flags = RTF_UP;
#ifdef AODV_LINK_LAYER_DETECTION
                rt->rt_errors = 0;
                rt->rt_error_time = 0.0;
#endif
        }
#ifdef DEBUG
        else if(ih->dst_ == index) {
                fprintf(stderr,
                        "(%2d) %2d - Extra Route Reply, dst: %2d, turnaround: %f, hops: %d\n",
                        ++extra_route_reply,
                        index,
                        rp->rp_dst,
                        CURRENT_TIME - rp->rp_timestamp,
                        rt->rt_hops);
        }
#endif

        /*
         *  Reply was for me, discard it.
         */
        if(ih->dst_ == index) {
                Packet::free(p);
        }
        /*
         * Forward the Route Reply.
         */
        else {
                rt_entry *rt0 = rtable.rt_lookup(ih->dst_);

                if(rt0 && (rt0->rt_flags & RTF_UP)) {
                        rp->rp_hop_count += 1;
                        forward(rt0, p, 0 /* No Jitter */);
                }
                else {
#ifdef DEBUG
                        fprintf(stderr, "%s: droping Route Reply\n",
                                __FUNCTION__);
#endif
                        drop(p, DROP_RTR_NO_ROUTE);
                }
        }

        /*
         * Send all packets queued for the destination.
         * XXX - observe the "second" use of p.
         */
        while((p = rqueue.deque(rt->rt_dst))) {
                if(rt->rt_flags & RTF_UP) {
                        forward(rt, p, 1 /* Jitter */);
                }
                else {
                        drop(p, DROP_RTR_NO_ROUTE);
                }
        }
}


void
AODV::recvTriggeredReply(Packet *p)
{
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
        rt_entry *rt = rtable.rt_lookup(rp->rp_dst);

        if(rt && (rt->rt_flags & RTF_UP)) {
                /*
                 *  I belive the INFINITY metric if this node has a larger
                 *  sequence number or if the node is my next hop (since
                 *  he won't forward packets for me anyways).
                 */
                if(rt->rt_seqno <= rp->rp_dst_seqno || 
                   rt->rt_nexthop == ih->src_) {
                        /*
                         *  XXX - This could result in getting a lower sequence
                         *  number, but I don't think that this matters.
                         */
                        rt->rt_seqno = rp->rp_dst_seqno;
                        rt_down(rt);
                }
        }
        Packet::free(p);
}


void
AODV::recvHello(Packet *p)
{
        struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
        Neighbor *nb;

        /*
         *  XXX: I use a separate TYPE for hello messages rather than
         *  a bastardized Route Reply.
         */
        nb = nb_lookup(rp->rp_dst);
        if(nb == 0) {
                nb_insert(rp->rp_dst);
        }
        else {
                nb->nb_expire = CURRENT_TIME +
                        (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
        }
        Packet::free(p);
}


/* ======================================================================
   Packet Transmission Routines
   ===================================================================== */
void
AODV::forward(rt_entry *rt, Packet *p, int jitter)
{
        struct hdr_cmn *ch = HDR_CMN(p);
        struct hdr_ip *ih = HDR_IP(p);
        Neighbor *nb;

        if(ih->ttl_ == 0) {
#ifdef DEBUG
                fprintf(stderr, "%s: calling drop()\n", __PRETTY_FUNCTION__);
#endif
                drop(p, DROP_RTR_TTL);
                return;
        }

        /*
         * Keep the "official" Neighbor List up-to-date.
         */
        if((nb = nb_lookup(ch->prev_hop_)) == 0) {
                nb_insert(ch->prev_hop_);
        }

        if(rt) {
                assert(rt->rt_flags & RTF_UP);
                /*
                 *  Need to maintain the per-route Neighbor List.  This is
                 *  kept separate from the Neighbor list that is the list
                 *  of ACTIVE neighbors.  I don't bother to expire these
                 *  entries.
                 */
                if(rt->nb_lookup(ch->prev_hop_) == 0) {
                        rt->nb_insert(ch->prev_hop_);
                }

                rt->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT;
                ch->prev_hop_ = index;
                ch->next_hop_ = rt->rt_nexthop;
                ch->addr_type() = AF_INET;
        }
        else {
                assert(ch->ptype() == PT_AODV);
                assert(ih->dst_ == (nsaddr_t) IP_BROADCAST);
                ch->addr_type() = AF_NONE;
        }

        if(jitter) {
                /*
                 *  Jitter the sending of broadcast packets by 10ms
                 */
                Scheduler::instance().schedule(target_, p,
                                               0.01 * Random::uniform());
        }
        else {
                target_->recv(p, (Handler*) 0);
        }
}


void
AODV::sendRequest(nsaddr_t dst)
{
        Packet *p = Packet::alloc();
        struct hdr_cmn *ch = HDR_CMN(p);
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
        rt_entry *rt = rtable.rt_lookup(dst);

        assert(rt);

        /*
         *  Rate limit sending of Route Requests
         */
        if(rt->rt_req_cnt > RREQ_RETRIES ||
           rt->rt_req_timeout > CURRENT_TIME) {
#ifdef DEBUG
                fprintf(stderr, "(%2d) - %2d can't send Request, dst: %d\n",
                        ++limit_route_request, index, rt->rt_dst);
#endif
                return;
        }
#ifdef DEBUG
        fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d\n",
                ++route_request, index, rt->rt_dst);
#endif
        rt->rt_req_timeout = CURRENT_TIME + RREP_WAIT_TIME;
        rt->rt_req_cnt += 1;

        // ch->uid() = 0;
        ch->ptype() = PT_AODV;
        ch->size() = IP_HDR_LEN + sizeof(*rq);
        ch->iface() = -2;
        ch->error() = 0;
        ch->addr_type() = AF_NONE;
        ch->prev_hop_ = index;          // AODV hack

        ih->src_ = index;
        ih->dst_ = IP_BROADCAST;
        ih->sport_ = RT_PORT;
        ih->dport_ = RT_PORT;
        ih->ttl_ = IP_DEF_TTL;

        rq->rq_type = AODVTYPE_RREQ;
        rq->rq_hop_count = 0;
        rq->rq_bcast_id = bid++;
        rq->rq_dst = dst;
        rq->rq_dst_seqno = (rt ? rt->rt_seqno : 0);
        rq->rq_src = index;
        rq->rq_src_seqno = seqno;
        rq->rq_timestamp = CURRENT_TIME;

        target_->recv(p, (Handler*) 0);
}

void
AODV::sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst,
                u_int32_t rpseq, u_int32_t lifetime, double timestamp)
{
        Packet *p = Packet::alloc();
        struct hdr_cmn *ch = HDR_CMN(p);
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
        rt_entry *rt = rtable.rt_lookup(ipdst);

        assert(rt);

        // ch->uid() = 0;
        ch->ptype() = PT_AODV;
        ch->size() = IP_HDR_LEN + sizeof(*rp);
        ch->iface() = -2;
        ch->error() = 0;
        ch->addr_type() = AF_INET;
        ch->next_hop_ = rt->rt_nexthop;
        ch->prev_hop_ = index;          // AODV hack

        ih->src_ = index;
        ih->dst_ = ipdst;
        ih->sport_ = RT_PORT;
        ih->dport_ = RT_PORT;
        ih->ttl_ = IP_DEF_TTL;

        rp->rp_type = AODVTYPE_RREP;
        rp->rp_flags = 0x00;
        rp->rp_hop_count = hop_count;
        rp->rp_dst = rpdst;
        rp->rp_dst_seqno = rpseq;
        rp->rp_lifetime = lifetime;
        rp->rp_timestamp = timestamp;

        target_->recv(p, (Handler*) 0);     
}

void
AODV::sendTriggeredReply(nsaddr_t ipdst, nsaddr_t rpdst, u_int32_t rpseq)
{
	// 08/28/98 - added this extra check
	if(ipdst == 0 || ipdst == index) return;

        Packet *p = Packet::alloc();
        struct hdr_cmn *ch = HDR_CMN(p);
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);

        // ch->uid() = 0;
        ch->ptype() = PT_AODV;
        ch->size() = IP_HDR_LEN + sizeof(*rp);
        ch->iface() = -2;
        ch->error() = 0;
        ch->addr_type() = AF_NONE;
        ch->next_hop_ = 0;
        ch->prev_hop_ = index;          // AODV hack

        ih->src_ = index;
        ih->dst_ = ipdst;
        ih->sport_ = RT_PORT;
        ih->dport_ = RT_PORT;
        ih->ttl_ = 1;

        rp->rp_type = AODVTYPE_UREP;
        rp->rp_flags = 0x00;
        rp->rp_hop_count = INFINITY;
        rp->rp_dst = rpdst;
        rp->rp_dst_seqno = rpseq;
        rp->rp_lifetime = 0;            // XXX

        target_->recv(p, (Handler*) 0);     
}


void
AODV::sendHello()
{
        Packet *p = Packet::alloc();
        struct hdr_cmn *ch = HDR_CMN(p);
        struct hdr_ip *ih = HDR_IP(p);
        struct hdr_aodv_reply *rh = HDR_AODV_REPLY(p);

        // ch->uid() = 0;
        ch->ptype() = PT_AODV;
        ch->size() = IP_HDR_LEN + sizeof(*rh);
        ch->iface() = -2;
        ch->error() = 0;
        ch->addr_type() = AF_NONE;
        ch->prev_hop_ = index;          // AODV hack

        ih->src_ = index;
        ih->dst_ = IP_BROADCAST;
        ih->sport_ = RT_PORT;
        ih->dport_ = RT_PORT;
        ih->ttl_ = 1;

        rh->rp_type = AODVTYPE_HELLO;
        rh->rp_flags = 0x00;
        rh->rp_hop_count = 0;
        rh->rp_dst = index;
        rh->rp_dst_seqno = seqno;
        rh->rp_lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL;

        target_->recv(p, (Handler*) 0);
}