Agent-based randomized broadcasting in large networks

Mobile agents are software abstractions that can migrate across the links of a network. They naturally extend the object oriented program style and nicely correspond to agents as examined in game theory. In this paper, we introduce a simple, robust, and efficient randomized broadcast protocol within this mobile agent programming paradigm. We show that by using this scheme, broadcasting enquiries in a random graph of certain density O(lnn) steps, where n denotes the number of nodes in the graph. Then, we consider bounded degree graphs and prove that we are able to distribute an information among all nodes in O(D) steps, where D denotes the diameter of the graph. We also show that, in contrast to traditional randomized broadcasting (TRB), graphs exist in which agent-based randomized broadcasting requires Ω(n²) steps. On the other hand, some graphs which require Ω(nlnn) steps to spread the information in the traditional broadcast model, allow very fast agent-based broadcasting. It should be noted that the previously mentioned results are guaranteed with probability 1-o(1/n).     

Threshold analysis of the susceptible-infected-susceptible model on overlay networks

In this paper, we study epidemic spreading on overlay networks in which n multiple sets of links interconnect among the same nodes. By using the microscopic Markov-chain approximation (MMA) approach, we establish the conditions of epidemic outbreak for two kinds of spreading mechanisms in such an overlay network: the concatenation case and the switching case. When a uniform infection rate is set in all the subnetworks, we find the epidemic threshold for the switching case is just n times as large as that of concatenation case. We also find that the overlay network with a uniform infection rate can be considered as an equivalent (in the sense of epidemic dynamics and epidemic threshold) weighted network. To be specific, the concatenation case corresponds to the integer weighted network, while the switching case corresponds to the fractional weighted network. Interestingly, the time-varying unweighted network can be mapped into the static weighted network. Our analytic results exhibit good agreement with numerical simulations.     

