This project will develop a new methodology, algorithms, and models for dynamic flow equilibria in networked systems, with emphasis on two specific real-world networking applications ? vehicular traffic network modeling and efficiency analysis, and routing and flow control in data communication networks. The first research goal of this project involves appropriate modeling of dynamic flow problems in networks with self-interested agents, and understanding the properties of the equilibria for these problems. The other major research goal is to specifically study the application of dynamic flows to vehicular traffic networks and data communication networks. The research goals of this project will be achieved by an interdisciplinary but closely-integrated effort bringing together techniques from game theory, algorithm design, optimization, and real-world network simulation. Intellectual Merit: The novelty of this project is that it provides a holistic understanding of the theoretical, algorithmic, and implementation issues of dynamic flow equilibria in networked systems, particularly in the context of vehicular traffic and data communication networks. This research explicitly takes into account the non-negligible travel time of flows in a network, and its variation as a function of the time-varying congestion in the network ? this results in new notions of flow equilibria that are fundamentally different and significantly more complex than those for non time-varying flows. The models used in the project are based on emerging concepts in game theory, optimization theory, and vehicular traffic modeling, and the project is expected to result in the development of a new algorithmic framework for studying dynamic flow equilibria in networks. In addition, this research will contribute techniques for dynamic flow equilibria study to many interested research communities, including transportation, algorithmic game theory, economics, sociology, and multi-agent systems, and facilitate the transfer of techniques between disciplines. Broader Impact: This project will facilitate better network engineering, particularly in the context of transportation and communication networks. The implementation of the models developed by this research in specific disciplines (vehicular transportation and data communication networks) will have significant societal impacts, such as (i) enabling more efficient analysis and provisioning of transportation networks, leading to lower travel delays, and (ii) faster Internet access and download speeds due to more efficient routing and flow control protocols. This research will help rethink and possibly redesign important core components of the Internet through better flow control and routing choices. The findings of this research will be integrated into several different courses, and in Interactive Learning Modules aimed at attracting undergraduate and high-school students to research careers. Special efforts will be made to encourage participation of undergraduate and minority students.
Dynamic flow equilibrium questions arise in a wide range of engineering applications that involve decision-making over time by self-interested agents. The notion of dynamic flow equilibrium takes into account the non-negligible travel time of flows in a network, and their variation as a function of the time-varying congestion in the system. As part of this project, we have explored some key theoretical, algorithmic, and implementation issues of dynamic flow and other related equilibria in general networked systems, and in the context of vehicular traffic and data communication networks in particular. For transportation networks, we characterized the inefficiency of dynamic traffic networks for different variants of the single bottleneck model. We have also obtained analytical characterizations of the notion of dynamic user equilibrium in multiple origin-destination transportation networks, and obtained methods through which such equilibria can be computed efficiently. We have further formulated the question of dynamic system optimal traffic flows in transportation networks, and developed algorithms that can efficiently compute the optimal flows. We have demonstrated the effectiveness of our solutions through extensive simulation studies involving realistic transportation networks. For communication networks, we studied the existence and efficiency questions of inter-domain traffic flows in the Internet, focusing on price-driven next-hop routing strategies. We have established through theoretical analysis that selfish per-unit pricing of traffic by Internet Service Providers (ISPs) can result in efficient equilibria in the network, under fairly general assumptions in the network topologies. Through simulations on Internet-like topologies, we have demonstrated that best-response based traffic pricing and forwarding by ISPs result in efficient data traffic flows in a vast majority of cases. This project has led to several publications in internationally reputed journals and conferences, simulation code, involvement of undergraduates in research, and a development of a new course in Algorithmic Game Theory.
