在如同全IP網路(ALL-IP Network)這類的分封交換網路(packet-switching network)中提供具時效性的服務(time-sensitive services)必須嚴格的控制時間。路由規劃是網路管理中重要的一環，所以這類網路的路由規劃必須考慮網路延遲。然而就我們目前所知，多數的傳統路由演算法並不以傳輸延遲(path delay)為主要考量因素；例外少數有考量延遲時間的演算法也僅限於鍊結延遲(link delay)，而未考慮節點延遲(node delay)。此乃肇因於以往頻寬的成本極為昂貴，因而造成演算法設計者在設計時會儘可能有效利用頻寬，如此免不了會犧牲傳遞速度。在過去幾年間，由於光通訊技術的提升，網路頻寬的成長速度遠遠已超過路由器(router)處理能力的成長。在這樣不對等的成長比例驅使下，節點延遲，亦即路由器處理封包時所耗時間，在傳輸延遲中所佔的比例亦隨之快速增長。也因此我們認為，在為高速封包交換網路設計路由演算法時，必須同時考量鍊結延遲和節點延遲。在本論文中，我們設計了一個訊務流為基礎的路由演算法(flow-based routing algorithm)，KLONE，來驗證我們的論點。在規劃路由時，KLONE會把發生在鍊結和節點上的延遲時間一併列入計算，並以全體延遲時間為主要考量。透過我們反覆的測試實驗，我們發現其較之於常用的OSPF演算法，可以在效能上有30%的勝出。藉此，我們的論點得到初步的證實。 / Providing time sensitive services becomes an essential task for some packet-switching networks such as All-IP networks, which will carry all the traffics supported by both circuit-switching and packet-switching networks. To fulfill this demand, such networks require a delay sensitive routing mechanism to provide time-related QoS for delay sensitive services. However, most of traditional routing algorithms do not take delay time as a major concern. Only a few are designed for time sensitive services. These time sensitive routing algorithms are designed at the time when the link bandwidth is the only scarce resource. As the bandwidth of communication links grows rapidly in recent years due to the advance of optical communication technologies, link bandwidth is no longer the only scarce resource. The processing speed of nodes, for example, routers, becomes another critical source of delay time. In this thesis, we designed a new flow-based routing algorithm, the KLONE algorithm, which takes average delay time as its minimization objective and takes both nodes and links as delay components. Through an intensive evaluation using simulation method, we demonstrate that a routing algorithm that considers both link and node delay might outperform the traditional OSPF algorithm.

No / Abstract: Internet of Things (IoT) aims to enable the interconnection of a large number of smart devices (things) using a combination of networks and computing technologies. But an influx of interconnected things makes a greater demand on the underlying communication networks and affects the quality of service (QoS). This paper investigates into the QoS of delay sensitive things and the corresponding traffic they generate over the network. Things such as security alarms, cameras, etc, generate delay sensitive information that must be communicated in a real time. Such things have heterogeneous features with limited buffer capacity, storage and processing power. Thus the most commonly used Best Effort service model cannot be an attractive mechanism to treat delay sensitive traffic. This paper proposes a cost-effective analytical model for a finite capacity queueing system with pre-emptive resume service priority and push-out buffer management scheme. Based on the analytical model various simulation results are generated in order to analyse the mean queue length and the blocking probability of high and low priority traffic for system with various capacities.

We investigate in detail two multiuser opportunistic scheduling problems in centralized wireless systems: the scheduling of "delay-sensitive" flows with packet delay requirements of a few tens to few hundreds of milliseconds over the air interface, and the scheduling of "best-effort" flows with the objective of minimizing mean file transfer delay. Schedulers for delay-sensitive flows are characterized by a fundamental tradeoff between "maximizing total service rate by being opportunistic" and "balancing unequal queues (or delays) across users". In choosing how to realize this tradeoff in schedulers, our key premise is that "robustness" should be a primary design objective alongside performance. Different performance objectives -- mean packet delay, the tail of worst user's queue distribution, or that of the overall queue distribution -- result in remarkably different scheduling policies. Different design objectives and resulting schedulers are also not equally robust, which is important due to the uncertainty and variability in both the wireless environment and the traffic. The proposed class of schedulers offers low packet delays, less sensitivity to the scheduler parameters and channel characteristics, and a more graceful degradation of service in terms of the fraction of users meeting their delay requirements under transient overloads, when compared with other well-known schedulers. Schedulers for best-effort flows are characterized by a fundamental tradeoff between "maximizing the total service rate" and "prioritizing flows with short residual sizes". We characterize two regimes based on the "degree" of opportunistic gain present in the system. In the first regime -- where the opportunistic capacity of the system increases sharply with the number of users -- the use of residual flow-size information in scheduling will 'not' result in a significant reduction in flow-level delays. Whereas, in the second regime -- where the opportunistic capacity increases slowly with the number of users -- using flow-size information alongside channel state information 'may' result in a significant reduction. We then propose a class of schedulers which offers good performance in either regime, in terms of mean file transfer delays as well as probability of blocking for systems that enforce flow admission control. This thesis provides a comprehensive theoretical study of these fundamental tradeoffs for opportunistic schedulers, as well as an exploration of some of the practical ramifications to engineering wireless systems. / text

