A theory of decomposition into prime factors of layered interconnection networks

The cross-product technique, introduced by Even and Litman (1992) [8], is extended into a full decomposition theory enabling a unique (up to isomorphism) and polynomial factorization of layered interconnection networks (including many well-known networks) into a product of prime factors. A polynomial algorithm is provided for checking whether a given layered interconnection network is isomorphic to a network that is uniquely decomposable into prime factors.     

A general performance analysis method for uniform memory architectures

The performance of a multiprocessor system greatly depends on the bandwidth of its memory architecture. In this paper, uniform memory architectures with various interconnection networks including crossbar, multiple-buses and generalized shuffle networks are studied. We propose a general method based on the Markov chain model by assuming that the blocked memory requests will be redistributed to the memory modules in the next memory cycle. This assumption results in an analysis with lower complexity where the number of states is linearly proportional to the number of processors. Moreover, it can provide excellent estimation on the system power and memory bandwidth for all three types of interconnection networks as compared with the simulation results in which the blocked memory requests are resubmitted to the same memory module. Comparisons also show that our method is more general and precise than most existing analysis methods. The method is further extended to estimate the performance of multiprocessor system with caches. The approximation results are also shown to be remarkably good.     

Layouts for mobility management in wireless ATM networks

In this paper, we present a new model that combines quality of service and mobility aspects in wireless ATM networks. Namely, besides the hop count and load parameters of the basic ATM layouts, we introduce a new notion of distance that estimates the time needed to reconstruct the virtual channel of a wireless user when he moves through the network. Quality of service guarantee dictates that the rerouting phase must be imperceptible, that is, the maximum distance between two virtual channels must be maintained as low as possible. Therefore, a natural combinatorial problem arises in which suitable trade-offs must be determined between the different performance measures. We first show that establishing the existence of a layout with maximum hop count h, load l and distance d is NP-complete, even in the very restricted case h=2, l=1 and d=1. We then provide optimal layout constructions for basic interconnection networks, such as chains and rings.     

Hamiltonicity of large generalized de Bruijn cycles

In this article, we determine when the large generalized de Bruijn cycles are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized cycles. They are Kronecker products of generalized de Bruijn digraphs and dicycles.     

Dynamical behaviors of fuzzy reaction–diffusion periodic cellular neural networks with variable coefficients and delays

When modeling neural networks in a real world, not only diffusion effect and fuzziness cannot be avoided, but also self-inhibitions, interconnection weights, and inputs should vary as time varies. In this paper, we discuss the dynamical behaviors of delayed reaction–diffusion fuzzy cellular neural networks with varying periodic self-inhibitions, interconnection weights as well as inputs. By using Halanay’s delay differential inequality, M$M$-matrix theory and analytic methods, some new sufficient conditions are obtained to ensure the existence, uniqueness, and global exponential stability of the periodic solution, and the exponentially convergent rate index is also estimated. In particular, the traditional assumption on the differentiability of the time-varying delays is no longer needed. The methodology developed in this paper is shown to be simple and effective for the exponential periodicity and stability analysis of neural networks with time-varying delays. Two examples are given to show the usefulness of the obtained results that are less restrictive than recently known criteria.     

Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.     

关于超立方体网络的(d,k)独立数

(d,k)独立数是分析互连网络性能的一个重要参数.对于任意给定的图G和正整数d和k,确定G的(d,k)独立数问题是一个NPC问题.因此,确定一些特殊图的(d,k)独立数显得很重要.本文确定了k维超立方体网络的(d,k)独立数等于2,如果d=k≥4或者d=k-1≥6 以及αd,k-t(Qk)=αd,k(Qk),其中0≤t≤k-2,1≤d≤k-t-1.     

An energy-based analysis of reduced-order models of (networked) synchronous machines

Stability of power networks is an increasingly important topic because of the high penetration of renewable distributed generation units. This requires the development of advanced techniques for the analysis and controller design of power networks. Although there are widely accepted reduced-order models to describe the power network dynamics, they are commonly presented without details about the reduction procedure. The present article aims to provide a modular model derivation of multi-machine power networks. Starting from first-principle fundamental physics, we present detailed dynamical models of synchronous machines and clearly state the underlying assumptions which lead to some of the standard reduced-order multi-machine models. In addition, the energy functions for these models are derived, which allows to represent the multi-machine systems as port-Hamiltonian systems. Moreover, the systems are proven to be shifted passive, which permits for a power-preserving interconnection with other passive components.     

Bellman最优原理在复杂加权网络中的应用研究

针对现有算法及软件计算复杂加权网络介数的局限性,应用Bellman最优原理于复杂加权网络介数计算中,并针对复杂网络动态演化,节点众多,重点,节点间无边连接等特点作了相应修改.依算法实例计算出了复杂加权网络的最短路径长、最短路径和介数,最后经验证算法具有较快的运行速度和较准确的结果.     

Insensitive Bandwidth Sharing in Data Networks

We represent a data network as a set of links shared by a dynamic number of competing flows. These flows are generated within sessions and correspond to the transfer of a random volume of data on a pre-defined network route. The evolution of the stochastic process describing the number of flows on all routes, which determines the performance of the data transfers, depends on how link capacity is allocated between competing flows. We use some key properties of Whittle queueing networks to characterize the class of allocations which are insensitive in the sense that the stationary distribution of this stochastic process does not depend on any traffic characteristics (session structure, data volume distribution) except the traffic intensity on each route. We show in particular that this insensitivity property does not hold in general for well-known allocations such as max-min fairness or proportional fairness. These results are ilustrated by several examples on a number of network topologies.     

