Article

Free access

A verified sliding window protocol with variable flow control

Author:

A U ShankarAuthors Info & Claims

SIGCOMM '86: Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols

Pages 84 - 91

https://doi.org/10.1145/18172.18183

Published: 01 August 1986 Publication History

PDF eReader

Abstract

We present a verified sliding window protocol which uses modulo-N sequence numbers to achieve reliable flow-controlled data transfer between a source and a destination. Communication channels are assumed to lose, duplicate and reorder messages in transit. The destination's data needs are represented by a receive window whose size can vary with time. The destination entity uses acknowledgement messages to inform the source entity of the current receive window size and the sequence number of the data word next expected. The source entity responds by sending segments of data words that lie within the allowed window. Each data segment is accompanied by an identifying sequence number and the size of the data segment. The destination entity also uses selective acknowledgement and selective reject messages to inform the source entity of the reception or lack of reception, respectively, of out-of-sequence data segments. Thus, this protocol is a proper extension of the Arpanet's TCP. We have obtained the minimum value of N that ensures correct data transfer and flow control, in terms of the minimum message transmission time, the maximum message lifetime, and the maximum receive window size. The protocol imposes no constraints on the retransmissions of messages or on the data segment sizes; thus, any retransmission policy that optimizes the protocol's performance can be used.

References

[1]

CCITT, Draft revised CCITT recommendation X.25, February 1980.

Google Scholar

[2]

Dijkstra, E. W., A Discipline of Programming, P~'ent{ee-Hall, Englewood Cliffs, N.J., 1076.

Digital Library

Google Scholar

[3]

DiVlto, B. L, "Mechanical verification of EL data transport p,'otoeol," Proe. ACM SIGCOMM '83, Austin, Texas, pp. 30-37, March 108a.

Google Scholar

[4]

Hailpern, B. T. and S. S. Owicki, "Modular verification of computer communication protocols," IEEE T~'ans. on Common., COM-31, 1, January 1083.

Google Scholar

[5]

Misre, J. and K. M. Chandy, "Prooh of Networks of Processes," IEEE Trans. Soft. E~g., Vol. SE-7, No. 4, July 1081.

Digital Library

Google Scholar

[6]

Postel, J. (ed.), "DOD Standa,'d T,'ansmlssion Control Protocol," Defense Advanced Research Projects Agency, Information Processing Techniques Office, RFC 761, IEN 129, January 1{)80; in A CM Computer Commu~icatio~ Review, Vol. 10, No. 4, October 1980, pp. 52-132.

Digital Library

Google Scholar

[7]

Shankar, A. U. and S. S. Lam, "Time-dependent communleation protocols," Tutorial: Principles of Communication and Networking Protocols, S. S. Lain (ed.), IEEE Computer Society, 1984.

Google Scholar

[8]

Shankar, A. U. and S. S. Lam, "Time-dependent distributed systems: proving safety, liveness and realtime properties," Teeh. Rep. CS-TR-I586, Computer Science Dept., Univ. of Maryland, also TR-85-24, Comi~uter Science Dept., Univ. of Texas, October 1985, (submitted to A CM TOPLAS).

Digital Library

Google Scholar

[9]

Shankar, A. U. and S. S. Lain, "Construction of sliding window protocols by stepwise refinement," Tech. Rep. CS-TR-1647, Computer Science Dept., Univ. of Maryland, February 1980.

Google Scholar

[10]

Shankar, A. U., "Verification of a time-dependent data transfer protocol," Tech. Rep., Computer Science Dept., Univ. of Maryland, (in preparation)

Google Scholar

[11]

Sloan, L., "Mechanisms that Enforce Bounds on Packet Lifetimes," A CM Trana. Comput. Syst., Vol. 1, No. d, Nov. 1983, pp. 311-330.

Digital Library

Google Scholar

[12]

Stenning, N. V., "A data transfer protocol," Computer Networks, Vol. 1, pp. 99-110, September 1976.

Google Scholar

Cited By

View all

