Search

An increasing number of high-performance networks provision dedicated channels through circuit switching or MPLS/GMPLS techniques to support large data transfer. The link bandwidths in such networks are typically shared by multiple users through advance reservation, resulting in varying bandwidth availability in future time. Developing efficient scheduling algorithms for advance bandwidth reservation has become a critical task to improve the utilization of network resources and meet the transport requirements of application users. We consider an exhaustive combination of different path and bandwidth constraints and formulate four types of advance bandwidth scheduling problems, with the same objective to minimize the data transfer end time for a given transfer request with a prespecified data size: 1) fixed path with fixed bandwidth (FPFB); 2) fixed path with variable bandwidth (FPVB); 3) variable path with fixed bandwidth (VPFB); and 4) variable path with variable bandwidth (VPVB). For VPFB and VPVB, we further consider two subcases where the path switching delay is negligible or nonnegligible. We propose an optimal algorithm for each of these scheduling problems except for FPVB and VPVB with nonnegligible path switching delay, which are proven to be NP-complete and nonapproximable, and then tackled by heuristics. The performance superiority of these heuristics is verified by extensive experimental results in a large set of simulated networks in comparison to optimal and greedy strategies.

High-performance networks are capable of provisioning dedicated channels through circuit/lambda-switching or MPLS/GMPLS techniques to support large-scale data transfer. These dedicated links are typically shared by multiple users through advance resource reservations, resulting in varying bandwidth availability in future time periods. Most previous efforts were focused on centralized bandwidth scheduling to improve the utilization of network resources and meet the transport requirements of application users. These centralized scheduling schemes imply the use of a central control plane, posing significant reliability and scalability challenges as the network size rapidly grows. We propose distributed algorithms for path computation and bandwidth scheduling in response to four basic bandwidth reservation requests: (i) fixed bandwidth in a fixed slot, (ii) highest bandwidth in a fixed slot, (iii) first slot with fixed bandwidth and duration, and (iv) all slots with fixed bandwidth and duration. These algorithms are developed through a rigorous extension of the classical breadth first search and Bellman-Ford algorithms to a completely distributed manner, and their performances are evaluated and analyzed through extensive simulations.

Detecting and identifying security events to provide cyber situation awareness has become an increasingly important task within the network research and development community. We propose a graph similarity-based approach to event detection and identification that integrates a number of techniques to collect time-varying situation information, extract correlations between event attributes, and characterize and identify security events. Diverging from the traditional rule- or statistical-based pattern matching techniques, the proposed mechanism represents security events in a graphical form of correlation networks and identifies security events through the computation of graph similarity measurements to eliminate the need for constructing user or system profiles. These technical components take fundamentally different approaches from traditional empirical or statistical methods and are designed based on rigorous computational analysis with mathematically proven performance guarantee. The performance superiority of the proposed mechanism is demonstrated by extensive simulation and experimental results.

The traditional client-server architecture widely adopted on the Internet is not adequate to meet the increasing user loads and bandwidth demands in live streaming systems especially for multimedia content delivery. Peer-to-peer P2P) overlay networks provide excellent system scalability and high resource utilization, which make it an attractive solution to this problem. This paper considers a hybrid hierarchical P2P overlay network structure that consists of both super and normal peers. The media streaming architecture is built upon a tree structured network of super peers and the tree construction process has a significant impact on the overall system performance. We construct network cost models and formulate a Bandwidth Constrained Tree (BCT) construction problem, which aims at maximizing the number of peers that satisfy a specified bandwidth constraint. We prove that BCT is NP-complete and propose optimal algorithms in two special cases and a heuristic approach in a general case. The performance superiority of the proposed method is illustrated by an extensive set of experiments on simulated networks of various sizes in comparison with existing greedy and degree constrained algorithms.

The client-server architecture widely adopted on the Internet is not adequate to meet the ever-increasing user loads and bandwidth demands in live streaming systems especially for multimedia content delivery. Peer-to-peer (P2P) overlay networks provide excellent system scalability and high resource utilization, which make it an attractive solution to this problem. We consider a hybrid hierarchical P2P overlay network that consists of both super and normal peers to support live streaming applications. This architecture is built upon a tree-structured network of super peers, which organize normal peers into clusters. The tree construction process has a significant impact on the overall system performance. We formulate a specific type of problem, max-minTC, to maximize the minimum node throughput in tree construction, where the system's stream rate is optimized by constructing an efficient spanning tree among super peers. We present a decentralized approach where super peers run the same algorithm in parallel to derive a tree from an identical database describing the topology of the streaming system. This approach is able to quickly converge to a new tree upon the detection of any topological changes in super peers. The performance superiority of the proposed solution is illustrated by extensive simulations on a large set of simulated networks of various sizes from small to large scales in comparison with other methods.

