A structured TCP in standard ML.

ABSTRACT

This paper describes the design of an implementation of the Transmission Control Protocol using an extension of the Standard ML (SML) language. SML supports higher-order functions, modularity, and type-safe module composition. We find that by using SML we can achieve good structure and good performance simultaneously. Good structure includes a modular decomposition of the protocol stack and of the TCP implementation, a control structure that imposes a total ordering on all events and processes them synchronously, and a test structure that allows component testing to catch problems before system integration. Strategies that help achieve good performance include using fast algorithms, using language constructs that make it easy to stage function evaluation, and language implementation features such as compacting garbage collection.

REFERENCES

• 1: Andrew W. Appel, A runtime system, Lisp and Symbolic Computation, v.3 n.4, p.343-380, Nov. 1990 [doi>10.1007/BF01807697]
• 2: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In J. Maluszynski and M. Wirsing, editors, Third International Symposium on Programming Languages Implementation and Logic Programming, pages 1-13, New York, August 1991. Springer- Verlag.
• 3: Edoardo Biagioni , Robert Harper , Peter Lee , Brian G. Milnes, Signatures for a network protocol stack: a systems application of Standard ML, Proceedings of the 1994 ACM conference on LISP and functional programming, p.55-64, June 27-29, 1994, Orlando, Florida, United States
• 4: R. Braden, D. Borman, and C. Partridge. Computing the internet checksum. RFC 1071, September 1988.
• 5: D. D. Clark , D. L. Tennenhouse, Architectural considerations for a new generation of protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.200-208, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 6: David D. Clark, The structuring of systems using upcalls, Proceedings of the tenth ACM symposium on Operating systems principles, p.171-180, December 1985, Orcas Island, Washington, United States
• 7: David D. Clark, Van Jacobson, John Romkey, and Howard Salwen. An analysis of TCP processing overhead. IEEE Communications, 27(6), June 1989.
• 8: USC Information Sciences Institute. Transmission control protocol. RFC 793, September 1981.
• 9: Jonathan Kay , Joseph Pasquale, The importance of non-data touching processing overheads in TCP/IP, Conference proceedings on Communications architectures, protocols and applications, p.259-268, September 13-17, 1993, San Francisco, California, United States
• 10: Chris Maeda , Brian N. Bershad, Protocol service decomposition for high-performance networking, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.244-255, December 05-08, 1993, Asheville, North Carolina, United States
• 11: Robin Milner , Mads Tofte, Commentary on standard ML, MIT Press, Cambridge, MA, 1991
• 12: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 13: David A. Moon, Symbolics architecture, Computer, v.20 n.1, p.43-52, Jan. 1987 [doi>10.1109/MC.1987.1663356]
• 14: Scott Nettles , James O'Toole, Real-time replication garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.217-226, June 21-25, 1993, Albuquerque, New Mexico, United States
• 15: iETF Network Working Group. Requirements for internet hosts -communication layers. RFC 1122, October 1989.
• 16: Sean W. O'Malley , Larry L. Peterson, A dynamic network architecture, ACM Transactions on Computer Systems (TOCS), v.10 n.2, p.110-143, May 1992 [doi>10.1145/128899.128901]
• 17: M. Persson, K. Odling, and D. Eriksson. A switching software architecture prototype using real time declarative language. In international Switching Symposium, Yokohama, 25- 30 October 1992.
• 18: R. Rashid, R. Baron, A. Forin, D. Golub, M. Jones, D. Orr, and R. Sanzi. MACH: a foundation for open systems (operating systems). In Workstation Operating Systems: Proceedings of the Second Workshop on Workstation Operating Systems, Sept 1989.
• 19: John H. Reppy, CML: A higher concurrent language, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.293-305, June 24-28, 1991, Toronto, Ontario, Canada
• 20: Christian Tschudin, Flexible protocol stacks, Proceedings of the conference on Communications architecture & protocols, p.197-205, September 03-06, 1991, Zurich, Switzerland
• 21: B. Zorn and P. Hilfinger. A memory allocation proffer for C and Lisp programs. In Proceedings of the Summer 1988 USENIX Conference, San Francisco, June 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: ML

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Languages, Performance, Standardization