返回Google圖書搜尋

Robust Algorithms for Packet Routing in a Mesh

Thomas J. Watson IBM Research CenterP. Raghavan

出版	IBM Thomas J. Watson Research Division, 1989
URL	http://books.google.com.hk/books?id=cRBVHQAACAAJ&hl=&source=gbs_api

註釋Abstract: "This paper considers the problem of permutation packet routing on a [square root n] x [square root n] mesh-connected array of processors. Each node in the array is assumed to be independently faulty with a probability bounded above by a value p. This paper gives a routing algorithm which, if p [is less than or equal to] 0.29, will with very high probability route every packet that can be routed in O([square root n]log n) steps with queue lengths that are O(log[superscript 2]n). Extensions to higher-dimensional meshes are given."