olsr.cc

UM-OLSR is an OLSR (Optimized Link State Routing protocol) implementation for the ns2 network simula

/********** OLSR class **********/


///
/// \brief Creates necessary timers, binds TCL-available variables and do
/// some more initializations.
/// \param id Identifier for the OLSR agent. It will be used as the address
/// of this routing agent.
///
OLSR::OLSR(nsaddr_t id) :	Agent(PT_OLSR),
				hello_timer_(this),
				tc_timer_(this),
				mid_timer_(this) {

	// Enable usage of some of the configuration variables from Tcl.
	//
	// Note: Do NOT change the values of these variables in the constructor
	// after binding them! The desired default values should be set in
	// ns-X.XX/tcl/lib/ns-default.tcl instead.
	bind("willingness_", &willingness_);
	bind("hello_ival_", &hello_ival_);
	bind("tc_ival_", &tc_ival_);
	bind("mid_ival_", &mid_ival_);
	bind_bool("use_mac_", &use_mac_);
	
	// Do some initializations
	ra_addr_	= id;
	pkt_seq_	= OLSR_MAX_SEQ_NUM;
	msg_seq_	= OLSR_MAX_SEQ_NUM;
	ansn_		= OLSR_MAX_SEQ_NUM;
}

///
/// \brief	This function is called whenever a packet is received. It identifies
///		the type of the received packet and process it accordingly.
///
/// If it is an %OLSR packet then it is processed. In other case, if it is a data packet
/// then it is forwarded.
///
/// \param	p the received packet.
/// \param	h a handler (not used).
///
void
OLSR::recv(Packet* p, Handler* h) {
	struct hdr_cmn* ch	= HDR_CMN(p);
	struct hdr_ip* ih	= HDR_IP(p);
	
	if (ih->saddr() == ra_addr()) {
		// If there exists a loop, must drop the packet
		if (ch->num_forwards() > 0) {
			drop(p, DROP_RTR_ROUTE_LOOP);
			return;
		}
		// else if this is a packet I am originating, must add IP header
		else if (ch->num_forwards() == 0)
			ch->size() += IP_HDR_LEN;
	}
	
	// If it is an OLSR packet, must process it
	if (ch->ptype() == PT_OLSR)
		recv_olsr(p);
	// Otherwise, must forward the packet (unless TTL has reached zero)
	else {
		ih->ttl_--;
		if (ih->ttl_ == 0) {
			drop(p, DROP_RTR_TTL);
			return;
		}
		forward_data(p);
	}
}

///
/// \brief Processes an incoming %OLSR packet following RFC 3626 specification.
/// \param p received packet.
///
void
OLSR::recv_olsr(Packet* p) {
	struct hdr_ip* ih	= HDR_IP(p);
	OLSR_pkt* op		= PKT_OLSR(p);
	
	// All routing messages are sent from and to port RT_PORT,
	// so we check it.
	assert(ih->sport() == RT_PORT);
	assert(ih->dport() == RT_PORT);
	
	// If the packet contains no messages must be silently discarded.
	// There could exist a message with an empty body, so the size of
	// the packet would be pkt-hdr-size + msg-hdr-size.
	if (op->pkt_len() < OLSR_PKT_HDR_SIZE + OLSR_MSG_HDR_SIZE) {
		Packet::free(p);
		return;
	}
	
	assert(op->count >= 0 && op->count <= OLSR_MAX_MSGS);
	for (int i = 0; i < op->count; i++) {
		OLSR_msg& msg = op->msg(i);
		
		// If ttl is less than or equal to zero, or
		// the receiver is the same as the originator,
		// the message must be silently dropped
		if (msg.ttl() <= 0 || msg.orig_addr() == ra_addr())
			continue;
		
		// If the message has been processed it must not be
		// processed again
		bool do_forwarding = true;
		OLSR_dup_tuple* duplicated = state_.find_dup_tuple(msg.orig_addr(), msg.msg_seq_num());
		if (duplicated == NULL) {
			// Process the message according to its type
			if (msg.msg_type() == OLSR_HELLO_MSG)
				process_hello(msg, ra_addr(), ih->saddr());
			else if (msg.msg_type() == OLSR_TC_MSG)
				process_tc(msg, ih->saddr());
			else if (msg.msg_type() == OLSR_MID_MSG)
				process_mid(msg, ih->saddr());
			else {
				debug("%f: Node %d can not process OLSR packet because does not "
					"implement OLSR type (%x)\n",
					CURRENT_TIME,
					OLSR::node_id(ra_addr()),
					msg.msg_type());
			}
		}
		else {
			// If the message has been considered for forwarding, it should
			// not be retransmitted again
			for (addr_list_t::iterator it = duplicated->iface_list().begin();
				it != duplicated->iface_list().end();
				it++) {
				if (*it == ra_addr()) {
					do_forwarding = false;
					break;
				}
			}
		}
			
		if (do_forwarding) {
			// HELLO messages are never forwarded.
			// TC and MID messages are forwarded using the default algorithm.
			// Remaining messages are also forwarded using the default algorithm.
			if (msg.msg_type() != OLSR_HELLO_MSG)
				forward_default(p, msg, duplicated, ra_addr());
		}

	}
	
	// After processing all OLSR messages, we must recompute routing table
	rtable_computation();
	
	// Release resources
	Packet::free(p);
}

