Coin handling – Deliverer – Delivery of a distinct number of plural coins from a single...
Reexamination Certificate
1998-12-28
2001-05-01
Trost, William G. (Department: 2746)
Coin handling
Deliverer
Delivery of a distinct number of plural coins from a single...
C455S418000, C455S422100, C455S435100
Reexamination Certificate
active
06224477
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to communication networks and, more particularly, to a method for ordering the records of subscribers to wireless communication networks, wherein the records are stored in location databases at Visitor Location Registers (VLR's) and/or a Home Location Register (HLR) of the communication network.
BACKGROUND
Public Land Mobile Networks (PLMN), such as the Global System for Mobile Communications (GSM), are designed as the wireless extension of the Public Switched Telephone Network (PSTN). Subscribers of a PLMN receive voice and data services while they are traveling within the network coverage area. To guarantee the timely and accurate delivery of incoming calls to a subscriber, a PLMN must be able to track the current location of each mobile station, or terminal. This tracking procedure is commonly referred to as location management.
Location management entails the recordation of up-to-date information on the location of each mobile terminal in a distributed network of location databases. Each mobile terminal is required to periodically report its location to the network. On receiving such information, the network updates its records in one or more location databases. When a call for such a mobile terminal arrives at a subsequent time, the location information of the mobile terminal will be retrieved from the location databases and the call is delivered accordingly.
As the number of subscribers using mobile terminals increases, the number of subscriber records that must be stored and updated in location databases increases, resulting in increased processing load on telecommunications switches and databases and increased time to access such subscriber records. As such processing load and access time increases, costs for providing such services increases, and network capacity and subscriber satisfaction diminish.
To alleviate the high processing load and access time, subscriber records are typically organized in a location database structured as a “binary tree”. Conventionally, there are a number of types of binary trees available for so organizing records. For example, an optimal, or ideal, binary tree may be generated using well-known techniques wherein records with the highest access rate are placed closest to the root of the tree such that the cost of searching for such records is absolutely minimized. The cost of generating such an optimal tree is, however, generally prohibitive if the number of records to be organized is very large.
Alternatively, a relatively simple binary tree may be randomly generated which requires that subscriber records be ordered as a data structure using as an index the identity of the subscriber's mobile terminal. If a subscriber population is large, the subscriber records may first be partitioned into a number of subsets using a “hash” function. For example, the first 8 bits of the subscriber identity may be used to partition all the subscriber records into 2
8
, or 256, subsets. A binary tree is then generated within each subset of subscriber records. In a randomly generated binary tree, the relative position of a subscriber record depends only on the chronological order in which the records are inserted into the tree. A newly added subscriber record must be positioned at the “bottom” of the tree regardless of the rate with which the record is accessed. As a result of the order in which subscribers are added to the tree, an early subscriber record with a relatively low access rate may be located “higher” in the binary tree and, thus, more economically accessible, than a later subscriber record having a higher access rate. Such a tree, while much less costly to generate than an ideal tree, is generally much less efficient and, therefore, much more expensive to use, than the aforementioned ideal tree in which subscribers having a high access rate are located generally higher and more accessibly in the tree.
The foregoing randomly generated binary tree may be “balanced” to locate an approximately equal number of subscribers on each side of the tree. The access cost of a binary tree, however, may not necessarily decrease by being balanced and, furthermore, may still require more time to access subscribers with high access rates than subscribers with lower access rates. The efficiency of a balanced binary tree is thus not near that of an ideal binary tree.
In yet another binary tree, the subscriber records are first arranged in decreasing order of access rate. The subscriber records are then inserted into the binary tree according to such order. This method guarantees that highly accessed subscriber records are located at the top of the tree. However, this method may generate an extremely unbalanced tree which may not result in lower overall access cost compared to the randomly generated binary tree.
While there are further variations on how a binary tree may be generated using conventional techniques, as exemplified above, each such binary tree is uneconomical with respect to the cost of either generating it or of using it.
Accordingly, a continuing search has been directed to methods for generating a binary tree which can quickly and efficiently access subscriber records in location databases and that is, therefore, more economical to generate and to use than is possible with conventional binary trees.
SUMMARY
The present invention, accordingly, provides a method for generating a binary tree used by a location database by stored in at least one of a Visitor Location Register (VLR) or a Home Location Register (HLR) of a wireless communications network by ordering the subscriber records in subsets according to the access rates of the records. Records within the respective subsets are then ordered in a middle-rootage order based on the subscriber ID of each subscriber record. The subscriber records are then inserted into a binary tree in subset order beginning with the subset containing subscriber records having the highest access rate. This method enables subscriber records to be more economically stored and used than is possible using conventional binary trees and, thereby, increases network capacity.
REFERENCES:
patent: 5418947 (1995-05-01), Hsu et al.
patent: 5583850 (1996-12-01), Snodgrass et al.
patent: 5761500 (1998-06-01), Gallant et al.
patent: 5850603 (1998-12-01), Lantto et al.
patent: 5941955 (1999-08-01), Wilby et al.
patent: 5956717 (1999-09-01), Kraay et al.
patent: 6026291 (1999-09-01), Carlsson et al.
patent: 6091952 (2000-07-01), Xu et al.
patent: 6097942 (2000-08-01), Laiho
patent: 6104931 (2000-08-01), Havinis et al.
Ho Joseph S. M.
Liu Julie Y. C.
Xu Jim
Carr & Storm, L.L.P.
Nortel Networks Limited
Tran Congvan
Trost William G.
LandOfFree
Method for ordering subscriber records of wireless... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for ordering subscriber records of wireless..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for ordering subscriber records of wireless... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2517640