Article

Free access

An axiomatic basis for communication

Authors:

Martin Karsten,

Sanjiva Prasad,

Mirza BegAuthors Info & Claims

SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications

Pages 217 - 228

https://doi.org/10.1145/1282380.1282405

Published: 27 August 2007 Publication History

Abstract

The de facto service architecture of today's communication networks, in particular the Internet, is heterogeneous, complex, ad hoc, and not particularly well understood. With layering as the only means for functional abstraction, and even this violated by middle-boxes, the diversity of current technologies can barely be expressed, let alone analyzed. As a first step to remedying this problem, we present an axiomatic formulation of fundamental forwarding mechanisms in communication networks. This formulation allows us to express precisely and abstractly the concepts of naming and addressing and to specify a consistent set of control patterns and operational primitives, from which a variety of communication services can be composed. Importantly, this framework can be used to (1) formally analyze network protocols based on structural properties, and also to (2) derive working prototype implementations of these protocols. The prototype is implemented as a universal forwarding engine, a general framework and runtime environment based on the Click router.

References

[1]

B. Ahlgren, M. Brunner, L. Eggert, R. Hancock, and S. Schmid. Invariants: A New Design Methodology for Network Architectures. In Proceedings of the ACM SIGCOMM Workshop on Future Directions in Network Architecture, Portland, OR, USA, pages 65--70, August 2004.

Digital Library

[2]

B. Ahlgren, L. Eggert, B. Ohlman, J. Rajahalme, and A. Schieder. Names, Addresses and Identities in Ambient Networks. In Proceedings of the 1st ACM Workshop on Dynamic Interconnection of Networks, Cologne, Germany, pages 33--37, September 2005.

Digital Library

[3]

H. Balakrishnan, K. Lakshminarayanan, S. Ratnasamy, S. Shenker, I. Stoica, and M. Walfish. A Layered Naming Architecture for the Internet. In Proceedings of SIGCOMM '04, Portland, OR, USA, pages 343--352, August 2004.

Digital Library

[4]

G. Chandranmenon and G. Varghese. Trading Packet Headers for Packet Processing. IEEE/ACM Transactions on Networking, 4(2):141--152, 1996.

Digital Library

[5]

D. Clark. The Design Philosophy of the DARPA Internet Protocols. In Proceedings of SIGCOMM '88, Stanford, CA, USA, pages 106--114, August 1988.

Digital Library

[6]

K. Fall. A Delay-Tolerant Network Architecture for Challenged Internets. In Proceedings of SIGCOMM '03, Karlsruhe, Germany, pages 27--34, August 2003.

Digital Library

[7]

Mohamed G. Gouda. Elements of network protocol design. John Wiley & Sons, Inc., New York, NY, USA, 1998.

Digital Library

[8]

T. G. Griffin and J. L. Sobrinho. Metarouting. In Proceedings of SIGCOMM '05, Philadelphia, PA, USA, pages 1--12, August 2005.

Digital Library

[9]

M. Gritter and D. R. Cheriton. An Architecture for Content Routing Support in the Internet. In Proceedings of USITS 2001, San Francisco, CA, USA, pages 37--48, March 2001.

Digital Library

[10]

C. A. R. Hoare. An Axiomatic Basis for Computer Programming. Communications of the ACM, 12(10):576--580, October 1969.

Digital Library

[11]

N. C. Hutchinson and L. L. Peterson. The x-Kernel: An Architecture for Implementing Network Protocols. IEEE Transactions on Software Engineering, 17(1):64--76, January 1991.

Digital Library

[12]

D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Tomasz Imielinski and Hank Korth, editors, Mobile Computing, pages 153--181. Kluwer Academic Publishers, 1996. Chapter 5.

[13]

M. Karsten, S. Keshav, and S. Prasad. An Axiomatic Basis for Communication. In 5th ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets V), Irvine, CA, USA.

Digital Library

[14]

E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek. The Click Modular Router. ACM Transactions on Computer Systems (TOCS), 18(3):263--297, August 2000.

