We consider a system of parallel queues where tasks are assigned (dispatched) to one of the available servers upon arrival. The dispatching decision is based on the full state information, i.e., on the sizes of the new and existing jobs. We are interested in minimizing the so-called mean slowdown criterion corresponding to the mean of the sojourn time divided by the processing time. Assuming no new jobs arrive, the shortest-processing-time-product (SPTP) schedule is known to minimize the slowdown of the existing jobs. The main contribution of this paper is three-fold: 1) To show the optimality of SPTP with respect to slowdown in a single server queue under Poisson arrivals; 2) to derive the so-called size-aware value functions for M/G/1-FIFO/LIFO/SPTP with general holding costs of which the slowdown criterion is a special case; and 3) to utilize the value functions to derive efficient dispatching policies so as to minimize the mean slowdown in a heterogeneous server system. The derived policies offer a significantly better performance than e.g., the size-aware-task-assignment with equal load (SITA-E) and least-work-left (LWL) policies.

We consider a dynamic dispatching problem where jobs are assigned upon arrival into parallel queues. Jobs have an arbitrary size distribution and each queue has its own service rate, queueing discipline, and operating power while serving jobs. Our goal is to minimize a weighted sum of delay and energy consumption under the assumption that the dispatcher is aware of the remaining service time of each job in the system, including that of the arriving job. We devise efficient dispatching heuristics based on the first policy iteration procedure of Markov Decision Processes. The resulting policies are illustrated by numerical examples. Direct control over the trade-off between performance and energy consumption will be increasingly important in future ICT equipment designs wherever dynamic queue assignment is needed.

We consider service systems where new jobs not only increase the load but also improve the service ability of such a system, cf. opportunistic scheduling gain in wireless systems. We study the optimal trade-off between the SRPT (Shortest Remaining Processing Time) discipline and opportunistic scheduling in the systems characterized by compact and symmetric capacity regions. The objective is to minimize the mean delay in a transient setting where all jobs are available at time 0 and no new jobs arrive thereafter. Our main result gives conditions under which the optimal rate vector does not depend on the sizes of the jobs as long as their order (in size) remains the same. In addition, it shows that in this case the optimal policy applies the SRPT principle serving the shortest job with the highest rate of the optimal rate vector, the second shortest with the second highest rate etc. We also give a recursive algorithm to determine both the optimal rate vector and the minimum mean delay. In some special cases, the rate vector, as well as the minimum mean delay, have even explicit expressions as demonstrated in the paper. For the general case, we derive both an upper bound and a lower bound of the minimum mean delay.

We consider dimensioning of data networks. The network is modeled in a dynamic setting where elastic flows (file transfers) arrive randomly and share the bandwidth according to balanced fairness. Simple methods are derived for determining the link capacities so that given flow-level throughput requirements are satisfied. We consider two different approaches to define the throughput requirements: single constraint on average throughput in the network and separate constraint for every route. The results enable a simple characterization of the order- of-magnitude of the required capacities, which can be utilized in practical network planning and dimensioning.

We study a time slotted random access network carrying elastic data traffic. We assume that the link access probabilities can be controlled on time scales comparable to network flow state changes but remain constant on shorter time scales and in particular do not react to slot-level backlogs. Capacity sets of such networks are defined, i.e. the effective link capacities which can be achievedby tuning the transmission probabilities. We revisit the problem of finding the capacity set and give an analytical characterization for the case of a single resource, which was derived already by Kleinrock. For the multihop case we provide a general algorithm to determine the boundary of the capacity set. The main contribution of the paper is to combine the capacity set results with the concept of balanced fairness to analyze the file transfer throughputs in a dynamic setting where a stochastically evolving number of file transfers adapt their rates to share the network resources among each other. Our numerical analysis shows that for light loads and short routes the throughput under flow-optimized random access is close to optimal that of slot-by-slot link scheduling, even though the control time scale required by the random access is much slower. With heavy loads the performance deteriorates.

We give an example of flow level performance analysis of data traffic in wireless networks by studying a scenario where two base stations with link adaptation serve in a coordinated fashion downloading users on a road or street between the stations. Due to the dynamic nature of such systems, a detailed flow level analysis is challenging and conventional methods run into computational difficulties. We motivate the detailed analysis by studying the system under different operational goals such as maximum throughput, max-min fairness and balanced fairness, concluding that the performance under these dynamic policies differ significantly from the performance under more tractable static policies. We discuss how the corresponding numerical analyses can be facilitated by applying the notion of balanced fairness and, in particular, introduce a novel approximation method referred to as value extrapolation. Value extrapolation can be applied to approximate any performance measure expressed as the expected value of a random variable which is a function of the system state. The idea of the value extrapolation is to consider the system in the MDP (Markov Decision Processes) setting and to solve the expected value from the Howard equations written for a truncated state space. Instead of a simple truncation, the relative values of states just outside the truncated state space are estimated using a polynomial extrapolation based on the states inside. This leads to a closed system and, unless the system is heavily loaded, allows one to obtain accurate results with remarkably small truncated state spaces.

We propose a simple nearly-optimal heuristic algorithm for multicast tree construction in static ad hoc networks. The objective is to deliver a data packet from a source node to a set of destination nodes with a sequence of transmissions so that the sum of given transmission-related costs is minimized. Also a brute-force enumeration method is described to obtain optimal solutions to the problem in unit cost case. Performance of the algorithms is compared against existing methods by simulations.

We propose an efficient heuristic algorithm for multicast tree construction in ad hoc networks. The objective is to connect a source node to a set of destination nodes with a sequence of transmissions so that the number of transmissions is minimized. The algorithm utilizes shortest path information, which can be obtained from unicast routing tables for fully distributed implementation. In addition to multicast routing, the algorithm is applicable to stateless multicast forwarding for small multicast groups.

We consider wireless multicast tree construction for energy efficiency. We introduce a novel algorithm, incremental shortest path tree (ISPT), to generate source-based multicast trees and analyse its performance. Additionally, the potential of further improvements in the tree construction is addressed comparing the performance of the algorithm with the results from a simulated annealing optimisation.