routing_table.c

一种用于AD HOC 无线自组网络上的动态路由的源代码

	   are expected to be symmetric. */
	if (rev_rt && rev_rt->state == VALID) {

		if (llfeedback || rev_rt->hcnt != 1 || rev_rt->hello_timer.used)
			rt_table_update_timeout(rev_rt, ACTIVE_ROUTE_TIMEOUT);

		next_hop_rt = rt_table_find(rev_rt->next_hop);

		if (next_hop_rt && next_hop_rt->state == VALID && rev_rt &&
		    next_hop_rt->dest_addr.s_addr != rev_rt->dest_addr.s_addr &&
		    (llfeedback || rev_rt->hello_timer.used))
			rt_table_update_timeout(next_hop_rt,
						ACTIVE_ROUTE_TIMEOUT);

		/* Update HELLO timer of next hop neighbor if active */
/* 	if (!llfeedback && next_hop_rt->hello_timer.used) { */
/* 	    struct timeval now; */

/* 	    gettimeofday(&now, NULL); */
/* 	    hello_update_timeout(next_hop_rt, &now,  */
/* 				 ALLOWED_HELLO_LOSS * HELLO_INTERVAL); */
/* 	} */
	}
}

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_t *NS_CLASS rt_table_find_gateway()
{
	rt_table_t *gw = NULL;
	int i;

	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 (rt->flags & RT_GATEWAY && rt->state == VALID) {
				if (!gw || rt->hcnt < gw->hcnt)
					gw = rt;
			}
		}
	}
	return gw;
}

#ifdef CONFIG_GATEWAY
int NS_CLASS rt_table_update_inet_rt(rt_table_t * gw, u_int32_t life)
{
	int n = 0;
	int i;

	if (!gw)
		return -1;

	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 (rt->flags & RT_INET_DEST && rt->state == VALID) {
				rt_table_update(rt, gw->dest_addr, gw->hcnt, 0,
						life, VALID, rt->flags);
				n++;
			}
		}
	}
	return n;
}
#endif				/* CONFIG_GATEWAY_DISABLED */

/* Route expiry and Deletion. */
int NS_CLASS rt_table_invalidate(rt_table_t * rt)
{
	struct timeval now;

	gettimeofday(&now, NULL);

	if (rt == NULL)
		return -1;

	/* If the route is already invalidated, do nothing... */
	if (rt->state == INVALID) {
		DEBUG(LOG_DEBUG, 0, "Route %s already invalidated!!!",
		      ip_to_str(rt->dest_addr));
		return -1;
	}

	if (rt->hello_timer.used) {
		DEBUG(LOG_DEBUG, 0, "last HELLO: %ld",
		      timeval_diff(&now, &rt->last_hello_time));
	}

	/* Remove any pending, but now obsolete timers. */
	timer_remove(&rt->rt_timer);
	timer_remove(&rt->hello_timer);
	timer_remove(&rt->ack_timer);

	/* Mark the route as invalid */
	rt->state = INVALID;
	rt_tbl.num_active--;

	rt->hello_cnt = 0;

	/* When the lifetime of a route entry expires, increase the sequence
	   number for that entry. */
	seqno_incr(rt->dest_seqno);

	rt->last_hello_time.tv_sec = 0;
	rt->last_hello_time.tv_usec = 0;

#ifndef NS_PORT
	nl_send_del_route_msg(rt->dest_addr, rt->next_hop, rt->hcnt);
#endif


#ifdef CONFIG_GATEWAY
	/* If this was a gateway, check if any Internet destinations were using
	 * it. In that case update them to use a backup gateway or invalide them
	 * too. */
	if (rt->flags & RT_GATEWAY) {
		int i;

		rt_table_t *gw = rt_table_find_gateway();

		for (i = 0; i < RT_TABLESIZE; i++) {
			list_t *pos;
			list_foreach(pos, &rt_tbl.tbl[i]) {
				rt_table_t *rt2 = (rt_table_t *) pos;

				if (rt2->state == VALID
				    && (rt2->flags & RT_INET_DEST)
				    && (rt2->next_hop.s_addr ==
					rt->dest_addr.s_addr)) {
					if (0) {
						DEBUG(LOG_DEBUG, 0,
						      "Invalidated GW %s but found new GW %s for %s",
						      ip_to_str(rt->dest_addr),
						      ip_to_str(gw->dest_addr),
						      ip_to_str(rt2->
								dest_addr));
						rt_table_update(rt2,
								gw->dest_addr,
								gw->hcnt, 0,
								timeval_diff
								(&rt->rt_timer.
								 timeout, &now),
								VALID,
								rt2->flags);
					} else {
						rt_table_invalidate(rt2);
						precursor_list_destroy(rt2);
					}
				}
			}
		}
	}
#endif

	if (rt->flags & RT_REPAIR) {
		/* Set a timeout for the repair */

		rt->rt_timer.handler = &NS_CLASS local_repair_timeout;
		timer_set_timeout(&rt->rt_timer, ACTIVE_ROUTE_TIMEOUT);

		DEBUG(LOG_DEBUG, 0, "%s kept for repairs during %u msecs",
		      ip_to_str(rt->dest_addr), ACTIVE_ROUTE_TIMEOUT);
	} else {

		/* Schedule a deletion timer */
		rt->rt_timer.handler = &NS_CLASS route_delete_timeout;
		timer_set_timeout(&rt->rt_timer, DELETE_PERIOD);

		DEBUG(LOG_DEBUG, 0, "%s removed in %u msecs",
		      ip_to_str(rt->dest_addr), DELETE_PERIOD);
	}

	return 0;
}

