Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “network partition”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Hierarchical Network Partitioning for Solution of Potential-Driven, Steady-State Nonlinear Network Flow Equations

The solution of potential-driven steady-state flow in large networks is a task which manifests in various engineering applications, such as transport of natural gas or water through pipeline networks. The resultant system of nonlinear equations depends on the network topology, and in general, there is no numerical algorithm that offers guaranteed convergence to the solution (assuming a solution exists). Some methods offer guarantees in cases where the network topology satisfies certain assumptions, but these methods fail for larger networks. On the other hand, the Newton-Raphson algorithm offers a convergence guarantee if the starting point lies close to the (unknown) solution. It would be advantageous to compute the solution of the large nonlinear system through the solution of smaller nonlinear sub-systems wherein the solution algorithms (Newton-Raphson or otherwise) are more likely to succeed. Here, this letter proposes and describes such a procedure, a hierarchical network partitioning algorithm that enables the solution of large nonlinear systems corresponding to potential-driven steady-state network flow equations.

42 ENGINEERING↗
DOE OSTI2023

Efficient Network Partitioning: Application for Decentralized State Estimation in Power Distribution Grids

Increase in the proliferation of distributed energy resources require real-time situational awareness for efficient grid operations. State estimation plays an important role for the real-time control and management of the power grid. As the sensing infrastructure grows, aggregating and handling high volumes of data at a centralized location is extremely difficult. To address this challenge, this paper first proposes a novel and efficient hier-archical spectral clustering-based network partitioning algorithm followed by a decentralized compressive sensing (DCS)-based state estimation. The applicability of the proposed network partitioning algorithm is tested on an IEEE 123-bus network, an IEEE 8,500-node system, and a 6,000+ node distribution network. The results shows that the proposed approach efficiently divides the network into multiple sub-networks with the minimum number of edge connections among the neighbors. Then, we perform DCS-based state estimation on the 6,000+ node distribution network after dividing the network into 18 optimal partitions. Simulation results show that the DCS-based state estimation recovers the system states with high accuracy and low complexity.

alternating direction method of multipliers↗
DOE OSTI2023

Efficient Network Partitioning: Application for Decentralized State Estimation in Power Distribution Grids: Preprint

Increase in the proliferation of DERs requires real-time situational awareness for efficient grid operations. State estimation plays an important role for real time control and management of the power grid. As the sensing infrastructure grows, aggregating and handling high volumes of data at a centralized location is extremely difficult. To address this challenge, this paper first proposes a novel and efficient hierarchical spectral clustering-based network partition algorithm followed by a decentralized compressive sensing (DCS) based state estimation. The applicability of the proposed network partitioning algorithm is tested on IEEE-123 bus, IEEE-8500 node, and a 6204-node distribution network. The results shows that the proposed approach efficiently divides the network into multiple sub-networks with the minimum edge connections among the neighbors. Then, we perform DCS-based state estimation on the 6204-node distribution network after dividing the network into 18 optimal partitions. Simulation results show that DCS-based state estimation recovers the system states with high accuracy and low complexity.

ADMM↗
NASA NTRS1988

How to cluster in parallel with neural networks

Partitioning a set of N patterns in a d-dimensional metric space into K clusters - in a way that those in a given cluster are more similar to each other than the rest - is a problem of interest in astrophysics, image analysis and other fields. As there are approximately K(N)/K (factorial) possible ways of partitioning the patterns among K clusters, finding the best solution is beyond exhaustive search when N is large. Researchers show that this problem can be formulated as an optimization problem for which very good, but not necessarily optimal solutions can be found by using a neural network. To do this the network must start from many randomly selected initial states. The network is simulated on the MPP (a 128 x 128 SIMD array machine), where researchers use the massive parallelism not only in solving the differential equations that govern the evolution of the network, but also by starting the network from many initial states at once, thus obtaining many solutions in one run. Researchers obtain speedups of two to three orders of magnitude over serial implementations and the promise through Analog VLSI implementations of speedups comensurate with human perceptual abilities.

Kamgar-Parsi, Behzad↗
NASA NTRS1993

Applications of CCSDS recommendations to Integrated Ground Data Systems (IGDS)

This paper describes an application of the CCSDS Principle Network (CPH) service model to communications network elements of a postulated Integrated Ground Data System (IGDS). Functions are drawn principally from COSMICS (Cosmic Information and Control System), an integrated space control infrastructure, and the Earth Observing System Data and Information System (EOSDIS) Core System (ECS). From functional requirements, this paper derives a set of five communications network partitions which, taken together, support proposed space control infrastructures and data distribution systems. Our functional analysis indicates that the five network partitions derived in this paper should effectively interconnect the users, centers, processors, and other architectural elements of an IGDS. This paper illustrates a useful application of the CCSDS (Consultive Committee for Space Data Systems) Recommendations to ground data system development.

Mizuta, Hiroshi↗
DOE OSTI2024

Parallel Simulation of Quantum Networks with Distributed Quantum State Management

