2
\$\begingroup\$

Inspired by my question Simulating a random packet routing algorithm and printing packet statistics in Java I decided to implement two more packet routing algorithms: one that computes all the shortest paths in the network and routes each packet via a shortest path between the packet and its destination. The second algorithm does the same, but rather instead of explicitly computing the shortest paths, the algorithm "learns" the shortest paths from the history data that is being gathered for each packet.

Note: The second, learning algorithm may get stuck in an unfunky loop: there might be situation where the packet "ping pongs" between two connected routers \$R_1\$ and \$R_2\$, because \$R_1\$ thinks that it should send the packet via \$R_2\$ and \$R_2\$ thinks it should send the packet via \$R_1\$. If that happens, my demonstration simply aborts the simulation of that learning algorithm, and proceeds to simulating the shortest path variant.

My code follows:

AbstractPacketRoutingAlgorithm.java

package net.coderodde.simulation.network;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

/**
 * This class defines the API and utility methods of a packet routing algorithm.
 * The simulation rules are as follows:
 * 
 * <ul>
 * <li>The network works in "cycles,"</li>
 * <li>During each cycle, each packet router may send at most one packet to 
 *     its neighbor, yet is allowed to receive any number of incoming packets,
 * </li>
 * <li>The packet queue of each packet router is FIFO.</li>
 * </ul>
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 18, 2016)
 */
public abstract class AbstractPacketRoutingAlgorithm {

    /**
     * This map maps each packet to its transmission history. The history of
     * each packet is the list of packet routers that the packet had to visit in
     * order to reach the destination. If a packet spends more than one 
     * consecutive "network cycle" in a router, it is reflected in the history
     * list by storing the router ID multiple times in a row.
     * <p>
     * For example, if a packet starts from router ID 3, spends two cycles in 
     * the router with ID 5 and finally reaches its destination (router ID 1),
     * the history list would contain <code><3, 5, 5, 1></code>.
     */
    protected Map<Packet, List<PacketRouter>> historyMap;

    /**
     * While simulation is running, this set contains only those packets that
     * have not yet reached their respective targets.
     */
    protected Set<Packet> undeliveredPacketSet;

    /**
     * This list stores all the queue length in all packet routers at all 
     * network cycles.
     */
    protected List<Integer> queueLengthList;

    /**
     * The number of network cycles made in a network. Starts form one as we 
     * count network initialization as well.
     */
    protected int cycles = 1;

    /**
     * Runs a packet routing algorithm and returns the statistics of a 
     * simulation run.
     * 
     * @param network    the list of packet routers comprising the network.
     * @param packetList the list of packets to deliver.
     * @return the object holding the statistical results of the simulation.
     */
    public abstract SimulationStatistics 
        simulate(final List<PacketRouter> network,
                 final List<Packet> packetList);

    protected SimulationStatistics buildStatistics() {   
        int minQueueLength = queueLengthList.get(0);
        int maxQueueLength = queueLengthList.get(0);

        int queueLengthSum = 0;
        int squaredQueueLengthSum = 0;

        for (final int i : queueLengthList) {
            if (minQueueLength > i) {
                minQueueLength = i;
            } else if (maxQueueLength < i) {
                maxQueueLength = i;
            }

            queueLengthSum += i;
            squaredQueueLengthSum += i * i;
        }


        final double queueLengthAverage = 
                1.0 * queueLengthSum / queueLengthList.size();

        final double queueLengthSd = 
                Math.sqrt(
                    (1.0 * squaredQueueLengthSum - 
                     1.0 * queueLengthSum * queueLengthSum / 
                           queueLengthList.size()) 
                  / (queueLengthList.size() - 1)
                );

        int minHistoryLength = historyMap.values().iterator().next().size();
        int maxHistoryLength = minHistoryLength;

        int historyLengthSum = 0;
        int squaredHistoryLengthSum = 0;

        for (final List<PacketRouter> history : historyMap.values()) {
            final int length = history.size();

            if (minHistoryLength > length) {
                minHistoryLength = length;
            } else if (maxHistoryLength < length) {
                maxHistoryLength = length;
            }

            historyLengthSum += length;
            squaredHistoryLengthSum += length * length;
        }

        final double historyLengthAverage = 
                1.0 * historyLengthSum / historyMap.size();

        final double historyLengthSd = 
                Math.sqrt(
                    (1.0 * squaredHistoryLengthSum -
                     1.0 * historyLengthSum * historyLengthSum / 
                           historyMap.size())
                  / (historyMap.size() - 1)
                );

        return new SimulationStatistics(minQueueLength,
                                        maxQueueLength,
                                        queueLengthAverage,
                                        queueLengthSd,
                                        minHistoryLength,
                                        maxHistoryLength,
                                        historyLengthAverage,
                                        historyLengthSd,
                                        cycles);
    }