///
/// \brief Computates MPR set of a node following RFC 3626 hints.
///
void
OLSR::mpr_computation() {
	// MPR computation should be done for each interface. See section 8.3.1
	// (RFC 3626) for details.
	
	state_.clear_mprset();
	
	nbset_t N; nb2hopset_t N2;
	// N is the subset of neighbors of the node, which are
	// neighbor "of the interface I"
	for (nbset_t::iterator it = nbset().begin(); it != nbset().end(); it++)
		if ((*it)->status() == OLSR_STATUS_SYM) // I think that we need this check
			N.push_back(*it);
	
	// N2 is the set of 2-hop neighbors reachable from "the interface
	// I", excluding:
	// (i)   the nodes only reachable by members of N with willingness WILL_NEVER
	// (ii)  the node performing the computation
	// (iii) all the symmetric neighbors: the nodes for which there exists a symmetric
	//       link to this node on some interface.
	for (nb2hopset_t::iterator it = nb2hopset().begin(); it != nb2hopset().end(); it++) {
		OLSR_nb2hop_tuple* nb2hop_tuple = *it;
		bool ok = true;
		OLSR_nb_tuple* nb_tuple = state_.find_sym_nb_tuple(nb2hop_tuple->nb_main_addr());
		if (nb_tuple == NULL)
			ok = false;
		else {
			nb_tuple = state_.find_nb_tuple(nb2hop_tuple->nb_main_addr(), OLSR_WILL_NEVER);
			if (nb_tuple != NULL)
				ok = false;
			else {
				nb_tuple = state_.find_sym_nb_tuple(nb2hop_tuple->nb2hop_addr());
				if (nb_tuple != NULL)
					ok = false;
			}
		}

		if (ok)
			N2.push_back(nb2hop_tuple);
	}
	
	// 1. Start with an MPR set made of all members of N with
	// N_willingness equal to WILL_ALWAYS
	for (nbset_t::iterator it = N.begin(); it != N.end(); it++) {
		OLSR_nb_tuple* nb_tuple = *it;
		if (nb_tuple->willingness() == OLSR_WILL_ALWAYS)
			state_.insert_mpr_addr(nb_tuple->nb_main_addr());
	}
	
	// 2. Calculate D(y), where y is a member of N, for all nodes in N.
	// We will do this later.
	
	// 3. Add to the MPR set those nodes in N, which are the *only*
	// nodes to provide reachability to a node in N2. Remove the
	// nodes from N2 which are now covered by a node in the MPR set.
	mprset_t foundset;
	std::set<nsaddr_t> deleted_addrs;
	for (nb2hopset_t::iterator it = N2.begin(); it != N2.end(); it++) {
		OLSR_nb2hop_tuple* nb2hop_tuple1 = *it;
		
		mprset_t::iterator pos = foundset.find(nb2hop_tuple1->nb2hop_addr());
		if (pos != foundset.end())
			continue;
		
		bool found = false;
		for (nbset_t::iterator it2 = N.begin(); it2 != N.end(); it2++) {
			if ((*it2)->nb_main_addr() == nb2hop_tuple1->nb_main_addr()) {
				found = true;
				break;
			}
		}
		if (!found)
			continue;
		
		found = false;
		for (nb2hopset_t::iterator it2 = it + 1; it2 != N2.end(); it2++) {
			OLSR_nb2hop_tuple* nb2hop_tuple2 = *it2;
			if (nb2hop_tuple1->nb2hop_addr() == nb2hop_tuple2->nb2hop_addr()) {
				foundset.insert(nb2hop_tuple1->nb2hop_addr());
				found = true;
				break;
			}
		}
		if (!found) {
			state_.insert_mpr_addr(nb2hop_tuple1->nb_main_addr());
			
			for (nb2hopset_t::iterator it2 = it + 1; it2 != N2.end(); it2++) {
				OLSR_nb2hop_tuple* nb2hop_tuple2 = *it2;
				if (nb2hop_tuple1->nb_main_addr() == nb2hop_tuple2->nb_main_addr()) {
					deleted_addrs.insert(nb2hop_tuple2->nb2hop_addr());
					it2 = N2.erase(it2);
					it2--;
				}
			}
			it = N2.erase(it);
			it--;
		}
		
		for (std::set<nsaddr_t>::iterator it2 = deleted_addrs.begin();
			it2 != deleted_addrs.end();
			it2++) {
			for (nb2hopset_t::iterator it3 = N2.begin();
				it3 != N2.end();
				it3++) {
				if ((*it3)->nb2hop_addr() == *it2) {
					it3 = N2.erase(it3);
					it3--;
					// I have to reset the external iterator because it
					// may have been invalidated by the latter deletion
					it = N2.begin();
					it--;
				}
			}
		}
		deleted_addrs.clear();
	}
	
	// 4. While there exist nodes in N2 which are not covered by at
	// least one node in the MPR set:
	while (N2.begin() != N2.end()) {
		// 4.1. For each node in N, calculate the reachability, i.e., the
		// number of nodes in N2 which are not yet covered by at
		// least one node in the MPR set, and which are reachable
		// through this 1-hop neighbor
		map<int, std::vector<OLSR_nb_tuple*> > reachability;
		set<int> rs;
		for (nbset_t::iterator it = N.begin(); it != N.end(); it++) {
			OLSR_nb_tuple* nb_tuple = *it;
			int r = 0;
			for (nb2hopset_t::iterator it2 = N2.begin(); it2 != N2.end(); it2++) {
				OLSR_nb2hop_tuple* nb2hop_tuple = *it2;
				if (nb_tuple->nb_main_addr() == nb2hop_tuple->nb_main_addr())
					r++;
			}
			rs.insert(r);
			reachability[r].push_back(nb_tuple);
		}
		
		// 4.2. Select as a MPR the node with highest N_willingness among
		// the nodes in N with non-zero reachability. In case of
		// multiple choice select the node which provides
		// reachability to the maximum number of nodes in N2. In
		// case of multiple nodes providing the same amount of
		// reachability, select the node as MPR whose D(y) is
		// greater. Remove the nodes from N2 which are now covered
		// by a node in the MPR set.
		OLSR_nb_tuple* max = NULL;
		int max_r = 0;
		for (set<int>::iterator it = rs.begin(); it != rs.end(); it++) {
			int r = *it;
			if (r > 0) {
				for (std::vector<OLSR_nb_tuple*>::iterator it2 = reachability[r].begin();
					it2 != reachability[r].end();
					it2++) {
					OLSR_nb_tuple* nb_tuple = *it2;
					if (max == NULL || nb_tuple->willingness() > max->willingness()) {
						max = nb_tuple;
						max_r = r;
					}
					else if (nb_tuple->willingness() == max->willingness()) {
						if (r > max_r) {
							max = nb_tuple;
							max_r = r;
						}
						else if (r == max_r) {
							if (degree(nb_tuple) > degree(max)) {
								max = nb_tuple;
								max_r = r;
							}
						}
					}
				}
			}
		}
		if (max != NULL) {
			state_.insert_mpr_addr(max->nb_main_addr());
			std::set<nsaddr_t> nb2hop_addrs;
			for (nb2hopset_t::iterator it = N2.begin(); it != N2.end(); it++) {
				OLSR_nb2hop_tuple* nb2hop_tuple = *it;
				if (nb2hop_tuple->nb_main_addr() == max->nb_main_addr()) {
					nb2hop_addrs.insert(nb2hop_tuple->nb2hop_addr());
					it = N2.erase(it);
					it--;
				}
			}
			for (nb2hopset_t::iterator it = N2.begin(); it != N2.end(); it++) {
				OLSR_nb2hop_tuple* nb2hop_tuple = *it;
				std::set<nsaddr_t>::iterator it2 =
					nb2hop_addrs.find(nb2hop_tuple->nb2hop_addr());
				if (it2 != nb2hop_addrs.end()) {
					it = N2.erase(it);
					it--;
				}
			}
		}
	}
}

