Method and apparatus for preferred roaming list compression

• US 6,901,395 B2
• Filed: 11/05/2001
• Issued: 05/31/2005
• Est. Priority Date: 11/05/2001
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Rezaiifar, Ramin, Bender, Paul E., Quick, Roy Franklin Jr., Cooper, Rotem, Andrus, Don Nielsen
• Primary Examiner(s): Le, Uyen
• Assistant Examiner(s): Thai, Hanh
• Application Number:
  US10/011,961
• Publication Number:
  US 20030088539A1
• Time in Patent Office: 1,303 Days
• Field of Search: 707/1, 370381-383, 370392-393, 370/477, 370/313, 709/247, 708/20, 711/212
• US Class Current: 1/1
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 8/245 from a network towards a terminal
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

Techniques for efficient storage and retrieval of Preferred Roaming Lists are disclosed. In one aspect, PRL entries are stored in two tables. One table contains records that are common to two or more PRL entries. Another table stores any information that is unique to a PRL entry, as well as an indicator of which common record is associated with it. The common record is concatenated with the unique information to generate the uncompressed PRL entry. Various other aspects of the invention are also presented. These aspects have the benefit of reducing the memory requirements for storing a PRL. In addition, time required to download the compressed PRL is reduced.

Claims

1. A processor implemented method of generating a compressed preferred roaming list (PRL), comprising:

generating a subnet address by performing a bitwise AND operation on a network identification (ID) and a subnet mask, the subnet address consisting of a plurality of most significant bits and a plurality of least significant bits, the most significant bits of the subnet address representing a common part of a subnet to be factored out;

storing the most significant bits of the subnet address in a subnet table;

storing the least significant bits of the subnet address in a system table;

factoring out at least one set of data common to two or more subnets;

storing said at least one set of data common to said two or more subnets in the subnet table;

generating an indicator for accessing said at least one set of data; and

storing the indicator in the system table.

2. The method of claim 1, further comprising the step of storing remaining data not common to said two or more subnets in the system table.

3. The method of claim 1, further comprising the step of storing remaining data not common to said two or more subnets in a symbol table.

4. The method of claim 1, wherein the step of factoring out at least one set of data common to two or more subnets comprises searching for a common characteristic.

5. The method of claim 4, wherein the common characteristic comprises a shared subnet address.

6. The method of claim 4, wherein the common characteristic comprises a shared frequency.

7. The method of claim 1, wherein the network ID consists of 128 bits.

8. The method of claim 7, wherein the subnet mask consists of a first predetermined number of bits each assigned a bit value of 1 and a second predetermined number of bits each assigned a bit value of 0, the sum of the first predetermined number of bits and the second predetermined number of bits equaling 128 bits.

9. The method of claim 1, wherein the system table comprises a subnet tab indicating whether there are any sets of data common to said two or more subnets.

10. The method of claim 9, wherein the subnet tab is 0 if there is no set of data common to said two or more subnets.

11. A processor implemented method of accessing a compressed preferred roaming list (PRL) resulting from generating a subnet address by performing a bitwise AND operation on a network identification (ID) and a subnet mask, the subnet address consisting of a plurality of most significant bits and a plurality of least significant bits, the most significant bits of the subnet address representing a common part of a subnet to be factored out, storing the most significant bits of the subnet address in a subnet table, storing the least significant bits of the subnet address in a system table, factoring out at least one set of data common to two or more subnets, storing said at least one set of data common to said two or more subnets in the subnet table, generating an indicator for accessing said at least one set of data, and storing the indicator in the system table, the method comprising:

retrieving from the system table remaining data not common to said two or more subnets;

retrieving from the system table the indicator for accessing said at least one set of data common to said two or more subnets;

retrieving from the subnet table said at least one set of data common to said two or more subnets corresponding to the indicator; and

concatenating said at least one set of data common to said two or more subnets with said remaining data to form a complete subnet record.

12. A processor implemented method of accessing a compressed preferred roaming list (PRL) resulting from generating a subnet address by performing a bitwise AND operation on a network identification (ID) and a subnet mask, the subnet address consisting of a plurality of most significant bits and a plurality of least significant bits, the most significant bits of the subnet address representing a common part of a subnet to be factored out, storing the most significant bits of the subnet address in a subnet table, storing the least significant bits of the subnet address in a system table, factoring out at least one set of data common to two or more subnets, storing said at least one set of data common to said two or more subnets in the subnet table, generating a subnet tag for indicating whether there are any sets of data common to said two or more subnets and for accessing said at least one set of data, and storing the subnet tag in the system table, the method comprising:

retrieving the subnet tag from the system table;

determining whether the subnet tag is 0;

if the subnet tag is 0, performing the steps of;

retrieving from the system table data not common to said two or more subnets; and

forming a complete subnet record by filling in the subnet record with data not common to said two or more subnets;

if the subnet tag is not 0, performing the steps of;

retrieving from the subnet table said at least one set of data common to said two or more subnets corresponding to the subnet tag;

retrieving from the system table remaining data not common to said two or more subnets; and

concatenating said at least one set of data common to said two or more subnets with said remaining data to form a complete subnet record.

13. The method of claim 12, wherein the step of retrieving from table said at least one set of data common to said two or more subnets corresponding to the subnet tag comprises:

locating the subnet tag in the subnet table;

retrieving from the subnet table a subnet common length indicator to determine how much amount of said at least one set of data common to said two or more subnets to retrieve;

retrieving from the subnet table said amount of said at least one set of data common to said two or more subnets according to the subnet common length indicator.

14. A processor implemented method of accessing a compressed preferred roaming list (PRL) resulting from generating a subnet address by performing a bitwise A.N.D operation on a network identification (ID) and a subnet mask, the subnet address consisting of a plurality of most significant bits and a plurality of least significant bits, the most significant bits of the subnet address representing a common part of a subnet to be factored out, storing the most significant bits of the subnet address in a subnet table, storing the least significant bits of the subnet address in a system table, factoring out at least one set of data common to two or more subnets, storing said at least one set of data common to said two or more subnets in the subnet table, generating a subnet common offset index for accessing said at least one set of data, and storing the subnet common offset index in the system table, the method comprising:

retrieving from the system table a system record comprising a subnet least significant bit length indicator, a subnet least significant bit field, and the subnet common offset index;

retrieving from the subnet table a subnet record comprising a subnet common length indicator and a subnet common field corresponding to the subnet common offset index; and

concatenating the subnet common field with the subnet least significant bit field to form a complete subnet field.

15. The method of claim 14, wherein the step of retrieving from the subnet table a subnet record comprising a subnet common length indicator and a subnet common field corresponding to the subnet common offset index comprises:

accessing the subnet common length indicator with a pointer representing the subnet common offset index into the subnet table; and

retrieving a number of bits of the subnet common field according to the subnet common length indicator.

16. The method of claim 14, wherein the subnet common offset index is 0 if no sets of data are common to said two or more subnets.