    protected void initializePackets(final List<Packet> packetList) {
        for (final Packet packet : packetList) {
            packet.getSourcePacketRouter().enqueuePacket(packet);

            historyMap.put(packet,
                           new ArrayList<>(
                                   Arrays.asList(
                                           packet.getSourcePacketRouter())));
        }
    }

    protected void loadPacketRouterQueueLengths(
            final List<PacketRouter> network) {
        network.forEach((router) -> { 
            queueLengthList.add(router.queueLength()); 
        });
    }

    protected void pruneDeliveredPackets() {
        final Iterator<Packet> iterator = undeliveredPacketSet.iterator();

        while (iterator.hasNext()) {
            final Packet packet = iterator.next();
            final PacketRouter targetOfPacket = packet.getTargetPacketRouter();
            final List<PacketRouter> historyOfPacket = historyMap.get(packet);

            if (lastOf(historyOfPacket).equals(targetOfPacket)) {
                iterator.remove();
                targetOfPacket.remove(packet);
            }
        }
    }

    protected static <T> T lastOf(final List<T> list) {
        return list.get(list.size() - 1);
    }

    protected static <T> T choose(final List<T> list, final Random random) {
        return list.get(random.nextInt(list.size()));
    }
}

RandomPacketRoutingAlgorithm.java:

package net.coderodde.simulation.network;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * This class implements a packet routing algorithm that sends each packet to a
 * randomly chosen neighbor packet router.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 11, 2016)
 */
public final class RandomPacketRoutingAlgorithm extends AbstractPacketRoutingAlgorithm {

    /**
     * The random number generator.
     */
    private Random random;

    /**
     * Constructs the API entry object.
     */
    public RandomPacketRoutingAlgorithm() {}

    /**
     * Constructs the actual state object of this algorithm.
     * 
     * @param dummy ignored. Used for distinction between the public and
     *              non-public constructors.
     */
    private RandomPacketRoutingAlgorithm(final boolean dummy) {
        this.historyMap           = new HashMap<>();
        this.undeliveredPacketSet = new HashSet<>();
        this.queueLengthList      = new ArrayList<>();
        this.random               = new Random();
    }

    @Override
    public SimulationStatistics simulate(final List<PacketRouter> network, 
                                         final List<Packet> packetList) {
        final RandomPacketRoutingAlgorithm state = 
                new RandomPacketRoutingAlgorithm(true);

        return state.simulateImpl(network, packetList);
    }

    private SimulationStatistics simulateImpl(final List<PacketRouter> network,
                                              final List<Packet> packetList) {
        initializePackets(packetList);

        undeliveredPacketSet.addAll(packetList);

        while (!undeliveredPacketSet.isEmpty()) {
            loadPacketRouterQueueLengths(network);
            simulateCycle(network);
            pruneDeliveredPackets();
            ++cycles;
        }

        return buildStatistics();
    }

    private void simulateCycle(final List<PacketRouter> network) {
        final Map<Packet, PacketRouter> map = new HashMap<>();

        // Find out to which packet router to send the packets:
        for (final PacketRouter packetRouter : network) {
            if (packetRouter.queueLength() > 0) {
                final Packet packet = packetRouter.dequeuePacket();
                final PacketRouter nextPacketRouter = 
                        choose(packetRouter.getNeighbors(), random);
                map.put(packet, nextPacketRouter);
            }
        }

        // Send the packets:
        for (final Map.Entry<Packet, PacketRouter> entry : map.entrySet()) {
            final Packet packet = entry.getKey();
            final PacketRouter packetRouter = entry.getValue();
            packetRouter.enqueuePacket(packet);
        }

        // Update the history of each packet.
        for (final PacketRouter packetRouter : network) {
            for (final Packet packet : packetRouter.getQueue()) {
                historyMap.get(packet).add(packetRouter);
            }
        }
    }
}

LearningPacketRoutingAlgorithm.java:

package net.coderodde.simulation.network;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * This class implements a packet routing algorithm that learns shorter paths
 * during its operation: whenever a packet is received, it checks its history to
 * see whether it is possible to improve the paths. For example, suppose the 
 * history of a received packet is <tt>n_1, n_2, ..., n_k</tt>. For each packet
 * router <tt>n_1, n_2, ..., n_k</tt> the algorithm checks whether the current
 * path improves the path lengths starting from the routers in question, and if
 * so, updates its state to further use those improved path, at least until they
 * may be improved even further.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 11, 2016)
 */
