meednode.java

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

			}
		}

		public boolean contactIdle(Contact ct)
		{
			if (!finishedDestinations.contains(ct))
			{
				Iterator<ProtocolStackMessage> it = buffer.iterator();

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

					if (m.getDestNode() == ct.getDest())
					{
						if (ct.sendMessage(m))
						{
							if (m.getSourceNode() == parent && m.getData(MSG_LEFT_SOURCE) == null)
							{
								MEEDDijkstra routing = (MEEDDijkstra) m.getData(MSG_ROUTING);

								if (routing == null)
								{
									routing = parent.topologyAgent.routingCache(m);

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

								Double cost = Double.POSITIVE_INFINITY;

								if (routing != null)
								{
									cost = routing.getCost(m.getDestNode());
								}

								m.storeData(Stats.MSG_SEND_PRED_DELAY, cost);
								m.storeData(MSG_PRED_DELAY, cost);
								m.storeData(Stats.MSG_SEND_TIME, new Double(parent.getNetwork().getCurrentTime()));
							}

							it.remove();
						}

						return true;
					}
				}

				// Remember that we already finished iterating over this
				// destation
				finishedDestinations.add(ct);
			}

			return false;
		}
	}

	public interface MEEDTopologyObserver
	{
		/** This method is called when any change to the topology state occurs. */
		public void topologyChanged();
	}

	public static class MEEDMsgsSender extends EventHandler
	{
		protected HashMap<Contact, ArrayList<ProtocolStackMessage>> msgsToSend = new HashMap<Contact, ArrayList<ProtocolStackMessage>>();

		public MEEDMsgsSender(Integer id)
		{
			super(id);
		}

		protected ArrayList<ProtocolStackMessage> getMsgsToSend(Contact ct)
		{
			ArrayList<ProtocolStackMessage> msgs = msgsToSend.get(ct);

			if (msgs == null)
			{
				msgs = new ArrayList<ProtocolStackMessage>();

				msgsToSend.put(ct, msgs);
			}

			return msgs;
		}

		public boolean contactIdle(Contact ct)
		{
			ArrayList<ProtocolStackMessage> msgs = msgsToSend.get(ct);

			if (msgs != null && msgs.size() > 0)
			{
				if (ct.sendMessage(msgs.remove(0)))
					return true;
			}

			return false;
		}

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

	/** Distributes MEED topology updates. */
	public static class MEEDTopologyEventHandler extends MEEDMsgsSender
	{
		private static int myID = getHandlerID();

		protected TreeNode treeCache = null;

		protected int lastSetHash = 0;

		protected int lastSetSize = 0;

		protected MEEDDijkstra lastR = null;

		protected MEEDNode parent = null;

		protected Network network = null;

		/** Stores the network topology state. */
		protected DTNTopology topology = null;

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

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

		/**
		 * Caches the routing state for efficiency. It only changes when
		 * contacts come up or go down.
		 */
		protected MEEDDijkstra lastRouting = null;

		protected HashMap<Node, MEEDDijkstra> lastRoutingBack = new HashMap<Node, MEEDDijkstra>();

		protected int selfSequence = 0;

		protected MEEDMetric metric = null;

		protected HashSet<Contact> connectedContacts = new HashSet<Contact>();

		protected ArrayList<MEEDTopologyObserver> observers = new ArrayList<MEEDTopologyObserver>();

		/**
		 * Records the contacts that are sending updates to this node.
		 * gettingUpdates contains contacts directed TO this Node (this node is
		 * their destination)
		 */
		protected HashSet<Contact> gettingUpdates = new HashSet<Contact>();

		public boolean isGettingUpdates()
		{
			return gettingUpdates.size() != 0;
		}

		public MEEDTopologyEventHandler(MEEDNode node)
		{
			super(myID);

			this.parent = node;
			this.network = node.getNetwork();
			this.topology = new DTNTopology();

			switch (parent.metricToUse)
			{
				case METRIC_MEED:
					this.metric = new MEEDComputation();
					break;
				case METRIC_LAST_UP:
					this.metric = new LastUpComputation();
					break;
				case METRIC_EWMA:
					this.metric = new MEEDEWMA();
					break;
				case METRIC_WINDOW:
					this.metric = new MEEDWindow();
					break;

				default:
					throw new RuntimeException("Unknown metric!");
			// break
			}
		}

		public void addObserver(MEEDTopologyObserver observer)
		{
			observers.add(observer);
		}

		/**
		 * When the topology changes we invalidate our cache and broadcast the
		 * event to any observers.
		 */
		protected void topologyChanged()
		{
			treeCache = null;

			lastSetHash = 0;
			lastSetSize = 0;
			lastR = null;

			lastRouting = null;
			lastRoutingBack.clear();

			for (Iterator i = observers.iterator(); i.hasNext();)
			{
				((MEEDTopologyObserver) i.next()).topologyChanged();
			}

			// When the topology changes, wake up any idle contacts
			parent.signalAllContactsIdle();
		}

		/**
		 * 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, Double> lastWeights = null;

		/**
		 * Test if the contact link weights have changed enough to create an
		 * update. This compares the current state with the cached state. It
		 * returns true if one of the following is true:
		 * 
		 * 1. A new contact has been detected. 2. A link metric has changed by
		 * more than absoluteThreshold (default = 30 mins). 3. A link metric has
		 * changed, relative to the previous value, by more than (default = 5%).
		 */
		private boolean contactStateChanged(HashMap<Contact, Double> currentState)
		{
			// If this is the first time through, return true
			if (lastWeights == null)
			{
				lastWeights = currentState;
				return true;
			}

			for (Map.Entry<Contact, Double> entry : currentState.entrySet())
			{
				// See if the metric has been updated enough to justify
				// a new update
				Contact ct = entry.getKey();
				Double oldMetric = lastWeights.get(ct);
				if (oldMetric == null)
				{
					// This link previously did not even exist: the state has
					// changed
					return true;
				}

				double newMetric = entry.getValue();
				double absoluteDifference = Math.abs(newMetric - oldMetric);
				if (absoluteDifference > absoluteThreshold)
				{
					return true;
				}

				double relativeDifference = absoluteDifference / oldMetric;
				if (relativeDifference > relativeThreshold)
				{
					return true;
				}
			}

			// None of the values have changed enough
			return false;
		}

		protected MEEDDijkstra getTreeCache(TreeSet<Node> set)
		{
			if (lastSetHash == set.hashCode() && set.size() == lastSetSize && lastR != null)
				return lastR;

			if (false)
			{
				topology.setForbiddenNodes(set);
				MEEDDijkstra r = new MEEDDijkstra(topology, parent, network.getCurrentTime(), null);
				topology.clearForbiddenNodes();

				lastSetHash = set.hashCode();
				lastSetSize = set.size();
				lastR = r;

				return r;
			}

			if (treeCache == null)
			{
				treeCache = new TreeNode();
			}

			Iterator<? extends Node> it = set.iterator();

			if (!it.hasNext())
			{
				assert false;
			}

			TreeNode lastLevel = treeCache;

			while (it.hasNext())
			{
				Node n = it.next();

				if (lastLevel.down == null)
				{
					TreeNode tn = new TreeNode();

					lastLevel.down = new HashMap<Node, TreeNode>(1);
					lastLevel.down.put(n, tn);

					lastLevel = tn;
				}
				else
				{
					TreeNode tn = lastLevel.down.get(n);

					if (tn == null)
					{
						tn = new TreeNode();
						lastLevel.down.put(n, tn);
					}

					lastLevel = tn;
				}
			}

			if (lastLevel.routing == null)
			{
				topology.setForbiddenNodes(set);

				lastLevel.routing = new MEEDDijkstra(topology, parent, network.getCurrentTime(), null);

				topology.clearForbiddenNodes();
			}

			lastSetHash = set.hashCode();
			lastSetSize = set.size();
			lastR = lastLevel.routing;

			return lastLevel.routing;
		}

		public MEEDDijkstra getNormalCache(ProtocolStackMessage forMsg)
		{
			// If we are getting updates, do not let others get the current
			// topology, as it is about to change
			if (isGettingUpdates())
				return null;

			if (lastRouting == null)
			{
				lastRouting = new MEEDDijkstra(topology, parent, network.getCurrentTime(), null);

				if (network.vShouldLog(Verbose.DEBUG1))
					network.vprint("MEED " + lastRouting.toString());
			}

			return lastRouting;
		}

		public MEEDDijkstra routingCache(ProtocolStackMessage forMsg)
		{
			if (forMsg == null)
			{
				return getNormalCache(forMsg);
			}

			TreeSet<Node> set = forMsg.forbiddenNodes();

			if (set == null || set.size() < 1)
			{
				return getNormalCache(forMsg);
			}

			MEEDDijkstra routing = getNormalCache(forMsg);

			if (routing == null)
			{
				return null;
			}

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

			if (route == null)
			{
				return routing;
			}

			Iterator<Contact> it = route.iterator();

			while (it.hasNext())
			{
				if (set.contains(it.next().getDest()))
				{
					// System.out.println("Cache for: " + set);
					return getTreeCache(set);
				}
			}

			return routing;
		}

		public MEEDDijkstra routingBackCache(Node fromNode)
		{
			// If we are getting updates, do not let others get the current
			// topology, as it is about to change
			if (isGettingUpdates())
				return null;

			MEEDDijkstra ret = lastRoutingBack.get(fromNode);

			if (ret == null)
			{
				lastRoutingBack.put(fromNode, new MEEDDijkstra(topology, fromNode, network.getCurrentTime(), null));
			}

			return ret;
		}

		protected boolean receivedProtocolMessage(ProtocolStackMessage msg, Contact contact)
		{
			// Is this a routing message with a routing summary vector?
			@SuppressWarnings("unchecked")
			HashMap<? extends Node, ? extends Integer> routingSummary = (HashMap<? extends Node, ? extends Integer>) msg
					.getData(routingSummaryKey);

			if (routingSummary != null)
			{
				if (!contact.isUp())
					return false;

				// Get the list of updates for the other node
				ArrayList updates = topology.getRoutingUpdates(routingSummary);

				if (topology.needRoutingUpdates(routingSummary))
				{
					if (network.vShouldLog(Verbose.DEBUG1))
						network.vprint("MEED " + this.parent + " needs updates from " + msg.getSourceNode());

					// We need a routing update: record that the routing
					// state is changing
					// Breaks: assert !gettingUpdates.contains(contact);
					gettingUpdates.add(contact);
				}

				// TODO: Include info about buffer space? This is actually
				// more complex than it seems, but maybe a
				// naive version will still improve things?
				if (updates.size() > 0)
				{
					// Package this up in an update message
					// base size is 4 bytes (number of updates)
					int size = 4;

					for (Iterator i = updates.iterator(); i.hasNext();)
					{
						size += 12; // add the "node id, sequence number,
						// length
						// of contact information"
						size += 8 * ((RoutingUpdate) i.next()).contactWeights.size(); // 4
						// bytes
						// other
						// node
						// id,
						// 4
						// bytes
						// contact
						// weight
					}

					ProtocolStackMessage updateMsg = new ProtocolStackMessage(network.getNextRoutingMessageId(),
							network.getCurrentTime(), parent, msg.getSourceNode(), 0, size, true);

					updateMsg.setProtocolID(PROTO_MEED_ID);
					updateMsg.setIsRoutingMessage(true);
					// ~ Stats.add( requestMsg );
					updateMsg.storeData(routingUpdateKey, updates);

					Contact ct = contact.getReverseContact();
					getMsgsToSend(ct).add(updateMsg);

					parent.signalContactIdle(ct);
				}

				if (network.vShouldLog(Verbose.DEBUG1))
					network.vprint("MEED " + this.parent + " got summary vector from " + msg.getSourceNode());

				return true;
			}

			// Is this a message with updates?
			ArrayList updates = (ArrayList) msg.getData(routingUpdateKey);

			if (updates != null)
			{
				// Mark that we are finished updating the routing for this
				// node
				if (network.vShouldLog(Verbose.DEBUG1))
					network.vprint("MEED " + this.parent + " finished getting updates from " + msg.getSourceNode());

				gettingUpdates.remove(contact);

				// Process the updates
				boolean didUpdate = false;

				for (Iterator i = updates.iterator(); i.hasNext();)
				{
					// Record if this update actually did something
					boolean updated = topology.processUpdate((RoutingUpdate) i.next());

					if (network.vShouldLog(Verbose.DEBUG1))
						network.vprint("MEED ProcessedUpdate: " + updated);