杂文

AODV结构分析

目录

部分描述由 ChatGPT 3.5 生成，代码为手动查找。

AODV（Ad-hoc On-demand Distance Vector）是一种自适应的距离向量路由协议，常用于无线自组网中。以下是 AODV 协议的实现中一些比较重要的函数和数据结构及其定义：

  1. struct rt_table：AODV 路由表的结构体，定义于 routing_table.h，包含以下字段：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* Route table entries */
struct rt_table {
    list_t l;
    struct in_addr dest_addr;	/* IP address of the destination */
    u_int32_t dest_seqno;
    unsigned int ifindex;	/* Network interface index... */
    struct in_addr next_hop;	/* IP address of the next hop to the dest */
    u_int8_t hcnt;		/* Distance (in hops) to the destination */
    u_int16_t flags;		/* Routing flags */
    u_int8_t state;		/* The state of this entry */
    struct timer rt_timer;	/* The timer associated with this entry */
    struct timer ack_timer;	/* RREP_ack timer for this destination */
    struct timer hello_timer;
    struct timeval last_hello_time;
    u_int8_t hello_cnt;
    hash_value hash;
    int nprec;			/* Number of precursors */
    list_t precursors;		/* List of neighbors using the route */
};

  1. rt_table_t rt_table_find(structin_addrdest_addr)：查找 AODV 路由表中与给定目标地址匹配的路由表项。如果找到，返回指向该路由表项的指针；否则返回 NULL。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
rt_table_t *NS_CLASS rt_table_find(struct in_addr dest_addr)
{
	hash_value hash;
	unsigned int index;
	list_t *pos;

	if (rt_tbl.num_entries == 0)
		return NULL;

	/* Calculate index */
	index = hashing(&dest_addr, &hash);

	/* Handle collisions: */
	list_foreach(pos, &rt_tbl.tbl[index]) {
		rt_table_t *rt = (rt_table_t *) pos;

		if (rt->hash != hash)
			continue;

		if (memcmp(&dest_addr, &rt->dest_addr, sizeof(struct in_addr))
		    == 0)
			return rt;

	}
	return NULL;
}
  1. rt_table_update(rt_table_t * rt, struct in_addr next, u_int8_t hops, u_int32_t seqno, u_int32_t lifetime, u_int8_t state, u_int16_t flags)：AODV 路由表项的输入处理函数，用于更新路由表项。当 AODV 节点收到一个数据包时，会调用此函数更新路由表项。如果该路由表项不存在，会创建新的路由表项并添加到路由表中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
rt_table_t *NS_CLASS rt_table_update(rt_table_t * rt, struct in_addr next,
				     u_int8_t hops, u_int32_t seqno,
				     u_int32_t lifetime, u_int8_t state,
				     u_int16_t flags)
{
	struct in_addr nm;
	nm.s_addr = 0;

	if (rt->state == INVALID && state == VALID) {

		/* If this previously was an expired route, but will now be
		   active again we must add it to the kernel routing
		   table... */
		rt_tbl.num_active++;

		if (rt->flags & RT_REPAIR)
			flags &= ~RT_REPAIR;

#ifndef NS_PORT
		nl_send_add_route_msg(rt->dest_addr, next, hops, lifetime,
				      flags, rt->ifindex);
#endif

	} else if (rt->next_hop.s_addr != 0 &&
		   rt->next_hop.s_addr != next.s_addr) {

		DEBUG(LOG_INFO, 0, "rt->next_hop=%s, new_next_hop=%s",
		      ip_to_str(rt->next_hop), ip_to_str(next));

#ifndef NS_PORT
		nl_send_add_route_msg(rt->dest_addr, next, hops, lifetime,
				      flags, rt->ifindex);
#endif
	}

	if (hops > 1 && rt->hcnt == 1) {
		rt->last_hello_time.tv_sec = 0;
		rt->last_hello_time.tv_usec = 0;
		rt->hello_cnt = 0;
		timer_remove(&rt->hello_timer);
		/* Must also do a "link break" when updating a 1 hop
		neighbor in case another routing entry use this as
		next hop... */
		neighbor_link_break(rt);
	}

	rt->flags = flags;
	rt->dest_seqno = seqno;
	rt->next_hop = next;
	rt->hcnt = hops;

#ifdef CONFIG_GATEWAY
	if (rt->flags & RT_GATEWAY)
		rt_table_update_inet_rt(rt, lifetime);
#endif

//#ifdef NS_PORT
	rt->rt_timer.handler = &NS_CLASS route_expire_timeout;

	if (!(rt->flags & RT_INET_DEST))
		rt_table_update_timeout(rt, lifetime);
//#endif

	/* Finally, mark as VALID */
	rt->state = state;

	/* In case there are buffered packets for this destination, we send
	 * them on the new route. */
	if (rt->state == VALID
	    && seek_list_remove(seek_list_find(rt->dest_addr))) {
#ifdef NS_PORT
		if (rt->flags & RT_INET_DEST)
			packet_queue_set_verdict(rt->dest_addr, PQ_ENC_SEND);
		else
			packet_queue_set_verdict(rt->dest_addr, PQ_SEND);
#endif
	}
	return rt;
}

