The deployment of large-scale LoRaWAN networks requires jointly optimizing conflicting metrics like Packet Delivery Ratio (PDR) and Energy Efficiency (EE) by dynamically allocating transmission parameters, including Carrier Frequency, Spreading Factor, and Transmission Power. Existing algorithms often ignore the complexity of multi-objective dynamic adaptation to oversimplify this challenge, focusing on a single metric or lacking the adaptability needed for dynamic channel environments, leading to suboptimal performance. To address this, we propose two online learning-based resource allocation frameworks that intelligently navigate the PDR-EE trade-off. Our foundational proposal, D-LoRa, is a fully distributed framework that models the problem as a Combinatorial Multi-Armed Bandit. By decomposing the joint parameter selection and employing specialized, disaggregated reward functions, D-LoRa dramatically reduces learning complexity and enables nodes to autonomously adapt to network dynamics. To further enhance performance in LoRaWAN networks, we introduce CD-LoRa, a hybrid framework that integrates a lightweight, centralized initialization phase to perform a one-time, quasi-optimal channel assignment and action space pruning, thereby accelerating subsequent distributed learning. Extensive simulations and real-world field experiments demonstrate the superiority of our frameworks, showing that D-LoRa excels in nonstationary environments while CD-LoRa achieves the fastest convergence. In physical deployments, our algorithms outperform state-of-the-art baselines, improving PDR by up to 10.8% and EE by 26.1%, demonstrating their practical effectiveness. Moreover, extensive simulations with up to 250 nodes confirm the scalability and efficiency of the proposed frameworks in large-scale LoRaWAN networks.

The deployment of LoRa networks necessitates joint performance optimization, including packet delivery rate, energy efficiency, and throughput, by dynamically configuring multiple LoRa parameters for packet transmission across varying channel environments. Due to the complexity of modeling channel features and the coupling relationship between LoRa parameters and metrics, existing works have sacrificed adaptability by focusing on specific aspects rather than the whole. Therefore, we propose D-LoRa, a distributed parameter adaptation scheme, based on reinforcement learning towards network performance. We first build a comprehensive analytical model for the LoRa network that considers complex channel features, including path loss, quasiorthogonality of spreading factor, and packet collision. Then, we formulate the joint optimization problem as a combinatorial Multi-Armed Bandit (CMAB) problem and devise metric factors to handle the trade-off among different performance metrics. Experimental results show that our scheme can increase the packet delivery rate by up to 18.5% and demonstrate superior adaptability across different performance metrics.

Accurate per-flow measurement is essential for effective network management in programmable networks. However, achieving this accuracy remains challenging due to limited switch resources and the massive scale of network flows. Existing sketch-based methods often encounter significant measurement errors, particularly when dealing with the large number of extremely small flows, known as "ant flows". To address this issue, this paper introduces Mix Sketch, a novel measurement framework designed for differentiated and precise per-flow measurement. Mix Sketch uniquely categorizes traffic into elephant, mouse, and ant flows, and employs a tailored three-level structure to measure each flow category appropriately. This approach significantly enhances measurement accuracy, especially for ant flows. Furthermore, we propose Co-Mix Sketch, a lightweight collaborative measurement scheme that leverages network topology to distribute Mix Sketch components across different node tiers, thereby optimizing resource utilization and improving accuracy without requiring complex coordination. Evaluations conducted on real-world traffic traces demonstrate that Mix Sketch substantially outperforms baseline single-node methods, while Co-Mix Sketch achieves notable accuracy improvements with minimal overhead compared to existing collaborative approaches.

Traffic measurement is essential for network management. Sliding window models can provide network management tasks with flow statistics within the most recent window at any moment. However, most existing solutions over sliding windows are not designed for traffic measurement scenarios, therefore they have higher complexity and cannot be implemented on programmable hardware switches. To address the issues, we designed Ring Sketch, which is a generic, low-complexity, and hardware-friendly traffic measurement framework over sliding windows. Ring Sketch can not only be easily implemented on programmable hardware switches but can also accurately answer typical flow statistics queries by using different sketches. Then we propose the estimation strategies for Ring Sketch and theoretically analyze its error bounds. At last, we implement Ring Sketch on OVS-DPDK and a programmable hardware switch with a Tofino chip, and all the source codes are released on GitHub. The experimental results show that Ring Sketch has a throughput over 3x higher than the state-of-the-art Sliding Sketch, and in typical measurement tasks, Ring Sketch can achieve high measurement accuracy.

Using multiple unmanned aerial vehicles (UAVs) with backscatter communication to collect data from Internet of Things (IoT) devices has emerged as a promising solution. However, many existing UAVs path planning schemes for data collection suffer from performance degradation due to their limited consideration of the full collaboration of UAVs and dynamic stochastic environments. Therefore, we propose a path planning scheme for the data collection task in multi-UAV IoT based on multi-agent reinforcement learning (MARL) to minimize the task completion time. Due to the inherent asynchronous decision making among the agents, we model the path planning problem as a macro-action decentralized partially observable Markov decision process. Furthermore, we design an action mask mechanism to enhance data efficiency, which accelerates the training speed. Simulation results show that our scheme reduces the average task completion time by 15 %.

Traffic measurement is critical for network manage-ment. The programmable networking paradigm paves the way for implementing fine-grained and accurate traffic measurement. However, in programmable networking, the programmable re-sources on hardware switches are highly limited. Most existing solutions have not considered the deployment of multiple traffic measurement tasks under resource constraints in programmable networks. To address the issue, we construct the network model and problem formulation, and we refer to this problem as the traffic measurement task deployment problem and prove it is NP-hard. To solve it, we proposed an approximate algorithm called Ant Colony Optimization with Dynamic Pruning (ACO-DP). We conducted simulations on the Fat-Tree topologies to evaluate the performance of ACO-DP. The evaluation results show that ACO-DP can achieve much higher overall measurement utility and faster convergence compared to other benchmark algorithms, and the solutions returned by ACO-DP are very close to the optimal solutions.

