Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Efficient routing of telephone calls in a circuit-switched network Braun, Darrel 2000

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2000-0347.pdf [ 3.08MB ]
Metadata
JSON: 831-1.0089511.json
JSON-LD: 831-1.0089511-ld.json
RDF/XML (Pretty): 831-1.0089511-rdf.xml
RDF/JSON: 831-1.0089511-rdf.json
Turtle: 831-1.0089511-turtle.txt
N-Triples: 831-1.0089511-rdf-ntriples.txt
Original Record: 831-1.0089511-source.json
Full Text
831-1.0089511-fulltext.txt
Citation
831-1.0089511.ris

Full Text

EFFICIENT R O U T I N G OF T E L E P H O N E IN A C I R C U I T - S W I T C H E D  C A L L S  N E T W O R K  by Darrel  Braun  B.Sc. (Computer Science) University o f Victoria,  A  1981  m a j o r essay s u b m i t t e d i n partial fulfilment o f the requirements for the degree  o f  Master; o f Science (Business Administration) in  T H E F A C U L T Y OF G R A D U A T E STUDIES (Department of Commerce and Business Administration)  We accept this thesis as conforming to the required standard  T H E UNIVERSITY OF BRITISH C O L U M B I A June 2000 © Darrel Braun, 2000  In presenting degree  this thesis  in partial fulfilment  of the requirements  for an advanced  at the University of British Columbia, I agree that the Library shall make it  freely available for reference and study. 1 further copying of this thesis for scholarly purposes department  or by his or her representatives.  agree that permission for extensive  may be granted It  by the head of my  is understood  that  copying or  publication of this thesis for financial gain shall not be allowed without my written permission.  Department of L ^ o v e r - c e .  <ani  8oS<ngs_s  The University of British Columbia Vancouver, Canada  Date  DE-6 (2/88)  Slooo  /Icm'inislrjio'n  Abstract Every year Telus invests tens of millions of dollars to increase the capacity of their circuit-switched network in response to growth in demand. Growth has accelerated in recent years due to rapid increases in data and Internet traffic, and the introduction of flatrate long-distance services. This in turn has forced Telus to accelerate their investments in the network to keep pace with demand. Circuit-switched technology is inefficient in comparison to newer packet-switched technology, especially for data, which constitutes a large and increasing portion of network traffic. In the near future Telus intends to begin the move away from a circuit-switched to a packet-switched network. Investments in the circuit-switched network will have very little value after the move to a packet-switched network. Therefore Telus is looking for ways to reduce the investments needed in their circuit-switched network. One possibility for reducing investments is to use the existing network more efficiently by improving the call routing. Every call has an origin switch and a destination switch. Most calls are routed on a circuit linking the two switches directly. Call routing concerns processing of calls where the direct circuit is either fully occupied or does not exist, in which case calls are routed indirectly through one or more intermediate switches. Presently Telus uses a method called Fixed-Hierarchical Routing. This is a fairly inflexible scheme that routes overflow calls through one of only two of the 33 lower mainland switches. The project team is investigating Sequential Alternate Routing which would allow calls to be routed through any of the 33 switches. A key tool in this investigation is a network simulator that was written for this project. The simulator will be used to compare the performance of various new routing schemes, and the simulation results will be used when recommending a scheme to Telus. The simulator was subjected to a number of tests to verify that it functions as intended. A key finding of those tests is that the simulator tends to underestimate the number of calls blocked due to network congestion, but that this effect can be managed through the judicious choice of the simulation run parameters. The tests also led to insights into the choice of appropriate measurement criteria comparing the performance of routing schemes.  ii  Table of Contents Abstract  ii  Table of Contents  iii  List of Figures  vi  List of Tables  vii  Chapter 1 - Introduction  1  The Telus Project  3  A Basic Circuit-Switched Network  4  Fixed Hierarchical Routing  5  Quality of Service  6  Idealised Network Design  8  Network Augmentation Decisions  9  Routing Rules  10  Chapter 2 - Literature Review  13  A Performance Comparison of Competitive On-Line Routing and State-Dependent Routing  '.  13  Comparison of Routing Methods for DCS-Switched Networks  14  Blocking Probabilities in Large Circuit-Switched Networks  16  Routing in Circuit-Switched Networks: Optimization, Shadow Prices and Decentralization  16  Bounds on the Performance of Dynamic Routing Schemes for Highly Connected Networks  18  Efficient Routing of Telephone Calls  19  A Global Optimization Routing Model and Applications in Telecommunication Networks  •• 20  Literature Summary  21  Chapter 3 - Methodology  22  Network Simulator  22  Verifying the Simulator  23  Validating the Simulation Model  24  in  Running Simulations  24  Comparing Routing Schemes via Simulation  26  Simple Improvement Heuristic  27  Multi-Commodity Network Flow Linear Program  27  Chapter 4 - Results  29  Manual Simulation Check  29  Call Generator Tests  30  Call Creation by OD Pair  30  Variables  30  Hypothesis  •  31  Goodness-of-Fit- Test  31  Call Arrivals over Time  31  Service Times Distribution  32  Variables  33  Hypothesis  34  Goodness-of-Fit- Test  34  Call Placement Balance  34  Observed Versus Expected Blockage  36  Simulation Understates Blockage  37  Fixed Increments Timing Effects Test  38  Comparison of Routing Schemes  40  Chapter 5 - Discussion and Recommendations  43  Chapter 6 - Areas for Further Investigation  44  Chapter 7 - Conclusion  45  Appendix 1 - Manual Simulation Rerun  47  Simulation by Program  47  Simulator Input Files  47  Simulator Output Report  48  Manual Simulation Rerun  49  Appendix 2 - Call Generator Tests  50  Call Arrivals by OD Pair  50  iv  Call Arrivals over Time  51  Appendix 3 - Call Placement Balance  52  Determining a Warm Up Period  52  Call Placement Test  53  Appendix 4 - Observed Versus Expected Blockage Determining a Demand Range and Warm Up Period  54 55  Appendix 5 - Comparison of Routing Schemes  57  References  59  v  List of Figures Figure 1: Basic Circuit-Switched Network  4  Figure 2: Fixed Hierarchical Routing in the Lower Mainland  6  Figure 3: Routing Rules Revision Process  29  Figure 4: Histogram of Calls Generated in 4999 Minutes  32  Figure 5: Call Placement Verification Model  34  Figure 6: 95% C.I. on Mean Blockage  35  Figure 7: Erlang's Loss Formula  36  Figure 8: Observed Versus Expected Blockage  37  Figure 9: Ratio of Observed Blockage to Expected Blockage  38  Figure 10: Effects on Blockage of Call Placement/Removal Timing  39  Figure 11: Ratio of Observed to Expected Blockage with Different Time Intervals  39  Figure 12: Test Network for Comparison of Routing Schemes  41  Figure 13: Mean Maximum Blockage Across all OD Pairs  42  Figure 14: Mean Blockage on OD Pairs with the Most Blockage  43  Figure 15: Warm Up Period - Run #1  52  Figure 16: Warm Up Period - Run #2  53  Figure 17: Warm Up Period — Run #3  53  Figure 18: Exponential Call Lengths Probabilities  55  Figure 19: Initial Conditions Effects at Medium and High Demand, Run #1  56  Figure 20: Initial Conditions Effects at Medium and High Demand, Run #2  56  vi  List of Tables Table 1: p-values of Observed versus Expected Calls  31  Table 2: Call Service Times Probability Input File  32  Table 3: Service Time Probabilities for Fixed Length Thirty Minute Calls  33  Table 4: Chi-Squared Test of Call Lengths  34  Table 5: Arc Capacities by OD Pair  47  Table 6: Routes = Origin, [Tandem], Destination  47  Table 7: Calls per Minute by OD Pair  47  Table 8: Mean Service Times by OD Pair  47  Table 9: Output Report (extract)  48  Table 10: Manual Rerun - Minutes 1 to 13  49  Table 11: Mnual Rerun - Minutes 14 to 25  49  Table 12: Chi-Squared Test of Observed Calls to Expected Calls  50  Table 13: Histogram of Calls Generated per Minute  51  Table 14: Descriptive Statistics for Blockage from 33 Test Runs  54  Table 15: t-Test: Paired Two Sample for Means  54  Table 16: Alternate Routes for FHR  57  Table 17: Differences in Alternate Routes for SAR versus F H R  58  vn  Chapter 1 - Introduction For most of the twentieth century the vast majority of telephone traffic comprised voice calls. Most of those calls have been carried over circuit-switched networks in which circuits connect telephones to switches and switches to one another. A person placing a call enters the number of the called party, and the system checks for a route with unused circuits between the switches connecting the caller to the callee. If no available route is found the call is blocked, and the caller receives a fast busy signal or " A l l circuits are busy" message. Far more often a route is found and, provided the called number is not busy, the call is put through. The route then, which consists of a specific series of circuits and switches, remains fully dedicated to that call, and unavailable to all other calls, until the call completes.  Circuits were originally twisted wire pairs that could each carry exactly one telephone call, but this was quite inefficient because voice calls use only a small portion of the capacity of a twisted wire pair. In 1948 engineers at Bells Labs developed a high-speed digital transmission system known as Pulse Code Modulation (PCM). P C M takes 8000 8-bit samples per second to convert analogue sound waves to digital signals. In 1962 Bell introduced the first commercial use of P C M , and today P C M and related coding techniques are used in telecommunications world-wide.  P C M serves as an enabling technology for Time-Division Multiplexing (TDM). This is a line sharing technique that places multiple calls on a single circuit. The current state of the art with T D M can place 96 simultaneous calls on a single twisted wire pair, although most North American telephone companies (telcos), including Telus, operate with a standard 24 calls per circuit. In effect each call is given dedicated use of l/24 ofthe th  circuit.  P C M is a big improvement over the days when each circuit could carry just one call, but it is still less than ideal because the calls are not compressed. In particular, data calls can be very choppy, often coming in short intense bursts of activity followed by long periods  1  of inactivity. During the periods of inactivity the call occupies a link but doesn't use it. Circuit-switched networks were not designed to identify data calls, making reliable figures difficult to obtain, but with the explosive growth of the Internet and E-commerce, data calls are becoming far more frequent.  Compounding the problem of data calls in circuit-switched networks are their very different statistical properties from those of voice calls. Circuit-switched networks were designed for voice calls with an average service time of 4 to 6 minutes, but for data calls the average service time is much longer than for voice calls and has a higher variance (Titch, 1997, see also Telecommunications News, Sept. 1998). Some data calls, including dial-up credit card verifications, are very short. Others, such as Internet modem connections, are often 30 minutes or longer (Titch, 1997). In addition, with cheap, flatrate Internet access, some subscribers choose to maintain permanent dial-up connections that are, in effect, infinitely long. From a telco's perspective, a permanent dial-up connection essentially removes one trunk from a route.  A more efficient method of transmitting both voice and data is with packet switching. In a packet-switched network calls are digitised and split into a series of small packets that are sent individually through the network. Each packet finds its own route, so the packets for a given call may follow any number of different routes through the network. This is more efficient than circuit switching because packets are sent only as needed. During periods of inactivity nothing is sent. The dynamic routing of packets also makes packet switching more responsive than circuit switching to changes in network congestion.  Many telcos, Telus included, are moving away from circuit switched networks to a form of packet switching called Asynchronous Transfer Mode (ATM). However such a move can not happen overnight. For Telus the migration to A T M is planned to start in early 2001 but will take a number of years to complete. In the meantime Telus must continue to support and augment their existing circuit-switched network to meet evergrowing demand. Telus spends approximately $60 million annually on the circuit switched network in British Columbia. According to Telus engineers, little of this  2  investment will be of use in an A T M network. Therefore, much of the equipment now being installed in the circuit-switched network will be obsolete, with little salvage value, long before it has been fully depreciated. The Telus Project The Vice President of Wireline Engineering Ferdi Shell invited the University of British Columbia's Centre for Operations Excellence to propose ways that Telus could reduce the level of investment needed in the circuit-switched network. As outsiders to the telecom industry, the COE could take a fresh look at the problem from a perspective that cut across organisational boundaries to gain a broad view of the issues governing network investments. In addition, the COE could bring access to the latest developments in academic thought on network design and operations. The mandate given to the COE for this project was to find means by which Telus could avoid or delay investments in their circuit-switched network prior to December 2000, after which the start of the transition to A T M was planned.  We started with an initial investigation that identified four broad areas of potential savings. First, Telus could simply reduce their investments, and allow service levels to degrade somewhat. This might be acceptable as a short-term strategy provided that the degradation was not excessive. Second, since the existing network has grown slowly over time, through thousands of individual augmentation decisions, the resulting design is almost certainly not optimal for the current traffic. It is possible that with a few key changes Telus could move their network closer to an optimal design, one that would result in more efficient use of the existing infrastructure. Third, much of the ongoing network growth consists of adding circuits as needed between existing switches, but the particular cost accounting that informs the investment decisions may not always lead to the most cost effective investments. Fourth, an important aspect of network operations is the rules by which calls are routed through the network. Calls between a pair of switches can connect over only a fixed set of routes. Improving these routing rules can make for more efficient use of the existing network through strictly operational changes. We chose this fourth option as our initial avenue of approach.  3  A Basic Circuit-Switched Network Figure 1 shows a basic circuit-switched network. Telephones are attached to switches either directly or through a remote. When a call is placed, if the calling and called phones are attached to the same switch then the call is connected directly. Often, the calling and called phones are on different switches. The origin switch then determines which destination switch serves the called phone and, in the simplest case, completes the call via a trunk group connecting the switches.  Switch B  Switch C  Figure 1: Basic Circuit-Switched Network  Network components include: >  A switch is a device that forms connections between pairs of circuits in order to route calls through a circuit-switched network.  >  A tandem is a switch serving as an intermediate switch between two other switches.  >  A remote or slave is a limited capacity switch. It normally does no switching but collects individual telephone lines into a trunk group for its master switch.  >  A circuit is a communication link connected to a switch. Circuits include the twisted wire pairs of individual telephone lines as well as the trunk groups between switches.  >  A trunk is a connection between a pair of switches with a capacity for exactly one phone call. Trunk is synonymous with circuit. Trunk is used more commonly in North America, and circuit elsewhere.  >  A trunk group is a collection of trunks between two switches.  4  >  A trunk card is a circuit board that connects a trunk to a switch. Most trunk cards have a capacity of 24 trunks - i.e. 24 simultaneous calls. Optical trunk cards have much higher capacities, such as 672 trunks, which is 28 * 24 simultaneous calls.  >  A rack is a cabinet with a fixed number of slots for mounting trunk cards.  >  A T D M (Time Division Multiplexer) is a concentrator that time-slices multiple calls onto a single circuit.  Fixed Hierarchical Routing There are far too many switches in a large telephone network to fully interconnect them all. For long distance calls in particular there is often no direct connection between switches. Nevertheless, barring network outages, any switch in North America can connect to any other switch. This is achieved through a method called Fixed Hierarchical Routing (FHR), consisting of a hierarchy of switches with switches at the lowest level denoted as class 5s and those at the highest as class Is. A l l calls begin and end with class 5 switches. There are many class 5s, and relatively fewer switches of each higher level, with only a few class Is for all of North America. The class 1 switches are fully interconnected. Every switch below class 1 is linked to a higher level switch called its home, and every switch above class 5 is home to one or more lower level switches.  Where traffic volumes warrant, some direct links, called High Usage (HU) routes, are added directly between switch pairs separate from the hierarchical links. For example, two class 4 switches might be directly linked, or a class 5 switch might link to its class 4 home and by a H U route to a another class 4. By convention H U routes are only ever built between switches separated by at most one level in the hierarchy.  5  Figure 2: Fixed Hierarchical Routing in the Lower Mainland  Telus uses a form of F H R to route lower mainland toll-free calls. Figure 2 illustrates routing in this network. The lower mainland has thirty-three switches divided into east and west sectors. Two switches, Mutual and New Westminster, serve as tandems for the west and east sectors respectively. Most calls follow a direct, or Primary High Usage (PHU), route, but if the P H U is blocked, an attempt is made to place the call through the tandem switches. For a call from switch West A to East B the first alternate route is called an Intermediate High Usage (IHU) route and goes through Mutual to East B. If the IHU is blocked there is second alternate route, called an Alternate Final (AF), that goes through both Mutual and New West to East B . Quality of Service Networks are engineered to provide a certain quality of service (QoS), defined as the probability of a call being blocked due to all circuits being busy during the period of peak demand. At Telus the target QoS is P.01, which is to say that the probability of a call being blocked is at most 1%. Peak demand is measured as an average of the busiest hour per day over the busiest days of the week during the busiest season, but excluding Christmas, Mother's Day and special events. This is called a bouncing busy hour because the peak hour may vary from day to day. In North America demand is usually expressed in units of centi-call seconds (CCS) equal to 100 seconds of call time. That is, a single 100 second phone call and two 50 second calls would both equal one CCS. 6  Elsewhere in the world demand is usually expressed in Erlangs equal to one hour of call time or 36 CCS.  To maintain service at or above a given QoS, network engineers must ensure that there are an adequate number of trunks in the trunk groups for the demand between each pair of switches. Trunks are added to groups twenty-four trunks at a time by installing new trunk cards at either switch. The cost of each card is about $10,000, and the cost of a new card rack, if needed, is about $100,000. These costs make it impractical to build arbitrarily large trunk groups, therefore, the engineers seek to install the fewest trunks needed to achieve a given QoS.  Telus engineers determine size trunk groups through a set of tables developed by Bell Systems traffic engineers. These tables, called Neal-Wilkinson peaked traffic tables, are from a field of engineering called Equivalent Random Theory. They give the trunk group size needed to support a given traffic load at a particular QoS. In the tables, traffic load is characterised by its mean and variance, and the ratio of the variance to the mean is referred to as the peakedness of the traffic. If the peakedness is less than one the traffic is said to be smooth, and if it is greater than one it is peaked. Traffic with an unequal mean and variance is transformed to an equivalent Poisson random load with equal mean and variance. The Poisson load can be approximated using the Rapp formula (Alternative Routing Systems. University of Cape Town, 1999). The trunk group size needed to ensure a given QoS for the Poisson load is found by applying Erlang's traffic formulas.  As strictly a short term tactic, Telus could allow service levels to degrade below P.01 rather than make further network investments. This option starts to become attractive near to the transition date to A T M because, presumably, the move to A T M would restore service to a level of P.01 or better. Near the transition date, therefore, Telus might chose to forego further investments in the circuit-switched network.  7  Idealised Network Design Telecom networks are rarely designed from a blank slate. Rather, they grow over time reflecting changes in technology and demand. However, it should be instructive to design an idealised network for the demand as i f one were starting from a blank slate. Such a design could give insight into how far the existing network is from the ideal. B y comparing the topology of the existing network to that of the ideal network, it might be possible to find cost-effective investments to improve the efficiency of the existing network. For example, the existing network might be found to have hidden reserves of under-utilised capacity that could be recovered at little cost  Typically the problem of designing a telecom network from a blank slate is broken down into a number of inter-related sub-problems. At the highest level is the problem of determining the number and placement of switches and remotes. Here the objective is to minimise the cost of the switches plus the cost of running wires to individual subscribers. These costs are largely governed by the geographic distribution of subscribers and by the cost versus capacity trade-offs of the switches. After that is the problem of placement and designation of switches by class type for the class hierarchy. Next is the problem of determining the size, technology and configuration of trunk groups between switches. Many configurations are possible from fully interconnected networks to sparsely connected rings or stars. Trunk costs vary widely depending on the number of trunks installed, the distance covered, and the choice of wire or fibre.  From the solutions to these problems comes the physical design of the network. Some degree of redundancy is typically included in the design so as to maintain some degree of service in the event of equipment failures.  Clearly these design problems are inter-related. The number and placement of switches affects the design of the class hierarchy, and the configuration and size of trunk groups. Ideally these problems would be solved as a single large optimisation, but the combined problem is far too complex to solve analytically for anything but a very small network.  8  After the design of the physical network comes the problem of designing the operational rules for routing traffic. Routing rules can take a wide variety of forms that will be explored in more detail later. Call routing distributes traffic over multiple routes with the effect of decreasing demand on some trunk groups and increasing it on others. Therefore, an idealised network design would optimise routing and trunk groups sizing together.  Since the objective of the Telus project is to reduce investments in the circuit-switched network, an ideal design is one that can meet future demand until the conversion to A T M for the minimum dollar investment at a P.01 QoS. There is little to be gained in this project by looking at broad design issues, such as the number and placement of switches, because the cost of implementing such broad changes could not be recovered over the project's time-frame. Therefore switch locations and overall network configuration will be taken as given. Instead the idealised design will need to focus on the size of trunk groups, the choice of routing rules, and possibly the size of switches.  The project team has discussed the possibility of developing an idealised network design, but only at a high-level conceptual stage. Research would be needed on how to construct an idealised design, and how to use it to find hidden capacity in the existing network. Network Augmentation Decisions Most of the dollars invested each year in the lower mainland go to increasing the size of the trunk groups. Once each year infrastructure planners use demand forecasts to anticipate trunk group requirements. Then they compare the anticipated requirements against the existing trunk group capacity to determine where new card racks will be needed. Card racks are then installed in anticipation of the coming year's growth.  Throughout the year, engineers monitor network traffic and install trunk cards as needed. Two cards are required for each trunk group, one at either switch. Therefore with FHR four cards are needed to expand an alternate route, two cards for each trunk group to and from a tandem. The installed cost of a trunk is roughly the $10,000 plus a pro-rated portion of the $100,000 cost of the card rack. Therefore the direct routes are usually  9  augmented rather than the alternate routes. N o t e , t h o u g h , that e v e r y trunk group to a t a n d e m is part o f m u l t i p l e routes so w h e n a group is e x p a n d e d its added c a p a c i t y is a v a i l a b l e for a l l routes sharing the group.  B a s i n g investment d e c i s i o n s o n average trunk c a r d costs c a n be m i s l e a d i n g i f one o f the c a r d racks is out o f space. In that case it m i g h t be m o r e cost efficient to a d d cards to an alternate route w i t h rack space already a v a i l a b l e . B y t r a c k i n g the amount o f u n u s e d space o n each r a c k , investment d e c i s i o n s c o u l d be b a s e d o n m a r g i n a l costs rather than average costs.  D e t e r m i n i n g the annual requirements for c a r d r a c k s is m o r e d i f f i c u l t at T e l u s today than it w a s i n past because changes i n the t e l e c o m market i n recent years have m a d e accurate d e m a n d forecasts m u c h harder to obtain. In past, d e m o g r a p h i c g r o w t h served as a f a i r l y g o o d predictor o f d e m a n d , but i n t o d a y ' s market c o m p e t i t i o n , n e w technologies and n e w services a l l i m p a c t o n d e m a n d . Internet g r o w t h , c e l l p h o n e s , a d v a n c e d c a l l i n g features, a n d flat-rate l o n g distance are o n l y s o m e o f the factors that c l o u d the forecasting o u t l o o k . C o m p e t i t i v e carriers c a n n o w b u y b u l k services f r o m T e l u s , creating d e m a n d w h e r e none p r e v i o u s l y existed, or they c a n reduce d e m a n d b y d r a w i n g customers a w a y to independent n e t w o r k s . In response T e l u s has f o r m e d a t e a m c h a r g e d w i t h d e v e l o p i n g a m o r e reliable approach to forecasting, better suited to t o d a y ' s m a r k e t p l a c e .  Routing Rules A l l alternate routes i n the l o w e r m a i n l a n d pass t h r o u g h t w o t a n d e m s w i t c h e s : M u t u a l and N e w W e s t m i n s t e r , i n a F H R scheme patterned after the l o n g distance n e t w o r k . H o w e v e r , F H R is o n l y one o f m a n y f o r m s o f routing. F o r e x a m p l e , any s w i t c h i n the l o w e r m a i n l a n d c o u l d serve as a tandem. T h e r e f o r e , any s w i t c h c o u l d serve as an i n t e r m e d i a r y for the creation o f alternate routes.  F H R is a subclass o f the m o r e general class o f  Sequential Alternate Routing ( S A R ) .  S A R schemes consist o f an ordered set o f routes for each o r i g i n / d e s t i n a t i o n ( O D ) s w i t c h pair. C a l l s are offered i n turn to each route i n the set u n t i l either an a v a i l a b l e route is  10  found, or the set is exhausted and the call is blocked. There are thirty-three switches in the lower mainland. F H R uses just two of these for its alternate routes, but S A R could use any of the thirty-three switches, plus combinations of switches. Therefore with S A R vastly more alternate routes are possible between every OD pair.  S A R functions as a simple greedy algorithm, with the system searching through an ordered route set and stopping at either the first route with available capacity, or when the set is exhausted. A route may include many trunk groups, and a trunk group may belong to many routes. Overflow traffic increases demand on every trunk group in a route. For example, given switches (A,B,C), if A—»B is a primary route and A—>C—>B is an alternate, then traffic overflowing onto A—»C—>B reduces demand on A—»B at the cost of increased demand, and potential congestion, on A—»C and C—>B. In practice, therefore, the choice of alternate routes is generally restricted to those that pass through one, or at most two, tandem switches.  This spill-over congestion can be managed by spreading alternate routes throughout the network. In any case, since F H R is a subset of SAR, it is always possible to design a S A R scheme that performs at least as well, if not better, than a FHR scheme.  Sometimes routing schemes reserve a portion of some or all trunk groups for use by traffic on the primary route only. For example, i f 5% of a trunk group is reserved, then any time the group's utilisation exceeds 95% it is blocked to overflow traffic, and only primary route traffic is accepted. Schemes with trunk reservation can spread traffic more evenly through a network, generating less spill-over congestion, than schemes without.  Demand varies by season, day of week, and time of day. Apart from holidays and special events, the overall demand peak in the lower mainland occurs midweek in the fall during morning business hours. A second peak occurs mid-evenings comprised mainly of personal calls and consumer Internet usage. These peaks occur in different geographic areas, with the morning peak centred on switches in the business district and the evening peak in residential districts. With this complementary pattern of demand one routing  11  strategy i s to a l l o w business traffic to o v e r f l o w t h r o u g h residential area s w i t c h e s and v i c e - v e r s a . T h i s strategy tends to s m o o t h the d e m a n d throughout the d a y , e m p l o y i n g the otherwise u n u s e d c a p a c i t y that exists i n areas o f the n e t w o r k d u r i n g their off-peak periods.  A m o n g the v a r i o u s r o u t i n g schemes d e s c r i b e d i n the literature r e v i e w , are f o r m s o f statedependent routing that respond d y n a m i c a l l y to the current traffic l o a d . T h e s e schemes route c a l l s a r o u n d c o n g e s t i o n . T h i s requires that the s y s t e m be capable o f m o n i t o r i n g traffic v o l u m e s and selecting appropriate routes. State-dependent r o u t i n g i s u s e d i n the C a n a d i a n inter-carrier l o n g distance network. U n l i k e the case w i t h traditional c i r c u i t s w i t c h e d n e t w o r k s , c a l l s i n the inter-carrier n e t w o r k c a n be d y n a m i c a l l y re-routed w h i l e they are i n progress. H o w e v e r , due to the age and m i x o f switches i n the T e l u s n e t w o r k , state-dependent r o u t i n g i s not an o p t i o n .  O n e f o r m o f r o u t i n g i s c a l l e d load share o r random routing. I n this scheme e a c h m e m b e r o f a route set is assigned a n u m e r i c a l w e i g h t c a l l e d a n attraction coefficient. C a l l s are distributed to m e m b e r s o f the set i n p r o p o r t i o n to their attraction c o e f f i c i e n t s . F o r e x a m p l e , i f a set o f routes Ri, R2, and R 3 h a v e w e i g h t s 7 5 , 15 and 10 r e s p e c t i v e l y , then 7 5 % o f c a l l s are r a n d o m l y directed to Ri, 1 5 % to R2, and 1 0 % to R 3 . D e p e n d i n g o n h o w the rules are i m p l e m e n t e d , i f a route i s b l o c k e d either the c a l l is b l o c k e d o r it i s retried o n another route. L o a d share r o u t i n g has the potential to distribute c a l l s m o r e e v e n l y across a n e t w o r k than S A R , thus l e a d i n g to f e w e r b l o c k e d edges and less s p i l l o v e r c o n g e s t i o n . H o w e v e r , this m e t h o d o f r o u t i n g i s not an o p t i o n for T e l u s .  O n e f o r m o f d y n a m i c r o u t i n g that i s a v a i l a b l e to T e l u s i s time-dependent routing, i n w h i c h the r o u t i n g rules change over time. T h e changes c a n i n c l u d e any aspects o f the rules, s u c h as the c h o i c e o f routes i n the route set, o r the c h o i c e o f attraction c o e f f i c i e n t s for l o a d share routing. S o m e t i m e s time-dependent r o u t i n g schemes are adaptive, w i t h rules that change a u t o m a t i c a l l y and p e r i o d i c a l l y i n response to past s y s t e m p e r f o r m a n c e . T h e s e schemes are s i m i l a r to state-dependent r o u t i n g except that they r e s p o n d to past c o n d i t i o n s rather than current c o n d i t i o n s . T e l u s c o u l d use a l i m i t e d f o r m o f t i m e -  12  dependent routing that consists of using different route sets for different times of the day. For example, they could have one set for the morning peak period and another for the evening, with each set tuned to the traffic patterns typical of its time of the day.  Chapter 2 - Literature Review A Performance Comparison of Competitive On-Line Routing and StateDependent Routing (Aiello, etal, 1997) Among the many possible variants of dynamic routing are Competitive On-Line (COL) routing and State-Dependent Routing (SDR). The authors of this article use simulation to compare the performance of C O L to that of SDR for a mix of different networks under different traffic loads.  Under COL, the call placement process begins with first computing the cost of placing the call on each potential route. Costs are computed for every arc of every route as an exponential function of each arc's utilisation, which is equal to its current load divided by its capacity. If the minimum cost over all routes is above some pre-set threshhold then the call is rejected. Otherwise it is accepted and placed on the minimum cost route.  Under SDR, the cost of accepting a call on a route is equal to the expected number of future calls that would be blocked as a result. The expected number of blocked calls is calculated using the Erlang-B blocking formula, also known as Erlang's loss formula (see Figure 7 in the Results section). This formula applies queuing theory to network traffic to determine the probability of a call being blocked given the arc capacities and the traffic load. If, for every potential route, accepting the call results in a probability of more than one future call being be blocked, the call is rejected. Otherwise it is accepted and placed on the route with the fewest expected blocked calls.  One of the parameters for the SDR cost function is the offered load, which is a product of the call arrival rates and holding times for an arc. The authors compare two versions of SDR that vary depending on how the offered load is calculated. If the arrival rates and 13  h o l d i n g t i m e s are k n o w n i n advance, the authors use a L i n e a r P r o g r a m ( L P ) to f i n d the o p t i m a l v a l u e s for e a c h arc. I f the rates and times are u n k n o w n , the authors start the a l g o r i t h m w i t h an offered l o a d equal to c a p a c i t y and adjust the v a l u e s p e r i o d i c a l l y d u r i n g operations i n response to the o b s e r v e d traffic. T h i s v a r i a t i o n they c a l l S D R - A D A P T .  T o c o m p a r e the p e r f o r m a n c e o f C O L , S D R and S D R - A D A P T the authors r a n s i m u l a t i o n s o n n e t w o r k s r a n g i n g i n size f r o m f i v e nodes to 66. T h e s e i n c l u d e d s m a l l n e t w o r k s w i t h u n i f o r m arc capacities as w e l l as m o r e c o m p l e x cases b a s e d o n r e a l - w o r l d c o m m e r c i a l n e t w o r k s . S o m e w e r e f u l l y c o n n e c t e d and others sparsely c o n n e c t e d . C a l l s w e r e m o d e l l e d u s i n g P o i s s o n a r r i v a l rates and e x p o n e n t i a l service t i m e s . A s a p e r f o r m a n c e measure the authors used the total n u m b e r o f rejected c a l l s . In m o s t cases S D R g a v e l o w e r r e j e c t i o n rates than the other algorithms - sometimes substantially l o w e r . C O L s o m e t i m e s gave rates c l o s e to S D R i f the right base w a s u s e d for the e x p o n e n t i a l f u n c t i o n . H o w e v e r , the authors c o u l d not f i n d a general m e t h o d for c h o o s i n g a g o o d e x p o n e n t i a l base.  T h i s study l o o k s o n l y at f o r m s o f d y n a m i c r o u t i n g that are not a v a i l a b l e to T e l u s . H o w e v e r , the study does point to the fact that changes i n r o u t i n g schemes c a n result i n large differences i n n e t w o r k performance.  Comparison of Routing Methods for DCS-Switched Networks ( D o v e r s p i k e and J h a , 1993) A D i g i t a l C r o s s - C o n n e c t S y s t e m ( D C S ) is a type o f c i r c u i t - s w i t c h e d n e t w o r k w i t h s w i t c h e d d i g i t a l lines. D C S networks are data n e t w o r k s that serve as a cost s a v i n g alternative to d i g i t a l leased lines. In this study the authors use s i m u l a t i o n to c o m p a r e the p e r f o r m a n c e o f a D C S n e t w o r k w i t h s i x different routing schemes. F i v e o f the schemes are variants o f S D R , d e s c r i b e d above i n the p a p e r b y A i e l l o et a l . T h e other is F H R - the scheme currently used b y T e l u s .  T h e f i v e S D R variants are based o n c o m b i n a t i o n s o f t w o options. T h e first o p t i o n is b e t w e e n u s i n g the same cost f u n c t i o n as d e s c r i b e d a b o v e for A i e l l o et a l , o r a m o d i f i e d  14  cost function that assigns higher costs to routes with mores edges. The second is between limiting the potential number of edges in a route versus allowing unlimited length routes. Combinations of these two options yield four SDR variants. The fifth variant uses the modified cost function and limited length routes, and also automatically and periodically re-routes calls in progress.  Traffic in a DCS network is different than traffic in a telephone network. In a DCS network, call attempts are much less frequent than calls in a telephone network. Arrival rates are not Poisson in a DCS network, and service times are very long, often weeks or months in length. Although telephone networks may have some very long Internet calls, most calls are only minutes long.  In this study the authors used two different performance measures to compare the six routing methods. One measure looked at the number of blocked calls; the same measure used by Aiello et al. A second measure used a network design algorithm to find the smallest network that is capable of supporting a given traffic load at a same level of service for each of the routing methods. B y either measure, F H R performed the poorest of the routing methods, and forward-looking SDR with automatic and periodic re-routing performed the best.  There are substantial differences between this study and the Telus project. For one, DCS traffic patterns are quite different from those in the Telus network, and the dynamic routing used in this study is not an option for Telus. Also, Telus requires blockage rates far below the 11.9% to 20.2% range measured in this study.  When measured by blockage, the best performing method had 40% fewer blocked calls than FHR, but when measured by network size, it required a network only 14% smaller than FHR. This may have implications for the Telus project, because Telus are asking for help to minimise network investments, not to reduce blockage. This study suggests that reducing blockage may not necessarily translate into comparable savings in network investments.  15  Blocking Probabilities in Large Circuit-Switched Networks (Kelly, 1986) One very prominent researcher in the area of routing in circuit-switched networks is F.P. Kelly. This paper by Kelly establishes a foundation for some of his later work. Here Kelly examines the use of Erlang's loss formula to calculate blocking probabilities in complex networks. In this model, calls have Poisson arrival rates and random service times.  First Kelly expresses the problem of finding blocking probabilities as a series of nonlinear equations. These are solvable for simple networks, but become impractical for large networks. He then demonstrates that for large networks, if both the number of circuits and the traffic volumes are increased together, individual links block traffic almost as if they were independent of all other links. Therefore, the probability of blockage on a route can be derived directly from the probabilities of blockage on the individual links. Probabilities for the links can be found from an optimisation in which the number of variables is equal to the number of links in the route. Kelly uses Erlang's loss formula to approximate the blocking probability, and then develops what he calls the Erlang fixed point to show that there exists a unique solution giving the expected losses per link. His approach holds in general for static routing, and for some limited forms of dynamic routing.  Kelly's approach requires high traffic volumes. In practice this is not a serious limitation because it is precisely when traffic volumes are high that blockage is a concern. He gives examples to show how his work can be applied to network operations, and discusses its potential for evaluating blockage under different routing schemes. Kelly's work offers an analytical method that the Telus team could use as an alternative to simulation to compare the performance of different routing schemes. Routing in Circuit-Switched Networks: Optimization, Shadow Prices and Decentralization (Kelly, 1988)  16  In this article Kelly applies the Erlang loss formula to a network with an adaptive routing policy. For his objective function, Kelly maximises the expected revenue from processing calls, under the assumption that each call has a known revenue value which depends on the route that the call takes. His approach can also be applied to revenue neutral networks, such as the routing of toll-free calls in the Telus project. In this case all calls are treated as having an equal unitary revenue value so that maximising revenue is equivalent to maximising the number of calls accepted or, conversely, minimising the number of calls blocked.  Kelly formulates the problem as a decentralised hill-climbing search with decision making intelligence distributed throughout the network's switches. Each switch routes calls based on its own knowledge of the network's resources and of the local traffic load. Switches periodically exchange traffic load data with their nearest neighbours so that each switch has a view of traffic beyond its immediate links.  This form of adaptive state-dependent routing is similar to the SDR-AD APT method in the study by Doverspike and Jha. In both studies the routing adapts to the current state of the network by updating candidate route sets between OD pairs. Doverspike and Jha do not say whether SDR-AD APT uses distributed or centralised knowledge of the network state.  Kelly's paper is based in part on his prior work of finding the Erlang fixed point for a network (Kelly, 1986). From the Erlang fixed point, Kelly here derives a formula that gives the expected rate of return for a network. The derivative of that formula yields shadow prices that can guide the network growth process by identifying the links with the greatest revenue potential. In the revenue neutral model, the shadow prices identify the links with the greatest potential to decrease blockage.  Although Telus can not directly implement the routing method described by Kelly, his work might be of use to the project team with the problem of designing an efficient S A R  17  scheme for Telus. The team could, for example, perform a simulation of the Telus network with Kelly's adaptive routing scheme, and observe the route sets that it selects. Bounds on the Performance of Dynamic Routing Schemes for Highly Connected Networks (Kelly, 1994) The choice of routing scheme for a network affects both its traffic carrying capacity and, for toll calls, its revenue generating capacity. A natural question then is, what are the limits on network performance that can be achieved with a well designed routing scheme? This is the question that Kelly addresses in this paper. He describes a procedure for finding bounds on the performance of dynamic routing schemes, especially in large, highly connected networks.  Kelly tackles the problem using a "bound developed from a network flow synthesis of carefully chosen Markov decision processes, one for each resource of the network". The bound emerges as solutions to a dual pair of convex programming problems in which the variables in the primal problem represent the mean flow of traffic over the various routes. Kelly contrasts the relative ease of obtaining cost and surplus values from the primal and dual problems with the relative difficulty of obtaining the equivalent values from his prior approach of finding the derivative of the Erlang fixed point solution (see Kelly, 1988).  Kelly then demonstrates that, for highly connected networks, simple trunk reservation schemes can approach the performance of dynamic routing schemes. With trunk reservation, calls of one type are given preferential access to a trunk group over calls of other types. Kelly discusses trunk reservation in the context of revenue generating calls, with higher revenue calls receiving preferential access to a trunk. In the lower mainland all calls have equal revenue value but, as was previously discussed, trunk reservation can also be used in toll-free networks by giving preference to calls on primary routes over those on alternate routes. This may warrant further study for the Telus project.  18  Efficient Routing of Telephone Calls (Denardo and Park, 1990) Denardo and Park present four related routing schemes. They start with a scheme in which the routes are ordered within route sets by the expected number of blocked future calls for each call assigned to a route. The probability of a blocked call is a function of the capacity of a link, and the probability of a given traffic load occurring on the link. The function is summed over all possible traffic loads for each link in a route to give the expected number of blocked calls on the route. In this scheme every call attempt is offered in turn to the members of the route set starting with the highest ranked route.  Next the authors present a refinement of the first scheme, in which calls are offered to routes only if the expected number of blocked future calls is less than one.  In the first two schemes, candidate routes are ranked prior to any incoming call attempts. In the third and fourth schemes, routes are not ranked in advance, but are rather evaluated for each call attempt based on the current state of the network. This evaluation requires knowledge of the current traffic load on each link for every member of the route set. The fourth schemes differs from the first three in the way it models the arrival rate of calls on the links. The first three schemes all assume a constant rate that reflects call attempts. In the fourth scheme, the rate reflects the number of calls accepted onto the network, and therefore the rate slows as the number of calls in progress approaches the number of available trunks. These last two schemes are similar to SDR described in the simulation study reported by Aiello, et al.  When schemes of this sort are implemented commercially they typically employ trunk reservation. As an example of a commercial implementation, the authors refer to A T & T ' s Dynamic Non-Hierarchical Routing scheme, which ranks the routes by a heuristic and uses trunk reservation. The authors devote a portion of their paper to a discussion of trunk reservation with these schemes.  19  T h e t h i r d and f o u r t h schemes the authors present are f o r m s o f d y n a m i c r o u t i n g . N e i t h e r o f these is a n o p t i o n for T e l u s . H o w e v e r , their first t w o schemes are b o t h f o r m s o f S A R a n d c o u l d b e i m p l e m e n t e d at T e l u s . T h e s e t w o schemes b o t h operate b y o f f e r i n g c a l l s s e q u e n t i a l l y to r a n k e d m e m b e r s o f a f i x e d route set, but differ i n h o w the m e m b e r s o f the route sets are ordered.  A Global Optimization Routing Model and Applications in Telecommunication Networks (Sanso and S o u m i s , 1989) Sanso a n d S o u m i s present a centralised n e t w o r k r o u t i n g m o d e l w h i c h y i e l d s the o p t i m a l r o u t i n g for a n e t w o r k m e a s u r e d i n terms o f the fewest lost calls. Sanso a n d S o u m i s start w i t h an o b j e c t i v e f u n c t i o n that m i n i m i s e s a lost c a l l penalty f u n c t i o n , i n w h i c h the n u m b e r o f lost c a l l s is f o u n d f r o m the p r o b a b i l i t y o f b l o c k i n g g i v e n b y E r l a n g ' s loss f o r m u l a s u m m e d o v e r a l l arcs i n the n e t w o r k . T e l e p h o n e n e t w o r k s are often m o d e l l e d as m u l t i - c o m m o d i t y f l o w s , w i t h deterministic d e m a n d and e x p l i c i t c a p a c i t y constraints. T h e a p p r o a c h d e v e l o p e d b y Sanso and S o u m i s eliminates the e x p l i c i t c a p a c i t y constraints, and m o r e accurately reflects the stochastic nature o f d e m a n d than a m u l t i - c o m m o d i t y flow model.  T h e authors describe t w o p o s s i b l e m o d i f i c a t i o n s to their objective f u n c t i o n : one that penalises the use o f l o n g paths, and another that balances lost c a l l s a m o n g the nodes. F o r the latter m o d i f i c a t i o n the authors a d d a t e r m to the objective f u n c t i o n that is e q u a l to the square o f the lost c a l l s per arc. W i t h this quadratic term i n the objective e q u a t i o n they s o l v e the r e s u l t i n g s y s t e m o f equations u s i n g a F r a n k - W o l f e a l g o r i t h m .  T o reduce c o m p u t a t i o n a l requirements, the authors approximate the E r l a n g loss f o r m u l a w i t h a set o f three functions - one e a c h for l o w , m e d i u m and h i g h traffic. F o r traffic l e v e l s f r o m j u s t b e l o w to j u s t above the c a p a c i t y o f an arc, they a p p r o x i m a t e b l o c k a g e b y a quadratic f u n c t i o n . A t levels b e l o w that, they approximate b l o c k a g e as z e r o , a n d above it they a p p r o x i m a t e it as the difference b e t w e e n the d e m a n d and the c a p a c i t y .  20  This model may offer an alternative to the use of a multi-commodity LP for the Telus project. In addition, the model can also be applied to problems of network dimensioning and performance, which may be of interest in later phases of the Telus project. Literature Summary The simulation results reported by Aiello et al. show that changes of routing schemes can produce a large change in the rate of blocked calls. A network can carry more traffic at the same level of service with an efficient scheme than it can with a less inefficient scheme. However, as reported by Doverspike and Jha, reducing the rate of blocked calls may not translate directly into comparable savings in network investments, and reducing investments is the goal of the Telus project.  Some of the papers suggest various approaches to the design of routing schemes. One approach would be to simulate the Telus network using the adaptive routing scheme described by Kelly (1988), and then to create a S A R scheme from the route sets it produces. Sanso and Soumis approach the design problem using numerical methods that eliminate the explicit capacity constraints inherent in the multi-commodity LP that was developed for the Telus project. Denardo and Park present approaches for ordering the routes within routes sets. Their work could complement that of Sanso and Soumis, where the work of the latter is used to generate route sets, and that of the former to order them.  Kelly (1994) discusses the limits on network performance that are attainable through improved routing, and in the same paper demonstrates that simple trunk reservation schemes can approach the performance of dynamic schemes in highly connected networks. This finding should be of interest for the Telus project because the thirty-three lower mainland switches are almost fully connected,. Kelly (1986) also presents a numerical method, based on Erlang's loss formula, for evaluating routing schemes. His method may be an alternative, though not necessarily an improvement, to comparing schemes through simulation.  21  Chapter 3 - Methodology In this section I primarily discuss the project methodology from the perspective of the Telus project team. I also give an overview of work specific to this thesis. Details of the thesis work are given in the Results section that immediately follow this one.  Initially the project team will focus on improving routing in the lower mainland, which will allow the existing network infrastructure to carry more traffic than it does now. Telus currently routes calls using FHR, but as the International Telephone and Telegraph Union notes, "Routing schemes that allow more flexible routing choices generally provide greater resilience ... than traditional fixed hierarchical routing methods" (Designing Networks to Control Grade of Service, <http://www.itu.org>).  Due to a heterogeneous mix of equipment, the routing options available to Telus are limited. Therefore the team is looking at SAR, a scheme that does allow for more flexible routing than FHR. FHR is, in fact, a subclass of SAR, therefore it is always possible to design a S AR scheme that is at least as efficient, if not more efficient, than FHR. At this point in the project, the team's focus will be on static SAR. Later the focus may shift to include time-dependent, adaptive SAR. Network Simulator Among the team's tools is a network simulator for running comparison tests of routing schemes. The inputs to the simulator include: a network model, routing rules, and demand, comprised of call frequencies and mean service times by OD pair. In each simulation run, the program generates calls as per the demand, then routes them through the network as per the routing rules. At the end of the run the simulator reports overflow and blockage statistics by route, by OD pair, and overall. These statistics will be analysed by the team to compare the performance of different routing schemes.  The simulator was written in C++ by students Earl Gordon and Jeff Hawkins. It uses an internal clock that advances in fixed time increments. With each increment the program examines every call in progress. It decrements the remaining service time for every call  22  and removes expired calls from the network. It then places new calls. Calls therefore enter and exit the network only at fixed increments, with expired calls being removed before new calls are added. This introduces some artificiality into the simulation. Shortening the increment would make for a more realistic simulation but at the cost of increased processing and longer run times.  With each time increment, the program generates new calls in the order in which OD pairs were read from the demand file. If the simulator were to place each call immediately as it was created, the effect would be to favour calls for OD pairs near the top of the file over those near the bottom. To avoid this, the simulator first saves the calls in an array, then randomises the array before placing the calls. Calls are, therefore, presented to the network in no particular order so there is no preference for one OD pair over another. Verifying the Simulator Before it is used to test routing schemes the simulator must be verified. Verification focuses on the "face-validity" of the software design and implementation, ensuring that the program works as it was intended to. With commercial software, verification is done by the developers, and rarely concerns the people using it unless it has bugs. Because the Telus project simulator was not commercially developed, it must be verified by the project team before it is used.  Most of the work presented in the Results section relates to verifying the software. The specific verification tests included manually reproducing a simulation run to ensure that results were reproducible; ensuring that call creation and call service times conform to the input file distributions; and verifying that the placement of calls does not favour one OD pair over another. These tests looked largely at the functionality of the software. One additional verification test was of more interest from a theoretical perspective. That test compared the blockage produced by the simulator on a single arc network against the expected blockage as predicted by Erlang's loss formula.  23  Validating the Simulation Model V a l i d a t i n g the s i m u l a t i o n m o d e l is a separate a n d distinct process f r o m that o f v e r i f y i n g the s o f t w a r e . V e r i f i c a t i o n focuses o n the t o o l u s e d to p e r f o r m the s i m u l a t i o n s . V a l i d a t i o n focuses o n h o w accurately the s i m u l a t i o n m o d e l represents the real w o r l d , and o n the c r e d i b i l i t y o f the results it generates.  S i m u l a t i o n is a t o o l w i t h w h i c h to study a s y s t e m ' s b e h a v i o u r . F o r e x i s t i n g systems, it c a n be u s e d to see h o w changes affect the s y s t e m ' s b e h a v i o u r . F o r p l a n n e d systems, it c a n be u s e d to test the b e h a v i o u r o f alternative s y s t e m designs. In either case, e v e r y s i m u l a t i o n m o d e l i n c l u d e s some s i m p l i f y i n g assumptions and a p p r o x i m a t i o n s . T h e r e f o r e , the b e h a v i o u r o f the m o d e l m a y not m a t c h e x a c t l y w i t h that o f the s y s t e m , but it s h o u l d be c l o s e e n o u g h that the m o d e l is a reliable p r o x y to the system. V e r i f y i n g a m o d e l i s the process o f c o n f i r m i n g that its b e h a v i o u r i s c l o s e e n o u g h to that o f the r e a l - w o r l d s y s t e m to r e l i a b l y serve as its p r o x y .  T h e team w i l l be w o r k i n g w i t h a m o d e l o f the e x i s t i n g T e l u s n e t w o r k and p e a k p e r i o d d e m a n d . W h e n this m o d e l is r u n w i t h the current F H R scheme it s h o u l d p r o d u c e results consistent w i t h those o b s e r v e d b y T e l u s . I f the s i m u l a t i o n results were f o u n d to be inconsistent w i t h the actual results, then a n y tests o f alternate r o u t i n g schemes w o u l d b e suspect. That is to say, i f s i m u l a t i o n c a n not accurately m o d e l the p e r f o r m a n c e o f the e x i s t i n g r o u t i n g s c h e m e , then what r e a s o n i s there to b e l i e v e that it c a n predict the p e r f o r m a n c e o f any alternate scheme?  V a l i d a t i n g the m o d e l w i l l require f o r m i n g c o n f i d e n c e intervals for b l o c k a g e a n d o v e r f l o w b y O D p a i r f r o m a n u m b e r o f s i m u l a t i o n runs. T h e n the c o n f i d e n c e intervals w i l l be c o m p a r e d w i t h the actual b l o c k a g e and o v e r f l o w for the same O D pairs to see i f the results are consistent.  Running Simulations E v e r y s i m u l a t i o n r u n starts c o l d w i t h n o c a l l s i n progress and little or n o b l o c k a g e . A s it w a r m s u p , the b l o c k a g e increases u n t i l it l e v e l s o f f and starts to fluctuate a r o u n d a m e a n .  24  Statistics collected during the warm up period understate blockage, and so should not be included when analysing the run unless the total run time is sufficiently long that their impact is negligible.  A generally preferred approach to the cold start is to simply discard the statistics collected during the warm up. This allows for shorter run times. First a few simulations are run with no warm up period, and their blockage is graphed. A visual inspection of the graphs reveals the approximate point at which the blockage levels off, signalling that the model has warmed up. This approach is demonstrated in appendixes 3 and 4.  When using simulation to compare routing schemes, any difference in the results between runs should reflect differences in the schemes, not differences in the model. Therefore each scheme is tested using exactly the same network model and demand. This eliminates variations due to changes in the model, but not those due to the stochastic nature of demand. Even the same routing scheme will give different results from one run to the next because demand is stochastic.  These stochastic changes can also be eliminated by testing each scheme with exactly the same set of calls. This particular variance reduction technique is demonstrated in the Results section, by using a common random number seed to re-create the same set of calls for a series of test runs. In this way, any differences in the results between runs reflect differences in the performance of the routing schemes.  Confidence intervals are used to compare the differences between schemes, therefore multiple observations are needed of each scheme. If the warm up period is relatively short, then multiple observations can be obtained most easily by multiple runs. However, if the warm up period is overly long, then multiple runs may be impractical. In that case the team may choose to perform one long run, and to divide the results into multiple observations. For this they will need to construct correlograms of the blockage over a run to ensure that the observations are not correlated. Varying the lag in the correlogram reveals the minimum sized interval needed to eliminate correlation.  25  Comparing Routing Schemes via Simulation Simulations of different routing schemes produce differences in both overflow and blockage. O f these, blockage is the item of most interest for measuring performance. Overflow can be used for validating the model, but it is not necessarily a good indicator of performance. Blockage is the measure that determines whether or not a network is operating within its QoS standard. Therefore a scheme with high overflow but low blockage is better than one with low overflow and high blockage. Blockage can be compared in many ways. One common approach is to look at blockage for the network overall (see Aiello et al., and Doverspike and Jha). This gives a rough measure of performance, but obscures the details of how blockage is distributed. For example, it may be better to have a scheme with higher overall blockage, provided the blockage is evenly distributed, than a scheme with lower blockage if the blockage is concentrated on just a few OD pairs.  Another approach is to compare blockage on the same OD pair for the different routing schemes. For example, blockage on 3—>7 might be compared across all schemes. The problem with this approach is that i f for one scheme 3—»7 has high blockage and 8—»4 has low blockage, while for another scheme the reverse is true, which scheme is better? Also, since traffic load varies across the network, the question naturally arises of whether it is better to have lower blockage where traffic is heavy at the expense of higher blockage where it is light.  One comparison measure, which is both easy to apply and free from the problems described above, measures the maximum blockage occurring across all OD pairs. This can occur on different OD pairs in each run, such as, on 3—»7 in one run and 8—»4 in another. This approach corresponds nicely with the Telus QoS standard which sets an upper limit on blockage for every OD pair. If the maximum blockage across all OD pairs is within the standard, then it follows that all OD pairs are within the standard. This method was used for comparison tests described in the Results section.  26  Arguably the best routing scheme is the one that can meet the QoS standard with the heaviest traffic load. To find this, one could run multiple simulations of each scheme while scaling up the traffic to find the level at which blockage exceeds the QoS standard. This is somewhat akin to doing a crude linear forecast of demand growth. A more refined approach might be to adjust the traffic using forecasts provided by Telus. Simple Improvement Heuristic Besides testing routing schemes,*the simulator also includes an option to apply a simple greedy heuristic that attempts to improve a routing scheme. This heuristic finds the OD pairs with the highest levels of blockage. Then for each such pair it searches for the single hop route with the greatest unused capacity and adds it to the route set. These additions are always made to the end of the route set. After the sets are updated, the simulation runs again to get comparison results of the original and updated route sets. Input parameters control the number of times that the simulation runs, and the number of OD pairs modified in each run. Multi-Commodity Network Flow Linear Program The project team has developed a tool for use in designing new routing schemes. The tool is a multi-commodity network flow Linear Program (LP) in which the commodities comprise calls originating at the individual switches. The L P was formulated by Dr. Maurice Queyranne, and written in X P R E S S - M P  ( t m )  by graduate students Isabelle Smith  and Steven Kabanuk. In the LP, demand is deterministic, modelled as the total traffic flow in CCS for each OD pair over a fixed period of time. Nodes represent the lower mainland switches and arcs represent trunk groups. Each arc's capacity is equal to the maximum CCS that the trunk group is able to carry.  The L P ' s objective function minimises the fraction of the network's capacity needed to satisfy demand. This fraction applies to every arc so, for example, i f the L P solves to a value of 0.83 then every arc in the network is utilised to no more than 83% of its capacity. This, in essence, gives a rough measure of the fraction of the network's resources needed to satisfy demand. If the LP yields a fraction greater than one it indicates that the network has insufficient resources for the demand. It is worth noting, 27  however, that demand in the LP model is static whereas actual demand is stochastic, therefore the LP will tend to understate the resources actually needed for the demand.  A solution to the LP gives traffic load by commodity type for every arc, which is equivalent to traffic per trunk group by origin switch. B y analysing a solution, the project team can infer the route set that was selected by the LP for each OD pair. The route sets can then be used as the starting point for the design of a S A R scheme.  A solution to the LP is specific to a particular traffic load, but since the LP runs quickly it can be solved multiple times for different loads. Solutions for the individual loads can then be pooled to obtain a result that, to some degree, reflects the stochastic nature of traffic. Such a pooled solution could, for example, be formed by taking the union of the route sets from the individual solutions.  What can not be inferred from the LP solutions is any ordering of routes within the sets. These must be ordered to be used in a S A R scheme. One of many possible approaches to ordering the routes is to sort them into increasing order by the number of tandem switches in each route. Another is to sort them by decreasing traffic loads as assigned by the LP. For a pooled solution, the routes could be sorted by the number of times that each route was selected in the individual solutions.  28  Origin to  Traffic  Network  Routing  Destination  Pattern  Structure  Rules  Call Data  Analysis  t  Linear  Solution  Network  Results  Program  Analysis  Simulation  Analysis  Figure 3: Routing Rules Revision Process  After the route sets are ordered, they can be tested using the network simulator. In this way the L P and the simulator serve as complementary tools. The LP generates routing schemes, and the simulator tests them and makes incremental improvements (Figure 3).  Chapter 4 - Results Manual Simulation Check This test consisted of running a short simulation of a small test network, and recording the time of creation, OD pair, and duration of every call created. Those calls were then rerun manually through an identical network in Excel, and the results of the manual run were compared with those of the simulation. This test checks for glaring errors in the simulation.  The test network consisted of three nodes and three arcs with four trunks each. A l l routing was direct, except for a single alternate route for calls from 0—>T via 0—»2—*1. Arrival rates between the OD pairs ranged from 0.25 calls per minute to 0.75 calls per minute, with service times drawn from a uniform [0,4] minute distribution. I ran the  29  model for 25 minutes, producing 77 call attempts of which 72 were routed successfully, including one call that overflowed via 0—>2—>l. The inputs to the simulation, and the results of both the simulation and the manual run, are given in Appendix 1.  The simulation and manual runs gave identical results. Both gave the same number of blocked and overflow calls, and the average number of trunks in use in the manual test matched the average trunk usage reported by the simulator. Call Generator Tests  Call Creation by OD Pair One of the simulator's inputs is a file specifying call arrival rates by OD pair. To verify that the simulator does in fact generate calls at the specified rate, I ran simulations with a rate of one call per minute for every OD pair. These were run on a model consisting of a complete four node mesh with 10,000 trunks per arc. Call service times were fixed at one minute, and all calls were routed directly.  The null hypothesis for this test is that generated call distribution equals the specified call distribution. At a rate of one call per minute, the expected number of calls is equal to the run length in minutes. A four node network has twelve OD pairs, so each simulation run produced twelve data points, where a data point is the actual number of calls generated for an OD pair.  This model was run six times, once each for: 50, 100, 200, 400, 800 and 1600 minutes, and the results were evaluated with a chi-squared test. The runs were evaluated separately because with the different run lengths the runs have non-constant variance.  Variables i = index for the 6 test runs {1 to 6} j = index for the 12 OD pairs {1 to 12} Lj = length of a test run in minutes {Li=50, L2=100, ..., 1,6=1600} Cy = calls created in test run i for OD pair j 30  Hypothesis Ho: Cy = Lj for all i j .  Goodness-of-Fit- Test  x] = ^  [  Q  J ~  L  L  ]  fori  2  = l t o 6 , 7 = Ito 12  Li  x\ is approximately chi-squared with 12 degrees of freedom.  The observed values, and calculation of the chi-squared statistics, are shown in Appendix 2. For the six tests the p-values are:  0.681  0.874  0.523  0.432  0.959  0.931  Table 1: p-values of Observed versus Expected Calls  We do not reject the hypothesis that the distribution of generated calls matches the specified distribution. Therefore we can rely on the simulator to generate call traffic at the specified rate.  Call Arrivals over Time New calls should be drawn from a Poisson distribution. To verify this, I ran a simulation for 4999 minutes using an arrival rate of 20 calls per minute. The test generated 100,151 calls over the 20 minutes, for an actual rate of 20.034 calls per minute. I counted the number of calls generated in each minute, and formed a 21 bin histogram of the counts. Next I calculated the expected number of calls for each of the 21 bins from a Poisson distribution with a mean of 20.  31  Calls Generated over 4999 Minutes 1000 (A  800 --  a o> c a>  600  o O  200  3 O  T  400 --  -  0 4  8  12  16  20  Calls in One Minute  24  28  I Observed  32  36  • Expected  Figure 4: Histogram of Calls Generated in 4999 Minutes A visual inspection of the histogram suggests that calls do follow a Poisson distribution. To confirm this, I performed a chi-squared goodness of fit test for the hypothesis that the two distributions are the same, and obtained a p-value of 0.78. Therefore I conclude that calls are created randomly, so the call generator can be used to model Poisson arrivals. Details of the test are in Appendix 2. Service Times Distribution Another of the simulator's inputs is a file specifying the distribution of call service times by OD pair. This file has one row for each pair, and every row has two parts; one part identifies an OD pair, and the other gives the service time probability distribution for the pair. This distribution consist of a series of columns, in which the first column gives the probability that a call will terminate in the first minute, the second column that it will terminate in the second minute, and so on. For example, in table 2 a call on 3—>1 has a probability of 0.10 of terminating in the first minute, probability of 0.25 of terminating in the second minute, etc.  Minute: OD Pair: 3,1  1  2  3  4  5  0.10  0.25  0.30  0.25  0.10  Table 2: Call Service Times Probability Input File In this example the longest possible service time is a five-minute call. 32  The network model for this test was the same as used for tests of the call generator, consisting of a complete four node mesh with 10,000 trunks per arc. Calls were generated at an arrival rate of one call per minute for every OD pair, and all calls were routed directly. This model was run three times with three different service time input files. One file specified fixed length thirty-minute calls with probabilities as shown for OD pair 3->l:  Minute:  1  2  3  ...  28  29  30  OD Pair 3 ^ 1 :  0  0  0  ...  0  0  1.0  Table 3: Service Time Probabilities for Fixed Length Thirty Minute Calls The second file specified fixed length one-minute calls, and the third specified service times to be uniformly distributed over the range from one to ten minutes.  The first two tests were evaluated as a pass or fail; either all calls had the specified fixed length, or they did not. These were run for 100 minutes each, generating 1197 calls and 1191 calls for the one-minute and thirty-minute service time files respectively. A l l calls had the lengths specified in the input.  The uniform distribution was run for 1000 minutes, generating 11,890 calls. A quick check confirmed that all calls fell within the specified one minute to ten minute range. O f interest in this test is whether the number of calls of each length is consistent with the uniform distribution specified in the file. Since every call can have exactly one of ten possible lengths, the results fit a multinomial distribution. The following test was used:  Variables i = call lengths in minutes {1 to 10} C = total count of all calls {equals 11,890} d = count of calls of length i Pi = expected probability of length i {equals 0.1 for all i} i 33  I  Hypothesis HQ: Distribution of call lengths is uniform.  Goodness-of-Fit- Test a _ Z i [Q-Pi*C] Pi*C  2  fori' = 1 to 10  X is approximately Chi-Squared with 9 degrees of freedom because one degree of freedom is lost due to the fixed number of outcomes in a multinomial distribution.  1  7  8  10  Total  Q  1204  1198  1237  1148  1205  1130  1183  1185  1184  1216  11890  Pi*C  1189  1189  1189  1189  1189  1189  1189  1189  1189  1189  11890  X  0.189  0.068 1.938  1.414  0.215  2.928 0.030 0.013  0.021  0.613  7.430  2  p-value 0.59 Table 4: Chi-Squared Test of Call Lengths  We do not reject the null hypothesis, and conclude that the generation of call lengths is consistent with the distribution specified in the input file. Call Placement  Balance  The simulator randomises new calls before it routes through the network in order to avoid favouring calls from one OD pair over those from another. Favouritism would produce relatively lower blockage for the OD pairs processed first. The purpose of this test was to confirm that no such favouritism occurs.  2  W  ^3  Figure 5: Call Placement Verification Model  34  For this model: •  Every arc had a one trunk capacity.  •  The arrival rate was exactly one call per minute on both 0—>1 and 3—*>2.  •  There were no arrivals on any other OD pairs.  •  Call service times were fixed at one minute.  •  The alternate route for 0—»1 was 0—>2—»1.  •  The alternate route for 3—>2 was 3—> 1—>2.  This model was run 33 times at 1000 minutes per run for 33,000 minutes of total run time. This produced of 33,254 call attempts on 0—>1, and 33,515 call attempts on 3—>2. Note that arc l<->2 is shared by both 0—>2—>1 and 3—»1—>2. This is the only resource used by calls from both 0—>1 and 3—>2.  Each run was first warmed up for 500 minutes before collecting statistics. The warm up period was selected by graphing the blockage at 25 minute intervals from three 1000 minute runs with no a warm up. A visual inspection of the graphs showed that in all three cases the model had reached a steady state by the end of 500 minutes. These graphs are presented in Appendix 3.  Confidence intervals were constructed of the mean blockage for each of 0—»1 and 3—>-2, based blockage from the 33 test runs.  95% C.I. On Mean Blockage 0.13589  0.14365  0->1:l 3^2:  0.15055  1  1  I  1  1  0.13780  0.14214  0.14610  Figure 6: 9 5 % C.I. on Mean Blockage These results give no evidence to reject the hypothesis that blockage is evenly distributed between the two OD pairs. The simulation passes the balanced call placement test. Detailed statistics for blockage by OD pair are given in Appendix 3.  35  Observed Versus Expected Blockage A trunk group can be viewed as a queueing system in which the number of servers equals the number of trunks, and the maximum length queue is zero. A call arriving when all servers are busy - i.e. all trunks are occupied - is lost.  If the demand on a trunk group can be characterised as Poisson arrivals at rate A, and exponential service time with mean E[S], then Erlang's loss formula gives the probability, Pj, that i trunks are occupied at any given time.  (XE[S]) 7i! j  Pi =  k  , _ , for i = 0, 1, ... ,k  where k is the number of trunks in the group.  KiEtsry/j!  j=o  Figure 7: Erlang's Loss Formula The probability that a call will be blocked is equal to the probability that all k trunks are occupied, which is Pk-  The hypothesis for this test is that the observed blockage from the simulation will equal Pk - the probability of blockage calculated with Erlang's loss formula. The model for this test comprised a single 1000 trunk arc between two nodes. A single arc was used for simplicity, and the choice of 1000 trunks was arbitrary. Service times were exponential and call arrivals were Poisson. A graph of the service times probability file is given in Appendix 4.  This model was run 36 times starting with an arrival rate of 170 calls per minute, and increasing by one call per minute for each run to a maximum of 205 calls per minute. Every run had a 1000 minute warm up period followed by 1000 minute of run time. A discussion of how the warm up period was determined is given in Appendix 4.  36  At the end of each run the simulator reported the actual arrival rate and mean service time based on the calls generated in the run. These values were used in Erlang's loss formula to find the expected blockage for the same level of demand.  Observed versus Expected Blockage  Figure 8: Observed Versus Expected Blockage  Demand in this graph is expressed as the offered load, which is the product of the arrival rate and the mean service time (see Aiello et al.). So if the arrival rate is 180 calls per minute and the mean service time is five minutes, then the offered load is 900 calls.  Simulation Understates Blockage Note that the curves for the observed and expected blockage follow each other quite closely, with the observed values falling consistently below the expected values. When observed blockage is expressed as a fraction of the expected blockage, the relative difference between the two is seen to be quite large, especially at lower levels of demand.  37  Ratio of Observed Blockage to Expected Blockage TJ d>  o a> a. x  UJ  O c  .2  1.00 .75 .50 .25  o re  .00  h 935  975  1015  1055  1095  1135  Calls per Minute * Average Length Figure 9: Ratio of Observed Blockage to Expected Blockage  Erlang's loss formula gives Pk = 0.01 (equivalent to a 1% QoS) when the offered load is roughly 971 calls. At this level of demand the simulator greatly understates the expected blockage. Since Telus has a 1% QoS standard, this result has implications for the usefulness of the simulator in the Telus project.  Understating blockage may be the result of a timing effect arising from the fact that the simulator removes expired calls before placing new calls. Thus, if in a minute, four calls expire and five new calls are placed, the simulator behaves as i f all four expiring calls terminate before the new calls arrive. In an actual telephone network, on average some of those expiring calls would still be in the system as the new calls arrive.  Fixed Increments Timing Effects Test If this hypothesis is correct, then shorter time increments should produce blockage closer to the expected level because there would be fewer calls in each increment and therefore fewer opportunities for timing effects to occur. Indeed, if the increments could be made infinitesimally small then probability of two events in one increment would be nil, and the timing effects would disappear.  To test this hypothesis I ran a set of tests using half-minute increments instead of the default full minutes. At the time, the simulator did not have a mechanism to set the time increments directly, so instead I reduced the call arrival rate by one-half and doubled the 38  mean call service time. I also doubled the warm up period and run length in keeping with the shorter increments. Therefore, on average only half as many calls arrive or expire in each half-minute increment, but the offered load remains unchanged. After these tests were run a mechanism was added to the simulator to set the time increments. Effects on Blockage of Call Placement/Removal Timing  935  960  985  1010  1035  Calls per Minute * Average Length  —o— Expected — o _ One Minute  Half Minute  Figure 10: Effects on Blockage of Call Placement/Removal Timing Ratio of Observed Blockage to Expected Blockage „  100  Figure 11: Ratio of Observed to Expected Blockage with Different Time Intervals The above graphs focus on the lower end of the demand range. They clearly show, as expected, that blockage is much closer to the expected level with a half-minute time increment.  39  This timing effect could complicate the task of validating the simulation model for the Telus network. We know that the simulator will understate blockage, but we don't know by how much. It may be possible to scale up demand until the simulator produces blockage comparable to what is observed by Telus, but this will leave the validity of the model open to question. Alternately, it may be possible to use a sufficiently small time increment that the simulated blockage reasonably approximate the actual level.  Note that the simulator may still be useful for obtaining comparative rankings of one routing scheme against another, provided that it understates blockage to a similar degree for each scheme. This seems like a reasonable assumption if the schemes are all run with the same network and demand, because the same timing effects will apply in all tests. Comparison of Routing Schemes These tests consisted of comparisons of various routing schemes on a 6-node network (Figure 12). The schemes were FHR, and SAR with and without trunk reservation, with reserve amounts of 4%, 8% , 12% and 16%. For the SAR scheme, the route sets were designed by trial and error from the FHR route sets. Both the FHR and SAR route sets are presented in Appendix 5.  The trunk capacities and call frequencies for these comparisons are shown in Figure 12. A l l calls had a mean service times of 11.029 minutes. Switches 1 and 5 can be thought of as serving a business district; switches 2, 3 and 4 as serving residential areas; and switch 0 as serving mainly as a tandem, but with some demand of its own. Traffic loads were set so that the highest load was in the business district, and the lightest in the residential areas, with an intermediate load on the trunks between the business district and residential areas.  40  Trunk Group Capacities • •  320 trunks: 280 trunks:  •  200 trunks:  0 + 1 , 0 5 and l<->5 l<-»2, l<->3 and l«->4 5-^2, 5-^3 and 5<->4 elsewhere  Call Frequencies • • • • •  5 calls/minute: 8 calls/minute: 9 calls /minute: 11 calls/minute: 12 calls/minute:  •  13 calls/minute:  •  19 calls/minute:  0 ^ 2 , 0 ^ 3 and 0 ^ 4 2 ^ 3 , 2 ^ 4 and 3<->4 1->0 and 5 ^ 0 0 ^ 1 and 0 ^ 5 1^2, 1^3 and 5 ^ 2 , 5 ^ 3 and 5->4 2 -> l , 3 ^ 1 and 4 ^ 1 2 ^ 5 , 3 ^ 5 and 4-»5 1^5  Figure 12: Test Network for Comparison of Routing Schemes  Overall these tests produced blockage that is well above the Telus 1% QoS standard. While this was not representative of the actual Telus network, it was useful for the comparison tests because the routing schemes are compared relative to how effectively they manage blockage.  Each test run was started with a 3000 minute warm up period followed by 3000 minutes of run time, and every routing schemes was run ten times. FHR was tested first and the simulator was allowed to choose the random number seeds. Next SAR and the trunk reservation schemes were tested using the same ten random number seeds.  For the analysis, I extracted the maximum blockage across all OD pairs from every run, and formed 95% confidence intervals on the mean maximum blockage for each scheme. The results are presented in Figure 13. The confidence intervals are very tight, therefore the Y-bars denoting the intervals are very narrow.  41  Mean Maximum Blockage Across all OD Pairs 30 <D  52  re re CQ  — 12%  o >20  o  CQ  6  c u  m 10  Q_  — 16%  — 8%  -4%  _ FHR — SAR  Routing Scheme Figure 13: Mean Maximum Blockage Across all OD Pairs Clearly in these tests SAR without trunk reservation outperforms both FHR and SAR with trunk reservation. The poor performance of trunk reservation is somewhat unexpected given the finding by Frank Kelly that this technique can approach the performance of dynamic routing schemes for highly connected networks (Kelly, 1994).  Although the 6-node test network used in these tests is fully connected, it may be too small to fit Kelly's description of being highly connected. Each switch in the test network connects with exactly five other switches. Traffic overflowing from any one these connections must find a route through the other four. A larger, highly-connected network would have more connections over which to distribute overflow traffic.  For the trunk reservation schemes the highest blockage consistently occurred on OD pair 5—>1, and the second highest on 1—>5. These were, not surprisingly, the OD pairs with the greatest demand. Figure 14 shows blockage on the OD pairs with the most blockage. With SAR, blockage was well distributed, decreasing very little between the highest and fourth highest OD pair. In contrast, for the trunk reservation schemes, blockage falls off very quickly after the two highest OD pairs. The results of the 8% and 12% trunk reservations schemes were intermediate between those of the 4% and 16% schemes, and for readability the 8% and 12% results are not shown.  42  Mean Blockage on OD Pairs with Most Blockage  1st  2nd  3rd  4th  OD Pairs with Most Blockage Figure 14: Mean Blockage on O D Pairs with the Most Blockage  Chapter 5 - Discussion and Recommendations Simulation is used to test routing schemes before they are deployed. This is important because there is a risk for Telus in adopting a new class of routing schemes to replace the existing FHR. Without some evidence that a new scheme will work as intended, Telus may be unwilling to change their network operations and risk the possibility that it will degrade performance. Simulation can give assurance that a new scheme will perform as intended.  This thesis has described a number of verification tests for the simulator, and although the simulator passed all of the functional tests, it failed to produce blockage at the expected level using the default time interval. Blockage was closer to the expected level when the simulator was run with shorter time increments. Because of these results I recommend using a short time increment to simulate the lower mainland network. Shorter increments require longer run times because more increments are needed to simulate a given length of time. B y testing with various increments the team may be able to find an increment that gives simulation results consistent with those observed by Telus, but without requiring overly long runs.  43  There is no obviously single best measure to use when comparing the performance of routing schemes. Total network-wide blockage gives no indication of how blockage is distributed, and pair by pair blockage comparisons can give ambiguous results, with one scheme better for some pairs and another scheme better for others. I recommend using the same comparison measure used for the tests in the Results section, namely the maximum blockage across all OD pairs. This approach is more sensitive to localised blockage than using total network-wide blockage, and it is free of the ambiguities of pair by pair comparisons.  The goal of any new routing scheme is to reduce or eliminate peak-period blockage in the lower mainland, but blockage is necessary in the simulation to compare routing schemes. If two schemes both eliminate all blockage, then both can be said to perform equally well for the given demand. In that case, it may be necessary to scale up the demand until blockage occurs for one or both schemes.  Chapter 6 - Areas for Further Investigation The simulator may understate blockage because it removes expired calls before placing new calls. Presumably, therefore, i f it placed new calls before removing expired calls it would overstate blockage. However, if the simulator was modified to randomise new and old calls together, it would process calls in no particular order and should neither overstate nor understate blockage. The simulator already randomises new calls to avoid an order bias among OD pairs. This process could be extended to include both new and expired calls. Afterward the simulator could be tested again against the expected blockage calculated by Erlang's loss formula.  Load share or random routing is an area for further investigation. Load share is similar to SAR, except that with SAR the route sets are ordered, whereas with load share they are unordered and, instead, routes have weights called attraction coefficients. S A R distributes calls in fixed sequence to the members of the route set, but load share distributes them randomly in proportion to their attraction coefficients. Load share should produce less spill-over congestion than SAR. Although load share routing is not an option  44  for Telus, this investigation could highlight the hidden costs of inefficiencies resulting from the heterogeneous mix of switches in the Telus network.  Both these areas for further investigation will need to use a separate random number generator from the one used to create calls. Otherwise it may not be possible to exactly reproduce a call stream by specifying a random number seed.  Another area worth investigating is to find upper bounds on performance as described by Frank Kelly (Kelly, 1994). A n upper bound on performance could show the project team how much room exists for an improvement in routing, and whether it is worth continuing the search to find it.  The purpose of a new routing scheme is to accommodate growth in demand without additional investments by Telus. Demand grows at uneven rates throughout the lower mainland, and this uneven growth could affect the relative performances of various routing schemes. Therefore it seems reasonable to test the schemes using not just today's demand, but the forecasted future demand.  Ultimately of interest to Telus is the savings in investment dollars that can be achieved with a new routing scheme. Doverspike and Jha describe a method of comparing routing schemes by finding the smallest network that can satisfy demand with each scheme (Doverspike and Jha, 1993). A variation on that method could be used by the Telus team to find the potential savings to Telus from a new scheme. This would involve first finding the best routing scheme for forecasted future demand with the existing network, then using the network design tools used by Telus to find the minimum sized network needed to give the same QoS with FHR. The difference between the existing network and the network needed with FHR represents the potential savings achieved by the new scheme.  Chapter 7 - Conclusion Simulation has an important role to play in the process of developing of an improved routing scheme for the lower mainland network. The role includes comparing various  45  schemes to find the most efficient scheme, demonstrating the robustness and sensitivity of that scheme to changes in demand.  The simulator written for this project is capable of running the required simulations, provided that the network and traffic model used for the simulations are sufficiently realistic. This will be confirmed through tests to validate simulation results against those of the production network. If the validity test results match those of the production network, then the simulator and model can be used to compare routing schemes. If not, then either the simulator or the model must be modified to more accurately reflect the production system.  46  Appendix 1 - Manual Simulation Rerun This test consisted of performing a short simulation run using a 3-node network. The test generated only a few calls, but sufficient calls that it had both overflow and blockage. Those same calls were then rerun manually through an identical network, and the results of the manual run were compared with those of the simulation. Simulation by Program  Simulator Input Files 0,1, 0,2, 1,2,  4 4 4  Table 5: Arc Capacities by O D Pair 0,1 0,2,1 0,2 1,0 1,2 2,0 2,1 Table 6: Routes = Origin, [Tandem], Destination 0,1, 0,2, 1,0, 1,2, 2,0, 2,1,  .75 .5 .25 .25 . 5 .75  Table 7: Calls per Minute by O D Pair 0,1, 0,2, 1,0, 1,2, 2,0, 2,1,  .25, .25, .25, .25, .25, .25,  .25, .25, .25, .25, .25, .25,  .25, .25, .25, .25, .25, .25,  .25 .25 .25 .25 .25 .25  Table 8: Mean Service Times by O D Pair  47  Simulator Output Report Run  0  0 0 1 1 2 2  D 1 2 0 2 0 1  time i n minutes:  Total Calls  15 15 7 8 13 19  25  Blocked Calls % 2  13  1  14  2  10  T o t a l C a l l s : 77 Successful C a l l s :  Overflow Calls % 1  6  72  Table 9: Output Report (extract)  48  Average Lines Used 1.80 2.88 1.80 2.40 2.88 2.40  Manual Simulation Rerun Minute 0-1 0-2-1 0-2 1-0 1-2 2-0 2-1  1  2 4 12 3 5 6 7 8 9 10 11 Ki>ui<> i()rigin- TandemJ-De 5lma la®n) and Calls in Progress by Minute 2 2 1 1 1 1 2 2 2 2 2 3  13  1  3 1 1 1 1  2  1  1  1  1  2  1 1  2  1  1  1  2 2 2 1 2 2 2 2 2 2 2 1 1 1 1 1 3 4 3 2 4 2 2 1 2 1 2 Trunks (Origin-Destination & IrankCount) and Calls in Progress bviMihute 1 1 2 2 2 0-1: 4 2 2 1 1 3 3 2 0-2: 4 3 4 3 3 3 3 4 2 2 2 2 2 1-2:4 1 3 4 3 2 4 2 2 3 4 3 3 l JM \ ttempfci p l inlMIi mati<SiM! C all LenS H l i M i n u l e - r : 2-0: 2 0-2: 1 2-1:4 0-2:4 2-1: 3 2-0:2 0-1:4 0-2: 3 2-0: 2 0-1:4 2-0: 3 0-2: 3 2-1: 3 2-0:4 0-1:4 2-1: 1 0-1:4 1-0: 1 1-2: 2 2-1: 3 1-2: 1 0-2: 3 2-1: 4 1-2: 4 0-1: 2 2-1: 2 2-1: 4 2-0: 4 0-1: 2 2-1: 2 0-1: 3 0-2: 3 2-1: 2 2-0: 3  Table 10: Manual Rerun - Minutes 1 to 13 14 I 15 I 16 I 17 I 18 I 19 I 20 I 21 I 22 I 23 I 24 I 25 Routes (Origm-[Tandem1-Destination) and Calls in Progress by.Minute'0-1 3 0-2-1 1 2 0-2 2 2 2 1-0 1 1 1 1 1 2 1 1-2 2 1 4 1 3 2-0 1 2 2 2-1 1 Trunks (Origin-Destination & Trunk Count) and Calls in Progress by Minute 0-1:4 4 3 2 2 1 1 0-2:4 4 2 4 4 1 4 4 1-2:4 4 1 1 4 1 3 Call Attempts (Oiigin-Ocstination and Call I ength) by Minute 1-2: 4 0- 2: 1 0-2: 2 2-1: 2 2-0:2 2-0:4 2-0:4 1- 0: 1 2-1: 3 1-2: 1 2-1: 2 0-2: 1 1-0:2 2-0: 3 2-1: 1 2- 0: 2 2-1: 3 2-1:2 0-2:4 1-0: 2 1- 0: 2 0-2: 2 2-0:4 0-1: 1 0-1: 1 2-1: 1 0-1: 3 1-0: 1 0-2: 3 0-2: 2 2-1: 1 1-2: 1 1-2:4 0-1: 3 0-1:3  Minute  Table 11: Mnual Rerun - Minutes 14 to 25 49  3  4 4 2 0-2:4 1-2: 1 0-2: 1 1-0: 4 0-1: 2 0-1: 3 0-1": 2  The column on the right labelled Count is the number of calls completed per route. Usage is equal to the average number of calls in progress per minute per trunk group. Blocked call attempts are shaded, and overflow calls are outlined with a heavy border.  The results from the simulator match exactly the results from the manual rerun.  Appendix 2 - Call Generator Tests Call Arrivals by OD Pair This test examined whether the simulator generates calls at the rate specified in the call arrivals input file. The null hypothesis is that the total number of calls generated for each OD pair does not differ significantly from the expected number of calls given a specified arrival rate and run length.  In the following table, the column headings are the expected number of calls for each of six test runs. The rows are the observed number of calls generated for twelve OD pairs in each run. There are 12 degrees of freedom for each column because the observed values are tested against the constant expected values. Given the p-values shown, we do not reject the null hypothesis.  Expected: Observed:  1600 800 400 200 100 50 1612 792 394 206 111 41 794 1638 369 161 92 50 1593 204 799 398 102 40 1584 805 386 206 98 51 1632 779 387 207 102 48 1609 831 425 208 98 52 394 1636 755 194 45 99 1544 820 414 202 98 51 1632 807 418 222 115 49 1568 785 367 210 103 53 1527 812 425 208 103 43 832 1597 387 205 107 53 Chi-Squared: 9.3 6.7 11.1 12.2 5.0 5.7 p-value: 0.681 0.874 0.523 0.432 0.959 0.931 Table 12: Chi-Squared Test of Observed Calls to Expected Calls 50  Call Arrivals over Time This test examined the distribution of calls created over time. The hypothesis is that calls are generated Poisson. The analysis involved counting the number of calls created in each minute, and forming a 21 bin histogram of the counts. Then the expected numbers were found for the bins using the marginal probabilities of a Poisson distribution with a mean of twenty, as shown in the column labelled Marginal (Table 13). If calls are generated Poisson, then the observed and expected counts should have the same distribution. A chisquared test of the two distributions gives a p-value 0.785614, so we do not reject the null hypothesis. The chi-squared test had 20 degrees of freedom. One degree of freedom is lost because the counts must sum to the same total.  Calls Observed Expected 0 0 0 2 0 0 4 0 0 6 3 1 12 8 9 10 35 44 141 12 135 14 308 329 16 578 581 802 18 809 893 888 20 22 856 807 24 585 613 26 388 394 28 221 218 104 30 116 32 41 44 34 15 16 36 3 5 38 1 2 >38 0 1 Sum: 4999 4999  Marginal Chi-Squared 1.030E-05 2.061E-09 4.535E-07 2.267E-03 1.649E-05 8.243E-02 2.382E-04 2.750E+00 1.832E-03 8.813E-01 8.724E-03 1.701E+00 2.820E-02 2.531E-01 6.585E-02 1.365E+00 1.481E-02 1.162E-01 1.603E-01 6.871E-02 1.777E-01 2.621E-02 1.615E-01 2.921E+00 1.226E-01 1.275E+00 7.889E-02 1.023E-01 4.355E-02 4.933E-02 2.086E-02 1.319E+00 8.747E-03 1.701E-01 3.238E-03 8.729E-02 1.066E-03 1.018E+00 3.141E-04 2.072E-01 1.088E-04 5.437E-01 1 1.48E+01 p-value: 0.785614  Table 13: Histogram of Calls Generated per Minute  51  Appendix 3 - Call Placement Balance Determining a Warm Up Period At the start of a simulation run the network is empty, so at least initially, the simulation tends to understate blockage and overflow because there are no calls in progress. The model needs to be warmed up before starting to record statistics for analysis. Because call traffic is stochastic, the warm up period may vary in length from one run to another. Therefore a longer, more conservative warm up period is generally desirable, but not so long as to involve a large amount of needless processing.  To chose the length of the warm up period, the model was first run three times with no warm up. Blockage was recorded both in discrete 25 minute intervals, and continuously from the start of the run. The results were graphed, and a warm up period was chosen by a visual inspection of the graphs. Three runs were used to get a rough indication of the degree of variability in the length of the warm up period.  Initial Conditions Effect  i  25  1  i  225  Minutes  1  i  !  1  425  625  i  1  1  825  _•_ Continuous —•—Interval  Figure 15: W a r m Up Period - Run #1  52  Initial Conditions Effect 30%  o> 20% o  o m  10%  0% 25  225  Minutes  425  625  _n— Continuous  825  -•— Interval  Figure 16: Warm Up Period - Run #2 Initial Conditions Effect 30%  225  Minutes  425  625  -o— Continuous  825  Interval  Figure 17: Warm Up Period — Run #3 From these graphs a warm up period of 500 minutes was chosen.  Call Placement Test The model was run 33 times, and for each run blockage was recorded independently for O D pairs 0->l and 3->2.  53  OD Pair 0^1 Mean Standard Error Median Standard Deviation Sample Variance Range Minimum Maximum Sum Count Confidence Level(95.0%)  0.14322 0.00360 0.14218 0.02068 0.00043 0.12809 0.11273 0.24082 4.72622 33 0.00733  OD Pair 3-+2 Mean Standard Error Median Standard Deviation Sample Variance Range Minimum Maximum Sum Count Confidence Level(95.0%)  0.14195 0.00204 0.14063 0.01171 0.00014 0.05584 0.11373 0.16957 4.68444 33 0.00415  Table 14: Descriptive Statistics for Blockage from 33 Test Runs  Mean Variance Observations Pearson Correlation Hypothesized Mean Difference df t Stat P(T<=t) one-tail t Critical one-tail P(T<=t) two-tail t Critical two-tail  OD Pair 0-+1 0.14321891 0.00042748 33 0.42436105 0 32 0.38383053 0.35182132 1.69388841 0.70364264 2.03693162  OD Pair 3^2 0.141953 0.000137 33  Table 15: t-Test: Paired Two Sample for Means  The means for the two samples were compared with two different tests - once by constructing 95% confidence intervals, and again with a two sample t-test. Neither test found any evidence of a difference between the means for the two samples, so we conclude that call placement is balanced.  Appendix 4 - Observed Versus Expected Blockage This test consisted of comparing blockage generated by the simulator against the expected blockage found using Erlang's loss formula. The network model comprised a single 1000 trunk arc between two nodes. The simulation was run multiple times with different arrival rates to observe blockage at various levels of demand. After each run, the expected blockage was found for the same level of demand, and the results were graphed.  54  One set of tests was run with a mean service time of 5.515 minutes per call. A second set of tests was then run with a mean service time of 11.029 minutes - double the length of the first set. Below is a graph of the probability distribution for call service times used for these tests with means of 5.515 minutes and 11.029 minutes.  Exponential Call Lengths Probabilities 0.20 0.15 !5 re  0.10  Q_  0.05  .a o  0.00 1 9 17 25 33 41 49 57 65 73 Call Length in Minutes M U = _ . _ 5 515 _ _ 11.029 Q  Figure 18: Exponential Call Lengths Probabilities  Determining a Demand Range and Warm Up Period The demand range for these tests was chosen by trial and error such that at its low end blockage was negligible, and at its high end blockage was about 12%. Because the warm up period had to be appropriate over the whole range, the simulation was then run for 2500 minutes, two times each, for low, medium and high levels of demand. With each run, blockage was sampled both at 25 minute intervals and continuously, and graphed.  55  Initial Conditions Effects 15%  „ . Af5?^^^ 10%  0%  T — i — I — I — r  —i—i—i—i—i—i—i—i—i—i—i—i—i—i—i—i—r  25 825 1625 2425 Minutes -o— Continuous High _ • _ Discrete High —±— Continuous Medium _o— Discrete Medium Figure 19: Initial Conditions Effects at Medium and High Demand, Run #1  Initial Conditions Effects 15% .  ^  1  1  ^^jf^i^mhh^  1  & 10% CO.  5%  n—i—i—i—i—i—i—i  i  i  r  825 1625 2425 -a— Continuous High —•_ Discrete High -tr- Continuous Medium —o— Discrete Medium Figure 20: Initial Conditions Effects at Medium and High Demand, Run #2  Since demand at the low end of the test range produced negligible blockage, the results are not included in the graphs. Medium and high levels of demand produced blockage averaging about 5% and 12% respectively. From a visual inspection of these graphs a warm up period of 1000 minutes was chosen.  56  Appendix 5 - Comparison of Routing Schemes Simulations were run on a 6-node test network to compare the performance of F H R and SAR schemes. The direct route was always the primary route for both schemes. The schemes differed in the choice of alternate routes. The full set of F H R alternate routes by OD pair is given in table 16. Route sets are listed in square brackets separated by commas, and only the tandem switches are shown. For example, route 4—>0—>3 is shown as [0]. If a route includes multiple tandems they are enclosed within curved brackets. For example, route 1—>3—>0—>5 is shown as [..., (3,0), ...].  0^1 0-*2 0->3 0^4 0-»5 1-+2 1^3 l->4 l->5 2->3 2^4 2^5 3^4 3^5 4^5  ]  [.0] [0] [0] [0] [0] [0] [0] [0] [0] [0]  1234523->l 4^1 5345455-  0] 0] 0] 0] 0] 0] 0] 0] 0] 0]  Table 16: Alternate Routes for F H R  With FHR, only switch 0 can serve as a tandem, therefore all alternate routes go through switch 0. As a consequence there are no alternate routes for traffic between switch 0 and any other switch.  In the S A R scheme any switch can serve as a tandem, so many more alternate routes are possible, including alternate routes for traffic between switch 0 and the other switches. The S A R route sets were designed using the F H R sets as a starting point. The differences between the S A R and FHR route sets are depicted in table 17. For example, for calls between OD pair 1—>5, overflow traffic is offered in turn to each of the following routes:  57  1—0—5, 1—4—5, 1—3—5, 1—>2—*5, 1—3—0—5, and finally 1—2—0—5. If all of these routes are blocked then the call is blocked.  0—1: 0— 5: 1 - 5: 3-1: 3—5:  [0,2] [0,4] [0,4, 3, 2, (3,0), (2,0)] [0,4] [0,2]  1—0: [0,2] 5—0: [0,2] 5 - 1 : [0, 4, 2, 3, (3,0), (4,0), (2,0)]  Table 17: Differences in Alternate Routes for S A R versus F H R  The differences between the F H R and SAR route sets are the alternate routes in S A R for traffic to and from switches 1 and 5. These were the switches with the highest traffic volumes.  58  References Ahuja, Ravinda K., Thomas L . Magnanti and James B . Orlin. Network Flows. Prentice Hall, New Jersey, 1993. Aiello, William, et al. A Performance Comparison of Competitive On-line routing and State-Dependent Routing. Bell Communications Research, 1997, <http://cm.bell-labs.com/cm/ms/who/andrews/comparison.ps>. Alternative Routing Systems. Department of Electrical Engineering, University of Cape Town, 1999, <http://www.ee.uct.za/~traffic/ch5>. Box, George E.P., William G. Hunter and J. Stuart Hunter. Statistics for Experimentation. John Wiley & Sons Inc., New York, 1978. Chan, Huang-Leng, and Ren-Hung Hwang. On L L R Routing in Circuit-Switched Networks. IEEE Computer Society, 1998, <http://www.computer.org/CONFEREN/proceed/icoin/7225/7225045abs.htm>. Denardo, Eric V . and Haechurl Park. Efficient Routing of Telephone Calls. Working paper, Yale University, October, 1990. Designing Networks to Control Grade of Service. International Telecommunications Union, June, 1992, <http://www.itu.org>. Doverspike, Robert and Vikas Jha. Comparison of Routing Methods for DCS-Switched Networks. Interfaces, 23:2 March-April 1993. Littlechild, S.C. Elements of Telecommunications Economics. A . Wheaton & Co. Ltd., Exeter, U.K., 1979. Kelly, F.P. Blocking Probabilities in Large Circuit-Switched Networks. Advanced Applied Probability, Northern Ireland, vol. 18: 473-505, 1986. Kelly, F.P. Bounds on the Performance of Dynamic Routing Schemes for Highly Connected Networks. Mathematics of Operations Research, Providence, RI, vol. 19: 1-20, February 1994. Kelly, F.P. Routing in Circuit-Switched Networks: Optimization, Shadow Prices and Decentraliation. Advanced Applied Probability, Northern Ireland, vol. 20: 112144, 1988. Kelton, W. David, Randall P. Sadowski and Deborah A . Sedowski. Simulation with Arena. WCB/McGraw-Hill, Boston, 1998. Martine, Roberta R. Basic Traffic Analysis. A T & T . Prentice Hall, Englewood Cliffs, New Jersey, 1994.  59  Montgomery, Douglas C. Design and Analysis of Experiments. John Wiley & Sons, Inc., New York, N Y , 1991. Norris, Mark. Understanding Networking Technology. Artech House, Boston, 1996. Notes on the Network. American Telephone and Telegraph Company, U.S.A., 1980. Mendenhall, William, Dennis D. Wackerly and Richard L. Scheaffer. Mathematical Statistics with Applications. PWS-Kent Publishing Company, Boston M A , 1990. Papadakis, Yanni. The Erlang Loss Network E L N Routing Problem, unpublished draft, University of British Columbia, September 1999. Sanso, Brunilde and Francois Soumis. A Global Optimization Routing Model and Applications in Telecommunications Networks. Centre for Research on Transportation, Ecole Polytechnique, Montreal, October 1989. Schwartz, Misha. Telecommunications Networks: Protocols, Modeling and Analysis. Addison-Wesley Publishing Company, Reading M A , 1987. Telecommunications News. Circuit-Switched or Packet-Switched. Issue 16, September, 1998, <http://www.tmo.hp.com/tmo/tcnews/9811/16tncov.html> Titch, Steven. Defensive Measures, Telephony, via ProQuest, vol. 232, Issue 11, Chicago IL, March, 1997. van de Leensel, Robert. Models and Algorithms for Telecommunication Network Design. Proefschrift Universiteit Maastricht, 1999. Weik, Martin H. Communications Standard Dictionary. Van Nostrand Reinhold Company, New York, 1983.  60  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0089511/manifest

Comment

Related Items