Throughput Region of Random Access Networks of General Topology

In this paper we introduce and study a random access model which is a generalization of the classical Slotted Aloha model [7]. Unlike the Slotted Aloha, where two or more simultaneous transmissions, on any subset of links, collide and "erase" each other, we allow a quite general interference structure, where transmission on link i erases a simultaneous transmission on link j with some fixed probability phi_{ij}. (In particular, it is allowed that phi_{ij} is not equal to phi_{ji}, which captures possible asymmetric interference in real - most notably wireless - communication networks.) We derive results characterizing the maximum achievable link throughput region, and its Pareto boundary. In some cases, the Pareto boundary characterization is almost as simple and explicit as that derived in [7] for the Slotted Aloha system.