Genomic selection (GS) has emerged as an effective technology to accelerate crop hybrid breeding by enabling early selection prior to phenotype collection. Genomic best linear unbiased prediction (GBLUP) is a robust method that has been routinely used in GS breeding programs. However, GBLUP assumes that markers contribute equally to the total genetic variance, which may not be the case. In this study, we developed a novel GS method called GA-GBLUP that leverages the genetic algorithm (GA) to select markers related to the target trait. We defined four fitness functions for optimization, including AIC, BIC, R2, and HAT, to improve the predictability and bin adjacent markers based on the principle of linkage disequilibrium to reduce model dimension. The results demonstrate that the GA-GBLUP model, equipped with R2 and HAT fitness function, produces much higher predictability than GBLUP for most traits in rice and maize datasets, particularly for traits with low heritability. Moreover, we have developed a user-friendly R package, GAGBLUP, for GS, and the package is freely available on CRAN (https://CRAN.R-project.org/package=GAGBLUP).

Wireless blockchain networks have played an important role in many network scenarios, among which wireless Practical Byzantine Fault Tolerance (PBFT) consensus is regarded as one of the most important consensus mechanisms. It enables nodes in wireless networks to reach consistency without any trusted entity. However, due to the instability of wireless communication links, the reliability of the PBFT consensus will be seriously affected. Meanwhile, it is difficult for nodes in wireless scenarios to obtain a timely energy supply. The high-energy-consumption blockchain functions will quickly consume the power of nodes, thus, affecting consensus performance. Fortunately, the symbiotic radio (SR) system enabled by cognitive backscatter communications can provide a solution to the above problems. In SR, the secondary transmitter (STx) transmits messages by modulating its information over the radio frequency (RF) signal of the primary transmitter (PTx) with extremely low energy consumption, and the STx can provide multipath gain to the PTx in return. In our paper, we propose the symbiotic PBFT (S-PBFT) consensus benefited from the mutualistic transmission in SR, which can increase the consensus security by 54.82 %, and save energy consumption by about 10%.

The fast anomaly detection and localization is essential for network management, however, it is also very challenging for the current networks due to the lack of flexible control and telemetry capabilities. Fortunately, the maturity of Deep Reinforcement Learning (DRL) and programmable networking technologies could shed a light on realizing fast and intelligent anomaly detection and localization. In the paper, we design a fast anomaly detection and localization system for programmable networks by leveraging the in-band network telemetry and flexible control capabilities of programmable networks. Based on the system, we propose a DRL-based abnormal link detection and localization algorithm. It can iteratively infer abnormal links based on the ingress-to-egress performance metrics of flows and the one-hop performance metrics of the flows on the already identified abnormal links. The simulation results show that our proposals can detect and localize link anomalies in a matter of seconds to tens of seconds with low network telemetry overhead.

With the development of Mobile Edge Computing (MEC) and Internet of Things (IoT) technology, various real-time monitoring and control applications are deployed to benefit people’s daily life. The performance of these applications relies heavily on the timeliness of collected environmental information, which can be effectively quantified by the recently introduced metric named age of information (AoI). Although extensive researches have been conducted to optimize AoI under various circumstances, these works commonly require a priori information about the system dynamics that is usually unknown in realistic situations. To design a more practical scheduling algorithm, in this paper, we formulate the AoI minimization problem as a Constrained Markov Decision Process (CMDP) which can be solved by Reinforcement Learning (RL) algorithms without prior knowledge. To improve the running efficiency, we (1) introduce post-decision states (PDSs) to exploit the partial knowledge of the system’s dynamics, (2) perform a batch update in every learning step, (3) decompose the system-level value function into multiple device-level value functions, and (4) propose a heuristic algorithm to find the greedy action. Numerical results demonstrate that our algorithm is highly efficient and outperforms the benchmarks under various scenarios.

The integration of Mobile Edge Computing (MEC) and Wireless Power Transfer (WPT), which is usually referred to as Wireless Powered Mobile Edge Computing (WP-MEC), has been recognized as a promising technique to enhance the lifetime and computation capacity of wireless devices (WDs). Compared to the conventional battery-powered MEC networks, WP-MEC brings new challenges to the computation scheduling problem because we have to jointly optimize the resource allocation in WPT and computation offloading. In this paper, we consider the energy minimization problem for WP-MEC networks with multiple WDs and multiple access points. We design an online algorithm by transforming the original problem into a series of deterministic optimization problems based on the Lyapunov optimization theory. To reduce the time complexity of our algorithm, the optimization problem is relaxed and decomposed into several independent subproblems. After solving each subproblem, we adjust the computed values of variables to obtain a feasible solution. Extensive simulations are conducted to validate the performance of the proposed algorithm.

Detecting quantitative trait loci (QTL) and estimating QTL variances (represented by the squared QTL effects) are two main goals of QTL mapping and genome-wide association studies (GWAS). However, there are issues associated with estimated QTL variances and such issues have not attracted much attention from the QTL mapping community. Estimated QTL variances are usually biased upwards due to estimation being associated with significance tests. The phenomenon is called the Beavis effect. However, estimated variances of QTL without significance tests can also be biased upwards, which cannot be explained by the Beavis effect; rather, this bias is due to the fact that QTL variances are often estimated as the squares of the estimated QTL effects. The parameters are the QTL effects and the estimated QTL variances are obtained by squaring the estimated QTL effects. This square transformation failed to incorporate the errors of estimated QTL effects into the transformation. The consequence is biases in estimated QTL variances. To correct the biases, we can either reformulate the QTL model by treating the QTL effect as random and directly estimate the QTL variance (as a variance component) or adjust the bias by taking into account the error of the estimated QTL effect. A moment method of estimation has been proposed to correct the bias. The method has been validated via Monte Carlo simulation studies. The method has been applied to QTL mapping for the 10-week-body-weight trait from an F2 mouse population.

With an ambitious increase in the number of Internet of Things (IoT) terminals, IoT networks face a huge challenge which is providing diverse and complex network services with different requirements on a common infrastructure. To solve this challenge, Software Defined Network (SDN) and Network Function Virtualization (NFV) are adopted to build next-generation IoT networks which are softwarized and virtualized. This way, network functions are virtualized as Virtualized Network Functions (VNFs) and a network service consists of a set of VNFs. One of the main challenges for realizing this paradigm is the optimal resource allocation for VNFs. Most existing works assumed that services are represented as Service Function Chains (SFCs) which are chains. However, network services in IoT networks are more complex and diverse, therefore, more appropriate representations are Virtualized Network Function Forwarding Graphs (VNF-FGs) which are Directed Acyclic Graphs (DAGs). Previous works failed to exploit this special graph structure, which makes them sub-optimal or non-applicable for IoT networks. In this paper, we investigate the VNF-FG placing problem in dynamic IoT networks where DAG-represented services arrive and depart. To fully exploit the graph structures of services and handle the complexity of dynamic IoT networks, we combine a novel neural network structure Graph Neural Network (GNN) with Deep Reinforcement Learning (DRL) and propose an efficient algorithm for VNF-FG placing, which is called Kolin. Extensive simulation results suggest that Kolin outperforms the state-of-the-art solutions in terms of system cost, acceptance ratio, and computation complexity.

Fine-grained and accurate network flow measurements are essential for various network management tasks. In recent years, the evolution of programmable networks enables flow measurement on the switch. However, limited hardware resources on programmable switches drive the shift of measurement from a single switch to network-wide coordinations. This paper aims to optimize the allocation strategy of flow measurement among switches under the objective of measurement coverage and accuracy in network-wide measurement scenarios. We design a Graph Neural Network model, NeuralMon, that can model and solve the above problem precisely. NeuralMon converts network topologies and network flows into a hypergraph and transforms the flow measurement task allocation problem into a node classification problem. NeuralMon is effective in learning the task allocation solution from the network topologies and flows directly. Even on untrained real-world network topologies, NeuralMon still provides excellent performance.

In recent years, with the rapid proliferation of smart devices, Mobile Edge Computing (MEC) has been regarded as a promising technique that provides computing services in proximity to end-users. To improve the performance of MEC systems, Collaborative Edge Computing (CEC) is proposed to balance the load among cooperative edge servers. In practice, however, edge servers belong to different MEC service providers (SPs) and they have no incentive to help others. To encourage the cooperation between self-interested SPs, in this paper, we propose a profit-sharing incentive mechanism based on the Shapley value. In addition to the desirable properties such as efficiency and fairness, we also proved that our mechanism induces optimal offloading strategies and provides every SP an incentive to join the coalition. To protect the private information of SPs, we defined an aggregate profit function for each SP and showed that revealing this function is sufficient to calculate the profit allocation. Simulation results demonstrate that the system performance and SPs' revenue are substantially improved under cooperation.

As one of the key concepts in the 5G network, MEC can support the latency-sensitive and compute-intensive services by widely deploying computing and storage capacity to the base stations at the network edge. Because these services are sensitive to latency, the joint optimization problem of task offloading and resource allocation needs to be solved in a short time. In this paper, we propose a Fast AI-assistant Solution for Task Offloading and Resource Allocation in MEC (FAST-RAM), which can directly solve the joint optimization problem leveraging a deep neural network. FAST-RAM can produce the offloading policy and resource allocation scheme in milliseconds. Meantime, our solution has near-optimal performance and sufficient feasibility under different network environments.

MOTIVATION: Genome-wide association studies (GWAS) are still the primary steps toward gene discovery. The urgency is more obvious in the big data era when GWAS are conducted simultaneously for thousand traits, e.g. transcriptomic and metabolomic traits. Efficient mixed model association (EMMA) and genome-wide efficient mixed model association (GEMMA) are the widely used methods for GWAS. An algorithm with high computational efficiency is badly needed. It is interesting to note that the test statistics of the ordinary ridge regression (ORR) have the same patterns across the genome as those obtained from the EMMA method. However, ORR has never been used for GWAS due to its severe shrinkage on the estimated effects and the test statistics. RESULTS: We introduce a degree of freedom for each marker effect obtained from ORR and use it to deshrink both the estimated effect and the standard error so that the Wald test of ORR is brought back to the same level as that of EMMA. The new method is called deshrinking ridge regression (DRR). By evaluating the methods under three different model sizes (small, medium and large), we demonstrate that DRR is more generalized for all model sizes than EMMA, which only works for medium and large models. Furthermore, DRR detect all markers in a simultaneous manner instead of scanning one marker at a time. As a result, the computational time complexity of DRR is much simpler than EMMA and about m (number of genetic variants) times simpler than that of GEMMA when the sample size is way smaller than the number of markers. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: We have developed a rapid mixed model algorithm for exhaustive genome-wide epistatic association analysis by controlling multiple polygenic effects. Our model can simultaneously handle additive by additive epistasis, dominance by dominance epistasis and additive by dominance epistasis, and account for intrasubject fluctuations due to individuals with repeated records. Furthermore, we suggest a simple but efficient approximate algorithm, which allows the examination of all pairwise interactions in a remarkably fast manner of linear with population size. Simulation studies are performed to investigate the properties of REMMAX. Application to publicly available yeast and human data has showed that our mixed model-based method has similar performance with simple linear model on computational efficiency. It took less than 40 h for the pairwise analysis of 5000 individuals genotyped with roughly 350 000 SNPs with five threads on Intel Xeon E5 2.6 GHz CPU. AVAILABILITY AND IMPLEMENTATION: Source codes are freely available at https://github.com/chaoning/GMAT. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Software-Defined Networking (SDN) provides programmable, flexible and fine-grained traffic control capability, which paves the way for realizing dynamic and high-performance traffic measurement and traffic engineering. In the SDN paradigm, the traffic forwarding and measurement strategies are realized through flow tables stored in the Tenantry Content Addressable Memories (TCAM) of SDN switches. However, the number of TCAM entries in SDN switches is limited. In this paper, we aim to jointly optimize the Traffic Matrix Measurement (TMM) and Traffic Engineering (TE) process under the TCAM capacity and flow aggregation constraints in software-defined networks. We first formulate the joint optimization problem as a Mixed Integer Linear Programming (MILP) model. Then to get an initial traffic matrix for the joint optimization problem, we propose a simple flow rule generation strategy named Maximum Load Rule First (MLRF) to efficiently generate feasible flow rules, which are used to provide direct measurements for the traffic matrix measurement problem. At last, to solve the joint optimization efficiently, we propose two efficient heuristic algorithms named Traffic Matrix Measurement First (TMMF) and Traffic Engineering First (TEF), respectively. TMMF and TEF can generate feasible flow rules for realizing TMM and TE strategies. Our evaluations on real network topologies and traffic traces verify that by jointly optimizing the TMM and TE strategies, both TMMF and TEF can significantly improve TMM accuracy and TE objective (i.e., load balancing) with limited TCAM resource.

Video streaming service has been consuming a massive amount of Internet traffic during recent years. Even though Dynamic Adaptive Streaming over HTTP (DASH) has become the mainstream technology for improving users' Quality of Experience (QoE), the competing of multiple independent DASH streams could degrade the QoE and make unfair resource allocation. With the support of Software Defined Networking (SDN), it is possible to jointly optimizing resource allocation and bitrate adaptation in this competing scenario. In this paper, we propose FAIR-AREA, a fast Artificial Intelligence based joint optimization of rate adaptation and resource allocation of DASH service. With FAIR-AREA, we can solve this complex optimization problem only in milliseconds and achieve near optimal performance at the same time.

Mobile edge computing (MEC) is an emerging paradigm which has drawn much attention from the academy and industry. Leveraging 5G technique, MEC provisions the ability to support the latency-sensitive and compute-intensive services by deploying computing and storage capacity at the network edge. As one of the critical problems in MEC, resource allocation problem needs to be solved within a very short time to satisfy the low latency requirement of services. In this paper, we propose an Accelerator for Resource allocation in MEC (ARM), which can directly solve the resource allocation problem based on deep neural network. With the aid of our scale-free representation scheme and feasible guarantee algorithm, ARM can solve the problem in milliseconds. Meanwhile, our algorithm achieves near 2-factor approximation to the optimal solution.

Due to the hard constraint of measurement resources in switches, accurately and timely measuring a huge number of fine-grained flows is very challenging. To handle this challenge, we design FlowMap, which is a Bloom filter and hash-based approach to keep track of fine-grained flows with small bandwidth as well as computation and memory overheads. In each switch, FlowMap stores flow IDentifiers (IDs) in the FlowID table and encodes flow counters in the counting table with small memory space and constant operation time. To get the per-flow counters, FlowMap leverages the computing power of the remote controller to decode the encoded flow statistics collected from switches periodically. In addition, to achieve scalable flow counter decoding, FlowMap divides the cells of the counting table into several groups, and then uses a two-level flow mapping scheme to map flows to different groups, each of which can be decoded independently and concurrently at the remote controller. The simulation results show that FlowMap can provide per-flow counters with high accuracy for all the flows in short time scales with low overheads, and comparing with the existing approach, FlowMap is more scalable and robust.

SUMMARY: We present GWASpro, a high-performance web server for the analyses of large-scale genome-wide association studies (GWAS). GWASpro was developed to provide data analyses for large-scale molecular genetic data, coupled with complex replicated experimental designs such as found in plant science investigations and to overcome the steep learning curves of existing GWAS software tools. GWASpro supports building complex design matrices, by which complex experimental designs that may include replications, treatments, locations and times, can be accounted for in the linear mixed model. GWASpro is optimized to handle GWAS data that may consist of up to 10 million markers and 10 000 samples from replicable lines or hybrids. GWASpro provides an interface that significantly reduces the learning curve for new GWAS investigators. AVAILABILITY AND IMPLEMENTATION: GWASpro is freely available at https://bioinfo.noble.org/GWASPRO. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Current dynamic phenotyping system introduces time as an extra dimension to genome-wide association studies (GWAS), which helps to explore the mechanism of dynamical genetic control for complex longitudinal traits. However, existing methods for longitudinal GWAS either ignore the covariance among observations of different time points or encounter computational efficiency issues. RESULTS: We herein developed efficient genome-wide multivariate association algorithms for longitudinal data. In contrast to existing univariate linear mixed model analyses, the proposed method has improved statistic power for association detection and computational speed. In addition, the new method can analyze unbalanced longitudinal data with thousands of individuals and more than ten thousand records within a few hours. The corresponding time for balanced longitudinal data is just a few minutes. AVAILABILITY AND IMPLEMENTATION: A software package to implement the efficient algorithm named GMA (https://github.com/chaoning/GMA) is available freely for interested users in relevant fields. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Genomic scanning approaches that detect one locus at a time are subject to many problems in genome-wide association studies and quantitative trait locus mapping. The problems include large matrix inversion, over-conservativeness for tests after Bonferroni correction and difficulty in evaluation of the total genetic contribution to a trait's variance. Targeting these problems, we take a further step and investigate a multiple locus model that detects all markers simultaneously in a single model. RESULTS: We developed a sparse Bayesian learning (SBL) method for quantitative trait locus mapping and genome-wide association studies. This new method adopts a coordinate descent algorithm to estimate parameters (marker effects) by updating one parameter at a time conditional on current values of all other parameters. It uses an L2 type of penalty that allows the method to handle extremely large sample sizes (>100 000). Simulation studies show that SBL often has higher statistical powers and the simulated true loci are often detected with extremely small P-values, indicating that SBL is insensitive to stringent thresholds in significance testing. AVAILABILITY AND IMPLEMENTATION: An R package (sbl) is available on the comprehensive R archive network (CRAN) and https://github.com/MeiyueComputBio/sbl/tree/master/R%20packge. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Almost all of the state-of-the-art object detectors employ convolutional neural network (CNN) to extract feature. However, how to fully utilize spatial information is a challenge. In this paper, we propose an effective framework for object detection. Our motivation is that multi-scale representation and context are extremely important for object detection. For multi-scale representation, our mothed combines hierarchical feature maps to a fusion map, which has abundant spatial information and high-level semantics. For context, we exploit spatial information by stacking multi-region feature maps. The network is learned end-to-end, by minimize an objective function. Our network achieves competitive results, 75.9% mAP on PASCAL VOC 2007, 72.0% mAP on PASCAL VOC 2012 and 23.2% mAP on MS COCO. The speed of the network is 10 fps. Our studies demonstrate that multiscale representation and context can further improve performance of object detection.

Motivation: Joint reconstruction of multiple gene regulatory networks (GRNs) using gene expression data from multiple tissues/conditions is very important for understanding common and tissue/condition-specific regulation. However, there are currently no computational models and methods available for directly constructing such multiple GRNs that not only share some common hub genes but also possess tissue/condition-specific regulatory edges. Results: In this paper, we proposed a new graphic Gaussian model for joint reconstruction of multiple gene regulatory networks (JRmGRN), which highlighted hub genes, using gene expression data from several tissues/conditions. Under the framework of Gaussian graphical model, JRmGRN method constructs the GRNs through maximizing a penalized log likelihood function. We formulated it as a convex optimization problem, and then solved it with an alternating direction method of multipliers (ADMM) algorithm. The performance of JRmGRN was first evaluated with synthetic data and the results showed that JRmGRN outperformed several other methods for reconstruction of GRNs. We also applied our method to real Arabidopsis thaliana RNA-seq data from two light regime conditions in comparison with other methods, and both common hub genes and some conditions-specific hub genes were identified with higher accuracy and precision. Availability and implementation: JRmGRN is available as a R program from: https://github.com/wenpingd. Supplementary information: Supplementary data are available at Bioinformatics online.

Motivation: Epistasis provides a feasible way for probing potential genetic mechanism of complex traits. However, time-consuming computation challenges successful detection of interaction in practice, especially when linear mixed model (LMM) is used to control type I error in the presence of population structure and cryptic relatedness. Results: A rapid epistatic mixed-model association analysis (REMMA) method was developed to overcome computational limitation. This method first estimates individuals' epistatic effects by an extended genomic best linear unbiased prediction (EG-BLUP) model with additive and epistatic kinship matrix, then pairwise interaction effects are obtained by linear retransformations of individuals' epistatic effects. Simulation studies showed that REMMA could control type I error and increase statistical power in detecting epistatic QTNs in comparison with existing LMM-based FaST-LMM. We applied REMMA to two real datasets, a mouse dataset and the Wellcome Trust Case Control Consortium (WTCCC) data. Application to the mouse data further confirmed the performance of REMMA in controlling type I error. For the WTCCC data, we found most epistatic QTNs for type 1 diabetes (T1D) located in a major histocompatibility complex (MHC) region, from which a large interacting network with 12 hub genes (interacting with ten or more genes) was established. Availability and implementation: Our REMMA method can be freely accessed at https://github.com/chaoning/REMMA. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

BACKGROUND: Genome-wide assisted selection is a critical tool for the genetic improvement of plants and animals. Whole-genome regression models in Bayesian framework represent the main family of prediction methods. Fitting such models with a large number of observations involves a prohibitive computational burden. We propose the use of subsampling bootstrap Markov chain in genomic prediction. Such method consists of fitting whole-genome regression models by subsampling observations in each round of a Markov Chain Monte Carlo. We evaluated the effect of subsampling bootstrap on prediction and computational parameters. RESULTS: Across datasets, we observed an optimal subsampling proportion of observations around 50% with replacement, and around 33% without replacement. Subsampling provided a substantial decrease in computation time, reducing the time to fit the model by half. On average, losses on predictive properties imposed by subsampling were negligible, usually below 1%. For each dataset, an optimal subsampling point that improves prediction properties was observed, but the improvements were also negligible. CONCLUSION: Combining subsampling with Gibbs sampling is an interesting ensemble algorithm. The investigation indicates that the subsampling bootstrap Markov chain algorithm substantially reduces computational burden associated with model fitting, and it may slightly enhance prediction properties.

Following publication of this article [1], it has come to our attention that some of the equations included were distorted by a formatting issue in the PDF form.This issue affected Eqs. 8, 9 and 11.The correct forms of the equations are shown below.

In-network content caching is an inherent capability of Content Centric Networking (CCN) architecture. Undoubtedly, efficient caching strategies can help CCN networks to achieve high performance content dissemination. In general, there are two types of caching strategies: collaborative and non-collaborative caching strategies. Compared with non-collaborative caching strategies, collaborative caching strategies have much better caching performance. However, collaborative caching strategies incur extra overhead (e.g., computation and communication). To make a trade-off between the performance and overhead, we propose a distributed lightweight collaborative in-network caching strategy in this paper, called Popularity Publishing based caching strategy (PopPub for short). PopPub uses a lightweight protocol to publish the content popularity statistics counted by edge routers to other routers, and caches different contents at different routers along the content delivery paths based on the popularities of the contents. To evaluate the performance of PopPub, we conduct both theoretical analysis and extensive simulations on different topologies. The evaluation results confirm that PopPub yields the best performance compared with several state-of-art caching strategies, and the extra overhead incurred by PopPub is low.

As Network Function Virtualization (NFV) becomes reality and cloud computing offers a scalable pay-as-you-go charging model, more network operators would like to outsource their Service Function Chains (SFC) to the public clouds in order to reduce the operational cost. However, how to minimize the operational cost with Quality of Service (QoS) guarantee when outsourcing SFC is still an open problem. In this paper, we are to study this problem when there are large number of candidate cloud providers with diverse pricing schemes of network functions. In addition, extra delay is introduced as the result of outsourcing SFCs. Firstly, we formulate this problem as an Integer Linear Programming (ILP) model. Then we design an efficient heuristic algorithm named QoS-Guaranteed SFC Outsourcing algorithm (QGSO) based on Hidden Markov Model (HMM). The extensive simulations show that QGSO saves up to 75.8% cost compared with that of deploying network functions in local network. QGSO also achieves up to 42.6% cost savings compared with the result of first-fit based optimization algorithm.

Content-Centric Networking (CCN) is a novel networking paradigm that treats the named contents, not the hosts, as the first-class citizens of the network. In the forwarding plane, CCN employs a stateful forwarding scheme, which maintains per-packet state information in Pending Interest Table (PIT). By employing stateful forwarding, CCN enables native support for content requests aggregation and multicast. However, the stateful forwarding scheme requires large-sized PITs with extremely high access speed to store per-packet state information, leading to scalability issue. To overcome the issue, this paper proposes a Hybrid forwarding scheme based on content POPularity (HyPOP) for CCN. HyPOP classifies the contents into popular and unpopular contents, and uses the stateful and Bloom Filter based stateless forwarding schemes to forward the popular and unpopular contents, respectively. The mathematical analysis results demonstrate that if PITs only store state information for popular contents, the small-sized PITs are sufficient for achieving satisfactory forwarding performance. Furthermore, the extensive simulation results also verify that HyPOP can reduce the size of PIT significantly and achieve promising forwarding performance.

The term epistasis refers to interactions between multiple genetic loci. Genetic epistasis is important in regulating biological function and is considered to explain part of the 'missing heritability,' which involves marginal genetic effects that cannot be accounted for in genome-wide association studies. Thus, the study of epistasis is of great interest to geneticists. However, estimating epistatic effects for quantitative traits is challenging due to the large number of interaction effects that must be estimated, thus significantly increasing computing demands. Here, we present a new web server-based tool, the Pipeline for estimating EPIStatic genetic effects (PEPIS), for analyzing polygenic epistatic effects. The PEPIS software package is based on a new linear mixed model that has been used to predict the performance of hybrid rice. The PEPIS includes two main sub-pipelines: the first for kinship matrix calculation, and the second for polygenic component analyses and genome scanning for main and epistatic effects. To accommodate the demand for high-performance computation, the PEPIS utilizes C/C++ for mathematical matrix computing. In addition, the modules for kinship matrix calculations and main and epistatic-effect genome scanning employ parallel computing technology that effectively utilizes multiple computer nodes across our networked cluster, thus significantly improving the computational speed. For example, when analyzing the same immortalized F2 rice population genotypic data examined in a previous study, the PEPIS returned identical results at each analysis step with the original prototype R code, but the computational time was reduced from more than one month to about five minutes. These advances will help overcome the bottleneck frequently encountered in genome wide epistatic genetic effect analysis and enable accommodation of the high computational demand. The PEPIS is publically available at http://bioinfo.noble.org/PolyGenic_QTL/.

We revisit the problem of identifying link metrics from end- to-end path measurements in practical IP networks where shortest path routing is the norm. Previous solutions rely on explicit routing techniques (e.g., source routing or MPLS) to construct independent measurement paths for efficient link metric identification. However, most IP networks still adopt shortest path routing paradigm, while the explicit routing is not supported by most of the routers. Thus, this paper studies the link metric identification problem under shortest path routing constraints. To uniquely identify the link metrics, we need to place sufficient number of monitors into the network such that there exist $m$ (the number of links) linear independent shortest paths between the monitors. In this paper, we first formulate the problem as a mixed integer linear programming problem, and then to make the problem tractable in large networks, we propose a Monitor Placement and Measurement Path Selection (MP-MPS) algorithm that adheres to shortest path routing constraints. Extensive simulations on random and real networks show that the MP- MPS gets near-optimal solutions in small networks, and MP- MPS significantly outperforms a baseline solution in large networks.

In Software Defined Networks (SDN), applications on the controller could enforce fine-grained control on flows by policies employing more packet fields. These policies are converted to flow entries and stored in switch Flow Table. To store these entries, Flow Table requires large storage space because an entry consisted of more packet fields needs more storage space and the number of entries also increases significantly due to fine-granularity definition of flows. However, Flow Table has limited storage space owing to the constraints of Ternary Content Addressable Memory (TCAM). As a result, the switch Flow Table in SDN faces scalability issue. We address this issue by means of adaptive Flow Table management, namely we manage how long the entries occupy the storage space by setting adaptive timeouts to them. Through this means, the storage space could be reused efficiently and more flows could be supported with the same Flow Table (without updating hardware devices). Our proposed method TimeoutX, for the first time, combines traffic characteristics, flow types and Flow Table utilization ratio to decide the timeout of each entry and it outperforms current timeout setting strategies in both metrics of table miss number and blocked packet number, which indicates TimeoutX could make the best of Flow Table and support more flows.

MOTIVATION: Mixed linear models provide important techniques for performing genome-wide association studies. However, current models have pitfalls associated with their strong assumptions. Here, we propose a new implementation designed to overcome some of these pitfalls using an empirical Bayes algorithm. RESULTS: Here we introduce NAM, an R package that allows user to take into account prior information regarding population stratification to relax the linkage phase assumption of current methods. It allows markers to be treated as a random effect to increase the resolution, and uses a sliding-window strategy to increase power and avoid double fitting markers into the model. AVAILABILITY AND IMPLEMENTATION: NAM is an R package available in the CRAN repository. It can be installed in R by typing install.packages ('NAM'). CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary date are available at Bioinformatics online.

In this paper, we study the multiobjective optimization problem for green network routing. Although traditional commonly used multiobjective optimization methods can yield a Pareto efficient solution, they need to construct an aggregate objective function (AOF) or model one objective as a constraint in the optimization problem formulation. As a result, it is difficult to achieve a fair tradeoff among all objectives. Accordingly, we induce a Nash bargaining framework, which treats the two objectives as two virtual players in a game theoretic model, who negotiate how traffic should be routed to optimize both objectives. During the negotiation, each of them announces its performance threat value to reduce its cost, so the model is regarded as a threat value game. Our analysis shows that no agreement can be achieved if each player sets its threat value selfishly. To avoid such a negotiation break-down, we modify the threat value game to have a repeated process and design a mechanism to not only guarantee an agreement, but also generate a fair solution. Finally, to evaluate the efficiency of our proposed framework, we implement it into two multiobjective optimization cases for network green routing. The first case is load balancing and energy efficiency optimization for intradomain routing, and the second one is the energy efficiency optimization of two domains for interdomain routing.

In Software Defined Networks (SDN), more packet fields are included to design fine-grained policies. These policies are stored as entries in switch Flow Table. However, fine-grained policies cause the scalability issue as a single flow entry needs larger storage space and a significant number of flow entries need to be stored, but the Flow Table is limited due to the constraints of Ternary Content Addressable Memory (TCAM). To address this issue, we propose Adaptive Hard Timeout Method (AHTM) to improve the Flow Table utilization by optimizing the timeouts of flow entries, thus the Flow Table is reused efficiently. AHTM models the Flow Table as a queueing system and derives closed-form formulas for analysis and optimization. We also implement AHTM as a light-weighted SDN application and it offers interfaces to other applications. The simulation results show that AHTM can achieve the balance between blocking probability and extra workload to SDN controller.

In this paper, we study how to manage the topology reconfiguration in OSA-based datacenter networks (DCNs). Though an OSA-based DCN can change its topology to adapt to the traffic matrix and improve the network scalability, it requires too much time (10ms) to reconfigure the topology, which may not only incur a great amount of traffic loss in high throughput low latency DCNs, but also bring much performance degradation to the delay sensitive flows. Therefore, a progressive topology reconfiguration scheme is required to reduce the traffic loss and guarantee the performance of delay sensitive flows. To this end, we first formulate the problem as a mathematical model, and then analyze its feasibility and complexity. Based on these analyses, topology management algorithm (TMA) is proposed to calculate the topology reconfiguration scheme that can maintain the topology connectivity during reconfiguration. By simulation, we find that TMA can reduce the traffic loss during topology reconfiguration by up to 50% in most of the cases and reconfigure topology without traffic loss in some cases.

We focus on the dynamic Routing and Spectrum Allocation (RSA) problem in EONs with mixed line rates. To solve the dynamic RSA problem efficiently, we decompose the problem into routing and spectrum allocation sub-problems. For the routing sub-problem, we propose an efficient multi-constrained routing algorithm, Sorted Feasible Paths Searching (SFPS), to find the shortest feasible paths for the dynamic traffic demands. For the spectrum allocation sub-problem, we propose a spectrum allocation strategy named Adaptive Segmentation (AS) to allocate spectrum for the non-commensurate traffic demands of EONs with mixed line rates. Simulation results prove that the proposed dynamic RSA algorithm is time-efficient and perform better than existing dynamic RSA algorithms in terms of bandwidth blocking probability and spectrum fragmentation ratio.

In-network caching as one of the primary components for ICN (information-centric network) has attracted more and more attentions. In this paper, we present a profit-based caching for ICN. The profit value for the content arriving on a router is determined by request popularity, distance to content source, content size and content duration, etc. The content duration is considered as an important factor in methodology to avoid the error caused by storing the overdue contents, which is the main difference from existing caching scheme. A 0-1 ILP (integer linear programming) is used to formulate whether to cache the coming content or not and eviction objects simultaneously. Also, a near-optimal heuristic algorithm is proposed to find profit-efficient cache decision, which can be quickly deployed. The analytical and simulation results show our profit-based caching scheme can attain a better network profit compare to Least Frequently used (LFU), and totally avoids caching withdrawing contents.

Data center networks (DCNs) generally adopt Clos network with crossbar middle switches to achieve non-blocking data switching among the servers, and the number of middle switches is proportional to the number of ports of the aggregation switches in a fixed manner. Besides, reconfiguration overhead of the switches is generally ignored, which may contradict the engineering practice. In this paper, we consider batch scheduling based packet switching in DCNs with reconfiguration overhead at each middle switch, which inevitably leads to packet delay. With existing state-of-the-art traffic matrix decomposition algorithms, we can generate a set of permutations, each of which stands for the configuration of a middle switch. By reconfiguring each middle switch to fulfill multiple configurations in parallel with others, we reveal that a tradeoff exists between packet delay and switch cost (denoted by the number of middle switches), while performance guaranteed switching with bounded packet delay can be achieved without any packet loss. Based on the tradeoff, we can minimize the number of middle switches (under a given packet delay bound) and an overall cost metric (by translating delay into a comparable cost factor), as well as formulating criterions for choosing a matrix decomposition algorithm. This provides a flexible way to reduce the number of middle switches by slightly enlarging the packet delay bound.

In this paper, we study the tradeoff between two important traffic engineering objectives: load balance and energy efficiency. Although traditional commonly used multi-objective optimization methods can yield a Pareto efficient solution, they need to construct an aggregate objective function (AOF) or model one of the two objectives as a constraint in the optimization problem formulation. As a result, it is difficult to achieve a fair tradeoff between these two objectives. Accordingly, we induce a Nash bargaining framework which treats the two objectives as two virtual players in a game theoretic model, who negotiate how traffic should be routed in order to optimize both objectives. During the negotiation, each of them announces its performance threat value to reduce its cost, so the model is regarded as a threat value game. Our analysis shows that no agreement can be achieved if each player sets its threat value selfishly. To avoid such a negotiation break-down, we modify the threat value game to have a repeated process and design a mechanism to not only guarantee an agreement, but also generate a fair solution. In addition, the insights from this work are also useful for achieving a fair tradeoff in other multi-objective optimization problems.

The concept of monitoring trail (m-trail) provides a striking mechanism for fast and unambiguous link failure localization in all-optical networks. To achieve fast m-trail design in large-size networks, two efficient heuristics RCA+RCS and MTA are proposed against the optimal ILP (Integer Linear Program) model. However, RCA+RCS suffers from the disjoint trail problem which increases the required number of m-trails, and MTA always finds a deterministic solution which may not be good enough due to the limited solution space. In this paper, we propose a new heuristic RNH-MTA (Monitoring Trail Allocation with the Random Next Hop policy) to solve those issues. Similar to MTA, RNH-MTA ensures a valid optical structure of each m-trail and sequentially adds necessary m-trails to the solution, and thus is free of the disjoint trail problem. By replacing the deterministic searching in MTA using the Random Next Hop policy, RNH-MTA sets up a probabilistic model in extending each m-trail. This not only enlarges the solution space and increases the solution diversity, but also enables a controllable tradeoff between the solution quality and the running time of the algorithm. Our numerical results show the advantages of RNH-MTA over both RCA+RCS and MTA.

LISP (Locator/Identifier Separation Protocol) is proposed to address the routing scalability problem of current Internet, and a mapping system is required to support the LISP EID-to-RLOC (Endpoint Identifier to Routing Locator) mapping services. In this paper we suggest ERMA (EID-to-RLOC Mapping Assignment) of local network could be tuned to specify the ingress points of inbound traffic, which is helpful for improving the network resource utilization in stub domains. One Mixed Integer Linear Programming model is proposed for ERMA-only optimization in the network with given link weights; another model is formulated for the joint optimization of ERMA and link weights. To make the joint optimization problem tractable, one local search algorithm, Optimized Stepsize Algorithm, is proposed. Our numerical results show that the maximum link utilization decreased by tuning ERMA in both cases.

MOTIVATION: Most biological traits may be correlated with the underlying gene expression patterns that are partially determined by DNA sequence variation. The correlations between gene expressions and quantitative traits are essential for understanding the functions of genes and dissecting gene regulatory networks. RESULTS: In the present study, we adopted a novel statistical method, called the stochastic expectation and maximization (SEM) algorithm, to analyze the associations between gene expression levels and quantitative trait values and identify genetic loci controlling the gene expression variations. In the first step, gene expression levels measured from microarray experiments were assigned to two different clusters based on the strengths of their association with the phenotypes of a quantitative trait under investigation. In the second step, genes associated with the trait were mapped to genetic loci of the genome. Because gene expressions are quantitative, the genetic loci controlling the expression traits are called expression quantitative trait loci. We applied the same SEM algorithm to a real dataset collected from a barley genetic experiment with both quantitative traits and gene expression traits. For the first time, we identified genes associated with eight agronomy traits of barley. These genes were then mapped to seven chromosomes of the barley genome. The SEM algorithm and the result of the barley data analysis are useful to scientists in the areas of bioinformatics and plant breeding. AVAILABILITY AND IMPLEMENTATION: The R program for the SEM algorithm can be downloaded from our website: http://www.statgen.ucr.edu.

BACKGROUND: The Bayesian shrinkage technique has been applied to multiple quantitative trait loci (QTLs) mapping to estimate the genetic effects of QTLs on quantitative traits from a very large set of possible effects including the main and epistatic effects of QTLs. Although the recently developed empirical Bayes (EB) method significantly reduced computation comparing with the fully Bayesian approach, its speed and accuracy are limited by the fact that numerical optimization is required to estimate the variance components in the QTL model. RESULTS: We developed a fast empirical Bayesian LASSO (EBLASSO) method for multiple QTL mapping. The fact that the EBLASSO can estimate the variance components in a closed form along with other algorithmic techniques render the EBLASSO method more efficient and accurate. Comparing with the EB method, our simulation study demonstrated that the EBLASSO method could substantially improve the computational speed and detect more QTL effects without increasing the false positive rate. Particularly, the EBLASSO algorithm running on a personal computer could easily handle a linear QTL model with more than 100,000 variables in our simulation study. Real data analysis also demonstrated that the EBLASSO method detected more reasonable effects than the EB method. Comparing with the LASSO, our simulation showed that the current version of the EBLASSO implemented in Matlab had similar speed as the LASSO implemented in Fortran, and that the EBLASSO detected the same number of true effects as the LASSO but a much smaller number of false positive effects. CONCLUSIONS: The EBLASSO method can handle a large number of effects possibly including both the main and epistatic QTL effects, environmental effects and the effects of gene-environment interactions. It will be a very useful tool for multiple QTL mapping.

We study the m-trail (monitoring trail) allocation problem in all-optical WDM mesh networks for achieving fast and unambiguous link failure localization. The existing ILP is not feasible for solving the problem in large-size networks. A heuristic RCA+RCS can find feasible solutions in a shorter running time, but it is a randomized algorithm. More importantly, RCA+RCS suffers from the disjoint trail problem which dramatically increases the number of required monitors in large-size networks. In this paper, we propose a new heuristic MTA (Monitoring Trail Allocation) to solve the problem. MTA avoids those issues in RCA+RCS, and achieves an efficient tradeoff between monitor cost and bandwidth cost. Compared with RCA+RCS, MTA greatly shortens the running time and achieves a much higher solution quality. We also show that MTA provides a flexible framework to enable multiple possible variations for future study.

The concept of p-cycle (Preconfigured Protection Cycle) allows fast and efficient span protection in WDM mesh networks. To construct p-cycles, conventional algorithms need to enumerate all the candidate cycles in the network before ILP (Integer Linear Program) can be applied to find the optimal solution. To reduce the size of the candidate set and thus speed up the optimization process, heuristic algorithms are proposed for candidate cycle pre-selection at the cost of lower solution quality. Recently, some interesting ILP formulations were proposed to construct p-cycles without candidate cycle enumeration/preselection. But they tend to require a long running time. Following the approach of no candidate cycle enumeration, we formulate a new ILP based on flow conservation in this paper. Numerical results show that our new ILP runs much faster than the existing ones.

The notion of p-cycle (preconfigured protection cycle) allows capacity efficient schemes to be designed for fast span protection in WDM mesh networks. Conventional p-cycle construction algorithms need to enumerate/pre-select candidate cycles before ILP (integer linear program) can be applied. In this paper, we propose a new algorithm which is only based on ILP. When the required number of p-cycles is not too large, our ILP can generate optimal/suboptimal solutions in reasonable amount of running time.

In this paper, we focus on the problem with the objective to maximize the system performance, while guaranteeing multiple QoS (quality of service) constraints for wireless data networks accommodating multiclass services with different quality requirements. First, we formulate and solve the opportunistic scheduling problem with multiple general long-term QoS constraints. Then, we generalize this problem to include short-term QoS constraints for real-time multimedia users and long-term QoS constraints for non-real-time data users simultaneously in multiclass services networks. Simulation results illustrate that the proposed scheduling schemes guarantee the different QoS constraints, and achieve high system performance.

In this paper, we address the problem of resource allocation with efficiency and quality of service (QoS) support in uplink for a wireless CDMA network supporting real-time (RT) and nonreal-time (NRT) communication services. For RT and NRT users, there are different QoS requirements. We introduce and describe a new scheme, namely the traffic aided uplink opportunistic scheduling (TAUOS). While guaranteeing the different QoS requirements, TAUOS exploits the channel condition to improve the system throughput. In TAUOS, the cross-layer information, file size information, is used to improve the fairness of NRT users. Extensive simulation results show that our scheme can achieve high system throughput in uplink wireless CDMA system, while guaranteeing the QoS requirements.

In this paper we present a novel efficient energy-aware approach for clustering nodes in wireless sensor networks. We use different cluster head (CH) declaration delays for each node to characterize the qualification to be a CH. The approach guarantees the fairly uniform cluster distribution while incurring low overheads. Additionally, we do not make any assumptions about the distribution or node capabilities, e.g., location-awareness. The simulation results show that our clustering approach outperforms LEACH both in cluster characteristics and in the efficiency of prolonging the network lifetime.

MOTIVATION: Grouping genes having similar expression patterns is called gene clustering, which has been proved to be a useful tool for extracting underlying biological information of gene expression data. Many clustering procedures have shown success in microarray gene clustering; most of them belong to the family of heuristic clustering algorithms. Model-based algorithms are alternative clustering algorithms, which are based on the assumption that the whole set of microarray data is a finite mixture of a certain type of distributions with different parameters. Application of the model-based algorithms to unsupervised clustering has been reported. Here, for the first time, we demonstrated the use of the model-based algorithm in supervised clustering of microarray data. RESULTS: We applied the proposed methods to real gene expression data and simulated data. We showed that the supervised model-based algorithm is superior over the unsupervised method and the support vector machines (SVM) method. AVAILABILITY: The program written in the SAS language implementing methods I-III in this report is available upon request. The software of SVMs is available in the website http://svm.sdsc.edu/cgi-bin/nph-SVMsubmit.cgi

A new class of quality of service (QoS) measures, EB(p), p/spl ges/1 for WDM optical transport networks is proposed in this paper. Compared with the traditional overall average blocking probability (OABP), EB(p) is a composite measure that is unbiased, makes reference to the QOS requirements, one-sided, and takes the potential revenue loss into consideration. In particular, EB(1) can be identified as (revenue) weighted average excessive blocking, and EB(2) as mean square (revenue) weighted excessive blocking. The effectiveness of this new composite measure is compared with OABP based on several existing routing and wavelength assignment algorithms.

This paper studies multihop optical networks in which nodes employ wavelength routing switches that enable the establishment of wavelength division multiplexed (WDM) channels, called lightpaths, between node pairs. In fact, most optical networks are multifiber networks. The problem of dynamical routing and assignment of wavelength (RAW) in such networks is studied in this paper. Two resource assignment strategies, PACK and SPREAD, are proposed. By virtue of a layered-graph, routing and assignment of wavelength subproblems can be considered simultaneously. These two strategies can be used to solve the RAW problem in networks with even links as well as that in networks with uneven links. Simulation shows that layered-graph-based RAW algorithms perform better than the existing ones. It also shows that SPREAD with distributive use of network resources can achieve better performance than PACK with collective use of resources in multifiber networks. The layered-graph-based algorithms can effectively deal with the failure of the fiber/link and node. By making use of the special structure of the layered-graph, we propose a shortest path algorithm, whose complexity is lower than that of the standard shortest path algorithm.

Two algorithms are proposed for the dynamic routing and assignment of wavelength problem in multi-fiber wavelength division multiplexing all-optical networks. By virtue of the layered graph, the routing and assignment of wavelength subproblems can be considered simultaneously. Simulation shows that layered-graph-based RAW algorithms perform better than the existing ones. Making use of the special structure of the layered graph, we propose a shortest path algorithm, whose complexity is lower than that of the standard shortest path algorithms.