Seminar on April 15, 2011

Date: Friday, April 15, 2011.

Place: Math Building, Room 201, East China Normal University,

Zhongshan North Road 3663#, Putuo, Shanghai.


11:00 am - 11:50 am

Title: Cross-Layer Survivability in a Layered Network

Speaker: Krishnaiyan Thulasiraman (University of Oklahoma, Norman, USA)


An IP-over-WDM optical network is an example of a layered network. In this network, the grapah representing the optical network is called the physical topology GP and the graph representing the IP layer is called the logical topology GL. Without loss of generality, we assume that GL has the same set of nodes as GP . Each logical link (i,j) is associated with a path in GP connecting the nodes i and j. Such a path is called a lightpath. The survivable logical topology mapping problem in a layered network is to map each link (u, v) in the logical topology into a lightpath between the nodes u and v in the physical topology such that failure of a physical link does not cause the logical topology to become disconnected. It is assumed that both the physical and logical topologies are 2-edge connected. This mapping problem also arises in other areas of applications such as the problem of mapping a parallel program onto a multiprocess system, though the constraints there are of a different type.

For the survivable logical mapping problem, two lines of investigations have been pursued in the literature: one pioneered by Modiano et al., and the other pioneered by Kurant and Thiran. Since then there has been a great deal of research on this problem. Kurant and Thiran presented an algorithmic framework called SMART that involves successively contracting circuits in the logical topology, and mapping the logical links in the circuits into edge disjoint lightpaths in the physical topology. In a recent work, we presented a dual framework involving cutsets and showed that both these frameworks possess the same algorithmic structure. Algorithms CIRCUIT-SMART, CUTSET-SMART, CUTSET-SMART- SIMPLIFIED and INCIDENCE-SMART were also presented in our work. Effectiveness of both these frameworks as well as their robustness in providing survivability against multiple failures depends on the lengths of the cutset cover and circuit cover sequences on which they are based. In subsequent works we investigated several issues related to the sturctural survivability of logical topology, as well as augmenting a logical topology with additional links that guarantees the existence of a survivable mapping of the logical topology as long as the physical topology is 3-edge connected. In this lecturewe will preent these results and recent advances in this area.


Krishnaiyan Thulasiraman received the Bachelor’s degree (1963) and Master’s degree (1965) in Electrical Engineering from the University of Madras, India, and the Ph.D. degree (1968) in Electrical Engineering from IIT, Madras, India. He holds the Hitachi Chair and is Professor in the School of Computer Science at the University of Oklahoma, Norman, where he has been since 1994. Prior to joining the University of Oklahoma, Thulasiraman was professor (1981-1994) and chair (1993-1994) of the ECE Department in Concordia University, Montreal, Canada. He was on the faculty in the EE and CS departments of the IIT during 1965-1981. Dr. Thulasiraman’s research interests have been in graph theory, combinatorial optimization, algorithms and applications in a variety of areas in CS and EE: electrical networks, VLSI physical design, systems level testing, communication protocol testing, parallel/distributed computing, telecommunication network planning, fault tolerance in optical networks, interconnection networks etc. He has published extensively in archival journals, coauthored with M. N. S. Swamy two text books “Graphs, Networks, and Algorithms” (1981) and “Graphs: Theory and Algorithms” (1992), both published by Wiley Inter-Science.

Dr. Thulasiraman has received several awards and honors: Distinguished Alumnus Award of IIT Madras( 2008), Fellow of the American Association for Advancement of Science ( 2007), 2006 IEEE Circuits and Systems Society Technical Achievement Award. Endowed Gopalakrishnan Chair Professorship in CS at IIT, Madras (Summer 2005), Elected Academician of the European Academy of Sciences (2002), IEEE CAS Society Golden Jubilee Medal (1999), Fellow of the IEEE (1990) and Senior Research Fellowship of the Japan Society for Promotion of Science (1988). He has held visiting positions at the Tokyo Institute of Technology, University of Karlsruhe, University of Illinois at Urbana-Champaign and Chuo University, Tokyo.

