On Spectrum Congestion and Capacity of Radio Links

This paper addresses the operation of radio links under mutual interference conditions, an important problem in spectrum management and radio link design. It introduces the capacity loss and isolation index as measures of effective use of radio links and radio frequency spectrum resources.     

Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks

In transmission networks an important routing problem is to find a pair of link disjoint paths which optimises some performance measure. In this paper the problem of obtaining the most reliable pair of link disjoint paths, assuming the reliability of the links are known, is considered. This is a non-linear optimisation problem. It is further introduced the constraint that the length of the paths should not exceed a certain number of links, which makes the efficient resolution of the problem more complex.     

Pairwise-stability and Nash equilibria in network formation

Suppose that individual payoffs depend on the network connecting them. Consider the following simultaneous move game of network formation: players announce independently the links they wish to form, and links are formed only under mutual consent. We provide necessary and sufficient conditions on the network link marginal payoffs such that the set of pairwise stable, pairwise-Nash and proper equilibrium networks coincide, where pairwise stable networks are robust to one-link deviations, while pairwise-Nash networks are robust to one-link creation but multi-link severance. Under these conditions, proper equilibria in pure strategies are fully characterized by one-link deviation checks. We thank William Thomson, an associate editor and two anonymous referees for their suggestions that led to substantial improvements. We also thank Sjaak Hurkens, Bettina Klaus, Jordi Massó and Giovanni Neglia for helpful conversations. The first author gratefully acknowledges the financial support from the Spanish Ministry of Education and FEDER through grant SEJ2005-01481/ECON, the Fundación BBVA and the Barcelona Economics Program of XREA. The second author is grateful to the Netherlands Organization for Scientific Research (NWO) for its support under grant VIDI-452-06-013.     

Optimal double-resource assignment for the robust design problem in multistate computer networks

This paper proposes a novel approach to get the exact optimal double-resource assignment for the robust design problem in multistate computer networks. A multistate computer network consists of links and vertices where both kinds of resources may have several states due to failure, partial failure or maintenance. Therefore, each link (vertex) in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a multistate computer network (MCN) is to search for the minimum capacity assignment of each link and vertex such that the network still survived even under both kinds of failures. However, how to optimally assign the capacity to each resource is not an easy task. This paper proposes an efficient approach to do such assignment and illustrates the efficiency of the proposed approach by some numerical examples.     

Routing and capacity assignment in backbone communication networks under time varying traffic conditions

This paper studies the problem of assigning capacities to links in a backbone communication network and determining the routes used by messages for all communicating node pairs in the network under time varying traffic conditions. The best routes are to be chosen from among all possible routes in the network. Tradeoffs between link costs and response time to users are achieved by specifying an upper limit on the average link queueing delay in the network. The goal is to minimize total link fixed and variable costs. The topology of the network and the end-to-end traffic requirements during the different busy-hours are assumed to be known. The problem is formulated as a mathematical programming model. An efficient solution procedure based on a Lagrangian relaxation of the problem is developed. The results of extensive computational experiments across a variety of networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

Time-dependent discrete road network design with both tactical and strategic decisions

This paper aims to model and investigate the discrete urban road network design problem, using a multi-objective time-dependent decision-making approach. Given a base network made up with two-way links, candidate link expansion projects, and candidate link construction projects, the problem determines the optimal combination of one-way and two-way links, the optimal selection of capacity expansion projects, and the optimal lane allocations on two-way links over a dual time scale. The problem considers both the total travel time and the total CO emissions as the two objective function measures. The problem is modelled using a time-dependent approach that considers a planning horizon of multiple years and both morning and evening peaks. Under this approach, the model allows determining the sequence of link construction, the expansion projects over a predetermined planning horizon, the configuration of street orientations, and the lane allocations for morning and evening peaks in each year of the planning horizon. This model is formulated as a mixed-integer programming problem with mathematical equilibrium constraints. In this regard, two multi-objective metaheuristics, including a modified non-dominated sorting genetic algorithm (NSGA-II) and a multi-objective B-cell algorithm, are proposed to solve the above-mentioned problem. Computational results for various test networks are also presented in this paper.     

Communication network formation with link specificity and value transferability

We model strategic communication network formation with (i) link specificity: link maintenance lowers specific attention and thus value (negative externality previously ignored for communication) and (ii) value transferability via indirect links for informational but not for social value (positive externality modeled uniformly before). Assuming only social value, the pairwise stable set includes many nonstandard networks under high and particular combinations of complete components under low link specificity. Allowing for social and informational value reduces this set to certain fragmented networks under high and the complete network under low link specificity. These extremes are efficient, whereas intermediate link specificity generates inefficiency.     