public final class LearningPacketRoutingAlgorithm 
extends AbstractPacketRoutingAlgorithm {

    private Map<PacketRouter, Map<PacketRouter, PacketRouter>> dispatchTable;
    private Map<PacketRouter, Map<PacketRouter, Integer>> distanceTable;
    private Random random;
    private int cycleLimit;

    public LearningPacketRoutingAlgorithm() {}

    private LearningPacketRoutingAlgorithm(final int cycleLimit) {
        this.historyMap           = new HashMap<>();
        this.undeliveredPacketSet = new HashSet<>();
        this.queueLengthList      = new ArrayList<>();
        this.dispatchTable        = new HashMap<>();
        this.distanceTable        = new HashMap<>();
        this.random               = new Random();
        this.cycleLimit           = cycleLimit;
    }

    public void setCycleLimit(final int cycleLimit) {
        this.cycleLimit = cycleLimit;
    }

    @Override
    public SimulationStatistics simulate(final List<PacketRouter> network,
                                         final List<Packet> packetList) {
        final LearningPacketRoutingAlgorithm state =
                new LearningPacketRoutingAlgorithm(cycleLimit);

        return state.simulateImpl(network, packetList);
    }

    private SimulationStatistics simulateImpl(final List<PacketRouter> network,
                                              final List<Packet> packetList) {
        initializePackets(packetList);
        buildDispatchTable(network);

        undeliveredPacketSet.addAll(packetList);

        while (!undeliveredPacketSet.isEmpty()) {
            loadPacketRouterQueueLengths(network);
            simulateCycle(network);
            relearnDispatchTable(network);
            pruneDeliveredPackets();
            ++cycles;

            if (cycleLimit != 0) {
                if (cycles > cycleLimit) {
                    // Discard all packets in each router.
                    clearNetwork(network);
                    return null;
                }
            }
        }

        return buildStatistics();
    }

    private void clearNetwork(final List<PacketRouter> network) {
        for (final PacketRouter packetRouter : network) {
            packetRouter.clearQueue();
        }
    }

    private void buildDispatchTable(final List<PacketRouter> network) {
        // Initialize the distance table:
        for (final PacketRouter source : network) {
            final Map<PacketRouter, Integer> localDistanceTable = 
                    new HashMap<>(network.size());

            distanceTable.put(source, localDistanceTable);

            for (final PacketRouter target : network) {
                if (!target.equals(source)) {
                    localDistanceTable.put(target, Integer.MAX_VALUE);
                }
            }
        }

        // Randomly initialize the dispatch table:
        for (final PacketRouter source : network) {
            final Map<PacketRouter, PacketRouter> localDispatchTable = 
                    new HashMap<>();

            dispatchTable.put(source, localDispatchTable);

            for (final PacketRouter target : network) {
                if (!target.equals(source)) {
                    PacketRouter nextRouter;

                    do {
                        nextRouter = choose(network, random);
                    } while (nextRouter.equals(source));

                    localDispatchTable.put(target, nextRouter);
                }
            }
        }
    }

    private void simulateCycle(final List<PacketRouter> network) {
        final Map<Packet, PacketRouter> map = new HashMap<>();

        // Find out to which packet routers to send the packets:
        for (final PacketRouter packetRouter : network) {
            if (packetRouter.queueLength() > 0) {
                final Packet packet = packetRouter.dequeuePacket();
                final PacketRouter targetRouterOfPacket = 
                        packet.getTargetPacketRouter();

                final PacketRouter nextPacketRouter = 
                        dispatchTable.get(packetRouter)
                                     .get(targetRouterOfPacket);

                map.put(packet, nextPacketRouter);
            }
        }

        // Send the packets:
        for (final Map.Entry<Packet, PacketRouter> entry : map.entrySet()) {
            final Packet packet = entry.getKey();
            final PacketRouter packetRouter = entry.getValue();
            packetRouter.enqueuePacket(packet);
        }

        // Update the history of each packet.
        for (final PacketRouter packetRouter : network) {
            for (final Packet packet : packetRouter.getQueue()) {
                historyMap.get(packet).add(packetRouter);
            }
        }
    }

    private void relearnDispatchTable(final List<PacketRouter> network) {
        for (final PacketRouter packetRouter : network) {
            final Map<PacketRouter, PacketRouter> localDispatchTable = 
                    dispatchTable.get(packetRouter);

            final Map<PacketRouter, Integer> localDistanceTable =
                    distanceTable.get(packetRouter);

            final List<Packet> queue = new ArrayList<>(packetRouter.getQueue());

            for (final Packet packet : queue) {
                final List<PacketRouter> history = historyMap.get(packet);
                final List<PacketRouter> compressedHistory = 
                        removeDuplicatesFromHistoryList(history);

                for (int i = 0; i < compressedHistory.size(); ++i) {
                    final PacketRouter pr = compressedHistory.get(i);

                    if (!packetRouter.equals(pr)) {
                        final int distance = compressedHistory.size() - i - 1;

                        if (localDistanceTable.get(pr) > distance) {
                            localDistanceTable.put(pr, distance);
                            localDispatchTable.put(
                                    pr, 
                                    compressedHistory.get(
                                            compressedHistory.size() - 2));
                        }
                    }
                }
            }
        }
    }

    public static List<PacketRouter> 
        removeDuplicatesFromHistoryList(final List<PacketRouter> history) {
        final List<PacketRouter> compressedHistory = 
                new ArrayList<>(history.size());

        PacketRouter previous = history.get(0);
        compressedHistory.add(previous);

        for (int i = 1; i < history.size(); ++i) {
            final PacketRouter current = history.get(i);

            if (!current.equals(previous)) {
                compressedHistory.add(current);
                previous = current;
            }
        }

        return compressedHistory;
    }
}

