Method for determining placement of internet taps in wireless neighborhood networks

• US 8,315,196 B2
• Filed: 02/17/2004
• Issued: 11/20/2012
• Est. Priority Date: 02/17/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Qiu, Lili, Jain, Kamal, Chandra, Ranveer, Mahdian, Mohammad
• Primary Examiner(s): Wu, Jianye
• Application Number:
  US10/780,262
• Publication Number:
  US 20050180329A1
• Time in Patent Office: 3,199 Days
• Field of Search: 370/238
• US Class Current: 370/312
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 88/16 Gateway arrangements
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

Disclosed is a method for determining the placement of ITAPs in wireless neighborhood networks. The method disclosed provides for efficient integration of multi-hop wireless networks with the Internet by placing ITAPs at strategic locations. Initially the method provides for the formulation of the ITAP placement problem under three wireless models. For each model, methods are developed to efficiently place ITAPs in the networks. The methods aim to minimize the number of required ITAPs while guaranteeing users'"'"' bandwidth requirements. Next, a fault tolerance version of the placement method is presented that provides bandwidth guarantees in the presence of failures. Finally the methods are extended to take into account variable traffic demands by developing an approximation algorithm to simultaneously optimize ITAP placement based on demands over multiple periods.

Claims

1. A method for reducing potential placement locations of Internet Transit Access Points (ITAPs) in a network by identifying equivalence classes of nodes in the network which may be serviced by the same ITAP, the method comprising:

(a) accepting equivalence class information for the network, wherein the network is a multi-hop wireless mesh network; and

(b) employing a processor executing computer-executable instructions to perform acts of;

(i) determining whether a first equivalence class is covered by a second equivalence class; and

(ii) eliminating the first equivalence class from consideration as a potential placement location for the ITAP if the first equivalence class is covered by the second equivalence class.

2. The method of claim 1 further comprising:

repeating the determining and eliminating until all equivalence classes covered by the second equivalence class have been identified.

3. A computer-readable storage medium, which does not consist of a modulated data signal, and which comprises computer-executable instructions that, when executed, perform a method for reducing potential placement locations of access points in a network by identifying equivalence classes of nodes in the network which may be serviced by the same access point, the method comprising:

accepting equivalence class information for the network, wherein the network is a multi-hop wireless mesh network;

determining whether a first equivalence class is covered by a second equivalence class; and

eliminating the first equivalence class from consideration as a potential placement location for the access point if the first equivalence class is covered by the second equivalence class.