rreq.c

一种AODV实现方法

/*
               Kernel AODV  v2.0
National Institute of Standards and Technology
               Luke Klein-Berndt
-----------------------------------------------------
  Version 2.0 new features:
     * Updated to AODV draft version 11
     * Managed internet gatewaying
     * Monitor wireles signal strength
     * Many bug fixes!
-----------------------------------------------------

Originally based upon MadHoc code. I am not
sure how much of it is left anymore, but MadHoc
proved to be a great starting point.

MadHoc was written by - Fredrik Lilieblad,
Oskar Mattsson, Petra Nylund, Dan Ouchterlony
and Anders Roxenhag Mail: [e-mail]

This software is Open Source under the GNU General Public Licence.

*/

#include "rreq.h"
/****************************************************

   rreq
----------------------------------------------------
Handles the generation of RREQ and recieving
****************************************************/

extern u_int32_t g_broadcast_ip;
extern struct route_table_entry *g_my_entry;


void convert_rreq_to_host(struct rreq *tmp_rreq)
{
    tmp_rreq->rreq_id=ntohl(tmp_rreq->rreq_id);
    tmp_rreq->dst_seq=ntohl(tmp_rreq->dst_seq);
    tmp_rreq->src_seq=ntohl(tmp_rreq->src_seq);
}

void convert_rreq_to_network(struct rreq *tmp_rreq)
{
    tmp_rreq->rreq_id=htonl(tmp_rreq->rreq_id);
    tmp_rreq->dst_seq=htonl(tmp_rreq->dst_seq);
    tmp_rreq->src_seq=htonl(tmp_rreq->src_seq);
}