A tight bound on the number of mobile servers to guarantee transferability among dominating configurations

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of nodes, and assume that a user can receive the service if at least one adjacent node (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees consisting of n nodes, ⌊n/2⌋ mobile servers are sometimes necessary and always sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with n nodes, ⌈(n+1)/3⌉ mobile servers are sometimes necessary and always sufficient.     

Dynamic network reliability modeling under nonhomogeneous Poisson processes

In this paper, we consider a two-state (up and down) network consisting of n links. We study the D-spectrum based dynamic reliability of the network under the assumption that the links are subject to failure according to a nonhomogeneous Poisson process. Several mixture representations are provided for the reliability function of residual lifetime of used networks, under different conditions on the status of the network or its links. These representations enable us to explore the residual reliability of operating networks in terms of the reliability functions of residual lifetimes of upper record values. The distribution function of inactivity time of a network is examined under the condition that the network has failed by inspection time t. Stochastic ordering properties of the residual lifetimes of networks under conditional D-spectra are investigated. Several examples and graphs are also provided to illustrate the established results.     

Concave cost minimization on networks

The paper deals with the problem of finding a minimum cost multicommodity flow on an uncapacitated network with concave link costs. Problems of this type are the optimal design of a network in the presence of scale economies and the telpack problem.Two different definitions of local optimality are given and compared both from the point of view of the computational complexity and from the point of view of the goodness of the solution they may provide.A vertex following algorithm to find a local optimum is proposed. The computational complexity of each iteration of the algorithm is O(n³), where n is the number of nodes of the network, and is independent of the differentiability of the objective function.Experimental results obtained from a set of test problems of size ranging from 11 nodes and 23 arcs to 48 nodes and 174 arcs, with number of commodities up to 5, are given.     

Broadcasting secure messages via optimal independent spanning trees in folded hypercubes

Fault-tolerant broadcasting and secure message distribution are important issues for network applications. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and security. An n-dimensional folded hypercube, denoted by FQ_n, is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, [12], Ho(1990) proposed an algorithm for constructing n+1 edge-disjoint spanning trees each with a height twice the diameter of FQ_n. Yang et al. (2009), [29] recently proved that Ho’s spanning trees are indeed independent, i.e., any two spanning trees have the same root, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce n+1 independent spanning trees of FQ_n, where the height of each tree is equal to the diameter of FQ_n plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal.     

A matrix-based measure of inter-node walk relatedness in a network

For a pair of nodes in a network, a measure of walk relatedness is introduced. The measure is based on the total weight (number) of k-step walks connecting the pair, i.e., the corresponding entry of the kth power of the network matrix as k → ∞. The damping factor r ^?k is used, where r is the largest eigenvalue of the network matrix. The measure turns out to be equal to the product of the pair’s coreness values, i.e., the nodes’ coordinates in the network matrix’s right and left eigenvectors corresponding to r. The reduction of walk relatedness in a network caused by the removal of a node or link is investigated, i.e., the dependence of the reduction on the structural position (coreness) of the removed element. It is revealed that the “damage” can be measured by the drop in the value of r after the removal; to find this drop, the perturbation method is used. Some possible applications are indicated, and a numerical example with a large real network of 197 nodes and 780 links is considered.     

Merger effect of two firms under network equilibrium

This paper studies the merger effect of two firms under the price competition of n firms, represented by n nodes on a linear network equilibrium model. The difference of profits between pre- and post-merger of the two firms can be described explicitly in terms of the substitution matrix. In general, the evaluation of the merger effect requires the knowledge of the substitution effects among all n nodes. For some interesting special cases, however, we obtain simple qualitative results. Specifically, the profitability of the merger can be predicted from the substitution effect of the two firms. Numerical examples exhibit the usefulness of our results.     

Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.     

Independent permutations,as related to a problem of Moser and a theorem of Pólya

We introduce the notion of a set of independent permutations on the domain {0, 1,… n ? 1}, and obtain bounds on the size of the largest such set. The results are applied to a problem proposed by Moser in which he asked for the largest number of nodes in a d-cube of side n such that no n of these nodes are collinear. Independent permutations are also related to the problem of placing n non-capturing superqueens (chess queens with wrap-around capability) on an n × n board. As a special case of this treatment we obtain Pólya's theorem that this problem can be solved if and only if n is not a multiple of 2 or 3.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Integer version of the multipath flow network synthesis problem

We consider the following integer multipath flow network synthesis problem. We are given two positive integers q, n, (1<q<n), and a non-negative, integer, symmetric, n×n matrix R, each non-diagonal element r_ij of which represents the minimum requirement of q-path flow value between nodes i and j in an undirected network on the node set N={1,2,…,n}. We want to construct a simple, undirected network G=[N,E] with integer edge capacities {u_e:e∈E} such that each of these flow requirements can be realized (one at a time) and the sum of all the edge capacities is minimum. We present an O(n³) combinatorial algorithm for the problem and we show that the problem has integer rounding property.     

Determining Knotsw and Links by Cyclic Branched Coverings

It is well known that different knots or links in the 3-sphere can have homeomorphic n-fold cyclic branched coverings. We consider the following problem: for which values of nis a knot of link determined by itsn-fold cyclic branched covering? We consider the class of hyperbolic resp.2π/n-hyperbolic links. The isometry or symmetry groups of such links are finite, and their n-fold branched coverings are hyperbolic 3-manifolds. Our main result states that if ndoes not divide the order of the finite symmetry group of such a link, then the link is determined by its n-fold branched covering. In a sense, the result is best possible; the key argument of its proof is algebraic using some basic result about finite p-groups. The main result applies, for example, to the cyclic branched coverings of the 2-bridge links; in particular, it gives a classification of the maximally symmetricD₆-manifolds which are exactly the 3-fold branched coverings of the 2-bridge links.     

Vassiliev invariants of type one for links in the solid torus

In Bataineh (2003) [2] we studied the type one invariants for knots in the solid torus. In this research we study the type one invariants for n-component links in the solid torus by generalizing Aicardi's invariant for knots in the solid torus to n-component links in the solid torus. We show that the generalized Aicardi's invariant is the universal type one invariant, and we show that the generalized Aicardi's invariant restricted to n-component links in the solid torus with zero winding number for each component is equal to an invariant we define using the universal cover of the solid torus. We also define and study a geometric invariant for n-component links in the solid torus. We give a lower bound on this invariant using the type one invariants, which are easy to calculate, which helps in computing this geometric invariant, which is usually hard to calculate.     

Sorting with networks of data structures

We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time Θ(n²) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time Ω(n^3/2), and that there exist graphs of k nodes which can sort in time Θ(nlog_kn), which is optimal.     

Scheduling independent jobs for torus connected networks with/without link contention

In this paper, we investigate the problem of how to schedule n independent jobs on an m × m torus based network. We develop a model to to quantify the effect of contention for communication links on the dilation of job execution time when multiple jobs share communication links; we then design an efficient algorithm to schedule a set of n independent jobs with different torus size requirements on a given torus with an objective to minimize the total schedule length. We also develop a feasibility algorithm for pre-emptively scheduling a given set of jobs on a torus of given size with a given deadline. We provide analysis for both the algorithms.     

The cut cone III: On the role of triangle facets

The cut polytopeP _n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP _n arises from the triangle inequalities:x _ij +x _ik +x _jk ≤ 2 andx _ij -x _ik -x _jk ≤ 0 for 1 ≤i,j, k ≤n. Hence, the metric polytope M_n, defined as the solution set of the triangle inequalities, is a relaxation ofP _n . We consider several properties of geometric type for P_n, in particular, concerning its position withinM _n . Strengthening the known fact ([3]) thatP _n has diameter 1, we show that any set ofk cuts,k ≤ log₂ n, satisfying some additional assumption, determines a simplicial face ofM _n and thus, also, ofP _n . In particular, the collection of low dimension faces ofP _n is contained in that ofM _n . Among a large subclass of the facets ofP _n , the triangle facets are the closest ones to the barycentrum of P_n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP _n and its triangle facets are mentioned.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

A note on a mixed routing and scheduling problem on a grid graph

We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.