Network locality at the scale of processes

ABSTRACT

Packets on a LAN can be viewed as a series of references to and from the objects they address. The amount of locality in this reference stream may be critical to the efficiency of network implementations, if the locality can be exploited through caching or scheduling mechanisms. Most previous studies have treated network locality with an addressing granularity of networks or individual hosts. This paper describes some experiments tracing locality at a finer grain, looking at references to individual processes, and with fine-grained time resolution. Observations of typical LANs show high per-process locality; that is, packets to a host usually arrive for the process that most recently sent a packet, and often with little intervening delay.

REFERENCES

• 1: AMER, P. D. A measurement center for the NBS Local Area Computer Center. IEEE Trans. Comput. C-31, 8 (Aug. 1982), 723-729.
• 2: AMER, P., KUMAR, R., KAO, R., PHILLIPS, J., AND CASSEL, L Local area broadcast network measurement: Traffic characterization. In Proceedings of the Spr~ng COMPCON (San Francisco, 1987). IEEE Computer Society, New York, 1987, pp. 64-70.
• 3: BoGcs, D. R., SHOCH, J. F., TAFT, E. A., AND METCALFE, M. R. Pup: An internetwork architecture. IEEE Trans. Commun. COM-28, 4 (Apr. 1980), 612-624.
• 4: Ramón Cáceres , Peter B. Danzig , Sugih Jamin , Danny J. Mitzel, Characteristics of wide-area TCP/IP conversations, Proceedings of the conference on Communications architecture & protocols, p.101-112, September 03-06, 1991, Zurich, Switzerland
• 5: J. B. Carter , W. Zwaenepoel, Optimistic implementation of bulk data transfer protocols, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.61-69, May 23-26, 1989, Oakland, California, United States
• 6: CHERITON D. VMTP Protocol Specifzcation. RFC 1045, Network Information Center, SRI International, Feb. 1988.
• 7: David R. Cheriton , Willy Zwaenepoel, The distributed V kernel and its performance for diskless workstations, Proceedings of the ninth ACM symposium on Operating systems principles, p.129-140, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 8: CHE~TTON, D. R. A~D WmLrAMSON, C. L. Network measurement of the VMTP requestresponse protocol in the V distributed system In Procee&ngs of the 1987 SIGMETRICS Conference (Banff, Alberta, Oct. 1987). ACM, New York, pp. 128-140.
• 9: FELDMEmR, D. C. Traffic measurements on a token ring network. In Proceedings of the 1986 Computer Networking Symposium (Washington, D.C , Nov. 1986). pp. 236-243.
• 10: FELDMEmR, D.C. hnproving gateway performance with a routing-table cache In Proceedings of the IEEE InfoCom '88 (New Orleans, Mar. 1988). IEEE, New York, pp. 298-307.
• 11: Riccardo Gusella, The Analysis of Diskless Workstation Traffic on an Ethernet, University of California at Berkeley, Berkeley, CA, 1987
• 12: HEmHCH, S.A. Traffic characterization of the NFSNET national backbone. In Proceedings of the Winter 199o USENIX ConfereT~ce (Washington, D.C., Jan. 1990). pp. 207 227.
• 13: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 14: JAIN, R, AND ROUTItlER, S Packet trains: Measurements and a new model for computer network traffic IEEE J. Sel. Areas Commun SAC4, 6 (Sept. 1986), 986-995.
• 15: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• 16: P. Karn , C. Partridge, Improving round-trip time estimates in reliable transport protocols, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.2-7, August 11-13, 1987, Stowe, Vermont, United States
• 17: LELAND, W. E., AND WmSON, D.V. High time-resolution measurement and analysis of LAN traffic: Implications for LAN interconnection In Proceedings of the IEEE lnfoCom '91, (Bal Harbour, Fla., Apr. 1991). pp. 1360-1366.
• 18: Mark J. Lorence , M. Satyanarayanan, IPwatch: a tool for monitoring network locality, ACM SIGOPS Operating Systems Review, v.24 n.1, p.58-80, Jan. 1990 [doi>10.1145/90994.91007]
• 19: MOGUL, J C. Simple and flexible datagram access controls for Unix-based gateways. In Procee&ngs of the Summer 1989 USENIX Conference (Baltimore, Md, June 1989). pp 203-221
• 20: J. Mogul, Efficient use of workstations for passive monitoring of local area networks, Proceedings of the ACM symposium on Communications architectures & protocols, p.253-263, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 21: Jeffrey C. Mogul , Anita Borg, The effect of context switches on cache performance, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.75-84, April 08-11, 1991, Santa Clara, California, United States
• 22: J. Mogul , R. Rashid , M. Accetta, The packer filter: an efficient mechanism for user-level network code, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.39-51, November 08-11, 1987, Austin, Texas, United States
• 23: NAGLE, J. On packet switches with infinite storage. IEEE Trans Commun. COM-35, 4 (Apr 1987), 435-438.
• 24: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 25: Bill Nowicki, Transport issues in the network file system, ACM SIGCOMM Computer Communication Review, v.19 n.2, p.16-20, April 1, 1989 [doi>10.1145/378444.378447]
• 26: OUSTERHOUT, J. K Scheduling techniques for concurrent systems In Proceedings of the 3rd International Conference on Distributed Computing Systems (Oct 1982). pp 22-30
• 27: OUSTERHOUT, J K. Why aren't operating systems getting faster as fast as hardware? In Proceedings of the Summer 1990 USENIX Conference (Anaheim, Cahf, June 1990). pp. 247 256.
• 28: PARTRIDGE, C. AND PINK, S. A faster UDP. In Proceedings of the 2r~d MuIttG Workshop (Stockholm, June 1991). pp 57-64. Submitted to IEEE Transactmns on Communicatmn~
• 29: PLUMMER, D. An Ethernet Address Resolution Protocol. RFC 826, Network Informatmn Center, SRI International, Sept. 1982.
• 30: POSTEL, J.B. User Datagram Protocol RFC 768, Network Information Center, SRI International, Aug. 1980.
• 31: POSTEL, J. B Internet Protocol. RFC 791, Network Information Center~ SRI International, Sept, 1981.
• 32: POSTEL, J.B. Transmission Co~ztrol Protocol. RFC 793, Network Information Center, SRI International, Dept. 1~51.
• 33: POSTEL, J. B Internet CoT~trol Message Protocol RFC 792, Network Information Center, SRI International, Sept. 1981
• 34: Richard F. Rashid , George G. Robertson, Accent: A communication oriented network operating system kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.64-75, December 14-16, 1981, Pacific Grove, California, United States
• 35: SC~ROEDER, M. D., BmRELL~ A. D., BURROWS, M., MURRAY, H., NEEDHAM. R. M., RODEHEF- FER, T L., SATTERTHW^ITE, E H, AND TSACKER, C P. Autonet: A high-speed, self configuring local area network using point-to-point links. Res. Rep. 59, Digital Equipment Corporation Systems Research Center, April 1990
• 36: John F. Shoch , Jon A. Hupp, Measured performance of an Ethernet local network, Communications of the ACM, v.23 n.12, p.711-721, Dec. 1980 [doi>10.1145/359038.359044]
• 37: SUN MICROSYSTEMS, INC. RPC: Remote Procedure Call Protocol Specification Versmn 2. RFC 1057, Network Information Center, SRI International, June 1988.
• 38: SUN MICROSYSTEMS, INC. NFS: Network File System Protocol Specification. RFC 1094, Network Information Center, SRI International, Mar. 1989.
• 39: SYSTEMS PERI*ORMANCE EVALUATION COOPERATIVE. Newsl. 2, 1 (1990)
• 40: Andrew S. Tanenbaum, Computer Networks, Prentice Hall PTR, Upper Saddle River, NJ, 1985
• 41: WAITZ, A.A. PMAX microsecond Clock. 1990~ Unpublished design document.
• 42: WILLIAMSON, C.L. Dynamic transport-level connection management m a distributed system. In Proceedings of the 14th Conference on Local Computer Networks (Minneapolis, Minn., Oct. 1989). pp 315-322.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

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

          Nouns: TCP/IP
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Measurement techniques

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
context switching, dallying, locality of reference, remote procedure calls