Simulations of a self-organized scheduling based on a dynamical system

Models of the Internet Topology

In order to achieve realistic simulations, the network topologies are generated randomly within a specified range for latencies and the number of nodes inside each type of network. We distinguished between a fast, a standard, and a slow type of local area network (LAN), as well as between a short-range and a medium-range optical carrier connection. In addition, networks connected by a digital subscriber line (DSL) are taken into account.

network

round trip time in microseconds

slow LAN

150-260

standard LAN

80-150

fast LAN

10-80

DSL

1000-1500

backbone segment

20-50

Visualization

The round trip time (RTT) between two nodes provides a distance measure. Accordingly, two well-connected nodes in terms of a small RTT can be regarded as close to each other. The round trip time between two directly connected nodes is depicted by the line width of the connection. Greater RTTs are represented by a reduced line width. Since an isometric projection into a two dimensional euclidean space is impossible, the length of a connection does not say much about the latency concerned with this connection.

Results

The following computer animation of the dynamical system of disposition values is based on a numerical simulation of the interactions between nodes. The animation illustrates that the disposition successively converges to a stable distribution within a few time steps. Nodes with a positive disposition value are indicated by a shaded background. The intensity of the shade corresponds to the magnitude of the disposition value.

The dynamical system performs a clustering of well-connected nodes with positive disposition values. These nodes form discrete domains that are readily identifiable and appear as islands. In some cases, however, several islands merge into a connected domain of positive disposition values, i.e. a single cluster of well-connected nodes. An example for two islands that constitute such a cluster is given by the two fast LANs. This cluster is depicted in the figure below. Here, one of the gateways is the node with the highest disposition value inside this cluster. We to refer to such a node as the Primary Scheduler of the domain and use its disposition value as a decision criterion for the job scheduling within the P2P system.

Another domain of positive disposition values is shown in the figure below. Despite of the standard connectivity within this network, disposition values are relatively high due to the large number of nodes in this LAN.

Further simulation results

single domain	224 nodes	291 nodes	415 nodes	594 nodes	808 nodes

Last modified: Thu Feb 05 20:33:00 CET 2009