///
/// \brief Creates the routing table of the node following RFC 3626 hints.
///
void
OLSR::rtable_computation() {
	// 1. All the entries from the routing table are removed.
	rtable_.clear();
	
	// 2. The new routing entries are added starting with the
	// symmetric neighbors (h=1) as the destination nodes.
	for (nbset_t::iterator it = nbset().begin(); it != nbset().end(); it++) {
		OLSR_nb_tuple* nb_tuple = *it;
		if (nb_tuple->status() == OLSR_STATUS_SYM) {
			bool nb_main_addr = false;
			OLSR_link_tuple* lt = NULL;
			for (linkset_t::iterator it2 = linkset().begin(); it2 != linkset().end(); it2++) {
				OLSR_link_tuple* link_tuple = *it2;
				if (get_main_addr(link_tuple->nb_iface_addr()) == nb_tuple->nb_main_addr() && link_tuple->time() >= CURRENT_TIME) {
					lt = link_tuple;
					rtable_.add_entry(link_tuple->nb_iface_addr(),
							link_tuple->nb_iface_addr(),
							link_tuple->local_iface_addr(),
							1);
					if (link_tuple->nb_iface_addr() == nb_tuple->nb_main_addr())
						nb_main_addr = true;
				}
			}
			if (!nb_main_addr && lt != NULL) {
				rtable_.add_entry(nb_tuple->nb_main_addr(),
						lt->nb_iface_addr(),
						lt->local_iface_addr(),
						1);
			}
		}
	}
	
	// N2 is the set of 2-hop neighbors reachable from this node, excluding:
	// (i)   the nodes only reachable by members of N with willingness WILL_NEVER
	// (ii)  the node performing the computation
	// (iii) all the symmetric neighbors: the nodes for which there exists a symmetric
	//       link to this node on some interface.
	for (nb2hopset_t::iterator it = nb2hopset().begin(); it != nb2hopset().end(); it++) {
		OLSR_nb2hop_tuple* nb2hop_tuple = *it;
		bool ok = true;
		OLSR_nb_tuple* nb_tuple = state_.find_sym_nb_tuple(nb2hop_tuple->nb_main_addr());
		if (nb_tuple == NULL)
			ok = false;
		else {
			nb_tuple = state_.find_nb_tuple(nb2hop_tuple->nb_main_addr(), OLSR_WILL_NEVER);
			if (nb_tuple != NULL)
				ok = false;
			else {
				nb_tuple = state_.find_sym_nb_tuple(nb2hop_tuple->nb2hop_addr());
				if (nb_tuple != NULL)
					ok = false;
			}