Efficient service-aware network algorithms

The internet supports a wide variety of services with varying levels of urgency. For example, health care and business services are likely to be more time critical than entertainment services. Service Level Agreements (SLAs) are formal contracts in which service providers and customers typically negotiate service terms such as the customer's requirements. Based on the customer's specific needs, service providers should efficiently manage network resources to better satisfy the needs of all customers. For example, some tele-medicine applications require highly reliable service at all times. However, some entertainment applications, such as video streaming with buffering, can tolerate short periods of downtime with little disruptions to the customers. Therefore, if network resources are scarce, service providers can conserve these resources for customers with stringent needs by providing less than full service to customers with flexible requirements.;We consider a dynamic network setting where customer requests arrive over time and are not known in advance. Events such as link failures and congestion also occur over time. In this unpredictable setting, it is difficult to determine the optimal decision for each request. Therefore, it is important to develop efficient and intelligent solutions using statistical estimates that approximate the distributions of events such as request arrivals and departures and link failures.;For some critical applications, customers may require full service in the event of a link failure. However for some less critical applications, customers may be more flexible in their service needs if the service is offered at lower costs. We first consider two settings where customers are willing to accept less than the full amount of required bandwidth as long as the overall service is typically high. In the first setting, customers accept a requested fraction of the bandwidth rather than the full amount in the event of a link failure. In the second setting, customers are willing to accept an expected level of bandwidth, rather than an absolute amount. For both settings, we develop efficient routing algorithms that exploit these relaxed reliability requirements.;In addition to the customer's requirements, SLAs typically also include the fees paid to the service provider for meeting these requirements and the penalties incurred to the provider for violations. Since the service provider wants to maximize profit, it is important to determine the most profitable requests. We develop and study routing algorithms that aim to satisfy customer reliability requirements while maximizing the overall profit to the service provider. We propose an efficient approach that judiciously determines which requests to accept, and routes these requests, to maximize expected profit.;Finally, we consider link congestion in a setting where links become congested and uncongested based on a known probability. Since traversing a link in its congested state requires more time than in the non-congested state, the goal is to minimize the expected routing time. We analyze algorithms to minimize this expected routing time.