Catálogo de publicaciones - libros

In shortest path routing, traffic is routed along shortest paths defined by link weights. However, not all path systems are feasible in that they can be realized in this way. This is something which needs to be taken into account when searching for a set of paths that minimize capacity consumption.

In this paper, we discuss a new necessary condition that can be used during search to prune infeasible path systems. The condition can be expressed using linear inequalities, or used in constraint programming, where its simple definition is convenient for the efficient implementation of propagation. Experiments on networks from the SNDLib benchmark show that this condition has strong pruning capabilities.

This paper discusses an optimization-based approach for congestion control together with multipath routing in a TCP/IP network. In recent research we have shown how natural optimization problems for resource allocation can be solved in decentralized way across a network, by traffic sources adapting their rates and routers adapting their traffic splits, all using a common congestion measure. We present here a concrete implementation of such algorithms, based on queueing delay as congestion price. We use TCP-FAST for congestion control, and develop a multipath variant of the distance vector routing protocol RIP. We demonstrate through ns2-simulations the collective behavior of the system, in particular that it reaches the higher transfer rates available through multiple routes.

In this paper we show how dynamic brokering for batch allocation in grids based on bi-dimensional indices can be used in practice in computational grids, with or without knowing the sizes of the jobs. We provide a fast algorithm (with a quadratic complexity) which can be used off-line or even on-line to compute the index tables. We also report numerous simulations providing numerical evidence of the great efficiency of our index routing policy as well as its robustness with respect to parameter changes. The value of information is also assessed by comparing the performance of indexes when the sizes of the jobs are known and when they are not known.

Recently Gerald Ash has shown through case studies that event dependent routing is attractive in large scale multi-service MPLS networks. In this paper, we consider the application of Load Shared Sequential Routing (LSSR) in MPLS networks where the load sharing factors are updated using reinforcement learning techniques. We present algorithms based on learning automata techniques for optimizing the load sharing factors both from the user equilibrium and system optimum perspectives. To overcome the computationally expensive gradient evaluation associated with the Kuhn-Tucker conditions of the system optimum problem, we derive a computationally efficient method employing shadow prices. The proposed method for calculating the user equilibrium solution represents a computationally efficient alternative to discrete event simulation. Numerical results are presented for the performance comparison of the LSSR model with the user equilibrium and the system optimum load sharing factors in some example network topologies and traffic demands.

In this paper we introduce a pricing scheme to be employed between a group of Internet service providers (ISPs) and a customer who wishes to initiate a packet flow from a fixed origin to a fixed destination. The ISPs are transparent to the customer who relies on a third party company for both the choice of the relevant ISPs and the unit flow price negotiated. The customer pays only for that portion of the traffic, which meets a predefined maximum tolerable total delay within the ISP networks. After taking in a fixed percentage of total profit, the third party redistributes the remaining benefits to the ISPs according to a sharing mechanism, which reflects both, the QoS the ISPs declare they will meet, as well as their real performance. The pricing emerges as the result of a Stackelberg game with the third party as the leader and the ISPs as the followers.

Agents competing in a network game typically prefer the least expensive route to their destinations. However, identifying such a route can be difficult when faced with uncertain cost estimates. We introduce a novel solution concept called (RWE) that takes into account these uncertainties. Our approach, which generalizes the traditional Wardrop equilibrium, considers that each agent uses distribution-free robust optimization to take the uncertainty into account. By presenting a nonlinear complementary problem that captures this user behavior, we show that RWE always exist and provide an efficient algorithm based on column generation to compute them. In addition, we present computational results that indicate that RWE are more stable than their nominal counterparts because they reduce the regret experienced by agents.

Using the inherent relation between price and demand, a usage-based pricing mechanism can be an efficient tool for controlling the usage of scarce resource like bandwidth in access networks and wireless communication, where there is big competition between users. I propose here to describe my contributions in this field of network pricing and particularly dealing with hierarchical game. This kind of multi-level game is well adapted for optimizing the system manager’s decision taking into account the follower game between users. We propose the use of hierarchical games for studying different networking scenarios : optimal scheduling in a DiffServ router and uplink transmissions in a CDMA cell.

We present both a game theoretic and a distributed algorithmic approach for the transit price negotiation problem in the interdomain routing framework. The analysis of the centralized transit price negotiation problem shows that the only one non cooperative equilibrium is when the lowest cost provider takes all the market. The perspective of the game being repeated makes cooperation possible while maintaining higher prices. We consider then the system under a realistic distributed framework and simulate its behaviour under a simple price adjustment strategy and analyse whether it matches the theoretical results.

The paper focuses on the problem of minimisation of energy consumption by wireless devices. Since wireless communications are some of the main causes of battery drainage, connections must be carefully established. We study complexity issues of the so called Cost Minimisation in Multi-Interface Networks problem. Given a graph  = (,) with || =  and || = , which models a set of wireless devices (nodes ) connected by multiple radio interfaces (edges ), the aim is to switch on the minimum cost set of interfaces at the nodes in order to satisfy all the connections. Every node holds a subset of all the possible interfaces. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. We distinguish two main variations of the problem by treating the cost of maintaining an active interface as uniform (i.e., the same for all interfaces), or non-uniform. In general, we show that the problem is -hard while we obtain an approximation factor of for the uniform case and a ( − 1)-approximation for the non-uniform case. Next, we concentrate our attention on several classes of networks: with bounded degree, planar, with bounded treewidth and complete.

In this paper we study a pursuit problem in the context of a wireless sensor network, where the pursuer (i.e., mobile sink) trying to capture a pursuee (i.e., tracked object), moving with constant velocity, is always directly communicating with a sensor node in the very near proximity of the pursuee. Assuming that the sensor nodes can adjust their transmission power depending on the distance between the pursuer and pursuee according to the usual power law , the task is to find the optimal trajectory of the pursuer minimizing the total transmission energy. We approach this classical control theoretic problem by the method of dynamic programming. The cost function, describing the transmission cost with an optimal policy, factorizes into radial and angular functions. The partial differential equation governing the cost function can then be reduced to an ordinary differential equation for the angular function. This equation as well as the related optimal trajectories can be solved numerically. The qualitative behavior of the trajectories is also discussed. The trajectories are self-similar in the sense that any magnification of an optimal trajectory is also an optimal trajectory for different initial conditions.