以上是一些维护底层路由表的重要函数和结构体。可以通过将这些函数进一步封装为更加抽象的接口，便于调用。

  1. hello_send(void *arg)：发送 hello 消息的函数，定义于 aodv_hello.c，用于检测邻居节点的存在。每个 AODV 节点定期发送 hello 消息，以便发现邻居节点的变化，并将变化更新到路由表中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
void NS_CLASS hello_send(void *arg)
{
    RREP *rrep;
    AODV_ext *ext = NULL;
    u_int8_t flags = 0;
    struct in_addr dest;
    long time_diff, jitter;
    struct timeval now;
    int msg_size = RREP_SIZE;
    int i;

    gettimeofday(&now, NULL);

    if (optimized_hellos &&
	timeval_diff(&now, &this_host.fwd_time) > ACTIVE_ROUTE_TIMEOUT) {
	hello_stop();
	return;
    }

    time_diff = timeval_diff(&now, &this_host.bcast_time);
    jitter = hello_jitter();

    /* This check will ensure we don't send unnecessary hello msgs, in case
       we have sent other bcast msgs within HELLO_INTERVAL */
    if (time_diff >= HELLO_INTERVAL) {

	for (i = 0; i < MAX_NR_INTERFACES; i++) {
	    if (!DEV_NR(i).enabled)
		continue;
#ifdef DEBUG_HELLO
	    DEBUG(LOG_DEBUG, 0, "sending Hello to 255.255.255.255");
#endif
	    rrep = rrep_create(flags, 0, 0, DEV_NR(i).ipaddr,
			       this_host.seqno,
			       DEV_NR(i).ipaddr,
			       ALLOWED_HELLO_LOSS * HELLO_INTERVAL);

	    /* Assemble a RREP extension which contain our neighbor set... */
	    if (unidir_hack) {
		int i;

		if (ext)
		    ext = AODV_EXT_NEXT(ext);
		else
		    ext = (AODV_ext *) ((char *) rrep + RREP_SIZE);

		ext->type = RREP_HELLO_NEIGHBOR_SET_EXT;
		ext->length = 0;

		for (i = 0; i < RT_TABLESIZE; i++) {
		    list_t *pos;
		    list_foreach(pos, &rt_tbl.tbl[i]) {
			rt_table_t *rt = (rt_table_t *) pos;
			/* If an entry has an active hello timer, we assume
			   that we are receiving hello messages from that
			   node... */
			if (rt->hello_timer.used) {
#ifdef DEBUG_HELLO
			    DEBUG(LOG_INFO, 0,
				  "Adding %s to hello neighbor set ext",
				  ip_to_str(rt->dest_addr));
#endif
			    memcpy(AODV_EXT_DATA(ext), &rt->dest_addr,
				   sizeof(struct in_addr));
			    ext->length += sizeof(struct in_addr);
			}
		    }
		}
		if (ext->length)
		    msg_size = RREP_SIZE + AODV_EXT_SIZE(ext);
	    }
	    dest.s_addr = AODV_BROADCAST;
	    aodv_socket_send((AODV_msg *) rrep, dest, msg_size, 1, &DEV_NR(i));
	}

	timer_set_timeout(&hello_timer, HELLO_INTERVAL + jitter);
    } else {
	if (HELLO_INTERVAL - time_diff + jitter < 0)
	    timer_set_timeout(&hello_timer,
			      HELLO_INTERVAL - time_diff - jitter);
	else
	    timer_set_timeout(&hello_timer,
			      HELLO_INTERVAL - time_diff + jitter);
    }
}
  1. void NS_CLASS neighbor_add(AODV_msg * aodv_msg, struct in_addr source,unsigned int ifindex)：加入新的邻居节点地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void NS_CLASS neighbor_add(AODV_msg * aodv_msg, struct in_addr source,
			   unsigned int ifindex)
{
    struct timeval now;
    rt_table_t *rt = NULL;
    u_int32_t seqno = 0;

    gettimeofday(&now, NULL);

    rt = rt_table_find(source);

    if (!rt) {
	DEBUG(LOG_DEBUG, 0, "%s new NEIGHBOR!", ip_to_str(source));
	rt = rt_table_insert(source, source, 1, 0,
			     ACTIVE_ROUTE_TIMEOUT, VALID, 0, ifindex);
    } else {
	/* Don't update anything if this is a uni-directional link... */
	if (rt->flags & RT_UNIDIR)
	    return;

	if (rt->dest_seqno != 0)
	    seqno = rt->dest_seqno;

	rt_table_update(rt, source, 1, seqno, ACTIVE_ROUTE_TIMEOUT,
			VALID, rt->flags);
    }

    if (!llfeedback && rt->hello_timer.used)
	hello_update_timeout(rt, &now, ALLOWED_HELLO_LOSS * HELLO_INTERVAL);

    return;
}
  1. void NS_CLASS aodv_socket_send(AODV_msg * aodv_msg, struct in_addr dst, int len, u_int8_t ttl, struct dev_info *dev)向指定的 aodv 节点发送数据。关于数据发送的操作都要经过这个函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
