UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Distributed architectures and databases for personal communications networks and services Ng, Leslie J. 1993

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

Item Metadata


831-ubc_1993_spring_ng_leslie.pdf [ 4.77MB ]
JSON: 831-1.0065097.json
JSON-LD: 831-1.0065097-ld.json
RDF/XML (Pretty): 831-1.0065097-rdf.xml
RDF/JSON: 831-1.0065097-rdf.json
Turtle: 831-1.0065097-turtle.txt
N-Triples: 831-1.0065097-rdf-ntriples.txt
Original Record: 831-1.0065097-source.json
Full Text

Full Text

Distributed Architectures and Databases forPersonal Communications Networks and Servicesby Leslie J. NgB.A.Sc. University of Waterloo, Waterloo ON, 1990.A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF ELECTRICAL ENGINEERINGWe accept this thesis as conformingto the required standard THE UNIVERSITY OF BRITISH COLUMBIAMarch 1993© Leslie J. Ng, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature) Department ofThe University of British ColumbiaVancouver, CanadaDate^/1-e ,^ c? 3DE-6 (2/88)AbstractThe objective of Personal Communications Services (PCS) is to enable subscribers to establishor receive calls at any user-network access point, independent of geographic location. A hierarchical,distributed database architecture has been developed to perform those mobility management functionsrequired for PCS. This database architecture is developed in the context of a distributed microcellularnetwork architecture based on the IEEE 802.6 Metropolitan Area Network (MAN). Several accessMANs are internetworked via a backbone MAN; these backbone MANs are themselves interconnectedto serve an entire metropolitan area (MA). The proposed database architecture can also be applied toother network architectures, such as those based on Asynchronous Transfer Mode (ATM) switches. Thephysical and logical database structure and contents have been defined. The protocols necessary toperform the basic mobility management functions of subscriber location at call setup as well as trackingof a roaming subscriber have been developed.Two subscriber location algorithms have been proposed. The signalling traffic and databasetransaction rates required to support subscriber location and tracking are calculated. The worst-casedatabase transaction rate of approximately 2300 transactions per second occurs at the highest leveldatabases. The worst case signalling traffic overhead is approximately 500 kbps on the access MAN and2.5 Mbps on the backbone MAN. Queueing theory has been applied to determine the means and standarddeviations of the database processing times for call setup. The worst case expected time for the ripplesearch is under 20 ms. The worst case expected time for the directory search is bounded above by 40 msor 10 ms, depending on the database transaction capacity. The approximate database sizes are estimatedat 14.5, 7, and 36.8 Mbytes for the access MAN, backbone MAN and MA level databases respectively.A similar analysis is completed for a centralized database architecture, where lower level accessand backbone MAN databases are eliminated and mobility management functions are performed by thecentralized high level Metropolitan Area databases. The worst case transaction rate is over 7000 persecond. The worst case signalling rate is approximately 6 Mbps on both the access and backbone MANs.The worst case expected database processing time is under 10 ms, but is only achievable with databaseshaving a much higher transaction capacity than those considered for the distributed architecture. Thecentral MA database size is estimated to be approximately 476 Mbytes.By utilizing the localized distribution of calls to spread query traffic among different database sitesand levels, our distributed database architecture is expected to be responsive and flexible as PCS demandincreases. Subscriber update traffic is distributed, with detailed information stored close to subscriberlocations.iiContentsAbstract ^  fiList of Figures  viList of Tables ^  viiiAcknowledgements  ix1 Introduction ^ 11.1 Overview and Motivation ^ 11.2 Review of Others' Work 21.2.1 GSM ^ 21.2.2 Ericsson CT-3 Wireless PBX — DECT ^ 41.2.3 Datacycle ^ 51.2.4 Fujitsu/Murakami ^ 61.2.5 Fujioka/Sakai 71.3 Summary of Thesis Research ^ 82 Network Support for Personal Communication Services ^ 92.1 The Intelligent Network ^ 92.2 Personal Communications Services (PCS) — Definition and Requirements ^ 102.3 IEEE 802.6 Metropolitan Area Network — Concept and Architecture^. . . . 112.4 The MAN-Based Personal Communications Network ^ 133 Distributed Database Architecture for Mobility Management Functions inPCS ^ 163.1 Distributed Database Architecture ^ 163.2 Database Contents ^ 193.3 Database Consistency and Concurrency ^ 233.4 Database Indexing Methods ^ 24iii4 Subscriber Location and Tracking ^ 264.1 Ripple Search ^ 264.2 Directory Search 274.3 Subscriber Tracking Methods Using Databases ^ 284.4 Signalling for Different Types of Boundary Crossing 284.5 Determination of Area Boundary Crossing Rates ^ 315 Database Architecture Performance Analysis 335.1 Parameters for Performance Analysis ^ 335.2 Methods Used to Determine Database Transaction Rate ^ 345.2.1 Database Transaction Rate Due to Subscriber Tracking 345.2.2 Database Transaction Rate due to Subscriber Location ^ 375.3 Methods Used to Determine Signalling Traffic ^ 385.3.1 Signalling Traffic Due to Subscriber Tracking 385.3.2 Signalling traffic due to subscriber location ^ 405.4 Methods Used to Determine Callee Location Time at Call Setup ^ 415.4.1 Sources of Delay ^ 415.4.2 Modelling of MAN Database Architecture ^ 415.4.3 Database Processing Delay Calculation Method 436 Results of Analysis ^ 456.1 Parameter Values Chosen 456.2 Database Transaction Rates ^ 496.3 Signalling Traffic ^ 526.4 Database Processing Time for Callee Location at Call Setup — Mean andStandard Deviation ^ 536.5 Relative Database Size 606.6 Analysis of and Comparison with Centralized Architecture ^ 616.6.1 Database Transaction Rate ^ 616.6.2 Signalling Traffic ^ 64iv^6.7^Database Processing Time for Callee Location at Call Setup ^ 656.8 Relative Database Size ^ 666.9^Mobility Management in the ATM Based PCN ^ 667 Conclusions   ^ 687.1^Concluding Remarks 687.2 Suggestions for Further Work ^ 69Appendix A^Database Search Sequence Tables for Ripple and Directory SearchAlgorithms ^  71Appendix B^Expressions to Calculate Database Transaction Rates — Ripple SearchAlgorithm ^  81Appendix C^Expressions to Calculate Database Transaction Rates — Directory SearchAlgorithm ^  84Appendix D^Expressions for Calculation of Signalling Traffic Using Ripple SearchAlgorithm ^  87Appendix E^Expressions for Calculation of Signalling Traffic Using Directory SearchAlgorithm ^  90Appendix F^Signalling Traffic Due to Subscriber Tracking   ^ 92Appendix G^Derivation of Mean Square Value Equation ^ 93References 94List of FiguresFigure 1Figure 2Figure 3Figure 4Figure 5Figure 6Figure 7Figure 8Figure 9Figure 10Figure 11Figure 12Figure 13Figure 14Figure 15Figure 16Figure 17Figure 18Figure 19Figure 20Location registration in GSM system ^ 4PCS network architecture^ 13MAN interconnection within a metropolitan area ^ 15Hierarchical database structure^ 16Database contents when subscriber A is at home access MAN ^ 20Database contents when subscriber A visits an access MAN on homebackbone MAN ^ 20Database contents when subscriber A visits an access MAN in home MA ^ 21Database contents when subscriber A visits outside home MA ^ 21Ripple search database search sequence ^ 27Signalling diagram for BSC area boundary crossing ^ 30Signalling diagram for access MAN area boundary crossing (in homebackbone MAN) ^ 30Signalling diagram for backbone MAN boundary crossing in home MA^. ^ 31Signalling diagram for MA boundary crossing ^ 31Access MAN area representation ^ 32Queueing model of database fragments on MAN ^ 42Directory database transaction rate ^ 49Access MAN database transaction rate 50Backbone MAN database transaction rate ^ 50MA database transaction rate ^ 51Total signalling on access MAN due to subscriber location and tracking ^ 52Figure 21^Total signalling on backbone MAN due to subscriber location and tracking . 53Figure 22 Ripple search — Expected database processing time for callee location —residents ^  54Figure 23^Ripple search — Expected database processing time for callee location —visitors from backbone ^  54Figure 24^Ripple search — Expected database processing time for callee location —visitors from MA ^  55Figure 25^Ripple search — Expected database processing time for callee location —visitors from outside MA^  55v iFigure 26^Ripple search — Expected database processing time for callee location . . . . 56Figure 27 Directory search — Expected database processing time for callee location —Amax = 0.6 ^  56Figure 28^Directory search — Expected database processing time for callee location —Equivalent database transaction capacities as ripple search ^ 57Figure 29^Ripple search — Std. dev. of database processing time for callee location —residents ^  57Figure 30^Ripple search — Std. dev. of database processing time for callee location —visitors from backbone ^  58Figure 31^Ripple search — Std. dev. of database processing time for callee location —visitors from MA ^  58Figure 32^Ripple search — Std. dev. of database processing time for callee location —visitors from remote MA ^  59Figure 33^Directory search — Std. dev. of database processing time for callee location— Amax = 0.6 ^  59Figure 34^Directory search — Std. dev. of database processing time for callee location— Equivalent database transaction capacities as ripple search ^ 60Figure 35^Centralized database transaction rate ^ 64Figure 36 Expected database processing time for callee location — Centralizedarchitecture ^  66Figure 37^Database hierarchy ^ 72viiList of TablesTable 1^Access MAN database transactions due to subscriber tracking ^ 35Table 2 Backbone MAN database transactions due to subscriber tracking^ 36Table 3^MA database transactions due to subscriber tracking ^ 36Table 4 Access MAN signalling traffic due to subscriber tracking 39Table 5^Backbone MAN signalling traffic due to subscriber tracking ^ 40Table 6 Assigned values of Pi to P4 for varying degrees of mobility 45Table 7^Assigned values of PA to PD for varying degrees of call localization^46Table 8 Transaction rate at access MAN level database due to subscriber locationupdate ^  48Table 9^Transaction rate at backbone MAN level database due to subscriber locationupdate ^  48Table 10^Transaction rate at MA level database due to subscriber location update .. 48Table 11 Centralized architecture database search sequence ^ 62Table 12^Database transactions due to subscriber tracking 63Table 13 Signalling traffic over access and backbone MANs due to subscribertracking ^  65Table 14^Ripple search database access sequence — residents of access MAN ^ 73Table 15 Ripple search database access sequence — visitors from backbone ^ 74Table 16^Ripple search database access sequence — visitors from MA ^ 75Table 17 Ripple search database access sequence — visitors from remote MA ^ 76Table 18^Directory search database query sequence — residents of access MAN . ^ 77Table 19 Directory search database query sequence — visitors from backbone MAN ^ 78Table 20^Directory search database query sequence — visitors from MA ^ 79Table 21 Directory search database query sequence — visitors from remote MA . . ^ 80Table 22^Calculation of signalling over access and backbone MANs for last entry ofTable 14 ^  87viiiAcknowledgementsI would like to express my sincere gratitude to my supervisor Dr. R.W. Donaldson for his supportand guidance during the course of this thesis, and to Dr. V.C.M. Leung for his helpful input.I would also like to express my appreciation to Dr. A.D. Malyan for providing time, effort, andmany helpful and interesting discussions during his stay here. I would like to thank Mr. B. Butemowskyfor his careful and only slightly facetious review of the thesis manuscript. And I would like to thankMr. D.P. Bouras, Mr. V.J.K. Wong, and Mr. W.K.W. Cheung for their frequent help.A special thank you is extended to my family for their support and encouragement throughout mygraduate studies.And last, but certainly not least, I would like to thank those "bastards" at St. Andrew's Hall (andyou know who you are!). What I learned and experienced there is just as significant as what I got outof my formal studies. Thanks for everything...ix1 Introduction1.1 Overview and MotivationOne of the major goals in the world of telecommunications is the realization of access to universallyavailable integrated broadband communications networks and services. The B-ISDN (BroadbandIntegrated Services Digital Network) concept is to provide one integrated network capable of providingall services, including data, voice, video imagery and graphics. The network will be capable of collectinginformation from many diverse sources and delivering it to designated destinations.One of the first mass services expected to be offered via B-ISDN is that of personal, portable wireless(tetherless) communications. Personal Communications Services (PCS) have received widespreadattention [1][2][3], and there is evidence to suggest that the potential market for PCS is very large.Wireless portable personal communications enables communications with people-on-the-move. The needfor PCS can be seen in the many service features provided to wireline telephone customers via currentnetwork intelligence; these services ease the impact of the tethered restrictions on people away fromtheir own wireline telephones (examples are call forwarding, call transfer, and the personal telephonenumber). The need for PCS can also be seen in the public's demand for wireless communications,which has consistently exceeded the capacity provided by available technology. Familiar examplesare the congestion of CB radio, interference problems with cordless telephones and the overloading ofcellular networks in densely populated areas.The ultimate goal of PCS is an integrated wireless network to support several different types ofwireless communications devices optimized for specific environments, as well as wireline devices forvarious forms of communication services. Such a network should allow a user to establish or receivecalls (for voice or data communication) anywhere within areas having reasonable population densities oralong transportation links interconnecting such areas. Eventually, service should be extended to suburbsand rural areas. A call connection should he maintained even if the user moves to another locationwhile the call is in progress.Mobility management refers to the network functions that locate and route information to a uservia a personal number. In current cellular networks, the mobility management functions required forcall setups and handoffs (the process of switching from a channel served by one radio cell to anotherchannel served by an adjacent cell during a call as the mobile unit moves from one cell to another)are performed by a mobile telephone switching office (MTSO) that controls all the calls in a largegeographical area. The rapidly growing demand for cellular telephone service strains the capacity of1MTSO's to control all of the calls in their service areas. Future systems, with smaller cells and ahigher volume of network control operations, will place considerably greater burdens on the processingcapabilities of cellular controllers. There is therefore a clear need for an intelligent network feature thatcan perform the mobility management functions in future high capacity systems.Since the current centralized wireless communication architectures may not be able to handle theanticipated demand for PCS, a distributed microcellular architecture based on the IEEE 802.6 MAN(Metropolitan Area Network) has been proposed [2][4115]. MANs will be an important part in theevolution towards B-ISDN. They will function initially as broadband gathering networks through theinterconnection of LANs. It is suggested that this single network architecture can also accommodatevarious other services including mobile pedestrian and vehicular communications.In this thesis, a hierarchical, distributed database architecture has been proposed which can beimplemented in the MAN based Personal Communications Network (PCN) described above to performthe mobility management functions required for PCS. The proposed database architecture is not restrictedto the 802.6 MAN architecture, but can also be used in other architectures, such as those based on ATMswitches. Some of the issues involved in mobility management have been examined, and a methodof analyzing and quantifying the performance of the architectures has been proposed. The ability ofthe proposed database architecture to perform the mobility management functions required for PCS isthen evaluated.1.2 Review of Others' WorkThe GSM and DECT systems are examples of existing wireless or mobile systems. The mobilitymanagement functions in these systems will be described briefly. This description is followed by adescription of methods proposed by others for mobility management.1.2.1 GSMThe system standard devised by the Groupe Speciale Mobile (GSM) describes a fully digital mobilecellular communications system that will be able to offer full roaming and compatibility across Europe[6]. The main components of the system are the Mobile Stations (MS), the Base Stations (BS), theMobile Services Switching Center (MSC), the Home Location Register (HLR) and the Visitor LocationRegister (VLR).The MSCs are the core of the network, providing the switching functionality to connect mobilesubscribers to other subscribers (mobile or fixed). The MSCs retrieve all data necessary to treat call2requests from three types of databases, the HLR, VLR, and Authentication Center (AC). In addition,the MSC updates the databases according to its latest information.The HLR stores the mobile subscriber related data, such as the mobile's access capabilities,authentication parameters, and subscriber services (static data), as well as the current location areaof the MS (dynamic data). Thus, on incoming calls, the HLR of the called mobile is accessed to locatethe subscriber and route the call to that location.The VLR records information pertaining to a mobile visiting its area. The data stored within theVLR "follows" the subscriber upon entry to another VLR area. The downloading of information fromHLR to VLR or from VLR to VLR is done to avoid accessing the HLR on every call.The procedure for location updating and downloading of data to the VLR when the mobile roamsbetween location areas of different MSCs involves the following sequence of operations:1. The MS detects through BS broadcast that transmission is better from a new BS, as compared tothe one currently in use.2. The MS sends a location update request through the new BS to the MSC.3. The MSC sends a location update message to the mobile's HLR giving its own identity as wellas that of the MS.4. Information from either the VLR of the MSC area that the mobile just left or from the HLR isdownloaded to the new VLR.5. The MS is acknowledged from the new base site.6. The previous VLR is directed to delete the MS from its contents.These steps are illustrated in Fig. 1.The Mobile Station Roaming Number (MSRN) is a number allocated by the VLR on a temporarybasis to an MS for the period that it remains in the area of a location register other than its HLR. TheMSRN is stored at the mobile's HLR, and enables incoming calls to be routed to the mobile station. Asubscriber in the network makes a call by dialling a fixed unique Directory Number (DN). The call isrouted to the nearest gateway MSC (GMSC). The GMSC uses the DN to locate the HLR of the calledsubscriber. From the HLR, the address (MSRN) of the MSC within whose area the MS is roamingcan be found. This MSC then interrogates the VLR to determine the exact location of the MS and theInternational Mobile Subscriber Identity (IMSI), a permanent identifier for a particular mobile terminal.Finally, the MSC instructs the base stations to page the MS using the IMSI.1.2.2 Ericsson CT-3 Wireless PBX — DECTThe DECT (Digital European Cordless Telecommunications) standard specifies the digital cordlessstandard for Europe. Ericsson's DCT 900 Cordless Subsystem (CSS) is an early implementation of theDECT technology [7].The CT-3 Telepoint system has a hierarchical system structure in which a Group Switching System(GSS) interconnects a number of Node Switching Systems (NSS), which in turn interconnect a numberof Cordless Subsystems (CSS).4Each CSS has a maximum capacity of 375 subscribers. In each CSS, a set of location numbersis assigned to the cordless subscribers which have this CSS as their home or default location, whileanother set of location numbers is reserved for roaming or visiting subscribers. The paging area on callsetup is the whole CSS area.Authentication information is stored in each CSS for the portables that have that CSS as theirhome CSS. In addition, a minicomputer connected to the NSS stores the information of all the cordlesssubscribers in the NSS and downloads the authentication information and encryption keys to the CSSsas needed.Whenever a portable leaves a CSS (or is switched on) it will scan all available channels on aregular basis and try to synchronize and lock to a new CSS. When it is locked, the portable will setup an initialization call to that CSS. Every CSS has the information on all the subscribers within theNSS available so that the portable and the CSS can exchange authentication information after whichthe roaming portable will be accepted by the CSS. The CSS will assign one of the location numbersreserved for visiting mobiles to the roaming mobile and activate the Remote Call Diversion Feature ofthe NSS to reroute all incoming calls to this particular CSS.1.2.3 DatacycleThe proposed Datacycle architecture implements a relational model for network services whichcan be expanded to support throughput of thousands of transactions per second [8]. The Datacyclearchitecture consists of a central subsystem called the "storage pump" which repeatedly broadcasts itsentire data content on a number of channels carried on high bandwidth fiber optic media. A broadcastof the entire database constitutes a cycle. Retrieval of data from the database takes place by loadingretrieval primitives into a number of hardware data filters, each of which monitors one of the broadcastchannels. The data filters are special purpose processors with an instruction set supporting relationaloperations, such as record retrieval based on specified conditions and calculation of aggregate valuessuch as sum, minimum and maximum. Together, the set of data filters has access to the entire databaseand can retrieve the requested records in a single cycle time. The access manager submits updaterequests to the update manager and observes the database on subsequent cycles to determine whetherthe proposed updates have, in fact, been applied to the database.There are a number of advantages to this architecture. Its centralized nature and the ability ofread transactions to take place in one cycle reduces the problem of concurrent access to shared data.The database can also be partitioned into segments to exploit the locality of reference that exists incalling patterns.5An architecture such as the Datacycle might be considered to be the ultimate goal for the intelligentbroadband network, since data for all services provided in the network could be integrated into oneapplication independent database providing uniform, application independent access to data. Suchintegration would allow data to be easily shared between services, and permit existing services tobe easily modified and new services to be easily introduced.A form of mobility management could be achieved as part of a Universal Number Translation service.In this proposed scheme, a national user database would be partitioned into segments representing eachof seven regions. Each partition would contain both a user directory for that region and an index, basedon the personal identifiers for each of the 240 million users in the other regions. This index wouldpoint to the region where the user subscribes to service and where the user's directory information iskept, and would be about 5 Gbytes in size. The index would be relatively static, changing only whena subscriber moved to another region. Calls within a region could be completed based on any attributecontained in the user directory. A call to a user who did not subscribe to the local region would requirethe use of the personal identification number to locate the subscription region while a second query tothe remote region's database would allow the call to be completed. The Datacycle proposal does nottake into account the mobility of subscribers; the effect of update traffic as subscribers move about ina microcell environment would have to be evaluated.1.2.4 Fujitsu/MurakamiMurakami and Katoh [9] have proposed an intelligent routing control system having the followingmajor features:1. All calls are routed by accessing databases hierarchically distributed throughout the network.2. Database locations are distributed physically in all switching nodes, but individual databases do notnecessarily correspond logically with switching systems in the same node.3. The translation of a logical subscriber number to the physical location of the subscriber takes placeat a database. Database queries are broadcast over the entire network.4. In individual databases, memory addresses correspond to physical addresses which are compared inparallel. This parallelism effectively speeds up address matching.Each database with a switching system manages the relationship between the physical addresses ofthe terminals or ports in the switching system and the corresponding logical number. The database isupdated when the state changes, i.e. when users register or reset their logical numbers. Upon receivinga call setup signal with a logical number whose corresponding physical address in the transport networkis not known, the switching system sends a signal requesting the routing control point (RCP) to searchits database for the physical address. If the requested physical address is found, the RCP returns thephysical address to the switching system. If not, the RCP sends a query with the called logical numberto other RCPs to find the requested physical address.The distributed routing control system is believed to be superior to the centralized system despitethe need for inter-RCP communication. The information volume for the address translation table overthe entire network is too large to store in a centralized database and the translation time in a centralizeddatabase increases beyond that of the distributed database.An RCP receiving a physical address request from a local switch and unable to find the physicaladdress must send physical address search requests to all other RCPs. Sending these requests one by onewould take too long, so they are sent all at once. For this reason, the question is distributed by a routingcontrol network. The routing control network has a two-level hierarchical topology, where there is anRCP and database at each toll switch and local switch. The local routing message switch broadcastsone question to 40 RCPs within one local area, under one toll switch. The Wide area Routing MessageSwitch (WRMS) broadcasts one question to 49 local areas. For a user wanting the search limited to alocal area, the LRMS can send the request to the other RCPs, but not to the WRMS.1.2.5 Fujioka/SakaiFujioka and Sakai [10] describe two network and database architectures for mobility management;one of these is hierarchical and one is distributed. In both cases, it is assumed that each subscriber hasa home network where the subscription to service occurs and that the subscriber's personal number willindicate the location of the subscriber's home network.In the distributed scheme, there are multiple, identical networks, each with their own centraldatabase. This scheme introduces the concepts of storing general location information pertaining toa roaming subscriber at the subscriber's home network, while detailed location information is stored incloser physical proximity to that subscriber. It is also suggested that a subset of a subscriber's personalprofile information be stored close to the roaming subscriber, either at the visited network's database,or in the form of a "smart" card carried by the subscriber.The hierarchical scheme proposes a network architecture consisting of a number of local networksinterconnected by transit networks, with each transit network having access to a global database.Databases are located at both the local and transit levels. The database at each local network keepsthe detailed location information for every subscriber located therein, while the central database in eachtransit network maintains information on where roaming subscribers are currently located. The globaldatabase maintains location information indicating in which transit network subscribers outside their7home transit network are currently located. Thus, if the called subscriber is located inside the homenetwork, no location information is stored at the transit or global databases. Conversely, if there is nolocation information for a particular subscriber at the global or transit databases, that subscriber may beassumed to be in the home transit network or home local network, respectively. It is suggested that theglobal database be located in a telecommunications satellite, or be distributed at several places on earthand accessed via a number of satellites in low orbit.1.3 Summary of Thesis ResearchThe research objective is to identify and examine issues pertaining to the use of distributed databasesto perform the mobility management functions of subscriber location and tracking and to analyse theperformance of these database architectures. Some of the key objectives that have been attained aresummarized below:1. A network architecture based on interconnection of IEEE 802.6 MANs has been adopted for theprovision of Personal Communications Services.2. A hierarchical, distributed database architecture that can be implemented in the network architecturedescribed above has been proposed. The proposed database architecture is also usable in othernetwork architectures, such as those based on ATM switching.3. Criteria on which to evaluate the performance of the database architecture have been suggested.Several methods of analysing the performance of the database architecture have been developed.4. The database structure and contents (logical and physical) have been defined. The protocolsnecessary to perform subscriber location and tracking have also been defined.5. Two database search algorithms for callee location at call setup have been proposed. The signallingtraffic and database transaction rates for each of these search algorithms as a function of subscribermobility and call localization have been calculated and compared.6. A means of estimating the database processing time (mean and standard deviation) for callee locationat call setup as a function of search type, call localization, subscriber mobility, and other parametershas been developed, and this method has been used to determine the database processing timestatistics.82 Network Support for Personal Communication ServicesThis chapter describes the intelligent network in relation to personal communications. A networkarchitecture based on interworked IEEE 802.6 MANs is also described.2.1 The Intelligent NetworkNetwork databases are increasingly involved in call processing for the realization of new networkservices. A major motivation has been the desire to permit more rapid creation and deployment of newnetwork services. Deploying service-specific data in central databases allows the data required for callprocessing to be accessed as necessary by any switching node in the network over a common channelsignalling network. This approach permits ubiquitous availability of a service with only minimal changesto local switches, and allows many aspects of the service to be defined and modified by alteration ofthe contents of the databases. Exchange carriers will thus be able to rapidly create new services inresponse to market opportunities, instead of having to implement them entirely within the switchingfabric. Ultimately, service creation, or at least service customization, can be extended to subscribers.The GSM system (described in section 1.2.1) is an example of an intelligent network in that routing andtreatment of calls is defined by information in a database which is separate from the switch controllingthe call. The database communicates with the switch over a data link.Separation of the specification, creation and control of telephony services from physical switchingnetworks is the key concept behind the Intelligent Network (IN) architecture. The IN architectureconsists of a switching system, a signalling network, a centralized database and an operations supportsystem (including a database administration system) which supports the database. The major elementsof the IN include the SSP (Service Switching Point), the STP (Signal Transfer Point), the SCP (ServiceControl Point), the IP (Intelligent Peripheral) and the SMS (Service Management System). These aredescribed in [11].PCS is generally accepted within the industry as a "lead IN service" [12], while mobility is widelyexpected to be one of the major driving forces for the evolution and deployment of INs [13]. It isessential that IN platforms provide network operators with the basic mechanics for mobility. However,consideration should be given to database access for customer features and services other than mobilesubscriber location before committing to system architectures based solely on the need to locate themoving subscriber.The data required to realize the overall set of network services should be viewed as a single integratedunit, which can be accessed by any application via a common data manipulation interface. Analysis will9be required to determine the signalling network capacities and database locations best suited for advancedservices. Such analysis should show the tradeoffs between data management, security, signalling networkcapacity, traffic network capacity, transmission quality, service functionality and service reliability.The architectural approaches to the Intelligent Network can vary from a highly centralized architec-ture with virtually all intelligence at a sole, centralized database, to an architecure with total distributionof functionality, down to the subscriber's terminal [14]. Centralized databases give the advantage ofcentralized OA&M (Operations, Administration and Maintenance), which simplifies the task of updatingand administrating the information. Centralization also enables the rapid and ubiquitous introductionof new services. Local databases, on the other hand, enable distribution of the intelligence closer tothe local exchanges. Such distribution is beneficial when the demand for the services is greater at thelocal level than at the regional or national level. One major problem that arises with this architecture isthe administration of the multiple local databases. Since the customer record information is duplicatedand or partitioned between the local or regional databases, the administration of customer records is animportant consideration in the management of IN services.2.2 Personal Communications Services (PCS) — Definition and RequirementsThe objective of Personal Communications Services (PCS) (also referred to as Universal PersonalTelecommunications (UPT)) is to enable the PCS subscriber, fixed or mobile, to establish and receivecalls across multiple networks at any user-network access point irrespective of geographic location.PCS also offers service portability, so that subscribers have location independent ability to originate andreceive calls using a common service profile.The PCS network identifies a user via a personal identification number (PIN). The PIN separatesusers' logical addresses from the physical addresses of terminals used to access the network. The PINcan specify a subscriber's home or default location, as it does in some of the networks described insection 1.2. Ideally, however, a subscriber should be able to retain the same PIN for life and thus thePIN should be independent of geographic location. This suggests the use of a flat (i.e. non hierarchical)numbering system. (Such a numbering scheme would also be more efficient in terms of capacity sincea flat PIN numbering scheme permits shorter PIN numbers, especially if they are used over large areas.)It is therefore the responsibility of the PCS network to manage the association between a user's PINand the current physical address.Two fundamental functions associated with mobility in the PCS network are subscriber location andtracking. Subscriber tracking refers to the means by which network databases are updated to reflect the10current locations of roaming subscribers, while subscriber location refers to the manner in which thedatabases are accessed and how the information contained in them is used to locate a called subscriber.Because of the existence of multiple-service providers, the PCS landscape will eventually be amosaic of many "islands of mobility", with access services being provided within each island by at leastone PCS vendor [12]. The challenge will be to provide users with a degree of uniformity across multipleislands toward the goal of a ubiquitous service. This challenge can be addressed by a PCS core networkthat has the role of integrating PCS usage across the mobility islands. The use of a common interworkingmodel and open interfaces will therefore be necessary. The overall service control architecture can beimplemented with the IN approach where a network element can communicate with other networkelements to influence and control call processing. PCS related functions which can be developed uponIN SCPs include authentication, call routing, handoff, charging, and operations and maintenance, aswell as location retrieval and update.The functions of location update and retrieval are also fundamental to other services that could beoffered within the IN framework. The provision of mobility management capabilities by IN elementsis an important step in the development of an infrastructure on which a wider variety of IN capabilitiescan be built.2.3 IEEE 802.6 Metropolitan Area Network — Concept and ArchitecturePCN architecture can be divided into three logical layers — the intelligent layer for controllingnetwork services, the transport layer for transmitting user information, and the access layer to providesubscriber personal communication access to the network. A transport layer architecture based on theIEEE 802.6 MAN has been proposed [4]. This architecture will be discussed, followed by a briefdescription of some aspects of the intelligent and access layer architectures.Broadband services will initially be supported on high speed LANs. Extension of broadbandservice areas will require high speed backbone networks to provide broadband services outside thelocal premises. A solution involving the use of the IEEE 802.6 Metropolitan Area Networks (MAN) forLAN interconnection would be most likely prior to implementation of the full Asynchronous TransferMode (ATM) network. ATM has been defined by the CCITT as the target transfer mode for B-ISDN.ATM is a packet oriented transfer mode using an asynchronous time division multiplexing technique.The next stage would involve MANs being interconnected via ATM switches to extend the broadbandservices to even larger areas. Since the cell format for the 802.6 MAN has a similar structure to thatof ATM, the interworking between the two networks is simplified and the transition to ATM will be11relatively easy and inexpensive. Eventually, LANs, MANs and ATM switches will be integrated intothe B-ISDN network [15].The ATM and 802.6 MAN cell format consists of a 5-byte header and 48 bytes of user information.The cells are multiplexed and switched based on their header content. Cells are generated and transmittedover a virtual circuit as necessary in response to the need for information transfer. ATM is inherentlyconnection-oriented; a virtual circuit number is associated with this connection and this number iscontained in the cell header. Since the connection is established at call setup using setup controlprocedures, no further routing information is required in the cell header. Bandwidth for the virtualcircuit can be varied dynamically, with variable bit rate services accommodated.The IEEE 802.6 MAN supports both voice and data traffic using a dual bus architecture, withthe two unidirectional buses supporting communications in opposite directions, allowing full duplexcommunications between any pair of nodes on the subnetwork. Each bus has a capacity of 155 Mbps.Cells (also called "slots") are generated by the node at the head of each bus. Other nodes along thebuses may write into the slots under the control of the access protocol, which is either queue arbitrated(QA) or pre-arbitrated (PA).Data transport is supported using both connection-oriented (PA) and connectionless (QA) slots.Distributed queueing is the media access control protocol that controls the access to the payload of QAslots on the DQDB bus. Scheduling is done by sending reservations "upstream" when a station wantsto transmit "downstream". Each node keeps an up/down counter running continuously, one for eachtransmission direction. This counting establishes a single ordered queue across the network for accessto each bus. With such queued access, priority levels can be established by operating a number ofqueues, one for each level. Within each level, packets will gain access as soon as capacity becomesavailable, but priority is always given to packets in higher level queues. Immediate access is given tohigh priority traffic without any delay due to queued lower priority traffic, making the highest prioritylevel suitable for signalling.Isochronous traffic (e.g. voice, video) will be supported through the use of pre-arbitrated (PA) slots.The allocation of a particular virtual circuit and bandwidth for an isochronous connection is establishedat call setup. The node at the head of each bus writes a Virtual Circuit Identifier (VCI) into each PA slotand ensures that PA slots for each VCI value are provided periodically at a rate that ensures sufficientbandwidth for isochronous service users. Bandwidth is determined by the rate at which slots are placedinto the transmission stream, and is not limited to certain discrete values. Bandwidth is allocated tousers at connection establishment time, or the connection request is denied if sufficient bandwidth is notavailable. This approach ensures a predictable overall performance of the network.122.4 The MAN-Based Personal Communications NetworkTo provide a ubiquitous service, future PCNs should be based upon two design criteria: (1) the useof wireline public network facilities should be maximized to realize efficient early service deployment,and (2) to accommodate the increased processing load as a result of the growing demand for wirelesscommunications, call control functions should be distributed in the network as opposed to the centralizedcontrol of the current networks [16]. Through the distribution of IN functions, information and decisionscan be concentrated at lower levels in the network, reducing the process congestion that could otherwiseoccur with centralized architectures with increased PCS demand.In current cellular mobile communications systems, capacity can be limited by either the radiochannel capacity, the data link capacity between the cell site and the MSC, or the switch capacity ofthe MSC. Current networks have tended to use separate fixed capacity links between BSs and switchingnodes, in effect using private high capacity circuits.Consider an integrated microcellular architecture using the IEEE 802.6 MAN, as illustrated in Fig.2. It is considered that a MAN-oriented microcellular system has those service capabilities needed tosupport the anticipated urban PCS demand [2] [17]. This design utilizes the MAN'S distributed switchingcapabilities to partition PCS call control and management functions, dynamically sharing the data linkcapacity with other services.The MAN distributes the processing necessary for wireless communications by interconnecting basestations (BSs) attached to MAN nodes. Various applications will be connected to the MAN via LANs,PBXs and BSs. Associated with the MAN is a bandwidth manager which allocates isochronous channelsfor voice/video, a trunk gateway (TGW) to interconnect the MAN with other public networks and a13database containing the PCS profile of each subscriber within the MAN coverage area. The TGWperforms the necessary format conversions between the public and wireless communication networks.Fixed and wireless terminals connected to LANs/PBXs will provide PCS coverage within buildings.To provide a contiguous coverage in public areas such as streets, shopping malls and railway stations,a grid of microcells will be necessary. Sets of BSs controlling these cells and coordinated by a BaseStation Controller (BSC) would then be interconnected to MANs via heterogeneous bridges. A MobileControl Center (MCC) on the MAN has the responsibility of managing the mobile aspects of calls.The function of the Signalling Termination (ST) on the MAN is to manage the fixed parts of all calls,irrespective of whether the call involves fixed or mobile subscribers.It is shown that, under certain conditions, the MAN could support the voice traffic for a coveragearea of 8 x 8 city blocks and adjacent microcells [5]. One sees that several MANs will be required toprovide coverage for an entire metropolitan area (MA). Initially, the relatively few MANs deployed inthe MA would be interconnected via point-to-point homogeneous bridges. As the deployed number ofMANs rises, however, network manageability would necessitate the use of a centralized higher-speedmultiport bridge — a B-ISDN switch at a Central Office (CO). Since the existing connection-orientedtelecommunication networks will continue to exist for many years, an Interworking Unit (IWU) at theCO should have the functionality to support both ATM and STM switching fabrics. Additionally, abackbone MAN could interconnect these access MANs using homogeneous bridges to form a cluster.An IWU would then connect the backbone MANs in an MA. (See Fig. 3.) If neighboring access MANswithin a cluster are also bridged, call setup and interMAN handoff would be simplified, and reliabilityagainst bridge failure would be enhanced. It can be shown that, under certain conditions, a backboneMAN could support approximately 9 access MANs [16].14The intelligent layer of the PCN consists of a Service Management System (SMS) used for servicedefinition and subscriber management, and Service Control Points (SCP) which contain the PCN servicelogic to control the network. The various databases necessary for PCS, including the Home LocationRegisters (HLR) and Visitor Location Registers (VLR), can be implemented within the SCPs.To provide a contiguous PCS independent of subscriber location, the access layer will interconnectto the transport layer using both wired and radio network interfaces.153 Distributed Database Architecture for Mobility Management Functions in PCS3.1 Distributed Database ArchitectureWe have proposed a distributed hierarchical database implementation for the MAN - orientedarchitecture described in section 2.4. In our proposed architecture, network intelligence and switchingcontrol are distributed at the various elements in an MA using three levels of control situated at: level1 — access MAN; level 2 — backbone MAN nodes; level 3 — centralized switch at the Central Office(CO). (See Fig. 4.) Each level tracks subscribers' movements at the level immediately below. Thus,access MAN level databases indicate the BSC control area in which each subscriber in the accessMAN is located, backbone MAN level databases indicate the access MAN where each subscriber in thebackbone MAN is located, and so forth.The replication of database contents at multiple nodes is one method of increasing the transactionprocessing capacity of a database system beyond that which can be achieved using a single processor.However, this approach can suffer from the processing overheads of the concurrency control messagesrequired to maintain consistency of the multiple copies of data. The expandability of such replicatedarchitectures can therefore be limited, because as the number of processing nodes increases, theconcurrency control overhead eventually saturates the processing resources in the system [81.16The hierarchical nature of the database design minimizes some of the pitfalls associated with thereplication of database contents. Since higher level databases indicate general subscriber location areaswhile lower level databases indicate more accurate subscriber locations, many of the updates made tolocal (i.e. lower level) databases as subscribers roam will not require a corresponding update to a higherlevel database to maintain consistency. The hierarchical structure also takes advantage of the localizednature of calls. Since it can be reasonably assumed that most calls are local as opposed to long distance,the called parties can most often be located by querying the local (i.e. lower level) databases. Only whenthe called party is located further away do higher level databases have to be queried. Thus, instead ofhaving one centralized database that is queried on every call attempt, the query traffic is divided amongthe different levels of databases, avoiding the traffic congestion associated with subscriber registrationand call setup inherent in a centralized database design.Another method of increasing the aggregate throughput of a database system is to partition(i.e. fragment) the database across processing nodes. The architecture of the MAN facilitates sucha distribution of database information among the various MAN nodes. In the proposed databasearchitecture, each access MAN node associated with a Base Station Controller (BSC) can have adatabase fragment. The broadcast nature of the MAN architecture allows database queries to be receivedsimultaneously by each fragment; taken together, these fragments act as a logically centralized databaseat the access MAN level but provide the capability for parallel processing to improve response time.Database fragmentation involves some disadvantages. Global access to data using an attributeother than the partition key is difficult. Processing overhead can be significant due to the exchange ofmessages and additional computation required to coordinate the different partitions. Administration ofthe partitions is necessary as processing demands, database contents and database distribution evolve [8J.However, these drawbacks are not expected to be significant for the particular implementation describedabove, for the following reasons. PCS will rarely require global access to subscriber data based on anattribute other than the partition (and primary) key which would in this case be the subscriber PINs; ininstances where such access is necessary, the use of another type of database known as the directorydatabase, described in section 3.2, could be considered. In addition, the broadcast nature of many typicalPCS database transactions combined with the broadcast nature of the MAN architecture facilitates thecoordination of the different fragments.The correspondence between information stored in the database fragment at a particular node andthe mobiles located in areas served by base stations connected to that node should be examined. Ifthe database fragment at a BSC contains only the addresses of subscribers within areas served by itsbase stations, then the node has, in effect, its "own" centralized database. The advantages of having17subscriber information available locally at the BSC would have to be weighed against the disadvantagesof having to update the database as subscribers moved from one BSC control area to another. The sizeof the database fragments is important; if there were relatively few fragments each containing relativelymany subscriber records, then having subscriber information available locally would be advantageous,since there would be a greater probability that the called party would be located at the same fragment asthe calling party. Signalling traffic to perform location retrieval could then be contained within the BSCcontrol area. Only if the subscriber were not located within the same fragment would the central MANdatabase have to be queried and signalling traffic sent out over the MAN. The larger database fragmentswould also imply that update traffic would be less frequent, since each fragment would cover a largergeographical area. As the number of fragments increases and the number of records in each decreases,the probability of being successful on the local access decreases until it becomes quicker not to accessthe local fragment at all and only access the central MAN database. As the fragments get smaller, thegeographical areas covered by each one decreases as well, making update traffic more frequent.The database fragments could be physically located at multiple MAN nodes, or they could all belocated at one node. In the latter case, the speed and signalling traffic advantages described above donot occur, since signalling traffic over the MAN would be necessary for all database transactions. Thisimplementation may still be advantageous, however, since some form of database management systemwill be required, and it might be cheaper and less complex to concentrate such a system at one noderather than having these functions available at each node.Database access could take place in the following way. The VCI having all bits set to 1 is thedefault value for the connectionless mode of service. All MAN nodes will recognize this VCI andprocess the slot accordingly. If the slot is determined to be one that the node is programmed to receive,it is buffered until the remaining slots are received and the IMPDU can be reassembled. Thus, databasescan be queried by transmitting an IMPDU, using the QA mode of access. The VCI value in the headerwould be the standard value for connectionless transfer, while the address would be one that would beshared and recognized by all MAN nodes as being designated for the database fragments. Each nodewith an associated database fragment would therefore recognize the address, reassemble the IMPDUand forward it to its database fragment.The way in which databases are actually partitioned is of interest. For example, the best performancewould likely be achieved in a configuration where each database fragment was accessed at approximatelythe same rate, since having some fragments accessed much more frequently than others could resultin bottlenecks developing at those access points. Partitioning of the database can be based on thefrequency of use of the individual fragments [18][191. Thus, by gathering statistics on how often18various subscribers are called, some performance improvement may be attained, although there wouldlikely be some constraints in the partitioning.Database information can also be distributed into a lower level of the hierarchy by storing infor-mation at the base station level. One possibility is to use a small high-speed RAM at the base stationsto store the identities of subscribers in its coverage area. In order to determine the exact location of aparticular subscriber, a paging message would be sent to all the base stations at a particular node, andthe base stations would in turn page all the mobiles in their coverage areas. The primary advantageof having subscriber locations stored at the base station level would be a reduction in traffic over theradio interface, since the base station itself could respond to the paging message from the node. Thisadvantage would need to be weighed against the resulting requirement that the mobiles transmit a signalupon every entry to a new cell area to enable RAM update.3.2 Database ContentsThe proposed database structure will be based on the relational data model [20]. Data andrelationships among data are logically represented as tables, where each table consists of a numberof columns with unique names. The databases contain two types of information: location informationindicates the geographical area in which a subscriber is located, while the service profile containsinformation specific to each subscriber.We first consider location information. Each PCS subscriber account has a particular access MANdesignated to be its home or default access MAN. The home access MAN is located within thesubscriber's home backbone MAN and home metropolitan area (MA). Each access MAN, backboneMAN and MA has a home and a visitor database. The home database contains information pertainingto subscribers having that database control area as a home area, while the visitor database containsinformation pertaining to subscribers visiting the database control area. Home and visitor databasesare therefore logically distinct but can be physically integrated into one database with entries for bothvisitors and residents. In this case, each entry might have a flag indicating whether it was a home entryand could therefore not be deleted, or whether it was a visitor entry and therefore had to be deletedupon departure of the visiting subscriber.When a subscriber is away from its home access MAN, its home access MAN database maintainsa pointer to the subscriber's general location. When a subscriber leaves its home backbone MAN,its home backbone MAN database points to the subscriber's home access MAN. Similarly, when asubscriber leaves its home MA, its home MA database points to its home backbone MAN. In this way,a subscriber can be located by examining its home MA, backbone or access MAN databases. When a19visiting subscriber leaves an access MAN, backbone MAN or MA, however, its entry is simply deletedfrom the corresponding visitor database. Figs. 5, 6, 7, and 8 indicate how the database contents changeto reflect a subscriber's position during roaming.Figure 5 Database contents when subscriber A is at home access MANFigure 6 Database contents when subscriber A visits an access MAN on home backbone MAN20The distribution of the databases permits detailed location information that requires frequent updatesto be stored relatively close to the subscriber as the subscriber roams, while databases located furtheraway need maintain only general location information requiring fewer updates as the subscriber roams.We can see that one can locate a subscriber by accessing any of its home or visitor databases.A particular database may not itself give the exact location of a subscriber, being instead a part of asequence of databases. The last database in the sequence gives the exact location of the subscriber.Note also that a subscriber's home databases are responsible for maintaining some indication of thesubscriber's current location at all times.21Service profile information is stored at the access MAN level only. Access MAN level databasesare analogous to the HLR and VLR databases in the GSM system. (The terms HLR and VLR cantherefore be used to refer to the home and visitor access MAN databases, respectively.) The serviceprofile is stored at this level because it must be easily and quickly accessed on every call. The serviceprofile can potentially be quite large; thus, placing it at the access MAN level distributes the serviceprofiles among various databases rather than having them all stored at a higher level. As the subscriberroams, its service profile should follow, as described in section 4.3.Information that could be contained in a typical service profile is listed below:1. HLR location: Full network address of subscriber's HLR2. Mobile terminal specifications: Terminal type, type of traffic (voice/data), data rate, presentterminal status, etc.3. Authentication and security info: Ciphering key, authentication key, key computation algorithmspecifications.4. Billing information5. Customized subscriber services related information: Call priority, call redirection, call screening,etc.6. Other service features (non user specific): Hold, ringback, display calling party, call waiting, etc.Once the callee's location area has been determined at call setup, the area is paged. In conventionalnetworks, the paging area is the control area of the subscriber profile database. An increase in thepaging area means an increase in paging traffic and a possible increase in the required radio capacityand/or mobile transmitter power. A decrease in the paging area, however, means an increase in locationupdate traffic as subscribers roam between the paging control areas. If the database fragment at the BSCmaintains a list of all subscribers currently in the BSC control area, then paging can be limited to theBSC control area which has the callee's PIN in its database, even though call setup requests are broadcastover the entire access MAN. It can be seen then that the paging area is significantly smaller than thesubscriber profile database area. Less radio capacity is required for each BSC control area compared tothe approach where the paging area corresponds to the subscriber profile database control area.One other type of database is the directory database, which maintains a mapping between everyPCS subscriber's PIN and home access MAN location. Thus, the location of any subscriber can beretrieved via lookup at the directory database. This database is very large but relatively static, since it isupdated only when subscribers change their home locations, and such updates do not necessarily have22to take place in real time. Therefore, multiple copies of the directory can be distributed throughout thenetwork to reduce congestion without update overhead becoming a significant problem.The directory database could be used for other purposes as well. For example, if subscribers' namesand residence or business addresses were included as part of the information in the directory database,then calls could be made by specifying a person's name, without having to know his or her PIN number.Another example is a database transaction which retrieves a range of names, addresses or PINs fromthe directory based on specific subscriber attributes.3.3 Database Consistency and ConcurrencyA database transaction consists of a sequence of database operations that transform a consistentdatabase state to another consistent database state. On distributed systems where a number of transactionscan execute concurrently, some care must be taken to ensure that concurrent transactions do not interferewith one another and leave the database in an inconsistent state. Inconsistencies can occur when two ormore transactions attempt to simultaneously modify the same data item.The SCPs and Database Administration system in the IN would have the responsibility of main-taining database consistency when subscriber profiles or locations change. In the distributed databasescheme proposed above, every data item corresponds to only one subscriber. A data item can only bemodified following a change in the state of the corresponding subscriber. Such a change occurs whenthe subscriber crosses a network boundary or when he/she initiates or terminates service (the subscriberturns the mobile on or off). Thus, no data item should be subject to concurrent modification (writeaccess) by more than one transaction simultaneously and it follows that database inconsistency cannotoccur due to concurrent execution of transactions (as long as each transaction is correct and carriedout to completion).Another source of database inconsistency can occur due to the propagation delay in updating allof the databases when the state of a subscriber changes. A number of examples are given below, andpossible solutions are suggested for each situation.a) Service may not be available to a mobile for a brief period of time after a mobile crosses intoa new base station control area, since the databases do not reflect its new position, and theservice profile may not yet be available on the new network. One solution is for the mobilenot to lock onto the new base station until it receives an ACK signal from the network. The ACKwould be sent only when the necessary databases have been updated. Once the mobile receives theACK, it will lock onto the base station in the new control area.23b) As databases in the new area are updated to reflect the mobile's entry, calls to the mobilefrom other subscribers in the new area may occur, which may lead to paging of the mobilebefore the mobile has locked onto the base station in the new area. A possible solution wouldbe for the databases in the new control area to not become active until they themselves are ACKed.Since the ACK signals propagate from the higher to the lower level databases until the mobile isreached, the databases could be set to become active only after they have forwarded the ACK. Acall from a subscriber in the new area could be "held" until the mobile actually entered.c) There will be a brief period of time between the time that the mobile locks onto the basestation in the new control area and the time that the mobile is completely deregistered fromthe previous control area. During this period, the databases in the previous control areawill incorrectly indicate the subscriber's presence. In this case, a call to the subscriber willfail. However, the window period in which this could occur is smaller than the window periodof a) above, since deletion of database records should be slightly faster than creation and copyingof database records. A search could "back up" to a higher level and attempt to again locate thesubscriber; since the mobile has crossed into an adjacent control area, the search would then besuccessful in most cases.The measures described above reduce the chances that calls will fail due to database inconsistency, butinconsistency will still occur for brief intervals. The length of time during which the databases areinconsistent should be small, however, and should result in only a very small performance degradationfrom the ideal case.3.4 Database Indexing MethodsTo minimize the delay associated with access of a given database record, some techniques thatallow fast random access to database records should be examined. Some index structures and hashingfunctions that could be of use are described below [20].An index structure is associated with a particular search key; for the purposes of PCS, the primarysearch key would be the subscriber's PIN number, and thus the primary index would be based on thesubscriber PIN numbers. The B+ tree file structure is an index structure that is useful for databases inwhich frequent insertions and deletions occur. A B+ tree index takes the form of a balanced tree in whichevery path from the root of the tree to a leaf of the tree is of the same length. In processing a query, apath is traversed in the tree from the root to some leaf node. If there are a total of K search key values inthe database, the path is no longer than log nr2K, where n is an integer specifying the maximum numberof children a node can have. Insertion and deletion of records in the database requires corresponding24modifications to the index structure as well. Some relatively complex operations are required to modifya B+ tree when a record is inserted or deleted, but it can be shown that the number of operations neededfor a worst case insertion or deletion is also proportional to the logarithm of the number of search keys.Hashing techniques eliminate the need to access an index structure in order to locate data. Theindex is partitioned among a number of buckets; the address of the bucket containing a pointer to thedesired data item is obtained directly by computing a function on the search-key value of the desiredrecord. A good hash function will ensure that, on average, records are distributed uniformly among thebuckets; in this case, the average-case lookup time is a (small) constant and independent of the number ofsearch keys. A worst-case scenario, however, would be one where a hash function maps all search-keyvalues to the same bucket, in which case the entire index is kept in the same bucket, and lookup timeis proportional to the number of search keys. Insertion and deletion are achieved easily; the appropriatebucket from which to insert or delete is found by computing the hash function on the search value.Average and worst case insertion and deletion times are similar to average and worst case lookup times.For the purposes of PCS, the use of hashing techniques has numerous advantages, includingsimplicity and speed of lookup and modification. The only significant advantage of an index overa hash structure is that the worst case lookup time for an index is proportional to the log of the numbersearch key values, while for a hash structure the lookup time is proportional to the number of searchkey values. If a completely flat numbering scheme for subscriber PINs is used, however, a worst casescenario is very unlikely.254 Subscriber Location and TrackingThere are 3 basic call setup phases: (1) Request setup — identify callee and class of service; (2)locate callee; and (3) establish virtual circuits along route between caller and callee. The caller firstspecifies the PIN of the called PCN subscriber. The ST serving the caller must ascertain that the supplieddirectory number is a PIN and determine the callee's location by initiating a database search. Once theaddress of the callee has been determined, the call request is then routed to the callee's current VLR,this being under the control of a MCC. The callee is then paged using the Temporary Mobile SubscriberIdentity (TMSI) supplied by the MCC. When the callee responds, the MCC then initiates authenticationprocedures. If this is successful, the MCC orders the controlling BSC to set up a radio channel andnotifies the CO serving the callee which in turn establishes a virtual circuit between the two parties.The database search of phase 2 can be undertaken in a number of ways. Two search methods, theripple search and the directory search, are described in sections 4.1 and 4.2 below. It is also essentialto track subscriber location to enable calls to be established and continued during and after crossings ofcoverage area boundaries. Sections 4.3, 4.4 and 4.5 address this issue.4.1 Ripple SearchDuring call setup, the calling party may have the option of instructing the network where the searchfor the callee is to begin. In the absence of any such instructions the databases are searched in thesequence shown below:1. Caller's local access MAN database.2. Caller's local backbone MAN database.3. Caller's local MA database.4. Caller's home access MAN database, if this is different from caller's local one.5. Caller's home backbone MAN database, if this is different from caller's local one.6. Caller's home MA database, if this is different from caller's local one.7. Directory database.This sequence is illustrated in Fig. 9 below. A timeout period is required to allow each database levelto respond before the search continues at the next level.26The rationale behind this search sequence is that the callee is most likely to be located either in thevicinity of the caller's current location or the caller's home location; thus, those databases associatedwith either location are searched first. Only if the callee cannot be located at any of those databasesis the directory database searched. Thus, the search can be said to ripple upward from low level tohigh level databases.4.2 Directory SearchThis method differs from the previous one in that the directory database is accessed immediately toobtain the address of the callee's home access MAN and, from that, the callee's current location. Thus,the directory search begins immediately at the highest level database. Note that by beginning the searchat the directory database, timeout periods are not required. Note also that this search algorithm does notinvolve any transactions with database fragments at the access MAN level.Since the directory database is always accessed first and the search always begins with the directorydatabase followed by the callee's home access MAN database, the sequence of database accesses isindependent of the location of the caller relative to the location of the callee.274.3 Subscriber Tracking Methods Using DatabasesBecause the PCN cannot assume a fixed relationship between call destination and called subscriber,subscriber locations must be updated as the subscriber roams. This updating can be achieved with thedatabase architecture described in section 3.1.An active MT could monitor its location in the network by monitoring the broadcast identity of itspresent network Base Station (BS). Thus, each BS could periodically transmit its address, while MTsscan the received signals and identify the BS sending the strongest signal. As an MT leaves one BScontrol area and enters another, it would identify the new BS and make a request to register in its controlarea. The MT should also store the identity of the most recent base station used for communication inRAM, for reasons to be explained below.Access MAN nodal addresses should be based on the hierarchical E.164 standard [21], wheredifferent portions of the address indicate the access MAN, backbone MAN and MA associated witheach BS. BS identities are an extension of the access MAN node addresses to which they are attached.Comparison of the new BS identity with the previous BS identity would permit the determination of thetype of network boundary (i.e. cell, access MAN node, access MAN, backbone MAN, or MA) crossedby the MT as it entered a new BS control area.Service profiles are located at the access MAN level. This location strategy permits quick andeasy access for calls originating at the subscriber (for example speed or priority dialing) as well asterminating at the subscriber (for example call screening). In either case, the service profile must beaccessed quickly and thus should follow as the subscriber roams. However, a large profile and a fastmoving subscriber would cause many profile transfers, occupying a significant portion of the networkcapacity even though the subscriber neither made nor received any calls. One possible solution is tomove or copy the service profile only if the subscriber crossed an access MAN or higher level boundary.If a mobile crossed a BSC level boundary, the mobile's identity would be registered at the databasefragment at that BSC area (thereby updating the access MAN level database), but the service profilewould not necessarily be copied. Instead, the service profile would be copied only if the subscribermade or received a call. This constraint could prevent unnecessary transfers of the service profile. If thesubscriber entered another BSC control area and remained there, the first call made or received wouldincur some delay as the profile was transferred, but any subsequent originating or received calls wouldnot incur any delay due to profile transfer.4.4 Signalling for Different Types of Boundary CrossingThe signalling required for subscriber location update can now be examined for each of the possible28cases of boundary crossing. There are essentially four phases to consider: mobile registration at thenew location, mobile deregistration at the previous location, service profile transfer to the new locationif necessary, and acknowledgement of the registering mobile. For an MT that is switched on, the sameprocedure can be used with the deregistration phase omitted. For an MT that is switched off, only thederegistration phase is necessary.The different cases of boundary crossing are as follows:I. BSC area boundary crossing within an access MAN2. Access MAN boundary crossing in home backbone3. Access MAN boundary crossing in visited backbone4. Backbone MAN boundary crossing in home MA5. Backbone MAN boundary crossing in visited MA6. MA boundary crossingNote that a higher level boundary crossing implies boundary crossings at each of the lower levels aswell. For example, when a subscriber crosses a backbone MAN level boundary, it also crosses accessMAN and BSC area boundaries.The signalling diagrams for cases 1, 2, 4 and 6 above are shown in Figs. 10, 11, 12 and 13.(The signalling diagrams for cases 3 and 5 are similar to those of cases 2 and 4, but without the HLRupdate.) From the signalling diagrams, an estimate of the amount of data transfer required for each typeof boundary crossing can be determined. As an illustration, consider the signalling diagram in Fig. 11for case 3 above. The steps involved are described below:1. The mobile has detected a stronger signal from BSN (new base station) compared to BSp (previousbase station) and so requests to be registered in the control area of BSN. The mobile transmits aregistration request signalling packet containing its ID and the address of BSp.2. BSN receives the signalling packet from the mobile and adds its own address to the mobile IDand BSp address. It forwards this information to the database fragment associated with BSCN, thenew BSC control area.3. The MT is then registered at the backbone database fragment associated with the current accessMAN and deregistered from the database fragment associated with the previous access MAN.4. Similarly, the mobile is deregistered from the previous access MAN. If the previous access MANwas the subscriber's home access MAN, the database will be set to point to the subscriber's currentaccess MAN. Otherwise, the subscriber's record will be deleted.295. If the new access MAN is not the subscriber's home access MAN, the subscriber's service profileis copied into the current one. The service profile can be copied either from the subscriber's homeaccess MAN or from the previously visited access MAN.6. The address of the subscriber's home access MAN will be available from the service profile. Usingthis address the subscriber's HLR is updated to point to the current access MAN. This step isnecessary only if the access MAN boundary crossing took place in the subscriber's home backboneand if the subscriber neither entered nor left its home access MAN.7. The mobile is acknowledged. Each of the registration, deregistration, and HLR update phasesare acknowledged. Once the database fragment management function at BSCN has received theacknowledgements, the MT is acknowledged. The MT can then lock onto the new base station.30Figure 13 Signalling diagram for MA boundary crossing4.5 Determination of Area Boundary Crossing RatesPrevious reports [4] [22] have assumed a multiple level network hierarchy. It has been shown thatan access MAN could support subscriber traffic in an 8-by-8 block urban area. There are two microcellsin each block, each microcell consisting of two pavements of 300m length. Thus, the access MAN area31can be represented as shown in Fig. 14. We can consider the subscriber traffic in the microcells at theedge of the access MAN area shown in Fig. 14 in order to calculate the rate at which subscribers crossthe access MAN boundary, which will in turn yield the subscriber location update traffic at the accessMAN database level. The assumptions made in [4] regarding microcell dimensions, subscriber densityand subscriber movement in the microcells will also be used in the calculations.325 Database Architecture Performance AnalysisSubscriber location methods can be compared in terms of database transaction rates, signallingtraffic over the access MAN and backbone MAN, and expected delay and delay variance due tosubscriber location at call setup. The database transaction rate criterion permits comparison of thenumber of transaction requests received at each database due to the mobility management functions ofsubscriber location and tracking. The signalling traffic criterion permits comparison of the amount ofsignalling traffic that is generated on the access MANs and backbone MANs due to the network mobilitymanagement functions. The mean and standard deviation database processing time due to subscriberlocation at call setup is a function of the database transaction rate and signalling traffic, and is onecomponent of the overall delay that a subscriber attempting to place a call could expect before the callis established.5.1 Parameters for Performance AnalysisSubscriber location methods are affected by a number of parameters, and can be compared byexamining their performance as these parameters vary.There are three parameters that have been considered:1. The relationship of the subscriber (caller or callee) with respect to the access MAN in whichthe subscriber is located. There are four possibilities: the subscriber is located in its homeaccess MAN, outside its home access MAN but in its home backbone MAN, outside its homebackbone MAN but within its home MA, or outside its home MA. The variables P1, P2, P3, andP4, respectively, represent the relative proportion of time a subscriber spends in each of the abovestates, and reflect the degree of subscriber mobility.2. The location of the callee's home access MAN with respect to the one in which the caller islocated. There are four possibilities. The first possibility is that the caller is located in the callee'shome access MAN area. Otherwise, the caller and callee's home access MAN can be locatedrelative to one another in one of the following three ways:a. caller and callee's home access MAN located on same backbone MANb. caller and callee's home access MAN located on different backbone MANs in same MAc. caller and callee's home access MAN located in different MAs33The variables PA, P13, Pc, and PD, respectively, can be used to represent the relative proportion ofcalls that fit each of the above four categories, and reflect the degree of call localization.3. The actual location of the callee relative to the caller. As an example, consider caller A andcallee B, where both A and B are outside their respective home MAs. There is a possibility thatA and B can be visiting the same access MAN. The analysis in [22] assumed that the probabilityof such an event occurring was negligible. If we do not make this assumption, we can account forthese events by defining the following variables:a = P(callee at same access MAN node (BSC area) as caller I callee on same access MANas caller)13 = P(callee at same access MAN as caller I callee on same backbone as caller)= P(callee at same backbone as caller I callee on same MA as caller)= P(callee at same MA as caller I callee outside its home MA)where P(AIB) represents the conditional probability of event A given event B.Subscriber mobility can be viewed as a measure of how much time a subscriber spends in different partsof the network. A high degree of mobility implies frequent roaming outside of home areas. The degreeof call localization is determined by the proximity of the caller to the callee's home location. Calllocalization is a measure of a caller's calling pattern or range (i.e. what destinations a subscriber calls asa function of and relative to the subscriber's current location). A high degree of call localization impliesthat a large proportion of calls are directed to areas in close proximity to the caller's present location.5.2 Methods Used to Determine Database Transaction Rate5.2.1 Database Transaction Rate Due to Subscriber TrackingRepresentative diagrams showing the signalling required for an access MAN boundary crossingappear in section 4.4. These signalling diagrams indicate the data traffic and database transactionsrequired for each type of boundary crossing. This information is summarized in Tables 1, 2, and 3.The types of transactions are defined below:1. registration: the subscriber's location is registered at the database(s) associated with a particularregion as it enters that region;2. deregistration: the subscriber's record is removed from the database(s) associated with a particularregion as it leaves that region;3. update: the contents of the database(s) are updated to reflect the subscriber's new location;344. service profile (SP) write: when a subscriber enters an access MAN other than its home accessMAN, its service profile is copied into the access MAN database (VLR); and5. HLR update: the subscriber's HLR is updated when the subscriber crosses an access MANboundary within its home backbone, a backbone MAN boundary within its home MA, or an MAboundary outside its home MA.The variables Pi, P2, P3 and P4 are defined in section 5.1.Consider Table 1, which lists the transactions occurring at the access MAN databases for differenttypes of boundary crossing. When a subscriber crosses a backbone MAN boundary, up to four actionsmust take place at the new and previous access MAN databases: registration at the new access MANdatabase, copying of the service profile into the new access database, deregistration from the previousaccess MAN database, and update of the subscriber's HLR. (Recall that a backbone MAN boundarycrossing implies an access MAN boundary crossing.)Type of boundary crossing Number ofdatabasetransactionsType of transactionBSC area 1 updateaccess MAN1 registration1 deregistration2(1-P1) SP writeP1+P2 HLR updatebackbone MAN1 registration1 deregistration2(1-P1) SP write1-P4 HLR updateMA1 registration1 deregistration2(1-P1) SP writeP4 HLR updateTable 1 Access MAN database transactions due to subscriber tracking35Type of boundary crossing Number ofdatabasetransactionsType of transactionBSC area N/A N/Aaccess MAN 1 updatebackbone MAN 1 registration1 deregistrationMA 1 registration1 deregistrationTable 2 Backbone MAN database transactions due to subscriber trackingType of boundary crossing Number ofdatabasetransactionsType of transactionBSC area N/A N/Aaccess MAN N/A N/Abackbone MAN 1 updateMA 1 registration1 deregistrationTable 3 MA database transactions due to subscriber trackingEvery boundary crossing involves one location registration and one location deregistration. Aservice profile write is necessary if the new access MAN is not the subscriber's home access MAN.If P1 represents the proportion of time a subscriber spends in its home access MAN, then 1—P1 is theapproximate amount of time a subscriber spends outside its home access MAN, and is therefore also anapproximation for the proportion of boundary crossings that will require a service profile write. Notealso that two transactions (one read and one write) are required for a service profile write since theservice profile is copied from one database to another, which accounts for the coefficient of 2 in frontof the 1—P1 terms. An HLR update is necessary if the backbone MAN boundary crossing takes placewithin the subscriber's home MA. Since the proportion of time a subscriber spends in its home MAis 1—P4 (=Pi+P2+P3) then the proportion of backbone MAN boundary crossings that require an HLRupdate can be approximated by 1—P4. The other expressions can be derived using similar reasoning.365.2.2 Database Transaction Rate due to Subscriber LocationThe transaction rate at the location databases due to subscriber tracking can be calculated as shownin section 5.2.1 above. We now consider the transaction rate at the databases due to subscriber locationat call setup. This traffic is a function of the search algorithm. In chapter 4, two search algorithms (theripple search and the directory search) were described.The sequence of databases that are accessed for each possible combination of call localization,subscriber mobility and actual location parameter (as defined in section 5.1) are tabulated in AppendixA for the ripple and directory search methods. There are four tables in each case, one for each categoryof caller. The databases and their locations relative to the access MAN on which the caller is currentlylocated are listed along the top of each table. Each parameter combination is listed along the leftmostcolumn of the tables. The databases and the access order for a particular combination are listed to theright of that combination, thus associating a database search sequence with each row. The last databasein the sequence identifies the most accurately known position of the callee.From these tables, expressions can be derived to determine the transaction rate at each database.Each row of the tables can be assigned a probability value, representing the proportion of time thatthe database sequence represented by that row will occur relative to the other combinations, based onassumed parameter values. By summing the probabilities associated with a particular column in a tableand multiplying by the call initiation rate for the category of subscriber represented by the table, thetransaction rate for the database associated with that column can be obtained. By summing correspondingcolumns in each table, the transaction rate for each database that results from subscriber location by allsubscribers in an access MAN can be determined.It has been assumed that subscribers are uniformly distributed, with each one having a similar callingand mobility pattern. Therefore, it can also be assumed that for every access of a non-local databasemade by a local subscriber, there is a corresponding access of the local database by some non-localsubscriber located elsewhere in the network, so that all databases at a given level (i.e. access MAN,backbone MAN or MA) would have transaction rates that are equivalent, on average. By this reasoning,the transaction rates at any database level in the network can be determined by considering the databasetransactions that are due to the subscribers of any one access MAN.Refer to Appendix B and Appendix C for the expressions derived from the tables of AppendixA. These expressions are used to calculate the database transaction rate for the ripple and directorysearches, respectively.375.3 Methods Used to Determine Signalling Traffic5.3.1 Signalling Traffic Due to Subscriber TrackingThe signalling due to subscriber tracking can be determined by examination of the signallingdiagrams of section 4.4. Each arrow in the diagrams represents the transfer of information from onenetwork component to another. The media over which the transfers occur are as shown below:• MT^BS: air interface.• BS H BSC/access MAN node: heterogeneous bridge• BSC backbone database fragment / MAN node: access MAN• backbone database fragment / MAN node MA database / CO: backbone MAN• MA database / CO MA database / CO: CO to CO link• BSCp BSCN: access MAN, access MAN and backbone MAN, or access MAN, backbone MANand CO to CO link.• BSCN^HLR: access MAN, or access MAN and backbone MAN, or access MAN, backboneMAN and CO to CO link.Most data transfers are assumed to require 2 QA slots on a MAN, with the exception of service profiletransfers which require 5 QA slots, and acknowledgements which require 1 slot. The data required foreach signalling operation, the number of data transfers and QA slots on the MANs required for eachtype of boundary crossing are summarized in Tables 4 and 5. The number of data transfers requiredfor each operation was calculated using reasoning similar to that used in section 5.2.1. Some operations(i.e. SP transfer, HLR update and ack.) require signalling capacity over the local and remote access orbackbone MANs. Therefore, a coefficient of 2 is placed before terms corresponding to these operations.The expressions thus derived are shown in Appendix F. The boundary crossing rates for each boundarytype can be determined as described in section 4.5, and therefore the overall signalling traffic over theaccess and backbone MANs due to subscriber tracking can be calculated.38Type of boundarycrossingNumber ofdata transfersSignalling operation Number ofQA slotsrequiredBSC area (see Fig.10)1 deregister MT 21 ack. 1access MAN (seeFig. 11)1 update loc. 21 deregister MT 21 ack. 12(1-P1) SP transfer 52(P1+P2) HLR update 22(P1+P2) ack. 1backbone MAN (seeFig. 12)1 register MT req 21 deregister MT 21 ack. 12(1-P1) SP transfer 52(1-P4) HLR update 22(1-P4) ack. 11 register MT req 21 deregister MT 21 ack. 1Fig. 13)MA (see2(1-P1) SP transfer 52P4 HLR update 22P4 ack. 1Table 4 Access MAN signalling traffic due to subscriber tracking39Type of boundarycrossingNumber ofdata transfersSignalling operation Number ofQA slotsrequiredBSC area N/A N/A N/Aaccess MAN (seeFig. 11)1 deregister MT 21-P1 SP transfer 5P1+P2 HLR update 2Pi+Pz ack. 1backbone MAN(see Fig. 12)1 update loc. 21 deregister MT 21 ack. 12(1-P1) SP transfer 52(1-P4) HLR update 22(1-P4) ack. 1MA (see Fig. 13)1 register MT 21 deregister MT 21 ack. 12(1-P1) SP transfer 52P4 HLR update 22P4 ack. 1Table 5 Backbone MAN signalling traffic due to subscriber tracking5.3.2 Signalling traffic due to subscriber locationBoth the ripple and directory search algorithms involve transactions with sequences of databases.Depending on the outcome of the search, a database query is either forwarded to another database orthe search terminates. It can be assumed that queries are buffered while databases are searched. Thesignalling traffic due to subscriber location is calculated by examining the sequence of database accessesas shown in the tables of Appendix A and determining the media over which data transfer must takeplace as queries are forwarded from one database to another. It is also assumed that the only way aquery can be routed from one access MAN to another is via the backbone MAN, and that the onlyway a query can be routed from one backbone MAN to another is via a CO. In reality, adjacent accessand backbone MANs can be bridged, and these bridges would carry some of the traffic load away fromthe backbone MANs and CO.40The signalling traffic due to subscriber location is a function of subscriber mobility and calllocalization. The tables of Appendix A can be used to derive equations that yield the signalling trafficdue to subscriber location at the access and backbone MANs. The method is similar to that describedin section 5.2.2; in this case, however, the sequence of media used when data is transferred betweendatabases is considered. As an illustration, consider the sequence of databases shown in Fig. 9. For aquery packet to be forwarded from database 1 (at the access MAN level) to database 2 (at the backboneMAN level), data will be transferred over the both the access and backbone MANs, while a query packetbeing forwarded from database 3 (at the MA level) to database 4 (at the access MAN level), data willhave to be transferred over a CO to CO link, the backbone MAN and the access MAN. The table-basedequations used to calculate the signalling traffic are shown in Appendices D and E.5.4 Methods Used to Determine Callee Location Time at Call Setup5.4.1 Sources of DelayThe time required to locate a called party is one component of the total call setup delay. The delaysthat occur during this phase of call setup can be classified as follows:1. Delays independent of mobile movement, traffic and location. These include propagation delaysover the networks and interfaces, signalling and processing delays at various network elements,database response timeout periods, etc.2. Delays dependent on mobile movement, traffic and location. These include database access andprocessing delays, queueing and transmission delays for packet transmission over the MANs, routingdelays, etc.This report will be primarily concerned with the second category of delays. A queueing model forthe database architecture will be described, and the resultant queueing and processing delays will bedetermined.5.4.2 Modelling of MAN Database ArchitectureAs described in section 3.1, each access MAN node associated with a base station controller (BSC)has a database fragment. This architecture can be modelled as shown in Fig. 15, where each fragmentcan be modelled as a server with an associated queue. A call setup request packet received from amobile is transmitted via the base station and base station controller to the access MAN node where itis processed. In order to access the access MAN level database, the request is broadcast over the accessMAN and received, queued and processed simultaneously at each fragment.41Figure 15 Queueing model of database fragments on MANIf we make the assumption that PCS subscribers are distributed uniformly throughout the accessMAN area, then it can be assumed that there are an equal number of subscribers in each BSC area. Wecan further assume that the average traffic generated by each subscriber is the same (i.e. on average,each subscriber initiates and receives the same number of calls per unit time and roams from one pagingarea to another at about the same rate). Since access MAN database transaction requests are broadcastover the MAN and all fragments on the MAN process the transaction requests in parallel, the multipleservers and queues on the MAN behave identically and the behaviour of one queue can be examined topredict the performance of the entire access MAN level database. Thus, the access MAN level databasecan be treated as a single server queue.Traffic arriving at the database consists of signalling packets resulting from location request queriesdue to callee location at call setup and location update resulting from subscriber tracking. We assumethat these are both Poisson processes which can be combined into an overall Poisson arrival rate at thedatabase. (The modelling of call setups (or initiations) as a Poisson process is similar to the approachtaken in [9] while the modelling of location updates (or registrations) for subscriber tracking as aPoisson process is similar to the approach taken in [23].)Modelling of the service process at the database must account for the average time needed to servicea transaction. There are different types of transactions:1. transactions involving read operations: database search, subscriber profile reference, etc.2. transactions requiring read and write operations: subscriber registration or deregistration, serviceprofile copy or transfer, location update, etc.Consider transactions involving read operations. The transaction time is the sum of the search time(the time required to find a particular data item) and the read time. The read time is a function of the42record length. If subscriber records are small compared to the size of the database, then the read timeis small and constant compared to the search time.The access time is a function of the type of indexing used. Two common indexing methods are theB+-tree indices, and hash functions, as described in section 3.4. For a B ±-tree index structure, the worstcase access, insertion, and deletion times are proportional to the logarithm of the number of search keyvalues. If a hash function is used, access, insertion and deletion times result in an average case lookuptime that is a (small) constant, independent of the number of search keys in the file.The transaction times for transactions involving write operations involve similar considerations. Thewrite time can also vary depending on the particular transaction; subscriber registration or deregistration,for example, involves writing or deleting a location pointer, while a subscriber profile transfer couldrequire the writing of a hundred bytes of data.Because of the variability in the service time, the analysis of the queueing model will specify thelevel of performance required by the database assuming that the service rate of the transactions is aPoisson process; that is, though the database transaction times may not be exponentially distributed, theanalysis will yield an equivalent performance measure which will give some indication as to the actuallevel of performance that would be required by the databases.The backbone MAN level database has a similar structure to the access MAN database and can bemodelled in a similar way. The MA level database is not fragmented, and can also be modelled as asingle queue and single server.5.4.3 Database Processing Delay Calculation MethodHaving determined the arrival traffic to each database level, the database processing time at eachdatabase level can be calculated by using some of the properites of the M/M/1 queue. The systemwaiting time pdf for the M/M/1 queue is given by [24]s(y) = - p)e-A(1-p)yThus, the system waiting time is exponentially distributed with parameter p,(1-p). The mean and varianceof the delay encountered by requests at each database can be obtained from the mean and variance ofthe system waiting time. The mean database processing time Ta, is thereforeTay —pt(1 - 19)while the variance Tvar isTvar =tt2 ( 1^p) 2—1143where A is the total number of database transaction requests per second arriving at the database dueto subscriber tracking and call setup, it is the number of database requests served per second, and theutilization p = AIR. (Note that the mean and standard deviation of an exponentially distributed randomvariable are identical.) The values for A for each database level can be calculated as shown in section5.2. Since the mean processing time grows exponentially as p approaches unity, and since A is greatestwhen the call localization is at a minimum and the mobility is at a maximum, the service rate it can bechosen such that the maximum utilization p at each database will be a chosen value between 0 and 1.Once the required service rates at each database are determined for a particular maximum value of p,the overall database processing time (mean and standard deviation) can be calculated.Consider the tables of Appendix A. Each row of the table represents a sequence of database accessesand an associated probability. Consider a particular row k which has an associated probability Pk. Eachdatabase in the sequence has an associated processing time. The overall expected processing time E[T]can be determined using the equationE[T] = E E[TkiPkk=1where E[Tk] is the sum of the expected processing times for the databases in the sequence of row k andN is the number of rows in the table. Repeating this process for each table will yield the overall expectedprocessing times for the four categories of subscribers (residents, visitors from backbone, visitors fromMA, visitors from outside MA) on a particular access MAN.To determine the overall database processing time variance, we first determine the mean squarevalue of the processing time E[Tk2] associated with the database sequence in each row. The E[Tk 2]value of a particular row k can be determined using the equationE[n] = V[Td+ (E[Tk])2where V[Tk] is determined by summing the processing time variances of the databases in the sequenceof row k. The overall mean square value E[T 2] can then be determined using the relationE[T2 ] =^E [n] Pkk=1(See Appendix G for a derivation of the above equation.) The overall variance can then be determinedusingV[1]= E[T2 ] — (E[T]) 2The standard deviation can then be obtained by taking the square root of V[T]. Repeating this processfor each table will yield the overall database processing time standard deviation for the four categoriesof subscribers on a particular access MAN.446 Results of Analysis6.1 Parameter Values ChosenA number of representative values for the call localization and subscriber mobility parametersdescribed in section 5.1 have been chosen. These are listed in Tables 6 and 7.The four degrees of subscriber mobility range from low (1), where subscribers are most often foundin their home access MAN, and never roam outside their home MA, to high (4), where subscribers areas likely to roam outside their home MA as within their home access MAN.The three degrees of call localization also range from low to high. A high degree of call localizationimplies that a high proportion of a subscriber's calls are to other subscribers whose home locations arein close proximity to the caller's current location, while a low degree of call localization implies thatthe subscriber's calls are distributed more randomly. It can also be assumed that some portion of asubscriber's calls will be intended for subscribers that share the caller's home location. This assumptionis reflected in the values chosen for the call localization parameters.Mobility VariablesDegree of Mobility1(low)2 3 4(high)P1 0.9 0.6 0.4 0.25P2 0.08 0.3 0.3 0.25P3 0.02 0.08 0.2 0.25P4 0 0.02 0.1 0.25Table 6 Assigned values of P1 to P4 for varying degrees of mobility45Call Localization VariablesDegree of Call Localizationhigh lowPAR 0.9 0.6 0.4PBR 0.08 0.3 0.2PCR 0.02 0.08 0.2PDR 0 0.02 0.2PAVB 0.8 0.5 0.3PBVB 0.18 0.4 0.3PCVB 0.02 0.08 0.2PDVB 0 0.02 0.2PAVM 0.8 0.5 0.3PBVM 0.1 0.25 0.2Pcvm 0.1 0.23 0.3PDVM 0 0.02 0.2PAVR 0.8 0.5 0.3PBVR 0.05 0.15 0.2PCVR 0.05 0.15 0.2PDVR 0.1 0.2 0.3Table 7 Assigned values of PA to PD for varying degrees of call localizationThe symbols R, VB, VM, and VR denote the location of the caller's home access MAN relativeto the caller's local access MAN, as shown below:• R: resident of access MAN - local access MAN is home access MAN• VB: visitor from local backbone MAN - home access MAN is on local backbone MAN• VM: visitor from local MA - home access MAN is on local MA• VR: visitor from outside local MA - home access MAN is outside local MAIt was assumed in [17] that subscribers in the microcell would be spaced 1.5m apart and have aneffective walking speed of approximately 1.2 m/s (taking the traffic light delay into account). If wefurther assume that a subscriber reaching the end of a microcell can either continue in the same direction,turn right, or turn left with equal probability, then the number of subscribers leaving access MAN canbe calculated by examining the subscriber traffic at each of the edge microcells. (See Fig. 14.) Thesecalculations yield the following results:1. 3.2 departures/s from microcells at left edge of .8 by 8 block area2. 3.2 departures/s from microcells at top edge463. 3.067 departures/s from microcells at bottom edge4. 3.067 departures/s from microcells at right edgefor a total of 12.53 access MAN departures per second. (The values at the bottom and right edgediffer from those at the left and top edge because we have arbitrarily assigned the microcells alongthe left and top edges of to this access MAN, and the microcells along the right and bottom edgesto the adjacent access MANs.) This is equivalent to approximately 45000 departures per hour. (Asa comparison, simulation results by Seskar and Maric for vehicular traffic in urban areas [25] haveindicated a departure rate of over 60000 per hour for a similar sized region.) In order to determine theaverage number of access MAN boundary crossings per second, the number of departures/sec must bemultiplied by 2, since we assume that the number of subscribers in an access MAN remains constant,and that for every subscriber departure there must be a corresponding subscriber arrival. The averagenumber of crossings per second is therefore 2(12.53) = 25.06 crossings per second per access MAN area.Analysis in [5] and [17] indicates that an access MAN can support approximately 96000 subscribers(fixed as well as mobile), under the assumption that each subscriber averages 2 call attempts per hourduring the busy hour. It has also been shown in [17] than an access MAN can support approximately12 nodes, where each node is associated with one BSC area. It has been shown in [16] that a backboneMAN can support 9 access MANs under certain conditions. In [22], it was assumed that there were5 backbone MANs per MA.With these assumptions, we can similarly calculate the number of backbone MAN boundarycrossings to be 75.2 crossings per second per backbone MAN area, the number of MA boundary crossingsto be 150.4 crossings per second per MA area, and the number of BSC area boundary crossings to beapproximately 6 crossings per second per BSC area.Consider the number of BSC crossings per access MAN area. If there are 12 BSCs per accessMAN then there are (12)(6) = 48 BSC boundary crossings per second per access MAN area. Of these,25.06 are also access MAN boundary crossings. (Recall that an access MAN boundary crossing impliesa BSC area crossing.) Thus, there are 48-25.06 = 22.94 BSC crossings per second per access MAN areathat are not higher level boundary crossings as well. Similarly, there are 150.4 access MAN crossingsper backbone MAN area and 225.6 backbone crossings per MA area that are not higher level boundarycrossings as well.Using these values and the information of Tables 1, 2 and 3, the number of database transactionsdue to subscriber location update can be calculated as shown in Tables 8, 9 and 10 below.47Type of boundary crossing Number of transactions per secBSC area (1)(22.94) = 22.94access MAN (4-P1+P2)(25.06)backbone MAN (5-2P1-P4)(75.2)19MA (4-2P1+P4)(150.4)/45TOTAL: 178.32 — 48.45P1 + 25.06P2 —5.008P4Table 8 Transaction rate at access MAN level database due to subscriber location updateType of boundary crossing Number of transactions per secBSC area N/Aaccess MAN (1)(150.4)backbone MAN (2)(75.2)MA (2)(150.4)/5TOTAL: 360.96Table 9 Transaction rate at backbone MAN level database due to subscriber location updateType of boundary crossing Number of transactions per secBSC area N/Aaccess MAN N/Abackbone MAN (1)(225.6)MA (2)(150.4)TOTAL: 526.4Table 10 Transaction rate at MA level database due to subscriber location updateThe assumed location of the directory databases is dependent on the type of search algorithm. Forthe ripple search, the directory database is assumed to be located at the MA level, since the directorydatabase would only be queried following an unsuccessful query at an MA level database. Placing thedirectory database at the MA level frees the signalling capacity that would otherwise be required on abackbone or access MAN. For the directory search, the directory database is assumed to be located atthe access MAN level, since it is queried first on every call attempt.The database transaction service rates are chosen such that the databases have a maximum utilizationAmax = 0.6. The values of a, /3, S and E defined in section 5.1 are, respectively, 0.4, 0.6, 0.8 and 0.4.486.2 Database Transaction RatesThe database transaction rates can be calculated as described in section 5.2. The database transactionrates at the directory, access MAN, backbone MAN and MA level databases for the ripple and thedirectory database searches are shown in Figs. 16, 17, 18 and 19 below. These results were obtainedby using the expressions listed in Appendices B and C and Tables 8, 9 and 10, and show the number ofdatabase transactions required to support both subscriber location and subscriber tracking. 700600500400300200100directory search — — — -rip. search - low call loc.rip. search - med. call loc.rip. search - high call loc.------------------------------02^3^4degree of mobilityFigure 16 Directory database transaction rate49Figure 17 Access MAN database transaction rateFigure 18 Backbone MAN database transaction rate50For the ripple search, the transaction rate at the each of the databases increases as call localizationdecreases and subscriber mobility increases. For the directory search, the transaction rate at theaccess MAN, backbone MAN and MA level databases also increases with subscriber mobility, butis independent of call localization, since the same number of databases are queried regardless of wherethe caller is situated relative to the callee's home access MAN. Since the directory database is queriedon every call, the total number of directory database queries is higher for the directory search than forthe ripple search (approximately 2300 transactions per second per MA area). However, because it hasbeen assumed that the directory databases are located at the MA level for the ripple search and at theaccess MAN level for the directory search, the transaction rate at each individual directory database islower for the directory search compared to the ripple search.From the figures above, it can be seen that the worst case transaction rate is approximately 2300transactions per second, occurring at the MA level database. Thus, the transaction service rate at theMA database would have to be approximately 3700 transactions per second for the maximum databaseutilization Amax to be 0.6. As a comparison, Bellcore in 1985 established a performance objective of110 transactions per second for the Call Management System Data Base (CMSDB). This performanceobjective was exceeded, with the 800 Service SCP handling 300 transactions per second when it wasintroduced [11]. Murakami and Katoh [9] have proposed a database structure for their routing controlnetwork and have suggested that a transaction capacity of 1000 transactions per second at each databasewould be achievable in practice. Analysis by Lo and Wolff [26] has shown that the total real-time51network database transaction volume per regional calling area to support voice PCS could be on theorder of 4200 queries/sec and 840 updates/sec. It is therefore reasonable to conclude that a service rateof 3700 transactions/sec should be achievable in the future.6.3 Signalling TrafficThe signalling traffic due to subscriber location and tracking can be calculated using the methodsdescribed in section 5.3. The signalling traffic at the access and backbone MANs databases for the rippleand directory search algorithms are shown in Figs. 20 and 21. These results were obtained by using theexpressions listed in Appendices D and E. The amount of signalling increases with subscriber mobilityand decreases with call localization, with the worst case signalling overhead being approximately 1200QA slots/s (500 kbps) on the access MAN and approximately 6000 QA slots/s (2.5 Mbps) on thebackbone MAN.526.4 Database Processing Time for Callee Location at Call Setup — Mean and Standard DeviationThe mean and variance of the time required for the network to locate the callee at call setup usingthe ripple search algorithm can be calculated as described in section 5.4.3. The expected databaseprocessing time using the ripple search algorithm for residents, visitors from the backbone, visitors fromthe MA, and visitors from outside the MA are shown in Figs. 22 — 25. The overall expected databaseprocessing time is shown in Fig. 26. As one would expect, the database processing time increases withincreasing subscriber mobility and decreasing call localization.The expected time required for the network to locate the callee using the directory search algorithm isshown in Fig. 27 for database utilizations of Amax = 0.6. If the databases are assumed to have equivalenttransaction capacities as in the ripple search algorithm, the resulting expected database processing timeis shown in Fig. 28. It can be seen that if the database utilizations are equivalent, there is a greater delayusing the directory search, but if the database transaction capacities are equivalent, there is a smallerdelay using the directory search compared to the ripple search.The standard deviation in the database processing time for the ripple search can be calculated asdescribed in section 5.4.3. The results are shown in Figs. 29 — 32 for the ripple search and in Figs.33 and 34 for the directory search algorithm. The directory search algorithm has a marginally lowerdatabase processing time standard deviation than does the ripple search.53Fil54low call loc. ^- med. call loc. ----------^high call loc. ^Figure 24 Ripple search - Expected database processing time for callee location - visitors from MA-^low call loc. ^-^med. call loc. ----------^high call loc. ^0.020.0180.0160.0140.0120.010.0080.0060.0040.0022^3^4degree of mobility00.0180.0160.0140.0120.010.0080.0060.0040.00202^3degree of mobilityFigure 25 Ripple search - Expected database processing time for callee location - visitors from outside MA55low call loc.med. call loc.-^high call loc.0.0180.0160.0140.0120.010.0080.0060.0040.0022^3degree of mobility0 1Figure 26 Ripple search — Expected database processing time for callee location0.050.0450.040.0350.030.0250.020.0150.010.0050 2^3^4degree of mobilityFigure 27 Directory search — Expected database processing time for callee location —^= 0.656low call loc.0.0125 - med. call loc.high call loc.^7.r7^0.01Ed20. 0.0075"6^-0^0.0050.00250^1 2^3degree of mobility0.0090.0080.0070.0060.0050.0040.0030.0020.0010 2^3^4degree of mobilityFigure 28 Directory search — Expected database processing time for calleelocation — Equivalent database transaction capacities as ripple searchFigure 29 Ripple search — Std. dev. of database processing time for callee location — residents570.0125,^low call loc._ med. call loc.high call loc.low call loc.- med. call loc.high call loc.0.012501 2^3degree of mobility47/7^0.01EaO0. 0.0075.o0.005U)0.00252^3degree of mobility0 1Figure 30 Ripple search — Std. dev. of database processing time for callee location — visitors from backbone7/7^0.01EO0.007500.005Tr;0.0025Figure 31 Ripple search — Std. dev. of database processing time for callee location — visitors from MA58Figure 32 Ripple search — Std. dev. of database processing time for callee location — visitors from remote MAFil596.5 Relative Database SizeIt has been assumed that an access MAN can support approximately 96000 subscribers, a backboneMAN can support approximately 9 access MANs, and that an MA consists of 5 backbone MANs (seesection 6.1). Location information consists of the network address of a BSC area or another database, andcan therefore be represented by approximately 60 bits. Subscriber profile information can be assumedto require a minimum of 100 bytes of storage. Each database contains location information for thesubscribers located in its control area; access MAN level databases will contain location informationas well as subscriber profiles.Assume values of Pi = 0.6, P2 = 0.3, P3 = 0.08, and P4 = 0.02. Therefore, at any given time,approximately 40%, or 38000 of the subscribers who normally reside on a particular access MAN areabsent. If we assume that there are approximately the same number of subscribers in each accessMAN, then there must be approximately 38000 visitors in this access MAN. Similarly, at any giventime, approximately 10000*9 subscribers on a backbone MAN and 2000*5*9 subscribers on an MAwill be visitors from outside the backbone MAN and MA, respectively. Since the database recordsfor subscribers who have that database control area as a home area are permanent , the access MANdatabases will have entries for approximately 96000 + 38000 = 134000 subscribers at any given time.Similarly, the backbone MAN databases will have entries for approximately 96000*9 + 10000*9 =60954000 subscribers, while the MA database will have entries for approximately 4.6 million subscribers.Thus, the approximate database sizes are as shown below:1. access MAN level database = 14.5 Mbytes2. backbone MAN level database = 7 Mbytes3. MA level database = 36.8 Mbytes6.6 Analysis of and Comparison with Centralized ArchitectureA performance analysis of a more centralized database architecture can now be carried out forcomparison purposes. Consider a MAN based PCN similar to the one described in section 2.4, buthaving databases located only at the MA level. The databases contain the location information andservice profile of every subscriber in the MA. The directory databases perform the same function asbefore, and are assumed to be located at the MA level as well. The database transaction rate andsignalling traffic criteria can be determined and used as a basis for comparison.6.6.1 Database Transaction RateThe database transaction rate can be calculated as shown previously in section 5.2. To calculatethe database transaction rate due to subscriber location, the sequence of databases accessed for eachpossible combination of call localization and subscriber mobility is tabulated in Table 11 below. Wedefine the following variables:• PDX ' = 1 - PDX = Probability that callee's home access MAN and caller are located within thesame MA• P4 ' = 1 — P4 = Probability that subscriber is located within its home MAEach column represents a particular database whose location is specified relative to the caller, as describedand illustrated in Appendix A. The expression used to calculate the database transaction rate due to61(1) (6) (9)PDR 'P4 ' 1PDR'P4 1 2PDRP4' 2 1 3PDRP4 2 1 3,4PDVB 'P4 ' 1PDVB 'P4 1 2PDVBP4' 2 1 3PDVBP4 2 1 3,4PDVM'P4 ' 1PDVM 'P4 1 2PDVMP4' 2 1 3PDVMP4 2 1 3,4PDVR'P4' 1PDVR 'P4 1 2PDVBP4 ' 3 1 2PDVRP4 3 1 2,4,5Table 11 Centralized architecture database search sequencesubscriber location can be derived from the table above, and is shown below:MA database transaction rate= (resident call rate)(1 + PDR 'P4 + PDRP4 ' 2PDRP4)+ (visitor from backbone call rate)(1 + PDVB 'P4 + PDVBP4 ' 2PDVBP4)+ (visitor from MA call rate)(1 + PDVM'P4 + PDVMP4' + 2PDVMP4)+ (visitor from remote MA call rate)(1 + PDVR 'P4 + PDVRP4' + 3PDVRP4)The database transaction rate due to subscriber tracking can be calculated by examining the transactionsoccurring at the databases for each type of boundary crossing. Assuming the subscribers are tracked atthe BSC level as before, the only boundary crossing types that need to be considered are the BSC andthe MA boundary crossings. The database transactions corresponding to each boundary crossing typeare tabulated below. The expression to calulcate the database transaction rate due to subscriber tracking62Type of boundary crossingNumber of databasetransactions per boundarycrossingType of transactionBSC area 1 updateMA1 update1 regP4 update HLR2P4 SP writeTable 12 Database transactions due to subscriber trackingcan be derived from the above table, and is shown below:Database transaction rate= (#BSC area crossings in MA)(1)+ (#MA crossings)(2+3P4)From the information in section 6.1 the number of BSC crossings per second in an MA can be calculatedas follows:(6 crossings/BSC area)(12 BSCs/access MAN)(9 access MANs/backbone MAN)(5 backboneMANs/MA) — 150.4 = 3089.6 BSC crossings/MA areaThe MA boundary crossing rate is 150.4 crossings per second. The total database transaction rate dueto subscriber location and tracking can be calculated using the above two equations, yielding the resultshown in Fig. 35 below.637500 low call loc.med. call loc.high call loc.80002^3degree of mobility5000 147000650060005500Figure 35 Centralized database transaction rate6.6.2 Signalling TrafficThe signalling traffic can be calculated as shown previously in section 5.3. Since the databasesare located at the MA level, traffic capacity is required over the access and backbone MANs for eachcall initiated or received by a subscriber in the MA. From the information in section 6.1, the signallingtraffic due to subscriber location can therefore be calculated as#QA slots per second required on access and backbone MANs = (# calls per sec involving subscriberswithin MA)(#QA slots per query packet)This yields a signalling traffic value of (2400)(2) = 4800 QA slots per second on the access andbackbone MANs.The signalling traffic due to subscriber tracking can be calculated by examining the transfer ofinformation between network components required for each type of boundary crossing. As in section6.6.1 above, the BSC area and MA boundary crossings are considered. The data required for eachsignalling operation and the number of data transfers and QA slots required for each type of boundarycrossing are tabulated in Table 13 below. Note that service profile transfers and HLR updates take place64Type of boundarycrossingNumber ofdata transfersSignalling operation Number ofQA slotsrequiredBSC area (see Fig.10)1 update loc. 21 ack. 1MA (see Fig. 13)1 register MT req 21 deregister. MT 21 ack. 1Table 13 Signalling traffic over access and backbone MANs due to subscriber trackingbetween MA level databases only, and do not require signalling capacity over the access or backboneMANs. The folowing expression can be derived from the information of Table 13:# QA slots per sec. required on access and backbone MANs = (#BSC area crossings per MA areaper sec)(3 QA slots) + (#MA crossings per sec.)(5 QA slots)This yields a signalling traffic value of (3090)(3) + (150.4)(5) = 9420 QA slots.The total signalling traffic due to subscriber location and tracking is 9420 + 4800 = 14220 QA slotsper second, which is approximately equivalent to 6 Mbps on both the access and backbone MANs.Examination of the above results shows that the centralized database architecture results in greatertransaction traffic at the database and greater signalling traffic over the access and backbone MANs (aswell as over the network interconnecting the MAs).6.7 Database Processing Time for Callee Location at Call SetupThe expected time required for the network to locate the callee at call setup can be calculatedas described in section 5.4.3. Using the database transaction rates calculated in section 6.6.1 and thedatabase search sequences of Table 11 the expected database processing time for callee location at callsetup for residents, visitors from the backbone, visitors from the MA, and visitors from outside theMA can be calculated. The overall expected database processing time for callee location is shown inFig. 36, for a database utilization of Amax = 0.6, corresponding to database transaction capacities ofapproximately 12000 and 900 transactions per second, respectively at the MA and directory databases.65It can be shown that in order to achieve delay values comparable to those achieved with the distributedarchitecture, the MA and directory databases require transaction capacities of approximately 7600 and570 transactions per second, respectively.6.8 Relative Database SizeThe centralized MA database will contain both location and subscriber profile information. Assumevalues of Pi = 0.6, P2 = 0.3, P3 = 0.08, and P4 = 0.02. Using similar reasoning to that of section 6.5,the size of the MA database can be calculated as follows:Proportion of subscriber who reside at this MA who are absent = 0.02.Number of subscribers visiting this MA = (0.02)(4320000) = 86400Number of subscriber records at central MA database = 4320000 + 86400 = 4406400.Size of centralized database = (4406400)(108 bytes) 476 Mbytes.6.9 Mobility Management in the ATM Based PCNAn alternate transport architecture that has been considered is one based on hierarhical internet-worked ATM switches [16], where small ATM switches would be used to interconect groups of micro-:ells and wireline customer networks. ATM multiplexers would be used to multiplex BSCs and LANsmto a high speed transmission link towards a higher capacity ATM switch. The choice of a distributed66processing integrated architecture using either MANs and/or ATM switches to interconnect fixed andradio terminals will depend upon various parameters including efficient use of existing facilities and therelative cost of MAN nodes in comparison to that of an ATM switch.The database architecture for PCS mobility management described in section 3.1 could also beapplied to such an ATM based architecture, where the 3 database levels could logically be co-locatedwith the BSCs (level 1), ATM multiplexers (level 2), and high capacity ATM switches at the CO (level3). Analysis of such a database architecture would be very similar to the approach taken in section 5.The database transaction rates and database processing delay statistics would be similar to the resultsobtained for the MAN based database architecture, since both these criteria are primarily affected byfactors other than the transport architecture. The signalling calculations would be affected, however,since the means by which information is transported from one network element to another for subscriberlocation and tracking is dependent on the specific transport architecture.677 Conclusions7.1 Concluding RemarksThe deployment of network intelligence in distributed databases is an aspect of the IN architecturewhich is well suited for mobility management functions in PCS. A distributed microcellular architecturebased on the IEEE 802.6 Metropolitan Area Network (MAN) has been proposed for provision of PCSfor fixed and pedestrian traffic in urban areas. A hierarchical distributed database architecture canbe implemented to support two basic functions of mobility management: (1) subscriber location at callsetup, and (2) tracking of a roaming subscriber. The physical and logical database structure and contentshave been defined, and the protocols necessary to perform the basic mobility management functions ofsubscriber location at call setup and tracking of a roaming subscriber have been developed.Two search methods using the proposed database architecture are compared. Some criteria on whichto evaluate their performance have been suggested. Methods to analyse the performance of the searchmethods have been proposed. The transaction rates at the location databases are higher for the ripplesearch algorithm compared to the directory search algorithm. However, the total number of transactionsat the directory databases is higher for the directory search than for the ripple search.The worst case signalling required for mobility management using the proposed architecture isapproximately 1200 QA slots/s (500 kbps) on the access MAN and approximately 6000 QA slots/s (2.5Mbps) on the backbone MAN, for both the ripple and the directory search algorithms. The worst casesignalling using the more centralized architecture is approximately 14220 QA slots/s (6 Mbps) on boththe access and the backbone MAN. The mean database processing time for callee location is under20 ms using the ripple search algorithm. The mean database processing time for the directory searchalgorithm is under 40 ms if the database utilization is the same as the ripple search case, and under 10ms if the database transaction capacity is the same as the ripple search case. Note that the times givenabove for the ripple search do not include the timeout periods between each phase.The ripple search would be advantageous in cases where the subscriber mobility is very low andcall localization is very high, since only the local databases or local database fragments would needto be queried in order to locate the callee. In cases where subscribers are more mobile and calls aremore widely distributed, the directory search algorithm is advantageous since fewer overall databasetransactions are required and better delay characteristics can be expected. However, the directory searchrequires a more widely distributed directory database. Thus, the advantage of the directory search isdependent on whether or not the directory databases can be economically replicated and distributed68throughout the network. Because callee location using the directory search algorithm does not involvequeries to the callers' local database fragments at the access MAN level, it may not be as advantageousto fragment the access MAN level database as it was in the case of the ripple search.For comparison purposes, a similar analysis is carried out for a more centralized database archi-tecture, where the lower level access and backbone MAN databases are eliminated and the mobilitymanagement functions are performed by the high level MA databases only. The worst case transactionrate is over 7000 transactions per second, while the worst case signalling is approximately 6 Mbps onboth the access and backbone MANs. For the centralized case, the MA database size is estimated to beapproximately 476 Mbytes. The worst case expected delay is under 1 ms, but is only achievable withdatabases having a much higher transaction capacity than the databases considered for the distributedarchitecture. This high transaction capacity could be difficult to attain, particularly when the requireddatabase size is taken into account.The proposed database architecture is therefore expected to provide superior performance ascompared to a purely centralized approach as demand for PCS increases. The hierarchical nature of thedatabase architecture spreads the query traffic among different levels of databases, taking advantage ofthe localized distribution of calls. The distributed nature of the database architecture spreads the updatetraffic as subscribers roam, localizing detailed information at databases close to the subscribers.7.2 Suggestions for Further WorkThe performance of the subscriber location and tracking methods described above has been deter-mined through analysis of fairly simple models, using simplifying assumptions. Simulations should beperformed to determine the accuracy of the models. The simulations could include the effects of otherfactors, such as access and transmission delays over the MAN and network routing delays. A moredetailed subscriber mobility and traffic model could also be used.The type of network architecture that has been considered is appropriate only for pedestrians andrelatively slow moving traffic in urban areas. Investigation into methods of providing PCS to subscribersin faster moving vehicular traffic (automobiles, trains, aircraft) would be useful.It is also important to investigate the issues associated with provision of mobility management andother PCS functions across multiple service providers. One possible scenario could be that one entitythat provides the subscription for services (the PCS service provider) and another that provides thefacilites for connectivity (the network provider). Even the basic functions of registration, routing andbilling to a single PCS number become very complex when multiple networks are involved.69Mobility management functions can be the basis of other services offered via the Intelligent Network.The proposed database architecture and contents considered here have included only the data necessaryfor mobility management. The integration of mobility management data with that for other services,and the consequent effect on the database architecture and contents could also be examined.The work here has focused on the IEEE 802.6 MAN network architecture. It may be useful toexamine in more detail the ways in which subscriber location and tracking performance change whendifferent architectures, such as those based on ATM switching, are used.70Appendix A Database Search Sequence Tables for Rippleand Directory Search AlgorithmsConsider the subscribers located on a particular access MAN. They can be grouped into one of fourcategories: residents of the access MAN, visitors to the access MAN from the backbone, visitors fromthe home MA, and visitors from outside the MA. The following tables list the database search sequencesthat would be used to locate the callee for each category of subscriber. The first four tables apply tothe ripple search and the next four tables to the directory search.Recall from [22] and section 5.1 that the database access rate is a function of three parameters:call localization, subscriber mobility, and actual position of callee relative to caller. The variables PA,PB, Pc, and PD represent degree of call localization, with the second subscript R, VB, VM, and VRindicating that the variable refers to a subscriber that is a resident, visitor from backbone, visitor fromMA, and visitor from remote MA, respectively. The variables Pi, Pz, P3, and P4 represent subscribermobility. The variables a, /3, and 6 are defined in section 5.1. Consider a caller A. Each columnrepresents a particular database level, where the specified locations are relative to the access MAN onwhich caller A is currently located. These locations are listed below:(1) Directory database(2) Local access MAN database fragment(3) Local access MAN database(4) Local backbone database(5) Access MAN database on backbone(6) Local MA database(7) Backbone MAN database on MA(8) Access MAN database on MA(9) Remote MA database(10)B ackbone MAN database on MA(11) Access MAN database on MA71Refer to Fig. 37.Figure 37 Database hierarchy72(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PARP1a 1PARP1( 1-0 1 2PARP2 1 2 3PARP3 1 2 3 4PARP4 1 2 3 4 5PBRP1 1 2 3 4PBRP2 ai3 1PBRP2 ( 1 -43 1 2PBRP2 ( 1 -P) 1 2 3 4PBRP3 1 2 3 4 5 6PBRP4 1 2 3 4 5 6 7PCRP1 1 2 3 4 5PcRP2 1 2 3 4 5 6PcRP3 OS 1PcRP3( 1 -036 1 2PcRP3( 1-)(3)6. 1 2 3 4PcRP3(1-6) 1 2 3 4 5 6PCRP4 1 2 3 4 5 6 7 8 9PDRP1 5 1 2 3 4 6PDRP2 5 1 2 3 4 6, 7PDRP3 5 1 2 3 4 7 6, 8PDRP4 aP Of 1PDRP4 (1 -a)POE 1 2PDRP4 ( 1 -p)Of 1 2 3 4PDRP4(1-6)€ 1 2 3 4 5 6PDRP4 (1 - E) 5 1 2 3 4 7 8 6, 9Table 14 Ripple search database access sequence — residents of access MAN73(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PAvei a 1PANTBP1 ( 1 -a) 1 2PAVBP2 1 2 3PAVBP3 1 2 3 4PAVBP4 1 2 3 4 5PBvei 1 2 3 4PBVBP2a/3 1PBVBP2(1-0 )/3 1 2PBv}3P2( 1-0) 1 2 3 4PBVBP3 1 2 3 4 5 6PBVBP4 1 2 3 4 5 6 7PcvBP1 1 2 3 4 5 6Pcvez 1 2 3 4 5 6PcvBP3 «PO 1PcvsP3 (1 -a)06 1 2PcvBP3(1-M6 1 2 3 4PcvBP3( 1-6) 1 2 3 4 5 6PcvBP4 1 2 3 4 5 6 7 8 9PDVBP1 5 1 2 3 4 6PDVBP2 5 1 2 3 4 6, 7PDVBP3 5 1 2 3 4 7 6, 8PDvBP4a/36€ 1PDvBP4( 1-a)06€1 2PDvBP4(1-8)Of 1 2 3 4PDvBP4(1-6)c 1 2 3 4 5 6PDvBP4(1-E) 5 1 2 3 4 7 8 6, 9Table 15 Ripple search database access sequence — visitors from backbone74(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PAvmPi a 1PAvmPi (1-a) 1 2PAVMP2 1 2 3PAVMP3 1 2 3 4PAVMP4 1 2 3 4 5PBvmPi 1 2 3 4PBVMP2ct/3 1PBvmP2(1-a)0 1 2PB VMP2( 1 - il3) 1 2 3 4PB VMP3 1 2 3 4 5 6PB VMP4 1 2 3 4 5 6 7PcvmPi 1 2 3 4 5 6PcvmP2 1 2 3. 4 5 6PcvmP3 a0 6 1PcvmP3 ( 1-006 1 2PcvmP3 ( 1-0)6 1 2 3 4PcvmP3 (14) 1 2 3 4 5 6PCVMP4 1 2 3 4 5 6 7 8 9PDvmPi 5 1 2 3 4 6PDVMP2 5 1 2 3 4 6, 7PDVMP3 5 1 2 3 4 7 6, 8PDvmP4 a0 Of 1PDVMP4 (1 -00(5 f1 2PDvmP4(1-73)Oc 1 2 3 4PDvmP4 (1 - (5)c 1 2 3 4 5 6PDvmP4 ( 1 -E) 5 1 2 3 4 7 8 6, 9Table 16 Ripple search database access sequence — visitors from MA75(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PAvRPia 1PAvRP1(1-a) 1 2PAVRP2 1 2 3PAVRP3 1 2 3 4PAVRP4 1 2 3 4 5PBVRPI 1 2 3 4PBVRP2 af3 1PB VRP2 ( 1 - a)/(3 1 2PsvRP2(1 -0) 1 2  3 4PBVRP3 1 2 3 4 5 6PB VRP4 1 2 3 4 5 6 7PcvRP1 1 2 3 4 5 6PcvRP2 1 2 3 4 5 6PcvRP3a0O 1PcvRP3(1-a),06 1 2PcvRP3(1 -0)6' 1 2  3 4PcvRP3(1 4) 1 2 3 4 5 6PcvRP4 1 2 3 4 5 6 7 8 9PDVRP1 8 1 2 3 4 7 6 5, 9PDVRP2 8 1 2 3 4 7 6 5, 9, 10PDVRP3 8 1 2 3 4 7 7,10 5, 9, 11PDvRP4a06( 1PDvRP4(1 -a)0Of1 2PDvRP4(1- 0)6E 1 2 3 4PDRP4(1-6)E 1 2 3 4 5 6PDvRP4(1-€)  8 1 2 3 4 7, 10 6, 11 5, 9, 12Table 17 Ripple search database access sequence — visitors from remote MA76(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PARP1 1 2PARP2 1 2 3PARP3 1 2 3 4PARP4 1 2 3 4 5PBRP1 1 2PBRP2 1 2,3PBRP3 1 2 3 4PBRP4 1 2 3 4 5PCRP1 1 2PcRP2 1 2,3PCRP3 1 3 2,4PCRP4 1 2 3 4 5PDRP1 1 2PDRP2 1 2,3PDRP3 1 3 2,4PDRP4 1 3 4 2,5Table 18 Directory search database query sequence — residents of access MAN77(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PAVBP1 1 2PAVBP2 1 2 3PAVBP3 1 2 3 4PAVBP4 1 2 3 4 5PBvei 1 2PBVBP2 1 2,3PBVBP3 1 2 3 4PBVBP4 1 2 3 4 5PcvBP1 1 2PCVBP2 1 2,3PcvBP3 1 3 2,4PcvBP4 1 2 3 4 5PDVBP1 1 2PDVBP2 1 2,3PDVBP3 1 3 2,4PDVBP4 1 3 4 2,5Table 19 Directory search database query sequence — visitors from backbone MAN78(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PAvmPi 1 2PAVMP2 1 2 3PAVMP3 1 2 3 4PAVMP4 1 2 3 4 5PsvmPi 1 2PBVMP2 1 2,3PBVMP3 1 2 3 4PBVMP4 1 2 3 4 5PcvmPi 1 2PcvmP2 1 2,3PCVMP3 1 3 2,4PCVMP4 1 2 3 4 5PDvmPi. 1 2PDVMP2 1 2,3PDVMP3 1 3 2,4PDVMP4 1 3 4 2,5Table 20 Directory search database query sequence — visitors from MA79(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PAVRP1 1 2PAVRP2 1 2 3PAVRP3 1 2 3 4PAVRP4 1 2 3 4 5PsvRPi 1 2PBVRP2 1 2,3PBVRP3 1 2 3 4PBVRP4 1 2 3 4 5PcvRP1 1 2PcvRP2 1 2,3PcvRP3 1 3 2,4PcvRP4 1 2 3 4 5PDvRP1 1 2PDVRP2 1 2,3PDVRP3 1 3 2,4PDVRP4 1 3 4 2,5Table 21 Directory search database query sequence — visitors from remote MA80Appendix B Expressions to Calculate Database TransactionRates — Ripple Search AlgorithmUsing the information presented in the tables of Appendix A, the database query traffic due tocallee location at call setup may be determined. The arrival rates at the databases as a function ofsubscriber mobility, call localization and actual position of caller relative to callee can be determinedby examining the tables, and summing the probability values corresponding to the marked values in thecolumns corresponding to the particular database level. For example, to calculate the arrival traffic atthe access MAN level database, we first note that columns 2, 3, 5, 8 and 11 of the tables correspond toaccess MAN level database accesses. From Table 14, these five columns yield:access MAN traffic arrival rate from residents= (resident call rate)* {1 (col. 2 and 3)+ PARP2 + PBRP1 + PBRP2( 1-0) PBRP3 + PBRP4 + PCRP3( 1-0)6 PDRP4(1-0) 6E (col. 5)+ PARP3 + PBRP3+PcRP1 + PCRP2 + PcRP3(1-6) + PCRP4 + PDRP4(1-6)E (col. 8)+ PARP4 + PBRP4 + PCRP4 + PDR(P1 + 2P2 + 2P3 + 2P4(1—E) ) (Col. 11) }Summing over all four tables in this way yields:total access MAN database traffic arrival rate= (resident call rate)* {1 (col. 2 and 3)+ PARP2 + PBRP1 + PBRP2( 1-0) PBRP3 + PBRP4 + PcRP3(1-0)(5 + PDRP4(1-0)(5E (col. 5)+ PARP3 + PBRP3+PCRP1 + PCRP2 + PCRP3( 1-6) PCRP4 + PDRP4(1—()f (col. 8)+ PARP4 + PBRP4 + PCRP4 + PDR(P1 + 2P2 + 2P3 + 2P4(1-0 ) (col. 11)+ (visitor from backbone call rate)* {1 (col. 2 and 3)+ PAVBP2 + PBVBPI + PBVBP2( 1-0) + PBVBP3 + PBVBP4 + PCVBP3( 1-05 + PDVBP4(1-0)6( (col. 5)+ PAVBP3 + PBVBP3+PCVBP1 + PCVBP2 + PCVBP3( 1-6) + PCVBP4 + PDVBP4( 1—(S)( (col. 8)+ PAVBP4 + PBVBP4 + PCVBP4 + PDVB(P1 + 2P2 + 2P3 + 2P4(1—E) ) (C01. 11) }+ (visitor from MA call rate)* {1 (col. 2 and 3)+ PAN/m132 + PBVMPI + Ft3vmP2( 1-0) + PBVMP3 + PBVMP4 + PcvmP3(1-0)6 + PDvmP4(1-0)6((col. 5)81+ PAVMP3 + PBvmP3+PcvmP i + PCVMP2 + PcvmP3( 1-6) + PCVMP4 + PDvmP4(1-6)( (col. 8)+ PAVMP4 + PBVMP4 + + PCVMP4 + PDVM(P1 + 2P2 + 2P3 + 2P4(1—E)) (col. 11) }+ (visitor from remote MA call rate)* [1 (col. 2 and 3)+ PAVRP2 + PI3vRP1 + PBVRP2( 1-73) + PBVRP3 + PBVBP4 + PCVRP3( 143)6 + PDVRP4(1-13)6( (col. 5)+ PAVRP3 + PBvRP3+PcyRP1 + PCVRP2 + PCVRP3( 1-ö) + PCVRP4 + PDVRP4( 1-6)E (C01. 8)+ PAVRP4 + PBVRP4 + PcvRP4 + PDvR(2P1 + 3P2 + 3P3 + 3134(1-E) ) (col. 11) }Similarly, of course, the arrival rate at the backbone MAN database can be calculated by examiningcolumns 4, 7, and 10 of the tables, yielding:total backbone MAN database traffic arrival rate= (resident call rate)* {PBRP1 + PBRP2(1—P) + PBRP3 + PBRP4+ PCRP1 + PCRP2 + PCRP3( 1-0)6 + PCRP3( 1-6) + PCRP4+ PDR(P1 + P2 + P3 + P4[(1-P)6E + (1-6)E + (1-E)] (col. 4)+ PARP3 + PBRP3 + PCR(P1+P2) + PcRP3(1-6) + PCRP4 + PDRP4(1-6)E (col. 7)+ PARP4 + PBRP4 + PD12033+P4( 1--E) + PCRP4 (COL 10) }+ (visitor from backbone call rate)* {PBVBP1 + PrivBP2( 1-0) + PBVBP3 + PBVBP4+ PCVBP1 + PCVBP2 + PCVBP3( 1-P) 46 + PCVBP3(1-6)+ PCVBP4 + PDVB(P1 + P2 + P3 + P4[(1—(3)6E + (1-6)c + (1—€)] (col. 4)+ PAVBP3 + PBVBP3 + PCVB(P1+P2) + PCVBP3( 1-6 ) + PCVBP4 + PDVBP4( 1-6)E (COL 7)+ PAVBP4 + PBVBP4 + PDVB(P3+P4( 1-E) + PCVBP4 (COI. 10) }+ (visitor from MA call rate)* {PBvmPi + PBvmP2( 1—P) + PBVMP3 + PBVMP4+ PcvmPi + PCVMP2 + PcvmP3(1—P)6 +PcvmP3(1-6) + PCVMP4 + Povm(Pi + P2 + P3 + P4[(1—/3)6€ + (1-6)€ + (l—€)] (col. 4)+ PAVMP3 + PBVMP3 + Pcvm(P1+P2) + PcvmP3(1—ö) + PCVMP4 + PovmP4(1-6)€ (col. 7)+ PAVMP4 + PBVMP4 + Povm(P3+P4(1—E) + PCVMP4 (col. 10)+ (visitor from remote MA call rate)* {PBvRPI. + PBvRP2( 1—P) + PBVRP3 + PBVBP4+ PCVRP1 + PcyRP2 + PCVRP3( 1-)(3)6 + PCVRP3( 1-6)+ PcvRP4 + PDVR(P1 + P2 + P3 + P4[(1-P)6E + (1-0€ + (1—c)] (col. 4)PAVRP3 PBVRP3 + PCVR(Pl+P2) + PCVRP3( 1-6 ) + PCVRP4 + PDVRP4( 1-6)E (col. 7)+ PAVBP4 + PByR134 + PCVRP4 + PDVR(P1 + P2 + 2P3 + 2P4(1-E) (COL 10) }82The arrival rate at the MA database can be calculated by examining columns 6 and 9 of the tables,yielding:total MA database arrival rate= (resident call rate)* 113cRP1 + PCRP2 + PcRP3(1-13)6 + PCRP4 + PDR(P1 + P2 + P3 + P4[(1-0E + (1—E)] )(COL 6)+ PARP4 + PBRP4 + PCRP4 + PDRP4( 1—E) (COI. 9) I+ (visitor from backbone call rate)* { PcvBP1 + PCVBP2 + PcyBP3(1—P)6 + PCVBP4 + PDVB(P1 + P2 + P3 + P4[(14)E + (1—E)] )(col. 6)+ PAVBP4 + PBVBP4 + PCVBP4 + PDVBP4 (1 -0 (col. 9) }+ (visitor from MA call rate)* { PcvmPi + PCVMP2 + PcvmP3(173)(5 + PCVMP4 + PDVM(P1 + P2 + P3 + P4[(1-0E + (1 —€)1)(col. 6)+ PAVMP4 + PBVMP4 + PCVMP4 + PDvmP4(1—e) (col. 9) }+ (visitor from remote MA call rate)* {PcvRP1 + PcvRP2 + PcvRP3( 1—t3)6 + PCVRP4 + PDVR(P1 + P2 + P3 + P4[(1-6)E + (1-0] )(col. 6)+ PAvRP4 + PBVRP4 + PCVRP4 + PDVR(P1 + P2 + P3 + 2P4(1—E) (COI. 9) IFinally, the total directory database access rate can be calculated by examining column 1 of the tables,yielding:total directory database arrival rate= (resident call rate)* {PDR(P1 + P2 + P3) + PDRP4(1-0 1+ (visitor from backbone call rate)* {PDVB(P1 + P2 + P3) + PDVBP4( 1—E) 1+ (visitor from MA call rate)* (Pnvm(Pi + P2 + P3) + PDVMP4(l—E) 1+ (visitor from remote MA call rate)* tPDvR(Pi + P2 + P3) + PDVRP4( 1-0 183Appendix C Expressions to Calculate Database TransactionRates — Directory Search AlgorithmThe database query traffic due to callee location at call setup using the directory search algorithmmay be determined using methods similar to the ones described in Appendix BConsider the rate of query arrival at the access MAN database due to call setup requests fromresidents of the access MAN:access MAN database traffic arrival rate from residents= (resident call rate)* {PARP1 + PARP2 PARP3 + PARP4 (col. 3)• PARP2 + PBRP1 + 2PBRP2 + PBRP3 + PBRP4 (col. 5)+ PARP3 + PBRP3+PozP1 + 2PCRP2 + 2PCRP3 + PCRP4 (col. 8)+ PARP4 + PBRP4 PCRP4 2(PDR(P2 + P3 + P4)) + PDRP1 (col. 11) 1This can be rearranged as:access MAN database traffic arrival rate from residents= (resident call rate)* [PARP1 + 2PARP2 + 2PARP3 + 2PARP4+ PBRP1 + 2PBRP2 + 2PBRP3 + 2PBRP4+ PCRP1 + 2PCRP2 + 2PCRP3 + 2PCRP4+ PDRP1 + 2PDRP2 + 2PDRP3 + 2PDRP4]By summing over all tables, we can obtain:total access MAN database traffic arrival rate= (resident call rate)* [PARP1 + 2PARP2 + 2PARP3 + 2PARP4+ PBRP1 + 2PBRP2 + 2PBRP3 + 2PBRP4+ PcRPI + 2PCRP2 + 2PCRP3 + 2PCRP4+ PDRP1 + 2PDRP2 + 2PDRP3 + 2PDRP4l+ (visitor from backbone call rate)* [PAvsPi + 2PAVBP2 + 2PAVBP3 + 2PAVBP4+ PBVBP1 + 2PBVBP2 + 2PBVBP3 + 2PBVBP4+ PcvBP1 + 2PcvBP2 + 2PcvBP3 + 2PcvsP484+ PDVBP1 + 2PDVBP2 + 2PDVBP3 + 2PDVBP41+ (visitor from MA call rate)* [PAVMP1 + 2PAVMP2 + 2PAVMP3 + 2PAVMP4+ PBvmPi + 2PBvmP2 + 2PBVMP3 + 2PBVMP4+ PcvmPi + 2PCVMP2 + 2PCVMP3 + 2PCVMP4+ PDvmPi + 2PDVMP2 + 2PDVMP3 + 2PDvmP4l+ (visitor from remote MA call rate)* [PAVRP1 + 2PAVRP2 2PAVRP3 + 2PAVRP4+ PBvRPI + 2PBvRP2 + 2PBVRP3 + 2PBVRP4+ PcvRP1 + 2PcvRP2 2PcvRP3 + 2PcvRP4+ PEN1P1 + 2PDVRP2 + 2PDVRP3 + 2PDVRP4JSimilarly, for the backbone MAN database access rate we have:total backbone MAN database access rate= resident call rate* [PARP3 + PARP4 + PBRP3 + PBRP4 + PCRP3 + PCRP4 + PDRP3 + PDRP4I+ visitor from backbone call rate* [PAVBP3 + PAVBP4 + PBVBP3 + PBVBP4 + PCVBP3 + PCVBP4 + PDVBP3 + PDVBP4]+ visitor from MA call rate* [PAVMP3 + PAVMP4 + PBVMP3 + PBVMP4 + PCVMP3 + PCVMP4 + PDVMP3 + PDVMP4I+ visitor from remote MA call rate* [PAvRP3 + PAVRP4 + PBVRP3 + PBVRP4 + PCVRP3 + PCVRP4 + PDVRP3 + PDVRP4]Total MA databaser access rate= (resident call rate)* [PARP4 + PBRP4 + PCRP4 + PDRP4]+ (visitor from backbone call rate)* [PAVBP4 + PBVBP4 + PCVBP4 + PDVBP4I+ (visitor from MA call rate)* [PAVMP4 + PBVMP4 + PCVMP4 + PDVMP4I+ (visitor from remote MA call rate)* [PAVRP4 + PBVRP4 + PCVRP4 + PDVRP4]85Since the directory database is queried on each call attempt the total directory database access rate issimply:total directory database access rate= (resident call rate) + (visitor from BB call rate) + (visitor from MA call rate) + visitor fromremote MA call rate)86Appendix D Expressions for Calculation of SignallingTraffic Using Ripple Search AlgorithmThe signalling traffic due to subscriber location is calculated by examining the sequence of databaseaccesses as shown in the tables of Appendix A and determining the media over which data transfer musttake place as queries are forwarded from one database to another. Consider the last entry of Table 14.The sequence of database searches that takes place for this case is as shown in the table entry, whichis reproduced here for convenience:(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)PDRP4(1-e) 5 1 2 3 4 7 8 6, 9Consider the query packets that are broadcast over the access and backbone MANs. The signallingcapacity in terms of query packets is calculated as shown in Table 22 below. The PDRP4(1—c) termsSending database: Receiving database: Number of querypackets transmittedover access MANNumber of querypackets transmittedover backbone MAN2 (access MANfragment)3 (access MANdatabase)1 03 (access MANdatabase)4 (backbone MANdatabase)1 14 (backbone MANdatabase)6 (MA database) 0 16 (MA database) 1 (directory database) 0 01 (directory database) 11 (access MANdatabase)1 111 (access MANdatabase)9 (MA database) 1 19 (MA database) 10 (backbone MANdatabase)0 110 (backbone MANdatabase)11 (access MANdatabase)1 1TOTAL: 5 6Table 22 Calculation of signalling over access and backbone MANs for last entry of Table 14therefore have the coefficients 5 and 6 in the access MAN and backbone MAN equations, respectively,87shown below. (Note also that a query packet has been assumed to require two QA slots of capacityon the backbone and access MANs.)access MAN traffic due to subscriber location retrieval= resident call rate *{ PARP1(1-a) + 3PARP2 + 3PARP3 + 3PARP4+ 3PBRP1 + PBRP2(1—a)13 + 3PBRP2(1-0) + 5PBRP3 + 5PBRP4+ 313cR131 + 3PCRP2 + PcRP3(1 —a)/36 + 3PcRP3(1-0)6 + 3PcRP3(1-6)+ 5PcRP4+ 3PDRP1 + 5PDRP2 + 5PDRP3 + PDRP4(1—a))36€ + 3PDRP4(1-0)6c + 3PDRP4(1-6)f + 5PDRP4(1—€) }+ visitor from backbone call rate *{ PAvBP1(1—a) + 3PAVBP2 + 3PAVBP3 + 3PAVBP4+ 3PBvei + PBvBP2(1-43 + 3PBvB132(1-0) + 5PBVBP3 + 5PBVBP4+ 3Pcve1 + 3PcvBP2 + PcvBP3( 1—a)06 + 3PcvBP3(1-0)6 + 3PcvBP3(1-6)+ 5PCVBP4+ 3PDVBP1 + 5PDVBP2 + 5PDVBP3 + PDvBP4(1—a)/36€ + 3PDvBP4(1-0)6€ +5PDvBP4( 1-0 }3PDvBP4( 1-0€ ++ visitor from MA call rate *{ PAvmPi(1—a) + 3PAVMP2 + 3PAVMP3 + 3PAVMP4+ 3PBvmPi + PBvmP2(1 —(00 + 3PBvmP2( 1-0) + 5PBVMP3 + 5PBVMP4+ 3PcvmPi + 3PcvmP2 + PcvmP3(1—a)06 + 3PcvmP3(1-0)6 + 3PcvmP3(1-6)+ 5PCVMP4+ 3PDvmPi + 5PDVMP2 + 5PDVMP3 + PDvmP4(1—a)06( + 3PDvmP4(1—P)6E + 3PDvmP4(1-6)c +5PDvmP4(1—E) }visitor from remote MA call rate *{ PAvRP1(1—a) + 3PAVRP2 + 3PAVRP3 + 3PAVRP4+ 3PBVRP1 + PBvRP2(1—a)0 + 3PBvRP2(1—M + 5PBvRP3 + 5PBVRP4+ 313cyR131 + 3PcvRP2 + PcvRP3(1 —a)06 + 3PcvRP3(1-0)6 + 3PcvRP3(1-6)+ 5PcvRP4+ 3PDVRP1 + 5PDVRP2 + 5PDVRP3 + PDvRP4(1—a)06€ + 3PDvRP4(1-0)6€ + 3PDvRP4(1-6)c +7PDvRP4(1—€) }88The total backbone MAN traffic due to subscriber location retrieval= resident call rate *( PARP2 + 3PARP3 + 3PARP4+ 2PBRP1 + 2PBRP2(1 -0) + 5PBRP3 + 5PBRP4+ 4PcRP1 + 4PCRP2 + 2PCRP3(1-0)6 + 4PcRP3(1-6) + 7PCRP4+ 3PDRP1 + 4PDRP2 + 5PDRP3 + 2PDRP4(1-/3)& + 4PDRP4(1-0( + 6PDRP4(1-€) )+ visitor from backbone call rate *( PAVBP2 + 3PAVBP3 + 3PAVBP4+ 2PBVBP1 + 2PBVBP2( 1-0) + 5PBVBP3 + 5PBVBP4+ 4PCVBP1 + 4PCVBP2 + 2PCVBP3( 1-/3)6 + 4PCVBP3(1-ö) + 7PCVBP4+ 3PDVBP1 + 4PDVBP2 + 5PDVBP3 + 2PDVBP4(1-0)6E + 4PDVBP4(1-6)E + 6PDVBP4( 1-E) )+ visitor from MA call rate *PAvmP2 + 3PAVMP3 + 3PAVMP4+ 2PBvmPi + 2PBvmP2(1-13) + 5PBVMP3 + 5PBVMP4+ 4PcvmPi + 4PCVMP2 + 2PcvmP3(1-73)6 + 4PcvmP3(1-6) + 7PCVMP4+ 3PDvmPi + 4PDVMP2 + 5PDVMP3 + 2PDvmP4(1-0)6f + 4PDvmP4(1-0€ + 6PDvmP4( 1—E) )+ visitor from remote MA call rate *( PAVRP2 + 3PAVRP3 + 3PAVRP4+ 2PBVRP1 + 2PBVRP2( 1-0) + 5PBVRP3 + 5PBVRP4+ 4PCVRP1 + 4PCVRP2 + 2PCVRP3(1-0)ö + 4PCVRP3(1-6) + 7PcvRP4+ 5PDVRP1 + 6PDVRP2 + 8PDVRP3 + 2PDRP4(1—i3)6E + 4PDRP4(1-6)( + 9PDRP4( 1—€) )89Appendix E Expressions for Calculation of SignallingTraffic Using Directory Search AlgorithmThe signalling traffic due to subscriber location using the directory search algorithm can be calculatedas described in Appendix D for the ripple search algorithm.Total access MAN traffic= resident call rate *( 3PARP1 + 5PARP2 + 5PARP3 + 5PARP4+ 4PBRP1 + 6PBRP2 + 6PBRP3 + 6PBRP4+ 413cRP1 + 6PcRP2 + 6PcRP3 + 6PCRP4+ 4PDRP1 + 6PDRP2 + 6PDRP3 + 6PDRP4)+ visitor from backbone call rate *( 3PAvBP1 + 5PAVBP2 + 5PAVBP3 + 5PAVBP4+ 4PBVBP1 + 6PBVBP2 + 6PBVBP3 + 6PBVBP4+ 4Pcve1 + 6PcvBP2 + 6PcvBP3 + 6PcvBP4+ 4PDVBP1 + 6PDVBP2 + 6PDVBP3 + 6PDVBP4)+ visitor from MA call rate *( 3PAvmPt + 5PAVMP2 + 5PAVMP3 + 5PAVMP4+ 4PBvmPi + 6PBVMP2 + 6PBVMP3 + 6PBVMP4+ 4PcvmPi + 6PCVMP2 + 6PCVMP3 + 6PCVMP4+ 4PDvmP1 + 6PDVMP2 + 6PDVMP3 + 6PDVMP4)+ visitor from remote MA call rate *( 3PAvRP1 + 5PAvRP2 + 5PAVRP3 + 5PAVRP4+ 4PBve1 + 6PBVRP2 + 6PBVRP3 + 6PBVRP4+ 4PcvRP1 + 6PcvRP2 + 6PcvRP3 + 6PcvRP4+ 4PDVRP1 + 6PDVRP2 + 6PDVRP3 + 6PDVRP4)Total backbone MAN traffic= resident call rate *PARP2 + 3PARP3 + 3PARP490+ PBRP1 + 2PBRP2 + 3PBRP3 + 4PBRP4+ 2PCRP1 + 3PCRP2 + 4PCRP3 + 5PCRP4+ 2PDRP1 + 3PDRP2 + 4PDRP3 + 5PDRP4)+ visitor from backbone call rate *( PAVBP2 + 3PAVBP3 + 3PAVBP4+ PBVBP1 + 2PBVBP2 + 3PBVBP3 + 4PBVBP4+ 2PCVBP1 + 3PCVBP2 + 4PCVBP3 + 5PCVBP4+ 2PDVBP1 + 3PDVBP2 + 4PDVBP3 + 5PDVBP4)+ visitor from MA call rate *PAvmP2 + 3PAVMP3 + 3PAVMP4+ PBvmPi + 2PBvmP2 + 3PBVMP3 + 4PBVMP4+ 2PcvmPI + 3PcvmP2 + 4PCVMP3 + 5PCVMP4+ 2PnvmPI + 3PDVMP2 + 4PDVMP3 + 5PDVMP4)+ visitor from remote MA call rate *( PAVRP2 + 3PAVRP3 + 3PAVRP4+ PBVRPI + 2PBVRP2 + 3PBVBP3 + 4PBVBP4+ 2PCVBP1 + 3PCVRP2 + 4PcvR133 + 5PcvRP4+ 2PDVRP1 + 3PDVRP2 + 4PDVRP3 + 5PDVRP4)91Appendix F Signalling Traffic Due to Subscriber TrackingThe signalling traffic due to subscriber tracking can be calculated directly from the information inTables 4 and 5.access MAN signalling load due to subscriber location update:= (# BSC boundary crossings per access MAN area) * (2 + 1) slots+ (# access MAN boundary crossings) * (2 + 2 + 1 + 2(5)(1—P1) + 2(2)(Pr+P2)+ 2(1)(P1+P2) ) slots+ (# backbone MAN boundary crossings) / 9 * + 2 + 1 + 2(5)( 1—P1)+ 2(2)(1—P4) + 2(1)(1—P4) ) slots+ (# MA boundary crossings) / 45 * (2 + 2 + 1 + 2(5)(1—P1) + 2(2)P4+ 2(1)P4 ) slotsbackbone MAN signalling load due to subscriber location update:= (# access MAN boundary crossings per backbone MAN area) * (2 + (1—P1)5 + 2(2)(P1+P2)+ 2(1)(P1+P2) ) slots+ (#backbone MAN boundary crossings) * (2 + 2 + 1+ 2(5)(1—Pi) + 2(2)(1—P4) + 2(1)(1—P4) ) slots+ (# MA boundary crossings) / 5 * (2 + 2 + 1 + 2(5)(1—P1) + 2(2)P4+ 2(1)P4 ) slots92Appendix G Derivation of Mean Square Value EquationConsider the random variable X. X can take on the values X1, X2, ... XN with probabilities P1, P2,PN, respectively. The values Xi to XN are themselves random variables, each of which can take onup to M values. We wish to prove the equationE[X2] = E E [n] Pkk=1To help picture this, consider N books, with each book having M pages, and each page having somerandom number written on it. We will pick a book at random and then pick a page at random; the valueX will then be the square of the number on the page. We can write:N ME [X 2 ] = EE niPkik=1 i=1where Xki represents the number on the ith page of the kth book and Pk; represents the probability ofchoosing page i of book k. We can rewrite this asN ME[X 2 ] = EE XLP(i,k I k)Pick=1 i=1where P(i,k I k) represents the conditional probability of choosing page i of book k, given that book kwas chosen. This is then equivalent toE[X 2 ] =^E[X] Pkk=1as required.93References[1] D.C. Cox, "Personal communications - A viewpoint," IEEE Commun. Mag., vol. 28, p. 8, Nov.1990.[2] D.J. Goodman, "Cellular packet communications," IEEE Trans. on Commun., vol. COM-38,pp. 1272-1280, Aug. 1990.[3] J. Regnier, W.H. Cameron, "Personal communication services - the new POTS," in Proc. IEEEGlobal Commun. Conf. GLOBECOM '90, (San Diego, CA), pp. 420-426, Dec. 2-5 1990.[4] A.D. Malyan, R.W. Donaldson, V.C.M. Leung, "A personal communications network architectureusing the IEEE 802.6 MAN," in Proc. IEEE Int. Conf. on Commun., (Chicago, IL), pp. 342.6.1-342.6.5, Jun. 1992.[5] A.D. Malyan, L.J. Ng, R.W. Donaldson, V.C.M. Leung, "A microcellular interconnectionarchitecture for personal communication networks," in Proc. IEEE Int. Veh. Tech. Conf., (Denver,CO), pp. 502-505, May 1992.[6] M. Wizgall, W. Weiss, "The ISDN approach for mobile radio," in XIII International SwitchingSymposium, (Stockholm, Sweden), Jun. 1990.[7] C. Buckingham, G.K. Wolterink, D. Akerberg, "A business cordless PABX telephone system on800 MHz based on the DECT technology ," IEEE Commun. Mag., vol. 29, pp. 105-110, Jan.1991.[8] T. Bowen, G. Gopal, "A scale database architecture for network services," IEEE Commun. Mag.,vol. 29, pp. 52-59, Jan. 1991.[9] K. Murakami, M. Katoh, "Control architecture for next generation communication networks basedon distributed databases," IEEE J. Select. Areas Commun., vol. SAC-7, pp. 418-423, Apr. 1989.[10] M. Fujioka, S. Sakai, "Hierarchical and distributed information handling for UPT," IEEE Network,vol. 4, pp. 50-60, Nov. 1990.[11] R.B. Robrock, "The intelligent network - Changing the face of telecommunications," Proc. ofthe IEEE, vol. 79, pp. 7-20, Jan. 1991.[12] J. Homa, S. Harris, "Intelligent network requirements for personal communications services,"IEEE Commun. Mag., vol. 31, pp. 70-76, Feb. 1992.[13] P. Cherng, K. Baughan, M. Beaudry, "Mobility: An intelligent network in action," in Third IEEConf. on Telecommunications, (Edinburgh, Scotland), pp. 24-28, Mar. 1991.94[14] H. Bauer, J. Jacoby, E. Sable, "Evolution of intelligence in switched networks," in XIIIInternational Switching Symposium, (Stockholm, Sweden), May 1990.[15] B. Materna, B. Vaughan, C. Britney, "Evolution from LAN and MAN access networks towardsthe integrated ATM network," in Proc. IEEE Global Commun. Conf. GLOBECOM '89, (Dallas,TX), pp. 1455-1461, Nov. 1989.[16] A.D. Malyan, V.C.M. Leung, "Network architecture and signalling for urban personal commu-nication," in Proc. IEEE Int. Conf on Select. Topics in Wireless Commun., (Vancouver, BC),pp. 305-30305-3099, Jun. 1992.[17] A.D. Malyan, L.J. Ng, V.C.M. Leung, R.W. Donaldson, "Network architecture and signalling forwireless personal communications," IEEE J. Select. Areas Commun., to appear 1993.[18] C.-C. Chang, T.-H. Chen, "Organizing distributed databases for parallel searching," Journal ofthe Chinese Institute of Engineers, vol. 12, no. 2, pp. 215-221, 1989.[19] D. Motzkin, E.Ivey, "An automated tool for the logical design of distributed relational databases,"in Proc. 12th Structural Methods Conf., (Chicago), 1987.[20] H.F. Korth, A. Silberschatz, Database System Concepts 2nd ed. McGraw Hill, Inc., New York,1991.[21] CCITT Recommendation E.164, "Numbering Plan for the ISDN era," CCITT Blue Book, 1988.ITU, Geneva Switzerland.[22] L.J. Ng, R.W. Donaldson, A.D. Malyan, "Distributed architectures and databases for intelligentpersonal communication networks," in Proc. IEEE Int. Conf on Select. Topics in WirelessCommun., (Vancouver, BC), pp. 300-304, Jun. 1992.[23] C. Wang, J. Wang, "Performance evaluation of a hierarchical location registration and call routingfor personal communications," in Proc. IEEE Mt. Conf. on Commun., (Chicago, IL), pp. 356.6.1-356.6.5, Jun. 1992.[24] L. Kleinrock, Queueing Systems. John Wiley and Sons, Inc., 1975.[25] I. Seskar, S.V. Maric, J. Holtzman, "Rate of location area updates in cellular systems," in Proc.IEEE Int. Veh. Tech. Conf, (Denver, CO), pp. 694-697, May 1992.[26] C.N. Lo, S. Mohan, R.S. Wolff, "An estimate of network database transaction volume to supportpersonal communications services," in Proc. Int. Conf. on Universal Personal Communications,(Dallas, TX), pp. 9.03.1-9.03.6, Sept.-Oct. 1992.95


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items