Copyright 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This article was published in the May 1998 issue of
IEEE Communications Magazine.

Abstract The rapid pace of technology introduction in the network infrastructure and services offered on this infrastructure are creating new challenges for telecommunication product and network planners. In particular, a multitude of choices, the unpredictability of future technologies and traffic, the need to operate heterogeneous networks, and the speed of change create a need for a set of tools which allow quantitative evaluation of alternatives quickly in early phases of decision making while allowing the same tools to migrate to more elaborate deployment help during the later stages. We have begun an effort to create such a set of tools under the umbrella of Integrated Network Design Tools (INDT). In this article, we describe key challenges and approaches used in INDT to meet these challenges. We also discuss the algorithmic and software architecture of INDT, and illustrate its use via examples from transport infrastructure evolution. Finally, we describe the migration path of INDT to move from early decision help to later deployment support tools.

Broadband Network Infrastructure of the Future: Roles of Network Design Tools in Technology Deployment Strategies

Bharat Doshi and P. Harshavardhana
Bell Laboratories

A major revolution is taking place in the wide area network infrastructure and services offered on this infrastructure. This revolution is fueled by the combined forces of technological advances, industry convergence, deregulation, competition, globalization, and the consumer lifestyle. On one hand, technological advances in electronics, photonics, and software have been providing ever increasing bandwidth, switching and routing capacity, and processing power at ever decreasing cost. On the other hand, deregulation, competition, and the entry of new players are making it imperative to introduce cost-reducing and revenue-generating technologies at an unprecedented pace. Finally, consumers, pressed for time at work and home, are willing to pay for network-based services which simplify business and home chores, allow anywhere/any-media communication, and provide high-quality entertainment.
This ongoing revolution is creating tremendous opportunities for network equipment vendors, infrastructure operators, and service providers. On the other hand, it is also creating many challenges for all of them. The rapid pace at which new technologies, with new capabilities and higher capacities, are becoming available is making it hard to decide which part of the existing infrastructure to keep, which new technologies to develop, when to introduce newly developed technologies, and how to interoperate old and new during the continuing transitions. Multiple options at any given time, and many more options when viewed as a sequence of choices over a planning horizon make this even more challenging. Explosive growth in overall traffic (especially generated from wireless access and created by the Internet and intranets) coupled with a high degree of uncertainty in future traffic patterns call for new approaches to planning network technologies, topologies, and capacities. Also, while the costs of processing and transport capacities are going down rapidly, the cost elements associated with operating, managing, and modifying the network tend to go up. This change in the relative costs of capital vs. operations, administration, and maintenance (OAM) of the network brings yet another set of challenges in planning and deploying networking technologies and capacities.
Network design tools play important roles in helping to evaluate alternative strategies and make technology development and deployment decisions. These roles differ in some critical ways from those in times when the pace of technological changes and introduction of new services in the network infrastructure was slow. Then, greater predictability in future traffic, incremental technological advances, and relatively few changes in the basic topology made capacity planning the most important role of network planning. Traffic forecasts, optimized routing, taking advantage of noncoincidence of busy times on different routes, and optimized location of switches and major transport hubs were brought together in sophisticated, specialized tools to design networks that guaranteed a specified service level with minimal capital expenses. While multiyear planning captured some of the rearrangement costs and designed for a degree of robustness against traffic unpredictability, much of the focus was on near-term consequences. With rapid changes in networking technologies, traffic types and volumes, heterogeneity in the network, and the increasing ratio of operations to capital costs, fundamental changes in approaches to developing and using network design tools are needed. In particular, the topology (locations of major service and transport nodes and interconnections among them) need to be robust against traffic unpredictability and possible technological advances, allowing higher capacities in switches, routers, and transmission media. Given the time it takes to develop design tools with specialized interfaces for each technology and the pace of technology introduction, greater emphasis needs to be put on developing core algorithms and software tools for selection of topology, routing, capacity allocation, and costing in ways that allow applicability to a wide variety of technologies (some not yet available) with minimal new custom development and innovative combination of existing tools. Of course, once we pass the technology planning phase to the near-term deployment phase, the approaches used for initial high-level evaluations can be incorporated in more automated and integrated tools with interfaces to allow repetitive use with minimal user intervention. This implies the ability to characterize networking technologies, their capabilities, their cost structure, and their view of current and future traffic with relatively few parameters in early phases and adding more details on technology, traffic, and specific products during later phases of deployment. This also implies the need for algorithms with flexibility to allow quick iterative analysis of many options during the early evaluation phase and detailed optimization of selected option(s) at the deployment phase.
The above requirements create challenges for people in the vendor, network operator, and service provider communities whose job is to provide quantitative tools to allow early selections among alternatives and then extend them to provide detailed deployment decisions. Also required are in-depth understanding of technologies to allow identifying key characteristics of each, identifying similarities among seemingly different technologies, modeling skills to capture the right level of details to be accurate for the purpose but avoiding unnecessary details (which make the tools too specific and non-reusable), and skills to develop algorithms which allow accurate comparisons as well as adequate optimization as needed.
We have been developing network planning/design tools along the lines suggested above. The focus is on the backbone infrastructure, including core transport -- synchronous optical network (SONET)/synchronous digital hierarchy (SDH), wavelength-division multiplexing (WDM) -- and service nodes providing various circuit- and packet-based services using switches, cross-connects, routers, gateways, and so on. The collection of tools we are developing is called Integrated Network Design Tools (INDT).
In this article, we discuss the motivation for the overall architecture and various modules of INDT, describe the approaches to meeting the above challenges, discuss some of the algorithmic details, and illustrate the use of INDT with specific examples. We also discuss how the modules can be and have been reused for many different environments and how many future needs can be accommodated with relatively small additional development effort. The key concepts used for this flexibility are described in some detail. While INDT was motivated by the need for technology/architecture/topology selection and early deployment decisions, we have taken various subsets of INDT to the stage where they can be used for designing specific networks with focus on optimality and ease of use. This effort is described briefly. INDT is evolving in response to the growing needs. We discuss ongoing and planned efforts briefly.

The Revolution in Network Services and Infrastructure