This thesis explores the queueing performance of a wireless communication system that transmits packets over a correlated erasure channel using the IEEE 802.11 protocol suit. The channel states and the queue length together form a Markov chain. Exploiting this mathematical structure, the probability of the queue exceeding a certain threshold can be obtained. Most previous contributions in this area treat code-rate selection, channel erasure probability and network congestion separately. In this thesis, a simple integrated approach, which jointly considers these factors, is introduced. This approach becomes especially valuable for capturing the performance of delay-sensitive communication systems over time-varying channels. This thesis starts with a review of related work about correlated bit-erasure wireless channel models. A numerical study is then conducted to demonstrate the importance of optimizing overall system performance, and how this process impacts error-control coding at the physical layer. Following this exercise, a packet-erasure channel model with a Poisson arrival process is analyzed. The Baum-Welch algorithm is subsequently presented as a means to estimate the parameters of wireless communication systems. Furthermore, a matrix geometric method for obtaining the stationary distribution of the ensuing Markov chain is discussed. This offers a new perspective on wireless communication in the context of delay-sensitive applications. To complement the analysis platform put forth in this work, illustrative numerical results are contained in the last section of the thesis. From these results, design guidelines for improving the performance of delay-sensitive wireless communication systems are established. Although these results are obtained under simplifying assumptions, the overall methodology applies to more general situations, especially for wide-band delay-sensitive wireless communication applications.

Wireless communication systems continue to face the challenge of time varying quality of the underlying communication channel. When a slow fading channel goes into a deep fade, the corresponding communication system might face successive decoding failures at the destination, and for delay-sensitive communication systems, this amounts to delays that are not desired. In such situations, it becomes a priority to get out of the deep fades. Many techniques and approaches are already available in the literature to counteract fading effects. This work is motivated by recent advances in fast reconfigurable antennas, which provide new means to change the statistical profile of fading channels, and hence reduce the probability of prolonged fades. Fast reconfigurable antennas are poised to improve overall performance, especially for delay-sensitive traffic in slow-fading environments. This potential enhanced performance motivates this study of the queueing behavior of point-to-point communication systems with reconfigurable antennas. We focus on finite-state channels with memory, and we analyze the queueing behavior of the wireless communication system over erasure channels, for a traditional system versus a reconfigurable antenna implementation. We provide numerical results for situations where using reconfigurable antennas yield substantial performance gains in terms of throughput, delay and buffer overflow.

Cloud Gaming systems are among the most challenging networked-applications, since they deal with streaming high-quality and bulky video in real-time to players’ devices. While all industry solutions today are centralized, we introduce an AI-assisted hybrid networking architecture that, in addition to the central cloud servers, also uses some players’ computing resources as additional points of service. We describe the problem, its mathematical formulation, and potential solution strategy. Edge computing is a promising paradigm that brings servers closer to users, leading to lower latencies and enabling latency-sensitive applications such as cloud gaming, virtual/augmented reality, telepresence, and telecollaboration. Due to the high number of possible edge servers and incoming user requests, the optimum choice of user-server matching has become a difficult challenge, especially in the 5G era where the network can offer very low latencies. In this thesis, we introduce the problem of fair server selection as not only complying with an application's latency threshold but also reducing the variance of the latency among users in the same session. Due to the dynamic and rapidly evolving nature of such an environment and the capacity limitation of the servers, we propose as solution a Reinforcement Learning method in the form of a Quadruple Q-Learning model with action suppression, Q-value normalization, and a reward function that minimizes the variance of the latency. Our evaluations in the context of a cloud gaming application show that, compared to a existing methods, our proposed method not only better meets the application's latency threshold but is also more fair with a reduction of up to 35\% in the standard deviation of the latencies while using the geo-distance, and it shows improvements in fairness up to 18.7\% compared to existing solutions using the RTT delay especially during resource scarcity. Additionally, the RL solution can act as a heuristic algorithm even when it is not fully trained. While designing this solution, we also introduced action suppression, Quadruple Q-Learning, and normalization of the Q-values, leading to a more scalable and implementable RL system. We focus on algorithms for distributed applications and especially esports, but the principles we discuss apply to other domains and applications where fairness can be a crucial aspect to be optimized.

No description available.

