部分描述由 ChatGPT 3.5 生成，代码为手动查找。
AODV（Ad-hoc On-demand Distance Vector）是一种自适应的距离向量路由协议，常用于无线自组网中。以下是 AODV 协议的实现中一些比较重要的函数和数据结构及其定义：
struct rt_table：AODV 路由表的结构体，定义于routing_table.h，包含以下字段：
/* 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 */
};
rt_table_t rt_table_find(structin_addrdest_addr)：查找 AODV 路由表中与给定目标地址匹配的路由表项。如果找到，返回指向该路由表项的指针；否则返回 NULL。
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;
}
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 节点收到一个数据包时，会调用此函数更新路由表项。如果该路由表项不存在，会创建新的路由表项并添加到路由表中。
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;
}
以上是一些维护底层路由表的重要函数和结构体。可以通过将这些函数进一步封装为更加抽象的接口，便于调用。
hello_send(void *arg)：发送 hello 消息的函数，定义于aodv_hello.c，用于检测邻居节点的存在。每个 AODV 节点定期发送 hello 消息，以便发现邻居节点的变化，并将变化更新到路由表中。
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);
}
}
void NS_CLASS neighbor_add(AODV_msg * aodv_msg, struct in_addr source,unsigned int ifindex)：加入新的邻居节点地址。
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;
}
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 节点发送数据。关于数据发送的操作都要经过这个函数。
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;
}