Ph.D Thesis

Ph.D StudentLandau Alexander
SubjectEfficient Schemes for Estimating the Number of Affected
Nodes in Very Large Networks
DepartmentDepartment of Computer Science
Supervisor PROF. Reuven Cohen
Full Thesis textFull thesis text - English Version


In this thesis, we present a generic scheme that we call NATO! (Not All aT Once!) for estimating the size of a group of nodes affected by the same event in a large-scale network, such as a grid, a sensor network or a wireless broadband access network, while receiving only a small number of feedback messages from this group. Using the proposed scheme, a centralized gateway analyzes the transmission times of these feedback messages, defines a likelihood function for them, and then uses the Newton-Raphson method to find the number of affected nodes for which this function is maximized. We present a complete mathematical analysis for the precision of the proposed algorithm and provide tight upper and lower bounds for the estimation error. These bounds allow us to improve the precision of our estimation, bringing the error very close to 0.

NATO! has many interesting applications. For example, in an 802.16-like mobile wireless network, the base station can use it to discover a DoS attack. In grid networks, a management entity is typically responsible for thousands of nodes, many of which can fail at once due to a single event. NATO! can substantially reduce the number of failure reports received by a management station in such cases.

We then consider a huge hierarchical sensor network consisting of millions of sensors. We address the problem of how a centralized gateway can estimate the number of sensors affected by a certain event. We evaluate the use of NATO! in such a network and propose a scheme called H-NATO! (Hierarchical NATO!) for solving this problem in the most efficient way. We show that the error of the new scheme is very small even if the number of sensors experiencing an event is several millions.

Another application of NATO! we consider is partially reliable streaming multicast. Streaming multicast is one of the most important transport layer services in future broadcast wireless networks. This service enables the delivery of real-time voice and video applications to an almost unlimited number of mobile devices, by taking advantage of a base station's ability to transmit a single packet to all the nodes in its cell. Using NATO!, we show how the base station can collect information regarding the channel quality of thousands of receivers, and choose the best coding and transmission parameters based on this information.