Access Restriction

Author Mansour, Yishay ♦ Schieber, Baruch
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1992
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Data link ♦ Lower bound ♦ Non-FIFO channels ♦ Sequence transmission
Abstract The efficiency of data-link protocols for reliable transmission of a sequence of messages over non-FIFO physical channels is discussed. The transmission has to be on-line; i.e., a message cannot be accessed by the transmitting station before the preceding message has been received. Three resources are considered: The number of packets that have to be sent, the number of headers, and the amount of space required by the protocol. Three lower bounds are proved. First, the space required by any protocol for delivering $\textit{n}$ messages that uses less than $\textit{n}$ headers cannot be bounded by any function of $\textit{n}.$ Second, the number of packets that have to be sent by any protocol that uses a fixed number of headers in order to deliver a message is linear in the number of packets that are delayed on the channel at the time the message is sent. Finally, the notion of a probabilistic physical channel, in which a packet can be delayed on the channel with probability $\textit{q},$ is introduced. An exponential lower bound, with overwhelming probability, is proved on the number of packets that have to be sent by any data-link protocol using a fixed number of headers when it is implemented over a probabilistic physical channel.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 39
Issue Number 4
Page Count 17
Starting Page 783
Ending Page 799

Open content in new tab

   Open content in new tab
Source: ACM Digital Library