ON NONUNIFORM PACKET SWITCHED DELTA-NETWORKS AND THE HOT-SPOT EFFECT

被引:3
作者
HARRISON, PG
机构
[1] Imperial Coll of Science, Technology and Medicine, London
来源
IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES | 1991年 / 138卷 / 03期
关键词
NETWORKS; COMPUTER APPLICATIONS; STOCHASTIC MODELING;
D O I
10.1049/ip-e.1991.0017
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We analyse the performance of a multistage interconnection network (MIN) with a packet-switching protocol, embedded in a closed network of processors. First, the expected value of transmission time through a delta-2 type of MIN is determined. We then obtain, for the first time by an analytical method, a formula for its probability density function from which the variance and higher moments follow. Previously densities have only been estimated by simulation which is expensive and can be unreliable, especially in the often crucial tail region. Numerical results reveal new insights into the hot-spot phenomenon which occurs when one output address is selected more frequently than the others. We first show how mean transmission time on hot paths increases with the hot-spot intensity and compare this with cooler paths. We also plot the density functions for these transmission times. Hence it is possible to determine precisely transmission time variability and to obtain reliability measures from their tails. The approach can handle arbitrary routing frequencies to the MIN output addresses and suggests new approximation techniques with wider applicability.
引用
收藏
页码:123 / 130
页数:8
相关论文
共 21 条
[1]  
ABATE T, 1988, MAY SIGMETRICS 1988
[2]  
Baskett F., 1975, J ACM, V22, P1975
[3]   COMPUTATIONAL ALGORITHMS FOR CLOSED QUEUING NETWORKS WITH EXPONENTIAL SERVERS [J].
BUZEN, JP .
COMMUNICATIONS OF THE ACM, 1973, 16 (09) :527-531
[4]   PASSAGE TIMES FOR OVERTAKE-FREE PATHS IN GORDON-NEWELL NETWORKS [J].
DADUNA, H .
ADVANCES IN APPLIED PROBABILITY, 1982, 14 (03) :672-686
[5]   CLOSED QUEUING SYSTEMS WITH EXPONENTIAL SERVERS [J].
GORDON, WJ ;
NEWELL, GF .
OPERATIONS RESEARCH, 1967, 15 (02) :254-&
[6]   THE REPRESENTATION OF MULTISTAGE INTERCONNECTION NETWORKS IN QUEUING MODELS OF PARALLEL SYSTEMS [J].
HARRISON, PG ;
PATEL, NM .
JOURNAL OF THE ACM, 1990, 37 (04) :863-898
[7]  
HARRISON PG, 1986, IEEE T COMPUT, V35, P54, DOI 10.1109/TC.1986.1676657
[9]   THE DISTRIBUTION OF CYCLE TIMES IN TREE-LIKE NETWORKS OF QUEUES [J].
HARRISON, PG .
COMPUTER JOURNAL, 1984, 27 (01) :27-36
[10]  
HARRISON PG, IN PRESS PERFORMANCE