void NS_CLASS aodv_socket_send(AODV_msg * aodv_msg, struct in_addr dst,
			       int len, u_int8_t ttl, struct dev_info *dev)
{
    int retval = 0;
    struct timeval now;
    /* Rate limit stuff: */

#ifndef NS_PORT

    struct sockaddr_in dst_addr;

    if (wait_on_reboot && aodv_msg->type == AODV_RREP)
	return;

    memset(&dst_addr, 0, sizeof(dst_addr));
    dst_addr.sin_family = AF_INET;
    dst_addr.sin_addr = dst;
    dst_addr.sin_port = htons(AODV_PORT);

    /* Set ttl */
    if (setsockopt(dev->sock, SOL_IP, IP_TTL, &ttl, sizeof(ttl)) < 0) {
	alog(LOG_WARNING, 0, __FUNCTION__, "ERROR setting ttl!");
	return;
    }
#else

    /*
       NS_PORT: Sending of AODV_msg messages to other AODV-UU routing agents
       by encapsulating them in a Packet.

       Note: This method is _only_ for sending AODV packets to other routing
       agents, _not_ for forwarding "regular" IP packets!
     */

    /* If we are in waiting phase after reboot, don't send any RREPs */
    if (wait_on_reboot && aodv_msg->type == AODV_RREP)
	return;

    /*
       NS_PORT: Don't allocate packet until now. Otherwise packet uid
       (unique ID) space is unnecessarily exhausted at the beginning of
       the simulation, resulting in uid:s starting at values greater than 0.
     */
    Packet *p = allocpkt();
    struct hdr_cmn *ch = HDR_CMN(p);
    struct hdr_ip *ih = HDR_IP(p);
    hdr_aodvuu *ah = HDR_AODVUU(p);

    // Clear AODVUU part of packet
    memset(ah, '\0', ah->size());

    // Copy message contents into packet
    memcpy(ah, aodv_msg, len);

    // Set common header fields
    ch->ptype() = PT_AODVUU;
    ch->direction() = hdr_cmn::DOWN;
    ch->size() += len + IP_HDR_LEN;
    ch->iface() = -2;
    ch->error() = 0;
    ch->prev_hop_ = (nsaddr_t) dev->ipaddr.s_addr;

    // Set IP header fields
    ih->saddr() = (nsaddr_t) dev->ipaddr.s_addr;
    ih->daddr() = (nsaddr_t) dst.s_addr;
    ih->ttl() = ttl;

    // Note: Port number for routing agents, not AODV port number!
    ih->sport() = RT_PORT;
    ih->dport() = RT_PORT;

    // Fake success
    retval = len;
#endif				/* NS_PORT */

    /* If rate limiting is enabled, check if we are sending either a
       RREQ or a RERR. In that case, drop the outgoing control packet
       if the time since last transmit of that type of packet is less
       than the allowed RATE LIMIT time... */

    if (ratelimit) {

	gettimeofday(&now, NULL);

	switch (aodv_msg->type) {
	case AODV_RREQ:
	    if (num_rreq == (RREQ_RATELIMIT - 1)) {
		if (timeval_diff(&now, &rreq_ratel[0]) < 1000) {
		    DEBUG(LOG_DEBUG, 0, "RATELIMIT: Dropping RREQ %ld ms",
			  timeval_diff(&now, &rreq_ratel[0]));
#ifdef NS_PORT
		  	Packet::free(p);
#endif
		    return;
		} else {
		    memmove(rreq_ratel, &rreq_ratel[1],
			    sizeof(struct timeval) * (num_rreq - 1));
		    memcpy(&rreq_ratel[num_rreq - 1], &now,
			   sizeof(struct timeval));
		}
	    } else {
		memcpy(&rreq_ratel[num_rreq], &now, sizeof(struct timeval));
		num_rreq++;
	    }
	    break;
	case AODV_RERR:
	    if (num_rerr == (RERR_RATELIMIT - 1)) {
		if (timeval_diff(&now, &rerr_ratel[0]) < 1000) {
		    DEBUG(LOG_DEBUG, 0, "RATELIMIT: Dropping RERR %ld ms",
			  timeval_diff(&now, &rerr_ratel[0]));
#ifdef NS_PORT
		  	Packet::free(p);
#endif
		    return;
		} else {
		    memmove(rerr_ratel, &rerr_ratel[1],
			    sizeof(struct timeval) * (num_rerr - 1));
		    memcpy(&rerr_ratel[num_rerr - 1], &now,
			   sizeof(struct timeval));
		}
	    } else {
		memcpy(&rerr_ratel[num_rerr], &now, sizeof(struct timeval));
		num_rerr++;
	    }
	    break;
	}
    }

    /* If we broadcast this message we update the time of last broadcast
       to prevent unnecessary broadcasts of HELLO msg's */
    if (dst.s_addr == AODV_BROADCAST) {

	gettimeofday(&this_host.bcast_time, NULL);

#ifdef NS_PORT
	ch->addr_type() = NS_AF_NONE;

	sendPacket(p, dst, 0.0);
#else

	retval = sendto(dev->sock, send_buf, len, 0,
			(struct sockaddr *) &dst_addr, sizeof(dst_addr));

	if (retval < 0) {

	    alog(LOG_WARNING, errno, __FUNCTION__, "Failed send to bc %s",
		 ip_to_str(dst));
	    return;
	}
#endif

    } else {

#ifdef NS_PORT
	ch->addr_type() = NS_AF_INET;
	/* We trust the decision of next hop for all AODV messages... */

	if (dst.s_addr == AODV_BROADCAST)
	    sendPacket(p, dst, 0.001 * Random::uniform());
	else
	    sendPacket(p, dst, 0.0);
#else
	retval = sendto(dev->sock, send_buf, len, 0,
			(struct sockaddr *) &dst_addr, sizeof(dst_addr));

	if (retval < 0) {
	    alog(LOG_WARNING, errno, __FUNCTION__, "Failed send to %s",
		 ip_to_str(dst));
	    return;
	}
#endif
    }

    /* Do not print hello msgs... */
    if (!(aodv_msg->type == AODV_RREP && (dst.s_addr == AODV_BROADCAST)))
	DEBUG(LOG_INFO, 0, "AODV msg to %s ttl=%d size=%u",
	      ip_to_str(dst), ttl, retval, len);

    return;
}