Weibo Gong - US grants

The goal of this research project is to develop a new approach for the modelling, analysis and design of stochastic discrete event dynamic systems (DEDS). The proposed approach is based on obtaining the Maclaurin series of the performance measure as a function of a decision parameter. Our objectives are (i) to develop efficient recursive expressions for the Maclaurin coefficients for a large class of stochastic DEDS and (ii) to investigate the theoretical and practical implications of the obtained Maclaurin series. The results of this project would form a powerful complement to existing methodologies for stochastic DEDS. In particular, we will develop simple closed form approximations of the performance measures for the purpose of analysis and design, as well as some stochastic DEDS modelling guidelines analogous to those in the classical Bode-Nyquist methodology for modelling continous variable dynamic systems.

Performance index functions with integer parameters are important in the evaluation and analysis of computer systems, communication networks and general distributed and parallel processing systems. These functions are often difficult to evaluate for large integers. On the other hand, most of these performance functions have nice properties such as monotonicity, convexity, analyticity, as well as obtainable asymptotic behavior. This research uses such properties to extrapolate the performance functions based on their values at small integers. The objective of this research is to further establish the theoretical foundation and to develop guidelines, algorithms and their software implementations that will be applicable to a wide array of systems. The results of this research will make it possible to express the performance measure function in terms of the system size of dimension as a low-degree rational function for some general classes of systems. The successful completion of this research will provide a framework in which various difficult modeling, control and optimization issues can be attacked.

Coming Broadband Integrated Services Digital Networks (B-ISDNs) will be required to carry a broad range of traffic classes ranging from bursty, variable-rate sources, such as voice and variable-rate coded video, to smooth constant bit rate sources. Moreover, these networks will have to do so while providing a guaranteed quality-of-service (QoS) to these traffic classes. The problem of characterizing the performance of such networks is thus particularly important since this must be done, not only during the network design (in an off-line manner) but also for on-line control purposes such as call admission control. In this proposal we describe a novel technique for evaluating network performance based on the use of Global Rational Approximations (GRA) which has the potential of providing accurate estimates for a variety of performance measures such as packet loss probability in a wide variety of network settings. We outline research on GRAs whose aim is to develop a solid theoretical foundation on which the proposed algorithms can rest and to develop practical techniques for estimating network performance both during the design phase and in a real-time setting. Specifically, we propose to develop a complete theoretical foundation on which to develop algorithms for obtaining accurate global rational approximations for a variety of quality-of-service (QoS) metrics such as packet loss probability and probability that packet delay exceeds a particular value and to develop practical algorithms which can be used to evaluate large B ISDNs.

Abstract EEC-9527422 This award provides funding to Harvard University for support of a Combined Research-Curriculum Development Program entitled, "Analysis, Control and Optimization of Discrete Event Dynamic Systems." The CRCD program emphasizes the need to incorporate exciting research advances in important technology areas into the upper level undergraduate and graduate engineering curricula and stimulates faculty researchers to place renewed, equal value on quality education and curriculum development. This three year program, involving faculty from Harvard University, Boston University and the University of Massachusetts at Amherst will develop a curriculum in the multidisciplinary area of Discrete Event Dynamic Systems (DEDS) based on research accomplishments and consisting of new courses and a novel laboratory setting for the study of these large, complex, and expensive engineering systems. *** ??

Researchers from the University of Massachusetts at Amherst and Dartmouth
College jointly propose to perform fundamental research on developing a
fluid simulation methodology that will enable efficient, multi-time-scale,
hierarchical performance modeling of complex networks such as the next
generation Internet. The proposed effort will allow networks to be more
easily modeled and their performance to be evaluated significantly faster;
it will make it possible to model significantly larger networks than before
and to allow the tradeoffs between modeling accuracy and solution speed to
be quantitatively assessed. The novel features of the proposed fluid
modeling methodology include:
>
>Modeling at multiple time-scales. The proposed unified modeling framework
provides for modeling system behavior at different time-scales, allowing for
significant savings in simulation execution times when modeling at coarser
time-scales. Development of formal means for quantitatively characterizing
the potential loss of modeling accuracy when fast-time-scale behavior is
modeled at a coarser time-scale is an important part of the framework.
>
>Hierarchical fluid modeling. The PIs demonstrate that multi-level
(hierarchical) fluid modeling allows for abstraction of a potentially
complex component of the simulation by a simpler model and substitution of
this simpler model into the larger simulation. The PIs also develop
rigorous techniques that can automatically identify when such substitution
can be performed without significant loss of modeling accuracy.
>
>Efficiency in modeling complex systems. The PIs demonstrate that in
addition to providing for multi-time-scale, multi-level modeling, fluid
simulation can be significantly more efficient than traditional discrete
event simulation. The PIs' initial work shows a 50-fold speedup in a
uniprocessor fluid simulation speed over the discrete-event counterpart with
little loss in modeling accuracy.
>
>Applicability in many problem domains. The PIs demonstrate that fluid
simulation methodologies are ``plug and play'' in the sense that they can be
applied equally well to the current Internet protocol suite, future
real-time and multicast protocols, or ATM networks.
>

