Symbiotic job scheduling exploits the fact that in a system with shared resources, the performance of jobs is impacted by the behavior of other co-running jobs. By coscheduling combinations of jobs that have low interference, the performance of a system can be increased. In this paper, we investigate the impact of using symbiotic job scheduling for increasing throughput. We find that even for a theoretically optimal scheduler, this impact is very low, despite the substantial sensitivity of per job performance to which other jobs are coscheduled: for example, our experiments on a 4-thread SMT processor show that, on average, the job IPC varies by 37% depending on coscheduled jobs, the per-coschedule throughput varies by 69%, and yet the average throughput gain brought by optimal symbiotic scheduling is only 3%. This small margin of improvement can be explained by the observation that all the jobs need to be eventually executed, restricting the job combinations a symbiotic job scheduler can select to optimize throughput. We explain why previous work reported a substantial gain from symbiotic job scheduling, and we find that (only) reporting turnaround time can lead to misleading conclusions. Furthermore, we show how the impact of scheduling can be evaluated in microarchitectural studies, without having to implement a scheduler.

As internet traffic will further increase in coming years, the current network infrastructure will have to grow along in terms of capacity. To this end, optical packet/burst switching have been proposed, allowing more efficient use of the available fiber capacity. To resolve packet contention in the involved optical switches, Fiber Delay Lines (for delay assignment) and wavelength converters (for wavelength conversion) are used to reschedule the contending packets, by means of a scheduling algorithm. Existing algorithms are effective when employed with an infinite number of converters, but generally perform poorly when the number of wavelength converters is small, as is the case in most switch prototype architectures. In this paper, several parametric cost-based scheduling algorithms are proposed that take scarcity of both FDLs and converters into account. Results obtained by Monte Carlo simulation show that these algorithms not only enable improved performance (in terms of packet loss probability), but also reduce the usage of the wavelength converters, and thus, the switch's overall energy consumption.

Running multiple programs on a processor aims at increasing the throughput of that processor. However, defining meaningful throughput metrics in a simulation environment is not as straightforward as reporting execution time. This has led to an ongoing debate on what forms a meaningful throughput metric for multiprogram workloads. We present a method to construct throughput metrics in a systematic way: we start by expressing assumptions on job size, job distribution, scheduling, and so forth that together define a theoretical throughput experiment. The throughput metric is then the average throughput of this experiment. Different assumptions lead to different metrics, so one should be aware of these assumptions when making conclusions based on results using a specific metric. Throughput metrics should always be defined from explicit assumptions, because this leads to a better understanding of the implications and limits of the results obtained with that metric. We elaborate multiple metrics based on different assumptions. In particular, we identify the assumptions that lead to the commonly used weighted speedup and harmonic mean of speedups. Our study clarifies that they are actual throughput metrics, which was recently questioned. We also propose some new throughput metrics, which cannot always be expressed as a closed formula. We use real experimental data to characterize metrics and show how they relate to each other.

With ever-increasing demands for bandwidth optical packet/burst switching is used to utilise more of the available capacity of optical networks. In current prototypes of optical switches time and wavelength multiplexing are combined to resolve packet contentions by means of Fiber Delay Lines and wavelength converters in the switching elements. Although optical switches have lower energy consumption than their electronic counterparts, it remains substantial. Since wavelength converters contribute significantly to the switches overall energy consumption, they should be used sparingly, rather than continuously. Current scheduling algorithms however do not take the usage of wavelength converters (and the related energy consumption) into account. To this end, we developed and evaluated new cost-based scheduling algorithms, which take both gap and delay into account to schedule an incoming packet. The performance improvement of these algorithms over existing algorithms can be traded off for a significant reduction in up-time of the wavelength converters by introducing a conversion cost in the involved cost function. This is backed by Monte Carlo simulation results, in which the algorithms are applied both in a void-filling and non-void-filling setting. The algorithms are of the same implementation complexity as current algorithms, and thus of immediate value to switch designers.

Both optical packet switching and optical burst switching provide viable alternatives to the current electronic switching in the backbone. To resolve contention, contiguous packets/bursts are sent over different channels, and/or provided with different Fiber Delay Line (FDL) buffer delays. Typically, the resulting channel and delay selection (CDS) algorithm bases its decision on the horizon value of the different channels. Up to now, a horizon algorithm known as MING (MINimal Gap) was assumed to provide minimal loss. Relying on Markov chain-based performance modeling and a Markov decision process (MDP), we reexamine the optimality of MING. This enables us to construct CDS algorithms that outperform MING, and this for any buffer size, traffic load and packet/burst size distribution. Further, we consider burst-size-dependent and load-dependent scheduling, two stochastic mechanisms that, together with preventive dropping, enhance the algorithm's performance. The paper presents the developed method in detail, together with detailed results of the performance gain realized.

DSL aggregation networks are evolving to the standard platform for the delivery of multimedia services such as television and network based personal video recording. These multimedia services introduce large challenges for network operators as they are sensitive to packet loss. Therefore, admission control mechanisms are required to avoid congestion caused by allowing too many sessions. However, as multimedia services are often bursty it is not possible to reserve a fixed amount of bandwidth in the network since this policy will lead to either over-admittance or under-admittance. Recently, the IETF Pre-Congestion Notification (PCN) Working Group, proposed a measurement based admission control mechanism, where the network load is measured at each node and sessions are allowed or blocked at the edge of the network. In this paper, we extend and evaluate the PCN mechanism: we propose a new measurement algorithm for PCN, based on bandwidth metering, and determine the configuration guidelines for the parameters of both the original token bucket based approach and the novel algorithm for different network conditions and traffic types. More specifically, we study PCN's applicability on protecting VBR video services, which is currently not studied in the PCN Working Group. Furthermore, we characterise the gain of PCN in comparison to a centralised admission control mechanism.

In optical burst switching and optical packet switching, contention of bursts (or packets) can be dealt with most effectively through a combination of wavelength conversion and optical buffering. While this is generally accepted in the optical networking community, and validated through simulation, analytic performance results for optical buffers were limited to the single-wavelength case, and the performance gain from wavelength conversion was never traced analytically for general assumptions. Quantifying this gain analytically is the scope of the current contribution. Relying on generating functions, we developed a fiber delay line (FDL) buffer model with wavelength conversion, which assumes the buffer located at the output of an optical switch, having access to multiple wavelengths. This document presents our model, validates its accuracy, and compares its output for different burst sizes (fixed or varying), scheduling policies and buffer sizes. Several numerical examples assess the applicability of our approximation, and show that our approach yields accurate results.

We present a performance model for fiber delay line (FDL) buffers having access to multiple wavelengths on an output fiber. In optical burst switching and optical packet switching, contending bursts (or packets) need to be dealt with in an effective way, and both wavelength conversion and optical buffering are viable solutions. The buffer studied here includes both solutions, with full wavelength conversion. It is situated at the output, and handles independent arrivals. We apply an analytic discrete-time queueing model to evaluate performance in terms of loss. We mainly consider the impact of burst size (fixed or varying), scheduling policy, and buffer size. Several numerical examples assess the accuracy of our approximation, and show that our approach is applicable when burst sizes are fixed, and, when a round-robin scheduling policy is adopted, also when burst sizes vary.