This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).
This project investigates unstructured dynamic overlay networks (unstructured networks): a type of computer network formed from interactions among constantly changing strategic (i.e., self- interested but rational) users. These users rely on each other for transferring and finding data, and they form unstructured networks based on their own cost-benefit tradeoffs by dynamically introducing/removing network communications links and performing distributed resource allocations on top of the Internet. Unstructured networks carry the majority of Internet traffic due to the prevalence of the applications they support. Such applications include file sharing (e.g., BitTorrent), user-assisted media streaming, video-on-demand, and voice-over-IP (e.g., Skype). These networks also include selfish data-routing overlays (where users choose routes independently), and multiple self-organized data-routing overlays. The fundamental interactions/conflicts between users within each unstructured network and among networks, and their interactions with the Internet, can result in drastically unstable states, inefficient resource usage, low performance of the applications they support, and adverse impact on Internet Service Providers. To address these problems, the project is developing effective mechanisms to ensure the stability and efficiency of unstructured networks, and providing seamless interoperation with the Internet architecture and service providers. Relying on a combination of optimization and game theory, stochastic modeling, and distributed algorithm/mechanism design, this research develops theoretical foundations/methodologies for quantifying the interaction dynamics within/among unstructured networks, and between unstructured networks and the Internet. Additionally, the project provides design principles/algorithms for application/network designers and service providers for meeting increasingly rich user requirements and will provide guidance for the design of future Internet architecture.
