Eigenvalues of a graph are of high interest in graph analytics for Big Data due to their relevance to many important properties of the graph including network resilience, community detection and the speed of viral propagation. Accurate computation of eigenvalues of extremely large graphs is usually not feasible due to the prohibitive computational and storage costs and also because full access to many social network graphs is often restricted to most researchers. In this paper, we present a series of new sampling algorithms which solve both of the above-mentioned problems and estimate the two largest eigenvalues of a large graph efficiently and with high accuracy. Unlike previous methods which try to extract a subgraph with the most influential nodes, our algorithms sample only a small portion of the large graph via a simple random walk, and arrive at estimates of the two largest eigenvalues by estimating the number of closed walks of a certain length. Our experimental results using real graphs show that our algorithms are substantially faster while also achieving significantly better accuracy on most graphs than the current state-of-the-art algorithms.

Performance monitoring of datacenters provides vital information for dynamic resource provisioning, anomaly detection, and capacity planning decisions. Online monitoring, however, incurs a variety of costs: the very act of monitoring a system interferes with its performance, consuming network bandwidth and disk space. With the goal of reducing these costs, this paper develops and validates a strategy based on adaptive-rate compressive sampling. It exploits the fact that the signals of interest often can be sparsified under an appropriate representation basis and that the sampling rate can be tuned as a function of sparsity. We use the Trade6 application as our experimental platform and measure the signals of interest-in our case, signals pertaining to memory and disk I/O activity-using adaptive sampling. We then evaluate whether the reconstructed signals can be used for trend detection to track the gradual deterioration of system performance associated with software aging. Our experiments show that the signals recovered by our methods can be used to detect, with high confidence, the existence of trends within the original signal. We also evaluate the reconstructed signals for threshold-violation detection wherein the magnitude of the signal exceeds a preset value. Our experiments show that performance bottlenecks and anomalies that manifest themselves in portions of the signal where its magnitude exceeds a threshold value can also be detected using the reconstructed signals. Most importantly, detection of these anomalies is achieved using a substantially reduced sample size-a reduction of more than 70 percent when compared to the standard fixed-rate sampling method.

Monitoring key properties of dynamic graphs in real time can help detect spam accounts in social networks, identify anomalies and intrusions, and inform resource management. Traditional frameworks for dynamic graphs have relied on processing only the stream of edges added into or deleted from an evolving graph, but not any additional related information such as the degrees or neighbor lists of nodes associated with the edges. In this paper, we propose a new edge sampling framework for big-graph analytics in dynamic graphs which enhances the traditional model and offers significantly improved trade-off between accuracy and computational/memory costs in the running estimates of a graph's properties. To demonstrate this higher accuracy using the framework, we present a new sampling algorithm, called Edge Sample and Discard, which generates an unbiased estimate of the total number of triangles in a fully dynamic graph. The experimental results show that, with the help of the neighborhood information of the sampled edges, the accuracy achieved by our algorithm is substantially better than the accuracy achieved by current state-of-the-art algorithms.

The spectral radius of a graph, i.e., the largest eigenvalue of its adjacency matrix, is of high interest in graph analytics for Big Data due to its relevance to many important properties of the graph including network resilience, community detection and the speed of viral propagation. Accurate computation of the largest eigenvalue of extremely large graphs is infeasible due to the prohibitive computational and storage costs, and also because full access to many social network graphs is often restricted to most researchers. In this paper, we present a new and efficient algorithm called Closed Walk Sampler (cWalker) which solves both of the above-mentioned problems. Unlike previous methods which try to extract a subgraph with the most influential nodes, the cWalker samples only a small portion of the large graph via a simple random walk, and arrives at an estimate of the largest eigenvalue by estimating the number of closed walks of a certain length. Our experimental results using real graphs show that the cWalker is substantially faster while also achieving significantly better accuracy on most graphs than the current state-of-the-art algorithms.

