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 There has been an explosion in the number of wireless subscribers in recent years. Currently a number of air interface technologies, such as GSM, TDMA, and CDMA, are available to wireless service providers for offering wireless services. In addition, a variety of networking technologies, such as STM, ATM and frame relay, are available to the wireless services provider for designing their infrastructure networks. The abundant choice of technologies, and their associated capabilities and costs, creates a need for network design tools which can help vendors and wireless service providers to understand the economics of investing in different technologies. This article is concerned with the design of narrowband and broadband infrastructure networks for wireless access. The article first describes the different technology alternatives and tariff structures and their impact on wireless infrastructure network design. The general infrastructure design problem is then stated and a solution methodology outlined. Examples of the economic trade-offs involved in narrowband and broadband networking technologies are also presented.

Narrowband and Broadband Infrastructure Design for Wireless Networks

Subra Dravida, Hong Jiang, Murali Kodialam, Behrokh Samadi, and Yufei Wang
Bell Laboratories, Lucent Technologies

There has been enormous growth in the number of subscribers for wireless services. The number of subscribers in the United States is approximately 50 million, and the growth rate is expected to be between 30 and 40 percent each year. Currently, a number of air interface technologies, such as Global System for Mobile Communications (GSM), time-division multiple access (TDMA), and code-division multiple access (CDMA), are available to a wireless service provider in order to provide wireless services. In addition, there is also a choice of different networking technologies available in the network infrastructure. Asynchronous transfer mode (ATM), frame relay, and synchronous transfer mode (STM) are the leading candidates for transporting information in the infrastructure network. Each of these technologies has different interface speeds, multiplexing capabilities, and so on. These capabilities exploit the facility tariff structure in different ways. In addition to networking technologies, there is also a choice of different facility technologies, such as terrestrial facilities based on copper, coax, or fiber, and digital microwave links. Given all these choices, there is a need for network design tools to study the economic trade-offs involved in the choice of different technologies.
A good wireless network design tool can provide utility from two perspectives. First, the manufacturer of wireless equipment needs a tool to understand its product plans from a vendor perspective. The tool should enable the manufacturer to understand the overall impact of introducing new products and functionality. By conducting what if studies on products and technologies not yet in the design stage, the manufacturer could identify gaps in either the current product line or the functionality of specific products. Such modeling can also help the manufacturer in pricing its product offerings and, more specifically, offering package deals to its customers. Second, network design tools are of immense value to wireless service providers since they are interested in obtaining the lowest-cost network designs to keep their operating and capital costs as low as possible. A network design tool helps in this regard by optimizing the transport cost, which is a significant recurring part of the cost of providing wireless service. Based on all the above considerations, a versatile transport network design tool which can accommodate multiple air-interface technologies, multiple infrastructure technologies, and multiple tariff structures (domestic and foreign) will be of great value to both wireless equipment manufacturers and wireless service providers.
The rest of the article is organized as follows. In the next section, we describe the architecture of a wireless infrastructure network. The cost structure of wireless infrastructure is then outlined. In the section after that, we formulate the network design problem and discuss solution approaches. Examples of network design are then given, illustrating the economic trade-offs involved in the choice of different networking and facility technologies, followed by the conclusion.

Wireless Infrastructure Network Architecture

