A hierarchical solution for application level store-and-forward deadlock prevention

ABSTRACT

Application level message transfer systems, primarily used to transport electronic mail, have several unique characteristics that make using existing methods of dealing with deadlock impractical. The special requirements for the efficient transport of application level messages are discussed and a description of a hierarchical scheme that meets these requirements is given. For networks consisting of interconnected clusters of computers, the structured buffer pool technique can be combined with other deadlock-free message transport schemes to form a network-wide, deadlock-free message transport facility. A properly chosen hierarchical system has the advantages of the individual schemes while lessening the impact of their disadvantages. The hierarchical scheme is also applicable to packet-switched and datagram-based networks.

REFERENCES

• 1: Bta~.ewicz, Jacek, Brzezifiski, Jerzy, and Gambosi, Giorgio. "Time-Stamp Approach to Store-and- Forward Deadlock Prevention", IEEE Transactions on Comm., vol. COM-35, no. 5, (May 1987), pp. 490-495.
• 2: G. Bongiovanni , D. P. Bovet, Minimal deadlock-free store-and-forward communication networks, Networks, v.17 n.2, p.187-200, Summer 1987 [doi>10.1002/net.3230170205]
• 3: Brachman, Barry J. "EANft User's Guide", unpublished memorandum, University of British Columbia, Dept. of Computer Science, September 1986.
• 4: Brachman, Barry J., and Chanson, Samuel T. "Fragmentation in Store-and-Forward Message Transfer", IEEE Communications Magazine, vol. 26, no. 7, (July 1988), pp. 18-27.
• 5: Brachman, Barry J., and Chanson, S~muel T. "Flow and Congestion Control in the Message Handling Environment'', Proc. IEEE INFOCOM '89, 1989, pp. 721-730.
• 6: Barry Jeffrey Brachman , Samuel T. Chanson, Resource management in application level message transfer systems, 1989
• 7: Chan, Cheung-Wing, and Yurn, Tak-Shing. ~An Algorithm for Detecting and Resolving Store-and- Forward Deadlocks in Packet Switched Networks", IEEE Trans. on Comm., vol. COM-35, no. 8, (August 1987), pp. 801-807.
• 8: Jack J Dongarra , Eric Grosse, Distribution of mathematical software via electronic mail, Communications of the ACM, v.30 n.5, p.403-407, May 1987 [doi>10.1145/22899.22904]
• 9: Oiessler, A., H~nle, J., K~nig, A., and Pade, E. ~Free Buffer Allocation- An Investigation by Simulation', Computer Networks, vol. 2, 1978, pp. 191-208.
• 10: Giessler, Alfred, J~gemann, Annemarie, Mgser, Ellen, and H~nle, J~rgen. "Flow Control Based on Buffer Classes", IEEE Transactions on Comm., vol. COM- 29, no. 4, (April 1981), pp. 436-443.
• 11: GopM, Inder S. "Prevention of Store-and-Forward Deadlock in Computer Networks", IEEE Transactions on Comm., vol. COM-33, no. 12, (December 1985), pp. 1258-1264.
• 12: Ghnther, Klaus D. "Prevention of Deadlocks in Packet-Switched Data Transport Systems", IEEE Transactions on Comm., vol. COM-29, no. 4, (April 1981), pp. 512-524.
• 13: John H. Howard, Jr., Mixed solutions for the deadlock problem, Communications of the ACM, v.16 n.7, p.427-430, July 1973 [doi>10.1145/362280.362290]
• 14: Isloor, Sreek~anth S., and Marsland, T. Anthony. "The Deadlock Problem: An Overview", Computer, vol. 13, no. 9, (September 1980), pp. 58-78.
• 15: Merlin, Philip M., and Schweitzer, Paul J. "Deadlock Avoidance in Store-and-Forward Networks, Parts I and II',IEEE Transactions on Comm., vol. COM-28, no. 3 (March 1980), pp. 345-360.
• 16: C. Partridge , C. Mooers , M. Laubach, The CSNET information server: automatic document distribution using electronic mail, ACM SIGCOMM Computer Communication Review, v.17 n.4, p.3-10, Aug. 1987 [doi>10.1145/37530.37531]
• 17: John S. Quarterman , Josiah C. Hoskins, Notable computer networks, Communications of the ACM, v.29 n.10, p.932-971, Oct. 1986 [doi>10.1145/6617.6618]
• 18: John S. Quarterman, The matrix: computer networks and conferencing systems worldwide, Digital Press, Newton, MA, 1990
• 19: Raubold, E., and H~nle, J. "A Method of Deadlockfree Resource Allocation and Flow Control in Packet Networks", Proc. 8rd International Con/erence on Computer Communication, 1976, pp. 483-487.
• 20: Thomas, Robert H., Forsdick, Harry C., Crowley, Terfence R., Schaaf, Richard W., Tomlinson, Raymond S., and Travers, Virginia M. "Diamond: A Multimedia Message System Built on a Distributed Architectur&, Computer, vol. 18, no. 12, (December 1985), pp. 65-78.
• 21: Sam Toueg , Jeffrey D. Ullman, Deadlock-free packet switching networks, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.89-98, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804402]
• 22: Sam Toueg, Deadlock- and livelock-free packet switching networks, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.94-99, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804656]
• 23: Wimmer, Wolfgang. "Using Barrier Graphs for Deadlock Prevention in Communication Networks", IEEE Trans. on Communications, vol. COM-32, no. 8, (August 1984), pp. 897-901.
• 24: Willy Zwaenepoel, Protocols for large data transfers over local networks, Proceedings of the ninth symposium on Data communications, p.22-32, September 1985, Whistler Moutain, British Columbia, Canada

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:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Topology (e.g., bus, point-to-point)

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Electronic mail

General Terms:
Design, Performance