Complexity Theory and Networks | Communication and Control | Physical Threats
"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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
|