几个著名网络的限长路径

设给出了（h,ψ）-η限长路径问题是图论中的Menger定理的变形和推广，在实时容错网络设计和分析中有重要意义。对于给定的正整数d,Ad(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数；Bd(D)表示D的顶点子集B中的最小顶点数使得D－B的直径大于d.已证明确定Ad(D)的问题是NPC问题，而且显然有不等式Ad(D)≤Bd(D)。本文考虑D为超立方体网络、De Bruijn网络和Kautz网络，对d的不同值确定了Ad(D)及Bd(D),而且均有Ad(D)=Bd(D)。     

Graphs for small multiprocessor interconnection networks

Let D be the diameter of a graph G and let λ₁ be the largest eigenvalue of its (0, 1)-adjacency matrix. We give a proof of the fact that there are exactly 69 non-trivial connected graphs with (D + 1)λ₁ ? 9. These 69 graphs all have up to 10 vertices and were recently found to be suitable models for small multiprocessor interconnection networks. We also examine the suitability of integral graphs to model multiprocessor interconnection networks, especially with respect to the load balancing problem. In addition, we classify integral graphs with small values of (D + 1)λ₁ in connection with the load balancing problem for multiprocessor systems.     

连通无向图Rabin数的一个界

可靠性和有效性是互连网络设计的重要标准,而Rabin数是度量网络容错性和传输延迟的重要参数.将通过图的容错直径给出2- 连通无向图和~3- 连通无向图的~Rabin 数r_2(G)和r_3(G)的界;同时也得到r_2(G) = D_2(G)成立的一个条件.     

State space collapse with application to heavy traffic limits for multiclass queueing networks

Heavy traffic limits for multiclass queueing networks are a topic of continuing interest. Presently, the class of networks for which these limits have been rigorously derived is restricted. An important ingredient in such work is the demonstration of state space collapse. Here, we demonstrate state space collapse for two families of networks, first-in first-out (FIFO) queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks, we employ law of large number estimates to show a form of compactness for appropriately scaled solutions. The limits of these solutions are next shown to satisfy fluid model equations corresponding to the above queueing networks. Results from Bramson [4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams [41]. State space collapse and the ensuing heavy traffic limits also hold for more general queueing networks, provided the solutions of their fluid model equations converge. Partial results are given for such networks, which include the static priority disciplines. This revised version was published online in June 2006 with corrections to the Cover Date.     

Activation clustering in neural and social networks

Questions related to the evolution of the structure of networks have received recently a lot of attention in the literature. But what is the state of the network given its structure? For example, there is the question of how the structures of neural networks make them behave? Or, in the case of a network of humans, the question could be related to the states of humans in general, given the structure of the social network. The models based on stochastic processes developed in this article, do not attempt to capture the fine details of social or neural dynamics. Rather they aim to describe the general relationship between the variables describing the network and the aggregate behavior of the network. A number of nontrivial results are obtained using computer simulations. © 2005 Wiley Periodicals, Inc. Complexity 10: 42–50, 2005     

A general formulation for mean-value analysis in product-form batch-movement queueing networks

A number of recent papers have shown that many classes of queueing networks with batches of customers served and routed through the network have equilibrium distributions which factorise into product forms over the nodes of the network. In this paper we demonstrate how such networks are amenable to a mean-value analysis which generalises that used for single-movement networks.Since product-form stochastic Petri nets (SPNs) can be viewed as batch-movement queueing networks, our algorithm is also applicable to their analysis.     

Large graphs with given degree and diameter. II

The following problem arises in the study of interconnection networks: find graphs of given maximum degree and diameter having the maximum number of vertices. Constructions based on a new product of graphs, which enable us to construct graphs of given maximum degree and diameter, having a great number of vertices from smaller ones are given; therefore the best values known before are improved considerably.     

Minimum spanning trees in networks with varying edge weights

This paper considers the problem of determining minimum spanning trees in networks in which each edge weight can assume a finite number of distinct values. We use the algebraic structure of an underlying Hasse diagram to describe the relationship between different edge-weight realizations of the network, yielding new results on how MSTs change under multiple edge-weight perturbations. We investigate various implementation strategies for updating MSTs in this manner. Computational results are provided for some challenging test networks.     

Deadlock free buffer allocation in closed queueing networks

Blocking queueing networks are of much interest in performance analysis due to their realistic modeling capability. One important feature of such networks is that they may have deadlocks which can occur if the node capacities are not sufficiently large. A necessary and sufficient condition for the node capacities is presented such that the network is deadlock free. An algorithm is given for buffer allocation in blocking queueing networks such that no deadlocks will occur assuming that the network has the special structure called cacti-graph. Additional algorithm which takes linear time in the number of nodes, is presented to find cycles in cacti networks.Akyildiz's work was supported in part by School of Information and Computer Science, ICS, of Georgia Tech and by the Air Force Office of the Scientific Research (AFOSR) under Grant AFOSR-88-0028.