Method for determining placement of internet taps in wireless neighborhood networks
First Claim
1. A method for determining placement of internet taps (ITAPS) in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
- accepting connectivity information for the network, comprising link capacity constraints, node capacity constraints, node demands for flow, and a set of potential ITAPs to be opened;
iterating through the set of potential ITAPs to be opened;
selecting an ITAP, from the set of potential ITAPs to be opened, to be added to a set of currently open ITAPs, wherein the selected ITAP increases the node demands satisfied when opened together with ITAPs in the set of currently open ITAPs;
adding the selected ITAP to the set of currently opened ITAPs;
repeating the iterating, selecting, and adding until all the node demands are satisfied; and
implementing the set of currently opened ITAPs in the network.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
27 Claims
-
1. A method for determining placement of internet taps (ITAPS) in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
accepting connectivity information for the network, comprising link capacity constraints, node capacity constraints, node demands for flow, and a set of potential ITAPs to be opened;
iterating through the set of potential ITAPs to be opened;
selecting an ITAP, from the set of potential ITAPs to be opened, to be added to a set of currently open ITAPs, wherein the selected ITAP increases the node demands satisfied when opened together with ITAPs in the set of currently open ITAPs;
adding the selected ITAP to the set of currently opened ITAPs;
repeating the iterating, selecting, and adding until all the node demands are satisfied; and
implementing the set of currently opened ITAPs in the network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A computer-readable medium containing instructions for performing a method for determining placement of internet taps (ITAPs) in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
accepting connectivity information for the network, comprising link capacity constraints, node capacity constraints, node demands for flow, and a set of potential ITAPs to be opened;
iterating through the set of potential ITAPs to be opened;
selecting an ITAP, from the set of potential ITAPs to be opened, to be added to a set of currently open ITAPs, wherein the selected ITAP increases the node demands satisfied when opened together with ITAPs in the set of currently open ITAPs;
adding the selected ITAP to the set of currently opened ITAPs;
repeating the iterating, selecting, and adding until all the node demands are satisfied; and
implementing the set of currently opened ITAPs in the network.
-
-
17. A method for determining placement of internet taps (ITAPs) in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
accepting connectivity information for the network, comprising link capacity constraints, node capacity constraints, node demands for flow, a set of potential ITAPs to be opened, and a set of time intervals;
iterating through the set of potential ITAPs to be opened;
iterating through the set of time intervals;
for each time interval, computing a total of node demands satisfied by adding an ITAP from the set of potential ITAPs to be opened, to a set of currently open ITAPs;
selecting the ITAP that results in the largest increase in the sum of satisfied node demands over all time intervals;
adding the selected ITAP to the set of currently opened ITAPs;
repeating the iterating, selecting, and adding until the node demands at all time intervals are satisfied; and
implementing the set of currently opened ITAPs in the network.
-
-
18. A computer-readable medium containing instructions for performing a method for determining placement of internet taps (ITAPs) in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
accepting connectivity information for the network, comprising link capacity constraints, node capacity constraints, node demands for flow, a set of potential ITAPs to be opened, and a set of time intervals;
iterating through the set of potential ITAPs to be opened;
iterating through the set of time intervals;
for each time interval, computing a total of node demands satisfied by adding an ITAP from the set of potential ITAPs to be opened, to a set of currently open ITAPs;
selecting the ITAP that results in the largest increase in the sum of satisfied node demands over all time intervals;
adding the selected ITAP to the set of currently opened ITAPs;
repeating the iterating, selecting, and adding until the node demands at all time intervals are satisfied; and
implementing the set of currently opened ITAPs in the network.
-
-
19. A method for determining placement of internet taps (ITAPs) in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
accepting connectivity information for the network, comprising link capacity constraints, node capacity constraints, node demands for flow, a set of potential ITAPs to be opened, and a set of time intervals;
iterating through the set of potential ITAPs to be opened;
selecting an ITAP, from the set of potential ITAPs to be opened, that satisfies the largest node demand;
adding the selected ITAP to the set of currently opened ITAPs, wherein each node'"'"'s demand is the node'"'"'s maximum demand over all time intervals;
repeating the iterating, selecting, and adding until the node demands at all time intervals are satisfied; and
implementing the set of currently opened ITAPs in the network.
-
-
20. A computer-readable medium containing instructions for performing a method for determining placement of internet taps (ITAPS) in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
accepting connectivity information for the network, comprising link capacity constraints, node capacity constraints, node demands for flow, a set of potential ITAPs to be opened, and a set of time intervals;
iterating through the set of potential ITAPs to be opened;
selecting an ITAP, from the set of potential ITAPs to be opened, that satisfies the largest node demand;
adding the selected ITAP to the set of currently opened ITAPs, wherein each node'"'"'s demand is the node'"'"'s maximum demand over all time intervals;
repeating the iterating, selecting, and adding until the node demands at all time intervals are satisfied; and
implementing the set of currently opened ITAPs in the network.
-
-
21. A method for reducing potential placement locations of internet taps (ITAPs) in a multi-hop wireless mesh network by identifying an equivalence class of nodes in the network which are reachable via a wireless link of the network, the method comprising:
-
accepting connectivity information for the network;
for each node in the network determining the set of nodes by which the node is reachable via the wireless link;
defining an equivalence class as a set of nodes reachable via the wireless link.
-
-
22. A computer-readable medium containing instructions for performing a method for reducing potential placement locations of internet taps (ITAPs) in a multi-hop wireless mesh network by identifying an equivalence class of nodes in the network which are reachable via a wireless link of the network, the method comprising:
-
accepting connectivity information for the network;
for each node in the network determining the set of nodes by which the node is reachable via the wireless link;
defining an equivalence class as a set of nodes reachable via the wireless link.
-
-
23. A method for reducing potential placement locations of internet taps (ITAPs) in a multi-hop wireless mesh network by identifying equivalence classes of nodes in the network which may be serviced by the same ITAP, the method comprising:
-
accepting equivalence class information for the 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 an ITAP if the first equivalence class is covered by the second equivalence class. - View Dependent Claims (24)
-
-
25. A computer-readable medium containing instructions for performing a method for reducing potential placement locations of internet taps (ITAPs) in a multi-hop wireless mesh network by identifying equivalence classes of nodes in the network which may be serviced by the same ITAP, the method comprising:
-
accepting equivalence class information for the 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 an ITAP if the first equivalence class is covered by the second equivalence class.
-
-
26. A method for supporting multi-path routing in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
assigning network traffic, by a source node, to multiple network paths, wherein the assignment is made according to a specified probability;
selecting one of the network paths;
routing the network traffic along the selected path, wherein the source node specifies the end-to-end path; and
forwarding the network traffic, by each intermediate node, wherein the forwarding is done according to the specified path.
-
-
27. A computer-readable medium containing instructions for performing a method for supporting multi-path routing in a multi-hop wireless mesh network, wherein the network employs a contention based media access control (MAC) protocol and the network comprises nodes and links between the nodes, the method comprising:
-
assigning network traffic, by a source node, to multiple network paths, wherein the assignment is made according to a specified probability;
selecting one of the network paths;
routing the network traffic along the selected path, wherein the source node specifies the end-to-end path; and
forwarding the network traffic, by each intermediate node, wherein the forwarding is done according to the specified path.
-
Specification