Algorithms for mining very large graphs, such as those representing online social networks, to discover the relative frequency of small subgraphs within them are of high interest to sociologists, computer scientists and marketeers alike. However, the computation of these network motif statistics via naive enumeration is infeasible for either its prohibitive computational costs or access restrictions on the full graph data. Methods to estimate the motif statistics based on random walks by sampling only a small fraction of the subgraphs in the large graph address both of these challenges. In this paper, we present a new algorithm, called the Waddling Random Walk (WRW), which estimates the concentration of motifs of any size. It derives its name from the fact that it sways a little to the left and to the right, thus also sampling nodes not directly on the path of the random walk. The WRW algorithm achieves its computational efficiency by not trying to enumerate subgraphs around the random walk but instead using a randomized protocol to sample subgraphs in the neighborhood of the nodes visited by the walk. In addition, WRW achieves significantly higher accuracy (measured by the closeness of its estimate to the correct value) and higher precision (measured by the low variance in its estimations) than the current state-of-the-art algorithms for mining subgraph statistics. We illustrate these advantages in speed, accuracy and precision using simulations on well-known and widely used graph datasets representing real networks.

The monitoring and management of high-volume feature-rich traffic in large networks offers significant challenges in storage, transmission, and computational costs. The predominant approach to reducing these costs is based on performing a linear mapping of the data to a low-dimensional subspace such that a certain large percentage of the variance in the data is preserved in the low-dimensional representation. This variance-based subspace approach to dimensionality reduction forces a fixed choice of the number of dimensions, is not responsive to real-time shifts in observed traffic patterns, and is vulnerable to normal traffic spoofing. Based on theoretical insights proved in this paper, we propose a new distance-based approach to dimensionality reduction motivated by the fact that the real-time structural differences between the covariance matrices of the observed and the normal traffic is more relevant to anomaly detection than the structure of the training data alone. Our approach, called the distance-based subspace method, allows a different number of reduced dimensions in different time windows and arrives at only the number of dimensions necessary for effective anomaly detection. We present centralized and distributed versions of our algorithm and, using simulation on real traffic traces, demonstrate the qualitative and quantitative advantages of the distance-based subspace approach.

Anomalies in communication network traffic caused by malware or denial-of-service attacks manifest themselves in structural changes in the covariance matrix of traffic features. Real-time detection of anomalies in high-dimensional data demands a very efficient algorithm to identify these changes in a compact low-dimensional representation. This paper presents an efficient algorithm for the rapid detection of structural differences between two covariance matrices, as measured by the maximum possible angle between the subspaces specified by subsets of the two sets of principal components of the matrices. We show that our algorithm achieves a significantly lower computational complexity compared to a naive approach. Finally, we apply our results to real traffic traces from Internet backbone links and show that our approach offers a substantial reduction in the computational overhead of anomaly detection.

Online performance monitoring of computer systems incurs a variety of costs: the very act of monitoring a system interferes with its performance and if the information is transmitted to a monitoring station for analysis and logging, this consumes network bandwidth and disk space. Compressive sampling-based schemes can help reduce these costs on the local machine by acquiring data directly from the system in a compressed form, and in a computationally efficient way. This paper focuses on reducing the computational cost associated with recovering the original signal from the transmitted sample set at the monitoring station for anomaly detection. Towards this end, we show that the compressed samples preserve, in an approximate form, properties such as mean, variance, as well as correlation between data points in the original full-length signal. We then use this result to detect changes in the original signal that could be indicative of an underlying anomaly such as abrupt changes in magnitude and gradual trends without the need to recover the full-length data. We illustrate the usefulness of our approach via case studies involving IBM's Trade Performance Benchmark using signals from the disk and memory subsystems. Experiments indicate that abrupt changes can be detected using a compressed sample size of 25% with a hit rate of 95% for a fixed false alarm rate of 5%; trends can be detected within a confidence interval of 95% using a sample size of only 6%.

Network traffic anomaly detection is now considered a surer approach to early detection of malware than signature-based approaches and is best accomplished with traffic data collected from multiple locations. Existing open-source tools are primarily signature-based, or do not facilitate integration of traffic data from multiple locations for real-time analysis, or are insufficiently modular for incorporation of newly proposed approaches to anomaly detection. In this paper, we describe DataMap, a new modular open-source tool for the collection and real-time analysis of sampled, anonymized, and filtered traffic data from multiple WiFi locations in a network and an example of its use in anomaly detection.