Real-time systems in embedded application have proliferated over the past few years. Many such systems are being used in life-critical and other important applications, where the failure of the computer to meet some deadlines can have disastrous consequences. The need therefore exists to accurately evaluate the reliability of such computers. Failure in a real-time system can occur due to timing as well as to traditional causes such as hardware failure. Timing overruns are often the consequence of a complicated series of interactions between various elements of the computer, such as individual application tasks, the operating system, the scheduling algorithm, the system architecture, component transient and permanent failure characteristics among other things. It is hard to take account of such interactions in analytical models without resorting to simplifying assumptions which raise questions about the models' accuracy and validity. Furthermore, traditional simulation to validate analytical models is very difficult because the failure rates that are being validated tend to be very low: system failure rates as low as .000000001 are involved. An earlier NSF-funded project developed the Rational Interpolation technique, and showed its usefulness in may compute applications. It created a framework in which various difficult modeling, control, and optimization issues can be attacked. The results indicate that Rational Interpolation is a powerful tool that can be used to complement other mechanisms of reliability and performance evaluation, especially in predicting very low failure rates. This project will involve the development of techniques and tools based on Rational Interpolation for real-time systems. While the focus will be on real-time systems, the results are expected to be useful in evaluating computers in other applications as well, such as random algorithms.

Future high-speed networks will be significantly larger and more complex than any existing network. The variety and interaction of the applications, the middleware and transport protocols, and the router/switch resource management algorithms will make the design, development, control, management and evaluation of these networks an exceptionally difficult task. One of the most critical components in the network control architecture is that concerned with congestion control. The Internet has relied till now on the additive increase, multiplicative decrease mechanism, found in most variations of TCP, for congestion control. There is increasing recognition, however, that new congestion control mechanisms, which will be able to coexist with TCP, are needed in future high speed networks. This is due to the increasing need to provide for heterogeneous application requirements and because of many future applications will rely on multicast. As is, TCP congestion control is inadequate for handling either heterogeneity or multicast.
There is also a need for a better methodology for modeling and analyzing the TCP performance and the performance of coming congestion control algorithms. The development of such a methodology is especially needed to evaluate the behavior of a mix of TCP sessions and future non-TCP sessions so as to avoid any unpleasant surprises as they are deployed. This proposal describes new and fundamental research in two broad areas:
(1)Formula-based congestion control. The researcher proposes research on a new approach to rate-based congestion control. The project introduces a formula-based approach in which a session monitors its end-end loss rate and adapts its transmission rate accordingly. The research shows how this can be used to construct a TCP-friendly rate control algorithm and then outline a research agenda for exploring and exploiting the potential of this approach to support multicast applications, and to support heterogeneous applications.
(2)Performance evaluation of congestion control algorithms. The researcher proposes research on the performance evaluation of different congestion control algorithms based on the use of
stochastic differential equations.
This proposed research represents a fundamentally important step in the understanding, design, analysis of congestion control algorithms needed by the next generation transport protocols.

In conjunction with Southern California Edison and Northeast Utilities, the goal of the research is to develop theory, models, and methods for reliable, affordable, and secure power. Two tasks will be performed:
Robustness of Complex Systems. Like many critical infrastructures, a power grid can experience cascading collapse where a seemingly small event cascades into a massive inability of the system to carry out its function. Our first task is to develop simulation-based methods for reducing vulnerability to collapse.
Economic and Gaming Considerations. Two fundamental market issues are considered. The first is the auctions used by Independent System Operators. We believe that current auctions are improperly designed resulting in higher than necessary costs to customers. A correct formulation and a novel methodology are proposed. The second issue is from the perspective of power providers, and focuses on methods that optimize day-ahead decisions while considering real-time markets and managing risks.
Our results will be validated against benchmark problems, the New England and California Power Markets. The intellectual merit lies in our recognition of the complexity, and tries to address the problems from a different perspective. The key idea for the first task is to use a model that not necessarily providing the exact performance value, but providing the correct performance order. This is based on the well-known fact that order is much easier to determine that value, and consequently a model only needs to capture the essential features that dominate the collapse behavior. Similarly, the second task would require solving mixed-integer problems with a non-separable structure. Rather than insisting on optimal solutions, our key idea is to obtain near-optimal solutions with quantifiable quality in a computationally efficient manner based on a novel "surrogate optimization framework."
The electric power infrastructure typifies the characteristics shared by virtually all critical networked infrastructures (transportation, finance, banking, emergency services, government, communications, media, manufacturing, social, etc.), therefore the proposed research will have broader impacts on other infrastructures. In addition, through courses, seminars, conferences, and summer programs for high school students and teachers, we shall reach out to students and professionals at various levels.

