sourceroutenode.java

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

				{
					nodeAlgo = ALGO_MED;
				}
				else if (alg.equals("minhop"))
				{
					nodeAlgo = ALGO_HOP_COUNT;
				}
				else if (alg.equals("block") || alg.equals("blocking"))
				{
					blockingNode = true;
				}
				else if (alg.equals("nonblock") || alg.equals("nonblocking"))
				{
					blockingNode = false;
				}
				else
				{
					return new CommandStatus("Unknown algorithm parameter: '" + part.get(1) + "'!");
				}

				return ok;
			}
			else if (param.equals("read_schedule"))
			{
				String scheduleFileName = part.get(1);
				File schedulePath = new File(path, scheduleFileName);

				InputReader ir = new InputReader(network, schedulePath.getPath());
				InputLine line = null;
				double time = 0;
				ArrayList<Contact> contacts = null;
				int i, j, s, t;

				if (network.vShouldLog(Verbose.DEBUG2))
					network.vprint("SCHEDULING contact up/down times from '" + scheduleFileName + "'.");

				while ((line = ir.pollNextLine()) != null)
				{
					if (!line.isCorrect())
					{
						if (network.vShouldLog(Verbose.ERR))
							network.vprint("INCORRECT LINE in '" + scheduleFileName + "'");
						continue;
					}

					if (line.hasTime())
					{
						time = line.time();

						if (time > autoSimTime && time < Double.MAX_VALUE && time < Double.POSITIVE_INFINITY)
						{
							autoSimTime = time;
						}
					}

					if (!line.hasCommand())
						continue;

					contacts = line.findContactsForCommand();

					if (contacts == null)
						continue;

					ArrayList<ArrayList<String>> args = line.commandArgs();

					t = args.size();
					s = contacts.size();

					for (j = 0; j < t; ++j)
					{
						if (args.get(j).size() > 0)
						{
							if (args.get(j).get(0).equals("up"))
							{
								for (i = 0; i < s; ++i)
								{
									Contact c = contacts.get(i);
									SourceRouteNode src = (SourceRouteNode) c.getSource();

									src.scheduleContactUp(c, time);
									if (network.vShouldLog(Verbose.DEBUG3))
										network.vprint("SCHED_UP in " + c + " to " + time);
								}
							}
							else if (args.get(j).get(0).equals("down"))
							{
								for (i = 0; i < s; ++i)
								{
									Contact c = contacts.get(i);
									SourceRouteNode src = (SourceRouteNode) c.getSource();

									src.scheduleContactDown(c, time);
									if (network.vShouldLog(Verbose.DEBUG3))
										network.vprint("SCHED_DOWN in " + c + " to " + time);
								}
							}

						}
					}
				}

				if (network.vShouldLog(Verbose.DEBUG2))
					network.vprint("FINISHED_SCHEDULING contact up/down times from '" + scheduleFileName + "'.");

				return new CommandStatus(CommandStatus.COMMAND_OK);
			}
		}
		catch (NumberFormatException e)
		{
			return new CommandStatus("Error parsing value of parameter '" + param + "': " + e);
		}

		return null;
	}

	protected static final class ContactSchedule
	{
		private UpTime nextUpTime = null;
		private ArrayList<UpTime> times = new ArrayList<UpTime>();
		private Contact contact = null;

		public ContactSchedule(Contact c)
		{
			contact = c;
		}

		public void scheduleUp(double time)
		{
			// Validate that things are being done in order
			assert nextUpTime == null;
			assert times.isEmpty() || time > times.get(times.size()-1).getTimeDown();

			nextUpTime = new UpTime(time);
		}

		public void scheduleDown(double time)
		{
			// again, validate the order
			assert nextUpTime != null;
			assert time > nextUpTime.getTimeUp();

			nextUpTime.setTimeDown(time);
			times.add(nextUpTime);
			nextUpTime = null;
		}

		/** Computes the MED metric assuming that time begins at startTime. */
		public double getMEDWeight()
		{
			if (nextUpTime != null)
			{
				throw new RuntimeException("ContactSchedule is not closed");
			}

			double downSquaredSum = 0;
			double lastTime = 0;

			for (UpTime up : times)
			{
				if (up.getTimeUp() != 0)
				{
					assert up.getTimeUp() > lastTime;
					double downTime = up.getTimeUp() - lastTime;
					assert downTime > 0;

					downSquaredSum += downTime * downTime;
				}

				lastTime = up.getTimeDown();
			}

			// Add the very last down time
			double downTime = simulationTime - lastTime;

			if (downTime > 0)
			{
				downSquaredSum += downTime * downTime;
			}

			double ret = (double) (downSquaredSum / (2 * simulationTime)) + contact.getLatency();

			return ret;
		}

		/** Computes the ED metric for given start Time. */
		public double getEDWeight(double startTime, Message forMsg)
		{
			if (nextUpTime != null)
			{
				throw new RuntimeException("ContactSchedule is not closed");
			}
			
			UpTime u = getFirstGoodUpTime(startTime, forMsg);

			if (u == null)
				return Double.POSITIVE_INFINITY;

			// - forTime as this is a Weight, not ending time
			double ret = Math.max(u.getTimeUp(), startTime) + contact.getLatency() - startTime;
			assert ret >= 0;

			if (forMsg != null)
			{
				ret += contact.getTransferTime(forMsg);
			}

			return ret;
		}

		public UpTime getFirstGoodUpTime(double afterTime, Message forMsg)
		{
			// Get the time it will take to send this message over the contact
			double transferTime = 0;
			if (forMsg != null)
				transferTime = contact.getTransferTime(forMsg);

			// Find the first uptime that we care about
			int index = Collections.binarySearch(times, new UpTime(afterTime));
			
			// If the element wasn't found, switch the index to the positive insertion point
			if (index < 0)
			{
				index = -index - 1;
				assert index >= 0;
			}
			
			if (index > 0 && times.get(index-1).getTimeDown() > afterTime)
			{
				// We are in the middle of an interval
				double timeRemaining = times.get(index-1).getTimeDown() - afterTime;
				if (timeRemaining >= transferTime)
				{
					// There is enough time remaining in this interval: Return an iterator at this point
					return times.get(index-1);
				}
			}
			
			if (index == times.size())
			{
				// There are no more times!
				assert afterTime >= times.get(times.size()-1).getTimeDown();
				return null;
			}
			
			assert times.get(index).getTimeUp() >= afterTime;
			
			while (index < times.size())
			{
				UpTime interval = times.get(index);
				double up = interval.getTimeUp();
				assert up >= afterTime;
				double down = interval.getTimeDown();
				
				if (down - up > transferTime)
				{
					return interval;
				}
				
				// This interval was not long enough for this message
				index += 1;
			}

			return null;
		}
	}

	protected static final class UpTime implements Comparable<UpTime>
	{
		private double timeUp = 0;
		private double timeDown = 0;

		public UpTime(double upT)
		{
			timeDown = timeUp = upT;
		}

		public double getTimeUp()
		{
			return timeUp;
		}

		public double getTimeDown()
		{
			return timeDown;
		}

		public void setTimeDown(double time)
		{
			timeDown = time;

			assert timeDown >= time;
		}
		
		public int compareTo(UpTime other)
		{
			if (timeUp > other.timeUp) return 1;
			if (timeUp < other.timeUp) return -1;
			
			assert timeUp == other.timeUp;
			return 0;
		}
	}
	
	public class RouteField implements Stats.StatFieldInterpreter
	{
		public boolean writeStatsField(Stats stat, BufferedWriter output, ArrayList<String> outFields,
				ArrayList<String> inFields, int fieldNum, HashMap<Object, Object> context) throws IOException
		{
			if (context.get(Stats.STAT_TYPE_MSG) == null)
			{
				return stat.splitResults(stat, output, outFields, inFields, fieldNum, context, Stats.STAT_TYPE_MSG);
			}

			String field = inFields.get(fieldNum);

			if (!field.equals("%msg_route") && !field.equals("%msg_route_len"))
			{
				throw new IllegalArgumentException("Wrong field description for Route stats field: "
						+ inFields.get(fieldNum));
			}

			ArrayList<Stats.StatEntry> entries = stat.getDataContextMap(Stats.STAT_TYPE_MSG, context);

			if (entries == null || entries.size() < 1)
				return false;

			Iterator<Stats.StatEntry> iter = entries.iterator();

			if (!iter.hasNext())
				return false;

			Message msg = null;

			msg = ((Stats.StatMsgEntry) iter.next()).msg;

			SourceRouteNode src = (SourceRouteNode) msg.getSourceNode();
			ArrayList<Contact> sourceRoute = null;

			if (nodeAlgo == ALGO_MED)
			{
				assert src.lastRouting != null;

				sourceRoute = src.lastRouting.routeTo((SourceRouteNode) msg.getDestNode());
			}
			else
			{
				assert src.lastRouting != null;

				if (src.lastRouting.getStartTime() != msg.getCreationTime())
				{
					src.lastRouting = new NetworkDijkstra(networkGraph(), src, msg.getCreationTime(), msg);
				}

				sourceRoute = src.lastRouting.routeTo((SourceRouteNode) msg.getDestNode());
			}

			String str = "???";

			if (sourceRoute == null || sourceRoute.size() < 1)
			{
				str = "ROUTE_UNKNOWN";
			}
			else
			{
				if (field.equals("%msg_route_len"))
				{
					str = "" + sourceRoute.size();
				}
				else
				{
					Iterator<Contact> it = sourceRoute.iterator();

					str = "ROUTE: ";

					while (it.hasNext())
					{
						Contact ct = it.next();

						if (nodeAlgo == ALGO_MED)
						{
							str += ct + ": ";
						}
						else
						{
							str += ct + "(" + src.lastRouting.getCost((SourceRouteNode) ct.getDest()) + "): ";
						}
					}
				}
			}

			outFields.set(fieldNum, str);

			return stat.writeStatsField(stat, output, outFields, inFields, fieldNum + 1, context);
		}
	}

	/** Implements the routing graph for ED. */
	private final static class EDGraph extends NetworkDijkstra.NetworkGraph
	{
		public double getWeight(Contact ofArc, double time, Message context)
		{
			ContactSchedule cs = contactSchedules.get(ofArc);
			if (cs == null)
				throw new RuntimeException("ED requires contact schedules");

			return cs.getEDWeight(time, context);
		}

		public double getArrivalTime(Contact ofArc, double time, Message context)
		{
			return time + getWeight(ofArc, time, context);
		}
	}
	
	/** Implements the routing graph for the minimum hop count metric. */
	private final static class HopCountGraph extends NetworkDijkstra.NetworkGraph
	{
		/**
		 * A generic Pair class for Java. Useful for quick and dirty hacks, like
		 * hash keys. It implements equals() using the == operator and not
		 * .equals.
		 */
		private final static class Pair<T1, T2>
		{
			private T1 first;

			public T1 first()
			{
				return first;
			}

			private T2 second;

			public T2 second()
			{
				return second;
			}

			public Pair(T1 first, T2 second)
			{
				this.first = first;
				this.second = second;
			}

			public int hashCode()
			{
				int code = 0;
				if (first != null)
					code = first.hashCode();
				if (second != null)
					code ^= second.hashCode();

				return code;
			}

			public boolean equals(Object o)
			{
				Pair<? extends T1, ? extends T2> other = (Pair<? extends T1, ? extends T2>) o;
				return other.first == first && other.second == second;
			}

			public String toString()
			{
				return "Pair( " + first + ", " + second + " )";
			}
		}

		/**
		 * A cache to avoid having to perform ED routing excessively. This
		 * speeds up min hop count routing ENORMOUSLY. TODO: This may be
		 * problematic if multiple runs are done inside one process. This cache
		 * needs to be reset.
		 */
		private static HashMap<Pair<Node, Node>, Pair<Double, Double>> deliveryCache = new HashMap<Pair<Node, Node>, Pair<Double, Double>>();

		private void updateCacheDeliverable(Pair<Node, Node> key, Pair<Double, Double> cached, double time)
		{
			double latest = Double.POSITIVE_INFINITY;

			if (cached != null)
			{
				// To get here, we must have had a cache miss, which means we
				// need to update this
				assert time > cached.first();

				latest = cached.second();
			}

			Pair<Double, Double> newCached = new Pair<Double, Double>(time, latest);
			deliveryCache.put(key, newCached);
		}

		private void updateCacheUndeliverable(Pair<Node, Node> key, Pair<Double, Double> cached, double time)
		{
			double earliest = Double.NEGATIVE_INFINITY;

			if (cached != null)
			{
				earliest = cached.first();

				// To get here, we must have had a cache miss, which means we
				// need to update this
				assert time < cached.second();
			}

			Pair<Double, Double> newCached = new Pair<Double, Double>(earliest, time);
			deliveryCache.put(key, newCached);
		}

		public double getWeight(Contact ofArc, double time, Message context)
		{
			// We return 1 if a path exists to the destination from the other
			// end of the contact
			// to the destination, after the arrival time at the other end of
			// the contact.

			// 1. Find when the message will arrive at the other end of the
			// contact
			double otherEndTime = getArrivalTime(ofArc, time, context);
			if (otherEndTime == Double.POSITIVE_INFINITY)
			{
				// This means that we NEVER reach the other end: return infinity
				return Double.POSITIVE_INFINITY;
			}

			// 2. Find if there is a path from the other node to the
			// destination, after otherEndTime
			// Check the cache first
			Pair<Node, Node> key = new Pair<Node, Node>(ofArc.getDest(), context.getDestNode());
			Pair<Double, Double> cached = deliveryCache.get(key);
			if (cached != null)
			{
				double latestGood = cached.first();
				if (otherEndTime <= latestGood)
				{
					// We already know that we can deliver this message
					// ~ System.out.println( "cache hit: deliverable" );
					return 1;
				}

				double earliestBad = cached.second();
				if (otherEndTime >= earliestBad)
				{
					// ~ System.out.println( "cache hit: undeliverable" );
					return Double.POSITIVE_INFINITY;
				}
			}
			NetworkDijkstra routing = new NetworkDijkstra(new EDGraph(), (SourceRouteNode) ofArc.getDest(),
					otherEndTime, context);

			ArrayList<Contact> route = routing.routeTo((SourceRouteNode) context.getDestNode());
			if (route == null)
			{
				// No route exists
				updateCacheUndeliverable(key, cached, otherEndTime);
				return Double.POSITIVE_INFINITY;
			}
			else
			{
				updateCacheDeliverable(key, cached, otherEndTime);
				return 1;
			}
		}

		public double getArrivalTime(Contact ofArc, double time, Message context)
		{
			ContactSchedule cs = contactSchedules.get(ofArc);
			if (cs == null)
				throw new RuntimeException("HopCount requires contact schedules");

			double arrival = time + cs.getEDWeight(time, context);
			return arrival;
		}
	}

	/** Implements the routing graph for MED. */
	private static class MEDGraph extends NetworkDijkstra.NetworkGraph
	{
		public double getWeight(Contact ofArc, double time, Message context)
		{
			ContactSchedule cs = contactSchedules.get(ofArc);
			if (cs == null)
				throw new RuntimeException("BED requires contact schedules");
			if (simulationTime <= 0)
			{
				if (autoSimTime == -1)
					throw new RuntimeException("No simulation time, no auto sim time");
				simulationTime = autoSimTime + 1;
			}

			return cs.getMEDWeight();
		}

		public double getArrivalTime(Contact ofArc, double time, Message context)
		{
			return time;
		}
	}
	
	/** Implements the routing graph for MED. */
	private final static class MEDPerContactGraph extends MEDGraph
	{
		private Node parent;
		
		public MEDPerContactGraph(Node parent)
		{
			this.parent = parent;
		}
		
		public double getWeight(Contact ofArc, double time, Message context)
		{
			// The message is currently at 
			if (ofArc.getSource() == parent && ofArc.isUp())
			{
				return ofArc.getLatency();
			}
			else
			{
				return super.getWeight(ofArc, time, context);
			}
		}
	}
}