Proportional fair schedulers with their ability to provide optimal schedulability along with hard timeliness and quality-of-service guarantees on multiprocessors form an attractive alternative in real-time embedded systems that concurrently run a mix of independent applications with varying timeliness constraints. This article presents ERfair Scheduler with Suspension on Multiprocessors (ESSM) , an efficient, optimal proportional fair scheduler that attempts to reduce system wide energy consumption by locally maximizing the processor suspension intervals while not sacrificing the ERfairness timing constraints of the system. The proposed technique takes advantage of higher execution rates of tasks in underloaded ERfair systems and uses a procrastination scheme to search for time points within the schedule where suspension intervals are locally maximal. Evaluation results reveal that ESSM achieves good sleep efficiency and provides up to 50% higher effective total sleep durations as compared to the Basic-ERfair scheduler on systems consisting of 2 to 20 processors.

In this paper, we develop an analytical framework which explains the emergence of superpeer networks on execution of the commercial peer-to-peer bootstrapping protocols by incoming nodes. Bootstrapping protocols exploit physical properties of the online peers like resource content, processing power, storage space, connectivity etc as well as take the finiteness of bandwidth of each online peer into consideration. With the help of rate equations, we show that execution of these protocols results in the emergence of superpeer nodes in the network - the exact degree distribution is evaluated. We validate the framework developed in this paper through extensive simulation. The analysis of the results shows that the amount of superpeers produced in the network depends on the protocol as well as the properties of the joining nodes. Interestingly, our analysis reveals that increase in the amount of resource and the number of resourceful nodes do not always help to increase the fraction of superpeer nodes in the network. The impact of the frequent leaving of the peers on the topology of the emerging network is also evaluated. As an application study, we show that our framework can explain the topological configuration of commercial Gnutella networks. The developed model can almost perfectly match the degree distribution of Gnutella network.

In this paper, we develop an analytical framework to explain the appearance of bimodal degree distribution in existing popular superpeer networks like Gnutella. The framework leads to several interesting and important inferences related to network topology and node/link dynamics. Beyond the simulation based study, we validate our framework through almost exact matching of the topological structure of Gnutella network constructed from real data.

Putting the processor into shutdown state when it is idling is one of the primary methodologies towards the reduction of energy consumption in today's systems where leakage power is emerging as a dominant concern. This paper presents ERfair Scheduler with Processor Shutdown (ESPS), a uniprocessor ERfair scheduler that attempts to minimize energy consumption in rate-based periodic real-time task systems by locally maximizing processor shut-down intervals while simultaneously maintaining proportional fairness among task executions. Evaluation results show that our proposed algorithm achieves good shut-down efficiency and provides upto 9 times higher effective shutdown lengths as compared to the Basic_ERfair scheduler.

In this paper, we develop an analytical framework to measure the vulnerability of superpeer networks against attack. Two different kinds of attacks namely deterministic and degree dependent attack have been introduced here. We formally model the superpeer networks with the help of bimodal structure and different attacks with the help of graph dynamics. Our analysis shows that fraction of superpeers and their connectivity have profound impact upon the stability of the network. The results obtained from the theoretical analysis are validated through simulation. The agreement between the simulation results and theoretical predictions is almost perfect.

Many previous works of Peer-to-Peer traffic characterization and modeling focused their attention on the distribution of query contents. However, few has been done towards a better understanding of the time series distribution of these queries, which is vital for system performance. To remedy this situation, this paper characterizes query traffic by using automatic time series analysis to evaluate different linear models(Box-Jenkins models and some simple windowed-mean models) for predicting the number of duplicated queries from 10 minutes to 2 hours into the future. Both the predictive power and the computational costs of these models are evaluated over 318,942,450 real world Gnutella queries collected over 3 months. We find the number of duplicated queries is consistently predictable. Simple, practical models like AR perform well on prediction. To show that these characteristics have a wide range of potential applications, we propose two enhancement to existing search results caching and load balancing algorithms. Our simulation study shows that our methodology works quite well in both scenarios in terms of efficiency and effectiveness. The main contribution of this paper lies in: (1) proposing new measurement techniques on Gnutella, (2) characterizing and modeling peer-to-peer query traffic with Box-Jenkins Models, (3) presenting a general enhancement to existing performance optimization algorithm in P2P systems.

No abstract available.