ShortestPathPacketRoutingAlgorithm.java:

package net.coderodde.simulation.network;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

/**
 * This class implements a packet routing algorithm that computes all-pairs 
 * shortest paths and transmits each packet along the shortest path between the 
 * terminal packet routers.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 11, 2016)
 */
public final class ShortestPathPacketRoutingAlgorithm 
extends AbstractPacketRoutingAlgorithm {

    /**
     * This map implements the dispatch table. It maps each source packet router
     * <tt>S</tt>, to a partial dispatch table <tt>T(S)</tt>. Each <tt>T(S)</tt>
     * maps each target packet router <tt>D</tt> to a neighbor router <tt>N<tt> 
     * such that <tt>N</tt> is on a shortest path between <tt>S</tt> and 
     * <tt>D</tt>.
     */
    private Map<PacketRouter, Map<PacketRouter, PacketRouter>> dispatchTable;

    public ShortestPathPacketRoutingAlgorithm() {}

    private ShortestPathPacketRoutingAlgorithm(final boolean dummy) {
        this.historyMap           = new HashMap<>();
        this.undeliveredPacketSet = new HashSet<>();
        this.queueLengthList      = new ArrayList<>();
        this.dispatchTable        = new HashMap<>();
    }

    @Override
    public SimulationStatistics simulate(final List<PacketRouter> network, 
                                         final List<Packet> packetList) {
        final ShortestPathPacketRoutingAlgorithm state = 
                new ShortestPathPacketRoutingAlgorithm(true);

        return state.simulateImpl(network, packetList);
    }    

    private SimulationStatistics simulateImpl(final List<PacketRouter> network,
                                              final List<Packet> packetList) {
        initializePackets(packetList);
        buildDispatchTable(network);

        undeliveredPacketSet.addAll(packetList);

        while (!undeliveredPacketSet.isEmpty()) {
            loadPacketRouterQueueLengths(network);
            simulateCycle(network);
            pruneDeliveredPackets();
            ++cycles;
        }

        return buildStatistics();
    }

    private void simulateCycle(final List<PacketRouter> network) {
        final Map<Packet, PacketRouter> map = new HashMap<>();

        // Find out to which packet routers to send the packets:
        for (final PacketRouter packetRouter : network) {
            if (packetRouter.queueLength() > 0) {
                final Packet packet = packetRouter.dequeuePacket();
                final PacketRouter targetRouterOfPacket = 
                        packet.getTargetPacketRouter();

                final PacketRouter nextPacketRouter = 
                        dispatchTable.get(packetRouter)
                                     .get(targetRouterOfPacket);

                map.put(packet, nextPacketRouter);
            }
        }

        // Send the packets:
        for (final Map.Entry<Packet, PacketRouter> entry : map.entrySet()) {
            final Packet packet = entry.getKey();
            final PacketRouter packetRouter = entry.getValue();
            packetRouter.enqueuePacket(packet);
        }

        // Update the history of each packet.
        for (final PacketRouter packetRouter : network) {
            for (final Packet packet : packetRouter.getQueue()) {
                historyMap.get(packet).add(packetRouter);
            }
        }
    }

    private void buildDispatchTable(final List<PacketRouter> network) {
        for (final PacketRouter source : network) {
            // Create the local dispatch table for the packet router 'source':
            final Map<PacketRouter, PacketRouter> parentMap = 
                    runBreadthFirstSearchFrom(source);

            final Map<PacketRouter, PacketRouter> localDispatchTable =
                    new HashMap<>();

            dispatchTable.put(source, localDispatchTable);

            for (final PacketRouter target : network) {
                if (target.equals(source)) {
                    // Trivial path (source -> source) does not have to be
                    // considered.
                    continue;
                }

                final List<PacketRouter> shortestPath = 
                        constructPath(target, parentMap);

                // shortestPath.get(0) is the source;
                // shortestPath.get(shortestPath.size() - 1) is the target;
                // If we want to reach 'target' from 'source' via a shortest 
                // path, we should move from 'source' to 
                // 'shortestPath.get(1)'.
                localDispatchTable.put(target, shortestPath.get(1));
            }
        }
    }

    private Map<PacketRouter, PacketRouter> 
        runBreadthFirstSearchFrom(final PacketRouter source) {
        final Deque<PacketRouter> queue = 
                new ArrayDeque<>(Arrays.asList(source));
        final Map<PacketRouter, PacketRouter> parentMap = new HashMap<>();
        parentMap.put(source, null);

        while (!queue.isEmpty()) {
            final PacketRouter current = queue.removeFirst();

            for (final PacketRouter neighbor : current.getNeighbors()) {
                if (!parentMap.containsKey(neighbor)) {
                    parentMap.put(neighbor, current);
                    queue.addLast(neighbor);
                }
            }
        }

        return parentMap;
    }

    private List<PacketRouter> constructPath(
            final PacketRouter target,
            final Map<PacketRouter, PacketRouter> parentMap) {
        final List<PacketRouter> path = new ArrayList<>();
        PacketRouter current = target;

        while (current != null) {
            path.add(current);
            current = parentMap.get(current);
        }

        Collections.<PacketRouter>reverse(path);
        return path;
    }
}

