Performance modeling of heterogeneous data networks

A heterogeneous data network consists of Local Area Networks (LANs) interconnected with either leased lines, packet-switched networks, Metropolitan Area Networks (MANs), or combinations thereof. Heterogeneous networks are characterized by bursty traffic, nested segmentation and reassembly of packets, window flow control and round-robin channel access. We develop a performance methodology for estimating user perceived delay and buffer overflow in heterogeneous data networks. The methodology is based on well-known two-moment approximation schemes. Modifications of these schemes are proposed in order to model the bandwidth allocation policies of the MANs and to capture the burstiness of the traffic. The methodology is applied to several LAN-MAN and LAN-MAN-WAN network examples.Supported partially through AT&T Grant No. 5-20491 and partially through NSF Grant No. NCR-8914447.     

A decentralized control mechanism for stream processing networks

Data streaming applications are becoming more and more common due to the rapid development in emerging areas such as sensor networks, multimedia streaming, and on-line data mining, etc. These applications are often running in a decentralized, distributed environment. The requirements for processing large volumes of streaming data at real time have posed many great design challenges. One of the critical issues is to optimize the ongoing resource consumption of multiple, distributed, cooperating processing units. In this paper, we consider a generic model for the general stream data processing systems. We address the resource allocation problem for a collection of processing units so as to maximize the weighted sum of the throughput of different streams. Each processing unit may require multiple input data streams simultaneously and produce one or many valuable output streams. We develop decentralized control mechanisms that maximize the overall system throughput in such data stream processing networks. Performance analysis on the optimality and complexity of these mechanisms are also provided.     

Database placement in communication networks for minimizing the overall transmission cost

The minimum spanning tree write policy for the maintenance of the consistency of a distributed database, where replicated data exist, has been proposed in [1]. In this paper, we first present a data placement heuristic algorithm in general networks for minimizing the overall transmission cost for processing the typical demands of queries (by a “simple” process strategy) and updates (by the minimum spanning tree write policy). Several interesting optimality estimation results of this algorithm are shown, while the computational intractability of the complete optimization, with respect to the simple strategy, is shown as well. Secondly, we apply a classical climbing hill technique to obtain a dynamic database placement algorithm based on an employed optimizer—a collection of distributed query process algorithms. This is guaranteed to output a “locally optimal” data allocation. The implementation results also show that those two heuristics work well in practice.     

Configuration of fully replicated distributed database system over wide area networks

The cost and performance of a distributed database system (DDS) depends on data distribution and database server configuration across the network. An inappropriate allocation of data and database severs could result in a DDS which is either too costly or unacceptably slow. This paper models the optimal configuration of fully replicated DDS. The problem is formulated as an integer linear programming problem and a solution procedure based on Lagrangian relaxation and subgradient optimization is proposed. The proposed solution procedure was computationally tested under various scenarios regarding communication, processor costs, and transaction characteristics.     

A framework of distributed indexing and data dissemination in large scale wireless sensor networks

Many data dissemination techniques have been proposed for wireless sensor networks (WSNs) to facilitate data dissemination and query processing. However, these techniques may not work well in a large scale sensor network where a huge amount of sensing data is generated. In this paper, we propose an integrated distributed connected dominating set based indexing (CBI) data dissemination scheme to support scalable handling of large amount of sensing data in large scale WSNs. Our CBI can minimize the use of limited network and computational resources while providing timely responses to queries. Moreover, our data dissemination framework ensures scalability and load balance as well as adaptivity in the presence of dynamic changes. Analysis and simulations are conducted to evaluate the performance of our CBI scheme. The results show that the CBI scheme outperforms the external storage-based scheme, local storage-based scheme and the data-centric storage-based scheme in overall performance.     

Modeling the complexity of genetic networks: Understanding multigenic and pleiotropic regulation