Much of the transport infrastructure based on plesiochronous digital hierarchy (PDH) is being replaced with SONET/SDH-based infrastructure. This in itself mainly changes the bandwidth units in the hierarchy. However, the higher end of the SONET/SDH bandwidth unit has gone up from STM-16 (2.5 Gb/s) to STM-64 (10 Gb/s) and may go up to STM-256 (40 Gb/s). In addition, SONET/SDH can be implemented as a traditional linear mesh or an interconnected set of self-healing rings, creating more choices in topology. Rings themselves may be path- or line-switched, with or without the full dual ring interworking (DRI) capability. WDM and optical amplifiers (OAs) allow another level of hierarchy by having many wavelengths on a fiber, each carrying a SONET/SDH signal. The possible number of wavelengths per fiber is getting higher every year (up to 80 are possible now). The wavelength need not carry SONET/SDH signal and could be made bit-rate-independent thus allowing even more choices that can be implemented without overhauling the whole network. With the advent of wavelength-division add-drop multiplexers (WADMs) and wavelength cross-connects (WXCs), there is now a possibility of creating a whole transport network in the optical domain. If the management structure offered by the SONET/SDH layer can be implemented in the optical domain or in a mixture of service and optical layers, there is a real possibility of carrying at least some of the traffic in an optical network without the intervening SONET/SDH layer.
Above this core transport layer is another infrastructure where the bandwidth offered by the wavelength layer (carrying SONET/SDH or other signals) is subdivided for different services. SONET/SDH add-drop multiplexers (ADMs) and cross-connects, with the appropriate tributary structure, can subdivide the bandwidth in chunks of T1 (1.544 Mb/s) or E1 (2.044 Mb/s), albeit at the cost of multiple equipment and rigidity of granularity. DS3s/E3s or SONET/SDH rates are likely to be more prevalent. This approach is the traditional time-division multiplexing (TDM) and uses known technologies. Another alternative is to use ATM virtual paths (VPs) to provide flexible granularity cross-connects above SONET/SDH "circuit" of relatively high bandwidth. By allowing flexible partitioning of point-to-point bandwidth as well as intermediate "grooming," ATM adds flexibility in overall bandwidth management, albeit with the penalty of overhead and complexities derived from ATM's broader envisioned role of multiservice integration with statistical multiplexing, switched services, and elaborate quality of service (QoS) management. Simpler ATM may be sufficient for this bandwidth management function. New protocols are being proposed [1] to partition point-to-point bandwidth using minimal overhead and only the necessary QoS management functions.
Whether the bandwidth is partitioned using SONET/SDH ADMs and cross-connects or using ATM VPs (or a combination of the two), the next higher layer will be the service provided to network elements which provide services to the end users. These elements may be traditional voice switches, frame relay switches, ATM switches, IP routers, digital cross-connect systems (DCSs) providing private line services, and so on. At this layer the networks have become increasingly heterogeneous. While ATM and/or IP may provide an integration layer in the long run, heterogeneity will exist for a long time.
As the overall traffic in the backbone explodes (driven by the explosive growth in the Internet and intranets and wireless, and availability of ever increasing access speeds), there will be places in the network where the routing and grooming capabilities provided by the intervening layers between service and optics may not compensate for the inefficiencies created by protocol overhead and additional equipment in the network. Thus, we see a move toward IP over SONET and IP directly over the optical (wavelength) layer. This will result in layered management of bandwidth where one or more layers may be eliminated in some parts of the network infrastructure.
While we will keep our focus on the backbone infrastructure, it is important to point out that the changes and resulting diversity are even more pronounced in premises networks and access networks. Until only a few years ago, the traffic in the backbone was dominated by traditional voice (POTS), voiceband data, and private line services. These services were offered over circuit-switched synchronous transfer mode (STM) networks. With the advent of public frame relay and ATM services, and with the explosive growth in the Internet and intranets, data traffic over a packet-switched network is growing at a much more rapid pace than circuit-based traffic. Even some services (e.g., fax and other voice band data, some private line traffic) traditionally carried over circuit networks are moving to packet networks. It is expected that packet traffic will surpass circuit traffic in the not so distant future. At the end-user level, simple data and voice services are supplemented by increasing use of multiple media, increasing diversity in speed, and QoS requirements. All these are creating new paradigms for the design and operation of the network infrastructure. In particular, the optical and SONET/SDH layer networks will have to be flexible enough to manage the rapidly changing traffic mix efficiently while maintaining robustness against unpredictability. Operations cost will drive network operators to minimize the use of multiple overlay networks and move to integrated operations. Elimination of networking layers and/or use of thin integration layers to support these moves will also lead to changing infrastructure. As the traffic mix and infrastructure supporting this mix change, questions also arise as to the best way to carry traditional traffic on new infrastructure (e.g., voice over ATM, voice over IP, everything over ATM, everything over IP over SONET/SDH or WDM). A whole new set of questions is thus created.
Along with advances in technologies and introduction of new services, changes in the regulatory environment and convergence of separate industries are bringing new operators into the picture. Their imperatives, not burdened by the embedded infrastructure and need to start with smaller customer base, are different from those of existing network operators. Their presence and competitive threats also create a different set of objectives for existing operators.

Challenges

The network infrastructure of the past was relatively static with major changes occurring infrequently (e.g., analog to digital). Services were relatively static, too. Of course, higher-capacity switches, DCSs, and links were available at regular intervals and new services of the same basic variety would be made possible periodically. Similarly, advances in routing strategies and increase in traffic would necessitate architectural changes (e.g., hierarchical to nonhierarchical networks with alternate routing). All these changes were implemented after sophisticated cost/benefit analysis. Once the basic architecture and set of network elements entered the network, the main function was capacity planning and provisioning. Highly customized algorithms and software could be developed and used for this purpose. However, the pace and magnitude of changes described above, diversity of network elements and hierarchies, diversity of services and options for carrying them, diversity of embedded bases, and multiple business imperatives make the network planning function much more challenging. In particular, decisions on technologies, interconnections of various technologies and protocols, relationships between service mix and networking technologies, topologies, and introduction timing play much bigger roles. These decisions have to be made with a much greater degree of uncertainty in the traffic types and mix. While network design algorithms and tools are needed to make these decisions with quantitative support, they need to be developed quickly for each new situation encountered. This requires a new approach to designing and developing such tools. We briefly look at the challenges these tools have to meet.
One big challenge is dealing with a large and increasing set of network elements in network design and analysis: circuit and packet switches, routers, multiplexers and cross-connects of different granularities, PDH and SONET/SDH hierarchies, ADMs, OAs, REGENs, WADMs, WXCs, and the list keeps growing. Each element has its own set of capabilities, constraints, cost structure, and interoperability requirements. When viewed in its entirety, even in the backbone, a network with these elements has many layers of hierarchy that interact with one another and change as new layers are added and old ones removed. Moreover, with the advent of self-healing rings, we have multiple topologies (mesh, ring, hybrid) to choose from. With the highly nonlinear impact of demand routing on capacity requirements, rings at one layer interact in curious ways with logical mesh at higher layers and physical fiber mesh at lower layers.
When dealing with networks of even moderate size (say, 100 core service nodes and several hundred physical fiber spans), the choices of topologies, hierarchies, and network elements, and the design of algorithms which provide a globally optimal solution is a daunting task at best, even in a static environment. Unpredictability of the future traffic and technology directions make it close to impossible, and even worthless. Of course, even when possible, highly specialized optimization algorithms may create inflexibility in handling technology constraints of similar but somewhat different network elements. We have observed this for both traditional mesh networks where the need to bundle demands make many algorithms based on linear programming (followed by some integerization heuristics) unusable, and in rings where the constraints of DRI make it hard to apply formal optimizing algorithms uniformly. The time needed to research and apply specialized algorithms frequently gives answers after they are needed for decision making. What is true of routing and design algorithms regarding inflexibility is also true of the specification of network elements and connectivity. For tools to be usable by people not familiar with the technology details, it would be nice to be able to specify each network element individually with an appropriate GUI, its specialized cost structure, and its own internal structure. The same would be desirable of the facility infrastructure. In this case, the tool will need the intelligence to handle the details of implied constraints, mapping specifications into the algorithmic modules to be used and the sequence in which to use them, and present results by combining the results of the sequence of algorithms used. With the growing number of choices, creation of tools with this level of intelligence is a time-consuming job and is creating another situation where updating the tool to handle the next set of questions takes longer than the time frame in which answers are needed.
The challenge, then, is to identify key characteristics of network elements in terms of both their capabilities/constraints and the cost structure. Given this, it may become possible to represent many existing and new elements using a few parametric models of network elements. Similarly, topological alternatives can be represented by a small number of parametric alternatives. Finally, a divide-and-conquer approach to handling a multilevel hierarchy allows handling a few layers at a time and then using the output of one study as the input to the next. Collectively, these approaches allow the studies to focus on key technology/architecture comparisons in early decision-making phases by minimizing custom development of algorithms/tools to where the effects are most critical. Once the decision-making process narrows down the alternatives, the deployment phase can be supported by a customized version of the tools with added details and more sophisticated algorithms to allow "turnkey" use. While allowing the time and robustness requirements critical in changing times to be met, this approach requires addressing modeling challenges and requires modeling to be an integral part of technology/architecture comparison studies. Also, it requires the modeling, technology development, and network operator communities to work in close partnership during the early selection process. In the next section, we discuss how we have attempted to address the modeling challenges mentioned above in the development of INDT. While INDT deals with transport as well as service layers (e.g., switched voice, packet data using IP), much of the discussion will be focused on the transport layer where the demands are specified (after appropriate preprocessing) in terms of bit rates. Of course, multiple layers of transport will be discussed in detail.

