/*
* Copyright (c) 2005-2010 KOM – Multimedia Communications Lab
*
* This file is part of PeerfactSim.KOM.
*
* PeerfactSim.KOM is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* any later version.
*
* PeerfactSim.KOM is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with PeerfactSim.KOM. If not, see .
*
*/
package de.tud.kom.p2psim.impl.topology.views;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import de.tud.kom.p2psim.api.linklayer.mac.Link;
import de.tud.kom.p2psim.api.linklayer.mac.MacAddress;
import de.tud.kom.p2psim.api.linklayer.mac.MacLayer;
import de.tud.kom.p2psim.api.linklayer.mac.PhyType;
import de.tud.kom.p2psim.api.topology.obstacles.Obstacle;
import de.tud.kom.p2psim.api.topology.obstacles.ObstacleModel;
import de.tud.kom.p2psim.api.topology.waypoints.WaypointModel;
import de.tud.kom.p2psim.impl.util.LiveMonitoring;
import de.tud.kom.p2psim.impl.util.LiveMonitoring.ProgressValue;
import de.tudarmstadt.maki.simonstrator.api.util.XMLConfigurableConstructor;
/**
* A topology view where connectivity is based on the distance between hosts.
* This basic version supports movement (ie. Neighborhoods change over time) and
* obstacles in that connectivity is only enabled if a link does not intersect
* with any obstacles. Extending classes could add a more versatile handling of
* obstacles, for example in allowing them to dampen the signal rather than
* completely destroying it.
*
* This View provides GlobalKnowledgeRouting information by implementing a
* cached version of Dijkstra. Depending on the requirements of your simulation
* you might find it useful to alter some parameters of the
* Dijkstra-Implementation - they are commented in the Dijkstra-subclass.
*
* @author Bjoern Richerzhagen
* @version 1.0, 07.03.2012
*/
public class RangedTopologyView extends AbstractTopologyView {
/**
* communication range for the static case
*/
private double range = 150;
/**
* Just a List of all Links
*/
private List linkList = new ArrayList();
/**
* These are used for the GlobalKnowledge-Functions
*/
private Map dijkstras = new HashMap();
/**
* Again, only used for the GlobalKnowledge-Functions
*/
protected List allMacAddresses = new ArrayList();
/**
* A Pointer to the Obstacle Model
*/
private ObstacleModel obstacleModel;
/**
* A Pointer to the Waypoint Model
*/
private WaypointModel waypointModel;
public static long _dijkstraCalculated, _dijkstraCached, _dijkstraPartly;
/**
* This View supports movement as well as obstacles (at least in a very
* basic form)
*
* @param phy
*
*/
public RangedTopologyView(PhyType phy, double range) {
super(phy, true);
this.range = range;
LiveMonitoring.addProgressValueIfNotThere(new DijkstraMonitor());
}
@XMLConfigurableConstructor({ "phy", "range" })
public RangedTopologyView(String phy, double range) {
this(PhyType.WIFI, range);
setPhy(phy);
}
@Override
protected void addedMac(MacLayer mac) {
dijkstras.put(mac.getMacAddress(), new Dijkstra(mac.getMacAddress()));
allMacAddresses.add(mac.getMacAddress());
}
@Override
protected RangedLink createLink(MacAddress source, MacAddress destination) {
RangedLink link = new RangedLink(source, destination, true,
determineLinkDropProbability(source, destination),
determineLinkBandwidth(source, destination),
determineLinkLatency(source, destination), getPhyType()
.getDefaultMTU(), getRange());
synchronized (linkList) {
linkList.add(link);
}
return link;
}
/**
* This might be overwritten to calculate ranges based on
* neighborhood-density or a statistical distribution. The default
* implementation just returns a constant
*
* @return max distance between hosts to still be able to communicate (ie.
* wireless range)
*/
protected double getRange() {
return range;
}
protected void setRange(double range) {
this.range = range;
}
@Override
public Link getBestNextLink(MacAddress source, MacAddress lastHop,
MacAddress currentHop, MacAddress destination) {
/*
* This one is a bit tricky... how to define a "best" link? Shortest
* path? Energy? DropRate? Bandwidth?
*/
// System.err.println(source + " => " + lastHop + " => " + currentHop
// + " => " + destination);
/*
* Dijkstra-Based implementation, try to use the one-time calculated
* path - this also prevents loops due to equi-distant nodes in a
* grid-setting.
*/
List path = dijkstras.get(source).getPath(destination);
RangedLink toReturn = null;
for (RangedLink link : path) {
if (link.getSource().equals(currentHop)) {
assert link.isConnected();
assert !link.isOutdated();
toReturn = link;
}
}
if (toReturn != null) {
assert toReturn.isConnected();
return toReturn;
}
/*
* It may happen that meanwhile the route changed to not include this
* node anymore. If this happens, we use dijkstra with the current node
* as starting point.
*/
_dijkstraPartly++;
path = dijkstras.get(currentHop).getPath(destination);
if (!path.isEmpty()) {
toReturn = path.get(0);
assert toReturn.isConnected();
return path.get(0);
}
/*
* No path, returning default Link (not connected)
*/
return getLinkBetween(currentHop, destination);
}
@Override
protected List updateNeighborhood(MacAddress source) {
/*
* We cache this information as well to reach consistency between
* getNeighbors and Link-Information.
*/
List updatedNeighbors = new ArrayList();
for (MacAddress neighbor : allMacAddresses) {
RangedLink link = getLinkBetween(source, neighbor);
if (link.isConnected()) {
assert !neighbor.equals(source);
updatedNeighbors.add(neighbor);
}
}
return updatedNeighbors;
}
@Override
public void afterComponentsMoved() {
super.afterComponentsMoved();
/*
* mark all links as outdated
*/
synchronized (linkList) {
for (RangedLink link : linkList) {
link.setOutdated(true);
}
for (Dijkstra dijkstra : dijkstras.values()) {
dijkstra.afterComponentsMoved();
}
}
}
@Override
protected void updateOutdatedLink(RangedLink link) {
link.updateNodeDistance(getCachedPosition(link.getSource())
.distanceTo(getCachedPosition(link.getDestination())));
/*
* Update latency and drop rate - note: it depends on the actual
* implementation of the determinators, whether the value is actually
* changed.
*/
if (link.isConnected()) {
link.updateLatency(getLatencyDeterminator().getLatency(this,
link.getSource(), link.getDestination(), link));
link.updateDropProbability(
getDropProbabilityDeterminator().getDropProbability(this,
link.getSource(), link.getDestination(), link));
}
/*
* The distance has already been updated, we just have to check for
* obstacles. More advanced Views might update the properties based on
* the type or size of the obstacle. Or they might provide a way to
* iterate over obstacles in the order they occur on the link.
*/
if (link.isConnected() && obstacleModel != null) {
double rangeWeighted = 0;
for (Obstacle obstacle : obstacleModel.getObstacles()) {
if (obstacle.dampingFactor() == 0) {
continue;
}
if (obstacle.intersectsWith(
getCachedPosition(link.getSource()),
getCachedPosition(link.getDestination()))) {
if (obstacle.dampingFactor() == 1) {
link.setConnected(false);
break;
}
double intersectionLength = obstacle
.totalIntersectionLength(
getCachedPosition(link.getSource()),
getCachedPosition(link.getDestination()));
/*
* Just an arbitrary formula to add some damping effect -
* this does in no way reflect a proper model, but showcases
* the functionality a view could have
*/
rangeWeighted += Math.pow(intersectionLength,
obstacle.dampingFactor() + 1);
}
}
if (link.getNodeDistance() > range - rangeWeighted) {
// no connection possible
link.setConnected(false);
}
}
}
/**
* Dijkstra-Implementation for the GlobalKnowledge-Functions. A path is
* calculated as soon as one of the Links on the old path is no longer
* connected (this adds some caching to the algorithm in order to ease
* computational load on scenarios where paths are rather persistent)
*
* FIXME currently, Dijkstra does not take into account if a MAC is online
* or not - this information should however be known in a GlobalKnowledge
* routing environment. It may on the other hand have a not-so-small impact
* on performance -> make it configurable
*
* @author Bjoern Richerzhagen
* @version 1.0, 21.03.2012
*/
private class Dijkstra {
/**
* A vertex inside Dijkstra - this is used for the {@link PriorityQueue}
* -based implementation.
*
* @author Bjoern Richerzhagen
* @version 1.0, 26.03.2012
*/
private class Vertex implements Comparable {
public MacAddress mac;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous = null;
public Vertex(MacAddress mac) {
this.mac = mac;
}
public void reset() {
this.minDistance = Double.POSITIVE_INFINITY;
this.previous = null;
}
@Override
public int compareTo(Vertex o) {
return Double.compare(minDistance, o.minDistance);
}
}
/**
* To choose a "robust" path, Dijkstra only selects connected Links
* where the node distance is less than the maxDistance minus this
* threshold. This improves performance, because paths can be used
* longer - but on the other hand you do not get the total 100% of
* available paths, which might lead to packet drops, even if a path
* would be available.
*/
private double RANGE_THRESHOLD = 10;
/**
* After MOVEMENT_THRESHOLD movements (calls to afterComponentsMoved) we
* will update Dijkstra. Otherwise, paths could still be valid but
* contain far to many hops (zig-zag). If this is set to 1, we
* re-compute the path on every movement, if set to zero, we compute
* graphs only if a path is broken
*/
private int MOVEMENT_THRESHOLD = 5;
private final boolean USE_NEW = true;
private int movement_counter = 0;
private MacAddress source;
private Map dist = new HashMap();
private Map previous = new HashMap();
private List q = new LinkedList();
private PriorityQueue vertexQueue = new PriorityQueue();
private HashMap toVertex = new HashMap();
private boolean recalculate = true;
public Dijkstra(MacAddress source) {
this.source = source;
}
public void afterComponentsMoved() {
/*
* Re-calculate
*/
if (MOVEMENT_THRESHOLD != 0) {
if (movement_counter % MOVEMENT_THRESHOLD == 0) {
recalculate = true;
}
movement_counter++;
}
}
public List getPath(MacAddress destination) {
if (recalculate) {
movement_counter = 0;
initialize();
calculate();
}
boolean pathBroken = false;
List path = new LinkedList();
if (USE_NEW) {
for (Vertex vertex = toVertex.get(destination); vertex.previous != null; vertex = vertex.previous) {
RangedLink link = getLinkBetween(vertex.previous.mac,
vertex.mac);
assert !link.isOutdated();
path.add(link);
if (!link.isConnected()) {
pathBroken = true;
}
}
Collections.reverse(path);
} else {
List pathMacs = new LinkedList();
MacAddress u = destination;
while (previous.get(u) != null) {
pathMacs.add(u);
u = previous.get(u);
}
pathMacs.add(u);
Collections.reverse(pathMacs);
Iterator it = pathMacs.iterator();
MacAddress prevHop = null;
while (it.hasNext() && !pathBroken) {
if (prevHop == null) {
prevHop = it.next();
continue;
}
MacAddress actHop = it.next();
RangedLink l = getLinkBetween(prevHop, actHop);
path.add(l);
prevHop = actHop;
assert !l.isOutdated();
if (!l.isConnected()) {
pathBroken = true;
}
}
// if (pathMacs.size() == 1) {
// pathBroken = true; // no path at all.
// }
}
if (pathBroken && !recalculate) {
recalculate = true;
return getPath(destination);
} else if (pathBroken) {
path.clear();
} else {
_dijkstraCached++;
}
recalculate = false;
return path;
}
private void calculate() {
_dijkstraCalculated++;
if (USE_NEW) {
// NEW
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
List neighbors = getNeighbors(u.mac);
for (MacAddress neighbor : neighbors) {
RangedLink l = getLinkBetween(u.mac, neighbor);
Vertex v = toVertex.get(neighbor);
double weight = Double.POSITIVE_INFINITY;
if (l.isConnected()
&& l.getNodeDistance() + RANGE_THRESHOLD < l
.getMaxDistance()) {
weight = l.getNodeDistance();
}
assert (l.isConnected() && l.getNodeDistance() < l
.getMaxDistance()) || !l.isConnected();
double distanceWithU = u.minDistance + weight;
if (distanceWithU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceWithU;
v.previous = u;
assert l.isConnected();
vertexQueue.add(v);
}
}
}
} else {
// OLD
while (!q.isEmpty()) {
// find smallest distance
double smallestDistance = Double.MAX_VALUE;
MacAddress u = null;
for (MacAddress candidate : q) {
if (u == null || dist.get(candidate) < smallestDistance) {
u = candidate;
smallestDistance = dist.get(candidate);
}
}
if (smallestDistance == Double.MAX_VALUE) {
break; //
}
q.remove(u);
List neighbors = getNeighbors(u);
for (MacAddress neighbor : neighbors) {
RangedLink l = getLinkBetween(u, neighbor);
if (l.isConnected()
&& l.getNodeDistance() < l.getMaxDistance()
- RANGE_THRESHOLD) {
assert !l.isOutdated() : "Outdated Link!";
double alt = dist.get(u) + l.getNodeDistance();
if (alt < dist.get(neighbor)) {
dist.put(neighbor, new Double(alt));
previous.put(neighbor, u);
}
}
}
}
}
}
private void initialize() {
if (USE_NEW) {
if (toVertex.isEmpty()) {
for (MacAddress macAddr : allMacAddresses) {
Vertex v = new Vertex(macAddr);
v.reset();
toVertex.put(macAddr, v);
}
} else {
for (Vertex v : toVertex.values()) {
v.reset();
}
}
Vertex sourceVertex = toVertex.get(source);
sourceVertex.minDistance = 0;
vertexQueue.clear();
vertexQueue.add(sourceVertex);
} else {
q = new ArrayList(allMacAddresses);
for (MacAddress macAddr : allMacAddresses) {
dist.put(macAddr, Double.MAX_VALUE);
previous.put(macAddr, null);
}
dist.put(source, new Double(0));
}
}
}
public class DijkstraMonitor implements ProgressValue {
@Override
public String getName() {
return "TopologyView Dijkstra (calc, cached, partly): ";
}
@Override
public String getValue() {
return Long.toString(_dijkstraCalculated) + " / "
+ Long.toString(_dijkstraCached) + " / "
+ Long.toString(_dijkstraPartly);
}
}
@Override
public void changedWaypointModel(WaypointModel model) {
this.waypointModel = model;
}
@Override
public void changedObstacleModel(ObstacleModel model) {
this.obstacleModel = model;
}
public WaypointModel getWaypointModel() {
return waypointModel;
}
}