Atomic routing games on maximum congestion

We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy  , PoA$PoA$, is determined by topological properties of the network. In particular, PoA=O(?+logn)$PoA=O(?+logn)$, where ?$?$ is the length of the longest path in the player strategy sets, and n$n$ is the size of the network. Further, κ−1≤PoA≤c(κ²+log²n)$\kappa -1\le PoA\le c({\kappa }^2+{log}^{2}n)$, where κ$\kappa$ is the length of the longest cycle in the network, and c$c$ is a constant.     

A new model for selfish routing

In this work, we introduce and study a new, potentially rich model for selfish routing over non-cooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, C.H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404–413] and the Wmodel [J.G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the of the Institute of Civil Engineers 1 (Pt. II) (1952) 325–378].     

An economic analysis of routing conflict and its resolution

Thousands of competing autonomous systems (ASes) must cooperate with each other to provide global Internet connectivity. Each AS has independent economic objectives and retains autonomy in setting their routing policies independently to maximize its profit. However, such autonomy enables ASes to produce conflicting routing polices and thus raises route oscillations between them (i.e., routing divergence). This paper studies the basic problem of routing divergence by investigating real ISP pricing data. We first demonstrate that routing divergences occur under economic dependency cycles, i.e., provider–customer cycles, of different ASes which are raised by economic conflicts between themselves. We then propose a provable cycle-breaking routing mechanism to detect and solve economic conflicts and route divergence. We show that every cycle-breaking strategy allows ASes to maximize their own profits to converge to a Nash equilibrium with a profit-sharing mechanism derived from the coalition game concept of Shapley value. At the Nash equilibrium point, the cycle-breaking strategies maximize ASes’ profits and encourage ASes so as to ensure divergence-free routing.     

On the implications of routing metric staleness in delay tolerant networks

Delay Tolerant Network (DTN) routing addresses challenges of providing end-to-end service where end-to-end data forwarding paths may not exist. The performance of current DTN routing protocols is often limited by routing metric “staleness”, i.e., routing information that becomes out-of-date or inaccurate because of long propagation delays. Our previous work, ParaNets, proposed a new opportunistic network architecture in which the data channel is augmented by a thin end-to-end control channel. The control channel is adequate for the exchange of control traffic, but not data. In this paper we present Cloud Routing, a routing solution for the ParaNets architecture. We motivate the need for such a solution, not only because of stale routing metrics, but also because of congestion that can occur in DTNs. Unable to use up-to-date routing metrics to limit congestion, existing DTN routing solutions suffer from low goodput and long data delivery delays. We show how Cloud Routing avoids congestion by smart use of forwarding opportunities based on up-to-date routing metrics. We evaluate our solution using extensive OPNET simulations. Cloud Routing extends network performance past what is currently possible and motivates a new class of globally cognizant DTN routing solutions.     

Non-cooperative routing in loss networks

The paper studies routing in loss networks in the framework of a non-cooperative game with selfish users. Two solution concepts are considered: the Nash equilibrium, corresponding to the case of a finite number of agents (such as service providers) that take routing decisions, and the Wardrop equilibrium, in which routing decisions are taken by a very large number of individual users. We show that these equilibria do not fall into the standard frameworks of non-cooperative routing games. As a result, we show that uniqueness of equilibria or even of utilizations at equilibria may fail even in the case of simple topology of parallel links. However, we show that some of the problems disappear in the case in which the bandwidth required by all connections is the same. For the special case of a parallel link topology, we obtain some surprisingly simple way of solving the equilibrium for both cases of Wardrop as well as Nash equilibrium.     

FIB Aplasia through probabilistic routing and autoforwarding

In this work, we propose Aplasia, an holistic architecture with a radical design. Aiming at simplifying the inner network devices (and so their cost), we tradeoff node architecture- and algorithmic-complexity for an increased (but tunable) communication cost. The main ingredients of our recipe are (i) the use of complete paths directly in the frames header, that allows core devices to perform data-plane switching functions without lookup and (ii) the use of a greedy probabilistic routing algorithm to quickly discover multiple, near optimal, paths in the control plane. We extensively simulate, analyze and implement our proposal to testify its soundness.     

An efficient Nash-implementation mechanism for network resource allocation

We propose a mechanism for auctioning bundles of multiple divisible goods in a network where buyers want the same amount of bandwidth on each link in their route. Buyers can specify multiple routes (corresponding to a source-destination pair). The total flow can then be split among these multiple routes. We first propose a one-sided VCG-type mechanism. Players do not report a full valuation function but only a two-dimensional bid signal: the maximum quantity that they want and the per-unit price they are willing to pay. The proposed mechanism is a weak Nash implementation, i.e., it has a non-unique Nash equilibrium that implements the social-welfare maximizing allocation. We show the existence of an efficient Nash equilibrium in the corresponding auction game, though there may exist other Nash equilibria that are not efficient. We then generalize this to arbitrary bundles of various goods. Each buyer submits a bid separately for each good but their utility function is a general function of allocations of bundles of various divisible goods. We then present a double-sided auction mechanism for multiple divisible goods. We show that there exists a Nash equilibrium of this auction game which yields the efficient allocation with strong budget balance.     

Equilibrium Values in a Competitive Power Exchange Market