/****************************************************

   recv_rreq
----------------------------------------------------
Handles the recieving of RREQs
****************************************************/
int recv_rreq(struct event_queue_entry *working_packet)
{
    struct rreq *working_rreq;
    struct interface_list_entry *tmp_interface;
    struct rreq       *out_rreq;  /* Forwarded RREQ */
    struct route_table_entry   *tmp_entry;       /* Routing table entry */
    struct rreq_id_queue_entry *tmp_rreq_id;
    u_int64_t          current_time;  /* Current time */
    int size_out;

    /* Update the hop count */
#ifdef MESSAGES
    char src_ip[16];
    char dst_ip[16];
#endif


    working_rreq=working_packet->data;
    convert_rreq_to_host(working_rreq);

    //find what interface the packet was recived on
    tmp_interface=find_interface_by_dev(working_packet->dev);

    if (tmp_interface==NULL)
    {
	#ifdef MESSAGES
        printk ("RECV_RREQ: Recieved on a RREQ from an unrecognized interface.\n");
	#endif
        return 1;
    }


#ifdef TRACE
    printk("REC_RREQ: Entered");
#endif

#ifdef TRACE
    strcpy(src_ip,inet_ntoa(working_rreq->src_ip));
    strcpy(dst_ip,inet_ntoa(working_rreq->dst_ip));
    printk("RREQ: Recieved a RREQ -  src: %s dst: %s \n",src_ip,dst_ip);
#endif

    /* Look in the route request list to see if the node has
       already received this request. */
    tmp_rreq_id = find_rreq_id_queue_entry(working_rreq->src_ip, working_rreq->rreq_id);

    current_time = getcurrtime(); /* Get the current time */

    /* Check if an entry in the route request list was found, and if it's
       still valid. If there is a valid entry, this request shouldn't be
       checked. */
    if (tmp_rreq_id != NULL)   // && (check_rreq_id_queue_entry_lifetime(tmp_rreq_id)==0))
    {
        return 0;
    }

    /* Have not received this RREQ within BCAST_ID_SAVE time */

    /* Add this RREQ to the list for further checks */

    if (insert_rreq_id_queue_entry(working_rreq->src_ip, working_rreq->dst_ip,working_rreq->rreq_id, current_time + PATH_TRAVERSAL_TIME) == 1)
    {
        /* Couldn't add the entry, ignore and continue */
    }
    working_rreq->hop_count=working_rreq->hop_count+1;

    /* UPDATE REVERSE */

    update_route_entry(working_rreq->src_ip,  working_packet->src_ip, working_rreq->hop_count, working_rreq->dst_seq, working_packet->dev);

#ifdef TRACE
    printk("updated reverse route!\n");
#endif

    tmp_entry = find_route_table_entry(working_rreq->dst_ip);


    if ((working_rreq->dst_ip == tmp_interface->ip) ||
            (tmp_entry != NULL && tmp_entry->route_valid && tmp_entry->route_seq_valid) )
    {

        if (working_rreq->u || seq_less_or_equal(working_rreq->dst_seq,tmp_entry->dst_seq ))
            /* The node already had a valid route to the destination */
        {
            if (!working_rreq->d || (find_interface_by_ip(working_rreq->dst_ip)!=NULL))
            {


                //If the RREQ is addressed to us and we have the same Seq as the RREQ we up our Seq by one
                if ((find_interface_by_ip(working_rreq->dst_ip)!=NULL) && (working_rreq->dst_seq==tmp_entry->dst_seq))
                {
                    tmp_entry->dst_seq++;
                }

#ifdef MESSAGES
                strcpy(src_ip,inet_ntoa(working_rreq->src_ip));
                strcpy(dst_ip,inet_ntoa(working_rreq->dst_ip));
                printk("RREQ: Generating RREP -  src: %s dst: %s \n",src_ip,dst_ip);
#endif

                /* Call for gen_rrep to send a Route Reply */


                gen_rrep(working_rreq->src_ip,working_rreq->dst_ip,working_packet->src_ip,working_rreq->dst_seq,working_rreq->g);

#ifdef TRACE
                printk("REC_RREQ:  for me - exited");
#endif

                return 0;
            }
        }
    }
    /* The node didn't have a valid route to the destination */

    if ((working_packet->ttl) <=1)
    {
#ifdef TRACE
        printk("REC_RREQ: No valid route and TTL too small to forward - exited");
#endif
        return 0;
    }

#ifdef TRACE
    strcpy(src_ip,inet_ntoa(working_rreq->src_ip));
    strcpy(dst_ip,inet_ntoa(working_rreq->dst_ip));
    printk("RREQ: Forwarding a RREQ -  ttl: %d src: %s dst: %s  \n",working_packet->ttl,src_ip,dst_ip);
#endif


    if ((out_rreq = (struct rreq*) kmalloc(sizeof (struct rreq),GFP_ATOMIC)) == NULL)
    {
			#ifdef MESSAGES
        printk("RREQ: Error creating a new RREQ\n");
			#endif

        /* Failed to allocate memory for forwarded RREQ */
        return 1;
    }
    size_out=sizeof(struct rreq);

    /* Set the RREQ structure */
    out_rreq->type = 1;
    out_rreq->j = working_rreq->j;
    out_rreq->r = working_rreq->r;
    out_rreq->g = working_rreq->g;
    out_rreq->d = working_rreq->d;
    out_rreq->u = working_rreq->u;
    out_rreq->reserved = 0;
    out_rreq->hop_count = working_rreq->hop_count;
    out_rreq->dst_ip = working_rreq->dst_ip;
    out_rreq->src_ip = working_rreq->src_ip;

    //we want it to be network byte order
    out_rreq->src_seq = htonl(working_rreq->src_seq);
    out_rreq->rreq_id = htonl(working_rreq->rreq_id);

    /* Set the right sequence number */
    if (tmp_entry!=NULL)
    {
        if (seq_greater(working_rreq->dst_seq, tmp_entry->dst_seq))
            out_rreq->dst_seq=htonl(working_rreq->dst_seq);
        else
            out_rreq->dst_seq=htonl(tmp_entry->dst_seq);
    }
    else
        out_rreq->dst_seq = htonl(working_rreq->dst_seq);


    /* Set the destination IP to broadcast */
#ifdef TRACE
    printk("constructed out RREQ!\n");
#endif

    /* Call send_datagram to send and forward the RREQ */
    local_broadcast(working_packet->ttl-1, out_rreq, sizeof(struct rreq));

#ifdef TRACE
    printk("REC_RREQ: Unkown route - exited");
#endif

    kfree(out_rreq);

    return 0;
}