To address the lack of versatile and scalable tools in the relatively new optical networking field, the research project proposes to conduct fundamental research on developing a novel approach called RAFONET (Rational Approximation For Optical Networks) for optical network design and analysis. RAFONET, which integrates advanced analytic and numerical techniques, will make it possible to evaluate many hard-to-measure yet crucial performance metrics in optical networks with a large number of wavelengths, various switching paradigms and associated protocols much faster and more accurate than before under a unified framework.

In the application area, the PIs will apply the RAFONET approach to evaluate optical networks with optical circuit-switching (OCS) e.g., wavelength routing, or optical packet/burst switching (OPS/OBS). In addition, the proposed research project will compare OCS and OPS/OBS to determine, for example, how much resources is needed by OCS, and OPS/OBS to support a set of common input traffic streams that include periodic (e.g., voice) and aperiodic (e.g., data) traffic. In the algorithmic area, the PIs will study the effects of simulation errors on the performance of the rational approximation algorithm, and obtain some analytical results in bounding the interpolation errors when the sampling error is bounded by a polynomial for example. The PIs will also develop new methods based on, e.g., the combination of rational interpolation and cross entropy to combat such errors. Finally, the PIs will research the applicable scope and theoretic validation of the transformations applied in rational approximation algorithm.

The ITR project will also develop course materials on numerical methods in optical network analysis, as well as other related topics.

The objective of this proposal will be to develop a new media access protocol that work efficiently in the wireless multihop environment, i.e., preserve battery power and bandwidth, provide QoS support and adhere to legacy standards, i.e., IEEE 802.11. The research is on a new MAC protocol, denoted by CSMA/CA2. The proposed scheme automatically adapts each node transmission rate to the bandwidth usage and the number of active nodes in the network. The proposed research includes a graceful rate adjustment algorithm that achieves fair channel access and a low collision rate, control theoretical analysis of the algorithm's parameters setting, and, provision of QoS support to diverse multimedia traffic. In addition, the proposed protocol adheres to the IEEE 802.11 CSMA/CA standard. The adherence to open standards broadens the scope of usage of the proposed algorithm, making it interoperable with other third party network interface cards that adhere to these open standards. The analysis and simulation studies demonstrate that the proposed CSMA/CA2 scheme has the following advantages of achieving significant power and bandwidth savings with reduced medium access delay compared to IEEE 802.11 CSMA/CA; it is easy to implement, i.e., CSMA/CA2 has low computational complexity and does not require additional control packets or buffers; it provides fair channel sharing with fast convergence; it is compatible with the IEEE 802.11 standard, i.e., nodes with both CSMA/CA and CSMA/CA2 can coexist in the same network; and, it can provide quality of service (QoS) support to different traffic classes. The project will extend the analysis to study the quantitative relationship between system convergence speed and the CSMA/CA2 parameters. In addition, it will define adjustments of the control parameters that allow the system to provide different QoS support to different senders. Thorough analysis, both theoretical and experimental, will be carried out to determine the trade-off between CSMA/CA2 performance under various coexistence environments as well as system convergence speed and stability. The project will also develop a wireless testbed that will allow us to test the proposed algorithms in a real wireless environment.

The goal of this project is to develop a framework for designing a multipath routing architecture whereby end hosts make adaptive, robust congestion-aware routing decisions based on information provided to them by their ISPs or by an overlay network infrastructure. Multipath routing can be used to perform congestion avoidance and to provide a natural load balancing over the different paths and a robust recovery from a link failure. The project will generate new network architectures that provide robustness to applications and networks in the face of faults and dynamic changes in traffic demands through congestion aware multipath routing. On the theoretical side, the principal investigators (PIs) will develop mathematical models to study the performance, stability, robustness, and economics of a multipath routing architecture. On the practical side, the PIs will develop new algorithms and mechanisms for providing congestion-dependent multipath routing that tolerate failures, onsets of congestion, etc. as well as new algorithms for performing traffic engineering appropriate for networks within which most traffic is multi-path.