Wireless networks consist of a mobile component and a fixed component. The mobile component consists of the mobile station or hand held terminal which originates and terminates the air interface. The mobile station also has the intelligence to provide call processing, registration, and handoff functions necessary for call setup and mobility management. The fixed part, the infrastructure network, is shown in Fig. 1. This portion of the wireless network is the topic of this article. The elements of the wireless infrastructure network are the base station (BS) or cell site at which the radio equipment is located, the multiplexers which concentrate the traffic to reduce cost, the mobile switching center (MSC), and the point of interface (POI) between the wireless provider and the public switched telephone network (PSTN). The BS, multiplexer, MSC, and POI are interconnected by leased or privately owned terrestrial or microwave facilities.
The base station controller (BSC) performs radio resource management for multiple BSs. For some technologies such as GSM [1], the BSC forms part of the transport network and voice calls are routed through the BSC to the MSC. Therefore, the cell sites have to be connected to the BSC, which in turn is connected to an MSC. This results in a three-layer network design. For other technologies such as CDMA [2], the BSC is part of the control network, not the transport network; therefore, voice calls do not go through the BSC during the information transfer phase. This results in a two-layer network, where the cell sites are connected to one of the MSCs directly. When the network design algorithms are outlined in the fifth section, we will talk about the design for the CDMA case; here we outline the approach that has to be taken for the GSM case.
The objective of network design is to minimize the overall network cost while meeting customers' network performance objectives. The design specifies the optimal number and locations for the BSCs, MSCs, and multiplexers, and the transport network to carry the traffic from the cell sites to the MSCs, including link capacities and end-to-end routing. There are two main categories of network design scenarios: green field and growth designs. Designing a new transport network from ground zero is considered a green field design. Adding capacities to accommodate growth on an existing network is design for growth. In this article we concentrate on the green field design problem. The ideas from the algorithms for green field design can be extended to the design for growth scenario.

Cost Structure of Wireless Infrastructure

Transport costs are often monthly recurring costs, and a significant portion of the total operating and capital costs for a wireless service provider. A wireless service provider generally leases transport services from incumbent local exchange carriers (ILECs), interexchange carriers (IXCs), and competitive local exchange carriers (CLECs) to build a backhaul network to carry traffic from cell sites to the MSCs to which they are homed. These leased lines are usually coax, copper, or fiber. The cost of leased lines typically have three components: a nonrecurring fee, a fixed monthly fee, and a mileage-based monthly fee. Usually, there is large economy of scale as we move up the transmission hierarchy. For instance, some LECs and IXCs offer the cost of T3 facilities equal to the cost of 510 T1s even though a T3 facility can transport 28 channelized T1 circuits. The bandwidth for a T1 circuit is 1.544 Mb/s; that for is T3 44.7 Mb/s.
Another transport option is to use microwave links. Microwave links have proven popular in international markets where the line-of-sight requirement can be met and the terrestrial telecommunications infrastructure is not ubiquitous. The tariff structure for microwave links are different from that for leased lines. The cost of microwave transport facility in addition to a bandwidth-dependent fee and a mileage-dependent fee also includes the cost of a repeater at regular intervals on the link. Furthermore, the set of bandwidths available with microwave links is different from that available in standard private lines facilities.
Typically, the cost structure is such that that the cost per unit bandwidth decreases significantly as we move up the transmission hierarchy. Therefore, significant cost savings can be realized when multiplexing is performed at the right locations. Circuit multiplexing at various transmission levels is available, usually for a fixed fee, from the carriers at their office locations. The type of transport facility to be used depends on the bandwidth requirement and tariff structure.
The amount of bandwidth needed at a particular location depends on the amount of traffic generated at the location and the networking technology used to transport this traffic. In first-generation wireless networks vocoders reside at each BS. Analog voice signals from the air link are digitized and transformed into 64 kb/s pulse code modulated (PCM) [3] bitstreams by these vocoders. Each voice call is carried using a full DS0 from the BS. Typically, 24 voice calls are multiplexed into one T1 strictly in STM. For example, a cell site with a capacity of 144 voice calls requires six T1 lines to transport the traffic from that cell site.
In second-generation networks digital cellular compression techniques have been used, and each voice call is compressed to 16 kb/s for GSM and TDMA, and 913 kb/s for CDMA. In addition, CDMA provides variable-length packets at the mobile station. It was recognized that it no longer made economic sense to convert each voice into 64 kb/s speech at the BS and use a single DS0 to carry each voice call; therefore, vocoders were moved into MSCs. This compression results in a capacity reduction of four to six times [4]. In contrast to GSM and TDMA, CDMA provides soft handoff which allows a voice call to have multiple handoff legs from which the best speech signals are selected. It is not uncommon to have a voice call spending 3040 percent of the time in soft handoffs. Based on this statistic, handoff legs could on average double the bandwidth requirement for each voice call on the backhaul network. It is therefore essential not to carry CDMA voice calls in DS0 circuits. Overall, transport efficiency of the second-generation networks is much higher than that of the first generation, when the compression and packet nature of source traffic is exploited in the network.
Third-generation wireless networks are likely to be based on ATM technology in the infrastructure network. ATM standard ATM adaptation layer type 2 (AAL2) [4] can transport variable-size CDMA packets from different voice calls in fixed-size ATM cells to achieve high bandwidth efficiency. The advantage of using ATM arises from the availability of standard low-cost high-speed interfaces. The largest variable-size CDMA packet is small (34 bytes) compared to the size of an ATM cell. It is therefore necessary to efficiently multiplex CDMA packets using AAL2. All voice calls between the BS and the MSC are carried in the same ATM virtual circuit connection (VCC). Voice packets from different calls are multiplexed onto the same ATM VCC using AAL2. At the MSC these packets are converted to 64 kb/s PCM.
The interplay between the air interface and the networking technology can be fairly complex. Private lines are appropriate for constant bit rate services. For instance, in GSM each voice call occupies 16 kb/s of bandwidth; therefore, a DS0 can carry four GSM voice calls. For variable-bit-rate voice traffic, both Frame Relay and ATM can take advantage of the statistical multiplexing gain of the voice traffic and may be able to carry the traffic in a more efficient manner. As an example, under the traffic engineering assumption that maximum delay variation is 20 ms and packet loss is no more than 0.1% for statistical multiplexing, the transport efficiencies achieved by ATM and Frame Relay in terms of number of voice channels a T1/T3 facility can carry in a CDMA system is shown in Table 1. The corresponding number of voice channels carried by STM is also shown in Table 1.

