On the remote server problem or more about TCP acknowledgments

作     者：Epstein, Leah Kesselman, Alex 

作者机构：Univ Haifa Dept Math IL-31905 Haifa Israel Max Planck Inst Informat Saarbrucken Germany 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2006年第369卷第1-3期

页      面：285-299页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：on-line algorithms TCP acknowledgement 

摘      要：`We study an on-line problem that is motivated by service calls management in a remote support center. When a customer calls the remote support center of a software company, a technician opens a service request and assigns it a severity rating. This request is then transferred to the appropriate support engineer (SE) who establishes a connection to the customer s site and uses remote diagnostic capabilities to resolve the problem. We assume that the SE can service at most one customer at time and a request service time is negligible. There is a constant setup cost of creating a new connection to a customer s site and a specific cost per request for delaying its service that depends on the severity of the request. The problem is to decide which customers to serve first so as to minimize the incurred cost. This problem with just two customers is a natural generalization of the TCP acknowledgment problem. For the on-line version of the Remote Server Problem (RSP), we present algorithms for the general case and for a special casef of two customers that achieve competitive ratios of exactly 4 and 3, respectively. We also show that no deterministic on-line algorithm can have competitive ratio better than 3. Then we study generalized versions of our model, these are the case of an asymmetric setup cost function and the case of multiple SEs. For the off-line version of the RSP, we derive an optimal algorithm with a polynomial running time for a constant number of customers. (c) 2006 Elsevier B.V. All rights reserved.