.#meednode.java.1.41

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

				// 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;

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

					didUpdate = didUpdate || updated;
				}

				// All other nodes that are currently connected had the same
				// topology state as this node.
				// They need this update as well. Flood it to all the other
				// contacts
				if (didUpdate)
				{
					for (Iterator<Contact> i = connectedContacts.iterator(); i.hasNext();)
					{
						Contact c = i.next();
						// If this is a different contact than this message
						// came from
						if (c.getDest() != contact.getSource())
						{
							// TODO: Should the src be this node, or the
							// original source? Does it matter?
							ProtocolStackMessage m = new ProtocolStackMessage(network.getNextRoutingMessageId(),
									network.getCurrentTime(), parent, c.getDest(), 0, msg.getProtocolLength(), true);

							m.setProtocolID(PROTO_MEED_ID);
							m.storeData(routingUpdateKey, updates);

							getMsgsToSend(c).add(0, m);

							parent.signalContactIdle(c);
						}
					}
				}

				if (!isGettingUpdates())
				{
					// Our routing state is now completely up to date:
					// Signal that the topology has changed
					// this will signal all relevant routing agents to do
					// their thing. We then wake up all the idle contacts

					if (network.vShouldLog(Verbose.DEBUG1))
						network.vprint("MEED " + this.parent
								+ " - routing state has been updated - signalling all contacts idle.");

					topologyChanged();

					parent.signalAllContactsIdle();
				}

				return true;
			}

			// Verify that we did not miss anything
			assert msg.getData(routingSummaryKey) == null && msg.getData(routingUpdateKey) == null;