In wireless sensor networks, a few sensor nodes end up being vulnerable to potentially rapid depletion of the battery reserves due to either their central location or just the traffic patterns generated by the application. In this paper, we use a new approach that balances the energy consumption at each of the nodes, thus increasing the functional lifetime of the network. We propose a new distributed dynamic topology control algorithm called Energy Balanced Topology Control (EBTC) which considers the actual energy consumed for each transmission and reception to achieve the goal of an increased functional lifetime. We analyze the algorithm's computational and communication complexity and show that it is equivalent or lower in complexity to other dynamic topology control algorithms. Using an empirical model of energy consumption, we show that the EBTC algorithm increases the lifetime of a wireless sensor network by over 40% compared to the best of previously known algorithms.

Topology control algorithms allow each node in a wireless multi-hop network to adjust the power at which it makes its transmissions and choose the set of neighbors with which it communicates directly, while preserving global goals such as connectivity or coverage. This allows each node to conserve energy and contribute to increasing the lifetime of the network. Previous work on topology control has largely used an approach based on considering only the energy costs across links without considering the amount of energy available on a node. Further, previous work has largely used a static approach where the topology is determined at the beginning of the network's life and does not incorporate the varying rates of energy consumption at different nodes. In this paper, we address these weaknesses and introduce a new topology control algorithm that dynamically adapts to current energy levels at nodes. The algorithm, called Cooperative Topology Control with Adaptation (CTCA), employs a game-theoretic approach that maps the problem of maximizing the network's lifetime into an ordinal potential game. This allows a node running the CTCA algorithm to make a sacrifice by increasing its transmission power if it can help reduce energy consumption at another node with a smaller lifetime. We prove the existence of a Nash equilibrium for the game. Our simulation results indicate that the CTCA algorithm extends the life of a network by more than 50% compared to the best previouslyknown algorithm.

Performance monitoring of data centers provides vital information for dynamic resource provisioning, fault diagnosis, and capacity planning decisions. However, the very act of monitoring a system interferes with its performance, and if the information is transmitted to a monitoring station for analysis and logging, this consumes network bandwidth and disk space. This paper proposes a low-cost monitoring solution using compressive sampling - a technique that allows certain classes of signals to be recovered from the original measurements using far fewer samples than traditional approaches - and evaluates its ability to measure typical signals generated in a data-center setting using a testbed comprising the Trade6 enterprise application. The results open up the possibility of using low-cost compressive sampling techniques to detect performance bottlenecks and anomalies that manifest themselves as abrupt changes exceeding operator-defined threshold values in the underlying signals.

Each node in a wireless multi-hop network can adjust the power at which it makes its transmissions and thus change the topology of the network to save energy by choosing a smaller number of neighbors with which it communicates directly. The Directed Relative Neighborhood Graph (DRNG) algorithm is among the most popular, efficient and versatile topology control algorithms that reduces energy costs while preserving connectivity. In this paper, however, we identify two key limitations of DRNG and address them in a new power-aware distributed topology control algorithm called Inclusive DRNG. We show that the Inclusive DRNG algorithm can cut down the energy cost of executing the topology control algorithm itself to as low as one-third that of executing DRNG. We further show that Inclusive DRNG also generates a topology that achieves a significant improvement of over 25% in the average energy cost of communication across a path between any two nodes in realistic irregular radio environments.

