The chilean highway problem

Abstract: We consider the problem faced by a server offering multiple services with adversarial service request sequences. The server may offer a single service at a time and suffers a fixed latency whenever it switches the type of offered service. This problem captures realistic features of traffic and packet routing on network components such as multiplexers. We state the problem as a packet routing problem on bounded size buffer networks and then examine the crucial issue of stability—under what conditions will the number of unserviced requests remain bounded as the system runs for an arbitrarily long period of time? We obtain a tight characterization in terms of a natural packet density criterion for star networks with bounded buffer size. [Copyright &y& Elsevier]