Digital Library

[15]

X. Liu, C. Kreitz, R. Renesse, J. Hickey, M. Hayden, K. Birman, and R. Constable. Building Reliable, High-Performance Communication Systems from Components. In Proceedings of SOSP 1999, Kiawah Island, SC, USA, pages 80--92, December 1999.

Digital Library

[16]

B. Loo, J. Hellerstein, I. Stoica, and R. Ramakrishnan. Declarative Routing: Extensible Routing with Declarative Queries. In Proceedings of SIGCOMM '05, Philadelphia, PA, USA, pages 289--300, August 2005.

Digital Library

[17]

C. Partridge, T. Mendez, and W. Milliken. RFC 1546 - Host Anycasting Service, November 1993.

Digital Library

[18]

J. H. Saltzer. Naming and Binding of Objects. Lecture Notes in Computer Science, 60:99--208, 1978.

Digital Library

[19]

M. Schroeder, A. Birrell, M. Burrows, H. Murray, R. Needham, T. Rodeheffer, E. Satterthwaite, and C. Thacker. Autonet: a High-speed, Self-configuring Local Area Network Using Point-to-point Links. IEEE Journal on Selected Areas in Communications, 9(8):1318--1335, 1991.

Digital Library

[20]

J. Scott, P. Hui, J. Crowcroft, and C. Diot. Haggle: A Networking Architecture Designed Around Mobile Users. In Proceedings of the 3rd Annual Conference on Wireless On demand Network Systems and Services (WONS 2006), Les Mnuires, France, January 2006.

[21]

I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana. Internet Indirection Infrastructure. IEEE/ACM Transactions on Networking, 12(2):205--218, April 2004.

Digital Library

[22]

I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. IEEE Transactions on Networking, 11:17--32, February 2003.

Digital Library

[23]

F. Tip. A Survey of Program Slicing Techniques. Centrum voor Wiskunde en Informatica, 1994.

[24]

Y. Wang, J. Touch, and J. Silvester. A Unified Model for End Point Resolution and Domain Conversion for Multi-Hop, Multi-Layer Communication. Technical Report ISI-TR-590, USC/ISI, June 2004.

[25]

P. Zave. Compositional Binding in Network Domains. In Proceedings of the 14th International Symposium on Formal Methods, Hamilton, Canada, pages 332--347, August 2006.

Digital Library

Cited By

MORIGUCHI SMORISHIMA TGOTO MTAKAHASHI K(2016)Verification of Content-Centric Networking Using Proof AssistantIEICE Transactions on Communications10.1587/transcom.2016NEP0013E99.B:11(2297-2304)Online publication date: 2016
https://doi.org/10.1587/transcom.2016NEP0013
Houidi ZZegura EFord BSnoeren A(2016)A Knowledge-Based Systems Approach to Reason About NetworkingProceedings of the 15th ACM Workshop on Hot Topics in Networks10.1145/3005745.3005758(22-28)Online publication date: 9-Nov-2016
https://dl.acm.org/doi/10.1145/3005745.3005758
Moriguchi SMorishima TGoto MTakahashi K(2015)Formalization of the Behavior of Content-Centric NetworkingProcedia Computer Science10.1016/j.procs.2015.07.19756(197-204)Online publication date: 2015
https://doi.org/10.1016/j.procs.2015.07.197
Show More Cited By

Index Terms

An axiomatic basis for communication
1. Networks
  1. Network types

Recommendations

An axiomatic basis for communication

The de facto service architecture of today's communication networks, in particular the Internet, is heterogeneous, complex, ad hoc, and not particularly well understood. With layering as the only means for functional abstraction, and even this violated ...
Mobile IPv6-based ad hoc networks: its development and application

The Internet protocol version 6 (IPv6)-enabled network architecture has recently attracted much attention. In this paper, we address the issue of connecting mobile ad hoc networks (MANETs) to global IPv6 networks, while supporting IPv6 mobility. ...
Broadcast Channels in Estelle
Special issue on protocol engineering

