Columbia University Joint Computer Science and Electrical Engineering Networking Seminar Series

Connectivity and Coverage Problems in Emerging Networks

Professor Arun Sen

Computer Science and Engineering Program
School of Computing, Informatics and Decision Systems Engineering
Arizona State University

Friday September 17, 2010, 14:30-15:30, CS Conference Room

Abstract: Efforts are currently underway in the U.S. Air Force to utilize a heterogeneous set of physical links (RF, Optical/Laser and SATCOM) to interconnect a set of terrestrial, space and highly mobile airborne platforms (satellites, aircrafts and Unmanned Aerial Vehicles (UAVs)) to form an Airborne Network (AN). We propose an architecture for an Airborne Network to provide a stable operating environment. We design algorithms to compute the speed of movement of the airborne platforms, so that the resulting dynamic topology remains connected at all times. Faults are often localized in military networks where an enemy attack may inflict localized damage to the network. To capture the notion of locality in fault tolerance capability of such networks, we introduce the notion of region-based connectivity. The attractive feature of the region-based connectivity as a metric is that it can achieve the same level of fault-tolerance as the metric connectivity, but with much lower transmission power for the nodes. Optical bypass is an emergent technology that eliminates the need for optical-electrical-optical (O-E-O) conversion at most of the network nodes. However, the resulting network is still not all-optical, i.e., all connections cannot be established solely in the optical domain. Since the optical reach (the distance an optical signal can travel before its quality degrades to a level that necessitates regeneration) ranges from 500 to 2000 miles, regeneration of optical signals is essential to establish lightpaths of lengths greater than the optical reach. Given the optical reach of the signal, the goal of the regenerator placement problem is to find the minimum number of regenerators necessary in the network, so that every pair of nodes is able to establish a lightpath between them. We formulate the regenerator placement problem as a Connected Dominating Set problem in a Labeled Graph (LCDS) and provide a procedure for computing it. We evaluate the effectiveness of our approach on several networks.

Speaker Biography: Arunabha (Arun) Sen received the Bachelor degree in Electronics and Telecommunication Engineering from Jadavpur University, Kolkata, India, and the Ph.D. degree in Computer Science from the University of South Carolina, Columbia. He is currently a Professor in the School of Computing, Informatics and Decision Systems Engineering at Arizona State University. He served as the Associate Chairman of the department responsible for Graduate Programs and Research from 2001-7. His research interest is in solving resource optimization problems in networks utilizing graph theoretic and combinatorial optimization techniques. He has published over 100 research papers in peer-reviewed journals and conferences on these topics. He has served many IEEE and ACM workshops and conferences either as a Program Committee member or as the Chair of the Program Committee. Currently, he serves as an Associate Editor of IEEE Transactions on Mobile Computing. His research is sponsored by the U.S. Army Research Office, Air Force Office of Scientific Research and Defense Threat Reduction Agency. He is also a member of the ASU team that won the DoD Minerva award in 2009. He served as a Co-Chair of the First and Second International Workshops on Network Science for Communication Networks (NetSciCom 2009, NetSciCom2010) held in conjunction with IEEE Infocom in Rio de Janeiro in April 2009 and in San Diego in March 2010.