void NS_CLASS rt_table_delete(rt_table_t * rt)
{
	if (!rt) {
		DEBUG(LOG_ERR, 0, "No route entry to delete");
		return;
	}

	list_detach(&rt->l);

	precursor_list_destroy(rt);

	if (rt->state == VALID) {

#ifndef NS_PORT
		nl_send_del_route_msg(rt->dest_addr, rt->next_hop, rt->hcnt);
#endif
		rt_tbl.num_active--;
	}
	/* Make sure timers are removed... */
	timer_remove(&rt->rt_timer);
	timer_remove(&rt->hello_timer);
	timer_remove(&rt->ack_timer);

	rt_tbl.num_entries--;

	free(rt);
	return;
}

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

/* Add an neighbor to the active neighbor list. */

void NS_CLASS precursor_add(rt_table_t * rt, struct in_addr addr)
{
	precursor_t *pr;
	list_t *pos;

	/* Sanity check */
	if (!rt)
		return;

	/* Check if the node is already in the precursors list. */
	list_foreach(pos, &rt->precursors) {
		pr = (precursor_t *) pos;

		if (pr->neighbor.s_addr == addr.s_addr)
			return;
	}

	if ((pr = (precursor_t *) malloc(sizeof(precursor_t))) == NULL) {
		perror("Could not allocate memory for precursor node!!\n");
		exit(-1);
	}

	DEBUG(LOG_INFO, 0, "Adding precursor %s to rte %s",
	      ip_to_str(addr), ip_to_str(rt->dest_addr));

	pr->neighbor.s_addr = addr.s_addr;

	/* Insert in precursors list */

	list_add(&rt->precursors, &pr->l);
	rt->nprec++;

	return;
}

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

/* Remove a neighbor from the active neighbor list. */

void NS_CLASS precursor_remove(rt_table_t * rt, struct in_addr addr)
{
	list_t *pos;

	/* Sanity check */
	if (!rt)
		return;

	list_foreach(pos, &rt->precursors) {
		precursor_t *pr = (precursor_t *) pos;
		if (pr->neighbor.s_addr == addr.s_addr) {
			DEBUG(LOG_INFO, 0, "Removing precursor %s from rte %s",
			      ip_to_str(addr), ip_to_str(rt->dest_addr));

			list_detach(pos);
			rt->nprec--;
			free(pr);
			return;
		}
	}
}

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

/* Delete all entries from the active neighbor list. */

void precursor_list_destroy(rt_table_t * rt)
{
	list_t *pos, *tmp;

	/* Sanity check */
	if (!rt)
		return;

	list_foreach_safe(pos, tmp, &rt->precursors) {
		precursor_t *pr = (precursor_t *) pos;
		list_detach(pos);
		rt->nprec--;
		free(pr);
	}
}