Sinalgo

While running any simulation, it is crucial to understand how the simulation simplifies from a real network. For example, Sinalgo simulates the physical propagation of transmissions only very superficially (in contrast to other simulators, such as ns2). In the remainder of this section, we describe the operating mode of Sinalgo on a high level. We stick as close as possible to the implementation, such that the simplifications/abstractions from reality can be easily spotted.

Node Storage

Sinalgo provides support to perform range queries, which return a set of potential neighbors for a given node. To perform these range queries, Sinalgo stores the nodes in a specialized data structure. In the default distribution, Sinalgo stores the nodes in a GeometricNodeCollection, which implements the NodeCollectionInterface. Because these range queries depend on the maximum distance between any two connected nodes, the GeometricNodeCollection needs to be configured through the project configuration file. It requires an entry of the following form, where rMax specifies the maximum distance between any two connected nodes.

The NodeCollectionInterface interface provides a method getPossibleNeighborsEnumeration(Node n), which returns an enumeration over all potential neighbors of a given node. Using this method, the connectivity model only needs to test a subset of all nodes, which increases the simulation time considerably. The ConnectivityModelHelper located in the package sinalgo.models gives an example on how to use this range query.

Note: The GeometricNodeCollection comes in two flavors, one for 2D and one for 3D. However, you may implement your own subclass of NodeCollectionInterface to obtain range queries that depend on other criteria. The project configuration file contains an entry which specifies the node collection implementation to use.

Implementation Note: The GeometricNodeCollection partitions the deployment area in a 2-dimensional (3-dimensional) grid with cell-size rMax. Each cell stores the nodes that are contained within its boundaries. Whenever a node moves into a different cell, this data structure is updated to reflect the new situation. A range query for a given node n determines the cell c in which n is located, and returns the nodes contained in c and any cell adjacent to c. Thus, getPossibleNeighborsEnumeration(Node n) returns the nodes contained in 9 cells in 2D, and the content of 27 cells in 3D.

Synchronous vs Asynchronous Mode

The simulation mode determines when exactly the method handleMessage() is called when a node receives a message, and when exactly the timers are fired when they expired.

Synchronous Simulation

The synchronous simulation is based on rounds. At the beginning of each round, the framework increments the global time by one unit. Then, it moves the nodes according to their mobility models and updates the connections according to the connectivity model. After that, the framework iterates over the set of nodes and performs the method step() on each node. The calling sequence of this method is described in the Node Implementation tutorial. The nodes are visited in a framework specific order, which the simulation should not rely on.

Each message and timer carries a time stamp that indicates at which time the event (arrival of message, execution of timer-handler) should happen. Because the time advances in steps of 1 unit, each node handles in its step() method all events whose time stamp is smaller or equal to the current time. For both, the set of messages and the set of timers, the node sorts the events according to their time stamp, such that the events happen in order on each individual node.

Note: From a global view, the message receptions and timer-handlers may not be executed in order: Suppose the case where node A receives a message M1 at 15.23 and M2 at 15.88 and node B receives a message M3 at 15.17 and M4 at 15.77. If the framework first executes the step() method on node A, then the messages M1 and M2 are handled prior to the messages M3 and M4, which are only handled in the call to step() of node B.

Implementation Note: If your project simulates mobile nodes, the position of the nodes is updated at the beginning of every round. As a result, the nodes hop around, which does not quite correspond a continuous path. To achieve a better approximation, you may increase the time resolution of the simulation by a given factor, e.g. 10: Decrease the node speed by this factor, and increase the message delivery time, as well as the countdown-time of all timers by the same factor. This inserts several (in this case 9) more rounds for the same distance a node moves, which gives a better approximation of the movement.

Asynchronous Simulation

The asynchronous simulation is purely event based. The framework holds a list of message events and timer events, which is sorted by the time when these events should happen (arrival of message, execution of timer-handler). The framework repeatedly picks the most recent event and executes it.

In a typical simulation, some of the events issue further events, which prevent the event list from draining. If the list empties anyways, the framework calls the handleEmptyEventQueue method of the project's CustomGlobal class. This method may issue further events to continue the simulation.

In general, the asynchronous simulation mode runs much faster than the synchronous mode. The main reason lies in the fact that the synchronous simulation mode loops over all nodes and performs for each node the step() method even if most of the nodes may not do anything at all. This is in sharp contrast to the asynchronous mode, where only message and timer events are processed and no unnecessary cycles are wasted. But to achieve its speed, the asynchronous mode is more limited: it does not support mobility. I.e. the nodes cannot change their position over time. (The framework configuration entry mobility needs to be set to false, such that the mobility model assigned to each node is not considered.) The reason for this limitation on the asynchronous mode is the continuity of the node movement, which does not allow to be described in terms of events. (Note that also the synchronous mode does not perform continuous moves, but moves the nodes in hops at the beginning of every round.)