Broader Impact: The project integrates research and education of graduate and undergraduate students through the close interaction and mentoring of students by project faculty. The PIs will seek international involvement with Universities in Brazil. The latter involvement will include the refinement of existing networked teaching tools so as to make them more robust through application of our multipath techniques.

The easy access and wide usage of the Internet makes it a prime target and conduit for malicious activities. It constitutes a critical infrastructure in the economic and social fabric of, not only our nation, but the developed and, increasingly, the developing world. Recently, the Internet has become a powerful mechanism for propagating malicious software programs. These have been designed to annoy (e.g., deface web pages), spread misinformation (e.g., false news reports or stock quotes), deny service (e.g., corrupt hard disks), steal financial information (e.g., VISA card numbers), enable remote login (e.g., Trojan horses), etc. Moreover, they have been used to disrupt normal operations within the Internet itself. Furthermore, the potential for significant network disruptions is extremely high. It is well known that a single misconfigured BGP router on April 25th, 1997 effectively shut down most of the major Internet backbones for up to two hours, unleashing a sequence of cascading failures. If an accidentally misconfigured router can wreak such havoc, one can only imagine what a carefully orchestrated attack can produce in the way of disruptions.

Although malicious activities have appeared on many occasions, to date there appears to be no well-defined methodology for predicting their behavior and the damage that they can cause. This proposal describes research aimed at developing sound mathematically-based methodologies that can be used to better understand the characteristics of different network attacks, and to detect and estimate their parameters. More specifically, the proposed research will focus on the following areas.

o Mathematical models of network attacks. The researcher will develop a modelling methodology based on fluid models and networked Markov chains (NMCs). These models will be used to answer questions such as: how does network topology affect the spread of an Internet worm? What conditions must an attack meet to be considered virulent (severe)?

o Detection and parameter estimation. The researchers will develop detection and parameter estimation techniques for different types of monitors, based on the exponential growth trend in the early stage of the network attacks, with fluid models and point process models, respectively. They will also develop "hypothesis testing" based detection methods and study the performance and the impact in the defense strategies.

Furthermore, the analysis methodology produced by this research will have broad applicability in the design and analysis of failure and attack scenarios in large complex man made systems such as the power grid.

Intellectual Merit: This project will generate new techniques for studying and detecting different network attacks (e.g., worms, email viruses, BGP infrastructure attacks). Furthermore, the project will enhance our understanding of how failures can propagate throughout a large distributed system like the Internet, and, more generally, large man-made systems.

Broader Impact: The project integrates research and education of graduate and undergraduate students through the close interaction and mentoring of students by project faculty. We will also seek international involvement with Universities in Brazil in the form of joint courses/seminars.

PI: Christos G. Cassandras
Institution: Boston University
Proposal Number: 0735974

EFRI-ARESCI: Event-Driven Sensing for Enterprise Reconfigurability and Optimization

This project, with investigators from Boston University and the University of Massachusetts-Amherst, seeks a fundamental understanding of reconfigurability and optimization. The modern enterprise encompasses a number of processes that are all subject to changes in operating conditions, some sudden and unexpected, others slower with effects that are not immediately discernible. The proliferation of sensor and sensor network technologies provides the opportunity to enable estimators and controllers designed to rapidly react to perceived changes or detected anomalies and to appropriately reconfigure underlying enterprise components. The goal of this project is to develop a fundamental understanding of reconfigurability based on which analytical methods and explicit reconfiguration algorithms can be derived and evaluated. The vision is a transformation of the enterprise towards not only flexibility, but also responsiveness to unexpected, not directly observable, and possibly adversarial events. The goals of the project are threefold: (i) to contribute to the theoretical foundations of a reconfigurability framework for an enterprise viewed as a large-scale dynamic system; (ii) to bring together and build upon the methodological advances the investigators have made spanning on-line performance sensitivity estimation, detection of random, adversarial and game-theoretic anomalies, robust optimization, and information acquisition systems that all capitalize on sensor and sensor network technologies; and (iii) to explore a critical shift in systems engineering with broad ramifications: replacing traditional fixed-interval, time-driven sampling and data processing by an event-driven approach better suited for large-scale asynchronous distributed environments. An integral part of the proposed project is the application of the ideas and explicit reconfiguration algorithms developed on two complementary test beds: (i) a warehouse with wireless sensor nodes on trucks; and (ii) the OpenAir wireless network over the city of Boston.

The project is expected to advance the state-of-the-art in application domains that benefit from reconfigurability, primarily focusing on the enterprise where advances will result in increased energy efficiency, productivity growth, product and service quality, and enhanced workplace safety and security. Plans also include new courses, training graduate students, involving undergraduate students in the project, creating interactive educational software and demos, establishing cross-campus summer internships, and reaching out to high school students through two programs in which the investigators are involved.

