Journal of Research of the National Bureau of Standards

Topics: Independence properties, matroids, maximal flows, network flows

34
34

Aug 19, 2016
08/16

by
Martin Vizváry and Petr Velan

texts

######
eye 34

######
favorite 0

######
comment 0

Software defined networking is being introduced to many networks. The most widely adopted open source software switch with software defined networking support is the Open vSwitch. The Open vSwitch, just as current hardware network devices, provides support for network monitoring, which is an integral part of a network management process. For this reason, this paper focuses on analysing the quality of flow monitoring features of the Open vSwitch. We propose and perform several tests of the...

Topics: network flows, Open vSwitch, measurement, Software Defined Networking

4,365
4.4K

Jun 25, 2007
06/07

by
MIT OCW, Gil Strang

movies

######
eye 4,365

######
favorite 1

######
comment 0

Mathematical Methods of Engineers II from MIT OpenCourseWare is a continuation of Mathematical Methods for Engineers I (18.085). Topics include numerical methods; initial-value problems; network flows; and optimization. Professor Gil Strang is a very popular mathematics professor at MIT.

Topic: video lectures, numerical methods, initial-value problems, network flows, optimization

Network Flow: the Encounter Complex uses no prior knowledge in its creation. It is based on encounter traces, which occur when two nodes meet. We record the time and analyze the data. Encounter traces can include: two animals meet at a watering hole. Two users use the same wireless node.

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST, *NETWORK FLOWS, CHARTS,...

Journal of Research of the National Bureau of Standards

Topics: Basic cut�sets, cut�sets, graph theory, network flows, mathematics, segs

A technique which yields fast parallel algorithms for several zero-one supply-demand problems is presented. We give NC algorithms for the following related problems: (1) Given a sequence of supplies a1, ..., an and demands b1, ..., bm, construct a zero-one flow pattern satisfying these constraints, where every supply vertex can send at most one unit of flow to each demand vertex. (2) Given a sequence of positive and negative integers summing to zero, representing supplies and demands...

Topics: DTIC Archive, CALIFORNIA UNIV BERKELEY COMPUTER SCIENCE DIV, *ALGORITHMS, *PARALLEL PROCESSING,...

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST, *NETWORK...

In this project we developed an input-output approach to predict and engineer collective behavior in networks. This approach overcomes the complexity of the large-scale, nonlinear dynamical model by dividing the analysis and design tasks into two layers: At the network layer, we represent the nodes with appropriate input-output properties as abstractions of their detailed models and exploit these properties in conjunction with the interconnection structure to ascertain desirable behaviors. At...

Topics: DTIC Archive, CALIFORNIA UNIV REGENTS BERKELEY, *NONLINEAR SYSTEMS, CONTROL, DYNAMICS, INPUT OUTPUT...

At FloCon 2005, conference participants gathered to discuss flow and network security analysis and ways to improve these technologies. These proceedings are comprised of a collection of papers and briefing charts without a table of contents. Content titles include: ** NVisionIP: An Animated State Analysis Tool for Visualizing NetFlows by Ratna Bearavolu, Kiran Lakkaraju and William Yurcik; ** NERD: Network Emergency Responder & Detector (briefing charts) by W. Biemolt; ** IP Flow...

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST, *COMPUTER NETWORK...

This FloCon conference included 12 papers and 13 presentations given by experts in the field of flow analysis. Discussions covered topics as flow processing, flow measurement, network traffic, and analysis methods. Contents include: ** IPFIX/PSAMP: What Future Standards can Offer to Network Security by Tanja Zseby, Elisa Boschi, Thomas Hirsch, and Lutz Mark; ** The Past and Future of Flow Analysis (briefing charts) by John McHugh; ** Attribution and Aggregation of Network Flows for Security...

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST, *COMPUTER NETWORKS,...