This paper considers a hybrid hierarchical P2P overlay network structure that consists of both super and normal peers. The media streaming architecture is built upon a tree-structured network of super peers and the tree construction process has a significant impact on the overall system performance. We build network cost models and formulate a specific type of problem to maximize the minimum node throughput in Tree Construction (max-minTC), which aims at optimizing the system's stream rate by constructing an efficient spanning tree among super peers. We consider two scenarios: (i) When the overlay network has an arbitrary topology, we prove max-minTC to be NP-complete by reducing from the Degree Constrained Spanning Tree problem and propose an efficient heuristic algorithm. The performance superiority of the proposed algorithm is justified by experimental results collected by a live media streaming system deployed in real networks and is also illustrated by extensive simulations performed on a large set of simulated networks of various sizes from small to large scales in comparison with other methods, (ii) When the topology of the overlay network is complete, we rigorously prove that the same heuristic algorithm yields an optimal solution.

Data transmission from sensor nodes to a base station or a sink node often incurs significant energy consumption, which critically affects network lifetime. We generalize and solve the problem of deploying multiple base stations to maximize network lifetime in terms of two different metrics under one-hop and multihop communication models. In the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution and a heuristic approach based on the minimal enclosing circle algorithm to deploy a base station at the geometric center of each cluster. In the multihop communication model, both base station location and data routing mechanism need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing paths for data transmission. Simulation results show the distinguished performance of the proposed deployment algorithms in maximizing network lifetime.

The success of various sensor network applications highly depends on the use of energy-conserving routing methods to prolong network lifetime. We present a heterogeneous sensor network architecture consisting of a small number of high-end sensors serving as sink nodes and a large number of low-end sensors responsible for environmental sensing. We propose a path bottleneck-oriented and energy cost-based routing scheme that uses a multi-objective function to optimize the balance of network-wide energy consumption. Within this routing scheme, we design (i) a centralized version for sensor networks with global topology information, (ii) a semi-distributed version to further improve energy efficiency, and (iii) a fully distributed version to support large-scale sensor networks. Extensive simulation results show that the proposed routing scheme outperforms existing routing algorithms in prolonging the lifetime of sensor networks.

Peer-to-peer (P2P) overlay networks provide a highly effective and scalable solution to live media streaming systems that require the collective use of massively distributed network resources. A P2P media streaming architecture is typically built completely or partially upon a tree-structured network topology and the process of tree construction has a significant impact on the overall system performance. We build network cost models and formulate a specific type of topology construction problem, Maximum Average Bandwidth Spanning Tree (MABST), which aims at optimizing the system's average stream rate. We prove that MABST is NP-complete by reducing from Hamiltonian Path problem and propose an efficient heuristic algorithm. The performance superiority of the proposed algorithm is justified by experimental results using a live media streaming system deployed in real networks and is also illustrated by an extensive set of simulations on simulated networks of various sizes in comparison with other methods based on a degree constraint or a greedy strategy.

We propose an adaptive cyber security monitoring system that integrates a number of component techniques to collect time-series situation information, perform intrusion detection, and characterize and identify security events so corresponding defense actions can be taken in a timely and effective manner. We employ a decision fusion algorithm with analytically proven performance guarantee for intrusion detection based on local votes from distributed sensors. The security events in the proposed system are represented as forms of correlation networks using random matrix theory and identified through the computation of network similarity measurement. Extensive simulation results on event identification illustrate the efficacy of the proposed system.

There are an increasing number of high-performance networks that provision dedicated channels through circuit-switching or MPLS/GMPLS techniques to support bulk data transfer in large-scale science or e-commerce applications. These dedicated links are typically shared by multiple users through advance reservations, resulting in varying bandwidth availability in future time periods. Therefore, efficient advance bandwidth reservation algorithms are needed to improve the utilization of network resources and meet the transport requirements of application users. We investigate the bandwidth-oriented path computation problem for two types of data transfer: (i) fixed path with variable bandwidth and (ii) variable path with variable bandwidth to minimize the transfer end time of a given data size. We prove that both problems are NP-complete and propose a heuristic algorithm for each of them. Extensive simulation results illustrate the performance superiority of the proposed heuristics over methods based on greedy strategies.

Sensor network lifetime is largely affected by the energy consumption for data transmission from sensor nodes to a base station. We generalize and solve the problems of deploying multiple base stations in sensor networks using one-hop and multi-hop communication models to maximize network lifetime. Under the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution for small-scale networks and a heuristic approach for large-scale ones based on the smallest enclosing circle algorithm that deploys a base station at the geometric center of each cluster. Under the multi-hop communication model, both the base station locations and the data routing scheme need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing path for benchmark purposes. Extensive simulation results show superior network lifetime performance of the proposed deployment algorithms in comparison with existing ones.

