Simon Fraser University IRMACS Centre
Vancouver, BC, Canada
Friday and Saturday, 18-19 August 2006
Department of Electrical Engineering and Center for Theoretical Studies
Indian Institute of Technology, Kharagpur, India
In many areas of complex systems and networks, one comes across discrete-time models that are piecewise smooth. Such situations arise in hybrid dynamical systems — where the continuous-time evolution of the state variables is punctuated by discrete switching events (e.g., power electronic circuits and impacting mechanical systems). Piecewise smooth maps also arise in systems involving discrete control logic (e.g., internet packet transfer using TCP-RED). In such systems, complex bifurcation phenomena are often observed that involve both smooth bifurcations as well as border collision bifurcations. In this talk, I will present a brief outline of the available theory of border collision bifurcations with which such phenomena can be understood and analyzed.
Dr. Soumitro Banerjee (born 1960) did his B.E. from the Bengal Engineering College (Calcutta University) in 1981, M.Tech. from IIT Delhi in 1983, and Ph.D. from the same Institute in 1987. He has been in the faculty of the Department of Electrical Engineering, IIT Kharagpur, since 1986.
Dr. Banerjee has been in the forefront of international research on the nonlinear phenomena in power electronics, and on border collision bifurcations. He has published three books: —Nonlinear Phenomena in Power Electronics— (Ed: Banerjee and Verghese, IEEE Press, 2001), —Dynamics for Engineers— (Wiley, London, 2005), and —Wind Electrical Systems— (Oxford University Press, New Delhi, 2005).
Dr. Banerjee served as Associate Editor of the IEEE Transactions on Circuits and Systems II (2003-05), and is currently serving as Associate Editor of the IEEE Transactions on Circuits and Systems I. He is a recipient of the S. S. Bhatnagar Prize (2003), and the Citation Laureate Award (2004). He is a Fellow of the Indian Academy of Sciences and of the Indian National Academy of Engineering.
Centre for Chaos and Complex Networks
City University of Hong Kong, Hong Kong
The current study of complex dynamical networks is pervading all kinds of sciences today, ranging from physical to biological, even to social sciences. Its impact on modern engineering and technology is prominent and will be far-reaching. Research on fundamental properties and dynamical features of various complex networks has become overwhelming. This talk will provide a brief introduction and overview of the pinning control methodology for complex dynamical networks, using some simple controllers as examples for illustration. Randomly selective and specially selective pinning control approaches will be discussed. It will be shown, by convincing numerical comparisons, that utilizing the network topology can significantly benefit classical control performance over large-scale complex networks.
Professor Chen received his MS degree in computer science from Zhongshan University, China and Ph.D degree in applied mathematics from Texas A&M University, USA, with Post-Doctorate research experience in nonlinear system dynamics and controls. He is an IEEE Fellow (since 1997) and currently a Chair Professor and the Director of Centre for Chaos and Complex Networks at the City University of Hong Kong. His research interests include chaos control and synchronization, complex dynamical networks, and their engineering applications.
School of Engineering Science
Simon Fraser University, Burnaby, BC, Canada
We present a methodology for protecting TCP traffic in a network domain that provides both virtual-circuit routing with bandwidth reservation for higher-priority QoS traffic and datagram routing for TCP traffic. When a QoS virtual circuit is established, bandwidths amounting to the traffic—s effective bandwidths are reserved along the links. We formulate a new QoS-virtual-circuit admission control and routing policy that sustains a minimum level of best-effort performance. In response to a QoS connection request, the policy executes a two-stage optimization. The first stage seeks a minimum-net-effective-bandwidth reservation path that satisfies a best-effort protecting constraint; the second stage is a tie-breaking rule, selecting from tied paths one that least disturbs best-effort traffic. Our novel policy implementation efficiently executes both optimization stages simultaneously by a single run of Dijkstra—s algorithm. According to simulation results, within a practical operating range, the consideration that our proposed policy gives to the best-effort service does not increase the blocking probability of a QoS connection request. The practicality of our best-effort-friendly methods is demonstrated by applying them to a well-known algorithm for restorable path routing.
Daniel C. Lee received the Ph.D. and S.M. degrees from the Massachusetts Institute of Technology in Electrical Engineering and Computer Science. He received a B.S. degree in Electrical Engineering with honors and a B.S. degree in Mathematics from the University of Maryland at College Park. From 1993 to 1998, Dr. Lee devoted his research to the systems engineering of networks and communication systems at the U.S. Naval Research Laboratory (NRL) in Washington, DC. At the Center for Computational Science in NRL, Dr. Lee participated in the development of an object-oriented protocol software framework, CASiNO. At the Naval Space Center in NRL, Dr. Lee developed a proxy agent for managing the ICEbox network, a U.S. government information-dissemination system. Dr. Lee—s academic career began in 1998 as he joined the faculty of Electrical Engineering Department at the University of Southern California. He is currently an Associate Professor in the School of Engineering Science at Simon Fraser University, Burnaby, BC, Canada. His main research interests have been quality of service and resource allocation issues in communication systems and networks. Applications of his research include wireless communications and networking, sensor networks, optical networks, and internet multimedia.
Department of Statistics
University of California, Irvine, California, USA
In this paper, we propose a novel approach to estimating traffic matrices that incorporates lightweight Origin-Destination (OD) flow measurements coupled with a computationally lightweight algorithm for producing the OD estimates. There are two key ingredients in our method, called PamTram, for PArtial Measurement of TRAffic Matrices. The first is to actively select a small number of informative OD flows to measure in each estimation time interval. To avoid the heavy computation of an optimal selection, we use a heuristic based on intuition from game theory. Randomized selection rules are developed based on the goals of reducing errors and adapting to traffic changes. We provide an algorithm for selecting a good flow to measure that is fast because it avoids the computations, such as integrating over past intervals, that are needed for optimal selection. The second key aspect of our method is an explanation and proof that an Iterative Proportional Fitting IPF) algorithm can be used to approximate the traffic matrix estimate when the goal is a minimum mean squared error and the optimization starts from a maximum entropy initial estimate.
In addition, we provide a one-step average error bound for PamTram when the randomized selection rule is uniform and no link counts are used. This bounds the average error for the worst case selection rule. Finally, we validate our method using data from Sprint's European Tier-1 IP backbone network. Results show that our method generates average errors below the 10% carrier target error rate. Interestingly, we show that it suffices to measure a single OD flow in each estimation interval, which renders our partial measurement method very lightweight in terms of measurement overhead.
Gang Liang is an assistant professor in the Department of Statistics, University of California at Irvine. He received his Ph.D in Statistics from University of California at Berkeley in 2004, and his BS and MS degree from Peking University, China in 1996 and 1999 respectively. His research areas of specialty are statistical theory, applications of statistical methods to computer networks. He is also interested in information theory, algorithm development, and machine learning.
Departments of Computer Science, and Electrical Engineering
California Institute of Technology, Pasadena, California, USA
Homogeneity of price is an implicit yet fundamental assumption underlying price based resource allocation theory. We study congestion control when this assumption is relaxed. We describe results on the existence, uniqueness, optimality, and stability of network equilibrium, and present experiments to illustrate and validate these theoretical predictions.
When heterogeneous congestion control protocols that react to different pricing signals share the same network, the resulting equilibrium can no longer be interpreted as a solution to the standard utility maximization problem as the current theory suggests. We prove the existence of equilibrium in general multi-protocol networks under mild assumptions. For almost all networks, the equilibria are locally unique. They are finite and odd in number. They cannot all be locally stable unless it is globally unique. Finally, we show that if the degree of heterogeneity is small, then global uniqueness is guaranteed. Moreover, the equilibrium is locally stable. Finally, we propose a scheme to steer an arbitrary network to a unique equilibrium that maximizes the total utility, by updating a scaling constant in the sources' utility functions.
(Joint work with Kevin Tang, Jiantao Wang, David Wei, Caltech; and Mung Chiang, Princeton)
Steven H. Low received his B.S. from Cornell University, and MS and PhD from Berkeley, all in electrical engineering. He is a Professor at Caltech, where he leads the FAST Project, and a Senior Fellow of the University of Melbourne, Australia. He was with AT&T Bell Laboratories, Murray Hill, from 1992 to 1996 and with the University of Melbourne from 1996 to 2000. He was a co-recipient of the IEEE William R. Bennett Prize Paper Award in 1997 and the 1996 R&D 100 Award. He is on the editorial boards of the IEEE/ACM Transactions on Networking, ACM Computing Surveys, NOW Foundations and Trends in Networking, and is a Senior Editor of the IEEE Journal on Selected Areas in Communications.
Department of Electrical Engineering
AGH University of Science and Technology, Krakow, Poland
One form of complexity visible in many physical processes and in nature is often characterized by the notion of fractal structure. It refers to the geometric properties of objects and can be characterized in mathematical terms by non-integer dimension and self-similarity. Objects having fractal properties can be also generated artificially using appropriate mathematical models. We will discuss one class of such models based on iterated processes/iterated geometric construction.
In this talk we will introduce basic notions and discuss properties of fractals. Further, we show how fractal structures can find interesting applications in modern electronics.
Three areas of applications will be discussed:
Application of fractal structures in all three cases brings significant improvement of system operation in terms of electrical properties and allows at the same time astonishing miniaturization of the circuitry.
Maciej Ogorzalek received is professor of electrical engineering at the AGH University of Science and Technology, Krakow, Poland and holds a joint appointment as head of Department of Information Technologies at the Jagiellonian University in Krakow, Poland.
His research and teaching interests include circuit theory with an emphasis on Nonlinear and dynamic circuits, complex phenomena and chaos, neural networks, nonlinear signal analysis and processing, nonlinear methods for mixed signal circuit design, biomedical signal analysis and modeling. He was the creator of the new department and new curricula in applied computer science including bio-informatics at the Jagiellonian University. Author or co-author of over 230 technical papers and one book (Chaos and Complexity in Nonlinear Electronic Circuits, World Scientific).
He held several visiting positions: Swiss Federal Institute of Technology Lausanne, The Technical University of Denmark, Artificial Brain Systems Laboratory, Institute of Physical and Chemical Research (RIKEN), Wako, Japan; Electronics Research Laboratory, University of California, Berkeley. Centro Nacional de Microelectronica, Sevilla, Spain, Kyoto University, Japan (Senior JSPS Award) and Goethe University Frankfurt-am-Main, Germany, Department of Electronic and Information Engineering, Hong Kong Polytechnic University.
He is an IEEE Fellow (1997), Recipient of the IEEE Guillemin-Cauer (Best Paper) Award 2002. Distinguished Lecturer of the CAS Society 2001-2003.
He served as Associate Editor for IEEE Transactions on Circuits and Systems, Part I 1993-1995 and 1999-2001. Since 2004 elected member of the Editorial Board of the Proceedings of the IEEE. Since 2004 he is the Editor-in-Chief of the Circuits and Systems Magazine. Associate Editor Int. J. Circuit Theory and Applications (1999- ) Associate Editor - Journal of The Franklin Institute (1997- ), Secretary of the Editorial Board for the Quarterly of Electrical Engineering and Electronics (Poland) (1993- ), Member of the Editorial Board of Automatics (in Polish Automatyka). Member of the Editorial Board of the International Journal of Bifurcation and Chaos.
He was the Vice-Chairman of the IEEE CAS Chapter Poland, recipient of the Chapter-of-the-Year Award 1995, Chairman of the Technical Committee of Nonlinear Circuits and Systems of CAS Society 1997/1998, Chairman of the Organizing Committee 1994 Workshop on Nonlinear Dynamics of Electronic Systems, member of technical committees of several IEEE sponsored conferences, Special Sessions chairman for ISCAS'2000. Founding member of the CASS Technical Committee on Biomedical Circuits and Systems. General Chairman, European Conference on Circuit Theory and Design 2003. Recipient of the IEEE-CAS Golden Jubilee Award. He has been elected CAS Society Vice-President for Region 8 for 2002-2004 and CAS Society Administrative Vice-President since 2004.
School of Engineering
University of Ferrara, Italy
Nowadays the problem designing electromagnetic compatible (EMC) systems is of great practical concern. High performance computing platforms are a perfect example in which the presence of Electromagnetic Interference (EMI) must be handled with particular care, in order to design more and more compact systems and architectures that can operate without having any of the subsystems interfering with the neighboring one.
EMI reduction by exploiting nonlinear dynamics is mainly done by altering conventional systems operating of the basis of periodic signal, such as switching power converters and digital circuits, with the introduction of periodic or even chaotic perturbations. This solution offer the advantage of preventing EMI at design stage, so that expensive shield and filters, commonly added to improve EMC, are not necessary.
Among the possible solution to achieve such goal, we will first review the classical solution based on frequency modulation (FM) of the timing signal by means of a simple sinusoid or an optimized (and patented) cubic periodic profile. Notably, this last solution allows to reduce the peak value of the spectrum of more than 7dB with respect to the unperturbed signal and had been employed in some products from Intel, IBM and Cypress. We will then show that further EMI reduction can be achieved by substituting the periodic modulating signal with a chaotic one. Theoretical and experimental results will be shown confirming that chaos-based methodologies allow a further reduction of more than 9dB in the power spectrum peak of the interfering signals.
Finally, we will give some details on the application of these methodologies to:
Gianluca Setti (S89, M91, SM02, F06) received a Dr. Eng. degree (with honors) in Electronic Engineering and a Ph.D. degree in Electronic Engineering and Computer Science from the University of Bologna, Bologna in 1992 and in 1997, respectively, for his contribution to the study of neural networks and chaotic systems. From May 1994 to
July 1995 he was with the Laboratory of Nonlinear Systems (LANOS) of the Swiss Federal Institute of Technology in Lausanne (EPFL) as visiting researcher. Since 1997 he has been with the School of Engineering at the University of Ferrara, Italy, where he is currently an Associate Professor of Circuit Theory and Analog Electronics. His research interests include nonlinear circuits, recurrent neural networks, implementation and application of chaotic circuits and systems, statistical signal processing, electromagnetic compatibility, wireless communications and sensor networks.
Dr. Setti received the 1998 Caianiello prize for the best Italian Ph.D. thesis on Neural Networks and he is co-recipient of the 2004 IEEE CAS Society Darlington Award.
He served as an Associate Editor for the IEEE Transactions on Circuits and Systems - Part I (1999-2002 and 2002-2004) and for the IEEE Transactions on Circuits and Systems - Part II (2004-2006). Currently he is acting as Deputy-Editor-in-Chief, for the IEEE Circuits and Systems Magazine (since 2004) and as Editor-in-Chief for the IEEE Transactions on Circuits and Systems - Part II (since 2006).
He was the 2004 Chair of the Technical Committee on Nonlinear Circuits and Systems of the IEEE CAS Society, a Distinguished Lecturer (2004-2005) and a member of the Board of Governors (since 2005) of the same society. Dr. Setti was also the Technical Program Co-Chair of NDES2000 (Catania) the Track Chair for Nonlinear Circuits and Systems of ISCAS2004 (Vancouver), the Special Sessions Co-Chair of ISCAS2005 (Kobe) and ISCAS2006 (Kos) and will be the Technical Program Co-Chair of ISCAS2007 (New Orleans), as well as the General Co-Chair of NOLTA2006 (Bologna).
He is co-editor of the book Chaotic Electronics in Telecommunications (CRC Press, Boca Raton) and one of the guest editors of the May 2002 special issue of the IEEE Proceedings on "Applications of Nonlinear Dynamics to Electronic and Information Engineering".
He is a Fellow of the IEEE.
School of Engineering Science
Simon Fraser University, Burnaby, BC, Canada
Interaction between Transmission Control Protocol (TCP) and Random Early Detection (RED) gateways may be captured using dynamical models. The TCP/RED mechanism is viewed as a discrete-time feedback control system where TCP adjusts its sending rate depending on packet loss.
We describe simple discrete-time first-order and second-order nonlinear dynamical models for the Transmission Control Protocol (TCP) with Random Early Detection (RED) algorithm. The TCP/RED models, constructed using iterative maps, capture a detailed dynamical behavior of TCP/RED, including slow start, fast retransmit, and timeout phases of the TCP congestion control mechanism. Model performance for various RED parameters is evaluated using the ns-2 network simulator. We then investigate bifurcations and chaos in a TCP/RED system with a single TCP connection.
We conjecture that the complex behavior observed in the system may be attributed to a class of discontinuity-induced bifurcations observed in piecewise smooth systems.
(Joint work with Mingjian Liu and Hui Zhang, SFU and Alfredo Marciello and Mario di Bernardo, University of Naples Federico II)
Ljiljana Trajkovic received the Dipl. Ing. degree from University of Pristina, Yugoslavia, in 1974, the M.Sc. degrees in electrical engineering and computer engineering from Syracuse University, Syracuse, NY, in 1979 and 1981, respectively, and the Ph.D. degree in electrical engineering from University of California at Los Angeles, in 1986.
She is currently a Professor in the School of Engineering Science at Simon Fraser University, Burnaby, British Columbia, Canada. From 1995 to 1997, she was a National Science Foundation (NSF) Visiting Professor in the Electrical Engineering and Computer Sciences Department, University of California, Berkeley. She was a Research Scientist at Bell Communications Research, Morristown, NJ, from 1990 to 1997, and a Member of the Technical Staff at AT&T Bell Laboratories, Murray Hill, NJ, from 1988 to 1990. Her research interests include high-performance communication networks, control of communication systems, computer-aided circuit analysis and design, and theory of nonlinear circuits and dynamical systems.
Dr. Trajkovic is currently serving as president-elect of the IEEE Circuits and Systems Society. She is currently serving on the Board of Governors of the IEEE Systems, Man, and Cybernetics Society (2004 — 2006). She was a member of the Board of Governors of the IEEE Circuits and Systems Society (2001 — 2003 and 2004 — 2005). She is Chair of the IEEE Circuits and Systems Society joint Chapter of the Vancouver/Victoria Sections. She was Chair of the IEEE Technical Committee on Nonlinear Circuits and Systems (1998). She was Technical Program Co-Chair of ISCAS 2005 and served as Technical Program Chair and Vice General Co-Chair of ISCAS 2004. She served as an Associate Editor of the IEEE Transactions on Circuits and Systems, Part I (2004 — 2005 and 1993 — 1995), the IEEE Transactions on Circuits and Systems, Part II (1999 — 2001 and 2002 — 2003), and the IEEE Circuits and Systems Magazine (2001 — 2003). She is a Fellow of the IEEE.
Department of Electronic and Information Engineering
Hong Kong Polytechnic University, Hong Kong
In this talk, we will examine the effects of the choice of user network models on the traffic analysis results. The main focus will be telephone, mobile networks and the Internet. The basic deficiencies of the conventional network models are that they assume uniformity of user activities. In the real world, a small percentage of users are actually taking up a large percentage of the resources, following a power-law distribution. The limitation of any network is due largely to user behavior and topology rather than the network capacity. Thanks to the latest advances in complex network modeling, we are able to construct a more realistic user model based upon a scale-free topology. This model can more realistically provide traffic data that can be used for better planning. Some results clearly highlight the importance of appropriate pricing strategies in order to control the traffic in a communication network.
Chi K. (Michael) Tse (M'90—SM'97—F'06) received the B.Eng degree with first class honors and the Ph.D. degree from the University of Melbourne, Australia, in 1987 and 1991, respectively.
He is presently Chair Professor of Electronic Engineering and Head of Department of Electronic and Information Engineering at the Hong Kong Polytechnic University, Hong Kong. His research interests include complex network applications, power electronics and chaos-based communications. Since 2002 he has been Guest Professor with the Southwest China Normal University, Chongqing, China. He is the author of the books Linear Circuit Analysis (London: Addison-Wesley, 1998) and Complex Behavior of Switching Power Converters (Boca Raton: CRC Press, 2003), co-author of Chaos-Based Digital Communication Systems (Heidelberg: Springer-Verlag, 2003), Digital Communications with Chaos (London: Elsevier, 2006), and Reconstruction of Chaotic Signals with Applications to Chaos-Based Communications (Beijing: TUP, 2007), and co-holder of a US patent and two other pending patents.
Dr. Tse received the L.R. East Prize from the Institution of Engineers, Australia, in 1987, the Best Paper Award from IEEE Transactions on Power Electronics in 2001, Dynamics Days Europe Presentation Prize in 2002, and the Best Paper Award from International Journal of Circuit Theory and Applications in 2003. While with the Hong Kong Polytechnic University, he received the President's Award for Achievements in Research in 1997 and 2000, the Faculty Best Researcher Award in 2000, the Faculty Research Grant Achievement Award in 2004, and a few other teaching awards. In 2005, he was named an IEEE Distinguished Lecturer. In 2006 he was elected an IEEE Fellow.
Dr. Tse was an Associate Editor for the IEEE Transactions on Circuits and Systems, Part I — Fundamental Theory and Applications from 1999 to 2001, and since 1999 has been an Associate Editor for the IEEE Transactions on Power Electronics. He also served as Guest Editor for the IEEE Transactions on Circuits and Systems, Part I — Fundamental Theory and Applications in 2003, Guest Associate Editor for the IEICE Transactions on Fundamentals of Electronics, Communications and Computers in 2004—2006, and Guest Editor for Circuits, Systems and Signal Processing in 2005. He currently also serves as an Associate Editor for the International Journal of Systems Science.
Department of Mathematics
University of Washington, Seattle, Washington, USA
We study a second-order cone programming (SOCP) relaxation of the NP-hard sensor network localization problem. We show that SOCP relaxation, though weaker than SDP relaxation, has nice properties that make it useful as a problem preprocessor. In particular, sensors that are uniquely positioned among interior solutions of the SOCP relaxation are accurate up to the square root of the distance error. Thus, these sensors, which can be easily identified, are accurately positioned. In our numerical simulation, the interior solution found can accurately position up to 80-90\% of the sensors. We also propose a smoothing coordinate gradient descent method for finding an interior solution faster than using interior point method.
Paul Y. Tseng received his B.Sc. from Queen's University in 1981 and the Ph.D. from MIT in 1986. After one year at the University of British Columbia as a research fellow and three years at MIT as a research associate, he joined the Dept. of Mathematics at University of Washington in 1990, where he has been since. His research area is in optimization.
Dr. Tseng received research support from the NSF and NIH, and serves on the editorial board of various optimization journals.