Problem Modeling and Solution Approaches

In this section, we outline the wireless network design problem more formally and then outline a solution approach that we have taken to solve the problem.

Problem Statement

In the wireless infrastructure design problem, a wireless service provider is expected to provide the following information as input:

Location of cell sites (BSs) and candidate locations of multiplexers
Number of subscribers and Erlang load, or number of voice channels at each cell site
Candidate transmission facilities and transport technologies
Facility cost or tariff for leased facilities/services

Traffic demand at each cell site in terms of number of voice channels, if not already given, can be determined by the number of subscribers and the Erlang load per subscriber. The objective of the network design algorithm is to decide the location of the MSCs and to design a transport network that connects cell sites to an MSC and the MSC to the POI at minimum cost. More specifically, we need to make the following decisions:

MSC location selection and homing cell sites (BSs) to the MSCs
Interconnecting cell sites to the MSCs
Type and number of facilities, and the transmission speed placed at each link
Traffic multiplexing points
Traffic routing

A Unified Link Cost Model

As discussed in previous sections, there are many options in deploying transport networks. A wireless service provider can build its own network, lease private lines, or lease frame relay/ATM services from telephone companies. It also has several choices of transport technologies, such as STM, frame relay, and ATM. We want to incorporate all these possibilities into a unified model so that one algorithm will be sufficient to solve the problem under various scenarios. The key to this unified model is a generic characterization of link capacity, link cost, and their relationship. To avoid ambiguity, here the terms capacity, speed, and bandwidth are used as synonyms. By facility, we mean a specific transmission hardware at a specified speed.
No matter whether a link is built/owned by a wireless service provider or leased from a telephone company, the only difference is in its cost. A leased line incurs monthly leasing cost determined by the tariff. An owned line has a monthly depreciation/amortization cost. Therefore, monthly costs of both leased lines and owned lines can be considered in a unified manner.
There exist many different types of transmission facilities and speed hierarchies. In the United States there are T1, T3, OC3, and so on. In Europe there are E1, E3, and so on. In Asia, microwave is very popular with channels at speeds of approximately 2 Mb/s, 8 Mb/s, 32 Mb/s, and so on. Although these facilities have very different transmission speed hierarchies, we can choose a common bandwidth unit and translate any transmission speed to this common unit.
In a transmission hierarchy, each level has a specific speed and a specific cost. The relationship between bandwidth and cost can be modeled by a generic cost curve which, for a given bandwidth requirement, gives the minimum cost combination of speed levels needed to make up the required bandwidth, taking into consideration the cost of multiplexing from lower to higher levels. As an example, Fig. 2 displays the cost curve of a T1/T3 digital hierarchy for a link. The hierarchy has two speed levels, T1 and T3, respectively. The common bandwidth unit chosen is DS1. The bandwidth and transmission cost of each speed and the multiplexing cost from its next lower speed level are given in Table 2. Here the costs are assumed to be monthly.
The cost curve is a piecewise linear function. Breakpoints are bandwidth thresholds where the optimal combination of speed levels start to change. If more than one transmission hierarchy is available to a service provider, we need to consider the most economical hierarchy to use on a given link. This will depend on the tariffs of the different hierarchies and the bandwidth requirement. As an example, Fig. 3 shows the cost curve of a digital radio hierarchy for the same link as in Fig. 2. The digital radio hierarchy has three speed levels, DR1, DR2, and DR3, respectively. The cost data is given in Table 3.
Figure 4 displays the composite cost curve marked by the solid lines. The dashed lines represent the segments of the original cost curve of a hierarchy which is higher than that of the other hierarchy. The composite cost curve gives the minimum cost of transmission facilities optimally selected from both hierarchies to satisfy any given bandwidth requirement. For instance, if the bandwidth requirement is one DS1, the optimal facility choice is one T1 at a total cost of $200; but if the bandwidth requirement is 10 DS1s, the optimal choice would be a combination of one DR2 and two DR1s at a total cost of $1500.
Given the traffic requirement on each link (in terms of number of voice channels), transport technologies differ only in the bandwidth each of them requires to transport the traffic as far as network design is concerned. Different bandwidth requirements in turn translate to different costs. Therefore, all the differences among these transport technologies are captured by the generic cost curve, which accounts for statistical multiplexing gains as well.
It should be pointed out that the cost curve at each link is generic enough to incorporate both the one-time link setup cost (if the link is to be used at all) and the capacity-specific cost. Decisions such as traffic concentration and multiplexing are also driven by link cost curves.