One-way flow network formation under constraints

We study the effects of institutional constraints on stability and efficiency in the “one-way flow” model of network formation. In this model the information that flows through a link between two players runs only towards the player that initiates and supports the link, so in order for it to flow in both directions, both players must pay whatever the unit cost of a directional link is. We assume that an exogenous “societal cover” consisting of a collection of possibly overlapping subsets covering the set of players specifies the social organization in different groups or “societies,” so that a player may initiate links only with players that belong to at least one society that he/she also belongs to, thus restricting the feasible strategies and networks. In this setting, we examine the impact of such societal constraints on stable/efficient architectures and on dynamics.     

Percolation in the secrecy graph

The secrecy graph is a random geometric graph which is intended to model the connectivity of wireless networks under secrecy constraints. Directed edges in the graph are present whenever a node can talk to another node securely in the presence of eavesdroppers, which, in the model, is determined solely by the locations of the nodes and eavesdroppers. In the case of infinite networks, a critical parameter is the maximum density of eavesdroppers that can be accommodated while still guaranteeing an infinite component in the network, i.e., the percolation threshold. We focus on the case where the locations of the nodes and eavesdroppers are given by Poisson point processes, and present bounds for different types of percolation, including in-, out- and undirected percolation.     

On the rate allocation problem under co-existence of uncertain utility function parameters and uncertain link capacities

The allocation problem is considered for a computer communication network with network links being shared among multiple transmissions running at the same time. Typically, each transmission brings benefit to a network owner proportional to the transmission rate allowed. Since the link capacities are limited and the minimal rates defined by Quality of Service (QoS) requirements have to be preserved, the rate allocation problem is defined here as a problem of maximizing the overall benefit (utility) under capacity and QoS constraints. In this paper, we consider the uncertain version of the problem, in which unknown utility function parameters and unknown link capacities are treated as uncertain variables characterized by certainty distributions. We present a method for solving the problem in a unified way, with both uncertainties combined in a single certainty index.     

Efficient automatic simulation of parallel computation on networks of workstations

Andrews et al. [Automatic method for hiding latency in high bandwidth networks, in: Proceedings of the ACM Symposium on Theory of Computing, 1996, pp. 257-265; Improved methods for hiding latency in high bandwidth networks, in: Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, 1996, pp. 52-61] introduced a number of techniques for automatically hiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identical in computational power to those of the guest network being simulated. They further assume that the links of the host are able to pipeline messages, i.e., they are able to deliver P packets in time O(P+d) where d is the delay on the link.In this paper we examine the effect of eliminating one or both of these assumptions. In particular, we provide an efficient simulation of a linear array of homogeneous processors connected by unit-delay links on a linear array of heterogeneous processors connected by links with arbitrary delay. We show that the slowdown achieved by our simulation is optimal. We then consider the case of simulating cliques by cliques; i.e., a clique of heterogeneous processors with arbitrary delay links is used to simulate a clique of homogeneous processors with unit delay links. We reduce the slowdown from the obvious bound of the maximum delay link to the average of the link delays. In the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining.The main motivation of our results (as was the case with Andrews et al.) is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a network of workstations (NOW). In such a setting it is unlikely that the links provided by the NOW will support pipelining and it is quite probable the processors will be heterogeneous. Combining our result on clique simulation with well-known techniques for simulating shared memory PRAMs on distributed memory machines provides an effective automatic compilation of a PRAM algorithm on a NOW.     

MinMaxDM distributions for an analysis of the tensile strength of a unidirectional composite

An analysis of the tensile strength of some fiber or fiber bundle specimens is presented. The specimens are modeled as chains of links consisting of longitudinal elements (LEs) with different cumulative distribution functions of strength, corresponding to the presence and absence of defects. Each link is considered as a system of parallel LEs a part of which can have defects. In the simplest case, the strength of defective elements is assumed equal to zero. The strength of a link is determined by the maximum average stress the link can sustain under a growing load. To calculate the stress, the randomized Daniels model or the theory of Markov chains is used. The strength of specimens is determined by the minimum strength of links. The concept of MinMaxDM family of distribution functions is introduced. A numerical example of processing experimental results for a monolayer of carbon bundles is presented.     

A framework for user equilibrium dynamic traffic assignment