Packet.java:

package net.coderodde.simulation.network;

import java.util.Objects;

/**
 * This class implements a simulated packet being transmitted in the network.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61 (Jul 10, 2016)
 */
public final class Packet {

    private final int id;
    private final PacketRouter sourcePacketRouter;
    private final PacketRouter targetPacketRouter;

    public Packet(final int id, 
                  final PacketRouter sourcePacketRouter,
                  final PacketRouter targetPacketRouter) {
        this.id = id;
        this.sourcePacketRouter = 
                Objects.requireNonNull(sourcePacketRouter,
                                       "The source packet router is null.");
        this.targetPacketRouter =
                Objects.requireNonNull(targetPacketRouter,
                                       "The target packet router is null.");

        if (sourcePacketRouter.equals(targetPacketRouter)) {
            throw new IllegalArgumentException(
                    "The source and target routers are same: " +
                    sourcePacketRouter);
        }
    }

    public int getId() {
        return id;
    }

    public PacketRouter getSourcePacketRouter() {
        return sourcePacketRouter;
    }

    public PacketRouter getTargetPacketRouter() {
        return targetPacketRouter;
    }

    @Override
    public boolean equals(final Object o) {
        if (o == null) {
            return false;
        }

        if (!getClass().equals(o.getClass())) {
            return false;
        }

        return id == ((Packet) o).id;
    }

    @Override
    public int hashCode() {
        return id;
    }
}

PacketRouter.java:

package net.coderodde.simulation.network;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;

/**
 * This class defines a packet router in a simulated network. Each 
 * {@code PacketRouter} maintains a FIFO queue of packets that have been 
 * received but not yet sent away. The routers work in cycles. At each cycle the
 * router may send away at most one packet (provided that the packet queue is 
 * not empty), and receive any number of packets.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 10, 2016)
 */
public final class PacketRouter {

    /**
     * The ID of the packet router. The IDs must be unique.
     */
    private final int id;

    /**
     * The list of packet routers to which there is an undirected link from this
     * packet router.
     */
    private final List<PacketRouter> neighbors = new ArrayList<>();

    /**
     * The internal queue of packets not yet emitted.
     */
    private final Deque<Packet> queue = new ArrayDeque<>();

    public PacketRouter(final int id) {
        this.id = id;
    }

    public final void connect(final PacketRouter neighborPacketRouter) {
        Objects.requireNonNull(neighborPacketRouter,
                               "The input neighbor packet router is null.");

        if (!neighbors.contains(neighborPacketRouter)) {
            neighbors.add(neighborPacketRouter);
            neighborPacketRouter.neighbors.add(this);
        }
    }

    public final List<PacketRouter> getNeighbors() {
        return Collections.<PacketRouter>unmodifiableList(neighbors);
    }

    public Collection<Packet> getQueue() {
        return Collections.<Packet>unmodifiableCollection(queue);
    }

    /**
     * Removes the delivered packet from the queue. This {@code PacketRouter} 
     * must be the target packet router of {@code packet}.
     * 
     * @param packet 
     */
    public void remove(final Packet packet) {
        if (!packet.getTargetPacketRouter().equals(this)) {
            throw new IllegalArgumentException(
                    "The input packet is not in its " +
                    "destination packet router.");
        }

        queue.remove(packet);
    }

    public int queueLength() {
        return queue.size();
    }

    public void enqueuePacket(final Packet packet) {
        queue.addLast(packet);
    }

    public Packet dequeuePacket() {
        return queue.removeFirst();
    }

    public void clearQueue() {
        queue.clear();
    }

    @Override
    public boolean equals(final Object o) {
        if (o == null || !getClass().equals(o.getClass())) {
            return false;
        }

        return id == ((PacketRouter) o).id;
    }

    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();

        sb.append("[PacketRouter: id = ")
          .append(id)
          .append(", neighbors = <");

        if (!neighbors.isEmpty()) {
            sb.append(neighbors.get(0).id);
        }

        for (int i = 1; i < neighbors.size(); ++i) {
            sb.append(", ").append(neighbors.get(i).id);
        }

        sb.append(">, queue = <");

        final Iterator<Packet> iterator = queue.iterator();

        if (iterator.hasNext()) {
            sb.append(iterator.next().getId());
        }

        while (iterator.hasNext()) {
            sb.append(", ").append(iterator.next().getId());
        }

        sb.append(">]");

        return sb.toString();
    }
}

SimulationStatistics.java:

package net.coderodde.simulation.network;