Molecular genetics presents an increasingly complex picture of the genome and biological function. Evidence is mounting for distributed function, redundancy, and combinatorial coding in the regulation of genes. Satisfactory explanation will require the concept of a parallel processing signaling network. Here we provide an introduction to Boolean networks and their relevance to present-day experimental research. Boolean network models exhibit global complex behavior, self-organization, stability, redundancy and periodicity, properties that deeply characterize biological systems. While the life sciences must inevitably face the issue of complexity, we may well look to cybernetics for a modeling language such as Boolean networks which can manageably describe parallel processing biological systems and provide a framework for the growing accumulation of data. We finally discuss experimental strategies and database systems that will enable mapping of genetic networks. The synthesis of these approaches holds an immense potential for new discoveries on the intimate nature of genetic networks, bringing us closer to an understanding of complex molecular physiological processes like brain development, and intractable medical problems of immediate importance, such as neurodegenerative disorders, cancer, and a variety of genetic diseases.     

Resource allocation for end-to-end QoS provisioning in a hybrid wireless WCDMA and wireline IP-based DiffServ network

In the future UMTS network, the heterogeneous traffics of multimedia services demand various QoS provisioning. At the same time, the seamlessly conveying of information between mobile users and a hybrid network requires the networking from wireless to wireline domains. However, in both academia and industries, the end-to-end QoS provisioning in the integration of wireline and wireless networks remains a challenge. In this paper, a modeling of a hybrid wireless WCDMA and wireline IP-based DiffServ network is presented to investigate the resource allocation for end-to-end QoS provisioning for multimedia services. In the wireless domain, the mathematical modeling of the cross-layer model including the physical layer, the link layer and the network layer is built. The connection admission control scheme is implemented based on the cross-layer model to determine the amount of resource for different services. In the wireline domain, we define the mapping of QoS classes between UMTS and DiffServ networks according to different QoS requirements. We propose a bandwidth allocation scheme to provide satisfactory packet loss and delay guarantee in DiffServ networks. The final end-to-end admission control scheme combines the resource allocation and admission control in both wireless and wireline domains. The analytical and simulation results show that the proposed resource allocation and admission control schemes work cooperatively in the presented hybrid wireless and wireline networks to guarantee the end-to-end QoS requirements for multimedia services.     

Stereoscopic neuro-vision for three-dimensional object recognition

Neural network technology has provided new methodologies for solving difficult computational problems in many areas of science and engineering. Neural networks, along with their varied learning techniques, have replaced complicated mathematical models, complex estimation techniques, or optimization procedures in several applications. One particular area seeing much benefit from these new computational paradigms is machine vision. The machine vision field has long needed approaches offering robust operation, massive parallel and distributed computational capabilities, and graceful system degradation. Neural networks offer these capabilities along with the potential of direct hardware implementation.This article demonstrates several novel uses of artificial neural networks in the processing of stereoscopic images for three-dimensional object recognition. It will be shown that several different types of neural networks can be combined, with a rule base and conventional processing techniques, for the creation of a powerful 3-D object recognition system. This hybrid system has been tested on several simple objects and the results are presented.     

Data association based on optimization in graphical models with application to sensor networks

We propose techniques based on graphical models for efficiently solving data association problems arising in multiple target tracking with distributed sensor networks. Graphical models provide a powerful framework for representing the statistical dependencies among a collection of random variables, and are widely used in many applications (e.g., computer vision, error-correcting codes). We consider two different types of data association problems, corresponding to whether or not it is known a priori which targets are within the surveillance range of each sensor. We first demonstrate how to transform these two problems to inference problems on graphical models. With this transformation, both problems can be solved efficiently by local message-passing algorithms for graphical models, which solve optimization problems in a distributed manner by exchange of information among neighboring nodes on the graph. Moreover, a suitably reweighted version of the max–product algorithm yields provably optimal data associations. These approaches scale well with the number of sensors in the network, and moreover are well suited to being realized in a distributed fashion. So as to address trade-offs between performance and communication costs, we propose a communication-sensitive form of message-passing that is capable of achieving near-optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.     

An integer programming model for the allocation of databases in a distributed computer system

