The problem of designing a cost-efficient network that survives the failure of one or more nodes or edges of the network is critical to modern telecommunications engineering. The method developed in this book is designed to solve such problems to optimality. In particular, a cutting plane approach is described, based on polyhedral combinatorics, that is ableto solve real-world problems of this type in short computation time. These results are of interest for practitioners in the area of communication network design. The book is addressed especially to the combinatorial optimization community, but also to those who want to learn polyhedral methods. In addition, interesting new research problemsare formulated.

These days, the nature of services and the volume of demand in the telecommu nication industry is changing radically, with the replacement of analog transmis sion and traditional copper cables by digital technology and fiber optic transmis sion equipment. Moreover, we see an increasing competition among providers of telecommunication services, and the development of a broad range of new services for users, combining voice, data, graphics and video. Telecommunication network planning has thus become an important problem area for developing and applying optimization models. Telephone companies have initiated extensive modeling and planning efforts to expand and upgrade their transmission facilities, which are, for most national telecommunication networks, divided in three main levels (see Balakrishnan et al. [5]), namely, l. the long-distance or backbone network that typically connects city pairs through gateway nodes; 2. the inter-office or switching center network within each city, that interconnects switching centers in different subdivisions (clusters of customers) and provides access to the gateway(s) node(s); 1 2 DESIGN OF SURVNABLE NETWORKS WITH BOUNDED RINGS 3. the local access network that connects individual subscribers belonging to a cluster to the corresponding switching center. These three levels differ in several ways including their design criteria. Ideally, the design of a telecommunication network should simultaneously account for these three levels. However, to simplify the planning task, the overall planning problem is decomposed by considering each level separately.

Survivable Networks: Algorithms for Diverse Routing provides algorithms for diverse routing to enhance the survivability of a network. It considers the common mesh-type network and describes in detail the construction of physically disjoint paths algorithms for diverse routing. The algorithms are developed in a systematic manner, starting with shortest path algorithms appropriate for disjoint paths construction. Key features of the algorithms are optimality and simplicity. Although the algorithms have been developed for survivability of communication networks, they are in a generic form, and thus applicable in other scientific and technical disciplines to problems that can be modeled as a network. A notable highlight of this book is the consideration of real-life telecommunication networks in detail. Such networks are described not only by nodes and links, but also by the actual physical elements, called span nodes and spans. The sharing of spans (the actual physical links) by the network (logical) links complicates the network, requiring new algorithms. This book is the first one to provide algorithms for such networks. Survivable Networks: Algorithms for Diverse Routing is a comprehensive work on physically disjoint paths algorithms. It is an invaluable resource and reference for practicing network designers and planners, researchers, professionals, instructors, students, and others working in computer networking, telecommunications, and related fields.

Covers these key topics: Shared-mesh protection for optical WDM networks. Survivable traffic grooming for hierarchical optical WDM networks. Survivable data over next-generation SONET/SDH with inverse multiplexing.

Nowadays, graph theory is an important analysis tool in mathematics and computer science. Because of the inherent simplicity of graph theory, it can be used to model many different physical and abstract systems such as transportation and communication networks, models for business administration, political science, and psychology and so on. The purpose of this book is not only to present the latest state and development tendencies of graph theory, but to bring the reader far enough along the way to enable him to embark on the research problems of his own. Taking into account the large amount of knowledge about graph theory and practice presented in the book, it has two major parts: theoretical researches and applications. The book is also intended for both graduate and postgraduate students in fields such as mathematics, computer science, system sciences, biology, engineering, cybernetics, and social sciences, and as a reference for software professionals and practitioners.

This comprehensive handbook brings together experts who use optimization to solve problems that arise in telecommunications. It is the first book to cover in detail the field of optimization in telecommunications. Recent optimization developments that are frequently applied to telecommunications are covered. The spectrum of topics covered includes planning and design of telecommunication networks, routing, network protection, grooming, restoration, wireless communications, network location and assignment problems, Internet protocol, World Wide Web, and stochastic issues in telecommunications. The book’s objective is to provide a reference tool for the increasing number of scientists and engineers in telecommunications who depend upon optimization.

In this dissertation, a new spare capacity planning methodology is proposed utilizing path restoration. The approach is based on forcing working flows/traffic which are on paths that are disjoint to share spare backup capacity. The algorithm for determining the spare capacity assignment is based on genetic algorithms and is capable of incorporating non-linear variables such as non-linear cost function and QoS variables into the objective and constraints. The proposed methodology applies to a wider range of fault scenarios than most of the current literature. It can tolerate link-failures, node-failures, and link-and-node failures. It consists of two stages: the first stage generates a set of network topologies that maximize the sharing between backup paths by forcing them to use a subset of the original network. The second stage utilizes a genetic algorithm to optimize the set of solutions generated by the first stage to achieve an even better final solution. It can optimize the solution based on either minimizing spare capacity or minimizing the total network cost. In addition, it can incorporate QoS variables in both the objective and constraints to design a survivable network that satisfies QoS constraints. Numerical results comparing the proposed methodology to Integer Programming techniques and heuristics from the literature are presented showing the advantages of the technique. The proposed methodology was applied on 4 different size networks based on spare capacity optimization criteria and it was found that it achieved solutions that were on average 9.3% better than the optimal solution of the IP design that is based on link-restoration. It also achieved solutions that were on average 22.2 % better than the previous heuristic SLPA. The proposed methodology is very scalable. It was applied on networks with different sizes ranging from a 13-node network to a 70-node network. It was able to solve the 70-node network in less than one hour on a Pentium II PC. The curve-fitting of the empirical execution time of the methodology was found to be O(n3).

In today’s fast paced, infocentric environment, professionals increasingly rely on networked information technology to do business. Unfortunately, with the advent of such technology came new and complex problems that continue to threaten the availability, integrity, and confidentiality of our electronic information. It is therefore absolutely imperative to take measures to protect and defend information systems by ensuring their security and non-repudiation. Information Assurance skillfully addresses this issue by detailing the sufficient capacity networked systems need to operate while under attack, and itemizing failsafe design features such as alarms, restoration protocols, and management configurations to detect problems and automatically diagnose and respond. Moreover, this volume is unique in providing comprehensive coverage of both state-of-the-art survivability and security techniques, and the manner in which these two components interact to build robust Information Assurance (IA). The first and (so far) only book to combine coverage of both security AND survivability in a networked information technology setting Leading industry and academic researchers provide state-of-the-art survivability and security techniques and explain how these components interact in providing information assurance Additional focus on security and survivability issues in wireless networks

The range of issues considered in graph drawing includes algorithms, graph theory, geometry, topology, order theory, graphic languages, perception, app- cations, and practical systems. Much research is motivated by applications to systems for viewing and interacting with graphs. The interaction between th- retical advances and implemented solutions is an important part of the graph drawing eld. The annually organized graph drawing symposium is a forum for researchers, practitioners, developers, and users working on all aspects of graph visualization and representations. The preceding symposia were held in M- treal (GD’98), Rome (GD’97), Berkeley (GD’96), Passau (GD’95), Princeton (GD’94), and Paris (GD’93). The Seventh International Symposium on Graph Drawing GD’99 was or- nized at Sti r n Castle, in the vicinity of Prague, Czech Republic. This baroque castle recently restored as a hotel and conference center provided a secluded place for the participants, who made good use of the working atmosphere of the conference. In total the symposium had 83 registered participants from 16 countries.