meednode.java

DTNSim2 is a simulator for Delay-Tolerant Networks (DTNs) written in Java. It is based on Sushant Ja

		{
			if (this.parent.getNetwork().vShouldLog(Verbose.DEBUG1))
				this.parent.getNetwork().vprint("MEED " + this.parent + " MEEDRouting idleContact: " + ct);

			// The MEED topology agent should prevent us from getting
			// idleContact if it is busy getting updates
			assert !topology.isGettingUpdates();

			// If we are not busy getting updates from anyone, and we have not
			// yet finished with this destination,
			// place an iterator
			if (!finishedWithDestinations.contains(ct))
			{
				Iterator<ProtocolStackMessage> i = buffer.iterator();

				while (i.hasNext())
				{
					ProtocolStackMessage m = i.next();

					Node dest = m.getDestNode();
					MEEDDijkstra routing = (MEEDDijkstra) m.getData(MSG_ROUTING);

					if (routing == null)
					{
						routing = topology.routingCache(m);

						if (parent.routingPolicy != ROUTING_POLICY_TOPOLOGY)
						{
							m.storeData(MSG_ROUTING, routing);
						}
					}

					ArrayList<Contact> route = routing.routeTo(dest);

					// System.out.println("Route: " + route);

					// If this route uses our contact as the next hop,
					// ~ System.out.println( "route size " + route.size() );
					// ~ if ( route.size() > 0 ) System.out.println( "next
					// hop = " + route.get(0) + " cost = " +
					// routingCache().getCost( m.dstNode() ) );

					if (route != null && route.size() > 0 && route.get(0) == ct && parent.allowSend(m, ct))
					{
						i.remove();

						// Store predicted delivery time (not to be used by
						// other nodes, but maybe by other protocols/layers
						// of this node. And statistics.

						Double cost = routing.getCost(dest);

						if (m.getSourceNode() == parent && m.getData(MSG_LEFT_SOURCE) == null)
						{
							m.storeData(Stats.MSG_SEND_PRED_DELAY, new Double(cost));
							m.storeData(Stats.MSG_SEND_TIME, new Double(parent.getNetwork().getCurrentTime()));
						}

						m.storeData(MSG_PRED_DELAY, new Double(cost));

						if (parent.useACK && m.getSourceNode() == parent)
						{
							double roundTripTime;

							if (parent.rndRetrans)
							{
								roundTripTime = parent.rndMin
										+ (parent.rnd.nextDouble() * (parent.rndMax - parent.rndMin));
							}
							else
							{
								roundTripTime = cost * parent.ackTripModif;

								MEEDDijkstra routingBack = topology.routingBackCache(dest);
								ArrayList<Contact> routeBack = null;

								if (routingBack != null)
									routeBack = routingBack.routeTo(parent);

								if (routeBack != null && routeBack.size() > 0)
								{
									roundTripTime += parent.ackBackTripModif * routingBack.getCost(parent);
								}
								else
								{
									roundTripTime *= parent.ackBothTripModif;
								}

								if (roundTripTime < parent.msgMinResendTime)
									roundTripTime = parent.msgMinResendTime;

								roundTripTime += parent.getNetwork().getCurrentTime();
							}

							if (parent.getNetwork().vShouldLog(Verbose.NOTIFY))
								parent.getNetwork().vprint("RESEND_TIME for " + m + " set to " + roundTripTime);

							m.storeData(MSG_RESEND_TIME, new Double(roundTripTime));
						}

						ct.sendMessage(m);

						assert !ct.isIdle();
						return true;
					}
				}

				finishedWithDestinations.add(ct);
			}

			return false;
		}

		public void topologyChanged()
		{
			// When the topology changes, we forget everything we knew in the
			// past wake up any idle contacts, because we need to do routing
			// again
			finishedWithDestinations = new HashSet<Contact>();
		}

		/** Should we accept the specified message? */
		public boolean acceptMessage(ProtocolStackMessage msg, Contact source, int size)
		{
			if (msg.isRoutingMessage() || size < msg.getLength())
			{
				// This agent doesn't handle routing messages
				// we also ignore incomplete messages.
				return false;
			}

			assert msg.getDestNode() != parent : "acceptMessage called for data message for this node in " + this;

			if (parent.hasACKForMsg(msg))
			{
				// This node has ACK for this message - we don't have to accept
				// it. But we say that we accepted it...
				return true;
			}

			if (source == null && msg.getProtocolID() == ProtocolStackNode.ProtocolStackMessage.PROTO_NONE)
			{
				msg.setProtocolID(PROTO_MEED_ID);

				// 0, maybe something different? Like 4 - one field with
				// expiration time if we ever need it?
				msg.setProtocolLength(0);
			}
			else if (msg.getProtocolID() != PROTO_MEED_ID)
			{
				return false;
			}

			// System.out.println("acceptMessage in " + this);

			// We are willing to store any message, as long as we have space in
			// the buffer:
			if (!parent.canAllocateCapacity(msg, handlerID))
			{
				if (parent.mySize != parent.bufferCapacity())
				{
					if (parent.getNetwork().vShouldLog(Verbose.WARN))
						parent.getNetwork().vprint(
								"MEED CAN'T ALLOCATE BUF; mySize: " + parent.mySize + " bufferCapacity: "
										+ parent.bufferCapacity());
				}

				parent.statMsgEntry.setup(msg, parent.network.getCurrentTime(), Stats.MSG_DROPPED_OOBUF);
				parent.network.stats().notify(parent.statMsgEntry);

				return false;
			}

			if (source != null)
			{
				if (parent.noBacktracking)
				{
					msg.createForbiddenNodes();
					msg.forbiddenNodes().clear();
					msg.forbiddenNodes().add(source.getSource());
				}

				msg.storeData(MSG_LAST_NODE, source.getSource());
			}

			// If routing policy is "Create" and we don't have any routing set
			// yet, or routing policy ise "accept" (and we don't care if we have
			// it already)
			if ((parent.routingPolicy == ROUTING_POLICY_CREATE && msg.getData(MSG_ROUTING) == null)
					|| parent.routingPolicy == ROUTING_POLICY_ACCEPT)
			{
				MEEDDijkstra routing = topology.routingCache(msg);

				if (routing != null)
				{
					msg.storeData(MSG_ROUTING, routing);
				}
				else if (parent.routingPolicy == ROUTING_POLICY_ACCEPT)
				{
					msg.removeData(MSG_ROUTING);
				}
			}

			parent.allocateCapacity(msg, handlerID);

			buffer.add(msg);
			parent.mySize += msg.getLength();

			// Notify the meed routing agent that a new message is available
			// It will handle sending new updates out to other nodes
			finalAgent.notifyNewMessage(msg);
			notifyNewMessage(msg);

			return true;
		}

		public void removeMessageCopies(Integer id)
		{
			int i = id.intValue();
			Iterator<ProtocolStackMessage> it = buffer.iterator();

			while (it.hasNext())
			{
				ProtocolStackMessage m = it.next();

				if (m.getId() == i)
				{
					it.remove();

					if (parent.getNetwork().vShouldLog(Verbose.INFO))
						parent.getNetwork().vprint("Removing MEED copy of ACKed message " + m);

					parent.freeCapacity(m);
					parent.mySize -= m.getLength();
				}
			}
		}

		public boolean messageSent(ProtocolStackMessage msg, Contact ct, int sizeSent)
		{
			if (!msg.isRoutingMessage() && msg.getProtocolID() == PROTO_MEED_ID)
			{
				if (sizeSent < msg.getLength() && !parent.hasACKForMsg(msg))
				{
					// The send failed: add the message back in the buffer
					buffer.add(msg);
				}
				else
				{
					if (parent.network.vShouldLog(Verbose.DEBUG1))
						parent.network.vprint("MEED " + parent + " sent: " + msg + "; size: " + msg.getLength()
								+ "; BufferAvail: " + parent.availableCapacity());

					// The message was sent (or in the meantime we received
					// ack): free up buffer space
					parent.freeCapacity(msg);
					parent.mySize -= msg.getLength();

					if (msg.getSourceNode() == parent && msg.getData(MSG_LEFT_SOURCE) == null)
					{
						msg.storeData(MSG_LEFT_SOURCE, new Integer(1));
					}
				}
			}

			// We don't block messageSent notify :)
			return false;
		}

		public void notifyNewMessage(ProtocolStackMessage msg)
		{
			MEEDDijkstra routing = topology.routingCache(msg);

			if (routing == null)
			{
				// Don't bother doing anything if the topology is being updated
				assert topology.isGettingUpdates();

				return;
			}

			ArrayList<Contact> route = routing.routeTo(msg.getDestNode());

			if (route == null)
			{
				if (this.parent.getNetwork().vShouldLog(Verbose.ERR))
					this.parent.getNetwork().vprint(
							"MEED: NO ROUTE for " + msg + " from " + this.parent + " to " + msg.getDestNode());

				if (msg.getData(Stats.MSG_CREATE_PRED_DELAY) == null)
				{
					msg.storeData(Stats.MSG_CREATE_PRED_DELAY, new Double(Double.POSITIVE_INFINITY));
				}
			}

			// If there is a route ...
			if (route != null && route.size() > 0)
			{
				// ... go mark the destination as no longer "finished"
				// this way, the next time it is idle, the messages will be sent
				// out
				Contact nextBestHop = route.get(0);

				if (finishedWithDestinations.remove(nextBestHop))
				{
					// If we we already finished with this contact, go check if
					// this contact is idle

					parent.signalContactIdle(nextBestHop);
				}

				if (msg.getData(Stats.MSG_CREATE_PRED_DELAY) == null)
				{
					double cost = routing.getCost(msg.getDestNode());

					msg.storeData(Stats.MSG_CREATE_PRED_DELAY, new Double(cost));
				}

				if (this.parent.getNetwork().vShouldLog(Verbose.DEBUG1))
					this.parent.getNetwork().vprint(
							"MEED " + this.parent + " MEEDRouting notifyNewMessage: " + msg + "; NextHop: "
									+ nextBestHop);
			}
		}

		public void contactDown(Contact ct)
		{
			finishedWithDestinations.remove(ct);
		}
	}

	public interface MEEDMetric
	{
		public void contactUp(Contact ct, double time);

		public void contactDown(Contact ct, double time);

		public HashMap<Contact, Double> contactWeights(double time);
	}

	/** This class computes the MEED metric. */
	public static class MEEDComputation implements MEEDMetric
	{
		/** Maps contacts to ContactHistory objects. */
		private HashMap<Contact, ContactHistory> history = new HashMap<Contact, ContactHistory>();

		/** Stores the history for a single contact. */
		private class ContactHistory
		{
			double firstContactTime;

			double totalDowntimeSquared;

			double lastConnected;

			double lastDownMetric;

			// ~ int numConnections = 0;

			private int state = 0;

			private static final int STATE_UP = 1;

			private static final int STATE_DOWN = 2;

			/** Creates a contact that is currently up. */
			public ContactHistory(double time)
			{
				firstContactTime = time;
				state = STATE_UP;
				// ~ numConnections = 1;
			}

			public void up(double time)
			{
				assert (state == STATE_DOWN);
				assert time > lastConnected;

				double downtime = time - lastConnected;
				state = STATE_UP;
				totalDowntimeSquared += downtime * downtime;
				// ~ numConnections += 1;
			}

			public void down(double time)
			{
				assert (state == STATE_UP);
				assert (time > lastConnected);

				// Record the metric at this point: the MEED value can
				// *decrease*
				// after a connection goes down, so we need to take the max of
				// the
				// current metric and this value
				lastDownMetric = metric(time);

				state = STATE_DOWN;
				lastConnected = time;
			}

			public double metric(double time)
			{
				assert (time >= lastConnected);

				// If we are currently disconnected, take that into account
				double currentTotalTime = time - firstContactTime;
				double currentDowntimeSquared = totalDowntimeSquared;
				if (state == STATE_DOWN)
				{
					double currentDisconnectedTime = time - lastConnected;
					currentDowntimeSquared += currentDisconnectedTime * currentDisconnectedTime;

					double metric = currentDowntimeSquared / 2.0 / currentTotalTime;

					// Just after a disconnection the "current" metric tends to
					// decrease.
					// This fixes that problem
					return Math.max(metric, lastDownMetric);
				}

				return currentDowntimeSquared / 2.0 / currentTotalTime;
			}

			/**
			 * This method returns true if the contact should be advertised to
			 * other nodes. For the moment, the only restriction is that it
			 * cannot be a brand new contact.
			 */
			public boolean shouldAdvertise(double time)
			{
				// TODO:Should we avoid advertising routes until they are
				// somewhat "stable"?
				if (time == firstContactTime)
					return false;
				else
					return true;

				// ~ System.out.println( "shouldAdvertise time = " + time + "
				// first contact = " + firstContactTime );
				// ~ return true;
			}

			public String toString()
			{
				return "(History (State: " + state + "); Times: FirstUp: " + firstContactTime + "; LastUp: "
						+ lastConnected + "; totalDown^2: " + totalDowntimeSquared + ")";
			}
		}

		/** Returns an Iterator over all contacts that are known. */
		public Iterator<Contact> contacts()
		{
			return history.keySet().iterator();
		}

		public void contactUp(Contact ct, double time)
		{
			ContactHistory h = history.get(ct);

			if (h != null)
			{
				h.up(time);
			}
			else
			{
				h = new ContactHistory(time);
				history.put(ct, h);
			}

			// System.out.println("History: " + history);
		}

		public void contactDown(Contact ct, double time)
		{
			ContactHistory h = history.get(ct);

			// UGH: When the simulator first creates a contact that is down, it
			// sends
			// the "closeContact" message to the Node. This is bad, but non
			// trival to fix
			if (h == null)
				return;

			// IGNORE THIS:
			// If the contact went down, it should have gone up
			// if it went up, we should know about it
			// if we know about it, h will not be null
			// ~ assert ( h != null );

			h.down(time);
		}

		public double metric(Contact ct, double time)
		{
			ContactHistory h = history.get(ct);

			if (h != null)
			{
				return h.metric(time);
			}
			else
			{
				// We do not know about this contact
				assert (false);
				return Double.POSITIVE_INFINITY;
			}
		}

		/** Returns a snapshot of the current routing state. */
		public HashMap<Contact, Double> contactWeights(double time)
		{
			HashMap<Contact, Double> retval = new HashMap<Contact, Double>();

			for (Iterator<Map.Entry<Contact, ContactHistory>> i = history.entrySet().iterator(); i.hasNext();)
			{
				Map.Entry<Contact, ContactHistory> entry = i.next();
				Contact ct = entry.getKey();
				ContactHistory h = entry.getValue();