Designers of distributed computer systems have to resolve issues like allocation of user nodes among processors, partitioning the central database and allocation of these partitions among processors. In this paper, we identify systems where decisions regarding the database partitioning and the allocation of these partitions among processors can be effectively merged with decisions regarding the assignment of user nodes to processors. An integer programming model that can be used in designing these systems is formulated. Heuristic and optimal solution procedures are developed. These procedures are tested and found to be effective on a wide range of problem structures.     

Four correlates of complex behavioral networks: Differentiation,behavior, connectivity,and compartmentalization: Carving networks at their joints

Some of the most complex networks are those that (i) have been engineered under selective pressure (either economic or evolutionary), and (ii) are capable of eliciting network‐level behaviors. Some examples are nervous systems, ant colonies, electronic circuits and computer software. Here we provide evidence that many such selected, behavioral networks are similar in at least four respects. (1) Differentiation: Nodes of different types are used in a combinatorial fashion to build network structures through local connections, and networks accommodate more structure types via increasing the number of node types in the network (i.e., increasing differentiation), not via increasing the length of structures. (2) Behavior: Structures are themselves combined globally to implement behaviors, and networks accommodate a greater behavioral repertoire via increasing the number of lower‐level behavior types (including structures), not via increasing the length of behaviors. (3) Connectivity: In order for structures in behavioral networks to combine with other structures within a fixed behavior length, the network must maintain an invariant network diameter, and this is accomplished via increasing network connectivity in larger networks. (4) Compartmentalization: Finally, for reasons of economical wiring, behavioral networks become increasingly parcellated. Special attention is given to nervous systems and computer software, but data from a variety of other behavioral selected networks are also provided, including ant colonies, electronic circuits, web sites and businesses. A general framework is introduced illuminating why behavioral selected networks share these four correlates. Because the four above features appear to apply to computer software as well as to biological networks, computer software provides a useful framework for comprehending the large‐scale function and organization of biological networks. © 2005 Wiley Periodicals, Inc. Complexity 10: 13–40, 2005     

Approximation for the mean value performance of locking algorithms for distributed database systems: a partitioned database

Concurrent access to databases must be synchronized for correct execution of transactions and preservation of data consistency. This is usually achieved through use of concurrency control algorithms, amongst which locking algorithms are the most popular both in the literature and in practice. Several analytic methods have been developed for predicting the performance of centralized database systems employing locking algorithms for concurrency control, but very few exist for distributed database systems.This paper proposes a method to approximate the mean value of various performance parameters in distributed database systems using locking for concurrency control. The main contribution of this approach is its ability to model the interaction between resource and data contention and the resulting effect on system performance. System performance is evaluated at a point where the interaction between these two factors is in equilibrium (stable state) and both the data and resource contention equations are simultaneously satisfied.The model involves the solution of a set of simultaneous polynomial equations whose order is dependent on several problem parameters such as the number of nodes and number of locks requested per transaction. These equations are solved by an iterative procedure to evaluate approximate values of relative throughput, utilization of servers and transaction response time. The small computational requirements of the analytical model permit sensitivity analysis on network parameters, and can thus be effectively used by system designers to evaluate choices of communication line speeds, processor capacity, database sizes, etc.The analytic approximations have been extensively verified against simulations for networks with up to 20 nodes. The input traffic was varied from light loads (about 5% utilization of the channels and processors) to heavy loads (about 65% utilization of the processors and channels). The discrepancies between the analytic approximation and the simulation were quite small (2–8%).This work was done while the authors were at Drexel University, Philadelphia.     

Modelling non-stationary dynamic gene regulatory processes with the BGM model

Recently, a Bayesian network model for inferring non-stationary regulatory processes from gene expression time series has been proposed. The Bayesian Gaussian Mixture (BGM) Bayesian network model divides the data into disjunct compartments (data subsets) by a free allocation model, and infers network structures, which are kept fixed for all compartments. Fixing the network structure allows for some information sharing among compartments, and each compartment is modelled separately and independently with the Gaussian BGe scoring metric for Bayesian networks. The BGM model can equally be applied to both static (steady-state) and dynamic (time series) gene expression data. However, it is this flexibility that renders its application to time series data suboptimal. To improve the performance of the BGM model on time series data we propose a revised approach in which the free allocation of data points is replaced by a changepoint process so as to take the temporal structure into account. The practical inference follows the Bayesian paradigm and approximately samples the network, the number of compartments and the changepoint locations from the posterior distribution with Markov chain Monte Carlo (MCMC). Our empirical results show that the proposed modification leads to a more efficient inference tool for analysing gene expression time series.     