In "area-sensing" applications of sensor networks, such as surveillance or target tracking, each sensor node has a sensing radius within which it can monitor events. Coverage problems in sensor networks have largely focused on such applications, where the goal of good coverage is one of ensuring that each point in the region of interest is within the sensing radius of at least one node. On the other hand, in "spot-sensing" applications, each node makes a measurement (such as temperature or humidity) at the precise location of the node and there is no concept of a sensing radius. In this paper, we introduce a new coverage problem that is more meaningful to spot-sensing applications. In such cases, good coverage usually implies even coverage across points in the region. We borrow from the field of economics and adapt a well-accepted measure of inequality, the Gini index, to develop a metric for the evenness of coverage by a sensor network. Based on mathematical results on the expected distances between neighboring nodes, we present a new distributed algorithm, called EvenCover, for each node to determine if and when it should sleep or sense. We prove that the expected Gini index is 1 - 1radic2 ap 0.293 when the spatial distribution of sensing nodes is given by a Poisson random process. On the other hand, when the sensing nodes are perfectly evenly distributed, we show that the Gini index has a lower bound of 0.2. These two results serve as points of reference to evaluate the coverage achieved by the EvenCover algorithm. We present a thorough simulation-based comparison of EvenCover against other distributed algorithms showing that it achieves better evenness and significantly increased lifetime. In addition, we discover that evenness of coverage permits a graceful degradation of the network as nodes exhaust their energy resources.

Fairness in traffic management can improve the isolation between traffic streams, offer a more predictable performance, eliminate transient bottlenecks, mitigate the effect of certain kinds of denial-of-service attacks, and serve as a critical component of a quality-of-service strategy to achieve certain guaranteed services such as delay bounds and minimum bandwidths. In this paper, we choose a popular notion of fairness called max-min fairness and provide a rigorous definition in the context of input-queued switches. We show that being fair at the output ports alone or at the input ports alone or even at both input and output ports does not actually achieve an overall max-min fair allocation of bandwidth in a switch. Instead, we propose a new algorithm that can be readily implemented in a distributed fashion at the input and output ports to determine the exact max-min fair rate allocations for the flows through the switch. In addition to proving the correctness of the algorithm, we propose a practical scheduling strategy based on our algorithm. We present simulation results, using both real traffic traces and synthetic traffic, to evaluate the fairness of a variety of popular scheduling algorithms for input-queued switches. The results show that our scheduling strategy achieves better fairness than other known algorithms for input-queued switches and, in addition, achieves throughput performance very close to that of the best schedulers.

Each node in a wireless multihop network can adjust the power at which it makes its transmissions and thus change the topology of the network by choosing the neighbors with which it directly communicates. Many previous algorithms for distributed topology control have assumed an ability at each node to deduce some spatial information such as the direction and the distance of its neighbor nodes with respect to itself. However, such a deduction of spatial information cannot be relied upon in a multipath environment where different paths of a signal may have different loss characteristics and none of the paths may be line-of-sight. In this paper, we present Step Topology Control (STC), a simple distributed topology control algorithm which reduces power consumption while preserving the connectivity of a heterogeneous sensor network in a multipath environment. The STC algorithm avoids the use of GPS devices and also makes no assumptions about the distance and direction between neighboring nodes. We provide analytical proofs of the relationship between the STC algorithm and a cone-based topology control algorithm. We present a detailed simulation- based comparative analysis of the energy savings achieved by the STC algorithm and previously known algorithms that also seek to reduce power consumption while preserving connectivity. The results show that the STC algorithm performs significantly better than other algorithms, especially in the presence of radio irregularities and multipath propagation. In addition, the STC algorithm scales better than other algorithms in performance and in fact, is more effective with increasing numbers of nodes.

This paper presents a randomized algorithm, called degree-sequenced matching (DSM), for scheduling packets in an input-queued switch. Previously known high-throughput, randomized algorithms implicitly prioritize the matching of ports with larger degrees and causes longer delays at the low-degree ports. Our algorithm, however, achieves a lower average delay but without compromising the throughput. The DSM algorithm sorts nodes based on their node-degrees and begin each iteration of the algorithm by matching the lowest degree nodes. Using real gateway traffic traces as well as synthetically generated traffic, we present simulation results showing that DSM achieves a low average delay, while still achieving near maximum throughput.