Solution Approaches

In this section we outline a solution for the wireless infrastructure design problem. Even simple versions of the problem are NP-hard [5]. Therefore, we use a decomposition heuristic to solve the problem. The algorithm description is for a green field CDMA system. The aim of the design problem is to decide the location of the MSCs, the homing of the cell sites to the MSCs, and the connection of the MSCs to the POIs. We assume that there are multiple POIs for each carrier, and the fraction of the total traffic to be routed to each carrier is also given. In addition, we have to design the backhaul network, including the transmission facilities on each link and the location of the multiplexers. We assume that there are multiple transmission hierarchies. We decompose the infrastructure network design problem into two steps:

MSC location selection and homing of cell sites
Interconnection of cell sites

We now describe these two steps in more detail.
MSC Location Selection and Homing of Cell Sites -- Each cell site is a potential MSC location. Each MSC has a capacity in terms of the number of cell sites homed to it as well as the amount of traffic it can switch. The desired number of MSCs can be specified by the user, or the cost of the MSC can be specified and the algorithm chooses the appropriate number of MSCs. The objective in this step is to locate the MSCs appropriately so that the cost of transporting traffic from the cell sites to the MSCs is minimized. At this stage of the design, we use an estimate of the cost for connecting cell sites to MSCs. For example, one can use the star connection to approximate the cost. The placement of the multiplexers taking advantage of the tariff structure will be done after the MSC locations are chosen and homing of cell sites to MSCs is completed. Even assuming a star connection, the problem of deciding the optimal placement of MSCs is NP-hard. The solution procedure starts off by generating candidate sites for the MSCs. These candidate sites are chosen by formulating an appropriate set covering problem [6] and then using a dual heuristic to solve it. The number of candidate sites selected will be more than the desired number of MSCs. Initially all the cell sites are homed to the closest MSC (subject to the MSC capacity constraint). Then a subset of these candidate sites are selected for the location of the MSCs using a greedy algorithm by sequentially deleting sites that increase the homing cost by the least amount. At the end of this step, we have the location of the MSCs and the cell sites that are homed to each MSC.
Interconnection of Cell Sites -- The cell sites that are homed to a particular MSC have to be connected to the MSC taking into account the multiplexing gains. The exact path that each demand unit will take from the cell site (BS) to the MSC will be determined in this step of the algorithm. Links of appropriate capacity from the appropriate hierarchy have to be designed in this step. Given the bandwidth requirement for a link, the cost of providing that bandwidth from a particular hierarchy can be determined from the link cost curve for that hierarchy. If multiple hierarchies are available, the hierarchy which results in the minimum cost for that bandwidth is used. The discrete nonlinear nature of the cost curve makes the problem of designing the interconnection network NP-hard. Therefore, we use a heuristic approach to solve this problem. The two steps in the heuristic are the following:

Generating an initial solution
Local improvement

A routine that will be used many times in this algorithm is one that gives the optimal allocation of facilities on a given link when the amount of traffic on the link is known. This problem is NP-hard to solve in general. However, using the facts that the cost per unit of bandwidth decreases as the size of the facility increases, and that the speeds in successive levels in a hierarchy are integer multiples of the lower levels, one can design an efficient procedure to compute the optimal cost of facilities given the demand on the link. We refer to this routine as the costing module. The first step creates an initial feasible solution, and the second step improves the initial solution by a local improvement procedure. We now describe each of these steps in more detail.
Initial Solution Construction -- In this step we generate an initial feasible solution to the single MSC backhaul network design problem. In fact, we generate two feasible solutions and pick the better one for further improvement in the next step. The first feasible solution is the star network, where each cell site is connected to the MSC via the direct link. The cost of this solution can be determined by the costing module. Note that there is no multiplexing in the star solution. The second solution takes into account the multiplexing gains. This solution is based on a directional minimum spanning tree. In order to compute the minimum spanning tree solution, we have to define the link cost. These link costs are computed so that a link which can potentially carry a lot of traffic is cheaper than a link which potentially carries little traffic. Note that the actual traffic carried by a link will be known only after solving the problem. Therefore, we have to estimate the actual flow on each link. For each cell site, the fraction of traffic originating at the cell site is assumed to go through each link going out of the cell site. The fraction of traffic is proportional to the shortest distance from the cell site to the MSC using that link. Once this flow is estimated, the cost of the flow on each link is estimated by the costing module, and the unit cost of the link is the ratio of the cost of flow to the flow on the link. This is the cost used as an input to the directed minimum spanning tree algorithm. Once the actual flows on the links are determined by the minimum directed spanning tree algorithm, the cost of installing the appropriate facilities to carry this flow is determined by the costing module. This computes the cost of the minimum directed spanning tree solution. The cost of the star solution is compared to the cost of the minimum spanning tree solution, and the solution with the lower value is taken as input to the local improvement heuristic.
Local Improvement Heuristic -- Recall that the bandwidthcost curve is discontinuous with piecewise linear segments. The type of curve will depend on whether the smallest facility and demand units are the same or not. For the rest of this discussion, we assume that the smallest facility unit is an integer (greater than one) multiple of the smallest demand unit. In this case the cost curve consists of horizontal segments. The flow on a given link is either in the middle of the horizontal segment or at one of its endpoints. If the flow in a link is in the middle of the horizontal portion, there is spare capacity on the link. Each horizontal line segment has a left and right breakpoint. Recall that the initial solution is a tree. If another arc is added to this solution, it will form a unique cycle. This step tries to send flow around the cycle if it results in a cost reduction. When sending flow in a cycle, the flow on some of the arcs will increase and on others will decrease. If the costs are linear, it is easy to compute whether the costs increase or decrease. Since the costs are nonlinear, this computation is done until the decrease in flow causes a decrease in cost on at least one of the arcs in the cycle. In other words, the computation is done until the flow on one of the arcs drops below its first breakpoint. If this results in a decrease in total cost, the new arc is added to the tree and the arc which dropped below its left breakpoint is dropped from the tree. Thus, the tree structure is preserved. This process is repeated until one entire pass through all the arcs does not result in any flow changes.
Once this solution is determined, the actual routing path of the demands from each cell site to the BSC to which it is homed is computed. The cost of the solution consists of the cost of:

The MSCs in the network
Transporting the demands from the BS to the MSC
Transporting the demands from the MSC to the POI

These are aggregated to give the final solution cost.
In the case of GSM networks the cell sites are homed to the BSC, and the BSCs in turn are connected to the MSC. This results in a three-layer system. The solution procedure is similar to the CDMA case outlined above. We execute the location module twice, once to locate the BSC with respect to the cell sites and a second time to locate the MSCs among the BSCs. The cell sites (BSs) are now linked to the BSC. The traffic from the cell sites that are homed to a BSC is consolidated at the BSC (taking into account Erlang concentration) before executing the MSC location module.

Network Design Examples

Because of the economy of scale offered by most tariff structures, appropriate optimization on traffic concentration and routing can substantially reduce transport cost. We first use an example to show the impact of transport optimization.

Example 1

The example has 15 nodes randomly generated over a 200 x 200 mi². One of these nodes is fixed as the MSC. All other nodes have demands which are uniformly generated between 1 and 30 DS0s. We only consider two types of transmission facilities: T1 and T3. The method of transport in the network is STM, where a single DS0 is used for each voice call. Their tariffs are given by Table 4. All the cost in the table are monthly costs.
We want to design a network which connects all the nodes to the MSC. We compare two designs. The first one is the commonly used star connection as shown in Fig. 5. The second, more cost effective design produced by the design tool, is shown in Fig. 6. The star design has a total cost of $9467, and the second multiplexed design has a cost of $7632. This particular example shows that the transport optimization results in a saving of about 20% in the total transport cost.

Example 2

In this example, we examine the effect of technology on the design of an infrastructure network. This example also illustrates the following capabilities of the network design tool:

Optimal number and location of MSCs
Homing of cell sites to MSCs
Network connecting cell sites to MSCs
Traffic concentration/multiplexing and routing to reduce transport cost
Evaluating different transport technology alternatives (STM, ATM, and frame relay) and different tariff structures

The example is again a randomly generated problem with 100 nodes. The nodes are generated uniformly within a 100 miles x 100 mi² area. Demand at each node is also uniformly distributed between 150 voice channels. Although nodes and traffic are generated randomly for illustration purposes, the tariff structures we use are real. We only consider two types of transmission facilities, T1 and T3, because they are the most commonly used in the United States. Their monthly leasing costs are given in Table 5.
We consider three transport technologies: STM, ATM, and frame relay. We assume that T1 and T3 facilities are leased to serve as physical transport pipes. The switching/muxing services to support each of the three technologies can be either leased or provided by installing privately owned equipment. In the latter case, an amortization period of eight years is used to derive the monthly cost figures.
For STM (circuit multiplexing), bandwidth in terms of number of voice channels and multiplexing cost are given in Table 6, where $50 can be considered the grooming cost at the T1 level.
For ATM, the number of voice channels supported by T1 and T3 are given by Table 7. Here, the bandwidth numbers for ATM are taken from Table 1. The cost of a simple ATM switch with only a few T1 interfaces is assumed to be $50/mo, while the cost of a full-functionality ATM switch is assumed to be $1000/mo.
For frame relay, we assume that only T1 interfaces are available, and therefore while multiplexing from T1s to T3s we have to use STM multiplexing. We further assume that there is no traffic grooming at the T1 level. Again from Table 1, we assume that a T1 can support up to 121 voice channels using frame relay. We use this capacity to determine how many T1s are needed at each node. From this point on, it is essentially an STM design. For both the ATM and frame relay cases, we do not consider the costs of ATM and frame relay interfaces because we are only focusing on the differences in recurring transport cost.
We run the tool for each of the three technologies to create three designs. In all three runs the number of MSCs to be used was set at two. Figure 7, Fig. 8, and Fig. 9 show the network topologies of the designs for STM, ATM, and frame relay, respectively. In the cases of STM and ATM, there are many traffic concentration points where grooming or multiplexing is performed to take advantage of economy of scale in the tariff structure. In the case of frame relay, the topology is a star connection because no grooming is allowed at the T3 level, and T1 to T3 multiplexing does not seem economical.
It should be pointed out that the comparisons for STM, ATM, and frame relay shown in Table 8 are only for the specific example based on our specific assumptions and should not warrant any general conclusions. Our purpose in using this example is to demonstrate the tool's capability to evaluate different technology alternatives in specific tariff and traffic scenarios. Different tariff structures and traffic assumptions affect the design drastically.

