olsr.cc

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

		}

		// 3. For each node in N2 create a new entry in the routing table
		if (ok) {
			OLSR_rt_entry* entry = rtable_.lookup(nb2hop_tuple->nb_main_addr());
			assert(entry != NULL);
			rtable_.add_entry(nb2hop_tuple->nb2hop_addr(),
					entry->next_addr(),
					entry->iface_addr(),
					2);
		}
	}
	
	for (u_int32_t h = 2; ; h++) {
		bool added = false;
		
		// 4.1. For each topology entry in the topology table, if its
		// T_dest_addr does not correspond to R_dest_addr of any
		// route entry in the routing table AND its T_last_addr
		// corresponds to R_dest_addr of a route entry whose R_dist
		// is equal to h, then a new route entry MUST be recorded in
		// the routing table (if it does not already exist)
		for (topologyset_t::iterator it = topologyset().begin();
			it != topologyset().end();
			it++) {
			OLSR_topology_tuple* topology_tuple = *it;
			OLSR_rt_entry* entry1 = rtable_.lookup(topology_tuple->dest_addr());
			OLSR_rt_entry* entry2 = rtable_.lookup(topology_tuple->last_addr());
			if (entry1 == NULL && entry2 != NULL && entry2->dist() == h) {
				rtable_.add_entry(topology_tuple->dest_addr(),
						entry2->next_addr(),
						entry2->iface_addr(),
						h+1);
				added = true;
			}
		}
		
		// 5. For each entry in the multiple interface association base
		// where there exists a routing entry such that:
		//	R_dest_addr  == I_main_addr  (of the multiple interface association entry)
		// AND there is no routing entry such that:
		//	R_dest_addr  == I_iface_addr
		// then a route entry is created in the routing table
		for (ifaceassocset_t::iterator it = ifaceassocset().begin();
			it != ifaceassocset().end();
			it++) {
			OLSR_iface_assoc_tuple* tuple = *it;
			OLSR_rt_entry* entry1 = rtable_.lookup(tuple->main_addr());
			OLSR_rt_entry* entry2 = rtable_.lookup(tuple->iface_addr());
			if (entry1 != NULL && entry2 == NULL) {
				rtable_.add_entry(tuple->iface_addr(),
						entry1->next_addr(),
						entry1->iface_addr(),
						entry1->dist());
				added = true;
			}
		}

		if (!added)
			break;
	}
}

///
/// \brief Processes a HELLO message following RFC 3626 specification.
///
/// Link sensing and population of the Neighbor Set, 2-hop Neighbor Set and MPR
/// Selector Set are performed.
///
/// \param msg the %OLSR message which contains the HELLO message.
/// \param receiver_iface the address of the interface where the message was received from.
/// \param sender_iface the address of the interface where the message was sent from.
///
void
OLSR::process_hello(OLSR_msg& msg, nsaddr_t receiver_iface, nsaddr_t sender_iface) {
	assert(msg.msg_type() == OLSR_HELLO_MSG);

        link_sensing(msg, receiver_iface, sender_iface);
	populate_nbset(msg);
	populate_nb2hopset(msg);
	mpr_computation();
	populate_mprselset(msg);
}

///
/// \brief Processes a TC message following RFC 3626 specification.
///
/// The Topology Set is updated (if needed) with the information of
/// the received TC message.
///
/// \param msg the %OLSR message which contains the TC message.
/// \param sender_iface the address of the interface where the message was sent from.
///
void
OLSR::process_tc(OLSR_msg& msg, nsaddr_t sender_iface) {
	assert(msg.msg_type() == OLSR_TC_MSG);
	double now	= CURRENT_TIME;
	OLSR_tc& tc	= msg.tc();
	
	// 1. If the sender interface of this message is not in the symmetric
	// 1-hop neighborhood of this node, the message MUST be discarded.
	OLSR_link_tuple* link_tuple = state_.find_sym_link_tuple(sender_iface, now);
	if (link_tuple == NULL)
		return;
	
	// 2. If there exist some tuple in the topology set where:
	// 	T_last_addr == originator address AND
	// 	T_seq       >  ANSN,
	// then further processing of this TC message MUST NOT be
	// performed.
	OLSR_topology_tuple* topology_tuple =
		state_.find_newer_topology_tuple(msg.orig_addr(), tc.ansn());
	if (topology_tuple != NULL)
		return;
	
	// 3. All tuples in the topology set where:
	//	T_last_addr == originator address AND
	//	T_seq       <  ANSN
	// MUST be removed from the topology set.
	state_.erase_older_topology_tuples(msg.orig_addr(), tc.ansn());

	// 4. For each of the advertised neighbor main address received in
	// the TC message:
	for (int i = 0; i < tc.count; i++) {
		assert(i >= 0 && i < OLSR_MAX_ADDRS);
		nsaddr_t addr = tc.nb_main_addr(i);
		// 4.1. If there exist some tuple in the topology set where:
		// 	T_dest_addr == advertised neighbor main address, AND
		// 	T_last_addr == originator address,
		// then the holding time of that tuple MUST be set to:
		// 	T_time      =  current time + validity time.
		OLSR_topology_tuple* topology_tuple =
			state_.find_topology_tuple(addr, msg.orig_addr());
		if (topology_tuple != NULL)
			topology_tuple->time() = now + OLSR::emf_to_seconds(msg.vtime());
		// 4.2. Otherwise, a new tuple MUST be recorded in the topology
		// set where:
		//	T_dest_addr = advertised neighbor main address,
		//	T_last_addr = originator address,
		//	T_seq       = ANSN,
		//	T_time      = current time + validity time.
		else {
			OLSR_topology_tuple* topology_tuple = new OLSR_topology_tuple;
			topology_tuple->dest_addr()	= addr;
			topology_tuple->last_addr()	= msg.orig_addr();
			topology_tuple->seq()		= tc.ansn();
			topology_tuple->time()		= now + OLSR::emf_to_seconds(msg.vtime());
			add_topology_tuple(topology_tuple);
			// Schedules topology tuple deletion
			OLSR_TopologyTupleTimer* topology_timer =
				new OLSR_TopologyTupleTimer(this, topology_tuple);
			topology_timer->resched(DELAY(topology_tuple->time()));
		}
	}
}

///
/// \brief Processes a MID message following RFC 3626 specification.
///
/// The Interface Association Set is updated (if needed) with the information
/// of the received MID message.
///
/// \param msg the %OLSR message which contains the MID message.
/// \param sender_iface the address of the interface where the message was sent from.
///
void
OLSR::process_mid(OLSR_msg& msg, nsaddr_t sender_iface) {
	assert(msg.msg_type() == OLSR_MID_MSG);
	double now	= CURRENT_TIME;
	OLSR_mid& mid	= msg.mid();
	
	// 1. If the sender interface of this message is not in the symmetric
	// 1-hop neighborhood of this node, the message MUST be discarded.
	OLSR_link_tuple* link_tuple = state_.find_sym_link_tuple(sender_iface, now);
	if (link_tuple == NULL)
		return;
	
	// 2. For each interface address listed in the MID message
	for (int i = 0; i < mid.count; i++) {
		bool updated = false;
		for (ifaceassocset_t::iterator it = ifaceassocset().begin();
			it != ifaceassocset().end();
			it++) {
			OLSR_iface_assoc_tuple* tuple = *it;
			if (tuple->iface_addr() == mid.iface_addr(i)
				&& tuple->main_addr() == msg.orig_addr()) {
				tuple->time()	= now + OLSR::emf_to_seconds(msg.vtime());
				updated		= true;
			}			
		}
		if (!updated) {
			OLSR_iface_assoc_tuple* tuple	= new OLSR_iface_assoc_tuple;
			tuple->iface_addr()		= msg.mid().iface_addr(i);
			tuple->main_addr()		= msg.orig_addr();
			tuple->time()			= now + OLSR::emf_to_seconds(msg.vtime());
			add_ifaceassoc_tuple(tuple);
			// Schedules iface association tuple deletion
			OLSR_IfaceAssocTupleTimer* ifaceassoc_timer =
				new OLSR_IfaceAssocTupleTimer(this, tuple);
			ifaceassoc_timer->resched(DELAY(tuple->time()));
		}
	}
}

///
/// \brief OLSR's default forwarding algorithm.
///
/// See RFC 3626 for details.
///
/// \param p the %OLSR packet which has been received.
/// \param msg the %OLSR message which must be forwarded.
/// \param dup_tuple NULL if the message has never been considered for forwarding,
/// or a duplicate tuple in other case.
/// \param local_iface the address of the interface where the message was received from.
///
void
OLSR::forward_default(Packet* p, OLSR_msg& msg, OLSR_dup_tuple* dup_tuple, nsaddr_t local_iface) {
	double now		= CURRENT_TIME;
	struct hdr_ip* ih	= HDR_IP(p);
	
	// If the sender interface address is not in the symmetric
	// 1-hop neighborhood the message must not be forwarded
	OLSR_link_tuple* link_tuple = state_.find_sym_link_tuple(ih->saddr(), now);
	if (link_tuple == NULL)
		return;

	// If the message has already been considered for forwarding,
	// it must not be retransmitted again
	if (dup_tuple != NULL && dup_tuple->retransmitted()) {
		debug("%f: Node %d does not forward a message received"
			" from %d because it is duplicated\n",
			CURRENT_TIME,
			OLSR::node_id(ra_addr()),
			OLSR::node_id(dup_tuple->addr()));
		return;
	}
	
	// If the sender interface address is an interface address
	// of a MPR selector of this node and ttl is greater than 1,
	// the message must be retransmitted
	bool retransmitted = false;
	if (msg.ttl() > 1) {
		OLSR_mprsel_tuple* mprsel_tuple =
			state_.find_mprsel_tuple(get_main_addr(ih->saddr()));
		if (mprsel_tuple != NULL) {
			OLSR_msg& new_msg = msg;
			new_msg.ttl()--;
			new_msg.hop_count()++;
			// We have to introduce a random delay to avoid
			// synchronization with neighbors.
			enque_msg(new_msg, JITTER);
			retransmitted = true;
		}
	}
	
	// Update duplicate tuple...
	if (dup_tuple != NULL) {
		dup_tuple->time()		= now + OLSR_DUP_HOLD_TIME;
		dup_tuple->retransmitted()	= retransmitted;
		dup_tuple->iface_list().push_back(local_iface);
	}
	// ...or create a new one
	else {
		OLSR_dup_tuple* new_dup = new OLSR_dup_tuple;
		new_dup->addr()			= msg.orig_addr();
		new_dup->seq_num()		= msg.msg_seq_num();
		new_dup->time()			= now + OLSR_DUP_HOLD_TIME;
		new_dup->retransmitted()	= retransmitted;
		new_dup->iface_list().push_back(local_iface);
		add_dup_tuple(new_dup);
		// Schedules dup tuple deletion
		OLSR_DupTupleTimer* dup_timer =
			new OLSR_DupTupleTimer(this, new_dup);
		dup_timer->resched(DELAY(new_dup->time()));
	}
}

///
/// \brief Forwards a data packet to the appropiate next hop indicated by the routing table.
///
/// \param p the packet which must be forwarded.
///
void
OLSR::forward_data(Packet* p) {
	struct hdr_cmn* ch	= HDR_CMN(p);
	struct hdr_ip* ih	= HDR_IP(p);

	if (ch->direction() == hdr_cmn::UP &&
		((u_int32_t)ih->daddr() == IP_BROADCAST || ih->daddr() == ra_addr())) {
		dmux_->recv(p, 0);
		return;
	}
	else {
		ch->direction()	= hdr_cmn::DOWN;
		ch->addr_type()	= NS_AF_INET;
		if ((u_int32_t)ih->daddr() == IP_BROADCAST)
			ch->next_hop()	= IP_BROADCAST;
		else {
			OLSR_rt_entry* entry = rtable_.lookup(ih->daddr());
			if (entry == NULL) {
				debug("%f: Node %d can not forward a packet destined to %d\n",
					CURRENT_TIME,
					OLSR::node_id(ra_addr()),
					OLSR::node_id(ih->daddr()));
				drop(p, DROP_RTR_NO_ROUTE);
				return;
			}
			else {
				entry = rtable_.find_send_entry(entry);
				assert(entry != NULL);
				ch->next_hop() = entry->next_addr();
				if (use_mac()) {
					ch->xmit_failure_	= olsr_mac_failed_callback;
					ch->xmit_failure_data_	= (void*)this;
				}
			}
		}

		Scheduler::instance().schedule(target_, p, 0.0);
	}
}

