Hash-based paging and location update using bloom filters: a paging algorithm that is best suitable for IPv6

ABSTRACT

We develop and analyze a hash-based paging and location update technique that reduces the paging cost in cellular systems. By applying a Bloom filter, the terminal identifier field of a paging message is coded to page a number of terminals concurrently. A small number of terminals may wake up and send what we call "false location updates" although they are not being paged. We compare the total number of paging and false location update messages with the cost of the standard paging procedure. Fortunately, the false location update probabilities can be made very small, and important bandwidth gains can be expected. The larger the size of the terminal identifier, the less probable are false location updates. Therefore, hash-based paging especially shows promise for IP paging in mobile IPv6 networks with 128-bit mobile host addresses.

REFERENCES

• 1: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 2: {2} A.T. Campbell et al., Design, implementation, and evaluation of cellular IP, IEEE Personal Communications, Special issue on IP-based mobile telecommunications networks (June/July 2000).
• 3: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.254-265, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 4: {4} D. Johnson, C. Perkins and J. Arkko, Mobility support in IPv6, Internet draft, draft-ietf-mobileip-ipv6-19.txt (work in progress, October 2002).
• 5: {5} J. Kempf, Dormant mode host alerting (IP paging) problem statement, RFC 3132 (June 2001).
• 6: {6} C. Perkins, IP mobility support, RFC 3344 (August 2002).
• 7: Ramachandran Ramjee , Kannan Varadhan , Luca Salgarelli , Sandra R. Thuel , Shie-Yuan Wang , Thomas La Porta, HAWAII: a domain-based approach for supporting mobility in wide-area wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.3, p.396-410, June 2002 [doi>10.1109/TNET.2002.1012370]
• 8: R. Ramjee , L. Li , T. La Porta , S. Kasera, IP paging service for mobile hosts, Proceedings of the 7th annual international conference on Mobile computing and networking, p.332-345, July 2001, Rome, Italy [doi>10.1145/381677.381708]
• 9: Xiaowei Zhang , Javier Gomez Castellanos , Andrew T. Campbell, P-MIP: paging extensions for mobile IP, Mobile Networks and Applications, v.7 n.2, p.127-141, April 2002 [doi>10.1023/A:1013774805067]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Standards (e.g., TCP/IP)

General Terms:
Management, Performance

Keywords:
IP paging, MIPv6, bloom filters, concurrent paging, false location update