Quantum network simulators offer the opportunity to cost-efficiently investigate potential avenues for building networks that scale with the number of users, communication distance, and application demands by simulating alternative hardware designs and control protocols. Several quantum network simulators have been recently developed with these goals in mind. As the size of the simulated networks increases, however, sequential execution becomes time-consuming. Parallel execution presents a suitable method for scalable simulations of large-scale quantum networks, but the unique attributes of quantum information create unexpected challenges. In this work, we identify requirements for parallel simulation of quantum networks and develop the first parallel discrete-event quantum network simulator by modifying the existing serial simulator SeQUeNCe. Our contributions include the design and development of a quantum state manager (QSM) that maintains shared quantum information distributed across multiple processes. We also optimize our parallel code by minimizing the overhead of the QSM and decreasing the amount of synchronization needed among processes. Using these techniques, we observe a speedup of 2 to 25 times when simulating a 1,024-node linear network topology using 2 to 128 processes. We also observe an efficiency greater than 0.5 for up to 32 processes in a linear network topology of the same size and with the same workload. We repeat this evaluation with a randomized workload on a caveman network. We also introduce several methods for partitioning networks by mapping them to different parallel simulation processes. We have released the parallel SeQUeNCe simulator as an open source tool alongside the existing sequential version.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2022

Quantifying Spatial Drought Propagation Potential in North America Using Complex Network Theory

Droughts have a dominant three-dimensional (3-D) spatiotemporal structure typically spanning hundreds of kilometers and often lasting for months to years. Here, we introduced a novel framework to explore the 3-D structure of the evolution of droughts based on network theory concepts. The proposed framework is applied to identify critical source regions responsible for large-scale drought onsets during 1901–2014 for the North American continent using the Standardized Precipitation Evaporation Index (SPEI). We built a spatial network connecting the drought onset timings for the North American continent. Using a spatially weighted network partitioning algorithm, the whole continent is then classified into regional spatial drought networks (RSN), where droughts are more likely to propagate within these regional systems. Finally, a customized network metric was applied to identify locations (source regions) where the drought onsets further propagate to other areas within the regional spatial network. Our results indicated that the West coast, Texas coastal region, and Southeastern Arkansas as major source regions through which atmospheric drought propagates to Western, South Central, and Eastern North America. The formation of drought source regions are due to presence of high pressure ridges and anomalous wind patterns. Furthermore, our results indicate that the drought propagation from these source regions may be due to inadequate moisture transport. The proposed framework can help to develop an early warning detection system for droughts and other spatially extensive extreme events such as heatwaves and floods.

Goutam Konapala↗
DOE OSTI2023

Probabilistic partition of unity networks for high–dimensional regression problems

We explore the probabilistic partition of unity network (PPOU-Net) model in the context of high-dimensional regression problems and propose a general framework focusing on adaptive dimensionality reduction. With the proposed framework, the target function is approximated by a mixture of experts model on a low-dimensional manifold, where each cluster is associated with a fixed-degree polynomial. We present a training strategy that leverages the expectation maximization (EM) algorithm. During the training, we alternate between (i) applying gradient descent to update the DNN coefficients; and (ii) using closed-form formulae derived from the EM algorithm to update the mixture of experts model parameters. Under the probabilistic formulation, step (ii) admits the form of embarrassingly paralleliazable weighted least-squares solves. The PPOU-Nets consistently outperform the baseline fully-connected neural networks of comparable sizes in numerical experiments of various data dimensions. Here, we also explore the proposed model in applications of quantum computing, where the PPOU-Nets act as surrogate models for cost landscapes associated with variational quantum circuits.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2016

Toward a Unified Routing Framework for Delay-Tolerant Networking

Routing in Delay-/Disruption-Tolerant Networking (DTN) has long been recognized as a challenging research topic. The difficulty lies in the fact that link intermittency and network partitioning, possibly coupled with long delays, prevent the use of Internet solutions based on an up-to-date comprehensive knowledge of network topology, as communicated by routing protocols. In the literature on DTN routing, there is a dichotomy between solutions designed for deterministic (e.g., space flight) networks, such as Contact Graph Routing (CGR), and the wide variety of protocols designed for opportunistic terrestrial networks. After a discussion of the origin and motivations of this duality, the paper presents an opportunistic extension of CGR (OCGR). The aim is to try to resolve the DTN routing dichotomy by providing a unified approach suitable for all DTN environments.

Routing↗
NASA NTRS1995

An approach to verification and validation of a reliable multicasting protocol: Extended Abstract

