### QoS provision and routing with stochastic guarantees

- Research Article in 1st International ICST Conference on Quality of Service in Heterogeneous Wired/Wireless Networks
- Authors
- E. Biton, A. Orda
- Abstract
This work presents a methodology for providing QoS guarantees by considering the coupling between the scheduling mechanism and the routing schemes. Our main focus are rate-based schedulers and stochastic guarantees. We consider several traffic models and obtain for each an appropriate upper bound o…

more »This work presents a methodology for providing QoS guarantees by considering the coupling between the scheduling mechanism and the routing schemes. Our main focus are rate-based schedulers and stochastic guarantees. We consider several traffic models and obtain for each an appropriate upper bound on the end-to-end delay tail distribution. With that at hand, we derive corresponding routing schemes that exploit the obtained bound. More specifically, we consider traffic with exponentially bounded burstiness (EBB) and stochastic QoS requirements. First, we extend previous results and provide an upper bound on the tail distribution of the end-to-end delay for packetized traffic and links with non-negligible propagation delays. Consequently, we formulate several routing schemes that identify feasible paths under various network optimization criteria. We demonstrate the efficiency of these routing schemes via simulation examples. Then, we consider traffic with (general) stochastic bounded burstiness (SBB). Here, we provide the corresponding upper bound on the end-to-end delay tail distribution for packetized traffic and links with propagation delays. Finally, focusing on the special case of a bounding function that is the sum of exponents, we design appropriate routing schemes.

### The primal simplex approach to the QoS routing problem

- Research Article in 1st International ICST Conference on Quality of Service in Heterogeneous Wired/Wireless Networks
- Authors
- Ying Xiao, K. Thulasiraman, Guoliang Xue
- Abstract
Quality-of-service (QoS) routing problem requires the determination of a minimum cost path from a source node s to a destination node t in a data network such that the delay of the path is bounded by Δ (> 0). This problem also known as the constrained shortest path (CSP) problem is NP-hard. So, heu…

more »Quality-of-service (QoS) routing problem requires the determination of a minimum cost path from a source node s to a destination node t in a data network such that the delay of the path is bounded by Δ (> 0). This problem also known as the constrained shortest path (CSP) problem is NP-hard. So, heuristics and approximation algorithms have been presented in the literature. Among the heuristics, the LARAC algorithm, based on the dual of the LP relaxation or the Lagrangian relaxation of the CSP problem is very efficient. In this paper we study the primal simplex approach to the LP relaxation of the CSP problem and present an approximation algorithm to this problem. Several issues relating to efficient implementations of our approach are discussed. Experimental results comparing the performance of the new algorithm with that of the LARAC algorithm are presented.

### Approximation and heuristic algorithms for delay constrained path selection under inaccurate state information

- Research Article in 1st International ICST Conference on Quality of Service in Heterogeneous Wired/Wireless Networks
- Authors
- Ying Xiao, K. Thulasiraman, Guoliang Xue
- Abstract
Given a communication network modeled as a directed graph with a delay parameter associated with each link, we consider the problem of determining the most probable delay constrained path from a source node to a destination node. Assuming that the link delays are random variables with continuous an…

more »Given a communication network modeled as a directed graph with a delay parameter associated with each link, we consider the problem of determining the most probable delay constrained path from a source node to a destination node. Assuming that the link delays are random variables with continuous and differentiable probability density function and using the central limit theorem this problem can be formulated as a path problem which involves simultaneously optimizing two additive path parameters. Two cases arise. When there is one path with mean delay less than the delay bound, we present an exact pseudo polynomial algorithm, a fully polynomial time ε-approximation algorithm and a strongly polynomial heuristic algorithm. In the unlikely case when this assumption is violated, the problem is shown to be NP-hard and no constant factor approximation algorithm exists if P ≠ NP. We also study the path protection problem under inaccurate state information.

### Dynamic resource management in competitive wireless data networks: a game theoretic framework

- Authors
- S.K. Das
- Abstract
Summary form only given. The competition among wireless data service providers brings in an option for the unsatisfied customers to switch their providers, which is called churning. The implementation of wireless local number portability (WLNP) is expected to further increase the churn rate (the pr…

more »Summary form only given. The competition among wireless data service providers brings in an option for the unsatisfied customers to switch their providers, which is called churning. The implementation of wireless local number portability (WLNP) is expected to further increase the churn rate (the probability of users switching the provider). However, the existing resource management algorithms for wireless networks fail to fully capture the far-reaching impact of this unforeseen competitiveness. From this perspective, we first formulate non-cooperative games between the service providers and the users. A user's decision to leave or join a provider is based on a finite set of strategies. A service provider can also construct its game strategy sets so as to maximize their utility (revenue) considering the churn rate. Based on the game theoretic framework, we propose an integrated admission and rate control (ARC) framework for CDMA based wireless data networks. The admission control is at the session (macro) level while the rate control at the link layer packet (micro) level. Two admission control modes are considered: one-by-one mode and batch processing mode in which multiple users are admitted at a time. We show that: (i) for the one-by-one mode, the Nash equilibrium in pure strategy can be established for both under-loaded and fully-loaded systems; and (ii) for batch processing mode, there is either an equilibrium in pure strategy, or a dominant strategy exists for the service provider. Therefore, the providers have clearly defined admission criteria as outcome of the game. Users are categorized into multiple classes and offered differentiated services based on the price they pay and the service degradation they can tolerate. We show that the proposed ARC framework significantly increases the provider's revenue and also successfully offers differentiated QoS to the users.

### End-to-end framework for QoS guarantee in heterogeneous wired-cum-wireless networks

- Authors
- Ming Li, Hua Zhu , S. Sathyamurthy, I. Chlamtac, B. Prabhakaran
- Abstract
With information access becoming more and more ubiquitous, there is a need for providing QoS support for communication that spans wired and wireless networks. For the wired side, RSVP/SBM has been widely accepted as a flow reservation scheme in IEEE 802 style LANs. In this paper, we investigate the…

more »With information access becoming more and more ubiquitous, there is a need for providing QoS support for communication that spans wired and wireless networks. For the wired side, RSVP/SBM has been widely accepted as a flow reservation scheme in IEEE 802 style LANs. In this paper, we investigate the integration of RSVP and a RSVP-like flow reservation scheme in wireless LANs, as an end-to-end solution for QoS guarantee in wired-cum-wireless networks. We propose WRESV, an RSVP-like flow reservation and admission control scheme for IEEE 802.11 wireless LAN. Using WRESV, wired/wireless integration can be easily implemented by cross-layer interaction at the access point. Main components of the integration are RSVP-WRESV parameter mapping, and the initiation of new reservation messages, depending on where senders/receivers are located. In addition, we also propose various optimizations for supporting multicast session, mobility management, and admission control.