Optimal static pricing for a tree network

We study the static pricing problem for a network service provider in a loss system with a tree structure. In the network, multiple classes share a common inbound link and then have dedicated outbound links. The motivation is from a company that sells phone cards and needs to price calls to different destinations. We characterize the optimal static prices in order to maximize the steady-state revenue. We report new structural findings as well as alternative proofs for some known results. We compare the optimal static prices versus prices that are asymptotically optimal, and through a set of illustrative numerical examples we show that in certain cases the loss in revenue can be significant. Finally, we show that static prices obtained using the reduced load approximation of the blocking probabilities can be easily obtained and have near-optimal performance, which makes them more attractive for applications.     

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.     

Topological design of wide area communication networks

This paper develops a model for designing a backbone network. It assumes the location of the backbone nodes, the traffic between the backbone nodes and the link capacities are given. It determines the links to be included in the design and the routes used by the origin destination pairs. The objective is to obtain the least cost design where the system costs consist of connection costs and queueing costs. The connection costs depend on link capacity and queueing costs are incurred by users due to the limited capacity of links. The Lagrangian relaxation embedded in a subgradient optimization procedure is used to obtain lower bounds on the optimal solution of the problem. A heuristic based on the Lagrangian relaxation is developed to generate feasible solutions.     

On-line routing of random calls in networks

 We consider a random sequence of calls between nodes in a complete network with link capacities. Each call first tries the direct link. If that link is saturated, then the `first-fit dynamic alternative routing algorithm' sequentially selects up to d random two-link alternative routes, and assigns the call to the first route with spare capacity on each link, if there is such a route. The `balanced dynamic alternative routing algorithm' simultaneously selects d random two-link alternative routes; and the call is accepted on a route minimising the maximum of the loads on its two links, provided neither of these two links is saturated. We determine the capacities needed for these algorithms to route calls successfully, and find that the second `balanced' algorithm requires a much smaller capacity. Our results strengthen and extend the discrete-time results presented in [10]. Received: 10 January 2002 / Revised version: 7 July 2002 / Published online: 28 March 2003     

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.     

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.     

Computing approximate Nash equilibria in general network revenue management games

Computing optimal capacity allocations in network revenue management is computationally hard. The problem of computing exact Nash equilibria in non-zero-sum games is computationally hard, too. We present a fast heuristic that, in case it cannot converge to an exact Nash equilibrium, computes an approximation to it in general network revenue management problems under competition. We also investigate the question whether it is worth taking competition into account when making (network) capacity allocation decisions. Computational results show that the payoffs in the approximate equilibria are very close to those in exact ones. Taking competition into account never leads to a lower revenue than ignoring competition, no matter what the competitor does. Since we apply linear continuous models, computation time is very short.     

Telecommunication Network Capacity Design for Uncertain Demand

The expansion of telecommunication services has increased the number of users sharing network resources. When a given service is highly demanded, some demands may be unmet due to the limited capacity of the network links. Moreover, for such demands, telecommunication operators should pay penalty costs. To avoid rejecting demands, we can install more capacities in the existing network. In this paper we report experiments on the network capacity design for uncertain demand in telecommunication networks with integer link capacities. We use Poisson demands with bandwidths given by normal or log-normal distribution functions. The expectation function is evaluated using a predetermined set of realizations of the random parameter. We model this problem as a two-stage mixed integer program, which is solved using a stochastic subgradient procedure, the Barahona's volume approach and the Benders decomposition.     

The Problem of Capacity Addition in Multi-user Elastic Demand Communication Networks

In this paper we consider some properties on prices under flow control in a network that is to be shared by noncooperative users. Each user is faced with an optimization problem which is formulated as the minimization of its own criterion subject to constraint on the flows of the other users. The operating points of the network are the Nash equilibria of the underlying routing game. Our objective is to study the behavior of prices of all users when the network designer needs to allocate capacities to network links. For parallel links topologies, we show that degradation of the performances such as prices will not take place, as well as the users may find it beneficial to improve their requests     

Parametric controllability of certain systems of rigid bodies

The concept of parametric controllability as applied to systems of rigid bodies is discussed. The topic of discussion is Langrangian systems for which “unfreezing” of the parameters is possible such as, for example, the refinement of a model by taking account of the small variability of the links assumed by rigid bodies in the first approximation. As has been shown, just taking account of a small change in the parameters can ensure the controllability of a mechanism which was not controllable assuming rigidity absolute of the links. Certain sufficient conditions are proposed for parametric controllability in invariant manifolds for objects with cyclic coordinates. A two-link pendulum in the horizontal plane under the action of an internal moment (from the first link to the second) is considered as an example. The effect of its mass inertial parameters on the controllability is investigated. The parametric controllability of such an object in a manifold of zero angular momentum, due to the elastic pliability of the second link or the oscillations of an additional mass on a spring along the second link, is demonstrated. An example of a parametrically controllable planetary mechanism with slippage of discs is also considered.     

Min-max vs. max-min flow control algorithms for optimal computer network capacity assignment

The theory for optimally assigning capacities to the links of a store forward computer communication network is developed by the minimization of the maximum of two groupings of all link capacities previously assigned to the network. The MIN-MAX and MAX-MIN Algorithms developed have both local and global properties. The basic mathematical structure of the local section of the MIN-MAX Algorithm is derived from the Lagrange Multiplier technique for minimizing convex functions, or the Kuhn-Tucker method for constrained minimization solutions, and the constraints imposed by the functional structure definitions. Since the MIN-MAX Algorithm attains the optimal minimized delay assignment by minimization of the Min-Max assignment, the aspects of its relation to the MAX-MIN Algorithms, the Min-Max inequality and the of both algorithms offers an option for considering all possible, allowed link assignment combinations (2ⁿ - 2) of the n capacities available to further minimize delay.     