In this paper, we present a polynomial time algorithm that gives an optimal solution to the routing and wavelength assignment (RWA) problem in a tree topology. One of the major design issues in wavelength-division multiplexed networks is the assignment of the limited number of wavelengths among network stations so that greater capacity can be achieved. The problem of RWA is known to be NP-hard problem. Many researchers have tackled the problem of RWA with a number of efficient heuristic algorithms. This paper presents an algorithm that optimally assigns a single wavelength to maximize one-hop traffic in a tree topology. The algorithm uses dynamic programming and is shown to be optimal with a time complexity of O(N/sup 4/). We also propose a heuristic scheme to use our optimal algorithm for wavelength assignment in a general graph. The heuristic works on the tree subgraphs of a given graph and the remaining spare wavelengths can be assigned with an existing RWA policy.

Presents a framework for efficiently solving logic formulations of combinatorial optimization problems using heuristic search techniques. In order to integrate cost, lower-bound and upper-bound specifications with conventional logic programming languages, we augment a constraint logic programming (CLP) language with embedded constructs for specifying the cost function and with a few higher-order predicates for specifying the lower and upper bound functions. We illustrate how this simple extension vastly enhances the ease with which optimization problems involving combinations of Min and Max can be specified in the extended language CLP* and we show that CSLDNF (Constraint SLD resolution with Negation as Failure) resolution schemes are not efficient for solving optimization problems specified in this language. Therefore, we describe how any problem specified using CLP* can be converted into an implicit AND/OR graph, and present an algorithm called GenSolve which can branch-and-bound using upper and lower bound estimates, thus exploiting the full pruning power of heuristic search techniques. A technical analysis of GenSolve is provided. We also provide experimental results comparing various control strategies for solving CLP* programs.

We present here a technique for allocation and binding for data path synthesis (DPS) using a Genetic Algorithm (GA) approach. This GA uses an unconventional crossover mechanism relying on a force directed data path binding completion algorithm. The data path is synthesized using some supplied design parameters. A bus-based interconnection scheme, use of multi-port memories, and provision for multicycling and pipelining are the main features of this system. The method presented here has been applied to standard benchmark examples and the results obtained are promising.

In this paper, we examine the multicriteria optimization involved in scheduling for data-path synthesis (DPS). The criteria we examine are the area cost of the components and schedule time. Scheduling for DPS is a well-known NP-complete problem. We present a method to find nondominated schedules using a combination of restricted search and heuristic scheduling techniques. Our method supports design with architectural constraints such as the total number of functional units, buses, etc. The schedules produced have been taken to completion using GABIND as written by Mandal et al., and the results are promising.

We provide an overall framework for learning in search based systems that are used to find optimum solutions to problems. This framework assumes that prior knowledge is available in the form of one or more heuristic functions (or features) of the problem domain. An appropriate clustering strategy is used to partition the state space into a number of classes based on the available features. The number of classes formed will depend on the resource constraints of the system. In the training phase, example problems are run using a standard admissible search algorithm. In this phase, heuristic information corresponding to each class is learned. This new information can be used in the problem solving phase by appropriate search algorithms so that subsequent problem instances can be solved more efficiently. In this framework, we also show that heuristic information of forms other than the conventional single valued underestimate value can be used, since we maintain the heuristic of each class explicitly. We show some novel search algorithms that can work with some such forms. Experimental results have been provided for some domains.

We investigate the role of learning in search-based systems for solving optimization problems. We use a learning model, where the values of a set of features can be used to induce a clustering of the problem state space. The feasible set of h* values corresponding to each cluster is called h*set. If we relax the optimality guarantee, and tolerate a risk factor, the distribution of h*set can be used to expedite search and produce results within a given risk of suboptimality. The off-line learning method consists of solving a batch of problems by using A* to learn the distribution of the h*set in the learning phase. This distribution can be used to solve the rest of the problems effectively. We show how the knowledge acquisition phase can be integrated with the problem solving phase. We present a continuous online learning scheme that uses an "anytime" algorithm to learn continuously while solving problems.

A new neural network strategy for clustering is presented. The network works on the histogram and the process is similar to mode separation. The number of clusters are autonomously detected by the network and it overcomes some major difficulties encountered by mode separation techniques. Clustering is done by first selecting the prototypes and then assigning patterns to one of the prototypes based on its distance from the prototype and the distribution of data. The network does not employ weight learning and is therefore faster than existing unsupervised learning networks. The network was applied to a wide class of problems including gray level image reduction, color segmentation and remotely sensed image segmentation. The experimental results obtained are promising.>

A connectionist network is presented for segmenting gray level images. The network detects the local peaks in the inverted histogram which will correspond to the bottoms of the valleys in the actual histogram. The neural network implementation successfully uses circumstantial evidence and detects multiple winners over the entire range of gray values such that these winners correspond to multiple thresholds for segmenting the image. The dynamics of the network has been analyzed and the conditions for convergence have been established. Experimental results obtained by applying the network for segmenting two X-ray images are presented.>