The authors consider a communication network shared by several selfish users. Each user seeks to optimize its own performance controlling the routing of given flow demand, giving rise noncooperative game. They investigate Nash equilibrium such systems. For two-node multiple links system, uniqueness is proven under reasonable convexity conditions. It shown that this point possesses interesting monotonicity properties. general networks, these conditions are not sufficient for guaranteeing...

In this paper the shortest-path problem in networks which delay (or weight) of edges changes with time according to arbitrary functions is considered. Algorithms for finding shortest path and minimum under various waiting constraints are presented properties derived investigated. It shown that if departure from source node unrestricted, then a can be found simple achieves as short most unrestricted path. case restricted transit, it there exist cases finite, but infinite.

This paper presents and discusses path selection algorithms to support QoS routes in IP networks. The work is carried out the context of extensions OSPF protocol, initial focus on unicast flows, although some proposed are also applicable multicast flows. We first review metrics required QoS, then present compare several algorithms, which represent different trade-offs between accuracy computational complexity. describe discuss associated link advertisement mechanisms, investigate options...

This paper investigates the problem of routing flows with quality-of-service (QoS) requirements through one or more networks, when information available for making such decisions is inaccurate. Inaccuracy in used computing QoS routes, e.g., network state as link and node metrics, arises naturally a number different environments that are reviewed paper. The goal to determine impact inaccuracy on ability path-selection process successfully identify paths adequate resources. In particular, we...

In noncooperative networks users make control decisions that optimize their individual performance objectives. Nash equilibria characterize the operating points of such networks. are generically inefficient and exhibit suboptimal network performance. Focusing on routing, a methodology is devised for overcoming this deficiency, through intervention manager. The manager controls part flow, aware behavior performs its routing aiming at improving overall system existence maximally efficient...

We investigate the problem of routing connections with QoS requirements across one or more networks, when information available for making decisions is inaccurate and expressed in some probabilistic manner. This uncertainty about actual state a node network arises naturally number different environments, that are reviewed paper. The main focus to determine impact such inaccuracies on path selection process, whose goal then identify most likely satisfy requirements.

In noncooperative networks users make control decisions that optimize their individual performance measure. Focusing on routing, two methodologies for architecting are devised, improve the overall network performance. These motivated by problem settings arising in provisioning and run time phases of network. For either phase, Nash equilibria characterize operating point The goal phase is to allocate link capacities lead systemwide efficient equilibria. solution such design problems is,...

We consider the problem of routing connections with quality service (QoS) requirements across networks when information available for making decisions is inaccurate. Such uncertainty about actual state a network component arises naturally in number different environments. The goal route selection process then to identify path that most likely satisfy QoS requirements. For end-to-end delay guarantees, this intractable. However, we show by decomposing constraint into local constraints,...

This paper provides an initial look at how support for advance reservations affects the complexity of path selection process in networks. Advance are likely to become increasingly important as networks and distributed applications functionally richer there have been a number previous works investigations that explored various related aspects. However, impact or on is topic has left largely untouched. investigates several service models reservations, which range from traditional basic model...

Unlike traditional routing schemes that route all traffic along a single path, multipath strategies split the among several paths in order to ease congestion. It has been widely recognized can be fundamentally more efficient than approach of paths. Yet, contrast single-path approach, most studies context focused on heuristic methods. We demonstrate significant advantage optimal (or near optimal) solutions. Hence, we investigate adopting rigorous (theoretical) approach. formalize problems...

We present dRMT (disaggregated Reconfigurable Match-Action Table), a new architecture for programmable switches. overcomes two important restrictions of RMT, the predominant pipeline-based switches: (1) table memory is local to an RMT pipeline stage, implying that not used by one stage cannot be reclaimed another, and (2) hardwired always sequentially execute matches followed actions as packets traverse stages. show these make it difficult programs efficiently on RMT.

We consider routing schemes for connections with end-to-end delay requirements, and investigate several fundamental problems. First, we focus on networks which employ rate-based schedulers and, hence, map guarantees into nodal rate guarantees, as done the guaranteed service class proposed Internet. first basic problem of identifying a feasible route connection, straightforward yet computationally costly solution exists. Accordingly, establish approximation that offer substantially lower...