Supply Chain Optimization via Distributed Model Predictive Control

Supply chains networks describe the flow of material, energy and information from their sources to end costumers. Typically, such a network consists of several stages such as suppliers, manufacturers and retailers, which contribute to the completion of a product. Here, we restrict ourselves to one arc from supplier to costumer. Instead of known strategies such as postponement, we apply a model predictive control scheme to deal with the optimal steering problem of the considered arc in a distributed way. To this end, we assign one controller to each stage along the considered arc. Since the stages may represent different companies, local cost criteria are imposed, which are optimized subject to local and global constraints while communicating with neighbors. Additionally, we discuss the applicability of such an approach regarding information requirements and respective policies of companies. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamics of Coupled Cell Networks: Synchrony, Heteroclinic Cycles and Inflation

We consider the dynamics of small networks of coupled cells. We usually assume asymmetric inputs and no global or local symmetries in the network and consider equivalence of networks in this setting; that is, when two networks with different architectures give rise to the same set of possible dynamics. Focussing on transitive (strongly connected) networks that have only one type of cell (identical cell networks) we address three questions relating the network structure to dynamics. The first question is how the structure of the network may force the existence of invariant subspaces (synchrony subspaces). The second question is how these invariant subspaces can support robust heteroclinic attractors. Finally, we investigate how the dynamics of coupled cell networks with different structures and numbers of cells can be related; in particular we consider the sets of possible “inflations” of a coupled cell network that are obtained by replacing one cell by many of the same type, in such a way that the original network dynamics is still present within a synchrony subspace. We illustrate the results with a number of examples of networks of up to six cells.     

A Closed Queueing Network Model to Evaluate the Impact of Recovery Operations on the Performance of Database Servers

As database servers proliferate in modern information systems architectures in organizations, the issue of protecting and recovering the databases becomes of utmost importance. By developing an analytical model based on a closed network of queues, this paper analyses how different database recovery mechanisms impact on the normal transaction processing. Such a model enables one to capture intricate effects that are peculiar to complex, tightly coupled, multi-component systems, such as database recovery systems, and can be used to facilitate the design and the tuning of database recovery managers. The proposed model provides important performance measures in terms of average transaction processing time and overall systems throughput. Numerical experiments using actual recovery methods demonstrate the effectiveness of the modelling approach.     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

A constrained nonlinear 0–1 program for data allocation

This paper analyzes the problem of allocating copies of relations from a global database to the sites of a geographically distributed communication network. The objective of the allocation is to minimize the total cost due to transmissions generated by queries from the various sites, including queries that access multiple relations. This allocation problem is modeled as a constrained nonlinear 0–1 subproblems generated during subgradient optimization are solved as optimization. Some of the unconstrained quadratic 0–1 subproblems generated during subgradient optimization are solved as maximum flow problems, while the others require implicit enumeration, depending on the nature of the objective function coefficients of the subproblems. Our solution approach is tested extensively on data allocation problems with as many as 100 sites and 20 relations. On a set of randomly generated test problems our approach was close to two orders of magnitude faster than the general purpose integer programming code OSL.     

Stable and emergent network topologies: A structural approach

Economic, social and military networks have at least one thing in common: they change over time. For various reasons, nodes form and terminate links, thereby rearranging the network. In this paper, we present a structural network mechanism that formalizes a possible incentive that guides nodes in constructing their local network structure. The mechanism assumes that nodes deliberately form and terminate links as they attempt to gain network advantage and/or an identifiable position in the network. Reiteration of this mechanism, which only uses local network characteristics, results in emergent, stable network topologies. Examples are uni-polar networks, bi-polar networks and cycle-networks. This process illustrates that local, binary decisions shape global network structures. These results may be used to derive some rules of thumb for designing networks.