|
Article Excerpt
1. Introduction
As is evident from the fierce price wars of the 1990s and the continued attempts by the Baby Bells to obtain regulatory approval to offer service, the long-distance communications industry in the United States is competitive. In the two decades since the breakup of the Bell Telephone System, the price of a long-distance phone call has fallen from more than $0.32 per minute in 1984 ($0.52 per minute in 2000 dollars) to an average of $0.12 per minute in 2000 (FCC 2001). And there are more than 700 companies offering long-distance service, all vying to capture a larger share of the $109 billion market (Lande and Lynch 2002), dominated by AT & T, WorldCom, and Sprint.
To compete effectively in the market, particularly given the difficult economic climate of the past few years, both large and small companies must explore every available avenue for reducing operating expenses. Access charges, which are the fees long-distance companies pay to local telephone companies to originate and terminate calls, comprise the largest portion of a long-distance company's network operating expenses. Traditionally, access rates have been set higher than the actual cost to the local telephone company as a means of indirectly subsidizing local phone service. In recent years, as part of its efforts to open local markets to competition, the FCC adopted a market-based approach to drive access charges toward the cost of providing service (FCC 1999). The resulting changes in the access rate structure have had two main impacts on the long-distance industry. One, the per-minute costs for originating and terminating a call have decreased, as a percentage of revenue, from 35% in 1996 to 25% in 2000. (At the time of divestiture in 1984, per-minute access charges accounted for 54% of revenue (FCC 2001).) Two, the relative price changes among the cost elements for the two main alternatives for interconnecting with the local telephone company have created opportunities for the long-distance companies to achieve additional savings by optimizing their access strategy. We call the problem of designing networks that minimize the access charges paid by a long-distance company to the local telephone company the long-distance access network design (LDAND) problem. In this paper, we develop and test an optimization-based solution approach for the LDAND problem.
The LDAND problem arises in each of the 184 local access and transport areas (LATAs) in the U.S. local telephone companies handle calls within a LATA, while long-distance companies handle calls between LATAs. Figure 1 illustrates the key components of the LDAND problem. (More detailed descriptions of access networks are available on the websites of several telephone companies. See, for example, www.qwest.com.) The LDAND problem involves two types of nodes: end offices (EOs), labeled A, B, C, D, and E in Figure 1, and a point of presence (POP). An EO is a collection point in the local telephone company's network for many (hundreds) individual customers. A long-distance carrier interconnects its facilities with the local company's network at a specially designated node, the POP. Transmission services leased from the local telephone company carry long-distance traffic between the POP and the EO that serves an individual customer.
[FIGURE 1 OMITTED]
Local telephone companies currently offer two types of transmission service between an EO and a POP, and they specify the associated charges in a tariff document filed with the FCC. Table 1 shows a sample tariff table. With direct trunked transport (DTT), a long-distance company leases dedicated facilities from the local telephone company to carry traffic between an EO and the POP. The long-distance company pays the local company a monthly fixed charge based on the type and the length of the facility leased. In Figure 1, dedicated DTT facilities leased between EO-A and the POP are represented by the solid line connecting the two nodes. With tandem switched transport (TST), the local company carries traffic on shared circuits from an EO through a tandem switch to the POP. The long-distance company pays fees to the local company based on usage--a per-minute charge for each minute of traffic carried. In Figure 1, shared TST circuits between EO-B and the tandem switch are represented by the dotted line connecting the two nodes.
Each type of transport service favors a different traffic pattern. With DTT, a long-distance company must pay the cost to lease all of a facility's capacity regardless of how much traffic is carried. Consequently, leasing dedicated facilities is generally cost effective for EOs generating and receiving large amounts of traffic at a steady rate throughout the day. Conversely, with TST, the long-distance company only pays for the actual traffic carried, so there is no penalty associated with low utilization. Compared to the equivalent per-minute cost on a dedicated facility with high utilization, however, the per-minute charge for TST is more expensive; therefore, TST is cost effective for EOs with small amounts of traffic occurring infrequently throughout the day.
When permitted, the most economical solution is to lease a combination of the two service types and to use a "fixed alternate routing" policy (Freeman 1996), as illustrated for EO-A in Figure 1. Under this strategy, traffic from (to) EO-A would be offered first to the group of dedicated DTT circuits connecting EO-A and the POP. Any traffic blocked by the dedicated circuits would overflow to the shared circuits (dotted line from EO-A to the tandem switch) and be transported to (from) the POP via the tandem switch. Determining the number of dedicated circuits to lease between each EO and the POP is a dimensioning problem, and the solution depends on the distribution of the traffic throughout the day and the costs for DTT and TST.
For access networks, dedicated transmission facilities are available at two standard rates: 1.544 Mbps and 44.736 Mbps, labeled DS1 and DS3, respectively. In general, a long-distance company will lease DS1 facilities for DTT. However, because of strong economies of scale, DTT costs often can be reduced by creating hubs. Under a hubbing strategy, each EO in a cluster is connected by DS1s to a hub node (which may be the POP). At the hub, their multiple low-speed DS1 signals are consolidated into a high-speed DS3 signal. The signals are consolidated using an electronic device called a multiplexer, which has the capacity to combine 28 DS1 signals into one DS3 signal. The DS3 signal then is transmitted from the hub to the POP. In Figure 1, a multiplexer is installed at EO-D to create a hub. The DS1s from EO-C, EO-D, and EO-E all are consolidated into a DS3 signal that connects EO-D to the POP. A second hub would be located at the POP to multiplex the DS1 facilities leased from EO-A. Determining the best hubbing strategy requires solving a hub location problem, and the solution specifies which nodes should be designated as hubs, how many multiplexers are required at each hub and how the EO demands should be routed, either directly to the POP (on DS1s) or via a hub.
The two subproblems of the LDAND problem, the dimensioning problem and the hub location problem, require different units of demand. The dimensioning problem deals with traffic demand, expressed in Erlang units, and considers the variation throughout the day. The hub location problem works with the number of circuits leased for DTT at each EO, which is an output of the dimensioning problem. This linkage between the two problems suggests a natural two-step solution approach: determine the number of DS1s to lease between each EO and the POP and then solve the hub location problem. However, this approach ignores the fact that the two aspects of the problem are interdependent. As will be evident, the best hubbing strategy depends, in part, on the number of DS1s leased for DTT from each EO, so the solution of the hub location problem depends on the solution of the dimensioning problem. In addition, because the cost of leasing facilities for DTT depends on the distance between an EO and the hub (or POP) to which it homes, the appropriate number of DS1s to lease, which is the solution of the dimensioning problem, depends on the solution of the hub location problem. Consequently, our model and solution algorithm must consider the interrelationship between the dimensioning problem and the hub location problem.
The rest of this paper is organized as follows. We conclude [section]1 with a review of the related literature. We present our model for the LDAND problem in [section]2. In [section]3, we describe an iterative solution algorithm that combines the queueing aspects of the dimensioning problem with an integer program for the hub location problem. In [section]4, we present computational results, which indicate that our solution approach is effective in designing low-cost access networks. We provide concluding remarks in [section]5.
Related Literature. Broadly defined, local access networks connect customers to a switching center that interconnects with a backbone network. In the associated design problem, demands from multiple source nodes (EOs) must be routed to a single sink node (the POP), and link capacities, selected from a set of standard types, must be assigned. Models for local access network planning have grown out of the work in centralized teleprocessing network design of the 1970s (for example, see Boorstyn and Frank 1977 and McGregor and Shen 1977). The survey papers by Gavish (1991) and Balakrishnan et al. (1991) provide a good introduction to the practical issues and the modeling aspects of local access network design. Researchers have studied several variations of the local access network design problem, with the major differences arising from assumptions on the topology of the underlying physical network, the treatment of existing facilities, and the structure of the facility costs. Balakrishnan et al. (1991) develop a general framework based on a layered network representation that encompasses a broad range of the single-period planning models that have been discussed in the literature.
Early work restricted the access network to a tree structure. Only recently have researchers studied access networks with no restrictions on the underlying physical network. Sherali et al. (2000) model an access network hub location problem that includes multiplexer installation costs with a discrete nonlinear function. The authors apply the reformulation-linearization technique to develop two stronger formulations and design a heuristic that combines an exact solution procedure and a Lagrangian dual-based heuristic. They conduct computational experiments on 80 instances generated using simulated and real data. The hybrid solution approach finds an optimal solution for 70 of the 80 problems and solutions within 2.6% of the best known for the remaining 10.
The local access network design problem is a special case of the more general network design problem studied by Salman et al. (2001). The authors propose a branch-and-bound technique called search by objective relaxation (SOR) to solve problems where capacity is installed in discrete quantities and the associated cost function exhibits economies of scale. The algorithm is based on solving relaxations that are obtained by approximating the noncontinuous function by its convex envelope. For randomly generated test problems, the SOR method solves to optimality problems with 10 nodes and is effective in reducing the integrality gap for problems with 20 and 30 nodes.
Frantzeskakis and Luss (1999) describe a capacity expansion model with the additional complexity that the embedded network may be rearranged. That is, demand may be rerouted and existing facilities may be disconnected or used differently at a cost. The authors formulate the problem as a network flow problem and develop a heuristic to solve it. Computational results on eight realistic test networks, ranging in size from 38 to 89 locations, indicate that the heuristic quickly finds solutions within 0% to 7.6% of optimality. The authors find that there is substantial benefit in allowing demand rearrangement; network costs are 7% to 39% higher when no rearrangement is allowed.
Sherali et al. (2000) and Salman et al. (2001) considered the design of new networks, while Frantzeskakis and Luss (1999) studied capacity expansion. For these three papers, and for the general network design literature, an underlying assumption is that demand is expressed in (discrete) units of circuits. In contrast, our assumption is that demand is expressed in Erlang units, which is typical for voice traffic and, hence, our work must consider the interaction between the queueing problem and the facility location problem. We believe that including the interaction between the two components more accurately models the long-distance access network design problem and provides the potential to telecommunications planners for even greater costs savings.
The contributions of this work to the literature are twofold. First, for a competitive industry where it is critical to reduce costs to be profitable, we describe a methodology to significantly lower the access costs paid by a long-distance company. And second, we explicitly consider the interaction between the queueing (or dimensioning) problem and the facility location problem, an approach that, to our knowledge, is novel to the literature.
2. Problem Formulation
In this section, we present the formulation of the LDAND problem. To begin, we describe how we model the fixed alternate routing policy as a queueing system and how we simultaneously consider the dimensioning and the hub...
|
