Location information recovery and management for mobile networks

• US 7,113,795 B2
• Filed: 01/30/2004
• Issued: 09/26/2006
• Est. Priority Date: 09/30/1999
• Status: Expired due to Fees

• Current Assignee: University of Iowa Research Foundation
• Original Assignee: University of Iowa Research Foundation
• Inventors: Krishnamurthi, Govindarajan, Somani, Arun K.
• Primary Examiner(s): Trinh, Sonny
• Assistant Examiner(s): Torres, Marcos L.
• Application Number:
  US10/769,456
• Publication Number:
  US 20040185871A1
• Time in Patent Office: 970 Days
• Field of Search: 4554561-4566, 455/457, 455/414.1, 455/414.2, 455/560, 709/205, 709/217, 709/238, 707/10, 707/201, 707/204
• US Class Current: 455/456.1
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• CPC Class Codes: H04W 60/04 using triggered events
• CPC Class Codes: H04W 8/12 between location registers or mobility servers
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Systems and methods for recovering and managing location information in mobile communication networks using a fast recovery protocol and load balanced query and update processes. According to the fast recovery protocol, if a location update processor does not receive a message from a global database server acknowledging receipt by the global database server of a location update message after a predetermined retry interval has elapsed since the location update message was sent by the location update processor, the location update processor sends a location update retry message after each predetermined retry interval elapses until the location update processor receives an acknowledgement message from the global database server. The global database server can use the location update retry messages and the predetermined retry interval to recover from a database or link failure. The recovery period using the fast recovery protocol is bounded by the predetermined retry interval. The fast recovery protocol can also be used in a system having a distributed location information database architecture. The load balanced query and update processes can be used to query and update, respectively, the databases of the distributed location information database architecture.

Claims

1. In a distributed database system having n database servers, D₁, . . . , D_n, arranged in a logical ring, a method of updating k of the database servers, D_γ

1, . . . , D<sub>γ

k</sub>, referred to by a placement vector Γ

=(γ

₁, . . . , γ

_k), wherein γ

i ε

{1, . . . , n} is the index of the ith database server updated by the method, the method comprising;

selecting γ

₁ from the set (1, . . . , n);

for i=1, . . . , k−

1, selecting γ

_i+1 according to γ

_i⊕

└

n/k┘

+a_i, wherein;

⊕

is modulo addition defined over the set (1, 2, . . . , n);

displacement vector â

=(a₁, . . . , a_k) is a binary vector having a Hamming weight of β

; and

β

=n−

└

n/k┘

*k; and

updating the k database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector Γ

=(γ

₁, . . . , γ

_k), with updated information.

2. The method of claim 1, wherein the database servers are location database servers for storing location information about a mobile device.

3. The method of claim 2, wherein updating the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, includes updating the k location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector Γ

=(γ

₁, . . . , γ

_k, with current location information for a mobile device.

4. The method of claim 3, wherein updating the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, includes transmitting location update messages to the k location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>.

5. The method of claim 4, further comprising, before transmitting location update messages to the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, deleting any location information previously stored in the n location database servers, D₁, . . . , D_n, for the mobile device.

6. The method of claim 4, wherein γ

₁ is selected randomly using a uniform distribution over the set (1, 2, . . . , n).

7. The method of claim 6, further comprising, before transmitting location update messages to the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, determining if all of the location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k) are accessible, and if all of the location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k), are not accessible, selecting a different placement vector, Γ

=(γ

₁, . . . , γ

_k).

8. The method of claim 7, wherein if no placement vector, Γ

=(γ

₁, . . . , γ

_k), can be found in which all the location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k), are accessible, selecting the placement vector, Γ

=(γ

₁, . . . , γ

_k), having the most number of location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, that are accessible.

9. In a distributed database system having n database servers, D₁, . . . . D_n, arranged in a logical ring for storing information about a first group of items in k₁, of the database servers and for storing information about a second group of items in k₂ of the database servers, wherein k₁>

k₂, a method of querying the database servers for information about a given item, the method comprising;

selecting a first database server D_i;

determining in parallel if any of ┌

n/k₁┐

successive database servers, D_i, D_i+1, . . . , D<sub>i⊕

┌

n/k1┐</sub>

, on the logical ring contain information about the given item;

if at least one of the ┌

n/k₁┐

successive database servers, D_i, . . . , D<sub>i⊕

┌

n/k1┐</sub>

, does not contain information about the given item then determining in parallel if any of the

next (┌

n/k₁┐

−

┌

n/k₂┐

) successive database servers, D<sub>i⊕

┌

n/k1┐

⊕

1</sub>, . . . , D<sub>i⊕

┌

n/k2┐</sub>

, on the logical ring contain information about the given device; and

if at least one of the next (┌

n/k₂┐

−

┌

n/k₁┐

) successive database servers,

D<sub>i⊕

┌

n/k1┐

⊕

1</sub>, . . . , D<sub>i⊕

┌

n/k2┐</sub>

, does not contain information about the given item, then until information for the given item is found or until all the database servers D₁, . . . , D_n, have been checked, determining in parallel if successive groups of ┌

n/k₂┐

database servers, D<sub>i⊕

(j*┌

n/k2┐

)⊕

1</sub>, . . . , D<sub>i⊕

(j+1)*┌

n/k2┐</sub>

, on the logical ring contain information for the given item wherein j represents the jth group of ┌

n/k₂┐

database servers that are checked.

10. The method of claim 9, wherein the database servers are location database servers for storing location information about a first group of mobile device in k₁ of the location database servers and for storing location information about a second group of mobile devices in k₂ of the location database servers, and wherein the method queries the location database servers for location information about a given mobile device.