Dr. Thulasiraman has been Vice President (Administration) of the IEEE CAS Society (1998, 1999), Technical Program Chair of ISCAS (1993, 1999), Deputy Editor-in-Chief of the IEEE Transactions on Circuits and Systems I ( 2004-2005), Co-Guest Editor of a special issue on "Computational Graph Theory: Algorithms and Applications" (IEEE Transactions on CAS , March 1988), , Associate Editor of the IEEE Transactions on CAS (1989-91, 1999-2001), and Founding Regional Editor of the Journal of Circuits, Systems, and Computers and a founding member of the editorial board of the AKCE International Journal of Graphs and Combinatorics publised by Kalasalingam university, India.


1:40 pm - 2:30 pm

Title: A Shapley Value Perspective on ISP Settlements

Speaker: Richard T.B. Ma (National University of Singapore)


Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. From a microscopic view, this concern manifests in ISP selfish routing strategies and discriminatory interconnections, which limit the stability of routes, balkanize the Internet and deteriorate performance and profit of the network. From a macroscopic view, this concern is at the heart of the Network Neutrality debate, which asks for an appropriate compensation structure that satisfies all types of ISPs. In this work, we design a profit-sharing mechanism based on the Shapley value originated from Coalition Game Theory. Under this mechanism, selfish ISPs would yield globally optimal routing and interconnecting decisions, reaching a Nash equilibrium that maximizes network efficiencies. We derive closed-form profit solutions for structured ISP topologies and develop a dynamic programming procedure to calculate solutions for general topologies. Based on these solutions, we draw some implications on the bilateral settlements between ISPs. In practice, these results provide guidelines for ISPs to solve disputes and negotiate stable and incentive settlements and for governments to establish regulatory policies for the Internet industry.


Richard T.B. Ma is currently an Assistant Professor in School of Computing, National University of Singapore and a Research Scientist at Advanced Digital Science Center, University of Illinois at Urbana-Champaign.

Richard received his Ph.D. degree from Columbia University and has worked as a Research Intern at IBM T.J. Watson Research Center in New York and Telefonica Research in Barcelona. He received his Mphil. and BSc.(first-class honors) degrees in Computer Science & Engineering from the Chinese University of Hong Kong.

His current research interests include:

* Networks, Distributed Systems and Smart Energy Systems

* Network Economics and Cloud Computing

* Game Theory and Mechanism Design

* Performance Evaluation, Stochastic Modeling and Analysis


2:40 pm - 3:30 pm

Title: Hard instances of algorithms and proof systems

Speaker: Yijia Chen ( Shanghai Jiaotong University )


Assuming that TAUT has no almost optimal algorithm, we show

that every algorithm A deciding TAUT has a polynomial time

computable sequence witnessing that A is not almost optimal.

Our result extends to every Pi_n^p-complete problem with

n\ge 1. Furthermore, for non-optimal propositional proof

systems it yields a version of a result due to Krajicek.


3:40 pm - 4:10 pm

Title: The Steiner Ratio Conjecture of Gilbert-Pollak is Still Open

Speaker: Boru Gong ( Fudan University )


Steiner tree problem, named after Jakob Steiner, is truly of great practical and scientifical interest. And its related Gilbert-Pollak conjecture about steiner ratio attempts to resolve the approximation ratio between minimum steiner tree and minimum spanning tree.

The aforementioned conjecture was proposed first in mid-1960s, and a commonly accepted proof was published in early 1990s by Ding-zhu Du et al. . However, it was discovered recently that his proof is problematic in the sense that one of its intermediate conclusion was wrong. As a result, the Gilbert-Pollak conjecture now is still open.

In this talk, the general thought behind Du's proof, in particular his problematic part, would be introduced.