A Modular Analysis of Network Transmission Protocols

TitleA Modular Analysis of Network Transmission Protocols
Publication TypeTechnical Report
Year of Publication1997
AuthorsAdler, M., Bartal Y., Byers J. W., Luby M., & Raz D.
Other Numbers1068

We describe a new model for the analysis of data transmission protocols in lossy communication networks. We study the performance of protocols in an adversarial setting where the loss pattern and latencies of packets are determined by an adversary. We advocate the modular decomposition of data transmission protocols into a time scheduling policy, which determines em when packets are to be sent, and a data selection policy, which determines what data is to be placed in each sent packet. We concentrate on the data selection policy and require that the protocol will achieve high bandwidth utilization in transmitting any prefix of the transmitted message. The simple and universal data selection policy we introduce is provably close to optimal in the following sense: For any time scheduling policy and em any network behavior, in the worst case prefix measure our data selection policy performs as well as any other data selection policy up to a constant additive term. Our explicit modular decomposition of a transmission protocol into two policies should be contrasted with existing network protocols such as TCP/IP. Our result shows that the performance of the overall transmission protocol would not degrade in performance (and could improve dramatically) if it used our universal data selection policy in place of its own. We therefore reduce the problem of designing a data transmission protocol to the task of designing a time scheduling policy.

Bibliographic Notes

ICSI Technical Report TR-97-001

Abbreviated Authors

M. Adler, Y. Bartal, J. W. Byers, M. Luby, and D. Raz

ICSI Publication Type

Technical Report