The capacity allocation problem in a network that is to be shared by noncooperative users considered. Each user decides independently upon its routing strategy so as optimize individual performance objective. operating points of the are Nash equilibria underlying game,. designer aims allocate link capacities, resulting efficient, according some systemwide criterion. In general, solution such design problems complex and at times counterintuitive, since adding might lead degradation...

Abstract We investigate the minimum weight path problem in networks whose link weights and delays are both functions of time. demonstrate that, general, there exist cases which no finite is optimal leading us to define an infinite (naturally, containing loops) such a way that always has solution. also characterize structure path. In many practical cases, paths do exist. formulate criterion guarantees existence develop algorithm find Some special e.g., loopless paths, discussed.

The exponential growth of computer networking demands massive upgrades in the capacity existing networks. Traditional design methodologies, developed with single-class paradigm mind, overlook non-cooperative structure modern Consequently, such approaches entail danger degraded performance when resources are added to a network, phenomenon known as Braess paradox. present paper proposes methods for adding efficiently network general topology. It is shown that paradox avoided across rather than...

Security breaches and attacks are critical problems in today's networking. A key-point is that the security of each host depends not only on protection strategies it chooses to adopt but also those chosen by other hosts network. The spread Internet worms viruses one example. This class has two aspects. First, deals with epidemic processes, as such calls for employment theory. Second, distributed autonomous nature decision-making major classes networks (e.g., P2P, ad- hoc, most notably...

In this paper, we introduce and investigate a "new" path optimization problem that denote the all hops optimal (AHOP) problem. The involves identifying, for hop counts, optimal, i.e., minimum weight, path(s) between given source destination(s). AHOP arises naturally in context of quality-of-service (QoS) routing networks, where routes (paths) need to be computed provide services guarantees, e.g., delay or bandwidth, at possible "cost" (amount resources required) network. Because service...

We consider routing games where the performance of each user is dictated by worst (bottleneck) element it employs. are given a network, finitely many (selfish) users, associated with positive flow demand, and load-dependent function for network element; social (i.e., system) objective to optimize in bottleneck). Although we show that such "bottleneck" appear variety practical scenarios, they have not been considered yet. Accordingly, study their properties, considering two namely when can...

Precomputation-based methods have recently been proposed as an instrument to facilitate scalability, improve response time, and reduce computation load on network elements. The key idea is, in effect, the time needed handle event by performing some advance, i.e., prior event's arrival. Such computations are performed background processes, enabling a solution be provided promptly upon request, through simple, fast procedure. We investigate precomputation context of quality-of-service (QoS)...

We consider a multiuser network that is shared by noncooperative users. Each user sets up virtual paths optimize its own selfish performance measure. This measure accounts for the guaranteed call level quality of service, as well cost incurred reserving resource. The interaction among strategies formalized game. show game has unique Nash equilibrium and it possesses certain fairness property. investigate dynamics this prove convergence to both Gauss-Seidel scheme Jacobi scheme. extend our...

We investigate the problem of optimal resource allocation for end-to-end QoS requirements on unicast paths and multicast trees. Specifically, we consider a framework in which is based local at each network link, associated with link cost function that increases severity requirement. Accordingly, address how to partition an requirement into requirements, such overall minimized. establish efficient (polynomial) solutions both connections. These results provide required foundations...

Networks are expected to meet a growing volume of requirements imposed by new applications such as multimedia streaming and video conferencing. Two essential support quality service (QoS) resilience failures. In order satisfy these requirements, common approach is use two disjoint paths between the source destination nodes, first serving primary path second restoration path. Such approach, referred restoration, has several advantages, major one being ability switch promptly from another in...

We consider a multicast game with selfish non- cooperative players. There is special source node and each player interested in connecting to the by making routing decision that minimizes its payment. The mutual influence of players determined cost sharing mechanism, which our case evenly splits an edge among using it. two different models: integral model, where connects choosing single path, fractional allowed split flow it receives from between several paths. In both models we explore...