Workload characterization is an important concept in performance tuning and efficiency improvement of high performance computing systems. Not only does it allow a system to dynamically adjust resources, it also helps improve energy efficiency resulting in lower cost for computation. Nevertheless, lack of quantitative methods to describe workload characteristics prevents the system to work at its full potential. In this work, we proposed two discrete-time Markov chains, which can describe workload characteristics of a set of computational kernels, called Berkeley's "dwarfs". These discrete-time models were derived from the relationship between stalling in processor pipeline and resource usage behaviors of the workload. The models can quantitatively describe behaviors of each dwarf. Moreover, the model enables the concept of combining each dwarf to extend performance analysis over any arbitrary processes.

This paper presents the use of adaptive bandwidth control (ABC) for a quantitative packet loss rate guarantee to aggregate traffic in packet switched networks. ABC starts with some initial amount of bandwidth allocated to a queue and adjusts it over time based on online measurements of system states to ensure that the allocated bandwidth is just enough to attain the specified loss requirement. Consequently, no a priori detailed traffic information is required, making ABC more suitable for efficient aggregate quality of service (QoS) provisioning. We propose an ABC algorithm called augmented Fuzzy (A-Fuzzy) control, whereby fuzzy logic control is used to keep an average queue length at an appropriate target value, and the measured packet loss rate is used to augment the standard control to achieve better performance. An extensive simulation study based on both theoretical traffic models and real traffic traces under a wide range of system configurations demonstrates that the A-Fuzzy control itself is highly robust, yields high bandwidth utilization, and is indeed a viable alternative and improvement to static bandwidth allocation (SBA) and existing adaptive bandwidth allocation schemes. Additionally, we develop a simple and efficient measurement-based admission control procedure which limits the amount of input traffic in order to maintain the performance of the A-Fuzzy control at an acceptable level.

The design of survivable mesh based communication networks has received considerable attention in recent years. One task is to route backup paths and allocate spare capacity in the network to guarantee seamless communications services survivable to a set of failure scenarios. This is a complex multi-constraint optimization problem, called the spare capacity allocation (SCA) problem. This paper unravels the SCA problem structure using a matrix-based model, and develops a fast and efficient approximation algorithm, termed successive survivable routing (SSR). First, per-flow spare capacity sharing is captured by a spare provision matrix (SPM) method. The SPM matrix has a dimension the number of failure scenarios by the number of links. It is used by each demand to route the backup path and share spare capacity with other backup paths. Next, based on a special link metric calculated from SPM, SSR iteratively routes/updates backup paths in order to minimize the cost of total spare capacity. A backup path can be further updated as long as it is not carrying any traffic. Furthermore, the SPM method and SSR algorithm are generalized from protecting all single link failures to any arbitrary link failures such as those generated by Shared Risk Link Groups or all single node failures. Numerical results comparing several SCA algorithms show that SSR has the best trade-off between solution optimality and computation speed.

Class-based traffic treatment frameworks such as differentiated service (DiffServ) have been proposed to resolve the poor scalability problem in the flow-based approach. Although the performance is differentiated in a class-based basis, the performance seen by individual flows in the same class may differ from that seen by the class and has not been well understood. We investigate this issue by simulation in a single node under FIFO, static priority, waiting time priority, and weighted fair queueing scheduling schemes. Our results indicate that such performance discrepancy occurs especially when flows joining the same class are heterogeneous, which is not uncommon considering that the same type of applications can generate traffic having very different statistical behaviors such as video traffic with different activity levels, or voice traffic with different compression schemes. We found that per-flow delay statistics, including the average and the 99/sup th/ percentile delay, can be very different from the corresponding class delay statistics, depending on flow burstiness, overall traffic load, as well as the queue discipline. We also propose a solution to reduce the mean delay variance experienced by flows in the same class.

The paper proposes an adaptive bandwidth control algorithm that efficiently provides an aggregate loss guarantee to resolve the problem of inefficient bandwidth allocation due to incomplete, inaccurate traffic descriptors supplied by users. Because the control attempts to allocate only just enough bandwidth to meet the QoS requirement, the amount of bandwidth saving compared to static allocation can be substantial. Another distinct advantage of our control algorithm is that no a priori information on the traffic characteristics of the aggregate is required. From the simulation study, the proposed control can maintain the packet loss QoS while attaining very high utilization, and is robust against different system configurations and controller parameters.

Spare capacity allocation (SCA) is an important part of a fault tolerant network design. In the spare capacity allocation problem one seeks to determine where to place spare capacity in the network and how much spare capacity must be allocated to guarantee seamless communications services survivable to a set of failure scenarios (e.g., any single link failure). Formulated as a multi-commodity flow integer programming problem, SCA is known to be NP-hard. We provide a two-pronged attack to approximate the optimal SCA solution: unravel the SCA structure and find an effective algorithm. First, a literature review on the SCA problem and its algorithms is provided. Second, a integer programming model for SCA is provided. Third, a simulated annealing algorithm using the above INP model is introduced. Next, the structure of SCA is modeled by a matrix method. The per-flow based backup path information are aggregated into a square matrix, called the spare provision matrix (SPM). The size of the SPM is the number of links. Using the SPM as the state information, a new adaptive algorithm is then developed to approximate the optimal SCA solution termed successive survivable routing (SSR). SSR routes link-disjoint backup paths for each traffic flow one at a time. Each flow keeps updating its backup path according to the current network state as long as the backup path is not carrying any traffic. In this way, SSR can be implemented by shortest path algorithms using advertised state information with complexity of O( Link/sup 2/). The analysis also shows that SSR is using a necessary condition of the optimal solution. The numerical results show that SSR has near optimal spare capacity allocation with substantial advantages in computation speed.

Packet scheduling disciplines play an important role in providing quality of service (QoS) guarantees to applications traffic in high speed networks. Several scheduling disciplines have emerged in the literature that are capable of providing guarantees on various QoS parameters, such as packet delay, jitter, loss and throughput, while maintaining fairness among various connections. However, there is a trade-off between the performance and the simplicity of operation and implementation performance of the scheduling schemes. Thus the first-come-first-serve (FCFS) scheduling discipline has remained popular due to its overriding simplicity in spite of its poor capabilities in providing QoS guarantees. In previous work it has been shown that a practical worst case bound can be obtained for a deterministic delay guarantee in networks using the FCFS discipline, by imposing a source rate condition on each connection, that restricts the overall network utilization. In this paper, a modified source rate condition is proposed that can significantly increase the bandwidth utilization, while still maintaining the deterministic delay guarantee.