It has been an continuous phenomenon that more and more information is transmitted and accessible via computer data networks. Therefore data networks become a critical spot with lots of risks and threats related to it. One example can be a temporary dysfunction of network caused by an intended attack (such as DDoS attack). Attacks may lead to server failures which can mean simple inability to provide required services but also they can paralyse systems on national level (what recently happened...

Topics: DTIC Archive, MASARYK UNIV BRNO (CZECHOSLOVAKIA), *COMPUTER NETWORK SECURITY, INTRUSION...

We consider the channel ronting problem of a set of multi-terminal nets in the knock-knee model. We develop a new approach to route all the nets within d+ alpha tracks, where d is the channel density, and 0 alpha d, such that the corresponding layout can be realized with three layers. Both the routing and the layer assignment algorithms have linear time sequential implementations. In addition both can be implemented on the CREW-PRAM model in 0(n/p + logn) time, with p processors, 1 p n, and n...

Topics: DTIC Archive, Krishnamurthy, Sridhar, MARYLAND UNIV COLLEGE PARK SYSTEMS RESEARCH CENTER, *ROUTING,...

The paper presents a one pass algorithm that determines an advanced dual basic feasible solution for a class of capacitated generalized network problems. Special cases in this class of problems include transportation and transshipment problems. Computational results are included which show that this new start substantially improves the solution performance of the dual method for transportation and transshipment problems. In fact, a dual code employing this advanced start is found to be faster...

Topics: DTIC Archive, Hultz, John, TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES, *LINEAR PROGRAMMING,...

N people have distinct bits of information, which they communicate via telephone calls in which they transmit everything they know. We require that no one ever hear the same piece of information twice. In the case 4 divides n, n or = 8, we provide a construction that transmits all information using only 9n/4-6 calls. Previous construction used 1/2n log n calls. (Author)

Topics: DTIC Archive, West,Douglas B, STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE, *OPTIMIZATION,...

We report on four areas of activity in the past six months. These include, (1) work on the control of integrated video and image traffic, both at the access to a network, and within a high-speed network; (2) more general/game theoretic models for flow control in networks; (3) work on fault management for high-speed heterogeneous networks to improve survivability; (4) work on all- optical (lightwave) networks of the future, designed to take advantage of the enormous bandwidth capability...

Topics: DTIC Archive, COLUMBIA UNIV NEW YORK, *COMMUNICATIONS NETWORKS, *NETWORK ANALYSIS(MANAGEMENT),...

Progress has been made on a number of problems including improved algorithms for the minimum cut problem and the arrangement problem as well as new data compression techniques for the shortest path problem.

Topics: DTIC Archive, Orlin, James, MASSACHUSETTS INST OF TECH CAMBRIDGE, *ALGORITHMS, *NETWORK FLOWS,...

University of Illinois Urbana-Champaign

168
168

Jun 1, 2012
06/12

by
Bunch, Steve R; Healy, David C. author; McCauley, Edwin J. author; Alsberg, Peter A. Principal Investigator; University of Illinois at Urbana-Champaign Center for Advanced Computation

texts

######
eye 168

######
favorite 0

######
comment 0

The basic design of an experimental distributed data management system is presented. The system is based upon the relational model. (Author)

Topics: Information Science, Data management, Information systems, Mathematical models, Sharing, Resource...

The tasks to be performed during the development of the Secure Multilevel Data Base System include the construction of a capability for the transformation of data of higher levels of classification to data at lower levels. The capability is to be part of a system in which access control is based upon a security kernel for the PDP-11/45. In this report a mechanism for facilitating downward transformations is developed, and the impact of the mechanism upon both the Bell-LaPadula model of secure...

Topics: DTIC Archive, Stork, D. F., MITRE CORP BEDFORD MA, *DATA PROCESSING SECURITY, GRAPHICS, NETWORK...

Two new generalizations of planar graphs, called quasiplanar and pseudoplanar graphs, are introduced and discussed. A graph is called quasiplanar if for each node t, the set of nodes incident to t can be labeled 1, ... , m so that for each 1 or = h i j k or = m, each pair of paths not containing t and having respective endnodes h,j and i,k share a common node. A (directed) graph is called pseudoplanar if for each pair of nodes s,t, the set of nodes adjacent to t can be labeled 1, ... , m so...

Topics: DTIC Archive, Erickson,Ranel E, STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH, *GRAPHS, *NETWORK...

An implementation of the fastest known algorithm to find the vertex connectivity of graphs with reduced space requirement is presented. Keyword: Network flows; Problem solving.

Topics: DTIC Archive, Girkar,Milind, ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP, *NETWORK...

A primary focus of this project is on how to find quickly good solutions and tight bounds on their quality for hard combinatorial optimization and integer programming problems. One of the basic ideas is to do repeated local search by solving small integer programs defined by fixing many of the variables. We demonstrate the effectiveness of such an approach by developing and testing such an algorithm for large-scale fixed-charge network flow (FCNF) problems [1]. The solution approach combines...

Topics: DTIC Archive, GEORGIA INST OF TECH ATLANTA, *INTEGER PROGRAMMING, ALGORITHMS, COMBINATORIAL...

This report provides a step-by-step guide for profiling discovering public-facing assets on a network using network flow (netflow) data. Netflow data can be used for forensic purposes, for finding malicious activity, and for determining appropriate prioritization settings. The goal of this report is to create a profile to see a potential attacker s view of an external network. Readers will learn how to choose a data set, find the top assets and services with the most traffic on the network, and...

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST, *NETWORK FLOWS, DATA...

Open computing environments are under a deluge of network attacks from complex threats. These threats are distributed, decentralized , dynamic, and operate over multiple timescales. Trusted Computing environments provide a means to manage cryptographic identity and authentication operations in the form of static assertions, but were not developed to provide complete end-to-end security for heterogeneous environments such as the NATO Architecture Framework (NAF). There is a gap in the contextual...

Topics: DTIC Archive, SONALYSTS INC WATERFORD CT, *COMPUTER NETWORK SECURITY, IDENTIFICATION, THREAT...

The paper addresses a variant of the minimum spanning tree problem in which a given node is required to have a fixed number of incident edges. It is shown that this problem, which is combinatorially a level of complexity beyond the ordinary minimum spanning tree problem, can be solved by a highly efficient 'quasi-greedy' algorithm. Applications include a telecommunication linking problem and a new relaxation strategy for the traveling salesman problem via appropriately defined order-constrained...

Topics: DTIC Archive, Glover, Fred, TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES, *NETWORK FLOWS,...

Delivering real-time streaming content requires finding paths with a minimum required bandwidth. Finding such paths when requested should be fast (low start-up latency) and efficient (high call acceptance rates). However, current algorithms for finding such QoS paths, are ineffective when the bulk of the flows are short-lived. First, these algorithms are computationally expensive to justify invoking them on a per-request basis, and they add substantial latency to the signaling process....

Topics: DTIC Archive, Vutukury, Srinivas, CALIFORNIA UNIV SANTA CRUZ SCHOOL OF ENGINEERING, *ROUTING,...

A number of problems in network operations and engineering call for new methods of traffic analysis. While most existing traffic analysis methods are fundamentally temporal, there is a clear need for the analysis of traffic across multiple network links--that is, for spatial traffic analysis. In this paper we give examples of problems that can be addressed via spatial traffic analysis. We then propose a formal approach to spatial traffic analysis based on the wavelet transform. Our approach...

Topics: DTIC Archive, Crovella, Mark, BOSTON UNIV MA, *NETWORK ANALYSIS(MANAGEMENT), *WAVELET TRANSFORMS,...

Discussion of intrusion detection methods, including the issues of scalability, data mining, anomaly detection, and false positives.

Topics: DTIC Archive, Miller, A., MISSOURI UNIV-ROLLA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING,...

This research develops an attacker-defender model of maritime trading. The defender's problem is represented as a minimum cost, multi-commodity network flow model. System cost is measured in terms of total ton-n.m. in the network. Our network contains the 120 most important ports in the world (by volume of cargo), 35 waypoints at sea, and 416 arcs. Port supply and demand have been estimated from different sources. Interdictions represent manmade disruption of the seaways, such as those in the...

Topics: DTIC Archive, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, *DEFENSE SYSTEMS, *INTERNATIONAL TRADE,...

The dynamic tree expression problem (DTEP) was defined in (Ma87). In this paper, efficient implementations of the DTEP algorithm are developed for the hypercube, butterfly, perfect shuffle and multi-dimensional mesh of trees families of networks.

Topics: DTIC Archive, Mayr, E. W., STANFORD UNIV CA, *ALGORITHMS, *NETWORK FLOWS, DYNAMICS, MESH, TREES,...

A new, fast algorithm has been developed for the solution of problems using Lagrangian relaxation. This algorithm appears to improve running times by a factor of n-squared, where n is the number of variables.

Topics: DTIC Archive, Orlin, James B, MASSACHUSETTS INST OF TECH CAMBRIDGE, *ALGORITHMS, *NETWORK FLOWS,...

This paper establishes a necessary condition for a set of spherical (n-1)-simplicies to cover the sphere S superscript (n-1) in R suberscript n. It is shown that the condition is also sufficient when n = 2 but is not so when n 2. The result can be viewed as a property of Q-matrices, which arise in connection with the linear complementarity problem. It follows from two others also proved here. One is a partitioning theorem for a particular type of convex body known as a simplotope (the cartesian...

Topics: DTIC Archive, Cottle,Richard W, STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH, *MATRIX THEORY,...

This paper describes an implementation of the Push-Relabel method for the Maximum Flow problem on a Connection Machine and gives computation times of the implementation on several classes of problems.

Topics: DTIC Archive, Alizadeh, Farid, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, *COMPUTATIONS, *NETWORK...

We consider the approximation algorithm of Leighton et. al. for the multicommodity flow problem. We give a more natural randomization strategy that is simpler than the one in the original algorithm and results in a better running time. This strategy also applies to several related algorithms.

Topics: DTIC Archive, Goldberg, Andrew V, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, *ALGORITHMS, *NETWORK...

This briefing looks at interoperable software that allows individual platforms to feed forward information about itself up the enterprise to assist in fleet management, maintenance, logistics and data mining. There is a need to design architectures with openness, upgradeability, and scalability in mind. DoDAF Technical Views for systems with CBM+ community must be standardized by defining standards using trade-off studies and proof of concept demonstrations.

Topics: DTIC Archive, Bechtel, Jim, TACOM RESEARCH DEVELOPMENT AND ENGINEERING CENTER WARREN MI, *GROUND...

This report covers some of the first applications of laboratory experimental methods in economics to the problems of understanding the principles that govern adjustments in complex networks of markets exchange processes. Key experiments were conducted in several areas to determine the appropriateness of classical economics models. Because the nature of networks suggests the possibility of instability and because there was little previous understanding of how to study instability experimentally,...

Topics: DTIC Archive, Plott, Charles R, CALIFORNIA INST OF TECH PASADENA, *NETWORK FLOWS, *ECONOMIC MODELS,...

Edmonds has given a complicated algorithmic proof of a theorem characterizing directed graphs that contain k edge-disjoint branchings having specified root sets. Tarjan has described a conceptually simple and good algorithm for finding such branchings when they exist. Tarjan's algorithm is based on a lemma implicit in Edmonds' results. A simple direct proof of this lemma is given, thereby providing a simpler proof of Edmonds' theorem and a simpler proof that Tarjan's algorithm works.

Topics: DTIC Archive, Fulkerson, D R, Harding, Gary, CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH,...

Presentation on Adaptive Logistics: Complexity and Adaptation. Agenda of the presentation consists of: Introduction, Network Fundamentals, Complex Control Fundamentals, Sense and Respond Logistics.

Topics: DTIC Archive, Cares, Jeffrey R, ALIDADE INC NEWPORT RI, *NETWORKS, *LOGISTICS, OPTIMIZATION,...

Building Information Modeling (BIM) technology has rapidly gained acceptance throughout the planning, architecture, engineer-ing, construction, operations, and maintenance industries. The challenge for the US Army Corps of Engineers (USACE) is to ex-tend BIM use beyond its basic labor- and time-saving benefits to become a fully realized information network that permanently transforms conventional business processes to unprecedented levels of efficiency and organization. This document describes...

Topics: DTIC Archive, AUTODESK INC SAN RAFAEL CA, *COMPUTER PROGRAMS, *CONSTRUCTION, *DATA MANAGEMENT, LIFE...

University of Illinois Urbana-Champaign

252
252

Jun 25, 2012
06/12

by
Alsberg, Peter A. author; Belford, Geneva G. author; Day, John D. author; Grapa, Enrique. author; University of Illinois at Urbana-Champaign. Center for Advanced Computation

texts

######
eye 252

######
favorite 0

######
comment 0

Includes bibliographic references (p. 48)

Topics: Information Science, Computer Hardware, Data management, Communications networks, Mathematical...

The paper describes a procedure for determining if constrained network problems (i.e., network problems with additional linear constraints) can be transformed into equivalent pure network problems by a linear transformation involving the node constraints and the extra constraints. The results extend procedures for problems in which the extra constraints consist of bounding certain partial sums of variables.

Topics: DTIC Archive, Klingman, Darwin, TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES, *NETWORK FLOWS,...

This research explores the potential of agent technology for adaptive Quality of Service (QoS) management of C4ISR networks. With the growing emphasis on information superiority, any time savings or additional utilization of resources enabled by effective network management becomes increasingly important. Intelligent agents are ideal for assessing information, adapting to dynamic conditions, and predicting future network conditions. In the kernel of the proposed multiple agent system (MAS)...

Topics: DTIC Archive, Rivera, Raymond A, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, *COMMUNICATIONS NETWORKS,...

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST, *NETWORK...

Spectroscope is a new toolset aimed at assisting developers with the long-standing challenge of performance debugging in distributed systems. To do so, it mines end-to-end traces of request processing within and across components. Using Spectroscope, developers can visualize and compare system behaviours between two periods or system versions, identifying and ranking various changes in the flow or timing of request processing. Examples of how Spectroscope has been used to diagnose real...

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA PARALLEL DATA LABORATORY, *SOFTWARE TOOLS,...

Research will test the hypothesis that the R3 routing architecture can be used to provide robust networking with reasonable levels of mobility. The hypothesis will be tested by using a network simulation tool (OPNET) to measure the performance of a network of static and mobile nodes and emulated wireless links. The goal is not to simulate the wireless environment but to model the impact of mobility on routing over such an environment. The simulations will cover: --Intermittent links --Links of...

Topics: DTIC Archive, Baughan, Kevin J, IDEAS NETWORK LTD BIRMINGHAM (UNITED KINGDOM), *COMMUNICATIONS...

Topics: DTIC Archive, CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST, *NETWORK...

The report describes the notions of duality and network flow and shows how these are used in the construction of algorithms for certain classes of LP (linear programming) problems. Reports that the problems include transportation problem network flow at minimum cost, and scheduling of activities at minimum cost in a PERT-like, or critical-path, system of project organization.

Topics: DTIC Archive, Karush, W, SYSTEM DEVELOPMENT CORP SANTA MONICA CA, *LINEAR PROGRAMMING,...

A mixed-integer linear programming formulation is developed for minimizing delay to traffic in a signal controlled road network. Offsets, splits of green time and a common cycle time for the network are considered as decision variables simultaneously. The traffic flow pattern is modeled as a periodic platoon, and a link performance function is derived in the form of a piecewise linear convex surface representing the delay incurred by these platoons. Stochastic effects are accounted for by a...

Topics: DTIC Archive, Gartner, Nathan, MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER,...

This research effort presents a formalism for writing programs which explicitly addresses and highlights some program construction issues. The formalism, a kind of production system, generates a graph that defines the process under inspection, making explicit both when and where variable bindings take place. From the standpoint of proper data structuring these extra dimensions are useful for analyzing a program, particularly with respect to ease of data access, access ambiguity, proper sequence...

Topics: DTIC Archive, Wilczynski, David, UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION...

Network theory and the theory of queues under several servicing priorities are combined in a mathematical simulation of requisition processing. Data describing requisition processing at NSC Norfolk and the Ships Parts Control Center are presented. Throughput time distributions which are observed are compared to throughput time distributions predicted by the simulation model. Generally, the model failed to explain requisition waiting times due to backlogs.

Topics: DTIC Archive, Lady, George M, RMC RESEARCH CORP BETHESDA MD, *NAVAL VESSELS, *SUPPLIES, COMPUTER...

Three alternatives are presented for the design of a scheduler for a multi-miniprocessor system. The alternatives are based in general on the theory of parallel program schemata and in particular on a new parallel derivative technique for constructing the maximally parallel flowchart equivalent to a given one.

Topics: DTIC Archive, Millen, J. K., MITRE CORP MCLEAN VA, *SCHEDULING, *MULTIPROCESSORS, *PARALLEL...