Using notation consistent with the Estelle ISO 9074 International Standard, the syntax and formal semantics for a broadcast channel are presented. These semantics make precise the meaning of an intuitive concept and additionally are compatible with ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications

August 2007

432 pages

ISBN:9781595937131

DOI:10.1145/1282380

General Chairs:
Jun Murai
Keio University, Japan
,
Kenjiro Cho
IIJ, Japan

ACM SIGCOMM Computer Communication Review Volume 37, Issue 4
October 2007
420 pages
ISSN:0146-4833
DOI:10.1145/1282427
Issue’s Table of Contents

Copyright © 2007 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCOMM07

Sponsor:

SIGCOMM07: ACM SIGCOMM 2007 Conference

August 27 - 31, 2007

Kyoto, Japan

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
846
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)6

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

MORIGUCHI SMORISHIMA TGOTO MTAKAHASHI K(2016)Verification of Content-Centric Networking Using Proof AssistantIEICE Transactions on Communications10.1587/transcom.2016NEP0013E99.B:11(2297-2304)Online publication date: 2016
https://doi.org/10.1587/transcom.2016NEP0013
Houidi ZZegura EFord BSnoeren A(2016)A Knowledge-Based Systems Approach to Reason About NetworkingProceedings of the 15th ACM Workshop on Hot Topics in Networks10.1145/3005745.3005758(22-28)Online publication date: 9-Nov-2016
https://dl.acm.org/doi/10.1145/3005745.3005758
Moriguchi SMorishima TGoto MTakahashi K(2015)Formalization of the Behavior of Content-Centric NetworkingProcedia Computer Science10.1016/j.procs.2015.07.19756(197-204)Online publication date: 2015
https://doi.org/10.1016/j.procs.2015.07.197
Crowcroft JFidler MNahrstedt KSteinmetz R(2013)Is SDN the de-constraining constraint of the future internet?ACM SIGCOMM Computer Communication Review10.1145/2541468.254147243:5(13-18)Online publication date: 4-Nov-2013
https://dl.acm.org/doi/10.1145/2541468.2541472
Lu ZSteinmuller CMukhopadhyay S(2013)Towards Formal Verification of a Commercial Wireless Router FirmwareProceedings of the 2013 IEEE 37th Annual Computer Software and Applications Conference10.1109/COMPSAC.2013.103(639-647)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1109/COMPSAC.2013.103
Zave PRexford J(2013)Compositional Network MobilityRevised Selected Papers of the 5th International Conference on Verified Software: Theories, Tools, Experiments - Volume 816410.1007/978-3-642-54108-7_4(68-87)Online publication date: 17-May-2013
https://dl.acm.org/doi/10.1007/978-3-642-54108-7_4
Kazemian PVarghese GMcKeown NGribble SKatabi D(2012)Header space analysisProceedings of the 9th USENIX conference on Networked Systems Design and Implementation10.5555/2228298.2228311(9-9)Online publication date: 25-Apr-2012
https://dl.acm.org/doi/10.5555/2228298.2228311
Sommers JBarford PLiblit B(2012)A router primitive approach for building diverse network services2012 Fourth International Conference on Communication Systems and Networks (COMSNETS 2012)10.1109/COMSNETS.2012.6151319(1-10)Online publication date: Jan-2012
https://doi.org/10.1109/COMSNETS.2012.6151319
Partridge C(2011)Forty data communications research questionsACM SIGCOMM Computer Communication Review10.1145/2043165.204317041:5(24-35)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2043165.2043170
Koradia ZPremi ABalachandran CSeth ADearden AParikh TSubramanian L(2010)Using ICTs to meet the operational needs of community radio stations in IndiaProceedings of the First ACM Symposium on Computing for Development10.1145/1926180.1926207(1-9)Online publication date: 17-Dec-2010
https://dl.acm.org/doi/10.1145/1926180.1926207
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents