Designing Least-Cost Nonblocking Broadband Networks

Integrated network technologies, such as ATM, support multimedia applications with vastly different bandwidth needs, connection request rates, and holding patterns. Due to their high level of flexibility and communication rates approaching several gigabits per second, the classical network planning techniques, which rely heavily on statistical analysis, are less relevant to this new generation of networks. In this paper, we propose a new model for broadband networks and investigate the question of their optimal topology from a worst-case performance point of view. Our model is more flexible and realistic than others in the literature, and our worst-case bounds are among the first in this area. Our results include a proof of intractability for some simple versions of the network design problem and efficient approximation algorithms for designing nonblocking networks of provably small cost. More specifically, assuming some mild global traffic constraints, we show that a minimum-cost nonblockingstarnetwork achieves near-optimal cost; the cost ratio is at most 2 if switch source and sink capacities are symmetric and at most 3 when the total source and sink capacities are balanced. In the special case of unit link costs, we can show that a star network is indeed the cheapest nonblocking network.     

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.     

A robust optimization approach for multicast network coding under uncertain link costs

Network coding is a technique that can be used to improve the performance of communication networks by performing mathematical operations at intermediate nodes. An important problem in coding theory is that of finding an optimal coding subgraph for delivering network data from a source node throughout intermediate nodes to a set of destination nodes with the minimum transmission cost. However, in many real applications, it can be difficult to determine exact values or specific probability distributions of link costs. Establishing minimum-cost multicast connections based on erroneous link costs might exhibit poor performance when implemented. This paper considers the problem of minimum-cost multicast using network coding under uncertain link costs. We propose a robust optimization approach to obtain solutions that protect the system against the worst-case value of the uncertainty in a prespecified set. The simulation results show that a robust solution provides significant improvement in worst-case performance while incurring a small loss in optimality for specific instances of the uncertainty.     

Equilibrium selection and altruistic behavior in noncooperative social networks

Given their importance in determining the outcome of many economic interactions, different models have been proposed to determine how social networks form and which structures are stable. In Bala and Goyal (Econometrica 68, 1181–1229, 2000), the one-sided link formation model has been considered, which is based on a noncooperative game of network formation. They found that the empty networks, the wheel in the one-way flow of benefits case and the center-sponsored star in the two-way flow case play a fundamental role since they are strict Nash equilibria of the corresponding games for a certain class of payoff functions. In this paper, we first prove that all these network structures are in weakly dominated strategies whenever there are no strict Nash equilibria. Then, we exhibit a more accurate selection device between these network architectures by considering “altruistic behavior” refinements. Such refinements that we investigate here in the framework of finite strategy sets games have been introduced by the authors in previous papers.     

基于FDI收益分成视角的FTA网络演化

本文假定双边自由贸易协定(bilateral free trade agreement,简称FTA)包含着无限制对外直接投资(foreign direct investment,简称FDI),并且通过FDI销售到非FTA伙伴国的收益按照一定比例在母国和东道国之间进行分配。基于Goyal和Joshi^[1],本文构建了FTA网络形成博弈模型。本文发现,FTA网络演化过程分为两个阶段:第一阶段,从空FTA网络到星状FTA网络,存在一条路径使得个体国家福利、世界总福利均改善,在此过程中,国家福利存在不对称性;第二阶段,从星状FTA网络到全连接FTA网络,存在一条路径使得个体国家福利改善,在此过程中,世界总福利不变,国家福利不对称性逐步消除。     

On the stability of the incomplete LU-factorizations and characterizations of H-matrices

Summary. Meijerink and van der Vorst [8] have shown that the incomplete LU-factorizations are numerically stable for M-matrices. Varga, Saff and Mehrmann [16] gave some characterizations of the H-matrices by using the incomplete LU-factorizations of them. The purpose of this paper is to show that the incomplete LU-factorizations of an H-matrix are at least as stable as the complete LU-factorizations of its comparison matrix. We give also some new characterizations of the H-matrices in connection with their incomplete LU-factorizations. Received November 12, 1993 / Revised version received May 27, 1994     

Efficiency and Stability in a Discrete Model of Country Formation

This paper studies efficient and stable country configurations in a simple model of country formation. Driving force of the model is a trade-off between the benefits of large countries and the costs of heterogeneity of large and diverse populations. We show that efficient configurations as well as stable configurations exist for each value of the model parameter; however, there is no unambiguous relation between them. Moreover, country sizes in efficient configurations may differ by at most two, while in stable configurations the differences in their sizes may be relatively high. Our results contrast with those of Alesina and Spolaore (1997).     

Hop Constrained Network Design Problem with Partial Survivability

This paper studies the hop constrained network design problem with partial survivability, namely, given an undirected network, a set of point-to-point demands (commodities), and transmission link costs, identify two node disjoint paths for each demand (commodity) to minimize the total costs subject to the constraints that each demand is routed and traverses at most a specified number of links (or hops) on both the paths.A mathematical programming formulation of the problem is presented and an efficient solution procedure based on the linear programming relaxation is developed. Extensive computational results across a number of networks are reported. These results indicate that the solution procedure is effective for a wide range of problem sizes.     

Co-authorship model with link strength

We generalize a network formation model for co-authorship introducing the possibility of the connections having different link strengths. Different link strengths represent the fact that authors may put different efforts into different collaborations. To evaluate the model, we consider the notions of efficiency and pairwise stability, which are based on a utility function that measures the benefits for an author to belonging to a certain network structure. We divide the analysis in two cases, considering that link strengths are unbounded or bounded. In the first case, we show that if there are more than two authors in the network, then there is no pairwise stable network. In the second case, we show that the pairwise stable networks consist of completely connected disjoint components where essentially all link strengths are maximal. Regarding efficiency, in both cases, if the number of authors is even, then the unique efficient network structure consists of pairs of connected authors.     

Contractually stable networks

We consider situations where players are part of a network and belong to coalitions in a given coalition structure. We propose the concept of contractual stability to predict the networks that are going to emerge at equilibrium when the consent of coalition partners is needed for adding or deleting links. Two different decision rules for consent are analyzed: simple majority and unanimity. We characterize the coalition structures that make the strongly efficient network contractually stable under the unanimity decision rule and the coalition structures that sustain some critical network as contractually stable under the simple majority decision rule and under any decision rule requiring the consent of any proportion of coalition partners. Requiring the consent of coalition members may help to reconcile stability and efficiency in some classical models of network formation.     

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.     

Impact of compressor failures on gas transmission network capability

National Grid, the gas operator in the United Kingdom, has experienced challenges in evaluating the capability of its gas transmission network to maintain function in the event of risks particularly to withstand the impact of compressor failures. We propose a mathematical programming model to support the operator in dealing with the problem. Several solution techniques are developed to solve the various versions of the problem efficiently. In the case of little data on compressor failure, an uncertainty theory is applied to solve this problem if the compressor failures are independent; while a robust optimisation technique is developed to solve it when they are not. Otherwise, when there are data on compressor failure, Monte Carlo simulation is applied to find the expected capability of the gas transmission network. Computational experiments, carried out on a case study at National Grid, demonstrate the efficiency of the proposed model and solution techniques. A further analysis is performed to determine the impact of compressor failures and suggest efficient maintenance policies for National Grid.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.     

Proprietor and customer costs in the incomplete hub location-routing network topology

The hub location problem finds the location of hubs and allocates the other nodes to them. It is widely supposed the network created with the hub nodes is complete in the extensive literature. Relaxation of this basic supposition forms the present work. The model minimizes the cost of the proprietor, including the fixed costs of hubs, hub links and spoke links. Costs of hub and spoke links are contemplated as fixed cost or maintenance cost. Moreover, the model considers routing costs of customers who want to travel from origins to destinations. In this study, we offer a model to the multiple allocations of the hub location problems, under the incomplete hub location-routing network design. This model is easily transformed to other hub location problems using one or more constraints. No network format is dictated on the hub network. We suggest a set of valid inequalities for the formulation. Some lower bounds are developed using a Lagrangian relaxation approach and the valid inequalities. Computational analyses evaluate the performances of the lower bounding implementations and valid inequalities. Furthermore, we explore the effects of several factors on the design and solution time of the problem formulation.     

New formulations and solution procedures for the hop constrained network design problem

Optical fiber provides tremendous advantages in being able to carry a wide range of services including video on demand, video conferencing, distance learning, remote medical imaging, and telecommuting. The high capacities encourage carriers to create networks that are substantially sparser than previous copper based networks. A recent publication by the Telecommunications Industry Association indicated that investment in fiber optics is projected to reach $35 billion in the year 2003. Given the magnitude of investments, the design of networks becomes a very important issue. Most telecommunication companies (telcos), IT consulting companies, network equipment manufacturers and network service providers have extensive network design groups. The primary function of these groups is to design the most efficient networks both in terms of costs and performance and maintain them. These designers need flexible tools to support topological network design decisions. These decisions involve significant levels of investments in transmissions and switching facilities, and impact the resulting networks’ performance fundamentally.In this paper we study a special type of a network design problem called the hop constrained backbone network design problem. We present new mathematical programming formulations of the problem and develop an efficient solution procedure based on the linear programming relaxation. Extensive computational results across a number of networks are reported.     

Global dynamical analysis of a heroin epidemic model on complex networks

In this paper, a heroin epidemic model on complex networks is proposed. By the next generation matrix, the basic reproduction number $R_0$ is obtained. If $R_0<1$, then the drug-free equilibrium is globally asymptotically stable. If $R_0>1$, there is an unique endemic equilibrium and it is also globally asymptotically stable. Our results show that if the degree of the network is large enough, the drug transmission always spreads. Sensitivity analysis of the basic reproduction number with the various parameters in the model are carried out to verify the important effects for control the drug transmission. Some simulations illustrate our theoretical results     

Bargaining in endogenous trading networks

We study a model in which heterogeneous agents first form a trading network where linking costs are positive but infinitesimally small. Then, a seller and a buyer are randomly selected among the agents to bargain through a chain of intermediaries. We determine both the trading path and the allocation of the surplus among the seller, the buyer and the intermediaries at equilibrium. We show that, under the initiator bargaining protocol, a trading network is pairwise stable if it is a core–periphery network where the core consists of all impatient agents who are linked to each other and the periphery consists of all patient agents who have a single link towards an impatient agent. Once agents do not know the impatience of other agents, each bilateral bargaining session may involve delay. Then, core–periphery networks may not be pairwise stable because agents may prefer to add links for reducing the length of trading paths and so avoiding costly delays in reaching a global agreement.     

Farsighted free trade networks

The paper examines whether bilateral free trade agreements can lead to global free trade. We reconsider the endogenous tariff model introduced by Goyal and Joshi (2006) who study pairwise stability of free trade networks. We depart from their analysis by adopting the concept of pairwise farsightedly stable networks (Herings et al. 2009, GEB). We show that the complete network (i.e., global free trade) constitutes a pairwise farsightedly stable set. In particular, there is a farsightedly improving path from the empty network (i.e., no free trade agreement in place) to the complete network, which involves link additions only, while farsightedly improving paths from preexisting free trade networks may involve link deletion (i.e., dissolution of some bilateral FTAs). Moreover, we show that pairwise farsightedly stable set of networks is not unique. One implication of our results is that bilateral trade negotiations, if properly channeled, can lead to global free trade, although some bilateral agreements may have to be dissolved first to pave the way towards global free trade.     

Partition inequalities for capacitated survivable network design based on directed p-cycles

We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the p-cycles.

We describe a model for designing capacitated survivable networks based on directed p-cycles. We motivate this model by comparing it with other means of ensuring survivability, and present a mixed-integer programming formulation for it. We derive valid inequalities for the model based on the minimum capacity requirement between partitions of the nodes and give facet conditions for them. We discuss the separation for these inequalities and present results of computational experiments for testing their effectiveness as cutting planes when incorporated in a branch-and-cut algorithm. Our experiments show that the proposed inequalities reduce the computational effort significantly.     

Parallel cleaning of a network with brushes

We consider the process of cleaning a network where at each time step, all vertices that have at least as many brushes as incident, contaminated edges, send brushes down these edges and remove them from the network. An added condition is that, because of the contamination model used, the final configuration must be the initial configuration of another cleaning of the network. We find the minimum number of brushes required for trees, cycles, complete bipartite networks; and for all networks when all edges must be cleaned on each step. Finally, we give bounds on the number of brushes required for complete networks.