A New Binary Logarithmic Arbitration Method for Ethernet
Mart L. Molle · 1994
Abstract — Recently, Ethernet celebrated its twentieth anniversary. Over those years, the processing speed of the attached hosts has increased by several orders of magnitude, to the point where the relative bandwidth of a 10 Mbps Ethernet has fallen from more than adequate to support large enterprise networks (whose utilizations were typically only a few percent, anyway), to marginally fast enough to support a single high performance desktop workstation. At the same time, the Ethernet standard has also evolved to incorporate new technology at the physical layer, including new media, new signalling methods, and support for higher data rates. However, the MAC layer protocols have remained essentially unchanged from the early days of undemanding applications running on large numbers of slow hosts. In this paper, we argue that it is time to review the MAC layer and incorporate advances made in the protocol performance field over the last twenty years. First, we describe several little-known facts about the dynamic behaviour of the current Truncated Binary Exponential Backoff (BEB) algorithm, and explain how these features can cause significant performance problems for a variety of interesting network configurations. We then show that the backoff algorithm can be modified to eliminate all of these performance anomalies, without sacrificing performance or interoperability with existing Ethernet compatible devices. Indeed, the actual performance characteristics of the resulting algorithm, which we call the Binary Logarithmic