This dissertation addresses some of the most important issues in delay-sensitive communication over wireless systems and networks. Traditionally, the design of communication networks adopts a layered framework where each layer serves as a “black box” abstraction for higher layers. However, in the context of wireless networks with delay-sensitive applications such as Voice over Internet Protocol (VoIP), on-line gaming, and video conferencing, this layered architecture does not offer a complete picture. For example, an information theoretic perspective on the physical layer typically ignores the bursty nature of practical sources and often overlooks the role of delay in service quality. The purpose of this dissertation is to take on a cross-disciplinary approach to derive new fundamental limits on the performance, in terms of capacity and delay, of wireless systems and to apply these limits to the design of practical wireless systems that support delay-sensitive applications. To realize this goal, we consider a number of objectives. 1. Develop an integrated methodology for the analysis of wireless systems that support delay-sensitive applications based, in part, on large deviation theory. 2. Use this methodology to identify fundamental performance limits and to design systems which allocate resources efficiently under stringent service requirements. 3. Analyze the performance of wireless communication networks that takes advantage of novel paradigms such as user cooperation, and multi-antenna systems. Based on the proposed framework, we find that delay constraints significantly influence how system resources should be allocated. Channel correlation has a major impact on the performance of wireless communication systems. Sophisticated power control based on the joint space of channel and buffer states are essential for delaysensitive communications.

In the past few years, we have witnessed the continuous growth in popularity of delay-sensitive applications. Applications like live video streaming, multimedia conferencing, VoIP and online gaming account for a major part of Internet traffic these days. It is also predicted that this trend will continue in the coming years. This emphasizes the significance of developing efficient scheduling algorithms in communication networks with guaranteed low delay performance. In our work, we try to address the delay issue in some major instances of wireless communication networks. First, we study a wireless content distribution network (CDN), in which the requests for the content may have service deadlines. Our wireless CDN consists of a media vault that hosts all the content in the system and a number of local servers (base stations), each having a cache for temporarily storing a subset of the content. There are two major questions associated with this framework: (i) content caching: which content should be loaded in each cache? and (ii) wireless network scheduling: how to appropriately schedule the transmissions from wireless servers? Using ideas from queuing theory, we develop provably optimal algorithms to jointly solve the caching and scheduling problems. Next, we focus on wireless relay networks. It is well accepted that network coding can enhance the performance of these networks by exploiting the broadcast nature of the wireless medium. This improvement is usually evaluated in terms of the number of required transmissions for delivering flow packets to their destinations. In this work, we study the effect of delay on the performance of network coding by characterizing a trade-off between latency and the performance gain achieved by employing network coding. More specifically, we associate a holding cost for delaying packets before delivery and a transmission cost for each broadcast transmission made by the relay node. Using a Markov decision process (MDP) argument, we prove a simple threshold-based policy is optimal in the sense of minimum long-run average cost. Finally, we analyze delay-sensitive applications in wireless peer-to-peer (P2P) networks. We consider a hybrid network which consists of (i) an expensive base station-to-peer (B2P) network with unicast transmissions, and (ii) a free broadcast P2P network. In such a framework, we study two popular applications: (a) a content distribution application with service deadlines, and (b) a multimedia live streaming application. In both problems, we utilize random linear network coding over finite fields to simplify the coordination of the transmissions. For these applications, we provide efficient algorithms to schedule the transmissions such that some quality of service (QoS) requirements are satisfied with the minimum cost of B2P usage. The algorithms are proven to be throughput optimal for sufficiently large field sizes and perform reasonably well for finite fields.

Timeliness in delivering packets for delay-sensitive applications is an important QoS (Quality of Service) measure in many systems, notably those that need to provide real-time performance. In such systems, if delay-sensitive traffic is delivered to the destination beyond the deadline, then the packets will be rendered useless and dropped after received at the destination. Bandwidth that is already scarce and shared between network nodes is wasted in relaying these expired packets. This thesis proposes that a deterministic per-hop delay can be achieved by using a dynamic queue threshold concept to bound delay of each node. A deterministic per-hop delay is a key component in guaranteeing a deterministic end-to-end delay. The research aims to develop a generic approach that can constrain network delay of delay-sensitive traffic in a dynamic network. Two adaptive queue management schemes, namely, DTH (Dynamic THreshold) and ADTH (Adaptive DTH) are proposed to realize the claim. Both DTH and ADTH use the dynamic threshold concept to constrain queuing delay so that bounded average queuing delay can be achieved for the former and bounded maximum nodal delay can be achieved for the latter. DTH is an analytical approach, which uses queuing theory with superposition of N MMBP-2 (Markov Modulated Bernoulli Process) arrival processes to obtain a mapping relationship between average queuing delay and an appropriate queuing threshold, for queue management. While ADTH is an measurement-based algorithmic approach that can respond to the time-varying link quality and network dynamics in wireless ad hoc networks to constrain network delay. It manages a queue based on system performance measurements and feedback of error measured against a target delay requirement. Numerical analysis and Matlab simulation have been carried out for DTH for the purposes of validation and performance analysis. While ADTH has been evaluated in NS-2 simulation and implemented in a multi-hop wireless ad hoc network testbed for performance analysis. Results show that DTH and ADTH can constrain network delay based on the specified delay requirements, with higher packet loss as a trade-off.