Reduction of a polling network to a single node

被引:10
作者
Beekhuizen, Paul [1 ,2 ]
Denteneer, Dee [3 ]
Resing, Jacques [4 ]
机构
[1] EURANDOM, Eindhoven, Netherlands
[2] Philips Res, Digital Signal Proc Grp, Eindhoven, Netherlands
[3] Philips Res, Connect Syst & Networks Grp, Eindhoven, Netherlands
[4] Eindhoven Univ Technol, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands
关键词
polling systems; HoL-based service disciplines; concentrating tree networks; reductions;
D O I
10.1007/s11134-008-9071-z
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We consider a discrete-time tree network of polling servers where all packets are routed to the same node (called node 0), from which they leave the network. All packets have unit size and arrive from the exterior according to independent batch Bernoulli arrival processes. The service discipline of each node is work-conserving and the service discipline of node 0 has to be HoL-based, which is an additional assumption that is satisfied by, a. o., m(i)-limited service, exhaustive service, and priority disciplines. Let a type i packet be a packet that visits queue i of node 0. We establish a distributional relation between the number of type i packets in the network and in a single station system, and we show equality of the mean end-to-end delay of type i packets in the two systems. Essentially this reduces an arbitrary tree network to a much simpler system of one node, while preserving the mean end-to-end delay of type i packets.
引用
收藏
页码:303 / 319
页数:17
相关论文
共 13 条
[1]   A SEQUENCE OF SERVICE STATIONS WITH ARBITRARY INPUT AND REGULAR SERVICE TIMES [J].
AVIITZHAK, B .
MANAGEMENT SCIENCE, 1965, 11 (05) :565-571
[2]  
Dally WJ, 2001, DES AUT CON, P684, DOI 10.1109/DAC.2001.935594
[3]   REDUCTION METHODS FOR TANDEM QUEUING SYSTEMS [J].
FRIEDMAN, HD .
OPERATIONS RESEARCH, 1965, 13 (01) :121-&
[4]   Sample-path large deviations for tandem and priority queues with Gaussian inputs [J].
Mandjes, M ;
Van Uitert, M .
ANNALS OF APPLIED PROBABILITY, 2005, 15 (02) :1193-1226
[5]   COMBINATORIAL LEMMA AND ITS APPLICATION TO CONCENTRATING TREES OF DISCRETE-TIME QUEUES [J].
MORRISON, JA .
BELL SYSTEM TECHNICAL JOURNAL, 1978, 57 (05) :1645-1652
[6]  
NEELY MJ, 2005, IEEE T INFORM THEORY, V51, P1
[7]   Heavy traffic analysis of polling systems in tandem [J].
Reiman, MI ;
Wein, LM .
OPERATIONS RESEARCH, 1999, 47 (04) :524-534
[8]   COMMUNICATION NETWORKS - MESSAGE PATH DELAYS [J].
RUBIN, I .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1974, 20 (06) :738-745
[9]   APPROXIMATE TIME-DELAY ANALYSIS FOR PACKET-SWITCHING COMMUNICATION NETWORKS [J].
RUBIN, I .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1976, 24 (02) :210-222
[10]   MESSAGE PATH DELAYS IN PACKET-SWITCHING COMMUNICATION NETWORKS [J].
RUBIN, I .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1975, CO23 (02) :186-192