Key Approaches in INDT to Meet Challenges

Many of the challenges mentioned above have been dealt with in our approach to developing INDT. Some of the key decisions are discussed here. More detail on key aspects will be provided in the INDT architecture and algorithms section.

Dealing with the Explosion of Network Elements

Network elements are classified and represented according to key capabilities. In particular, simple multiplexers (variously called muxes and access nodes) allow many lower-granularity demands to be multiplexed for carrying efficiently to another node using a higher-granularity facility. ADM allows a high-speed facility to terminate, extract lower-speed signals, drop some of them, add new ones up to the capacity of the high-speed facility, and send the undropped and added signals on an outgoing high-speed facility. A cross-connect allows extraction of lower-speed signals arriving on many high-speed facilities, mixing them according to routing algorithms for low-speed signals, and then sending the rebundled signals on outgoing high-speed facilities to different nodes.
Amplifiers and regenerators are elements needed to maintain signal quality and are specified as spacing requirements on the core physical facilities. Collectively, most network elements used in the core transport network can be represented using the collection mentioned above by using the right parameters. For example, a DCS (x, y) may represent an electronic cross-connect with PDH or SONET/SDH units where x represents the speed of the interfaces and y the granularity of signals (demands) that can be extracted and rebundled (groomed) before sending on outgoing facilities. It can also represent optical cross-connect where x and y may represent fiber and wavelengths, respectively.
Similar unification is true of multiplexers and ADMs, whether in the electronic or optical domain. ADMs play a significant role in self-healing rings in the electronic or optical domain and need to be represented as an entity different from simple multiplexers. Of course, networks may involve many different types of muxes, ADMs, and cross-connects with different values of parameters. However, the parameters adequately specify their functions and interconnection capabilities, and the algorithms needed to optimize node selection, routing, and box/link sizing. This generic representation also allows the same algorithms and tools to be used for multiple problems (sometimes iteratively), even involving new technologies. When dealing with service networks, the traffic may not be specified in bit rate (or some multiple of a unit bit rate). For example, switched 64 kb/s voice demand is specified in terms of Erlangs (or more generally as call arrival rate, holding time, and peak rate). Voice switches are really cross-connects with call-by-call reconfiguration of rebundling.
Blocking probability requirements along with traffic demands allow calculation of the bandwidth required to support the traffic demand between two such dynamic cross-connects. The basic difference from the algorithm perspective is this conversion from call demand into bandwidth for every link connecting such muxes and cross-connects. Since this is done link by link, the multiplexing advantage will be affected by other traffic on the link. Thus, multiplexers and cross-connects of this type also provide a concentration function where appropriate. The degree of concentration depends on the traffic pattern and is easily captured by the algorithms. For packet traffic using permanent virtual connections (PVCs), the aggregate variable bit rate (VBR) demand, buffering strategies, and loss requirements can be mapped into the bandwidth required between two nodes carrying specified traffic. This mapping takes advantage of statistical multiplexing from VBR traffic. In the spirit of keeping the algorithms generic, multiplexing gain achieved with generic priority structure and buffering is captured here. More sophisticated product-specific additional gains can be captured during the deployment stage. If this differential is a key item of interest, the modular software architecture of INDT allows a specific conversion algorithm instead of the generic one.
For switched packet services, generalization of Erlang formulas [2, 3] and iterative calculation techniques are used to achieve conversion to bandwidth requirements. INDT allows standalone design of such packet networks using conversions after each routing decision. This approach is ideal when the operator leases facilities of a given granularity. For an operator providing different services over a common facility infrastructure, the conversion algorithms are used as preprocessors to calculate the bandwidth needs. These are then combined with other demands (e.g., circuit, private line) between nodes to generate aggregate demands and then sent to the optimizing modules.
In any case, core algorithms coupled with appropriate preprocessing modules allow INDT to design fixed-rate, variable-rate, permanent, and switched networks at the services layer. At the transport layer, all the demands are already converted into bit rates (or some multiple of a unit bit rate), so a uniform structure can be applied. It is also important to note that various packet-switching technologies (ATM, IP, frame relay) can be modeled in a unified way using this approach as long as the specific routing restrictions (e.g., domain-based routing in IP) are handled in preprocessors which convert specified point-to-point demand into input demands between network nodes. These types of demand conversions are also needed for bridging and multicasting applications. Another important demand conversion is related to addition of protocol overheads, depending on which protocols are used and in what combination. By leaving these conversions to preprocessors, we have been able to reuse the core modules as engines for multiple applications.
In order to make the structure even more generic, we have defined two network elements: virtual point of presence (POP), such as a virtual node (VN) and functional POP, such as a service node (SN). Functional POPs for a given example are those nodes at which cross-connects, switching, and other key functions are provided. VPOPs are ones where only multiplexing is provided. The demands have to be backhauled to an FPOP even for traffic within a VPOP. In order to allow hierarchy in design and/or hybrid circuit/packet network designs, INDT provides for multiple types of FPOPs in the same design. This construct has been profitably used to model multiplexing and cross-connect functions in switched and dedicated mesh networks, including optical-layer mesh. ADMs are important additional network elements for ring designs.

Topologies