///
/// \brief Enques an %OLSR message which will be sent with a delay of (0, delay].
///
/// This buffering system is used in order to piggyback several %OLSR messages in
/// a same %OLSR packet.
///
/// \param msg the %OLSR message which must be sent.
/// \param delay maximum delay the %OLSR message is going to be buffered.
///
void
OLSR::enque_msg(OLSR_msg& msg, double delay) {
	assert(delay >= 0);
	
	msgs_.push_back(msg);
	OLSR_MsgTimer* timer = new OLSR_MsgTimer(this);
	timer->resched(delay);
}

///
/// \brief Creates as many %OLSR packets as needed in order to send all buffered
/// %OLSR messages.
///
/// Maximum number of messages which can be contained in an %OLSR packet is
/// dictated by OLSR_MAX_MSGS constant.
///
void
OLSR::send_pkt() {
	int num_msgs = msgs_.size();
	if (num_msgs == 0)
		return;
	
	// Calculates the number of needed packets
	int num_pkts = (num_msgs%OLSR_MAX_MSGS == 0) ? num_msgs/OLSR_MAX_MSGS :
		(num_msgs/OLSR_MAX_MSGS + 1);
	
	for (int i = 0; i < num_pkts; i++) {
		Packet* p		= allocpkt();
		struct hdr_cmn* ch	= HDR_CMN(p);
		struct hdr_ip* ih	= HDR_IP(p);
		OLSR_pkt* op		= PKT_OLSR(p);
		
		op->pkt_len()		= OLSR_PKT_HDR_SIZE;
		op->pkt_seq_num()	= pkt_seq();
	
		int j = 0;
		for (std::vector<OLSR_msg>::iterator it = msgs_.begin(); it != msgs_.end(); it++) {
			if (j == OLSR_MAX_MSGS)
				break;
			
			op->pkt_body_[j++]	= *it;
			op->count		= j;
			op->pkt_len()		+= (*it).size();
			
			it = msgs_.erase(it);
			it--;
		}
	
		ch->ptype()		= PT_OLSR;
		ch->direction()		= hdr_cmn::DOWN;
		ch->size()		= IP_HDR_LEN + UDP_HDR_LEN + op->pkt_len();
		ch->error()		= 0;
		ch->next_hop()		= IP_BROADCAST;
		ch->addr_type()		= NS_AF_INET;
		if (use_mac()) {
			ch->xmit_failure_	= olsr_mac_failed_callback;
			ch->xmit_failure_data_	= (void*)this;
		}

		ih->saddr()	= ra_addr();
		ih->daddr()	= IP_BROADCAST;
		ih->sport()	= RT_PORT;
		ih->dport()	= RT_PORT;
		ih->ttl()	= IP_DEF_TTL;
		
		Scheduler::instance().schedule(target_, p, 0.0);
	}
}

///
/// \brief Creates a new %OLSR HELLO message which is buffered to be sent later on.
///
void
OLSR::send_hello() {
	OLSR_msg msg;
	double now		= CURRENT_TIME;
	msg.msg_type()		= OLSR_HELLO_MSG;
	msg.vtime()		= OLSR::seconds_to_emf(OLSR_NEIGHB_HOLD_TIME);
	msg.orig_addr()		= ra_addr();
	msg.ttl()		= 1;
	msg.hop_count()		= 0;