Several analytic approaches have been developed to describe or predict traffic flows on networks with time-varying (dynamic) travel demands, flows and travel times. A key component of these models lies in modelling the flows and/or travel times on the individual links, but as this is made more realistic or accurate it tends to make the overall model less computationally tractable. To help overcome this, and for other reasons, we develop a bi-level user equilibrium (UE) framework that separates the assignment or loading of flows on the time–space network from the modelling of flows and trip times within individual links. We show that this model or framework satisfies appropriate definitions of UE satisfies a first-in-first-out (FIFO) property of road traffic, and has other desirable properties. The model can be solved by iterating between (a) a linear network-loading model that takes the lengths of time–space links as fixed (within narrow ranges), and (b) a set of link flow sub-models which update the link trip times to construct a new time–space network. This allows links to be processed sequentially or in parallel and avoids having to enumerate paths and compute path flows or travel times. We test and demonstrate the model and algorithms using example networks and find that the algorithm converges quickly and the solutions behave as expected. We show how to extend the model to handle elastic demands, multiple destinations and multiple traffic types, and traffic spillback within links and from link to link.     

Exact approaches for solving robust prize-collecting Steiner tree problems

In the Prize-Collecting Steiner Tree Problem (PCStT) we are given a set of customers with potential revenues and a set of possible links connecting these customers with fixed installation costs. The goal is to decide which customers to connect into a tree structure so that the sum of the link costs plus the revenues of the customers that are left out is minimized. The problem, as well as some of its variants, is used to model a wide range of applications in telecommunications, gas distribution networks, protein–protein interaction networks, or image segmentation.     

Percolation of interdependent network of networks

Complex networks appear in almost every aspect of science and technology. Previous work in network theory has focused primarily on analyzing single networks that do not interact with other networks, despite the fact that many real-world networks interact with and depend on each other. Very recently an analytical framework for studying the percolation properties of interacting networks has been introduced. Here we review the analytical framework and the results for percolation laws for a Network Of Networks (NONs) formed by n interdependent random networks. The percolation properties of a network of networks differ greatly from those of single isolated networks. In particular, because the constituent networks of a NON are connected by node dependencies, a NON is subject to cascading failure. When there is strong interdependent coupling between networks, the percolation transition is discontinuous (first-order) phase transition, unlike the well-known continuous second-order transition in single isolated networks. Moreover, although networks with broader degree distributions, e.g., scale-free networks, are more robust when analyzed as single networks, they become more vulnerable in a NON. We also review the effect of space embedding on network vulnerability. It is shown that for spatially embedded networks any finite fraction of dependency nodes will lead to abrupt transition.     

Constructing banking networks under decreasing costs of link formation

The structure of networks plays a central role in the behavior of financial systems and their response to policy. Real-world networks, however, are rarely directly observable: banks’ assets and liabilities are typically known, but not who is lending how much and to whom. This paper adds to the existing literature in two ways. First, it shows how to simulate realistic networks that are based on balance-sheet information. To do so, we introduce a model where links cause fixed-costs, independent of contract size; but the costs per link decrease the more connected a bank is (scale economies). Second, to approach the optimization problem, we develop a new algorithm inspired by the transportation planning literature and research in stochastic search heuristics. Computational experiments find that the resulting networks are not only consistent with the balance sheets, but also resemble real-world financial networks in their density (which is sparse but not minimally dense) and in their core-periphery and disassortative structure.

     

Knots and the Bracket Calculus

In this paper, we introduce a way of encoding links (long links). This ways leads to a combinatorial representation of links by words in a given finite alphabet. We prove that the link semigroup is isomorphic to some algebraically defined semigroup with a simple system of relations. Thus, knot theory is represented as a bracket calculus: the link recognition problem is reduced to a recognition problem in this semigroup.     

Overlap functions

In this paper we address a key issue in scenario classification, where classifying concepts show a natural overlapping. In fact, overlapping needs to be evaluated whenever classes are not crisp, in order to be able to check if a certain classification structure fits reality and still can be useful for our declared decision making purposes. In this paper we address an object recognition problem, where the best classification with respect to background is the one with less overlapping between the class object and the class background. In particular, in this paper we present the basic properties that must be fulfilled by overlap functions, associated to the degree of overlapping between two classes. In order to define these overlap functions we take as reference properties like migrativity, homogeneity of order 1 and homogeneity of order 2. Hence we define overlap functions, proposing a construction method and analyzing the conditions ensuring that t-norms are overlap functions. In addition, we present a characterization of migrative and strict overlap functions by means of automorphisms.