Abstract
Many governmental agencies and businesses organizations use networked systems to provide a number of services. Such a service-oriented network can be implemented as an overlay on top of the physical network. It is well recognized that the performance of many of the networked computer systems is severely degraded under node and edge failures. The focus of our work is on the resilience of service-oriented networks. We develop a graph theoretic model for service-oriented networks. Using this model, we propose metrics that quantify the resilience of such networks under node and edge failures. These metrics are based on the topological structure of the network and the manner in which services are distributed over the network. Based on this framework, we address two types of problems. The first type involves the analysis of a given network to determine its resilience parameters. The second type involves the design of networks with a given degree of resilience. We present efficient algorithms for both types of problems. Our approach for solving analysis problems relies on known algorithms for computing minimum cuts in graphs. Our algorithms for the design problem are based on a careful analysis of the decomposition of the given graph into appropriate types of connected components.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brightwell, G., Oriolo, G., Shepherd, F.: Reserving Resilient Capacity in a Network. SIAM J. Discrete Mathematics 14(4), 524–539 (2001)
Colbourn, C.: Network Resilience. SIAM J. Algebraic and Discrete Methods 8, 404–409 (1987)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press and McGraw-Hill, Cambridge (2001)
Cuenca-Acuna, F., Martin, R., Nguyen, T.: Autonomous Replication for High Availability in Unstructured P2P Systems. In: Proc. 22nd IEEE Symposium on Reliable Distributed Systems (SRDS 2003), Florence, Italy (August 2003)
Czerwinski, S., Zhao, B., Hodes, T., Joseph, A., Katz, R.: An Architecture for a Secure Service Discovery Service. In: Proc. ACM Symposium on Mobile Computing and Communications (MobiCom 1999), New York, NY, pp. 24–35 (August 1999)
Dabrowski, C., Mills, K., Elder, J.: Understanding Consistency Maintenance in Service Discovery Architectures in Response to Message Loss. In: Proc. 4th International Workshop on Active Middleware Services (WAMS 2002), pp. 51–60 (July 2002)
Dabrowski, C., Mills, K., Elder, J.: Understanding Consistency Maintenance in Service Discovery Architectures During Communication Failure. In: Proc. 3rd International Workshop on Software Performance (WOSP 2002), pp. 168–178 (July 2002)
Dabrowski, C., Mills, K., Rukhin, A.: Performance of Service-Discovery Architectures in Response to Node Failures. In: Proc. 2003 International Conference on Software Engineering Research and Practice (SERP 2003), pp. 95–101 (June 2003)
Douceur, J., Wattenhofer, R.: Optimizing File Availability in a Secure Serverless Distributed File System. In: Proc. 20th IEEE Symposium on Reliable Distributed Systems (SRDS 2001), New Orleans, LA, pp. 4–13 (October 2001)
Even, S.: Graph Algorithms. Computer Science Press, Rockville (1979)
Gedik, B., Liu, L.: Reliable Peer-to-Peer Information Monitoring Through Replication. In: Proc. 22nd IEEE Symposium on Reliable Distributed Systems (SRDS 2003), Florence, Italy (August 2003)
Georgatsos, P., Joens, Y. (eds.): Towards Resilient Networks and Services, ACTS Guidelines NIG-G5 (June 1999)
Goel, S., Belardo, S., Iwan, L.: A Resilient Network that can Operate Under Duress: Supporting Communication Between Government Agencies During Crisis Situations. In: Proc. Hawaii Intl. Conference on System Sciences (January 2003)
Goel, S., Talya, S., Sobolewski, M.: Service-Based P2P Overlay Network for Collaborative Problem Solving (March 2003) (submitted for publication)
Harary, F., Hayes, J.: Edge Fault Tolerance in Graphs. Networks 23(2), 135–142 (1993)
Helvik, B.: Dependability Issues in Smart Networks. In: Proc. 5th IFIP Conference on Intelligence in Networks, Thailand, pp. 53–76 (November 1999)
Hwang, F.: Comments on Network Resilience: A Measure of Network Fault Tolerance. IEEE Trans. Computers 43(12), 1451–1452 (1994)
Iamnitchi, A., Foster, I.: On Fully Decentralized Resource Discovery in Grid Environments. In: Proc. Intl. Workshop on Grid Computing, Denver, CO (November 2001)
Jalote, P.: Fault Tolerance in Distributed Systems. Prentice-Hall, Englewood Cliffs (1994)
Jha, S., Wing, J., Linger, R., Longstaff, T.: Survivability Analysis of Network Specifications. In: Proc. 2000 IEEE International Conference on Dependable Systems and Networks (DSN 2000), Workshop on Dependability Despite Malicious Faults, New York, NY (June 2000)
Loguinov, D., Kumar, A., Rai, V., Ganesh, S.: Graph-Theoretic Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience. In: Proc. ACM SIGCOMM 2003, Karlsruhe, Germany, pp. 395–406 (August 2003)
Massoulie, L., Kermarrec, A., Ganesh, A.: Network Awareness and Failure Resilience in Self-Organizing Overlay Networks. In: Proc. 22nd IEEE Symposium on Reliable Distributed Systems (SRDS 2003), Florence, Italy (August 2003)
Moitra, S., Oki, E., Yamanaka, N.: Some New Survivability Measures for Network Analysis and Design. IEICE Trans. Communications E80-B(4), 625–631 (1997)
Najjar, W., Gaudiot, J.: Network Resilience: A Measure of Network Fault Tolerance. IEEE Trans. Computers 39(2), 174–181 (1990)
Pradhan, D. (ed.): Fault-Tolerant Computing: Theory and Techniques, vol. I, II. Prentice-Hall, Englewood Cliffs (1986)
Saif, U., Paluska, J.: Service-Oriented Network Sockets., Technical Report, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA (2003)
Singhal, M.: Research in High-Confidence Distributed Information Systems. In: Proc. 20th IEEE Symposium on Reliable Distributed Systems (SRDS 2001), New Orleans, LA, pp. 76–77 (October 2001)
Stoer, M., Wagner, F.: A Simple Min-Cut Algorithm. J. ACM 44(4), 585–591 (1997)
West, D.: Introduction to Graph Theory. Prentice-Hall, Inc., Englewood Cliffs (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rosenkrantz, D.J., Goel, S., Ravi, S.S., Gangolly, J. (2005). Structure-Based Resilience Metrics for Service-Oriented Networks. In: Dal Cin, M., Kaâniche, M., Pataricza, A. (eds) Dependable Computing - EDCC 5. EDCC 2005. Lecture Notes in Computer Science, vol 3463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11408901_26
Download citation
DOI: https://doi.org/10.1007/11408901_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25723-3
Online ISBN: 978-3-540-32019-7
eBook Packages: Computer ScienceComputer Science (R0)