Message Delivery

The receiver of the message can retrieve this information for each received message in the handleMessages() through the Inbox object.

Project developers only get in touch with Packet objects when implementing a new interference model. The member

indicates whether the message hold in the packet will be received properly at the destination. If this flag is set to false, the receiving node will not include the corresponding message in the inbox, handed over to the handleMessages() method.

Refer to the Node Implementation part of this tutorial for more information on how to implement project specific messages.

Network Edges

Sinalgo requires that the same edge object is present between two nodes until the connection breaks. Upon reconnection of the two nodes, a new edge object has to be used. To distinguish edges, each edge object carries a unique ID.

The send and broadcast methods provided by the node superclass deliver messages only if the sending node has an outgoing edge to the destination. The method sendDirect is an exception: it is the only method that does not test whether the sender and receiver are really interconnected. This latter method may be used to simulate a wired overlay network, or to send messages between network nodes that are connected through another means.

Note: Especially when manually adding an edge in GUI mode, remember that the added edge is unidirectional. To connect two nodes A and B in both direction, you need to add an edge from A to B, and another edge from B to A. To avoid this issue, you may want to use bidirectional edges.

Bidirectional Edges

The use of unidirectional links may be desirable to simulate lossy and unpredictable networks. However, one may often want to abstract from these low-level issues and only consider bidirectional links. To ensure, that there is either no link at all between two nodes, or a link in both directions (a bidirectional link), use the BidirectionalEdge. This edge implementation automatically ensures that there is an edge in both directions between a given pair of nodes.

To implement bidirectional edges, and to draw edges properly, each edge (not only the bidirectional ones) has a member oppositeEdge, which points to the edge that connects the two end-nodes in the opposite direction, or is null, if there is no such edge.

Edge Creation, valid Flag

At any time, Sinalgo uses the same edge type for all edges - the framework holds one global factory that creates the new edges. The type of edges to be used is defined in the configuration file, and may be changed at runtime. But note that when changing the edge type at runtime, the existing edge objects are not replaced and thus implement the previous edge type. A change of the edge time at runtime only affects edges that are added to the network graph afterwards.

We have seen that the Connectivity Model determines to which other nodes a given node N is connected by adding and removing edges from the outgoingConnections list of N. In most cases, this model is too powerful, and the simpler ConnectivityModelHelper class can be used, where the subclass only needs to answer whether node N is connected to another node B. If node N has a (unidirectional) connection to node A, the model calls N.outgoingConnections.add(N, B, true);, which adds an edge NB to the set of outgoing connections of node N. If the edge already exists, the call to add does not replace the existing edge.

The removal of the edges is somewhat more involved, because Sinalgo requires the same edge object to remain installed until the corresponding connection breaks up. Therefore, we may not just empty the set of outgoing connections before calling the connectivity model. Sinalgo proposes to handle this issue using the valid member of each edge: Whenever the connectivity model calls N.outgoingConnections.add(N,B,true) to ensure that there is an edge NB, the valid flag of the added (or already existing) edge is set to true. Before the connectivity model returns, it calls N.outgoingConnections.removeInvalidLinks(), which iterates over all outgoing edges of N and removes the ones whose valid flag is false. (At the same time, the method resets the valid flags to false for the next round.)

Interference

Each sender node can send its message with a given signal power, which we call intensity. The interference model can use the set of all messages and their corresponding intensity to determine the noise-level a given receiver node experiences.

One example is the SINR interference model, which assumes a signal decay exponential to the Euclidean distance to the sender. Roughly speaking, SINR drops a message if the signal of the message at the receiver is below the sum of all interfering signals times a given constant. A sample implementation of SINR is provided in the defaultProject.

Memory Management

It seems that Java's garbage collector (GC) has a hard time when the application constantly creates a huge amount of small, short living objects. But that's exactly what our simulation framework does: For every message that is being sent, there are at least two new objects allocated, and if the network graph changes frequently, many edge objects need to be allocated.

To alleviate this problem, Sinalgo tries to recycle objects as often as possible: Instead of returning a removed edge to the GC, Sinalgo stores the edge object for reuse the next time an edge object of this type is needed. The same holds for the packets, which encapsulate the messages sent by the nodes. After a message arrived at its destination, the corresponding packet object is returned to Sinalgo for storage. Whenever a message is sent, Sinalgo only creates a new packet object if there is no recycled packet left.

Note: Remind from the message implementation section that a sent message object is cloned by default. To save memory, a project may apply a read-only policy for all messages, in which case the cloning of the messages can be circumvented. This preserves a lot of memory, especially for broadcast messages.

Sinalgo - Simulator for Network Algorithms

Insight Into the Clockwork of Sinalgo