/**
 * This class holds statistical results of a simulation. The data includes
 * <ul>
 *   <li>the minimum queue length,</li>
 *   <li>the maximum queue length,</li>
 *   <li>the average queue length,</li>
 *   <li>the standard deviation of the queue lengths,</li>
 *   <li>the minimum transmission duration,</li>
 *   <li>the maximum transmission duration,</li>
 *   <li>the average transmission duration,</li>
 *   <li>the standard deviation of the transmission duration,</li>
 *   <li>the number of network cycles needed to deliver all packets.</li>
 * </ul>
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 10, 2016)
 */
public class SimulationStatistics {

    private final int minimumQueueLength;
    private final int maximumQueueLength;
    private final double averageQueueLength;
    private final double queueLengthStandardDeviation;

    private final int minimumTransmissionDuration;
    private final int maximumTransmissionDuration;
    private final double averageTransmissionDuration;
    private final double transmissionDurationStandardDeviation;

    private final int networkCycles;

    SimulationStatistics(final int minimumQueueLength,
                         final int maximumQueueLength,
                         final double averageQueueLength,
                         final double queueLengthStandardDeviation,
                         final int minimumTransmissionDuration,
                         final int maximumTransmissionDuration,
                         final double averageTransmissionDuration,
                         final double transmissionDurationStandardDeviation,
                         final int networkCycles) {
        this.minimumQueueLength = minimumQueueLength;
        this.maximumQueueLength = maximumQueueLength;
        this.averageQueueLength = averageQueueLength;
        this.queueLengthStandardDeviation = queueLengthStandardDeviation;
        this.minimumTransmissionDuration = minimumTransmissionDuration;
        this.maximumTransmissionDuration = maximumTransmissionDuration;
        this.averageTransmissionDuration = averageTransmissionDuration;
        this.transmissionDurationStandardDeviation =
                transmissionDurationStandardDeviation;
        this.networkCycles = networkCycles;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();

        // Packet queue statistics:

        sb.append("Minimum queue length:          ")
          .append(minimumQueueLength)
          .append("\n");

        sb.append("Maximum queue length:          ")
          .append(maximumQueueLength)
          .append("\n");

        sb.append("Average queue length:          ")
          .append(averageQueueLength)
          .append("\n");

        sb.append("Queue length s.d.:             ")
          .append(queueLengthStandardDeviation)
          .append("\n");

        // Delivery time statistics:

        sb.append("Minimum transmission duration: ")
          .append(minimumTransmissionDuration)
          .append("\n");

        sb.append("Maximum transmission duration: ")
          .append(maximumTransmissionDuration)
          .append("\n");

        sb.append("Average transmission duration: ")
          .append(averageTransmissionDuration)
          .append("\n");

        sb.append("Transmission duration s.d.:    ")
          .append(transmissionDurationStandardDeviation)
          .append("\n");

        sb.append("Total network cycles:          ")
          .append(networkCycles);

        return sb.toString();
    }
}

Demo.java:

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import net.coderodde.simulation.network.Packet;
import net.coderodde.simulation.network.PacketRouter;
import net.coderodde.simulation.network.AbstractPacketRoutingAlgorithm;
import net.coderodde.simulation.network.LearningPacketRoutingAlgorithm;
import net.coderodde.simulation.network.RandomPacketRoutingAlgorithm;
import net.coderodde.simulation.network.ShortestPathPacketRoutingAlgorithm;
import net.coderodde.simulation.network.SimulationStatistics;

public class Demo {

    private static final int DEFAULT_NUMBER_OF_ROUTERS = 50;
    private static final int DEFAULT_NUMBER_OF_LINKS   = 350;
    private static final int DEFAULT_NUMBER_OF_PACKETS = 1000;

    private static final int MINIMUM_NUMBER_OF_ROUTERS = 1;
    private static final int MINIMUM_NUMBER_OF_LINKS   = 1;
    private static final int MINIMUM_NUMBER_OF_PACKETS = 1;

    private static final int BAR_LENGTH = 80;
    private static final char BAR_CHAR = '-';
    private static final String BAR;

    static {
        final StringBuilder sb = new StringBuilder(BAR_LENGTH);

        for (int i = 0; i < BAR_LENGTH; ++i) {
            sb.append(BAR_CHAR);
        }

        BAR = sb.toString();
    }

    public static enum ErrorCondition {

        BAD_ROUTERS_TOKEN (1),
        TOO_LITTLE_ROUTERS(2),

        BAD_LINKS_TOKEN   (3),
        TOO_LITTLE_LINKS  (4),

        BAD_PACKETS_TOKEN (5),
        TOO_LITTLE_PACKETS(6),

        NETWORK_DISCONNECTED(7);

        ErrorCondition(final int returnCode) {
            this.returnCode = returnCode;
        }

        public int code() {
            return returnCode;
        }

        private final int returnCode;
    }

    private static final String USAGE_INFO = 
            "Usage: java -jar This.jar [ROUTERS LINKS PACKETS]\n" +
            "Where: \n" +
            "    ROUTERS the number of routers in the network.\n" +
            "    LINKS   the number of links between routers.\n" +
            "    PACKETS the number of packets to simulate.\n";