Topology choices and specification are another challenge. For a service network, the topology is a fully or partially connected mesh. We specify this with a connectivity matrix with or without capacity constraints Besides the connectivity matrix, capacity granularity and limits (if any) suffice to specify the choice of topologies. Any specific routing constraints are handled in the preprocessor for that application, leaving the core module to optimize routing along all paths where capacities are available. This works when the facilities are PDH or SONET/SDH links or fiber links with multiple wavelengths. The exception is when we design a transport-layer mesh network over fiber spans. Since fiber spans may carry fibers between multiple node pairs, additional mapping between links and spans is needed. This is mainly important in designing for restoration where a span failure may affect multiple links, and the primary and alternate routes cannot use the same span.
Another important topological construct is the ring. With the advent of self-healing SONET/SDH rings, this has become an important aspect of transport networks and needs to be handled separately. Unfortunately, standards and product technologies allow many different types of rings: path- or line-switched, two- or four-fiber, with or without DRI. Networking using interconnected rings designed over fiber spans carrying multiple wavelengths pose many challenges. These arise from choices in ring generation, ring interconnections, demand routing within and between rings, and myriad constraints. A significant portion of the algorithm and software development effort in INDT has been expended on creating a flexible, hierarchical strategy and mathematical specification of constraints to allow ring design problems of many different types to be handled with minimal customization. Also, this approach makes it easier to design transition from an existing ring network to a network for the future demand matrix. Although motivated by the need to design SONET/SDH rings of any capacity (e.g., STM1, STM4, STM 16, STM 64), the generic structure allows the tool to be used for optical rings of different types.
Integration of different modules in the tool allows the service-layer mesh to feed input to the transport-layer ring design. If some rings are to be interconnected using an optical mesh network, the output of the ring design can also feed the mesh design tool.

Cost Models

Creating cost models that can accurately reflect cost elements of relevance in decision making without making them inflexibly specific is a major challenge. Equally important is to make sure that the cost models and algorithms work well together. These requirements have affected both algorithm selection and cost structure selection. For the mesh design, the selection of nodes for cross-connect (FPOP, SN) functionality is based on simulated annealing, allowing almost any cost structure for a node. Routing optimization is based on bin packing algorithms, allowing link cost to depend mainly on the integral multiples of the basic unit used on that link; otherwise, it could be specific to that link. Similar flexibility is provided in the ring designs by selecting algorithms that do not rely heavily on a specific cost structure except honoring integer constraints.
Given this flexibility and the need to have some easily usable cost model in the absence of more details, we have provided default models as well as allowed for more specificity. For links in mesh designs, the default cost model is the cost of terminations on both ends and cost per mile of the basic bandwidth unit (even if a fraction is used). However, the user is allowed to specify the cost of the unit individually for each link. In designs involving more than one bandwidth hierarchy, each bandwidth unit has its own cost, thus allowing economy-of-size modeling.
For the VPOP (VN) and FPOP (SN) node cost models, the simplest involves the cost per port specified separately for ports on the access and network sides. For networks with multiple FPOP types, ports connecting different types have different costs to account for speed differences and protocol conversions. Additionally, a fixed cost of the basic box is specified. These elements cover cross-connects, switches, routers, wavelength multiplexers, and so on. As mentioned above, the algorithms allow a separate routine for calculating the node cost based on the links terminating there, so any detail can be specified. The default model discussed above is adequate for most purposes.
For ADMs, the fixed cost of ADM for one unit of high-speed termination and cost per low-speed port are the main cost elements whether the ADM is for SONET/SDH or WDM.
The cost of OA is per unit of fiber (e.g., a four-fiber system has OA cost specified for a four-fiber bundle). The cost of REGEN is a fixed cost plus cost per wavelength regenerated. These costs are special cases of the box cost structure described above.

Traffic Types

There are a few traffic types in INDT. One key construct is multirate constant bit rate (CBR), where each demand is specified as a bit rate, usually as an integral multiple of a basic unit specified as input. The rate itself is specific to a demand. Routing algorithms make sure a demand is not split among multiple routes. If a demand can be split it should be specified as multiple demands, so each can be routed independently. This construct allows specification of private line traffic, switched voice traffic, and packet-/frame-/cell-based traffic aggregated at a level where the equivalent bandwidth suffices to characterize it. At the transport layer, the same construct may specify SONET/SDH demands between network elements or wavelength demand between optical elements. The other traffic type is VBR. This is specified by peak rate, average rate, burst parameter, acceptable loss rate, and acceptable delay. These specifications, along with buffer sizes, allow calculation of equivalent bandwidth required to support aggregated traffic for the specified QoS requirements. This construct works for ATM, frame relay, IP, and other packet networks in permanent circuits or aggregated traffic between routers. For switched services, additional specification of the acceptable blocking probability (individually for each demand) allows the use of generalized Erlang formulas to convert demands into bandwidth requirements.

Flexible Algorithms

In order to provide a flexible, reusable suite of tools, the overall analytic/algorithmic architecture is divided into a few interconnected modules.

The Bandwidth engineering module

This provides the bandwidth (equivalent bandwidth) for a given mix of traffic and QoS requirements. As discussed above, this concept allows conversion of all traffic types to a common denominator: bandwidth needed to support the traffic mix. With appropriate front-ends, bandwidth engineering can model the bandwidth needs of private lines, circuit and packet voice, single session or aggregate data, video, and so on arriving over circuit, IP, FR, ATM, and other protocols. Current default algorithms incorporated in INDT capture significant research on this subject and suffice for most purposes. As switches and routers become more sophisticated in QoS management algorithms, new results will be needed to accurately characterize the effective bandwidth. For that reason, a flexible environment is provided for replacing the existing bandwidth engineering algorithm with a new one and using it as a preprocessor before applying optimal design algorithms.

The Homing Module

The homing module provides the best way to connect VNs to SNs. Two versions are available in INDT. One is a simple homing scheme using minimum distance. This suffices for most purposes. The other uses a more sophisticated homing scheme exploiting multiplexing nodes between VNs and SNs to take advantage of the economy of size. This is important when the focus is on the design of the homing network (e.g., wireless operators designing a leased line network between base stations and cellular switches). When the focus is on the backbone design it is assumed that the homing optimization is done, and the average cost resulting from that is used in the simple homing module for design purposes. Special needs such as dual homing for reliability can be incorporated when needed.

The Mesh Backbone Design Module

