Thinning protocols for routing hh-relations over shared media

Various shared media support several channels and provide extensive connectivity enabling nodes of such media to 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 hh-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.