Lam SShankar A(2005)Refinement and projection of relational specificationsStepwise Refinement of Distributed Systems Models, Formalisms, Correctness10.1007/3-540-52559-9_75(454-486)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-52559-9_75
Baraff DWitkin AKass M(2003)Untangling clothACM Transactions on Graphics10.1145/882262.88235722:3(862-870)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882357
Rasmussen NNguyen DGeiger WFedkiw R(2003)Smoke simulation for large scale phenomenaACM Transactions on Graphics10.1145/882262.88233522:3(703-707)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882335
Show More Cited By

Index Terms

A verified sliding window protocol with variable flow control

Recommendations

A verified sliding window protocol with variable flow control

We present a verified sliding window protocol which uses modulo-N sequence numbers to achieve reliable flow-controlled data transfer between a source and a destination. Communication channels are assumed to lose, duplicate and reorder messages in ...
Verified data transfer protocols with variable flow control

We present and verify a sliding window protocol which uses modulo-N sequence numbers to achieve reliable flow-controlled data transfer between a producer and a consumer connected by unreliable channels. The consumer's data needs are represented by a ...
Sliding window protocol with selective-repeat ARQ: performance modeling and analysis

A sliding window mechanism is well known to be a convenient way to integrate cumulative acknowledgement and flow control functions in a simple manner. Hence, widely used reliable data-transfer protocols such as TCP-SACK and RLC utilize this sliding ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGCOMM '86: Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols

September 1986

414 pages

ISBN:0897912012

DOI:10.1145/18172

ACM SIGCOMM Computer Communication Review Volume 16, Issue 3
Aug. 5, 1986
392 pages
ISSN:0146-4833
DOI:10.1145/1013812
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGCOMM86

Sponsor:

SIGCOMM

SIGCOMM86: ACM SIGCOMM Conference on Communications Architecture & Protocols

August 5 - 7, 1986

Vermont, Stowe, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
851
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lam SShankar A(2005)Refinement and projection of relational specificationsStepwise Refinement of Distributed Systems Models, Formalisms, Correctness10.1007/3-540-52559-9_75(454-486)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-52559-9_75
Baraff DWitkin AKass M(2003)Untangling clothACM Transactions on Graphics10.1145/882262.88235722:3(862-870)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882357
Rasmussen NNguyen DGeiger WFedkiw R(2003)Smoke simulation for large scale phenomenaACM Transactions on Graphics10.1145/882262.88233522:3(703-707)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882335
Décoret XDurand FSillion FDorsey J(2003)Billboard clouds for extreme model simplificationACM Transactions on Graphics10.1145/882262.88232622:3(689-696)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882326
Adams BDutré P(2003)Interactive boolean operations on surfel-bounded solidsACM Transactions on Graphics10.1145/882262.88232022:3(651-656)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882320
Pauly MKeiser RKobbelt LGross M(2003)Shape modeling with point-sampled geometryACM Transactions on Graphics10.1145/882262.88231922:3(641-650)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882319
Kwatra VSchödl AEssa ITurk GBobick A(2003)Graphcut texturesACM Transactions on Graphics10.1145/882262.88226422:3(277-286)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1145/882262.882264
Liu CRichardson D(2002)Research directions in RAICACM SIGSOFT Software Engineering Notes10.1145/638574.63858627:3(43-46)Online publication date: 1-May-2002
https://dl.acm.org/doi/10.1145/638574.638586
Inverardi P(2002)The SALADIN projectACM SIGSOFT Software Engineering Notes10.1145/638574.63858527:3(38-43)Online publication date: 1-May-2002
https://dl.acm.org/doi/10.1145/638574.638585
Nanevski A(2002)Meta-programming with names and necessityACM SIGPLAN Notices10.1145/583852.58149837:9(206-217)Online publication date: 17-Sep-2002
https://dl.acm.org/doi/10.1145/583852.581498
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A verified sliding window protocol with variable flow control

Verified data transfer protocols with variable flow control

Sliding window protocol with selective-repeat ARQ: performance modeling and analysis