The basic algorithm for selection of the locations of two types of SNs use simulated annealing, thus allowing fast (few iterations) or optimized (more iterations) results. Good heuristic for starting simulated annealing allows good results even with few iterations. Backbone cost is estimated by simple but tight lower bounds to use minimal computation time, thus allowing a large number of iterations in a relatively short time. Once the SN locations are selected, backbone routing optimization involves bin packing algorithms, taking into account the integrality constraints, and exploits the networkwide statistics on utilization to search for spare capacity and eliminate lightly loaded links. Both capacitated and unconstrained designs are permitted in this step. Bin packing heuristics, while simple and proven very effective in generating near-optimal designs, also provides flexibility for adding capacity and/or technology constraints easily.
While only two SN types are designed in one step, repeated use of the tool allows a multiple-level hierarchy. The overall structure is applicable to service networks like a network of voice switches, data switches (ATM, FR), routers, and transport networks like PDH, SDH/SONET, and optical networks (with full cross-connect capabilities). Iterative use allows the design of a service network to feed the transport network design, and that design to feed the optical network design. Transport costs can be folded into service costs, thus allowing studies of the impact of changes in transport costs on the service network topology. Finally, multiple levels of service networks are possible (e.g., bandwidth hierarchies, IP over ATM, voice over IP or ATM).

Ring Designs

Ring designs are inherently different from mesh network designs, and many different choices exist in the ring designs. The overall problem is broken down into many steps (generation, selection, inter-ring routing, intra-ring routing, etc.) to allow easy accounting of myriad technology constraints. The algorithmic and software architecture allows various types of SONET/SDH rings (UPSR, BLSR, with or without DRI, with or without WDM, etc.), optical-layer rings, and virtual rings. Special care is taken to model technology constraints on routing and interconnections carefully. Also, care is taken to allow optimal expressing in stacked rings and to allow optical mesh/ring connecting SONET/SDH rings.

INDT Structure and Algorithm Approaches

A schematic depiction of the INDT architecture is shown in Fig. 1. At a high level, there are three main components in INDT: an access network design module, a service-layer mesh network design module, and a physical-layer mesh or ring network design module.

The Access Network Design Module

The access network design module interfaces with the customer traffic and designs the specific type of access network desired. Currently this module has the capability to design wireline infrastructure supporting wireless access networks as well as designing conventional switched and dedicated access networks. Future generics of the access module will include newer access technologies such as fiber to the curb (FTTC), hybrid fiber coax (HFC), and others. A description of the wireless infrastructure design module is given in [4]. Switched and dedicated access design issues are conceptually similar to the wireless design module and are omitted for the sake of brevity. The role of the access network is to provide end users access to different types of service networks, in addition to completing calls within their own serving areas. Thus, wireless access networks may provide access to the public wireline voice network in addition to completing wireless calls within the serving area. Similarly, switched or dedicated access networks will provide access to the appropriate service network -- switched voice, private line, frame relay, ATM, Internet, and so on -- in addition to completing calls within the serving area. The output of the access network design module thus serves as input to the service network design module. This is illustrated in Fig. 2, which shows an end-to-end customer circuit from A to Z broken up into the access and service network components.
The virtual node (VN) shown in Fig. 2 is a traffic concentration point from which traffic is hauled to various types of wide-area service networks. From the perspective of service network design, the role of the access network design module is to provide the mapping between end-user traffic and VN locations. The focus of the service network design module, therefore, is on providing an optimal service network connecting the VNs.

The Service Network Design Module

The service network design problem may be systematically depicted as shown in Fig. 3.
Fig. 3 are service grooming locations where service-specific processing necessary to complete the call are performed in addition to providing better service-layer efficiencies by concentrating traffic belonging to similar services.
Broadly speaking, the service-layer network design problem consists of two key steps: selection and interconnection of SN locations. For each service type, the VNs must be homed to the appropriate SNs, which must then be interconnected in the most cost-efficient manner possible. In what follows, we will first provide a generic description of the service network design problem and then discuss the service-specific nuances captured within the INDT framework.
In INDT, the SN selection problem is solved using an optimization technique known as simulated annealing. Simulated annealing is a well-known method for solving combinatorial optimization problems [5]. The starting point of this approach is to make an initial guess regarding SNs to be selected (the initial guess may be completely arbitrary, although educated guesses usually yield better results.) The VNs are then homed to the SNs. The homing may be done based on the shortest distance rule or, if appropriate, minimizing the homing cost based on a specified homing cost model. In either case, this step is usually quite straightforward. Once the VNSN homing is done, all the SNSN traffic flows are determined. The cost of the backbone network (BBN) interconnecting the SNs must now be computed. In small networks (less than 50 nodes) the computation time is sufficiently small that the actual "optimal" BBN may be computed. In larger networks the computation time is larger, and hence we need to estimate the BBN network. We have developed an efficient optimization heuristic that may be used tp provide a fast estimate of the BBN cost [6]. Once the BBN network cost (estimated or actual) is computed, the total network cost, including homing and backbone, is computed. The total network cost is then used to perturb the current SN selection. The process is then repeated for the new SN selection. This is repeated iteratively until either the solution converges or a specified upper limit to the number of iterations is reached. The best SN selection thus obtained is then taken to be the optimal SN selection.
Given the optimal SN selection, a detailed BBN design is performed, producing detailed network statistics such as the number of different types of terminations and ports at each node, the number of trunks between node pairs, and the end-to-end routing of demands. The trunks connecting node pairs in the service network design are logical connections, which serve as input to the physical-layer design.
In the preceding, we provided a description of the generic approach to service-network design in INDT. As described earlier, there are many subtleties in the service network design problem. Below we provide a brief overview of some of the different service network design modules in INDT. INDT has three main service network design modules:

Nonswitched multirate CBR module
Switched single-rate CBR module
The switched/nonswitched multimedia module

Each of these comes with logical and capacitated design options. Below we summarize the main features of each module.

The Nonswitched Multirate CBR Module

The nonswitched multirate CBR module takes CBR packet (e.g., ATM) and circuit demands as input and designs a single-backbone or two-backbone mesh network. The single-backbone network may be ATM or circuit-switched, depending on whether the demands are ATM-CBR or circuit-switched. The two-backbone network supports ATM-CBR as well as circuit-switched traffic; one of the backbone networks will be an ATM backbone consisting of ATM cross-connects, while the other will be a circuit backbone consisting of circuit cross-connects. It should be noted that the ATM backbone can carry circuit traffic via the synchronous/asynchronous card (SAC) interface, while the circuit backbone can only accommodate circuit traffic. No matter which option is exercised, the SN selection procedure will pick the "best" SN locations; for the one-backbone case SN locations correspond to either ATM or circuit cross-connects, while for the two-backbone case SN locations selected afford the "best" combination of ATM and circuit cross-connects which minimizes network cost. Once the SN locations are determined, the BBN design procedure determines the "best" interconnection network for the ATM, circuit, or combination ATM and circuit backbone, depending on the option selected. Note that the ATM model also allows design with other frame/packet technologies like frame relay and IP.

The Switched Single-Rate CBR Module

The switched single-rate CBR module is primarily meant for designing switched voice networks, although it can be used for designing any single-bandwidth demand-switched network. This module takes point-to-point traffic demands in the form of Erlang loads and demand blocking. The demands are fed to an Erlang preprocessor which converts the demands to point-to-point bandwidth demands. These bandwidth demands are then used to determine the size of the backhaul trunks needed to connect the VNs to SNs. However, once the VNSN homing is decided, the point-to-point aggregated Erlang loads between SNs and the point-to-point bandwidth required between SNs are computed by processing the aggregate Erlang loads through the Erlang preprocessor. The interconnecting BBN network is then estimated or designed depending on whether SN selection or BBN design is performed to provide the required point-to-point bandwidths.