This paper describes the process of implementing a complex communications protocol that provides reliable delivery of data in multicast-capable, packet-switching telecommunication networks. The protocol, called the Reliable Multicasting Protocol (RMP), was developed incrementally using a combination of formal and informal techniques in an attempt to ensure the correctness of its implementation. Our development process involved three concurrent activities: (1) the initial construction and incremental enhancement of a formal state model of the protocol machine; (2) the initial coding and incremental enhancement of the implementation; and (3) model-based testing of iterative implementations of the protocol. These activities were carried out by two separate teams: a design team and a V&V team. The design team built the first version of RMP with limited functionality to handle only nominal requirements of data delivery. This initial version did not handle off-nominal cases such as network partitions or site failures. Meanwhile, the V&V team concurrently developed a formal model of the requirements using a variant of SCR-based state tables. Based on these requirements tables, the V&V team developed test cases to exercise the implementation. In a series of iterative steps, the design team added new functionality to the implementation while the V&V team kept the state model in fidelity with the implementation. This was done by generating test cases based on suspected errant or off-nominal behaviors predicted by the current model. If the execution of a test in the model and implementation agreed, then the test either found a potential problem or verified a required behavior. However, if the execution of a test was different in the model and implementation, then the differences helped identify inconsistencies between the model and implementation. In either case, the dialogue between both teams drove the co-evolution of the model and implementation. We have found that this interactive, iterative approach to development allows software designers to focus on delivery of nominal functionality while the V&V team can focus on analysis of off nominal cases. Testing serves as the vehicle for keeping the model and implementation in fidelity with each other. This paper describes (1) our experiences in developing our process model; and (2) three example problems found during the development of RMP. Although RMP has provided our research effort with a rich set of test cases, it also has practical applications within NASA. For example, RMP is being considered for use in the NASA EOSDIS project due to its significant performance benefits in applications that need to replicate large amounts of data to many network sites.

Callahan, John R.↗
NASA NTRS1993

Virtually-synchronous communication based on a weak failure suspector

Failure detectors (or, more accurately Failure Suspectors (FS)) appear to be a fundamental service upon which to build fault-tolerant, distributed applications. This paper shows that a FS with very weak semantics (i.e., that delivers failure and recovery information in no specific order) suffices to implement virtually-synchronous communication (VSC) in an asynchronous system subject to process crash failures and network partitions. The VSC paradigm is particularly useful in asynchronous systems and greatly simplifies building fault-tolerant applications that mask failures by replicating processes. We suggest a three-component architecture to implement virtually-synchronous communication: (1) at the lowest level, the FS component; (2) on top of it, a component (2a) that defines new views; and (3) a component (2b) that reliably multicasts messages within a view. The issues covered in this paper also lead to a better understanding of the various membership service semantics proposed in recent literature.

Schiper, Andre↗
NASA NTRS1995

Fault recovery in the reliable multicast protocol

The Reliable Multicast Protocol (RMP) provides a unique, group-based model for distributed programs that need to handle reconfiguration events at the application layer. This model, called membership views, provides an abstraction in which events such as site failures, network partitions, and normal join-leave events are viewed as group reformations. RMP provides access to this model through an application programming interface (API) that notifies an application when a group is reformed as the result of a some event. RMP provides applications with reliable delivery of messages using an underlying IP Multicast (12, 5) media to other group members in a distributed environment even in the case of reformations. A distributed application can use various Quality of Service (QoS) levels provided by RMP to tolerate group reformations. This paper explores the implementation details of the mechanisms in RMP that provide distributed applications with membership view information and fault recovery capabilities.

Callahan, John R.↗
NASA NTRS1996

Design and Implementation of Replicated Object Layer

One of the widely used techniques for construction of fault tolerant applications is the replication of resources so that if one copy fails sufficient copies may still remain operational to allow the application to continue to function. This thesis involves the design and implementation of an object oriented framework for replicating data on multiple sites and across different platforms. Our approach, called the Replicated Object Layer (ROL) provides a mechanism for consistent replication of data over dynamic networks. ROL uses the Reliable Multicast Protocol (RMP) as a communication protocol that provides for reliable delivery, serialization and fault tolerance. Besides providing type registration, this layer facilitates distributed atomic transactions on replicated data. A novel algorithm called the RMP Commit Protocol, which commits transactions efficiently in reliable multicast environment is presented. ROL provides recovery procedures to ensure that site and communication failures do not corrupt persistent data, and male the system fault tolerant to network partitions. ROL will facilitate building distributed fault tolerant applications by performing the burdensome details of replica consistency operations, and making it completely transparent to the application.Replicated databases are a major class of applications which could be built on top of ROL.

Koka, Sudhir↗
NASA NTRS1996

Specification and Design of a Fault Recovery Model for the Reliable Multicast Protocol

The Reliable Multicast Protocol (RMP) provides a unique, group-based model for distributed programs that need to handle reconfiguration events at the application layer. This model, called membership views, provides an abstraction in which events such as site failures, network partitions, and normal join-leave events are viewed as group reformations. RMP provides access to this model through an application programming interface (API) that notifies an application when a group is reformed as the result of a some event. RMP provides applications with reliable delivery of messages using an underlying IP Multicast media to other group members in a distributed environment even in the case of reformations. A distributed application can use various Quality of Service (QoS) levels provided by RMP to tolerate group reformations. This paper explores the implementation details of the mechanisms in RMP that provide distributed applications with membership view information and fault recovery capabilities.

Montgomery, Todd↗