As data communication has become increasingly important to our society, demands on the networking infrastructure have reached a point where it is desirable to implement an optical packet switching core. The prohibitive cost of large optical buffers has lead to many optical network designs with small buffers on routers. A major challenge in this context is to envision efficient operation scenarios that justify these small buffer networks. This project aims at developing an architecture that implements packet spacing on network links such that suitable statistical properties of network traffic can be ensured and small-buffer networks can be operated efficiently. The specific goals of this project are: (1) understanding of packet spacing and its network-wide impact, (2) development of a pacing node prototype, and (3) consideration of network-wide deployment. The packet spacing architecture developed in this project can help in promoting the broad deployment of optical packet switching technology.
Intellectual Merit: The intellectual merit of this project includes three aspects. First, the research will further our understanding of the impact of packet spacing on the whole network (rather than being limited to a single buffer analysis). Second, the pacing architecture will help improve the efficiency of operation of optical core networks and thus improve the Internet as a whole. Third, the cross-disciplinary research covering queuing analysis, network measurements, system design, and prototype implementation and deployment sets up an agenda to address real-world network issues.
Broader Impact: Guarantees on traffic statistics that a packet pacing architecture can provide are an essential step in the process to convince the Internet community, especially Internet service providers, to adopt and deploy optical networks. A wide-spread adoption of such networks in the U.S. could increase the availability of high-bandwidth data communication and improve wide-spread access to modern communication services and applications.

There has been a rapid increase in the number and types of digital networks over the last 2 decades beginning, of course with the Internet, its constituent networks, and the World Wide Web. We now have a wide range of on-line social networks (OSNs) such as Facebook, Twitter, mobile ad hoc networks (MANETs) and delay tolerant networks (DTNs). These networks pervade all aspects of our lives and provide a growing range of services in commerce, business, communications, and connectivity. Many of these networks are continually in a dynamic state of flux and/or extremely large. For example, the topology of a MANET or a DTN is constantly changing, and that of an OSN such as Facebook is rapidly growing and evolving. The modeling, analysis, and measurement of such networks are challenging, due to their dynamism and sizes. As a consequence, traditional mathematical techniques are not suitable and fundamentally new techniques are needed.

This research will focus on three interrelated problems. The first is to develop useful and accurate models that capture the dynamics of today?s social and technological networks. The second is to develop and study a class of techniques for characterizing and searching such networks. These techniques are based on a very simple mechanism, namely to let an agent explore the network by randomly choosing where to go. This is known as a random walk in the mathematics literature and has been shown to exhibit desirable search and characterization properties in static networks that shows promise in dynamic networks. Last, many static networks exhibit what is known as a power law, namely that the distribution for the number of neighbors of a node roughly decays as k−a where k is the number of neighbors and a is a positive constant greater than one. The third problem is to understand what constitutes a power law in a dynamic network, how this power law comes to be, and what implications there might be regarding the health of the network.

Broader Impact. The work will positively impact society by providing a deeper understanding of and a set of tools for managing and monitoring digital networks such as MANETs and OSNs. The project includes a comprehensive dissemination plan including public release of tools for network characterization. The education plan includes cross-specialty seminars, undergraduate involvement in research through a REU site, and international outreach to South America.

The project aims at making cities "smarter" by engineering processes such as traffic control, efficient parking services, and new urban activities such as recharging electric vehicles. To that end, the research will study the components needed to establish a Cyber-Physical Infrastructure for urban environments and address fundamental problems that involve data collection, resource allocation, real-time decision making, safety, and security. Accordingly, the research is organized along two main directions: (i) Sensing and data acquisition using a new mobile sensor network paradigm designed for urban environments; and (ii) Decision Support for the "Smart City" relying on formal verification and certification methods coupled with innovative dynamic optimization techniques used for decision making and resource allocation. The work will bring together and build upon methodological advances in optimization under uncertainty, computer simulation, discrete event and hybrid systems, control and games, system security, and formal verification and safety. Target applications include: a "Smart Parking" system where parking spaces are optimally assigned and reserved, and vehicular traffic regulation.

The research has the potential of revolutionizing the way cities are viewed: from a passive living and working environment to a highly dynamic one with new ways to deal with transportation, energy, and safety. Teaming up with stakeholders in the Boston Back Bay neighborhood, the City of Boston, and private industry, the research team expects to establish new collaborative models between universities and urban groups for cutting-edge research embedded in the deployment of an exciting technological, economic, and sociological development.