    public static void main(final String[] args) {
        int routers = DEFAULT_NUMBER_OF_ROUTERS;
        int links   = DEFAULT_NUMBER_OF_LINKS;
        int packets = DEFAULT_NUMBER_OF_PACKETS;

        if (args.length != 0) {
            if (args.length != 3) {
                printUsageInfo();
                return;
            }

            // Try read the number of routers from the command line.
            try {
                routers = Integer.parseInt(args[0]);
            } catch (final NumberFormatException ex) {
                System.err.println(
                        "ERROR: Cannot parse the number of routers: \"" +
                        args[0] + "\".");
                System.exit(ErrorCondition.BAD_ROUTERS_TOKEN.code());
            }

            if (routers < MINIMUM_NUMBER_OF_ROUTERS) {
                System.err.println("ERROR: The number of routers is too " +
                                   "small (" + routers + "). Must be at " +
                                   "least " + MINIMUM_NUMBER_OF_ROUTERS + ".");
                System.exit(ErrorCondition.TOO_LITTLE_ROUTERS.code());
            }

            // Try read the number of links from the command line.
            try {
                links = Integer.parseInt(args[1]);
            } catch (final NumberFormatException ex) {
                System.err.println(
                        "ERROR: Cannot parse the number of links: \"" +
                        args[1] + "\".");
                System.exit(ErrorCondition.BAD_LINKS_TOKEN.code());
            }

            if (links < MINIMUM_NUMBER_OF_LINKS) {
                System.err.println("ERROR: The number of links is too " +
                                   "small (" + links + "). Must be at " +
                                   "least " + MINIMUM_NUMBER_OF_LINKS + ".");
                System.exit(ErrorCondition.TOO_LITTLE_LINKS.code());
            }

            // Try read the number of packets from the command line.
            try {
                packets = Integer.parseInt(args[2]);
            } catch (final NumberFormatException ex) {
                System.err.println(
                        "ERROR: Cannot parse the number of packets: \"" +
                        args[2] + "\".");
                System.exit(ErrorCondition.BAD_PACKETS_TOKEN.code());
            }

            if (packets < MINIMUM_NUMBER_OF_PACKETS) {
                System.err.println("ERROR: The number of routers is too " +
                                   "small (" + routers + "). Must be at " +
                                   "least " + MINIMUM_NUMBER_OF_PACKETS + ".");
                System.exit(ErrorCondition.TOO_LITTLE_PACKETS.code());
            }
        }

        final long seed = System.nanoTime();
        final Random random = new Random(seed);

        System.out.println("[INFO] Seed = " + seed);
        System.out.println("[INFO] Requested number of routers: " + routers);
        System.out.println("[INFO] Requested number of links:   " + links);
        System.out.println("[INFO] Requested number of packets: " + packets);
        System.out.println("[STATUS] Building the network...");

        long startTime = System.nanoTime();
        final List<PacketRouter> network = createRandomNetwork(routers,
                                                               links, 
                                                               random);
        long endTime = System.nanoTime();

        System.out.printf ("[STATUS] Network build in %.1f milliseconds!\n",
                           (endTime - startTime) / 1e6);

        if (!inputNetworkIsConnected(network)) {
            System.err.println(
                    "ERROR: The constructed network is disconnected.");
            System.exit(ErrorCondition.NETWORK_DISCONNECTED.code());
        }

        final List<Packet> packetList = createRandomPacketList(network, 
                                                               packets, 
                                                               random);
        final AbstractPacketRoutingAlgorithm algorithm1 = 
                new RandomPacketRoutingAlgorithm();

        final LearningPacketRoutingAlgorithm algorithm2 =
                new LearningPacketRoutingAlgorithm();

        algorithm2.setCycleLimit(4000);

        final AbstractPacketRoutingAlgorithm algorithm3 = 
                new ShortestPathPacketRoutingAlgorithm();

        profile(algorithm1, network, packetList);
        profile(algorithm2, network, packetList);
        profile(algorithm3, network, packetList);
    }

    private static void profile(final AbstractPacketRoutingAlgorithm algorithm,
                                final List<PacketRouter> network,
                                final List<Packet> packetList) {
        final long startTime = System.nanoTime();
        final SimulationStatistics statistics = algorithm.simulate(network, 
                                                                   packetList);
        final long endTime = System.nanoTime();

        System.out.println(BAR);
        System.out.printf(
                "[STATISTICS] Actual simulation time: %.1f milliseconds.\n", 
                (endTime - startTime) / 1e6);

        System.out.println("[STATISTICS] Algorithm class: " + 
                           algorithm.getClass().getSimpleName());
        System.out.println("[STATISTICS] Result:");
        System.out.println(statistics);
    }

    private static void printUsageInfo() {
        System.out.println(USAGE_INFO);
    }