The Switched/Nonswitched Multimedia Module

The switched/nonswitched multimedia module is the most versatile service network design module in INDT. This module accepts CBR and VBR demands in switched and nonswitched form. All the switched demands are considered part of an integrated switched network, while the nonswitched demands are part of an integrated nonswitched network. The integrated switched network may be used to model a broadband integrated services digital network (B-ISDN), while the integrated nonswitched network may be used to model an IP network (this correspondence is not rigid but may be interpreted as needed; e.g., the latter may also be viewed as a B-ISDN PVC network). In this module, demands must first be processed by an equivalent bandwidth module for converting VBR demands into equivalent CBR demands. The equivalent bandwidth approach has been widely used as a convenient way to represent VBR traffic for the purposes of network modeling and analysis [79]. Once the equivalent bandwidth representation is obtained, the design algorithms must now handle a mixture of multirate switched and nonswitched demands. INDT employs a generalized Erlang model [2, 3] to convert multirate switched demands, together with their associated offered loads and blocking requirements, into point-to-point bandwidth demands. Once this is accomplished, just as in the case of the switched single-rate CBR module, the backhaul trunk bandwidths may be determined. Again, as before, for a specific choice of SNs, the aggregate Erlang loads between SNs are computed. and the point-to-point bandwidth required between SNs is computed by processing the aggregate Erlang loads through the generalized Erlang processor. The point-to-point bandwidths corresponding to the nonswitched demands are added to the bandwidths corresponding to the switched demands, and the BBN network is designed or estimated as needed. It is worth noting that our generalized Erlang model has the sophistication to account for peak rates resulting from alternate routing of overflow traffic.
Note that the approach and algorithm used here are applicable to other packet-switched networks such as those based on IP and frame relay.

The Physical Network Design Module

The output of the service network design module produces a set of point-to-point trunking demands. The sum total of all these point-to-point trunking demands due to the multiservice networks supported by the physical network now serves as the input to the physical-layer design process. The distinction between VNs and SNs based on service grooming is not valid in this step. Here all nodes with trunking demands are VNs, and nodes that serve as physical-layer hubs are SNs. Thus, SNs here may be locations of high-speed SONET DCSs in a physical-layer mesh network, of SONET ADMs in a physical-layer ring network, or of optical ADMs (OADMs) in an optical network, just to name a few examples. INDT has three modules for designing the optimal physical-layer network.
The first is the optimal mesh network design module, which functions just like the service-layer nonswitched multirate CBR module with the difference that SN locations are now facility hubs. Since all the previous discussion applies here as well, we will not elaborate on this any further. It should be noted that this mesh design module can design an optimal mesh using SONET/SDH DCSs or optical cross-connects. It can also design an optimal mesh subnetwork interconnecting SONET/SDH rings. This is an excellent example of multiple uses of the same design module.
The second physical network design option provides the ability to design networks of interconnected rings. The ring design module is capable of designing large interconnected networks of rings. It can accommodate four- and two-fiber bidirectional line- and path-switched rings. The DRI feature has been modeled within INDT in complete detail and several of the heretofore unknown operational complexities due to DRI have been captured. A host of constraints imposed by bandwidth granularity, product features, and standards have been modeled. The ring design module consists of the following submodules:

Ring generation
Ring selection
Inter-ring routing
Intra-ring routing and load balancing
Ring deloading
Ring costing

In this article, we present a high-level overview of each of these submodules. More details may be found in [10].

Ring Generation

Given the point-to-point demands to be carried on the ring network and the fiber connectivity, the ring generation module creates all "sensible" rings. No attempt is made here to pick the best set of rings; the main purpose of the module is to generate a large set of sensible rings. This superset is then fed to the ring selection module which finds the best subset of rings to be used. In generating sensible rings, the ring generation module takes into account the following factors:

Inter-ring demands
Intra-ring demands
Span diversity
Maximum number of nodes allowed on a ring
Maximum allowed distance between consecutive nodes on a ring
Need for stacked rings, that is, rings that follow the same physical fiber path but differ in their placement of ADMs
Need for express rings, that is, rings meant primarily to carry long distance traffic
Rings with good interconnectivity from a DRI perspective

For the sake of brevity, we shall not go into algorithmic details, but we will outline the significance of each of the above factors. Rings with a balanced mix of inter-ring and intra-ring demands will, after careful optimization, allow good utilization of almost all the links on the ring, and, hence lead to a lower cost design [11]. Ensuring span diversity between any pair of links on the ring is crucial to meet the standards requirement that any single failure should be restorable via ring restoration. Current standards requirement places a constraint of no more than 16 nodes on a ring. This is likely to increase to 32 in the near future, but nevertheless will place a constraint that ring generation must satisfy. Current optical technology allows for signal loss budgets that permit optical amplifier spacing up to 75 mi and regenerator spacing up to 225 mi. These depend on complex engineering rules taking into account the number of wavelengths per span, span distance, and so on. The loss budget also assumes that the total length of fiber is within the permissible maximum. Thus, ring generation needs to ensure that the distance between consecutive nodes on a ring is less than the permissible maximum fiber length. Also, it is often convenient to provide separate addresses for regenerators in order to facilitate fast automated fault location, and this causes each regenerator to be counted as a node and may thus reduce the maximum number of real nodes allowed to even less than 16 (or 32). Stacked rings are needed sometimes to allow better load balancing on a ring.
Express rings are efficient for carrying long distance traffic on larger rings requiring fewer ring interconnections. This is very important, because it is well known [11] that ring interconnections using DRI impose a substantial capacity and hence cost penalty. Lastly, it is important to ensure that ring pairs with significant inter-ring traffic should have three or more interconnection points (DRI nodes) whenever possible, because this substantially reduces the DRI penalty [11].

Ring Selection

Given a superset of rings (produced by the ring generation module, specified by the network designer, or both), this module generates the "optimal" subset of rings that can transport the given demands at the least possible cost. This module assumes that the given superset of rings defines a completely connected ring network (i.e., any two nodes are reachable on the ring network), and proceeds to pick the best subset while ensuring that the reachability property is retained.
The first step in ring selection is to attempt to pick rings that result in good fiber utilization. This is important because many of the physical-layer equipment can be shared by multiple rings. For example, the Lucent Technologies Optical Line System (OLS) can multiplex 40 OC-192 signals onto a single fiber. Thus, up to 40 OC-192 rings can share an OLS. Since the OLS is a fairly expensive piece of equipment, if we select rings that allow this kind of resource sharing, the resulting ring network cost will be lower. We refer to this as physical-layer optimization. Our approach to physical-layer optimization is as follows: the set of nodes and links belonging to the superset of rings is treated like a physical-layer mesh network. On this mesh network we route the demands to be transported by the ring network, and perform a mesh network optimization as described earlier. This is achieved by packing the links to ensure a good fiber fill and eliminating underutilized links. The only extra step needed here compared to the standard mesh network optimization is ensuring that optimization does not destroy the ring reachability property.
Physical-layer optimization results in a reduced set of rings which are guaranteed to have the reachability property. From this reduced set of rings, we next pick the optimal subset best suited for transporting the given demands. Many of the considerations that drive ring selection are similar to those used in ring generation. The process is somewhat simpler here, since rings are already given. The main factors to be considered in ring selection are:

Inter-ring demands
Intra-ring demands
Need for stacked rings
Need for express rings
Rings with good interconnectivity from a DRI perspective

Since we have already described the role of these factors in the previous section, we will not elaborate on them further here.

Inter-Ring Routing

This is perhaps the most complex of the submodules in ring design, from both the algorithmic and software perspectives. This is because this submodule is impacted the most by product, standards, and technology constraints, and hence both the algorithms and software architecture in this submodule must be flexible enough to allow many different implementations. A complete description of all the subtleties and complexities encountered in this submodule is beyond the scope of this article.
There are two main steps in inter-ring routing:

Demand assignment
Demand routing

Demand assignment assigns the originating and terminating nodes to the right rings whenever these nodes belong to more than one ring. To illustrate, consider the example in Fig. 4.
In Fig. 4 node A belongs to rings R1 and R2, and node Z belongs to rings R3 and R4. Now suppose there is a demand from A to Z. To which of the four possible originating/terminating ring pair combinations (R1R3, R1R4, R2R3, R2R4) should this demand be assigned? Furthermore, for each originating/terminating ring pair, there may be several paths connecting them; which of these paths should be chosen? These two questions together constitute the inter-ring routing problem. Four factors need to be considered in addressing this problem. They are:

Stacked rings should be used to improve ring utilization.
Express rings should be used for long distance traffic, and local rings should be preferred for the local traffic.
Not all paths may be feasible owing to technology, product, and standards constraints; hence, the search for the best route for a given demand must be limited to the set of feasible paths for that demand.
As a general rule, the shortest feasible path (in terms of number of rings in the path) should be preferred because this keeps ring interworking and the consequent DRI penalty to a minimum.

Intra-Ring Routing and Load Balancing

Once inter-ring routing is done, the loads to be carried on each ring are completely specified. In the case of bidirectional line-switched rings, the next step is to balance the load on each ring to minimize the ring capacity required. In the case of path-switched rings or unidirectional line-switched rings, load balancing is not needed since the ring capacity is simply the sum of demands. Our approach to intra-ring routing and load balancing is described in [12]. Here we omit the details for the sake of brevity.

Ring Deloading

After load balancing is done, the ring capacities are modularized. For example, suppose we are designing OC-192 rings and a particular ring has a maximum load of 193 OC-1s. After modularization, this will lead to two OC-192 rings, the first of which has a maximum loading close to one OC-192, and the second a very low maximum load which could be as low as one OC-1, depending on the distribution of demand sizes. We call such underutilized rings straggler rings. The object of ring deloading is to see if these straggler rings can be eliminated by rerouting some demands. Thus, in the example above, suppose that the maximum load of 193 OC-1s included a single OC-3 demand from node A to node Z. If we could remove this demand from this ring and find an alternate path without pushing some other ring over the OC-192 boundary, we would eliminate the need for a second OC-192 ring. We refer to this as ring deloading.
The main steps in ring deloading are:

Identifying the straggler rings
Identifying demands to be deloaded from straggler rings
Identifying alternate paths for demands to deloaded
Rerouting the deloaded demands and checking to ensure that no ring in the new path exceeds the modular ring capacity; and, if some ring does, disallowing the deloading of that demand

Each of these steps is quite complex and computationally expensive. However, ring deloading is a very important last step which can significantly reduce the total network cost.

Ring Costing

After all the ring capacities are determined, the tool reports various quantities of interest to the costing module, including:

Total number of ADMs
Total number of OAs
Total number of regenerators
Total number of DWDMs
Total number of low-speed circuit packs on ADM
Total number of originating/terminating low-speed circuit packs
Total number of inter-ring low-speed circuit packs
Link lengths for each ring

This information is used by the ring costing module to cost out the network design in complete detail. If the user so desires, the cost information could also be obtained on a per-ring basis.

Examples

INDT modules have been used in the past to design infrastructure for private line services to hundreds of thousands of customers, switched voice networks with circuit and/or ATM-based transport, and large networks of interconnected SONET rings; and to compare circuit- and packet-based transport of voice, large and small link granularity, and ATM and SONET mesh-layer restoration capacity requirements; and many other technology comparison problems in large networks. Instead of presenting results from specific studies conducted in the past, we illustrate some of the capabilities of INDT with a small set of examples created for illustration purposes only.
The examples presented here are based on a hypothetical network spanning the continental United States. While INDT has been used to study networks with up to 1000 nodes and over 10,000 links, we will use a somewhat smaller example network. The core physical network layout is as shown in Fig. 5 and consists of 26 nodes and 41 links. These 26 nodes may be thought of as being the core network nodes, and the 41 links are fiber links interconnecting the 26 nodes. In the examples below we examine three types of mesh network design and a BLSR ring network design.
The point-to-point demands are given as the number of DS3 connections required between node pairs. The point-to-point DS3s are transported as OC-192 pipes in the case of mesh networks and as STS-1 connections on OC-192 BLSR rings, in the case of ring networks.
In the first mesh example, the DS3 demands are transported over an OC-192 circuit network. The SNs in this case are SONET cross-connects which can groom DS3s within the backbone OC-192 trunks. The cost parameters for this mesh design are summarized in Table 1. These cost numbers are for illustration only.
With the cost parameters in Table 1 and using all 26 nodes as SNs, the resulting mesh network cost is $385,000.00.
Now with the same 26 nodes as SNs for an ATM-based mesh network using ATM cross-connects to groom the DS3 within the backbone OC-192s, and assuming the costs in Table 2, resulted in a mesh network cost of $270,000.00.
Since all the demands were assumed to be circuit demands, we needed to add a synchronous-to-ssynchronous converter (SAC) cost of $75/OC-192. The SAC function provides the interface between the circuit demands and an ATM cross-connect. Again, the cost numbers used are for illustration only.
Note that the cost savings in the ATM-based network comes from less expense ($150 vs. $200) per OC-192 with grooming at the DS3 level for SONET and at an arbitrary level with ATM ports. This would be true if ATM were a better technology to provide DCS functions. If the ATM ports were more expensive, the main benefits of ATM would come from being able to groom at different granularities.
Next we illustrate a hybrid circuit/ATM mesh network design. Here half the demands are circuit DS3s, the other half ATM DS3s (arriving in the form of ATM cells rather than DS3 circuits). The circuit DS3s may home to either an ATM or a circuit SN, but ATM DS3s must home to an ATM SN. We chose half of the 26 SNs to be ATM SNs and the other half to be circuit SNs. The cost of this hybrid network turned out to be $340,000.00. The cost parameters used for this design are the same as those shown in Table 1 and Table 2.
We would like to emphasize again that the cost numbers are purely illustrative; thus, the results do not reflect the actual technology selection recommendation for this case.
Just to reinforce this point we now provide two other designs, an all-circuit design where the OC-192 circuit port cost is $50/OC-192 and an all-ATM design where the OC-192 ATM port cost is $200/OC-192; all other cost numbers are as in Table 1 and Table 2. For these new cost numbers, the circuit-based mesh design cost was $295,000.00, ATM-based mesh design $360,000.00, and hybrid mesh design $340,000.00. Fig. 6. Studies like these can also show the range of costs over which one technology solution is better than another for the network at hand.
Using the physical fiber layout shown in Fig. 5 and assuming the same all-circuit point-to-point DS3 demands as before, we next designed a BLSR ring network. For simplicity we assumed that the links are span disjoint (i.e., no two links share a fiber span). This is rarely true in practice, and, in fact, INDT allows a link-to-span map to be specified in order to provide the span sharing information to the ring design tool. This is an important feature of ring design, since links on a ring are required to be span disjoint. Figure 7 shows the rings designed by INDT.
For designing these rings, it was assumed that common-node DRI connectivity between rings is desired. If common-edge DRI had been specified, the rings chosen could have been different since the rings shown in Fig. 7 do not share many common edges. The cost of the resulting OC-192 BLSR ring network was $850,000.00. For this design, we did not associate cost to miles directly. However, the costs of optical amplifiers and regenerators were added. In addition, the costs of high-speed (OC-192) and low-speed (DS3) interfaces were included. No attempt was made to make the unit costs for the ring network elements and mesh physical-layer elements consistent in relative terms. Thus, no conclusion can be derived from these results about the desirability of ring vs. mesh physical layers. Also, the rings provide 100 percent restoration, while the mesh designs did not include the capacity needed to provide equivalent restoration. The overall trade-off between rings and mesh depend subtly on many factors: desired speed of restoration; capacity requirements assuming 100 percent restorability in both cases (even if the mesh restoration may be slower); relative costs of SONET DCS and BLSR ADM ports. From the cost perspective only, we have encountered results in both directions. SONET mesh restoration is likely to be much slower than BLSR restoration.

