Thinning Protocols for Routing h-Relations Over Shared Media



: Kautonen A, Leppänen V, Penttonen M

Publisher: Elsevier

: 2010

: Journal of Parallel and Distributed Computing

: JPDC

: 8

: 70

: 8

: 783

: 789

: 7

: 0743-7315

DOI: https://doi.org/10.1016/j.jpdc.2010.03.012(external)


Various shared media support several channels and provide extensive
connectivity enabling nodes of such media simultaneously communicate
with each other. Especially, optical communication offers huge
bandwidth and makes it possible to build communication networks of
very high bandwidth. However, contention of shared channels may be
challenging.

In this paper we examine the problem setup called $h$-relation routing
on complete networks under so-called OCPC or 1-collision assumption.
We present some simple and robust communication algorithms and
study their efficiency, analytically and experimentally. The analyses
and experiments show that if there is enough parallel slackness,
then routing is work-optimal, and the amortized routing cost per packet
is a small constant.



Last updated on 2024-26-11 at 20:36