Optimal many-to-one routing on the mesh with constant queues

详细信息    查看全文

• 作者：Andrea Pietracaprina and Geppino Pucci
• 关键词：Parallel algorithms ; Interconnection networks ; Mesh ; Packet routing
• 刊名：Information Processing Letters
• 出版年：2005
• 出版时间：2005
• 年：2005
• 卷：96
• 期：1
• 页码：24-29
• 全文大小：91 K

文摘

We present randomized and deterministic algorithms for many-to-one packet routing on an n-node two-dimensional mesh under the store-and-forward model. We consider the general instance of many-to-one routing where each node is the source (resp., destination) of ℓ (resp., k) packets, for arbitrary values of ℓ and k. All our algorithms run in optimal time and use queues of only constant size at each node to store packets in transit. The randomized algorithms, however, are simpler to implement. Our result closes a gap in the literature, where time-optimal algorithms using constant-size queues were known only for the special cases ℓ