This paper illustrates how networking protocols can inadvertently exacerbate obstacles to providing real-time guarantees for distributed problem solving in wireless mobile and sensor networks. We analyze the effects of control packet timing on providing quality of service guarantees. Inappropriate timing of control packets gives rise to synchronizations that result in sharp increases and decreases in throughput with small changes in node speed. Such synchronizations can seriously jeopardize network performance with direct effect on real-time guarantees. This paper introduces these synchronizations, analyzes them and suggests ways to modify the control packet timing to overcome them. These analyses include investigating the role of buffering at the network layer and its impact on network throughput. We analyze these effects and evaluate our protocol enhancements through simulation studies.

The problem of achieving fairness in the allocation of the bandwidth resource on a link shared by multiple flows of traffic has been extensively researched over the last decade. However, with the increasing pervasiveness of optical networking and the occasional trend toward using over-provisioning as the solution to bandwidth congestion, a router's processor also becomes a critical resource to which, ideally speaking, all competing flows should have fair access. For example, achieving fairness in the allocation of processing resources can be part of an overall strategy of countering certain kinds of denial of service attacks (such as those based on an excessive use of the router processor by using unnecessary optional headers). In this paper, we investigate the issue of achieving fairness in the joint allocation of the processing and bandwidth resources. We first present a simple but powerful general principle for defining fairness in such systems based on any of the classic notions of fairness such as max-min fairness, proportional fairness, and utility max-min fairness defined for a single resource. We apply our principle to a system with a shared processor and a shared link with max-min fairness as the desired goal. We then propose a practical and provably fair packet-by-packet algorithm for the joint allocation of processing and bandwidth resources. We demonstrate the fairness achieved by our algorithm through simulation results using both synthetic and real gateway traffic traces. The principles and the algorithm detailed in this paper may also be applied in the allocation of other kinds of resources such as power, which is a critical resource in mobile systems.

It is widely believed that diversity in operating systems, software packages, and hardware platforms will decrease the virulence of worms and the effectiveness of repeated applications of single attacks. Research efforts in the field have focused on introducing diversity using a variety of techniques on a system-by-system basis. This paper, on the other hand, assumes the availability of diverse software packages for each system and then seeks to increase the intrinsic value of available diversity by considering the entire computer network. We present several distributed algorithms for the assignment of distinct software packages to individual systems and analyze their performance. Our goal is to limit the ability of a malicious node to use a single attack to compromise its neighboring nodes, and by extension, the rest of the nodes in the network. The algorithms themselves are analyzed for attack tolerance, and strategies for improving the security of the individual software assignment schemes are presented. We present a comparative analysis of our algorithms using simulation results on a topology obtained from e-mail traffic logs between users at our institution. We find that hybrid versions of our algorithms incorporating multiple assignment strategies achieve better attack tolerance than any given assignment strategy. Our work thus shows that diversity must be introduced at all levels of system design, including any scheme that is used to introduce diversity itself.