The significance of high-performance dedicated networks has been well recognized due to the rapidly increasing number of large-scale applications that require high-speed data transfer. Efficient algorithms are needed for path computation and bandwidth scheduling in dedicated networks to improve the utilization of network resources and meet diverse user requests. We consider two periodic bandwidth scheduling problems: multiple data transfer allocation (MDTA) and multiple fixed-slot bandwidth reservation (MFBR), both of which schedule a number of user requests accumulated in a certain period. MDTA is to assign multiple data transfer requests on several pre-specified network paths to minimize the total data transfer end time, while MFBR is to satisfy multiple bandwidth reservation requests, each of which specifies a bandwidth and a time slot. For MDTA, we design an optimal algorithm and provide its correctness proof; for MFBR, we prove it to be NP-complete and propose a heuristic algorithm, Minimal Bandwidth and Distance Product Algorithm (MBDPA). Extensive simulation results illustrate the performance superiority of the proposed MBDPA over a greedy heuristic approach and provide valuable insight into the advantage of periodic bandwidth scheduling over instant bandwidth scheduling.

There are an increasing number of high- performance networks that provision dedicated channels through circuit-switching or MPLS/GMPLS techniques to support large- scale data transfer. The available bandwidths on these dedicated links vary over time and therefore efficient bandwidth scheduling algorithms are needed to improve the utilization of network resources and satisfy diverse user requirements. Based on different path and bandwidth constraints, we formulate four instant scheduling problems for a data transfer request: (i) variable path with variable bandwidth (VPVB), (ii) fixed path with variable bandwidth (FPVB), (iii) variable path with fixed bandwidth (VPFB), and (iv) fixed path with fixed bandwidth (FPFB), with the common objective to minimize transfer end time for a given data size. We design an optimal algorithm for each of these scheduling problems with polynomial- or pseudo- polynomial-time complexity with respect to the network size and total number of time slots in a bandwidth reservation table.

UNLABELLED High-throughput genomic technologies enable researchers to identify genes that are co-regulated with respect to specific experimental conditions. Numerous statistical approaches have been developed to identify differentially expressed genes. Because each approach can produce distinct gene sets, it is difficult for biologists to determine which statistical approach yields biologically relevant gene sets and is appropriate for their study. To address this issue, we implemented Latent Semantic Indexing (LSI) to determine the functional coherence of gene sets. An LSI model was built using over 1 million Medline abstracts for over 20,000 mouse and human genes annotated in Entrez Gene. The gene-to-gene LSI-derived similarities were used to calculate a literature cohesion p-value (LPv) for a given gene set using a Fisher's exact test. We tested this method against genes in more than 6,000 functional pathways annotated in Gene Ontology (GO) and found that approximately 75% of gene sets in GO biological process category and 90% of the gene sets in GO molecular function and cellular component categories were functionally cohesive (LPv

An increasing number of high performance research network testbeds and production networks have the capability of provisioning dedicated channels for high speed data transfer in support of large scale scientific applications. Each dedicated channel in these networks typically consists of one or more physical links that are shared by multiple applications in both time and bandwidth through in advance reservation. The design of efficient bandwidth scheduling algorithms is critical to maximizing the utilization of dedicated network resources and meeting diverse end-to-end transport performance requirements. The topology of a dedicated network is represented by a graph, where each link maintains a list of residual bandwidths specified as segmented constant functions of time. Given a graph with an aggregated time-bandwidth table combining the reservation information on all links, designated source, and destination vertices, and a specified data size, we formulate and investigate five bandwidth scheduling problems to minimize the data transfer end time under different path and bandwidth constraints: (i) variable path with variable bandwidth (VPVB), which computes the widest (highest bandwidth) path in each time slot; (ii) fixed path with variable bandwidth (FPVB), which computes a fixed path with varying bandwidths across different time slots; (iii) variable path with fixed bandwidth (VPFB), which computes one path in each time slot with the same bandwidth; (iv) fixed path with fixed bandwidth (FPFB), which computes a fixed path with a constant bandwidth; and (v) multiple fixed paths with fixed bandwidths (MFPFB), which computes multiple concurrent fixed paths with constant bandwidths. Among these problems, VPVB represents the most flexible scenario where the network resources are fully utilized and the minimal transfer end time is achieved, while FPFB imposes the most stringent transport conditions by fixing both path and bandwidth. We design an optimal algorithm for each of these scheduling problems. VPVB is solved using an extension of the classical Dijkstra's algorithm, and FPVB is solved using Maximum Permutation Algorithm, which tries all possible permutations of throughputs at different time slots to obtain the minimal transfer end time. The algorithm for VPFB, FPFB, and MFPFB are based on Adjacent Time Slots Search, which finds the minimum transfer end time by examining the possibility of data transfer in any number of contiguous time slots. All these algorithms are of polynomial or pseudo polynomial time complexity with respect to the network size and the total number of time slots in a bandwidth reservation table.