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

E F F I C I E N T R O U T I N G O F T E L E P H O N E C A L L S I N A C I R C U I T - S W I T C H E D N E T W O R K b y D a r r e l B r a u n B . S c . ( C o m p u t e r S c i e n c e ) U n i v e r s i t y o f V i c t o r i a , 1 9 8 1 A m a j o r e s s a y s u b m i t t e d i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r t h e d e g r e e o f M a s t e r ; o f S c i e n c e ( B u s i n e s s A d m i n i s t r a t i o n ) i n 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 this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. 1 further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of L^over-ce. <ani 8oS<ngs_s /Icm'inislrjio'n The University of British Columbia Vancouver, Canada Date Slooo DE-6 (2/88) 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 flat-rate 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 wil l 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. i i Table of Contents Abstract i i Table of Contents i i i 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 54 Determining a Demand Range and Warm Up Period 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 FHR 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 t hofthe 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, flat-rate 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 ever-growing 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, i f 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 FHR 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 i f 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, i f 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 i f 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. By 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. No te , though, that every trunk group to a tandem is part o f mul t ip le routes so when a group is expanded its added capaci ty is avai lable for a l l routes shar ing the group. B a s i n g investment decis ions on average trunk card costs can be mis lead ing i f one o f the card racks is out o f space. In that case it might be more cost eff ic ient to add cards to an alternate route w i th rack space already avai lable. B y t rack ing the amount o f unused space on each rack, investment decis ions cou ld be based on marg ina l costs rather than average costs. De te rm in ing the annual requirements for card racks is more d i f f icu l t at Te lus today than it was i n past because changes in the te lecom market i n recent years have made accurate demand forecasts m u c h harder to obtain. In past, demographic growth served as a fa i r ly good predictor o f demand, but i n today 's market compet i t ion, new technologies and new services a l l impact on demand. Internet growth, ce l l phones, advanced ca l l i ng features, and flat-rate long distance are on ly some o f the factors that c l oud the forecast ing out look. Compet i t i ve carriers can n o w buy bu lk services f rom Te lus , creat ing demand where none p rev ious ly existed, or they can reduce demand b y d rawing customers away to independent networks. In response Te lus has fo rmed a team charged w i t h deve lop ing a more rel iable approach to forecast ing, better suited to today 's marketplace. Routing Rules A l l alternate routes i n the lower ma in land pass through two tandem swi tches: M u t u a l and N e w Westminster , i n a F H R scheme patterned after the long distance network. H o w e v e r , F H R is on l y one o f many forms o f rout ing. F o r example, any sw i tch i n the lower ma in land cou ld serve as a tandem. Therefore, any sw i tch cou ld serve as an intermediary for the creat ion o f alternate routes. F H R is a subclass o f the more 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 or ig in/dest inat ion ( O D ) sw i tch pair . C a l l s are offered in turn to each route in the set unt i l either an avai lable route is 10 found, or the set is exhausted and the call is blocked. There are thirty-three switches in the lower mainland. FHR uses just two of these for its alternate routes, but SAR could use any of the thirty-three switches, plus combinations of switches. Therefore with SAR vastly more alternate routes are possible between every OD pair. SAR 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), i f 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 FHR is a subset of SAR, it is always possible to design a SAR scheme that performs at least as well, i f 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 is to a l l ow business traff ic to over f l ow through resident ial area swi tches and v ice-versa. T h i s strategy tends to smooth the demand throughout the day, emp loy ing the otherwise unused capaci ty that exists i n areas o f the network dur ing their of f -peak per iods. A m o n g the var ious rout ing schemes descr ibed i n the literature rev iew, are forms o f state-dependent routing that respond dynamica l l y to the current traff ic load. These schemes route cal ls around congest ion. Th is requires that the system be capable o f mon i to r ing traff ic vo lumes and select ing appropriate routes. State-dependent rout ing is used i n the Canad ian inter-carr ier long distance network. U n l i k e the case w i th tradi t ional c i rcu i t -swi tched networks, cal ls i n the inter-carrier network can be dynamica 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 Te lus network, state-dependent rout ing is not an opt ion. One fo rm o f rout ing is ca l led load share or random routing. In this scheme each member o f a route set is assigned a numer ica l weight ca l led an attraction coeff ic ient . C a l l s are distr ibuted to members o f the set i n propor t ion to their attraction coef f ic ients. F o r example , i f a set o f routes Ri, R2, and R 3 have weights 75, 15 and 10 respect ive ly , then 7 5 % o f ca l ls are randomly directed to Ri, 1 5 % to R2, and 1 0 % to R 3 . Depend ing on h o w the rules are implemented, i f a route is b l ocked either the ca l l is b l ocked or it is retr ied on another route. L o a d share rout ing has the potent ia l to distr ibute ca l ls more even ly across a network than S A R , thus leading to fewer b locked edges and less sp i l l -over congest ion. H o w e v e r , this method o f rout ing is not an opt ion for Te lus . One fo rm o f dynamic rout ing that is avai lable to Te lus is time-dependent routing, i n w h i c h the rout ing rules change over t ime. The changes can inc lude any aspects o f the rules, such as the cho ice o f routes i n the route set, or the cho ice o f attraction coef f ic ients for load share rout ing. Somet imes t ime-dependent rout ing schemes are adaptive, w i t h rules that change automat ical ly and per iod ica l l y i n response to past system per formance. These schemes are s imi la r to state-dependent rout ing except that they respond to past condi t ions rather than current condi t ions. Te lus cou ld use a l im i ted fo rm o f t ime-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 State-Dependent 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 COL 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 ho ld ing t imes are k n o w n in advance, the authors use a L inea r P rog ram ( L P ) to f ind the op t ima l va lues for each arc. I f the rates and t imes are unknown , the authors start the a lgor i thm w i t h an offered load equal to capaci ty and adjust the values per iod ica l l y dur ing operat ions i n response to the observed traff ic. Th is var iat ion they ca l l S D R - A D A P T . T o compare the performance o f C O L , S D R and S D R - A D A P T the authors ran s imulat ions on networks ranging in size f rom f ive nodes to 66. These inc luded sma l l networks w i th un i f o rm arc capacit ies as w e l l as more comp lex cases based on rea l -wor ld commerc ia l networks. Some were fu l ly connected and others sparsely connected. C a l l s were mode l l ed us ing Po i sson arr ival rates and exponent ia l service t imes. A s a per formance measure the authors used the total number o f rejected ca l ls . In most cases S D R gave lower re ject ion rates than the other algor i thms - somet imes substant ial ly lower . C O L somet imes gave rates c lose to S D R i f the r ight base was used for the exponent ia l funct ion. H o w e v e r , the authors cou ld not f ind a general method for choos ing a good exponent ia l base. Th i s study looks on ly at forms o f dynamic rout ing that are not avai lable to Te lus . H o w e v e r , the study does point to the fact that changes i n rout ing schemes can result i n large di f ferences in network performance. Comparison of Routing Methods for DCS-Switched Networks (Doversp ike and Jha, 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 rcu i t -swi tched network w i t h swi tched d ig i ta l l ines. D C S networks are data networks that serve as a cost sav ing alternative to d ig i ta l leased l ines. In this study the authors use s imula t ion to compare the per formance o f a D C S network w i th s ix different rout ing schemes. F i v e o f the schemes are variants o f S D R , descr ibed above in the paper b y A i e l l o et a l . The other is F H R - the scheme current ly used by Te lus . T h e f ive S D R variants are based on combinat ions o f two opt ions. The first op t ion is between us ing the same cost funct ion as descr ibed above for A i e l l o et a l , or a mod i f i ed 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. By either measure, FHR 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 non-linear equations. These are solvable for simple networks, but become impractical for large networks. He then demonstrates that for large networks, i f both the number of circuits and the traffic volumes are increased together, individual links block traffic almost as i f 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 SAR 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 i f 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 AT&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 th i rd and fourth schemes the authors present are forms o f dynamic rout ing. Ne i ther o f these is an opt ion for Te lus . H o w e v e r , their first two schemes are both forms o f S A R and cou ld be implemented at Te lus . These two schemes both operate b y o f fer ing cal ls sequent ia l ly to ranked members o f a f i xed route set, but di f fer i n h o w the members o f the route sets are ordered. A Global Optimization Routing Model and Applications in Telecommunication Networks (Sanso and Soumis , 1989) Sanso and Soum is present a central ised network rout ing mode l w h i c h y ie lds the op t ima l rout ing for a network measured i n terms o f the fewest lost cal ls . Sanso and Soum is start w i t h an object ive funct ion that m in im ises a lost ca l l penalty funct ion, i n w h i c h the number o f lost cal ls is found f rom the probab i l i t y o f b l ock ing g iven b y E r l a n g ' s loss fo rmu la summed over a l l arcs i n the network. Te lephone networks are often mode l l ed as mu l t i - commod i t y f lows , w i th determinist ic demand and expl ic i t capaci ty constraints. The approach deve loped b y Sanso and Soumis el iminates the expl ic i t capaci ty constraints, and more accurately reflects the stochastic nature o f demand than a mu l t i - commod i t y f l ow mode l . T h e authors descr ibe two poss ib le mod i f i ca t ions to their object ive funct ion: one that penal ises the use o f l ong paths, and another that balances lost cal ls among the nodes. F o r the latter mod i f i ca t i on the authors add a term to the object ive funct ion that is equal to the square o f the lost cal ls per arc. W i t h this quadrat ic term in the object ive equat ion they so lve the resul t ing system o f equations us ing a F r a n k - W o l f e a lgor i thm. T o reduce computat ional requirements, the authors approximate the E r l a n g loss fo rmu la w i t h a set o f three funct ions - one each for l ow , m e d i u m and h igh traff ic. F o r traff ic levels f r om just be low to just above the capaci ty o f an arc, they approximate b lockage b y a quadrat ic funct ion. A t levels be low that, they approximate b lockage as zero , and above it they approximate it as the di f ference between the demand and the capaci ty . 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 SAR 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 wil l 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, i f 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 Va l i da t i ng the s imula t ion m o d e l is a separate and dist inct process f rom that o f ve r i f y i ng the so f tware . Ve r i f i ca t i on focuses on the too l used to per form the s imulat ions. V a l i d a t i o n focuses on h o w accurately the s imula t ion mode l represents the real w o r l d , and o n the cred ib i l i ty o f the results it generates. S imu la t ion is a too l w i t h w h i c h to study a sys tem's behaviour . F o r ex is t ing systems, it can be used to see h o w changes affect the sys tem's behaviour . F o r p lanned systems, it can be used to test the behaviour o f alternative system designs. In either case, every s imula t ion mode l inc ludes some s imp l i f y i ng assumptions and approx imat ions. Therefore, the behav iour o f the mode l may not match exact ly w i t h that o f the system, but it shou ld be c lose enough that the mode l is a rel iable p r o x y to the system. V e r i f y i n g a mode l is the process o f con f i rm ing that its behaviour is c lose enough to that o f the rea l -wor ld system to re l iab ly serve as its proxy . The team w i l l be w o r k i n g w i th a mode l o f the ex is t ing Te lus network and peak per iod demand. W h e n this mode l is run w i th the current F H R scheme it should produce results consistent w i t h those observed by Te lus. I f the s imula t ion results were found to be inconsistent w i t h the actual results, then any tests o f alternate rout ing schemes w o u l d be suspect. That is to say, i f s imulat ion can not accurately mode l the per formance o f the ex is t ing rout ing scheme, then what reason is there to be l ieve that it can predict the performance o f any alternate scheme? Va l i da t i ng the mode l w i l l require fo rm ing conf idence intervals for b lockage and ove r f l ow b y O D pair f rom a number o f s imulat ion runs. T h e n the conf idence intervals w i l l be compared w i t h the actual b lockage and over f l ow for the same O D pairs to see i f the results are consistent. Running Simulations E v e r y s imula t ion run starts co ld w i th no ca l ls i n progress and l itt le or no b lockage. A s it warms up, the b lockage increases unt i l it levels o f f and starts to f luctuate around a mean. 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, i f 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. Of 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 i f 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 LP 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 LP'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 LP 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. By 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 SAR 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 SAR 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 Destination Call Data Traffic Pattern Analysis Network Structure Routing Rules t Linear Program Solution Analysis Network Simulation Results 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 LP 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 ] 2 fori = 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 T (A 800 --a> oc 600 a> 3 400 --O o O 200 -0 4 8 12 16 Calls in One Minute 20 24 28 32 36 I Observed • 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 wil l 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: 1 2 3 4 5 OD Pair: 3,1 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. Of 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] 2 Pi*C 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 Pi*C 1189 1189 1189 1189 1189 1189 1189 1189 1189 1189 X2 0.189 0.068 1.938 1.414 0.215 2.928 0.030 0.013 0.021 0.613 11890 11890 7.430 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.15055 0->1:l 1 1 3^2: 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]) j7i! , _ , Pi = for i = 0, 1, ... ,k where k is the number of trunks in the group. k K i E t s r y / 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 i f 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 T J d> o a> a . x UJ 1.00 .75 .50 O c .2 .25 o re .00 h 935 975 1015 1055 1095 Calls per Minute * Average Length 1135 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, i f 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, i f 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 0+1,0 • 320 trunks: • 280 trunks: • 200 trunks: Call Frequencies • 5 calls/minute: • 8 calls/minute: • 9 calls /minute: • 11 calls/minute: • 12 calls/minute: • 13 calls/minute: • 19 calls/minute: Figure 12: Test Network for Comparison of Routing Schemes 5 and l<->5 l<-»2, l<->3 and l«->4 5-^2, 5-^3 and 5<->4 elsewhere 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 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 re o o 52 re CQ >20 CQ 6 m c u Q_ 10 — 8% — 12% — 16% - 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 OD 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 wil l 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. By 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, i f 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. SAR 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). An 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 , 4 0 , 2 , 4 1 , 2 , 4 Table 5: Arc Capacities by OD Pair 0 , 1 0 , 2 , 1 0 , 2 1 ,0 1 ,2 2 , 0 2 , 1 Table 6: Routes = Origin, [Tandem], Destination 0 , 1 , . 7 5 0 , 2 , . 5 1 , 0 , . 2 5 1 , 2 , . 2 5 2 , 0 , . 5 2 , 1 , . 7 5 Table 7: Calls per Minute by OD Pair 0 , 1 , . 2 5 , . 2 5 , . 2 5 , . 2 5 0 , 2 , . 2 5 , . 2 5 , . 2 5 , . 2 5 1 , 0 , . 2 5 , . 2 5 , . 2 5 , . 2 5 1 , 2 , . 2 5 , . 2 5 , . 2 5 , . 2 5 2 , 0 , . 2 5 , . 2 5 , . 2 5 , . 2 5 2 , 1 , . 2 5 , . 2 5 , . 2 5 , . 2 5 Table 8: Mean Service Times by OD Pair 47 Simulator Output Report Run time i n minutes: 25 Total Blocked Overflow Average 0 D Calls Calls % Calls % Lines Used 0 1 15 2 13 1 6 1.80 0 2 15 2.88 1 0 7 1 14 1.80 1 2 8 2.40 2 0 13 2.88 2 1 19 2 10 2.40 T o t a l C a l l s : 77 Successful C a l l s : 72 Table 9: Output Report (extract) 48 Manual Simulation Rerun Minute 1 2 3 4 5 6 7 8 9 10 11 12 13 Ki>ui<> i( )rigin- Tande mJ-De 5lma la® n) and Calls in Progress by Minute 0-1 2 2 1 1 1 1 2 2 2 2 3 2 3 0-2-1 0-2 1 2 1 1 1 1 2 1 2 1 1 1 3 1-0 1 1 1-2 2 2 2 1 1 2-0 2 2 2 2 2 2 2 1 1 1 1 1 2-1 1 3 4 3 2 4 2 2 1 2 1 2 1 Trunks (Origin-Destination & I rank Count) and Calls in Progress bviMihute 0-1: 4 2 2 1 1 1 1 2 3 2 2 3 2 4 0-2: 4 3 4 3 3 3 3 4 2 2 2 2 2 4 1-2:4 1 3 4 3 2 4 2 2 3 4 3 3 2 l JM \ ttempfc i p l inlMIi mati<SiM! C all Len S 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:4 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 1-2: 1 0-1: 2 2-1: 2 2-1: 4 2-0: 4 2-1: 4 1-2: 4 0-1: 2 2-1: 2 0-2: 1 0-1: 3 0-2: 3 1-0: 4 2-1: 2 0-1: 2 2-0: 3 0-1: 3 0-1": 2 Table 10: Manual Rerun - Minutes 1 to 13 Minute 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 0-2-1 0-2 1-0 1-2 2-0 2-1 3 1 2 1 2 1 2 2 1 2 1 1 1 1 1 1 2 4 3 1 2 2 Trunks (Origin-Destination & Trunk Count) and Calls in Progress by Minute 0-1:4 0-2:4 1-2:4 4 4 3 3 2 1 2 4 4 4 2 4 1 1 1 4 1 4 1 Call Attempts (Oiigin-Ocstination and Call I ength) by Minute 1-2: 4 1-0: 2 0-1: 1 1-2: 1 0-1:3 0- 2: 1 1- 0: 2 0-2: 2 0-2: 2 2-1: 2 2-0:2 1-0:2 2-0:4 2-0: 3 0-1: 1 0-2: 2 2-0:4 2-1: 1 2-1: 1 2-1: 1 1-2:4 1- 0: 1 2- 0: 2 0-1: 3 2-1: 3 2-1: 3 1-0: 1 1-2: 1 2-1:2 2-1: 2 0-2:4 2-0:4 0-2: 3 0-1: 3 0-2: 1 Table 11: Mnual Rerun - Minutes 14 to 25 49 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: 1600 800 400 200 100 50 Observed: Chi-Squared: p-value: 1612 792 394 206 111 41 1638 794 369 161 92 50 1593 799 398 204 102 40 1584 805 386 206 98 51 1632 779 387 207 102 48 1609 831 425 208 98 52 1636 755 394 194 99 45 1544 820 414 202 98 51 1632 807 418 222 115 49 1568 785 367 210 103 53 1527 812 425 208 103 43 1597 832 387 205 107 53 9.3 6.7 11.1 12.2 5.0 5.7 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 chi-squared 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 Marginal Chi-Squared 0 0 0 2.061E-09 1.030E-05 2 0 0 4.535E-07 2.267E-03 4 0 0 1.649E-05 8.243E-02 6 3 1 2.382E-04 2.750E+00 8 12 9 1.832E-03 8.813E-01 10 35 44 8.724E-03 1.701E+00 12 135 141 2.820E-02 2.531E-01 14 308 329 6.585E-02 1.365E+00 16 578 581 1.162E-01 1.481E-02 18 809 802 1.603E-01 6.871E-02 20 893 888 1.777E-01 2.621E-02 22 856 807 1.615E-01 2.921E+00 24 585 613 1.226E-01 1.275E+00 26 388 394 7.889E-02 1.023E-01 28 221 218 4.355E-02 4.933E-02 30 116 104 2.086E-02 1.319E+00 32 41 44 8.747E-03 1.701E-01 34 15 16 3.238E-03 8.729E-02 36 3 5 1.066E-03 1.018E+00 38 1 2 3.141E-04 2.072E-01 >38 0 1 1.088E-04 5.437E-01 Sum: 4999 4999 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 1 i 1 i 1 ! i 1 1 25 225 425 625 825 Minutes _•_ Continuous —•—Interval Figure 15: Warm 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 0.14322 Standard Error 0.00360 Median 0.14218 Standard Deviation 0.02068 Sample Variance 0.00043 Range 0.12809 Minimum 0.11273 Maximum 0.24082 Sum 4.72622 Count 33 Confidence Level(95.0%) 0.00733 OD Pair 3-+2 Mean 0.14195 Standard Error 0.00204 Median 0.14063 Standard Deviation 0.01171 Sample Variance 0.00014 Range 0.05584 Minimum 0.11373 Maximum 0.16957 Sum 4.68444 Count 33 Confidence Level(95.0%) 0.00415 Table 14: Descriptive Statistics for Blockage from 33 Test Runs OD Pair 0-+1 OD Pair 3^2 Mean 0.14321891 0.141953 Variance 0.00042748 0.000137 Observations 33 33 Pearson Correlation 0.42436105 Hypothesized Mean Difference 0 df 32 t Stat 0.38383053 P(T<=t) one-tail 0.35182132 t Critical one-tail 1.69388841 P(T<=t) two-tail 0.70364264 t Critical two-tail 2.03693162 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 .a o Q_ 0.05 0.00 1 9 17 25 33 41 49 57 65 73 Call Length in Minutes M U = _ . _ 5 515 _Q_ 11.029 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% 0% „ 10%. A f 5 ? ^ ^ ^ 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 & 10% ^^jf^i^mhh^1 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 FHR 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 FHR 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] 1-2-3-4-5-2-3->l 4 ^ 1 5-3-4-5-4-5-5-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 SAR 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 SAR route sets were designed using the FHR sets as a starting point. The differences between the SAR 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,2] 1—0: [0,2] 0— 5: [0,4] 5—0: [0,2] 1 - 5: [0,4, 3, 2, (3,0), (2,0)] 5 - 1 : [0, 4, 2, 3, (3,0), (4,0), (2,0)] 3 - 1 : [0,4] 3—5: [0,2] Table 17: Differences in Alternate Routes for SAR versus F H R The differences between the FHR and SAR route sets are the alternate routes in SAR 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: 112-144, 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. AT&T. Prentice Hall, Englewood Cliffs, New Jersey, 1994. 59 Montgomery, Douglas C. Design and Analysis of Experiments. John Wiley & Sons, Inc., New York, NY, 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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0089511/manifest

Comment

Related Items