The EAFRP model has been recently proposed for modeling the self-similar and impulsive traffic of high-speed networks. For mathematical simplicity, it assumes that the available transmission bandwidth in the network is infinite. We here propose a modification of the model that takes into account the fact that the network has a limit, R, on the total traffic rate through it, and in addition, each user's traffic rate is often independently limited to a value, L, which is significantly lower than the network's limit (L

A number of emerging Internet applications, such as video-conferencing and live multimedia broadcasts, must rely on scheduling algorithms in switches and routers to guarantee performance and an acceptable level of quality of service. Fairness in packet schedulers is an intuitively desirable property with practical value; fair schedulers are a critical component of QoS mechanisms that seek to guarantee end-to-end delay bounds. Popular measures of the fairness achieved by packet schedulers are based on bounds, such as the relative fairness bound which captures the maximum possible difference between the normalized service received by any two flows. We argue that such measures do not capture the actual fairness achieved at most instants of time, and therefore, do not represent a true measure of the ability of a scheduler to successfully deliver end-to-end quality for real-time applications. We borrow from the field of economics and propose a new measure of fairness based on the Gini index. This measure captures the instantaneous fairness of a scheduler and, unlike other measures based on bounds, also captures the fairness of the scheduler in its handling of flows during idle periods. Using real traces of gateway and video traffic, we present a simulation-based evaluation of several well-known schedulers based on the Gini index. We also present a qualitative analysis of the phenomena underlying the observed results.

As flows of traffic traverse a network, they share with other flows a variety of resources such as links, buffers and router CPUs in their path. Fairness is an intuitively desirable property in the allocation of resources in a network shared among flows of traffic from different users. While fairness in bandwidth allocation over a shared link has been extensively studied, overall end-to-end fairness in the use of all the resources in the network is ultimately the desired goal. End-to-end fairness becomes especially critical when fair allocation algorithms are used as a component of the mechanisms used to provide end-to-end quality-of-service guarantees. This paper seeks to answer the question of what is fair when a set of traffic flows share multiple resources in the network with a shared order of preference for the opportunity to use these resources. We present the Generalized Principle of Fairness (GPF), a powerful extension of any of the classic notions of fairness such as max-min fairness, proportional fairness and utility max-min fairness defined over a single resource. We illustrate this principle by applying it to a system model with a buffer and an output link shared among competing flows of traffic. To complete our illustration of the applicability of GPF we propose a measure of fairness and evaluate representative buffer allocation algorithms based on this measure. Besides buffer allocation, GPF may also be used in other contexts in data communication networks and operating system design.

Fair scheduling algorithms are an important component of most QoS mechanisms designed to support the performance guarantees required by real-time applications. In this paper, we present greedy fair queueing (GrFQ), a novel scheduler based on a greedy strategy of reducing the maximum difference in normalized service received by any two flows at each transmission boundary. We prove that the GrFQ scheduler achieves a better bound on the normalized lag than other known schedulers. We further propose a simplified version of the scheduler, called GrFQ-lite, which avoids the emulation of a fluid flow system and has a per-packet work complexity of O(1) in the computation of the timestamps. Borrowing from the field of economics, we use the Gini index as a measure of instantaneous fairness. Using real gateway traffic traces, we show that the GrFQ scheduler achieves better fairness than any other known scheduler at virtually all instants of time. We further show that the GrFQ-lite scheduler achieves equivalent or better fairness than other known schedulers including those that are significantly more computationally intensive in their emulation of the ideally fair fluid flow system.

Pricing is an effective tool to control congestion and achieve QoS provisioning for multiple differentiated levels of service. In this paper, we propose a practical, flexible and computationally simple pricing strategy that can achieve QoS provisioning in differentiated services networks with multiple priority classes at close to peak efficiency, while also maintaining stable transmission rates from end-users. In contrast to previous work in which dynamic pricing strategies are based on the state of congestion alone, our strategy adds a separate price component for the preferential service received by a packet. In addition, it utilizes a user-centric approach where a user is not charged a higher price unless preferential service is actually delivered.

This paper evaluates the gain in throughput achieved by the use of a shared buffer to realize the output queues of switching elements in the presence of self-similar multimedia traffic. Unlike previous studies, we focus on credit-based systems typical of networks used in parallel multimedia servers. It is generally believed that buffer sharing improves performance in the presence of non-uniform traffic. With self-similar traffic exhibiting burstiness over all time-scales, however, we show that buffer sharing is a superior design choice only when the total buffer capacity is more than a certain minimum threshold. We explain the non-trivial reasons for the existence of this threshold through an analysis based on head-of-line blocking probabilities. The results presented here have implications in switch design, especially in systems where the total buffering capacity may be limited.

The emerging high-speed broadband packet-switched networks are expected to simultaneously support a variety of services with different quality-of-service (QoS) requirements over the same physical infrastructure. Fair packet scheduling algorithms used in switches and routers play a critical role in providing these QoS guarantees. Deficit round robin (DRR), a popular fair scheduling discipline, is very efficient with an O(l) dequeuing complexity. Using the concept of latency-rate (/spl Lscr//spl Rscr/) servers introduced by Stiliadis and Varma (1996), we obtain an upper bound on the latency of DRR and prove that our bound is tight. Our upper bound is lower than the previously known upper bound. This illustrates that the DRR scheduler has better performance characteristics than previously believed, especially for real-time applications where the latency plays a role in the size of the playback buffer required.

In the emerging high-speed packet-switched networks, packet scheduling algorithms used in the switches and routers will play a critical role in satisfying the quality of service (QoS) requirements of various applications. The latency bound of a scheduling discipline is an important QoS parameter, especially for real-time playback applications. Frame-based schedulers such as deficit round robin (DRR), though extremely efficient with an O(1) dequeuing complexity, lead to high latencies due to bursty transmissions of each flow's traffic. In a previous work by, Tsao and Lin (see Computer Networks, vol.35, no.2-3, p.287-305, 2001), the authors propose pre-order deficit round robin, a novel scheme that overcomes this limitation of DRR while still achieving a low work complexity. In pre-order DRR, a priority queue module is appended to the original DRR scheduler which re-orders the packet transmission sequence in DRR to distribute the output more evenly among flows and thus reduce burstiness and improve the latency. We employ a novel approach to analytically derive the latency bound of pre-order DRR and show that our bound is a tight one. Our latency bound is significantly lower than the bound derived by Tsao and Lin, demonstrating that pre-order DRR has even better performance characteristics than previously argued by its own authors.

Parallel systems are increasingly being used in multiuser environments with the interconnection network shared by several users at the same time. Fairness is an intuitively desirable property in the allocation of bandwidth available on a link among traffic flows of different users that share the link. Strict fairness in traffic scheduling can improve the isolation between users, offer a more predictable performance and improve performance by eliminating some bottlenecks. This paper presents a simple, fair, efficient, and easily implementable scheduling discipline, called Elastic Round Robin (ERR), designed to satisfy the unique needs of wormhole switching, which is popular in interconnection networks of parallel systems. In spite of the constraints of wormhole switching imposed on the design, ERR is also suitable for use in Internet routers and has better fairness and performance characteristics than previously known scheduling algorithms of comparable efficiency, including Deficit Round Robin and Surplus Round Robin. In this paper, we prove that ERR is efficient, with a per-packet work complexity of O(1). We analytically derive the relative fairness bound of ERR, a popular metric used to measure fairness. We also derive the bound on the start-up latency experienced by a new flow that arrives at an ERR scheduler. Finally, this paper presents simulation results comparing the fairness and performance characteristics of ERR with other scheduling disciplines of comparable efficiency.

Most switch architectures for parallel systems are designed to eliminate only the worst kinds of unfairness such as starvation scenarios in which packets belonging to one traffic flow may not make forward progress for an indefinite period of time. However stricter fairness can lead to a more predictable and better performance, in addition to improving isolation between traffic belonging to different users. This paper presents a new easily implementable scheduling discipline, called Elastic Round Robin (ERR), for the unique requirements of wormhole switching, popular in interconnection networks for parallel systems. Despite the constraints of wormhole switching imposed on the design, our scheduling discipline is at least as efficient as other scheduling disciplines, and more fair than scheduling disciplines of comparable efficiency proposed for any other kind of network, including the Internet. We prove that the work complexity of ERR is O(1) with respect to the number of flows. We analytically prove the fairness properties of ERR, and show that its relative fairness measure has an upper bound of 3 m, where m is the size of the largest packet that actually arrives during an execution of ERR. Finally, we present simulation results comparing the fairness and performance characteristics of ERR with other scheduling disciplines of comparable efficiency.

While the interconnection network topology is one of the most important determinants of the performance of a parallel system, no single topology offers an ideal cost/performance trade-off for all classes of applications in parallel processing. The modular units used in the IBM RS/6000 SP topologies allow the construction of a large variety of topologies including 4-ary fat-tree networks. In our experience, however, cost and cost/performance ratio are often the primary concerns of customers. Therefore, while fat-tree topologies offer excellent performance, they are not always the most attractive choice for customers of large-scale parallel systems. This paper presents the lower-cost RS/6000 SP topologies for large systems designed with fewer switching elements than fat-tree networks, and describes some of the rationale behind the choices made.