.#meednode.java.1.13

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

		{
			this.parent.getNetwork().vprint(Verbose.DEBUG1, "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))
			{
				// ~ System.out.println( Simulator.time() + " routing is not
				// getting updates, we are going to do iterator stuff now" );
				finishedWithDestinations.add(ct);

				outboundQueues.appendIterator(ct, new MEEDRoutingIterator(ct));
				// Directly handle the event with the outboundQueues
				// TODO - check - appendIterator already called
				// signalIdleContact(ct)
				// outboundQueues.contactIdle(ct);
			}

			return true;
		}

		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>();
		}

		public void notifyNewMessage(Message msg)
		{
			Dijkstra<Node, Contact, Message> routing = topology.routingCache();

			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)
			{
				this.parent.getNetwork().vprint(Verbose.ERR,
						"MEED: NO ROUTE for " + msg + " from " + this.parent + " to " + msg.getDestNode());
			}

			// 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.signalIdleContact(nextBestHop);
				}

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

		// TODO - change: localMsg -> accept(Remote or Routing)Message
		// public boolean handleLocalMessage(Message m, Contact s)
		public boolean acceptMessage(Message msg, Contact ct, int size)
		{
			// System.out.println("acceptMessage in " + this);
			return false;
		}

		public void contactUp(Contact ct)
		{
		}

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

		/**
		 * This class iterates over all the messages in the queue, returning the
		 * first one that should be sent over the specified contact.
		 */
		private class MEEDRoutingIterator implements Iterator<Message>
		{
			private Contact forContact = null;

			public MEEDRoutingIterator(Contact forCon)
			{
				forContact = forCon;
			}

			private Message next = null;

			private Message findNext()
			{
				// It is possible that we could call hasNext(), and then remove
				// a message from the queue
				// and then actually call next, and get a message that does not
				// exist
				// to solve this, we verify that the message is in the queue
				// everytime
				if (next == null || !buffer.contains(next))
				{
					for (Iterator<Message> i = buffer.iterator(); i.hasNext();)
					{
						Message m = i.next();
						ArrayList<Contact> route = topology.routingCache().routeTo(m.getDestNode());

						// 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) == forContact)
						{
							// This is our next object
							next = m;
							break;
						}
					}
				}

				return next;
			}

			public boolean hasNext()
			{
				if (topology.isGettingUpdates())
				{
					// No routing is permitted while getting an update: the
					// iterator becomes invalid
					return false;
				}

				// ~ System.out.println( "Routing iterator hasNext = " +
				// (findNext() != null) + " queue length = " +
				// primaryQueue.size() );
				return (findNext() != null);
			}

			public Message next()
			{
				if (topology.isGettingUpdates())
				{
					assert (false);
					// If an exception is thrown here, it is "user error": Call
					// hasNext() before calling next
					throw new NoSuchElementException();
				}

				Message ret = findNext();

				if (ret == null)
					throw new NoSuchElementException();

				next = null;

				// Leave the message in the primary queue
				// It will not get sent twice, due to the routing protocols
				// TODO: What happens if reactive fragmentation occurs?
				// The message is placed back at the head of the queue if
				// delivery fails
				// NOTE: We do not decrement primaryQueueOccupied because the
				// message is
				// still stored in memory on this node, it just should not be
				// routed through other contacts
				boolean result = buffer.remove(ret);

				assert result;

				return ret;
			}

			public void remove()
			{
				// TODO - But ProtocolStack tries to do this.
				// It doesn't hurt, as the message was removed in last next()
				// But Maybe this is better to be left here, and not to remove
				// messages in next() method?
				// assert (false); // don't do this
			}
		}
	}

	public void messageSent(Message msg, Contact ct, int sizeSent)
	{
		super.messageSent(msg, ct, sizeSent);

		if (!msg.isRoutingMessage())
		{
			if (sizeSent < msg.getLength())
			{
				// The send failed: add the message back in the buffer
				primaryQueue.add(msg);
			}
			else
			{
				network.vprint(Verbose.DEBUG1, "MEED " + this + " sent: " + msg + "; size: " + msg.getLength()
						+ "; Buffer: " + (primaryQueueOccupied - sizeSent));

				// ~ boolean found = primaryQueue.remove( msg );
				// There actually is a tiny chance that this message could get
				// sent out another
				// link, while this is happening. This will assert here if that
				// happens
				// ~ assert ( found );

				// The message was sent: free up buffer space
				primaryQueueOccupied -= sizeSent;
				assert (primaryQueueOccupied >= 0);
			}
		}
	}

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

		/**
		 * Used to determine when the weights have changed enough to send an
		 * update.
		 */
		// TODO: Decide what is a good metric here: absolute or relative
		// thresholds? Time since last update? All of the above?
		HashMap<Contact, Float> lastWeights = null;

		static final float percentageThreshold = 0.05f;

		static final float absoluteThreshold = 60;

		public MEEDComputation()
		{
		}

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

			float totalDowntime;

			float totalDowntimeSquared;

			float lastConnected;

			// ~ 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(float time)
			{
				firstContactTime = time;
				state = STATE_UP;
				// ~ numConnections = 1;
			}

			public void up(float time)
			{
				assert (state == STATE_DOWN);
				assert (time >= lastConnected);
				float downtime = time - lastConnected;
				state = STATE_UP;

				totalDowntime += downtime;
				totalDowntimeSquared += downtime * downtime;
				// ~ numConnections += 1;
			}

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

				lastConnected = time;
			}

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

				// If we are currently disconnected, take that into account
				float currentDisconnectedTime = 0;
				float currentTotalDowntime = totalDowntime;
				float currentDowntimeSquared = totalDowntimeSquared;
				if (state == STATE_DOWN)
				{
					currentDisconnectedTime = time - lastConnected;
					currentTotalDowntime += currentDisconnectedTime;
					currentDowntimeSquared += currentDisconnectedTime * currentDisconnectedTime;
				}

				// If this contact has never been down, then the estimate is
				// zero
				if (currentTotalDowntime == 0)
					return 0;

				float totalTime = time - firstContactTime;
				float probDown = currentTotalDowntime / totalTime;
				assert (0.0 <= probDown && probDown < 1.0);

				return probDown * 0.5f * currentDowntimeSquared / currentTotalDowntime;
			}

			/**
			 * 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(float time)
			{
				// TODO:Should we avoid advertising routes until they are
				// somewhat "stable"?
				if (time == firstContactTime)
					// TODO - changed false -> true for testing!
					// TODO
					// TODO
					// TODO
					return true;
				else
					return true;

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

			public ContactHistory clone()
			{
				try
				{
					return (ContactHistory) super.clone();
				}
				catch (Throwable e)
				{
					return null;
				}
			}

			public String toString()
			{
				return "(History (State: " + state + "); Times: FirstUp: " + firstContactTime + "; LastUp: "
						+ lastConnected + "; TotalDown: " + totalDowntime + "; 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, float 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, float 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 float metric(Contact ct, float time)
		{
			ContactHistory h = history.get(ct);

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

		/** Returns a snapshot of the current routing state. */
		public HashMap<Contact, Float> contactWeights(float time)
		{
			// First time through: We have changed (no previous history)
			// otherwise, lastWeights is *not* null, and therefore we have
			// changed
			boolean hasChanged = (lastWeights == null);

			HashMap<Contact, Float> retval = new HashMap<Contact, Float>();

			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().clone();

				// System.out.println("Checking: " + ct + " = " + h + ";
				// ShouldAdvertise(" + time + "): "
				// + h.shouldAdvertise(time));

				if (h.shouldAdvertise(time))
				{
					float newMetric = h.metric(time);
					if (!hasChanged)
					{
						// See if the metric has been updated enough to justify
						// a new update
						Float oldMetric = lastWeights.get(ct);

						if (oldMetric == null)
						{
							// This link previously did not even exist:
							// definitely update this
							hasChanged = true;
						}
						else
						{
							float absoluteDifference = Math.abs(newMetric - oldMetric.floatValue());

							if (absoluteDifference > absoluteThreshold
									|| absoluteDifference / oldMetric.floatValue() > percentageThreshold)
							{
								hasChanged = true;
							}
						}
					}
					// ~ System.out.println( "Computing metric for " + ct + " =
					// " + h.metric(time ) );
					retval.put(ct, newMetric);
				}
			}

			// System.out.println("Weights: " + retval);

			if (hasChanged)
			{
				lastWeights = retval;
				return retval;
			}
			else
			{
				return null;
			}
		}
	}
}