We consider an open electricity market with demand uncertainty.In this market, the generators each decide on a bidding price tomaximize profit. Units are dispatched in order of the bid from lowestto highest until demand is satisfied. The market clearing price isthe highest bid among the dispatched units.All dispatched units are then sold at this market clearing price.Under a market stability assumption, we derive Nashequilibrium solutions, i.e., bidders' optimal bidding strategiesand the resulting market clearing price.     

Energy-aware routing in the Cognitive Packet Network

An energy aware routing protocol (EARP) is proposed to minimise a performance metric that combines the total consumed power in the network and the QoS that is specified for the flows. The algorithm uses source routing based on the functionalities provided by the Cognitive Packet Network (CPN), running autonomously at each input node to the network based on smart packets which gather relevant information throughout the network using reinforcement learning at each of the intermediate nodes. Measurements on an experimental test-bed that uses EARP are presented and they indicate that it offers a reduction in power consumption, as compared to a purely QoS driven approach, and also respects the requested QoS level.     

Multicommodity flows over time: Efficient algorithms and complexity

Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g. the Internet) and financial flows. The common characteristic are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. Moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks.     

Two-terminal routing games with unknown active players

We analyze 2-terminal routing games with linear cost functions and with unknown number of active players. We deal with both splittable and unsplittable models. We prove the existence and uniqueness of a symmetric safety-level equilibrium in such games and show that in many cases every player benefits from the common ignorance about the number of players. Furthermore, we prove new theorems on existence and uniqueness of equilibrium in 2-terminal convex routing games with complete information.     

An optimal time bound for oblivious routing

The problem of routing data packets in a constant-degree network is considered. A routing scheme is calledoblivious if the route taken by each packet is uniquely determined by its source and destination. The time required for the oblivious routing ofn packets onn processors is known to be (n). It is demonstrated that the presence of extra processors can expedite oblivious routing. More specifically, the time required for the oblivious routing ofn packets onp processors is (n/p + logn).     

A competitive neural network algorithm for solving vehicle routing problem

This paper describes a self organization Neural Network algorithm for a class of Vehicle Routing Problems. Motivated by the outstanding performance of adaptive Neural Network approach in the Traveling Salesman Problem, we devised an algorithm to extend the domain of applicability of this approach to more complex problems. First, relevant adaptation is proposed to refine the model for the Multiple Traveling Salesman Problem. Then, an additional mechanism to satisfy further constraints are embodied into the algorithm. The effectiveness of the proposed algorithm is evaluated by considering a series of standard problems from the literature. The results show that the algorithm can yield solutions within a few percent of optimality.     

An ant colony optimization routing algorithm for two order pickers with congestion consideration

This paper develops a routing method to control the picker congestion that challenges the traditional assumption regarding the narrow-aisle order picking system. We proposes a new routing algorithm based on Ant Colony Optimization (ACO) for two order pickers (A-TOP) with congestion consideration. Using two extended dedicated heuristics with congestion consideration as reference group, a comprehensive simulation study is conducted to evaluate the effectiveness of A-TOP. The simulation proves that A-TOP achieves the shortest total picking time in most instances and performs well in dealing with the congestion. The impacts of warehouse layout, order size, and pick:walk-time ratio on A-TOP and system performance are analyzed as well. A-TOP can adapt to different warehouse configurations, meanwhile, it can be easily extended to the situation with more than two order pickers.     

基于博弈论的无线传感器网络簇间路由选择算法

针对无线传感器网络(WSN)中,网络覆盖范围大,但传感器节点通信范围有限,长距离传输容易造成数据丢失的问题,提出了一种基于博弈论的无线传感器网络簇间路由算法,通过建立以网络服务质量(QoS)和节点剩余能量为效用函数的博弈模型,并求解其纳什均衡来解决以上问题。仿真结果表明：所提出的博弈模型在优化网络服务质量、降低节点能耗的同时,延长了整个网络的生存时间。     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

The structure and complexity of Nash equilibria for a selfish routing game

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m$m$ parallel links. We assume a collection of n$n$ users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. In a Nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.     

Competitive equilibrium in e-commerce: Pricing and outsourcing

The success of firms engaged in e-commerce depends on their ability to understand and exploit the dynamics of the market. One component of this is the ability to extract maximum profit and minimize costs in the face of the harsh competition that the internet provides. We present a general framework for modeling the competitive equilibrium across two firms, or across a firm and the market as a whole. Within this framework, we study pricing choices and analyze the decision to outsource IT capability. Our framework is novel in that it allows for any number of distributions on usage levels, price–QoS tradeoffs, and price and cost structures.     

无线传感网协作能量感知路由方法*

将多跳分集引入无线传感网中以节能,提出协作能量感知路由方法（CEAR：Cooperative Energy Aware Routing）。协作能量感知路由方法利用多跳分集方法对无线传感网经典的能量感知路由（EAR: Energy Aware Routing）方法加以改进。分析了多跳分集方法中各跳的总能耗,并基于能耗分析结果设计协作能量感知路由方法。仿真结果表明,相比于能量感知路由方法,协作能量感知路由方法有更好的节能性能。     

一种集成免疫进化算法及其收敛性研究

文章首先总结了传统进化计算和标准遗传算法的缺陷,介绍了免疫系统的多种处理机制,提出了其对于进化计算的可借鉴意义,并分析了现有的免疫遗传算法。然后集成免疫记忆和免疫调节理论提出了一种新的免疫进化算法I-IEA,给出了算法描述及其运算机理,并利用马尔柯夫链证明了其收敛性和收敛速度。最后结合NFL定理,展望了免疫算法的适用性和发展潜力。