Exact emulation of a priority queue with a switch and delay lines

作     者：Sarwate, A. D. Anantharam, V. 

作者机构：Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA 

出 版 物：《QUEUEING SYSTEMS》 (排队系统)

年 卷 期：2006年第53卷第3期

页      面：115-125页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：National Science Foundation, NSF U.S. Department of Defense, DOD Office of Naval Research, ONR, (N00014-1-0637) Defense Advanced Research Projects Agency, DARPA, (N66001-00-C-8062) National Defense Science and Engineering Graduate, NDSEG 

主　　题：erasure control coding error control coding networking optical networking priority queues queueing switching 

摘      要：All-optical packet switched networking is hampered by the problem of realizing viable queues for optical packets. Packets can be buffered in delay lines, but delay lines do not functionally emulate queues from an input-output point of view. In this paper we consider the problem of exact emulation of a priority queue of size K using a switching system comprised of a switch of size (M + 1) x (M + 1), which has one distinguished input for external arrivals, one distinguished output for external departures, and fixed-length delay lines of lengths L-1, L-2, ..., L-M connecting the other inputs and outputs in pairs. We measure the complexity of such an emulation by M + 1. We prove that M = [log(K - 1)] and present a construction Sigma(M)(m=1) L-m = K = O(root K). We also sketch an idea for an all-optical packet switched communication network architecture based on approximate emulation of priority queues of finite size using switches and delay lines, with erasure control coding at the packet level.