meednode.java

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

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

				if (h.shouldAdvertise(time))
				{
					double newMetric = h.metric(time);

					// ~ System.out.println( "Computing metric for " + ct + " =
					// " + h.metric(time ) );
					retval.put(ct, newMetric);
				}
			}

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

	/** A simple metric that uses the last time we saw a contact. */
	public static class LastUpComputation implements MEEDMetric
	{
		private HashMap<Contact, Double> lastUp = new HashMap<Contact, Double>();

		public void contactUp(Contact ct, double time)
		{
			lastUp.put(ct, -1.0);
		}

		public void contactDown(Contact ct, double time)
		{
			assert lastUp.containsKey(ct);
			lastUp.put(ct, time);
		}

		/** Returns a snapshot of the current routing state. */
		public HashMap<Contact, Double> contactWeights(double time)
		{
			HashMap<Contact, Double> snapshot = new HashMap<Contact, Double>();
			for (Map.Entry<Contact, Double> entry : lastUp.entrySet())
			{
				Contact key = entry.getKey();
				double value = entry.getValue();

				if (value == -1)
				{
					snapshot.put(key, 0.0);
				}
				else
				{
					assert value <= time;
					snapshot.put(key, time - value);
				}
			}

			return snapshot;
		}
	}

	/** An exponentially weighted moving average version of the MEED metric. */
	public static class MEEDEWMA implements MEEDMetric
	{
		private final static double ALPHA = 0.9;

		/** Stores the current disconnection and connection averages. */
		private final static class CostEstimate
		{
			private double connectAvg = Double.NEGATIVE_INFINITY;

			private double disconnectAvg = Double.NEGATIVE_INFINITY;

			private double lastEvent;

			private final static byte STATE_UP = 1;

			private final static byte STATE_DOWN = 2;

			private byte state = STATE_UP;

			/** Create a new EWMA estimate that is up at time. */
			public CostEstimate(double time)
			{
				lastEvent = time;
				assert state == STATE_UP;
			}

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

				// The contact just came up: recompute the disconnect average
				double disconnected = time - lastEvent;
				assert disconnected > 0;

				if (disconnectAvg == Double.NEGATIVE_INFINITY)
				{
					// This is the first complete disconnect cycle
					disconnectAvg = disconnected;
				}
				else
				{
					disconnectAvg = ALPHA * disconnectAvg + (1 - ALPHA) * disconnected;
				}

				lastEvent = time;
				state = STATE_UP;
			}

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

				double connected = time - lastEvent;
				assert connected > 0;

				if (connectAvg == Double.NEGATIVE_INFINITY)
				{
					// This is the first complete connect cycle
					connectAvg = connected;
				}
				else
				{
					connectAvg = ALPHA * connectAvg + (1 - ALPHA) * connected;
				}

				lastEvent = time;
				state = STATE_DOWN;
			}

			private double computeMetric(double connect, double disconnect)
			{
				return disconnect * disconnect / 2.0 / (disconnect + connect);
			}

			public double metric(double time)
			{
				double lastEventTime = time - lastEvent;
				double disconnect = disconnectAvg;

				if (connectAvg == Double.NEGATIVE_INFINITY)
				{
					// This is the first up time: return a zero metric
					assert state == STATE_UP;
					return 0;
				}

				if (disconnectAvg == Double.NEGATIVE_INFINITY)
				{
					// This is the first down time: return a current metric
					assert state == STATE_DOWN;
					assert connectAvg > 0;
					disconnect = lastEventTime;
				}

				double metric = computeMetric(connectAvg, disconnect);

				if (lastEventTime > 0)
				{
					if (state == STATE_UP && lastEventTime > 0)
					{
						// Take the minimum of the current metric and the most
						// up to date metric
						double connect = ALPHA * connectAvg + (1 - ALPHA) * lastEventTime;
						metric = Math.min(computeMetric(connect, disconnect), metric);
					}
					else
					{
						assert state == STATE_DOWN;
						// Take the maximum of the current metric and the most
						// up to date metric
						disconnect = ALPHA * disconnect + (1 - ALPHA) * lastEventTime;
						metric = Math.max(computeMetric(connectAvg, disconnect), metric);
					}
				}

				return metric;
			}
		}

		private HashMap<Contact, CostEstimate> estimates = new HashMap<Contact, CostEstimate>();

		public void contactUp(Contact ct, double time)
		{
			CostEstimate e = estimates.get(ct);
			if (e == null)
			{
				// No current estimate: add one
				e = new CostEstimate(time);
				estimates.put(ct, e);
			}
			else
			{
				e.up(time);
			}
		}

		public void contactDown(Contact ct, double time)
		{
			CostEstimate e = estimates.get(ct);
			assert e != null;

			e.down(time);
		}

		/** Returns a snapshot of the current routing state. */
		public HashMap<Contact, Double> contactWeights(double time)
		{
			HashMap<Contact, Double> snapshot = new HashMap<Contact, Double>();
			for (Map.Entry<Contact, CostEstimate> entry : estimates.entrySet())
			{
				snapshot.put(entry.getKey(), entry.getValue().metric(time));
			}

			return snapshot;
		}
	}

	/** A sliding window version of the MEED metric. */
	public static class MEEDWindow implements MEEDMetric
	{
		// Window size = 2 days
		private final static double PERIOD = 2 * 24 * 60 * 60;

		private final static byte STATE_UP = 1;

		private final static byte STATE_DOWN = 2;

		/** Type for events. */
		private final static class ContactEvent
		{
			private byte state;

			private double time;

			public ContactEvent(byte state, double time)
			{
				assert state == STATE_UP || state == STATE_DOWN;

				this.state = state;
				this.time = time;
			}

			public double time()
			{
				return time;
			}

			public byte state()
			{
				return state;
			}
		}

		/** Stores the current disconnection and connection information. */
		private final static class CostEstimate
		{
			private ArrayList<ContactEvent> events = new ArrayList<ContactEvent>();

			/** Create a new EWMA estimate that is up at time. */
			public CostEstimate(double time)
			{
				events.add(new ContactEvent(STATE_UP, time));
			}

			private ContactEvent lastEvent()
			{
				return events.get(events.size() - 1);
			}

			/** Delete all events that end before timeLimit. */
			private void trimEventsBefore(double timeLimit)
			{
				int i = 0;
				while (i < events.size() - 1)
				{
					double endTime = events.get(i + 1).time();

					if (endTime > timeLimit)
					{
						// This event ends AFTER the time limit:
						// We need to keep it, but delete everything before
						break;
					}

					i += 1;
				}

				// We need to delete all items from 0 to i-1
				events.subList(0, i).clear();
			}

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

				events.add(new ContactEvent(STATE_UP, time));
				trimEventsBefore(time - PERIOD);
			}

			private double lastDownMetric = Double.NEGATIVE_INFINITY;

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

				events.add(new ContactEvent(STATE_DOWN, time));
				trimEventsBefore(time - PERIOD);

				// Record the last down metric, because this is the worst case
				// estimate
				lastDownMetric = computeMetric(time);
			}

			private double computeMetric(double now)
			{
				double beginningOfTime = events.get(0).time();
				double disconnectSquared = 0;
				for (int i = 0; i < events.size(); ++i)
				{
					ContactEvent e = events.get(i);
					if (e.state() == STATE_DOWN)
					{
						double start = e.time();
						double end = -1;

						// This is a disconnection interval
						if (i == events.size() - 1)
						{
							// This is the very last interval
							end = now;
						}
						else
						{
							end = events.get(i + 1).time();
						}

						double disconnect = end - start;
						assert disconnect >= 0;
						disconnectSquared += disconnect * disconnect;
					}
				}
				return disconnectSquared / 2.0 / (now - beginningOfTime);
			}

			public double metric(double time)
			{
				double metric = computeMetric(time);

				if (lastEvent().state() == STATE_DOWN)
				{
					assert lastDownMetric >= 0;
					// Take the maximum of the last down metric and the most up
					// to date metric
					metric = Math.max(metric, lastDownMetric);
				}

				return metric;
			}
		}

		private HashMap<Contact, CostEstimate> estimates = new HashMap<Contact, CostEstimate>();

		public void contactUp(Contact ct, double time)
		{
			CostEstimate e = estimates.get(ct);
			if (e == null)
			{
				// No current estimate: add one
				e = new CostEstimate(time);
				estimates.put(ct, e);
			}
			else
			{
				e.up(time);
			}
		}

		public void contactDown(Contact ct, double time)
		{
			CostEstimate e = estimates.get(ct);
			assert e != null;

			e.down(time);
		}

		/** Returns a snapshot of the current routing state. */
		public HashMap<Contact, Double> contactWeights(double time)
		{
			HashMap<Contact, Double> snapshot = new HashMap<Contact, Double>();
			for (Map.Entry<Contact, CostEstimate> entry : estimates.entrySet())
			{
				snapshot.put(entry.getKey(), entry.getValue().metric(time));
			}

			return snapshot;
		}
	}

	public static class ACKHandler extends EventHandler
	{
		protected static int PROTO_ACK_ID = ProtocolStackMessage.getNewProtocolID();

		protected static Message.Header ACK_MSG_ID = new Message.Header();

		// TODO - Implement Expiration of ACKs
		protected static Message.Header ACK_EXPIRY_TIME = new Message.Header();

		protected static int ACK_EVENT = 0;

		protected static int myID = getHandlerID();

		protected MEEDNode parent;

		protected int acksSize = 0;

		protected HashMap<Integer, ProtocolStackMessage> ackIDs = new HashMap<Integer, ProtocolStackMessage>();

		protected HashSet<Integer> sawAcksFor = new HashSet<Integer>();

		protected ArrayList<ProtocolStackMessage> acks = new ArrayList<ProtocolStackMessage>();

		protected HashMap<Integer, ProtocolStackMessage> buffer = new HashMap<Integer, ProtocolStackMessage>();

		// Only for statistics
		protected HashMap<Integer, ProtocolStackMessage> allOrgs = new HashMap<Integer, ProtocolStackMessage>();

		protected HashMap<Contact, HashSet<Integer>> acksForContacts = new HashMap<Contact, HashSet<Integer>>();

		protected BasicEvent nextACKEvent = null;

		protected double nextEventTime = Double.MAX_VALUE;

		protected ACKEventSender myEventSender = null;

		public ACKHandler(MEEDNode node)
		{
			super(myID);
			parent = node;
			myEventSender = new ACKEventSender(parent.getNetwork(), this);
		}

		public void receiveACKEvent(Event ev)
		{
			assert ev == nextACKEvent;
			assert ev.getTime() == parent.getNetwork().getCurrentTime();

			nextACKEvent = null;
			nextEventTime = Double.MAX_VALUE;
			double nextTime = Double.MAX_VALUE;

			double curTime = ev.getTime();

			Iterator<ProtocolStackMessage> it = buffer.values().iterator();
			ArrayList<ProtocolStackMessage> toAccept = new ArrayList<ProtocolStackMessage>();

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

				double expiry = ((Double) m.getData(MSG_RESEND_TIME)).doubleValue();

				if (expiry <= curTime)
				{
					toAccept.add(m);
					it.remove();

					if (parent.orgsUseBuffer)
					{
						parent.freeCapacity(m);
						parent.mySize -= m.getLength();
					}
				}
				else if (expiry < nextTime)
				{
					nextTime = expiry;
				}
			}

			if (toAccept.size() > 0)
			{
				it = toAccept.iterator();

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

					if (parent.getNetwork().vShouldLog(Verbose.INFO))
						parent.getNetwork().vprint("RE-INSERTING Message without ACK on time: " + m + " in " + parent);

					parent.acceptMessage(m, null, m.getLength());
				}
			}

			assert nextEventTime == Double.MAX_VALUE;
			assert nextACKEvent == null;

			if (nextTime < parent.getNetwork().getCurrentTime())
			{
				setupEvent(parent.getNetwork().getCurrentTime());
			}
			else
			{
				setupEvent(nextTime);
			}
		}

		protected void setupEvent(double checkTime)
		{
			if (checkTime < nextEventTime)
			{
				if (nextACKEvent != null)
					myEventSender.cancelEvent(nextACKEvent);

				nextEventTime = checkT