    private static List<Packet> 
        createRandomPacketList(final List<PacketRouter> network,
                               final int numberOfPackets,
                               final Random random) {
        if (network.size() < 2) {
            return new ArrayList<>();
        }

        final List<Packet> packetList = new ArrayList<>(numberOfPackets);

        for (int id = 0; id < numberOfPackets; ++id) {
            final PacketRouter sourcePacketRouter = 
                    network.get(random.nextInt(network.size()));

            PacketRouter targetPacketRouter;

            do {
                targetPacketRouter = 
                        network.get(random.nextInt(network.size()));
            } while (targetPacketRouter.equals(sourcePacketRouter));

            packetList.add(new Packet(id, 
                                      sourcePacketRouter, 
                                      targetPacketRouter));
        }

        return packetList;
    }

    private static boolean 
        inputNetworkIsConnected(final List<PacketRouter> network) {
        if (network.isEmpty()) {
            throw new IllegalArgumentException("The input network is empty.");
        }

        final Set<PacketRouter> networkAsSet = new HashSet<>(network);
        final Set<PacketRouter> visitedSet = new HashSet<>();
        final Deque<PacketRouter> queue = new ArrayDeque<>();

        queue.add(networkAsSet.iterator().next());

        while (!queue.isEmpty()) {
            final PacketRouter current = queue.removeFirst();

            for (final PacketRouter neighbor : current.getNeighbors()) {
                if (!visitedSet.contains(neighbor)) {
                    visitedSet.add(neighbor);
                    queue.addLast(neighbor);
                }
            }
        }

        return visitedSet.size() == networkAsSet.size();
    }    

    private static List<PacketRouter> createRandomNetwork(final int routers,
                                                          int links,
                                                          final Random random) {
        final List<PacketRouter> network = new ArrayList<>(routers);

        for (int id = 0; id < routers; ++id) {
            network.add(new PacketRouter(id));
        }

        final int maximumNumberOfLinksPossible = routers * (routers - 1) / 2;

        final List<Point> linkDescriptorList = 
                new ArrayList<>(maximumNumberOfLinksPossible); 

        for (int startId = 0; startId < routers; ++startId) {
            for (int endId = startId + 1; endId < routers; ++endId) {
                linkDescriptorList.add(new Point(startId, endId));
            }
        }

        if (linkDescriptorList.isEmpty()) {
            // No links possible due to too small number of routers.
            return network;
        }

        Collections.<Point>shuffle(linkDescriptorList, random);

        links = Math.min(links, maximumNumberOfLinksPossible);

        for (int i = 0; i < links; ++i) {
            final Point point = linkDescriptorList.get(i);
            network.get(point.x).connect(network.get(point.y));
        }

        return network;
    }
}

Demonstration

I get more or less the following output:

[INFO] Seed = 58423324954053
[INFO] Requested number of routers: 50
[INFO] Requested number of links:   350
[INFO] Requested number of packets: 1000
[STATUS] Building the network...
[STATUS] Network build in 35.8 milliseconds!
--------------------------------------------------------------------------------
[STATISTICS] Actual simulation time: 446.8 milliseconds.
[STATISTICS] Algorithm class: RandomPacketRoutingAlgorithm
[STATISTICS] Result:
Minimum queue length:          0
Maximum queue length:          142
Average queue length:          7.825630026809652
Queue length s.d.:             19.78700477214822
Minimum transmission duration: 2
Maximum transmission duration: 1866
Average transmission duration: 730.74
Transmission duration s.d.:    475.4296643729393
Total network cycles:          1866
--------------------------------------------------------------------------------
[STATISTICS] Actual simulation time: 107.9 milliseconds.
[STATISTICS] Algorithm class: LearningPacketRoutingAlgorithm
[STATISTICS] Result:
Minimum queue length:          0
Maximum queue length:          42
Average queue length:          10.291780821917808
Queue length s.d.:             9.089401786447638
Minimum transmission duration: 2
Maximum transmission duration: 74
Average transmission duration: 38.565
Transmission duration s.d.:    16.462830856198448
Total network cycles:          74
--------------------------------------------------------------------------------
[STATISTICS] Actual simulation time: 86.6 milliseconds.
[STATISTICS] Algorithm class: ShortestPathPacketRoutingAlgorithm
[STATISTICS] Result:
Minimum queue length:          0
Maximum queue length:          37
Average queue length:          8.803928571428571
Queue length s.d.:             9.352746553320292
Minimum transmission duration: 2
Maximum transmission duration: 57
Average transmission duration: 25.651
Transmission duration s.d.:    11.983939828529424
Total network cycles:          57

Critique request

As always, please tell me anything that comes to mind.

\$\endgroup\$
  • \$\begingroup\$ Why's the output bolded? \$\endgroup\$ – Pimgd Jul 19 '16 at 14:06
  • \$\begingroup\$ I (personally) find it more readable. \$\endgroup\$ – coderodde Jul 19 '16 at 14:07
  • \$\begingroup\$ @Pimgd Updated! \$\endgroup\$ – coderodde Jul 19 '16 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.