Fast restoration of real-time communication service from component failures in multi-hop networks

ABSTRACT

For many applications it is important to provide communication services with guaranteed timeliness and fault-tolerance at an acceptable level of overhead. In this paper, we present a scheme for restoring real-time channels, each with guaranteed timeliness, from component failures in multi-hop networks. To ensure fast/guaranteed recovery, backup channels are set up a priori in addition to each primary channel. That is, a dependable real-time connection consists of a primary channel and one or more backup channels. If a primary channel fails, one of its backup channels is activated to become a new primary channel. We describe a protocol which provides an integrated solution to the failure-recovery problem (i.e., channel switching, resource re-allocation, ...). We also present a resource sharing method that significantly reduces the overhead of backup channels. The simulation results show that good coverage (in recovering from failures) can be achieved with about 30% degradation in network utilization under a reasonable failure condition. Moreover, the fault-tolerance level of each dependable connection can be controlled, independently of other connections, to reflect its criticality.

REFERENCES

• ARA94: C. M. Aras, J. F. Kurose, D. S. Reeves, and H. Schulzrinne, "Real-time communication in packetswitched networks," Proceedings of the IEEB, vol. 82, pp. 122-139, January 1994.
• MCC96: Steven McCanne , Van Jacobson , Martin Vetterli, Receiver-driven layered multicast, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.117-130, August 28-30, 1996, Palo Alto, California, United States
• TRI82: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• WHA90: J. Whalen and J. Kenney, "Finding maximal link disjoint paths in a multigraph," in Proc. IEEE GLOBECOM, pp. 400-404, 1990.
• SID91: Deepinder Sidhu , Raj Nair , Shukri Abdallah, Finding disjoint paths in networks, Proceedings of the conference on Communications architecture & protocols, p.43-51, September 03-06, 1991, Zurich, Switzerland
• HAN97a: Seungjae Han , Kang G. Shin, Experimental Evaluation of Failure-Detection Schemes in Real-time Communication Networks, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.122, June 25-27, 1997
• ZHA93: L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP: A new Resource ReSerVation Protocol," IEEE Network, pp. 8-18, September 1993.
• HAN97b: S. Ran and K. G. Shin, "Efficient spaxe-resource allocation for fast restoration of real-time channels from network component failures," submitted for publication, 1997.
• RAM92: Parameswaran Ramanathan , Kang G. Shin, Delivery of time-critical messages using a multiple copy approach, ACM Transactions on Computer Systems (TOCS), v.10 n.2, p.144-166, May 1992 [doi>10.1145/128899.128902]
• KAO94: B. Kao , H. Garcia-Molina , D. Barbará, Aggressive Transmissions of Short Messages Over Redundant Paths, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.102-109, January 1994 [doi>10.1109/71.262594]
• BAN96: Anindo Banerjea, Simulation study of the capacity effects of dispersity routing for fault tolerant realtime channels, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.194-205, August 28-30, 1996, Palo Alto, California, United States
• BAN93: A. Banerjea, C. Parr.s, and D. Ferrari, "Recovering guaranteed performance service connections from single and multiple faults," Tech. Rep. TR-93-066, Computer Science Division, UC Berkeley, 1993.
• ZHE92: Q. Zheng and K. G. Shin, "Fault-tolerant realtime communication in distributed computing systems," in Proc. IEEE FTCS, pp. 86 - 93, 1992.
• GRO87: W. Grover, "The sel~ealing network: A fast distributed restoration technique for networks using digital crossconnect machines," in Proc. IEEE GLOBE. COM, pp. 1090-1095, 1987.
• YAN88: C. Yang and S. Hasegawa, ~FITNESS: Failure immunization technology for network service survivability," in Proc. IEEE GLOBECOM, pp. 1549-1554, 1988.
• BAK91: J. Baker, "A distributed link restoration algorithm with robust preplanning,' in Proc. IEEE GLOBE- COM, pp. 306-311, 1991.
• KAW94: R. Kawamura, K. Sato, and I. ToMzawa, "Selfhealing ATM networks based on virtual path concept," IEEE Journal on Selected Areas in Communications, vol. 12, pp. 120-127, January 1994.
• AND94: J. Anderson, B. Doshi, S. Dravida, and P. Hat~ shavadhana, "Fast restoration of ATM networks," IEEE Journal on Selected Areas in Communications, vol. 12, pp. 128-138, January 1994.
• MUR94: K. Murakami and It. Kim, "Near-optimal virtual path routing for survivable ATM networks," in Proc. IEEE INFOCOM, pp. 208-215, 1994.

INDEX TERMS

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

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

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Documentation, Reliability