Summary and Future Work

In this article we have outlined the different technology and transport alternatives available to a wireless infrastructure designer. We also outlined the effect of these alternatives on the design of an optimal infrastructure network. We then formulated the optimal network design problem and developed a solution procedure for generating a good solution. This was followed by some examples illustrating the economic trade-offs.
So far, the focus of our work has been on the transport aspects of wireless networks. An equally important task is to provide a design tool for control complex design. The call processing and mobility management functions such as handoffs, paging, and registration will be handled by servers in the wireless network. Currently message flows are being identified for each of the call processing scenarios, such as origination, location updates, and handoffs. These control functions will be implemented on commercial platforms such as HP or Sun workstations. Each call processing function such as origination has end-to-end delay objectives. We intend to model and analyze the call processing scenarios with a view to developing engineering rules for sizing the control servers. The objective is to incorporate these rules into a control complex design tool which, along with the transport design tool, will enable the design of the complete wireless network.

Acknowledgments

We gratefully acknowledge insightful discussions with Alan Cipolone, Sujan Dasgupta, Bharat Doshi, Edmond Hong, Marc Hornby, and Albert Jordan. We thank Bharath Ramana and Kishore Talagadadeevi for their programming assistance.

References
[1] M. Mouly and M. B. Pautet, The GSM System for Mobile Communications, 1992.
[2] "IS95: A Mobile Station -- Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System," TIA, Mar. 1995.
[3] J. Bellamy, Digital Telephony, Wiley Series in Telecommun., 1991.
[4] J. H. Baldwin et al., "AAL-2 - A New Adaptation Layer for Small Packet Encapsulation and Multiplexing," Bell Labs Tech. J., Spring 1997, pp. 11131.
[5] H. R. Garey and D. S. Johnson, Computers and Intractibility, Freeman, 1979.
[6] S. Even, Graph Algorithms, Computer Science Press, 1979.

Biographies
Subra Dravida obtained his B.Tech. degree in electrical engineering from Indian Institute of Technology, Madras, in 1979. He earned his M.S.E.E. and Ph.D. degrees in electrical engineering from Rensselaer Polytechnic Institute, Troy, New York, in 1980 and 1984, respectively. Since December 1983, he has been with Bell Laboratories, where he is currently a technical manager in the Performance Analysis Department. His work activities and responsibilities include work on protocols, architectures, and network design algorithms for ATM/SONET, wireless, optical, and cable networks. He holds 12 patents related to networking with another 14 applications pending.
Hong Jiang received her M.S. and Ph.D. in electrical engineering from Northwestern University. Since joining Bell Laboratories-Lucent Technologies in 1995, she has been involved in analyzing the performance of a distributed and ATM-based next-generation wireless network and cellular digital packet radio. She also evaluated the economic trade-offs of Lucent's current and next-generation wireless infrastructure products employing new transport technologies. She is currently designing an all-wireless multimedia network with airborne base stations.
Murali Kodialam received a Ph.D. in operations research from MIT in 1991. He has since worked in AT&T Laboratories and Bell Laboratories. His research interests are in the areas of resource allocation in communication networks and performance analysis.
Behrokh Samadi is a technical manager in the Performance Analysis Department at Bell Laboratories-Lucent Technologies. She holds a B.Sc. Honors degree in mathematics from University College London, and M.S. and Ph.D. degrees in computer science from Stanford University and UCLA, respectively. Her interests include algorithm design and performance analysis of wireless, computer communication, and distributed systems.
Yufei Wang received the BS degree in Mathematics from the University of Science and Technology of China in 1983, the MS and Ph.D. degrees in Operations Research from Cornell University in 1989 and 1992 respectively. He is currently a member of technical staff at Bell Laboratories of Lucent Technologies. His area of interests include network design, analysis, restoration, and performance.