In online service systems, delay experienced by a user from the service request to the service completion is one of the most critical performance metrics. To improve user delay experience, in this thesis, we investigate a novel aspect of system design: proactive serving, where the system can predict future user request arrivals and allocate its capacity to serve these upcoming requests proactively. This approach is complementary to the conventional capacity boosting mechanism and is motivated by recent industrial and academic advances. In particular, we investigate the fundamentals of proactive serving from a queuing theory perspective. / First, most importantly, we show that under proactive serving the average user delay decreases exponentially (in the prediction window size) for a wide range of queuing models. Furthermore, the delay reduction is robust against prediction errors. We also show that both the variance of user delay and the tail of user delay decrease exponentially under proactive serving, which are also important user delay experience metrics. / We then show that proactive serving is more effective in decreasing user delay than capacity boosting in light workload regime. In particular, the average user delay decays inverse-proportionally in system capacity, but exponentially in the prediction window size in proactive serving. / Finally we demonstrate how to leverage proactive serving in system design from a optimization point of view, e.g., how many resources are dedicated to proactive serving. The results provide useful engineering insights to system designers. / Our trace-driven simulation results demonstrate the practical power of proactive serving: for example, under the YouTube data trace of 1000 different videos, the average user delay can be decreased by 50% when the system predicts 100 seconds ahead. Our results provide useful insights for proactive serving and justify its increasing applications in practical systems. / 對於在線服務系統，由於系統服務造成的用戶延遲是衡量系統性能的重要指標。提高用戶的延遲體驗的傳統方法是提高系統中服務器的性能。在本論文中，我們研究一種新穎的叫做“前瞻性服務”的方法用來提高用戶的延遲體驗。前瞻性服務是指系統在預測用戶需求的基礎上，在用戶產生需求之前，系統已經將服務送到用戶手中。前瞻性服務是傳統方法的有力補充。我們從排隊論的角度研究前瞻性服務對用戶的延遲的提高。 / 首先，對於多种排隊系統，我們證明前瞻性服務能夠指數性降低用戶的平均延遲。而且前瞻性服務對於用戶需求預測的誤差具有魯棒性。我們同時也證明了前瞻性服務能夠指數性降低用戶的延遲方差和尾概率。 / 然後，我們證明前瞻性服務在系统低负载时比傳統方法在降低用戶的平均延遲上更加有效。前瞻性服務能夠指數性降低用戶的平均延遲。而通過提高系統服務器性能，只能反比例降低用戶的平均延遲。 / 最後，我們從優化的角度分析怎樣在系統設計中利用前瞻性服務，給系統設計者提供有用的建議。 / 我們基於實際數據的仿真結果驗證了前瞻性服務在實際系統的作用。例如，基於Youtube數據的仿真表明，如果系統能提前一百秒預測用戶的需求，那麼前瞻性服務能夠降低一半的用戶延遲。 / Zhang, Shaoquan. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2014. / Includes bibliographical references (leaves 103-108). / Abstracts also in Chinese. / Title from PDF title page (viewed on 02, December, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.

none

Nowadays, computer networks have always been complicated deployment for both the scientific and industry groups as they attempt to comprehend and analyze network performance as well as design efficient procedures for their operation. In software-defined networking (SDN), predicting latency (delay) is essential for enhancing performance, power consumption and resource utilization in meeting its significant latency requirements. In this thesis, we present a graph-based formulation of Abilene Network and other topologies and apply a Graph Neural Network (GNN)-based model, Spatial-Temporal Graph Convolutional Network (STGCN), to predict end-to-end packet delay on this formulation. The evaluation uses STGCN to compare with other machine learning methods: Multiple Linear Regression (MLR), Extreme Gradient Boosting (XGBOOST), Random Forest (RF), and Neural Network (NN). Datasets in use include Abilene, 15-node scale-free, 24-node GEANT2, and 50-node networks. Notably, our GNN-based methodology can achieve 97.0%, 95.9%, 96.1%, and 63.1% less root mean square error (RMSE) in the most complex network situation than the baseline predictor, MLR, XGBOOST and RF, respectively. All the experiments show that STGCN has good prediction performance with small and stable prediction errors. This thesis illustrates the feasibility and benefits of a GNN approach in predicting end-to-end delay in software-defined networks.

Context: Wireless Mesh Network (WMN) is a form of ad-hoc network with flexible backhaul infrastructure and configuration, provides adaptive wireless internet connectivity to end users with high reliability. WMN is a wireless network consisting of mesh clients, mesh routers and gateways which are organized in a mesh topology with decentralized nature can consume more energy for data transmission. The networking performance of WMNs can be degraded due to the fact of high energy consumption for data transmission. Therefore, energy efficiency is the primary factor for attaining eminent performance. Organizing efficient routing and proper resource allocation can save huge amount of energy. Objectives: The main goal of this thesis is to reduce the energy consumption in WMNs. To do this, a new energy efficient routing algorithm is suggested. Adaptive rates based on rate allocation strategy and end to end delay metric are used mainly for optimal path selection in routing, which may in turn reduces the resource utilization and energy consumption. Method: An energy efficient routing algorithm is implemented by using the Ad hoc OnDemand Distance Vector (AODV) routing protocol. The RREQ packet in AODV is modified by adding a new field known as delay parameter which measures end to end delay between nodes. Adaptive rates obtained from Rate allocation policy are considered in the routing process to reduce energy consumption in the network. Energy measurement of the WMN and its performance is evaluated by measuring the metrics such as Throughput, End-to-End delay, Packet Delivery Ratio (PDR). For performing the simulation process, in this thesis, Network Simulator - 3 (NS-3) which is an open source discrete-event network simulator in which simulation models can be executed in C++ and Python is used. Using NetAnim-3.107 animator in NS-3-25.1, traffic flows between all the nodes are displayed. Results: The results are taken for existing algorithm and proposed algorithm for 25,50,75 and 100 nodes. Comparison of results shows that the total energy consumption is reduced for proposed algorithm for in all four scenarios. Conclusion: Energy efficient routing algorithm is implemented in different scenarios of radio access networks and energy is saved. Due to this algorithm even the performance metrics, Throughput, End-to-End delay, Packet Delivery Ratio (PDR) have shown eminent performance.

<p>The first part of the thesis (Part I) is devoted to find methods to describe transient behaviour of traffic processes, where the main emphasis is put on the description and analysis of excess periods and excess volumes of quite general stochastic processes. By assuming that traffic changes on different time scales, the transient characteristics such as excess periods could be important measures to describe periods of congestion on a communication link and moreover, the corresponding excess volume will represent lost information during such periods. Although the results obtained are of rather general nature, they provide some rather fundamental insight into transient characteristics of traffic processes. The distributions of the length of excess periods may then be expressed it terms of some excess probabilities that are related to the minimum of the process in the time interval considered. Similar relationsfor the excess volumes are harder to obtain and require the joint probability of the arrived volume and the minimum of the process in the same time interval.</p>

The first part of the thesis (Part I) is devoted to find methods to describe transient behaviour of traffic processes, where the main emphasis is put on the description and analysis of excess periods and excess volumes of quite general stochastic processes. By assuming that traffic changes on different time scales, the transient characteristics such as excess periods could be important measures to describe periods of congestion on a communication link and moreover, the corresponding excess volume will represent lost information during such periods. Although the results obtained are of rather general nature, they provide some rather fundamental insight into transient characteristics of traffic processes. The distributions of the length of excess periods may then be expressed it terms of some excess probabilities that are related to the minimum of the process in the time interval considered. Similar relationsfor the excess volumes are harder to obtain and require the joint probability of the arrived volume and the minimum of the process in the same time interval.

Some of the applications in modern data networks are delay sensitive (e.g., video and voice). An end-to-end delay analysis is needed to estimate the required network resources of delay sensitive applications. The schedulers used in the network can impact the resulting delays to the applications. When multiple applications are multiplexed in a switch, a scheduler is used to determine the precedence of the arrivals from different applications. Computing the end-to-end delay and queue sizes in a network of schedulers is difficult and the existing solutions are limited to some special cases (e.g., specific type of traffic). The theory of Network Calculus employs the min-plus algebra to obtain performance bounds. Given an upper bound on the traffic arrival in any time interval and a lower bound on the available service (called the service curve) at a network element, upper bounds on the delay and queue size of the traffic in that network element can be obtained. An equivalent end-to-end service curve of a tandem of queues is the min-plus convolution of the service curves of all nodes along the path. A probabilistic end-to-end delay bound using network service curve scales with O(H logH) in the path length H. This improves the results of the conventional method of adding per-node delay bounds scaling with O(H^3). We have used and advanced Network Calculus for end-to-end delay analysis in a network of schedulers. We formulate a service curve description for a large class of schedulers which we call Delta-schedulers. We show that with this service curve, tight single node delay and backlog bounds can be achieved. In an end-to-end scenario, we formulate a new convolution theoii rem which considerably improves the end-to-end probabilistic delay bounds. We specify our probabilistic end-to-end delay and backlog bounds for exponentially bounded burstniess (EBB) traffic arrivals. We show that the end-to-end delay varies considerably by the type of schedulers along the path. Using these bounds, we also show that a if the number of flows increases, the queues inside a network can be analyzed in isolation and regardless of the network effect.

Some of the applications in modern data networks are delay sensitive (e.g., video and voice). An end-to-end delay analysis is needed to estimate the required network resources of delay sensitive applications. The schedulers used in the network can impact the resulting delays to the applications. When multiple applications are multiplexed in a switch, a scheduler is used to determine the precedence of the arrivals from different applications. Computing the end-to-end delay and queue sizes in a network of schedulers is difficult and the existing solutions are limited to some special cases (e.g., specific type of traffic). The theory of Network Calculus employs the min-plus algebra to obtain performance bounds. Given an upper bound on the traffic arrival in any time interval and a lower bound on the available service (called the service curve) at a network element, upper bounds on the delay and queue size of the traffic in that network element can be obtained. An equivalent end-to-end service curve of a tandem of queues is the min-plus convolution of the service curves of all nodes along the path. A probabilistic end-to-end delay bound using network service curve scales with O(H logH) in the path length H. This improves the results of the conventional method of adding per-node delay bounds scaling with O(H^3). We have used and advanced Network Calculus for end-to-end delay analysis in a network of schedulers. We formulate a service curve description for a large class of schedulers which we call Delta-schedulers. We show that with this service curve, tight single node delay and backlog bounds can be achieved. In an end-to-end scenario, we formulate a new convolution theoii rem which considerably improves the end-to-end probabilistic delay bounds. We specify our probabilistic end-to-end delay and backlog bounds for exponentially bounded burstniess (EBB) traffic arrivals. We show that the end-to-end delay varies considerably by the type of schedulers along the path. Using these bounds, we also show that a if the number of flows increases, the queues inside a network can be analyzed in isolation and regardless of the network effect.

IEEE 802.11 has become the standard in wireless LAN. Originally, 802.11 is designed for the best-effort services only. To support the increasing demand of delay-sensitive applications, IEEE 802.11 Task Group E is developing a QoS-aware MAC protocol, EDCF, for differentiated services. However, when the network becomes congested, there exists unexpected packet delay due to collisions and retransmissions. This thesis proposes a dynamic contention control (DCC) scheme to reduce packet delay and increase the percentage of packets arriving in time. DCC estimates per-hop delay, denoted as Mrtt, and end-to-end delay, denoted as Sigma_t, based on either the received MAC-layer ACK or the control packets of a reactive routing protocol. Then, Mrtt and Sigma_t are used to dynamically adjust the associated contention window for each priority. Besides, when a frame is retransmitted, the backoff time is determined according to the remaining end-to-end delay instead of a uniformly distributed random number. For the propose of evaluation, we perform simulations on the well-known network simulator, NS-2. DCC is compared with the EDCF and one previously proposed scheme, AEDCF. The simulation results demonstrate the effectiveness and superiority of DCC.

Wireless sensor networks have arrived because of further developments of themodern Internet, and this has been considered to be one of the most importanttechnologies of the 21st century. Currently, the wireless sensor network has becomean important technology in a variety of areas and is widely used in thefield of national defense, national security, environmental monitoring, trafficmanagement, anti-terrorism, anti-disaster, and so on. The majority of these applicationsrequire real-time communication as the WSNs are required to sendthe data to the data center within a specified time. In order to meet the real-timedemand for wireless sensor networks, this work mainly focuses on the analysisand measurement of the end-to-end delay, including both single-hop and multihopdelays. This thesis first analyzes the composition of the end-to-end delayand then describes the end-to-end delay measurement algorithms and methods.The measurement is implemented in TelosB motes within TinyOS. Finally thereport will show the evaluation of the end-to-end delay in wireless sensor networks.