Publications

Complexity Theory and Networks | Communication and Control | Physical Threats

 COMPLEXITY THEORY AND NETWORKS


    "Towards Secure and Scalable Computation in Peer-to-Peer Networks" by Valerie King, Jared Saia, Vishal Sanwalani and Erik Vee.

    "Self-Healing Algorithms for Reconfigurable Networks " by Iching Boman, Jared Saia, Chaouki T. Abdallah and Edl Schamiloglu.

    "A Framework for Analysis of Dynamic Social Networks" by Tanya Y. Berger-Wolf and Jared Saia.


    1. Vamsi Kalapala, Vishal Sanwalani, Aaron Clauset and Cristopher Moore, "Scale Invariance in Road Networks", in Phys. Rev. E 73, 026130 (2006) [pdf]

      Abstract. We study the topological and geographic structure of the national road networks of the United States, England and Denmark. By transforming these networks into their dual representation, where roads are vertices and an edge connects two vertices if the corresponding roads ever intersect, we show that they exhibit both topological and geographic scale invariance. That is, we empirically show that the degree distribution of the dual is well-characterized by a power law with exponent between 2.0 and 2.5, and that journeys, regardless of their length, have a largely identical structure. To explain these properties, we introduce and analyze a simple fractal model of road placement that reproduces the observed structure, and suggests a connection between the scaling exponent alpha and the fractal dimensions governing the placement of roads and intersections.


    2. Dimitris Achlioptas, Aaron Clauset, David Kempe and Cristopher Moore, "On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs", in Proceedings of the 37th ACM STOC (2005). [pdf]

      Abstract. Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph structure is a surprisingly difficult task, as edges cannot be explicitly queried. Instead, empirical studies rely on traceroutes to build what are essentially single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a recent paper by Lakhina et al. found empirically that the resuting sample is intrinsically biased. For instance, the observed degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson.

      In this paper, we study the bias of traceroute sampling systematically, and, for a very general class of underlying degree distributions, calculate the likely observed distributions explicitly. To do this, we use a continuous-time realization of the process of exposing the BFS tree of a random graph with a given degree distribution, calculate the expected degree distribution of the tree, and show that it is sharply concentrated. As example applications of our machinery, we show how traceroute sampling finds power-law degree distributions in both delta-regular and Poisson-distributed random graphs. Thus, our work puts the observations of Lakhina et al. on a rigorous footing, and extends them to nearly arbitrary degree distributions.


    3. Herbert G. Tanner, Ali Jadbabaie and George J. Pappas, "Flocking in Teams of Nonholonomic Agents", in the series Lecture Notes in Control and Information Sciences, Springer: Berlin, ISSN: 0170-8643 ,Volume 309 / 2004 Chapter: p. 229 , to appear. [pdf]

      Abstract. The motion of a group of nonholonomic mobile agents is synchronized using local control laws. This synchronization strategy is inspired by the early flocking model proposed by Reynolds [22] and following work [29, 8]. The control laws presented ensure that all agent headings and speeds converge asymptotically to the same value and collisions between the agents are avoided. The stability of this type of motion is closely related to the connectivity properties of the underlying interconnection graph. Proof techniques are based on LaSalles invariant principle and algebraic graph theory and the results are verified in numerical simulations.

    4. Herbert G. Tanner, Ali Jadbabaie and George J. Pappas, "Flocking Agents with Varying Interconnection Topology", Submitted to Automatica. [pdf]

      Abstract. The work of this paper is inspired by the flocking phenomenon observed in Reynolds (1987). We introduce a class of local control laws for a group of mobile agents that result in:
      (i) global alignment of their velocity vectors, (ii) convergence of their speeds to a common one, (iii) collision avoidance, and (iv) local minimization of the agents artificial potential energy. These are made possible through local control action by exploiting the algebraic graph theoretic properties of the underlying interconnection graph. Algebraic connectivity affects the performance and robustness properties of the overall closed loop system. We show how the stability of the flocking motion of the group is directly associated with the connectivity properties of the interconnection network and is robust to arbitrary switching of the network topology.
    5. Aaron Clauset and Cristopher Moore, "Accuracy and Scaling Phenomena in Internet Mapping", Submitted, Physical Review Letters, 2004. [pdf]

      Abstract. A great deal of effort has been spent measuring topological features of the Internet. However, it was recently argued that sampling based on taking paths or traceroutes through the network from a small number of sources introduces a fundamental bias in the observed degree distribution. We examine this bias analytically and experimentally. For Erdos-Renyi random graphs with mean degree c, we show analytically that traceroute sampling gives an observed degree distribution P(k) ~ k-1 for k < c, even though the underlying degree distribution is Poisson. For graphs whose degree distributions have power-law tails P(k) ~ k-alpha, traceroute sampling from a small number of sources can significantly underestimate the value of alpha when the graph has a large excess (i.e., many more edges than vertices). We find that in order to obtain a good estimate of alpha it is necessary to use a number of sources which grows linearly in the average degree of the underlying graph. Based on these observations we comment on the accuracy of the published values of alpha for the Internet.


    6. Aaron Clauset, M. E. J. Newman, and Cristopher Moore, "Finding community structure in very large networks", Physical Review E, 2004, to appear. [pdf]

      Abstract. The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(mdlog n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log2 n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400 000 vertices and 2 million edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.

       COMMUNICATION AND CONTROL

    7. Sophie Tarbouriech, Chaouki Abdallah, John Chiasson (Eds.), Advances in Communication Control Networks, in the series Lecture Notes in Control and Information Sciences, vol. 308, Springer: Berlin, 2004 (ISBN 3-540-22819-5).

      About this book. The area of communication and computer networks has become a very active field of research by the control systems community in the last years. Tools from convex optimization and control theory are playing increasing roles in efficient network utilization, fair resource allocation, and communication delay accommodation and the field of Networked Control systems is fast becoming a mainstay of control systems research and applications. This carefully edited book brings together solicited contributions from experts in the various areas of communication/control networks referring to both networks under control (control in networks) as well as networked control systems (control over networks). The aim of this book is to reverse the trend of fragmentation and specialization in Communication Control Networks connecting various interdisciplinary research fields including control, communication, applied mathematics and computer science.


    8. J. Ghanem,C. T. Abdallah, M. M. Hayat, S. Dhakal, J.D Birdwell, J. Chiasson, and Z. Tang., "Implementation of Load Balancing Algorithms over a Local Area Network and the Internet", 43rd IEEE Conference on Decision and Control, Bahamas 2004. [pdf]

      Abstract. In this paper, experimental evaluation of a control-theoretic based load balancing algorithm in real environments is presented. we emphasize on the effects of delays in the exchange of information among nodes, and the constraints these effects impose on the design of a load balancing strategy. two test-beds in two different real environments have been built; The first implementation was over a local area network whereas the second one was over Planet-Lab. The results show the effect of the network delays and variances in the tasks processing time on choosing adequate gain values for the load balancing algorithm.


    9. M. M. Hayat, Sagar Dhakal, C. T. Abdallah, J. Douglas Birdwell and John Chiasson, "Dynamic Time Delay Models for Load Balancing Part II: A Stochastic Analysis of the Effect of Delay Uncertainty", In Advances in Time Delay Systems, in the series Lecture Notes in Computational Science and Engineering, (Keqin Gu and Silviu-Iulian Niculescu, Editors), vol. 38, pp.371-385, Springer: Berlin, 2004 (ISBN 1439-7358). [pdf]

      Abstract: In large-scale distributed computing systems, in which the computational elements are physically or virtually distant from each other, there are communication-related delays that can significantly alter the expected performance of load-balancing policies that do not account for such delays. This is a particularly significant problem in systems for which the individual units are connected by means of a shared broadband communication medium (e.g., the Internet, ATM, wireless LAN or wireless Internet). In such cases, the delays, in addition to being large, fluctuate randomly, making their one-time accurate prediction impossible. In this work, the stochastic dynamics of a load-balancing algorithm in a cluster of computer nodes are modeled and used to predict the effects of the random time delays on the algorithm's performance. A discrete-time stochastic dynamical-equation model is presented describing the evolution of the random queue size of each node. Monte Carlo simulation is also used to demonstrate the extent of the role played by the magnitude and uncertainty of the various time-delay elements in altering the performance of load balancing. This study reveals that the presence of delay (deterministic or random) can lead to a significant degradation in the performance of a load-balancing policy. One way to remedy such a problem is to weaken the load-balancing mechanism so that the load-transfer between nodes is down-scaled (or discouraged) appropriately.


    10. C. T. Abdallah, N. Alluri, J.D. Birdwell, J. Chiasson, V. Chupryna, Z. Tang, T. Wang, "A Linear Time Delay Model for Studying Load Balancing Instabilities in Parallel Computations", International Journal Systems Sciences, vol 34, pp 563-573, 2003. [pdf]

      Abstract: A linear time-delay system is used to model load balancing in a cluster of computer nodes used for parallel computations. The linear model is analyzed for stability in terms of the delays in the transfer of information between nodes and the gains in the load balancing algorithm. This model is compared with an experimental implementation of the algorithm on a parallel computer network.

       PHYSICAL THREATS

    11. E. Schamiloglu, "High Power Microwave Sources and Applications,"(Invited Paper), 2004 IEEE MTT-S Digest (Ft. Worth, TX, USA, 2004),pp. 1001-1004. [pdf]

      Abstract. There has been considerable interest recently in high power microwave (HPM) sources for nonlethal directed energy weaponry applications. Many of these sources that are being developed are derivatives of sources that are well known to the vacuum electronics community. Others are unique to the HPM community and have no analog in traditional microwave sources. For electronic attack (referred to in the media as the 'e-bomb', HPM sources are being developed that provide peak powers that exceed 1 GW at frequencies on the order of 1 GHz in short pulses, typically on the order of 100 ns. The technology that is used to drive such sources has its roots in pulsed power, and a comprehensive understanding of their behavior requires the use of tools that have been developed in the plasma physics community. The ever-increasing reliance on the use of microprocessors that have increasing density of circuits packaged on a chip makes such systems increasingly vulnerable to HPM. This paper will provide an overview of HPM sources, their applications, and will highlight areas of intense, ongoing research activity.