Local detection of selfish routing behavior in ad hoc networks

Speaker:	Dr. Jonathan Shapiro
		Computer Science and Engineering
		Michigan State University

Title:		"Local detection of selfish routing behavior in
		 ad hoc networks"

Date:		Wednesday, 14 December 2005

Time:		4:00pm- 5:00pm

Venue:		Lecture Theatre H (near lift nos. 27/28)
		HKUST


Abstract:

Reputation mechanisms for detecting and punishing free-riders in ad hoc
networks depend on the local detection of selfish behavior.  Although
naive selfish strategies based on dropping data packets are readily
detected, more sophisticated strategies that manipulate ad hoc routing
protocols present a greater challenge. In this work we develop a method to
distinguish selfish peers from cooperative ones based solely on local
observations of AODV routing protocol behavior. Our approach uses a finite
state machine model of locally observed AODV actions to build a
statistical description of the behavior of each neighbor. We then use
standard statistical tests and clustering techniques to separate neighbors
into behavior classes, which are then classified as either selfish or
cooperative. We use these ideas to develop an on-line detection algorithm
suitable for low mobility environments. Through simulations, we evaluate
our algorithm against an adversary who attempts to operate as selfishly as
possible while still evading detection. Under reasonable assumptions about
the punishment regime used in conjunction with our, our algorithm forces
such an adversary to limit its selfish behavior to a level that is
statistically indistinguishable from cooperative behavior.



******************
Biograhpy:

Jonathan Shapiro is an assistant professor of Computer Science and
Engineering at Michigan State University. He received a BA in Physics from
Columbia University and an MS and PhD in Computer Science from the
University of Massachusetts at Amherst. His primary research interests
concern the application of economics to problems in networks and
distributed systems, including the use of pricing mechanisms for
distributed resource allocation and the role of incentives in promoting
cooperation among self-interested network users. Other research interests
include congestion control, privacy and security, electronic commerce, and
peer-to-peer networking.