Simulation study of the capacity effects of dispersity routing for fault tolerant realtime channels

ABSTRACT

The paper presents a simulation study of the use of dispersity routing to provide fault tolerance on top of a connection oriented realtime service such as that provided by the Tenet scheme. A framework to study the dispersity schemes is presented. The simulations show that the dispersity schemes, by dividing the connection's traffic among multiple paths in the network, have a beneficent effect on the capacity of the network. Thus, for certain classes of dispersity schemes, we obtain a small improvement in fault tolerance as well as an improvement in the number of connections that the network can support. For other classes of dispersity schemes, greater improvement in service may be purchased at the cost of decrease in capacity. The paper explores the tradeoffs available through exhaustive simulations. We conclude that dispersity routing is a flexible approach to increasing the fault tolerance of realtime connections, which can provide a range of improvements in service with a corresponding range of costs.

REFERENCES

• 1: A. Banerjea, "A taxonomy of dispersity routing schemes for fault tolerant realtime channels", European Conference on Multimedia Applications, Services and Techniques (ECMAST'96), Louvainla-Neuve, Belgium, May 1996.
• 2: N. F. Maxemchuk, "Dispersity Routing", Proceedings of ICC'75, San Francisco, California, June 1975, 41.10-41.13.
• 3: A. Albanese, J. B loemer, J. Edmonds and M. Luby, "Priority Encoding Transmission", 35th Annual Symposium on Foundations of Computer Science, 1994.
• 4: Anindo Banerjea , Domenico Ferrari , Bruce A. Mah , Mark Moran , Dinesh C. Verma , Hui Zhang, The Tenet real-time protocol suite: design, implementation, and experiences, IEEE/ACM Transactions on Networking (TON), v.4 n.1, p.1-10, Feb. 1996 [doi>10.1109/90.503757]
• 5: I. Cidon, I. Gopal and R. Guerin, "Bandwidth Management and Congestion Control in PlaNET", IEEE Communications Magazine, October 1991, 54-64.
• 6: D.P. Anderson, R. G. Herrtwich and C. Schaefer, "SRP: A Resource Reservation Protocol for Guaranteed Performance Communication in Interact", Tech. Rep.-90-006, International Computer Science Institute, Berkeley, California, February 1990.
• 7: C. Vogt, R. Herrtwich and R. Nagaragan, "HeiRAT - The Heidelberg Resource and Administration Technique: Design Philosophy and Goals", IBM Tech. Rep. 43.9243 , IBM ENC, Heidelberg, Germany, 1992.
• 8: Jay Hyman , Aurel A. Lazar , Giovanni Pacifici, MARS: the magnet II real-time scheduling algorithm, Proceedings of the conference on Communications architecture & protocols, p.285-293, September 03-06, 1991, Zurich, Switzerland
• 9: F.J. MacWilliams and N. J. A. Sloane, The theory of error correcting codes, North-Holland, New York, 1977.
• 10: A. Banerjea, C. Parris and D. Ferrari, "Recovering Guaranteed Performance Service Connections from Single and Multiple Faults", Proceedings of Globecom'94, San Francisco, November 1994, 162-168. Also available as Tech. Rep.-93-066, International Computer Science Institute, Berkeley, CA.
• 11: C. Parris, Dynamic Channel Management, University of California at Berkeley. PhD Thesis.
• 12: N. F. Maxemchuk, Dispersity routing in high-speed networks, Computer Networks and ISDN Systems, v.25 n.6, p.645-661, Jan. 1993 [doi>10.1016/0169-7552(93)90059-D]
• 13: Q. Ding and S. C. Liew, "A Performance Analysis of a Parallel Communications Scheme for ATM Networks", Proceedings of the IEEE GLOBECOMM'95, Singapore, November, 1995, 898-902.
• 14: L. Zhang, R. Braden, D. Estrin, S. Herzog and S. Jamin, Resource ReSerVation Protocol (RSVP) -- Version 1 Functional Specification, Internet Draft, May, 1996. available from ftp ://ds. in terni c .n e t/in tern e t-drafts/draft- i e tf- rs vpspec- 12.txt.
• 15: C. Partridge and S. Shenker, Specification of Guaranteed Quality of Service, Internet Draft, December, 1995. available from ftp ://ds. internic.net/internet- drafts/draft-ietf- int servguaranteed-svc-03.txt.
• 16: Anindo Banerjea, Fault management for real time networks, University of California at Berkeley, Berkeley, CA, 1995
• 17: S. Chiou and V. O. K. Li, "Diversity Transmissions in a Communication network with Unreliable Components", Proceedings of ICC'87, Seattle, Washington, June 1987, 968-973.
• 18: Q. Zheng and K. G. Shin, "Fault-tolerant real-time communication in distributed computing systems", Proceedings of the 22nd International Symposium on Fault-Tolerant Computing, Boston, MA, July 1992.
• 19: Qin Zheng , Kang G. Shin, Establishment of Isolated Failure Immune Real-Time Channels in HARTS, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.113-119, February 1995 [doi>10.1109/71.342122]
• 20: A. J. McAuley, Reliable broadband communication using a burst erasure correcting code, Proceedings of the ACM symposium on Communications architectures & protocols, p.297-306, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 21: E. Ayanoglu, C. I, R. D. Gitlin and J. E. Mazo, "Diversity coding: Using error control for self healing in communication networks", Proceedings of INFOCOM'90, San Francisco, California, June 1990, 95-104.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Performance