A Stackelberg Network Game with a Large Number of Followers

We consider a hierarchical network game with multiple links, a single service provider, and a large number of users with multiple classes, where different classes of users enter the network and exit it at different nodes. Each user is charged by the service provider a fixed price per unit of bandwidth used on each link in its route, and chooses the level of its flow by maximizing an objective function that shows a tradeoff between the disutility of the payment to the service provider and congestion cost on the link the user uses, and the utility of its flow. The service provider, on the other hand, wishes to maximize the total revenue it collects. We formulate this problem as a leader-follower (Stackelberg) game, with a single leader (the service provider, who sets the price) and a large number of Nash followers (the users, who decide on their flow rates). We show that the game admits a unique equilibrium, and obtain the solution in analytic form. A detailed study of the limiting case where the number of followers is large reveals a number of interesting and intuitive properties of the equilibrium, and answers the question of whether and when the service provider has the incentive to add additional capacity to the network in response to an increase in the number of users on a particular link.     

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.     

Supply chain network capacity competition with outsourcing: a variational equilibrium framework

This paper develops a supply chain network game theory framework with multiple manufacturers/producers, with multiple manufacturing plants, who own distribution centers and distribute their products, which are distinguished by brands, to demand markets, while maximizing profits and competing noncooperatively. The manufacturers also may avail themselves of external distribution centers for storing their products and freight service provision. The manufacturers have capacities associated with their supply chain network links and the external distribution centers also have capacitated storage and distribution capacities for their links, which are shared among the manufacturers and competed for. We utilize a special case of the Generalized Nash Equilibrium problem, known as a variational equilibrium, in order to formulate and solve the problem. A case study on apple farmers in Massachusetts is provided with various scenarios, including a supply chain disruption, to illustrate the modeling and methodological framework as well as the potential benefits of outsourcing in this sector.     

Inferring missing links in partially observed social networks

Determining the pattern of links within a large social network is often problematic due to the labour-intensive nature of the data collection and analysis process. With constrained data collection capabilities it is often only possible to either make detailed observations of a limited number of individuals in the network, or to make fewer observations of a larger number of people. Previously we have shown how detailed observation of a small network can be used, which infer where in the network previously unconnected individuals are likely to fit, thereby attempting to predict network growth as new people are considered for inclusion. Here, by contrast, we show how social network topology can be inferred following a limited observation of a large network. Essentially the issue is one of inferring the presence of links that are missed during a constrained data collection campaign on the network. It is particularly difficult to infer network structures for those organizations that actively seek to remain covert and undetected. However, it is often very useful to know if two given individuals are likely to be connected even though limited surveillance effort yields no evidence of a link. Specifically, we show how a statistical inference technique can be used to successfully predict the existence of links that are missed during network sampling. The procedure is demonstrated using network data obtained from open source publications.     

Supply chain network competition among blood service organizations: a Generalized Nash Equilibrium framework

In this paper we present a Generalized Nash Equilibrium model of supply chain network competition among blood service organizations which compete not only for blood donors but also for business from hospitals and medical centers. The model incorporates not only link capacities and associated arc multipliers to capture perishability, but also bounds on the number of donors in regions as well as lower and upper bounds on the demands at the demand points in order to ensure needed amounts for surgeries, treatments, etc., while reducing wastage. The concept of a variational equilibrium is utilized to transform the problem into a variational inequality problem, and alternative formulations are given. A Lagrange analysis yields economic insights. The proposed algorithmic procedure is then applied to a series of numerical examples in order to illustrate the impacts of disruptions in the form of a reduction on the number of donors as well as that of decreases in capacities of critical links such as testing and processing on RBC prices, demands, net revenues of the blood service organizations, and their overall utilities.

     

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.     

Reroute sequence planning in telecommunication networks and compact vector summation

The paper deals with the reroute sequence planning in telecommunication networks. Initially, we are given communication requests between terminal pairs and a path system which is able to satisfy these demands while respecting the physical link capacities. A reconfiguration problem arises when the path set is recalculated by a global optimization method for achieving a better resource utilization. After the recalculation the paths in the routing have to be changed to the optimized ones in the working network. In this case, a sequence of one by one reroutings have to be found with the constraint that the capacities should not be violated and no one of the demands can become unsatisfied during the reroute process. Provided that the (initial and final) free capacities are large enough, such a permutation can be computed. The paper deals with theoretical results giving bounds for these free capacities, with vector-sum and discrepancy methods.     

Collective Intelligence and its Implementation on the Web: Algorithms to Develop a Collective Mental Map

Collective intelligence is defined as the ability of a group to solve more problems than its individual members. It is argued that the obstacles created by individual cognitive limits and the difficulty of coordination can be overcome by using a collective mental map (CMM). A CMM is defined as an external memory with shared read/write access, that represents problem states, actions and preferences for actions. It can be formalized as a weighted, directed graph. The creation of a network of pheromone trails by ant colonies points us to some basic mechanisms of CMM development: averaging of individual preferences, amplification of weak links by positive feedback, and integration of specialised subnetworks through division of labor. Similar mechanisms can be used to transform the World-Wide Web into a CMM, by supplementing it with weighted links. Two types of algorithms are explored: 1) the co-occurrence of links in web pages or user selections can be used to compute a matrix of link strengths, thus generalizing the technique of &201C;collaborative filtering&201D;; 2) learning web rules extract information from a user&2018;s sequential path through the web in order to change link strengths and create new links. The resulting weighted web can be used to facilitate problem-solving by suggesting related links to the user, or, more powerfully, by supporting a software agent that discovers relevant documents through spreading activation.