Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
复制标题
DOI：
10.1145/23005.23006
复制
发表时间：
1987-04
期刊：
影响因子：
--
通讯作者：
A. Greenberg;P. Flajolet;R. Ladner
中科院分区：
文献类型：
--
作者：
A. Greenberg;P. Flajolet;R. Ladner
新的，改进的算法，提出了调节访问多路访问通道，一个共同的信道共享的许多地理分布的计算站。当n个站同时向信道发送时，发生多重数n的冲突。结果，所有站接收指示n是0、1还是≥2的反馈。如果n = 1，则传输成功;而如果n ≥ 2，则所有传输失败。算法提出和分析，允许冲突的站计算随机估计n* 的n，合作，在小成本，作为其执行过程中引起的反馈的函数。解决两个或多个站之间冲突的算法控制冲突站的重传，使得每个站最终单独向信道发送。将我们的估计算法与树算法（Capetanakis，Hayes，Tsybakov和Mikhailov）相结合，然后导致冲突解决的混合算法。有几种有效的组合是可能的，其中最有效的解决冲突的速度比迄今为止报道的任何可比算法平均快20%。
New, improved algorithms are proposed for regulating access to a multiple-access channel, a common channel shared by many geographically distributed computing stations. A conflict of multiplicity n occurs when n stations transmit simultaneously to the channel. As a result, all stations receive feedback indicating whether n is 0, 1, or ≥2. If n = 1, the transmission succeeds; whereas if n ≥ 2, all the transmissions fail. Algorithms are presented and analyzed that allow the conflicting stations to compute a stochastic estimate n* of n, cooperatively, at small cost, as a function of the feedback elicited during its execution. An algorithm to resolve a conflict among two or more stations controls the retransmissions of the conflicting stations so that each eventually transmits singly to the channel. Combining one of our estimation algorithms with a tree algorithm (of Capetanakis, Hayes, and Tsybakov and Mikhailov) then leads to a hybrid algorithm for conflict resolution. Several efficient combinations are possible, the most efficient of which resolves conflicts about 20 percent faster on average than any of the comparable algorithms reported to date.