Ongoing and Future Work

The current capabilities of INDT are being extended in many directions. For mature algorithms (e.g., mesh and ring designs at the service and transport layers), a GUI and simple-to-use database structure have been developed to make the tools more widely usable. Algorithms and software for the design of wireless infrastructure using STM, frame relay, and/or ATM transport are being added. More formal structure to allow the design of IP-based networks is being added. We are also studying various algorithms for optical layer restoration and capacity planning under various technology constraints. They will be formally added to the overall capability in INDT, at least for the schemes to be used. This will also allow better treatment of mesh designs incorporating service-layer restoration capacity.

Acknowledgments

We would like to acknowledge the very substantial contribution of our colleagues Song Chen, Subra Dravida, Cindy Funka-Lea, Ramesh Nagarajan, S. Ravikumar, and Yufei Wang to the INDT concepts, algorithms, and software development effort. We also thank Mark Hornby for providing input from the perspective of a broader set of users.

References
[1] B. T. Doshi et al., "Multi-Protocol over a Bytestream (MOB): A New Protocol Stack for Supporting Heterogeneous Traffic over a Common Link," to be presented at Networld INTEROP, Las Vegas, NV, May 1998.
[2] J. S. Kaufman, "Blocking in a Shared Resource Environment," IEEE Trans. Commun., vol. COM-29, no. 10, Oct. 1981, pp. 147485.
[3] J. W. Roberts, "A Service System with Heterogeneous User Requirements in Performance of Data Communications Systems and Their Applications," G. Pujolle, Ed., North Holland, 1981, pp. 42331.
[4] S. Dravida et. al., "Narrowband and Broadband Design for Wireless Infrastructure Networks," IEEE Commun. Mag., this issue.
[5] D. S. Johnson et al., "Optimization by Simulated Annealing: An Experimental Evaluation, Part I, Graph Partitioning," Oper. Res., vol. 37, no. 6, 1989.
[6] B. T. Doshi, S. Dravida, and P. Harshavardhana, "Overview of INDT -- A New Tool for Next Generation Network Design," Proc. IEEE GLOBECOM, Nov. 1317, 1995.
[7] B. T. Doshi, "Deterministic Rule Based Traffic Descriptors for Broadband ISDN: Worst Case Behavior and the Concept of Equivalent Bandwidth," Proc. 14th ITC, June 1994.
[8] A. Elwalid, and D. Mitra, "Effective Bandwidth of General Markovian Traffic Sources and Admission Control of High Speed Networks," IEEE/ACM Trans. Networking, vol. 11, no. 3, pp. 32943.
[9] K. M. Rege, "Equivalent Bandwidth and Related Admission Criteria for ATM Systems -- A Performance Study," Int'l. J. Commun. Sys., vol. 7, 1994, pp. 18197.
[10] B. T. Doshi et al., "Integrated Network Design Tools (INDT): A Suite of Network Design Tools for Current and Next Generation Networking Technologies," IEEE Networks Specialist Conf., Montebello, Canada, Oct. 1996.
[11] B. T. Doshi et al., "Dual Ring Interworking: High Penalty Cases and How to Avoid Them," ITC 15.
[12] C. Buyukkoc et al., "Load Balancing on SONET-Rings," Proc. ICT '96, Istanbul, Turkey, 1996, pp. 76366.

Biographies
Bharat Doshi is department head of the Performance Analysis Department in the Advanced Communications Technologies Center of Bell Laboratories-Lucent Technologies. He is also a fellow of Bell Laboratories. He received his B.Tech. from the Indian Institute of Technology, Bombay, in 1970, and an M.S. and a Ph.D. from Cornell University in 1973 and 1974, respectively. He joined Bell Laboratories in 1979 and was promoted to technical manager in 1982. In 1994, he was promoted to his current position. In 1996 he was made a fellow of Bell Laboratories. He manages research in communications protocols, network architecture, performance/reliability engineering, traffic engineering, and network routing for advanced communications technologies and systems. His department also conducts research in integrated communication systems and networks. Recent work has concentrated on frame relay, ATM, SONET/SDH, optical networks, wireless networks, and the Internet. He has been associate editor of three journals, and has over 90 publications in a wide variety of technical journals.
P. Harshavardhana obtained his B.Tech. degree in electronics from the Indian Institute of Technology, Madras, in 1980 and his M.S. and Ph.D. degrees in EE from the University of Southern California in 1982 and 1984, respectively. From October 1984 to July 1987 he was with Bell Communications Research where he worked on the performance monitoring of digital transmission systems. He has been with Bell Laboratories since July 1987. At Bell Labs his work has focused on various aspects of networking such as routing, robust topology design, forward error correction, congestion control, network design and restoration. He is currently managing several network design and analysis projects including SONET/SDH rings and optical networking. He holds several patents in the area of network routing, design, restoration, and congestion control.