/****************************************************

   gen_rreq
----------------------------------------------------
Generates a RREQ! wahhooo!
****************************************************/
int gen_rreq(u_int32_t src_ip, u_int32_t dst_ip)
{
    struct route_table_entry *tmp_entry;
    struct rreq *out_rreq, *timer_rreq;
    u_int8_t  out_ttl;

#ifdef TRACE
    printk("REC_RREQ: Entered\n");
#endif


    /* Do not send rreq to the same host again if its already in the timer queue */

    if (find_first_timer_queue_entry_of_id_and_flag(dst_ip,EVENT_RREQ) != NULL)
        return 0;

    /* Allocate memory for the rreq message */


    if ((out_rreq = (struct rreq*) kmalloc(sizeof(struct rreq),GFP_ATOMIC)) == NULL)
    {
#ifndef NO_ERROR
        printk("GEN_RREQ: Can't allocate new rreq\n");
#endif
        return 1;
    }

    /* Allocate memory for the timer queue position for the rreq */

    if ((timer_rreq = kmalloc(sizeof(struct rreq),GFP_ATOMIC))==NULL)
    {
#ifndef NO_ERROR
        printk("GEN_RREQ: Can't allocate for a new timer queue position\n");
#endif
        /* Couldn't allocate memory */
        return 1;
    }

    /* Get routing table entry for destination */
    tmp_entry = find_route_table_entry(dst_ip);


    if (tmp_entry == NULL)
    {
        /* Entry does not exist -> set to initial values*/
        out_rreq->dst_seq = 0;
        out_rreq->u = TRUE;
        out_ttl =  TTL_START;
    }
    else
    {
        /* Entry does exist -> get value from rt */
        out_rreq->dst_seq = htonl(tmp_entry->dst_seq);
        if (tmp_entry->route_seq_valid)
        {
            out_rreq->u=FALSE;
        }
        else
        {
            out_rreq->u=TRUE;
        }
        out_ttl =  tmp_entry->hop_count + TTL_INCREMENT;
    }

    /* Get routing table entry for source, when this is ourself this one should allways exist*/

    tmp_entry = (find_interface_by_ip(src_ip))->route_entry;

    if (tmp_entry == NULL)
    {

#ifndef NO_ERROR
        printk("GEN_RREQ: Can't get route to self\n");
#endif
        return 1;
    }

    /* Get our own sequence number */
    (tmp_entry->rreq_id)++;
    tmp_entry->dst_seq=tmp_entry->dst_seq+1;
    out_rreq->src_seq = htonl(tmp_entry->dst_seq);
    out_rreq->rreq_id = htonl(tmp_entry->rreq_id);

    /* Fill in the package */
    out_rreq->dst_ip = dst_ip;
    out_rreq->src_ip = src_ip;
    out_rreq->type = 1;
    out_rreq->hop_count = htonl(0);
    out_rreq->j = 0;
    out_rreq->r = 0;
    out_rreq->d = 0;
    out_rreq->reserved = 0;
    out_rreq->second_reserved = 0;
    out_rreq->g=1;

    /* Get the broadcast address and ttl right */

    if (insert_rreq_id_queue_entry(out_rreq->src_ip, out_rreq->dst_ip,out_rreq->rreq_id, getcurrtime() + 2* out_ttl * NODE_TRAVERSAL_TIME) == 1)
    {
#ifndef NO_ERROR
        printk("GEN_RREQ: Can't add to broadcast list\n");
#endif
        return 1;
    }

    memcpy(timer_rreq,out_rreq,sizeof(struct rreq));

    insert_timer_queue_entry(getcurrtime() + NET_TRAVERSAL_TIME,timer_rreq, sizeof(struct rreq),out_rreq->dst_ip,0,out_ttl, EVENT_RREQ);
    update_timer_queue();

    local_broadcast(out_ttl,out_rreq,sizeof(struct rreq));

    kfree(out_rreq);

    #ifdef TRACE
    printk("GEN_RREQ: Exited\n");
#endif

    return 0;
}