BOUNDS ON EVACUATION TIME FOR DEFLECTION ROUTING

被引：30

作者：

HAJEK, B ^{[1
]}

机构：

[1] UNIV ILLINOIS,COORDINATED SCI LAB,URBANA,IL 61801

来源：

DISTRIBUTED COMPUTING | 1991年 / 5卷 / 01期

关键词：

ADAPTIVE ROUTING; HOT POTATO ROUTING; DEFLECTION ROUTING; MISROUTING; HYPERCUBE NETWORK;

D O I：

10.1007/BF02311228

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Upper bounds are given on the time T needed to evacuate k packets from a synchronous packet network using deflection routing, whereby all packets that arrive at a node during one time slot leave the node during the next slot. For example, T less-than-or-equal-to n + 2(k - 1) for a binary n-cube network when priority is given to packets closer to their destination, and for a single destination network T is less than or equal to the network diameter plus k - 1 times the network deflection index. Deflection routing for one pass through an omega network is also considered.

引用

页码：1 / 6

页数：6

共 9 条

[1] ON DISTRIBUTED COMMUNICATIONS NETWORKS [J].

BARAN, P .

IEEE TRANSACTIONS ON COMMUNICATIONS SYSTEMS, 1964, CS12 (01) :1-&

[2] ROUTING, MERGING, AND SORTING ON PARALLEL MODELS OF COMPUTATION [J].

BORODIN, A ;

HOPCROFT, JE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (01) :130-145

[3]

Greenberg A. G., 1986, Teletraffic Analysis and Computer Performance Evaluation. Proceedings of the International Seminar, P255

[4]

HILLIS D, 1985, CONNECTION MACHINE

[5]

Lawrie D. H., 1980, Proceedings ofthe Workshop on Interconnection Networks for Parallel and Distributed Processing, P116

[6] ACCESS AND ALIGNMENT OF DATA IN AN ARRAY PROCESSOR [J].

LAWRIE, DH .

IEEE TRANSACTIONS ON COMPUTERS, 1975, 24 (12) :1145-1155

[7]

NGAI JY, 1989, P 1 S PAR ALG ARCH, P1

[8]

SMITH B, 1981, REAL TIME SIGNAL PRO, V4, P241

[9]

WU F, INTERCONNECTION NETW

← 1 →