Gradient-based optimization methods implemented on distributed computing architectures are increasingly used to tackle large-scale machine learning applications. A key bottleneck in such distributed systems is the high communication overhead for exchanging information, such as stochastic gradients, between workers. The inherent causes of this bottleneck are the frequent communication rounds and the full model gradient transmission in every round. In this study, we present SASG, a communication-efficient distributed algorithm that enjoys the advantages of sparse communication and adaptive aggregated stochastic gradients. By dynamically determining the workers who need to communicate through an adaptive aggregation rule and sparsifying the transmitted information, the SASG algorithm reduces both the overhead of communication rounds and the number of communication bits in the distributed system. For the theoretical analysis, we introduce an important auxiliary variable and define a new Lyapunov function to prove that the communication-efficient algorithm is convergent. The convergence result is identical to the sublinear rate of stochastic gradient descent, and our result also reveals that SASG scales well with the number of distributed workers. Finally, experiments on training deep neural networks demonstrate that the proposed algorithm can significantly reduce communication overhead compared to previous methods.

Recently, the data-parallel pipeline approach has been widely used in training DNN models on commodity GPU servers. However, there are still three challenges for hybrid parallelism on commodity GPU servers: i) a balanced model partition is crucial for efficiency, whereas prior works lack a sound solution to generate a balanced partition automatically; ii) an orchestrated device mapping is essential to reduce communication contention, however, prior works ignore server heterogeneity, exacerbating communication contention; iii) the startup overhead is inevitable and especially significant for deep pipelines, which is an essential source of pipeline bubbles and severely affects pipeline scalability. We proposeAutoPipe-Hto solve these three problems, which contains i) apipeline partitionercomponent for automatically and quickly generating a balanced sub-block partition scheme; ii) adevice mappingcomponent that assigns pipeline stages to devices, considering server heterogeneity, to reduce communication contention; and iii) adistributed training runtimecomponent that reduces pipeline startup overhead by splitting the micro-batch evenly. The experimental results show that AutoPipe-H can accelerate training by up to 1.26x over the hybrid parallelism framework DAPPLE and Piper, with a 2.73x-12.7x improvement in the partition balance and an order-of-magnitude time reduction in partition scheme searching.

Artificial Intelligence (AI) has almost become the default approach in a wide range of applications, such as computer vision, chatbots, and natural language processing. These AI-based applications require computing large-scale data with sufficient precision, typically in floating-point numbers, within a limited time window. A primary target for AI acceleration is matrix multiplication, mainly involving dot products through Multiply-Accumulate (MAC) operations. Current research employs the Fused Multiply-Add (FMA) operation, based on IEEE-754 Floating Point (FP) standard, to meet these requirements. However, current research focuses more on simplifying the internal digital circuits of the Processing Elements (PEs) performing FMA operations, rather than optimizing the FMA process specifically for MAC tasks. Current PE arrays often use a two-dimensional (2-D) systolic array design, without specific optimization for MAC operations, thus their parallelism is not fully utilized. Additionally, these designs lack reconfigurability and flexibility, leading to suboptimal performance on Field-Programmable Gate Arrays (FPGAs). Moreover, some designs adopt lower precision computing in AI inference for higher performance. However, some AI models still rely on high-precision computing to maintain the accuracy. Thus, multi-precision computing is commonly used in AI accelerators. To address these challenges, this paper proposes a novel Multi-Fused Multiply-Accumulate (MFMA) scheme and a corresponding three-dimensional (3-D) scalable systolic FP computing architecture. The MFMA scheme addresses the problem of the classical FMA scheme. It optimizes FMA for MAC operations with the Fused Multiply-Accumulate (FMAC) operation. Also, it combines multi-precision and mixed-precision FP computing methods for higher accuracy and lower overflow error. The proposed architecture integrates two 2-D systolic arrays into the PE for a 3-D systolic array, achieving higher parallelism and flexibility. The proposed scalable architecture can be customized to suit various FMAC operations. Compared with existing state-of-the-art FP architectures on FPGAs, our proposed architecture achieves 47%, 10%, and 159% energy efficiency improvements in FP32, FP16, and INT8 operations, respectively. Furthermore, our proposed architecture achieves energy efficiency improvements of 105%, 54%, and 262% under efficiency saturation conditions, outperforming the existing state-of-the-art design.

Asynchronous pipeline model parallelism with a “1F1B” (one forward, one backward) schedule generates little bubble overhead and always provides quite a high throughput. However, the “1F1B” schedule inevitably leads to weight inconsistency and weight staleness issues due to the cross-training of different mini-batches across GPUs. To simultaneously address these two problems, in this paper, we propose an optimizer-dependent weight prediction strategy (a.k.a PipeOptim) for asynchronous pipeline training. The key insight of our proposal is that we employ a weight prediction strategy in the forward pass to approximately ensure that each mini-batch uses consistent and staleness-free weights to compute the forward pass of the “1F1B” schedule. To be concrete, we first construct the weight prediction scheme based on the update rule of the used optimizer when training the deep neural network models. Then throughout the “1F1B” pipeline training, each mini-batch is mandated to execute weight prediction, subsequently employing the predicted weights to perform the forward pass. As a result, PipeOptim 1) inherits the advantage of the “1F1B” schedule and generates high throughput, and 2) can ensure effective parameter learning regardless of the type of the used optimizer. We conducted extensive experimental evaluations using nine different deep-learning models to verify the effectiveness of our proposal. The experiment results demonstrate that PipeOptim outperforms the other five popular pipeline approaches including GPipe, PipeDream, PipeDream-2BW, SpecTrain, and XPipe.

The goal of knowledge graph completion (KGC) is to predict missing facts among entities. Previous methods for KGC re-ranking are mostly built on non-generative language models to obtain the probability of each candidate. Recently, generative large language models (LLMs) have shown outstanding performance on several tasks such as information extraction and dialog systems. Leveraging them for KGC re-ranking is beneficial for leveraging the extensive pre-trained knowledge and powerful generative capabilities. However, it may encounter new problems when accomplishing the task, namely mismatch, misordering and omission. To this end, we introduce KC-GenRe, a knowledge-constrained generative re-ranking method based on LLMs for KGC. To overcome the mismatch issue, we formulate the KGC re-ranking task as a candidate identifier sorting generation problem implemented by generative LLMs. To tackle the misordering issue, we develop a knowledge-guided interactive training method that enhances the identification and ranking of candidates. To address the omission issue, we design a knowledge-augmented constrained inference method that enables contextual prompting and controlled generation, so as to obtain valid rankings. Experimental results show that KG-GenRe achieves state-of-the-art performance on four datasets, with gains of up to 6.7% and 7.7% in the MRR and Hits@1 metric compared to previous methods, and 9.0% and 11.1% compared to that without re-ranking. Extensive analysis demonstrates the effectiveness of components in KG-GenRe.

Asynchronous stochastic gradient descent (ASGD) has evolved into an indispensable optimization algorithm for training modern large-scale distributed machine learning tasks. Therefore, it is imperative to explore the generalization performance of the ASGD algorithm. However, the existing results are either pessimistic and vacuous or restricted by strict assumptions that fail to reveal the intrinsic impact of asynchronous training on generalization. In this study, we establish sharper stability and generalization bounds for ASGD under much weaker assumptions. Firstly, this paper studies the on-average model stability of ASGD and provides a non-vacuous upper bound on the generalization error, without relying on the Lipschitz assumption. Furthermore, we investigate the excess generalization error of the ASGD algorithm, revealing the effects of asynchronous delay, model initialization, number of training samples and iterations on generalization performance. Secondly, for the first time, this study explores the generalization performance of ASGD in the non-smooth case. We replace smoothness with the much weaker Hölder continuous assumption and achieve similar generalization results as in the smooth case. Finally, we validate our theoretical findings by training numerous machine learning models, including convex problems and non-convex tasks in computer vision and natural language processing.

Recently, one-bit direction of arrival (DOA) estimation has received significant attention due to its low cost and low implementation complexity, while still achieving high accuracy without the need of high-resolution measurements. In this work, we consider nonlinear estimation errors under finite number of snapshots in one-bit covariance reconstruction, and propose the two-step reconstruction approach, first using the arcsine law to reconstruct the unquantized covariance matrix and then incorporating the Toeplitz Hermitian structure as prior information to reconstruct the full-scale virtual uniform linear array (ULA) covariance matrix. It is shown that the error is smaller than the case when the two steps are swapped in order. Simulation results demonstrate the large difference in performance due to the order in which the two steps are applied, our proposed method has remarkably outperformed the current state-of-the-art solutions.

Open knowledge graph (OpenKG) link prediction aims to predict missing factual triples in the form of (head noun phrase, relation phrase, tail noun phrase). Since triples are not canonicalized, previous methods either focus on canonicalizing noun phrases (NPs) to reduce graph sparsity, or utilize textual forms to improve type compatibility. However, they neglect to canonicalize relation phrases (RPs) and triples, making OpenKG maintain high sparsity and impeding the performance. To address the above issues, we propose a Canonicalization-Enhanced Known Fact-Aware (CEKFA) framework that boosts link prediction performance through sparsity reduction of RPs and triples. First, we propose a similarity-driven RP canonicalization method to reduce RPs' sparsity by sharing knowledge of semantically similar ones. Second, to reduce the sparsity of triples, a known fact-aware triple canonicalization method is designed to retrieve relevant known facts from training data. Finally, these two types of canonical information are integrated into a general two-stage re-ranking framework that can be applied to most existing knowledge graph embedding methods. Experiment results on two OpenKG datasets, ReVerb20K and ReVerb45K, show that our approach achieves state-of-the-art results. Extensive experimental analyses illustrate the effectiveness and generalization ability of the proposed framework.

Knowledge graphs are crucial foundations for building intelligent systems, such as question answering and recommendation. However, their performance is hampered by the incompleteness of KGs, so the knowledge graph completion arises to infer whether a triple of the form (head entity, relation, tail entity) is a missing fact. The path‐based approach that encodes paths from the head entity to the tail entity for reasoning achieves good performance. Previous work suggests that entity type is beneficial for learning path representations. Nevertheless, the semantics of entities are not captured accurately, as many entities are not typed or loosely typed. In addition, previous methods tend to model paths only from the forward direction but fail to capture new path patterns from the reverse direction (i.e., tail entity to head entity). In this paper, we introduce a structure enhanced path reasoning (SPR) framework to address the above‐given problems. First, the model uilizes the structure of entities, i.e., their relational contexts (the relations linked from the given entity), to obtain a reliable path representation that captures correct entity semantics. This information is accessible to all nonisolated entities in all KGs, so that it can compensate the semantics for entities or KGs that have no type available. Second, we leverage the structure of paths to derive their reverse paths, so as to enhance the path representation by additionally encoding the new patterns embedded in them through a dual path encoding method. In order to verify the effectiveness of the proposed methods, we design different architectures based on LSTM and Transformer, respectively. Experimental results on two benchmark datasets, WN18RR, and FB15k‐237, show that our approach apparently outperforms state‐of‐the‐art methods on fact prediction task and relation prediction task. Furthermore, extensive experiments illustrate the benefits of enhancing path reasoning by exploiting structure information from entity relational contexts and the dual path encoding method.

Class-incremental Few-shot Named Entity Recognition (CFNER) aims to learn novel entity categories step by step and keep recognizing old classes simultaneously, in which only a few examples of novel classes are added at each incremental step. Many previous works have proved that decoupled two-phase (entity span detection and entity class discrimination) NER models are more suitable for handling CFNER. However, we find that in the second phase, discriminating entity spans has a large performance loss due to feature overlapping (i.e., samples of different categories appear relatively densely in the same region of the feature space). To solve this problem, we propose a Similarity-Driven Adaptive Prototypical Network (SDAPN) for enhancing current CFNER models. Specifically, we reserve a part of feature space for novel categories at the previous step and further mitigate the bias brought by anomalous samples according to the relative similarity of new samples and old class prototypes. Experimental results on two NER datasets show that our proposed approach significantly outperforms prior state-of-the-art approaches. A serial of analytical experiments is conducted to verify the effectiveness of our SDAPN model.

Support vector machines (SVMs) have been recognized as a powerful tool to perform linear classification. When combined with the sparsity-inducing nonconvex penalty, SVMs can perform classification and variable selection simultaneously. However, the nonconvex penalized SVMs in general cannot be solved globally and efficiently due to their nondifferentiability, nonconvexity, and nonsmoothness. Existing solutions to the nonconvex penalized SVMs typically solve this problem in a serial fashion, which are unable to fully use the parallel computing power of modern multi-core machines. On the other hand, the fact that many real-world data are stored in a distributed manner urgently calls for a parallel and distributed solution to the nonconvex penalized SVMs. To circumvent this challenge, we propose an efficient alternating direction method of multipliers (ADMM) based algorithm that solves the nonconvex penalized SVMs in a parallel and distributed way. We design many useful techniques to decrease the computation and synchronization cost of the proposed parallel algorithm. The time complexity analysis demonstrates the low time complexity of the proposed parallel algorithm. Moreover, the convergence of the parallel algorithm is guaranteed. Experimental evaluations on four LIBSVM benchmark datasets demonstrate the efficiency of the proposed parallel algorithm.

Deep learning models have achieved state-of-the-art performance in named entity recognition (NER); the good performance, however, relies heavily on substantial amounts of labeled data. In some specific areas such as medical, financial, and military domains, labeled data is very scarce, while unlabeled data is readily available. Previous studies have used unlabeled data to enrich word representations, but a large amount of entity information in unlabeled data is neglected, which may be beneficial to the NER task. In this study, we propose a semi-supervised method for NER tasks, which learns to create high-quality labeled data by applying a pre-trained module to filter out erroneous pseudo labels. Pseudo labels are automatically generated for unlabeled data and used as if they were true labels. Our semi-supervised framework includes three steps: constructing an optimal single neural model for a specific NER task, learning a module that evaluates pseudo labels, and creating new labeled data and improving the NER model iteratively. Experimental results on two English NER tasks and one Chinese clinical NER task demonstrate that our method further improves the performance of the best single neural model. Even when we use only pre-trained static word embeddings and do not rely on any external knowledge, our method achieves comparable performance to those state-of-the-art models on the CoNLL-2003 and OntoNotes 5.0 English NER tasks.

In this paper, the problem of distributed opportunistic channel access in wireless cooperative networks is investigated. To cope with the energy limitation problem of relay nodes, radio-frequency (RF) energy harvesting is considered, and thus, no external energy is needed for each relay node. Then, a novel distributed opportunistic scheduling (DOS) scheme is proposed. In the scheme, users contend for the channel access opportunity by random access, and then, the user with a successful contention makes a decision whether to give up the opportunity after probing the source-to-relay link and relay-to-destination link by following a strategy. To maximize the average throughput of the network, the optimal strategy of the proposed scheme, which is to help the user to decide whether to give up the transmission opportunity, is derived by optimal stopping theory. The obtained optimal strategy has a threshold-based structure, and thus, it is easy to implement in practice. In addition, the threshold can be calculated off-line by a proposed low-complexity algorithm. Simulation results are provided to demonstrate the superior performance of the proposed DOS scheme.

Mobile edge computing (MEC) has recently emerged as a promising paradigm to meet the increasing computation demands in Internet of Things (IoT). However, due to the limited computation capacity of the MEC server, an efficient computation offloading scheme, which means the IoT device decides whether to offload the generated data to the MEC server, is needed. Considering the limited battery capacity of IoT devices, energy harvesting (EH) is introduced to enhance the lifetime of the IoT systems. However, due to the unpredictability nature of the generated data and the harvested energy, it is a challenging problem when designing an effective computation offloading scheme for the EH MEC system. To cope with this problem, we model the computation offloading process as a Markov decision process (MDP) so that no prior statistic information is needed. Then, reinforcement learning algorithms can be adopted to derive the optimal offloading policy. To address the large time complexity challenge of learning algorithms, we first introduce an after-state for each state-action pair so that the number of states in the formulated MDP is largely decreased. Then, to deal with the continuous state space challenge, a polynomial value function approximation method is introduced to accelerate the learning process. Thus, an after-state reinforcement learning algorithm for the formulated MDP is proposed to obtain the optimal offloading policy. To provide efficient instructions for real MEC systems, several analytical properties of the offloading policy are also presented. Our simulation results validate the great performance of our proposed algorithm, which significantly improves the achieved system reward under a reasonable complexity.

Although concern has been recently expressed with regard to the solution to the non-convex problem, convex optimization is still important in machine learning, especially when the situation requires an interpretable model. Solution to the convex problem is a global minimum, and the final model can be explained mathematically. Typically, the convex problem is re-casted as a regularized risk minimization problem to prevent overfitting. The cutting plane method (CPM) is one of the best solvers for the convex problem, irrespective of whether the objective function is differentiable or not. However, CPM and its variants fail to adequately address large-scale dataintensive cases because these algorithms access the entire dataset in each iteration, which substantially increases the computational burden and memory cost. To alleviate this problem, we propose a novel algorithm named the mini-batch cutting plane method (MBCPM), which iterates with estimated cutting planes calculated on a small batch of sampled data and is capable of handling large-scale problems. Furthermore, the proposed MBCPM adopts a “sink” operation that detects and adjusts noisy estimations to guarantee convergence. Numerical experiments on extensive real-world datasets demonstrate the effectiveness of MBCPM, which is superior to the bundle methods for regularized risk minimization as well as popular stochastic gradient descent methods in terms of convergence speed.

Distributed systems have become the backbone of modern clouds. Users often expect high scalability and performance isolation from distributed systems. Unfortunately, a type of poor software design, which we refer to as performance cascading bugs (PCbugs), can often cause the slowdown of non-scalable code in one job to propagate, causing global performance degradation and even threatening system availability.

Modern object detectors usually suffer from low accuracy issues, as foregrounds always drown in tons of back-grounds and become hard examples during training. Compared with those proposal-based ones, real-time detectors are in far more serious trouble since they renounce the use of region-proposing stage which is used to filter a majority of back-grounds for achieving real-time rates. Though foregrounds as hard examples are in urgent need of being mined from tons of backgrounds, a considerable number of state-of-the-art real-time detectors, like YOLO series, have yet to profit from existing hard example mining methods, as using these methods need detectors fit series of prerequisites. In this paper, we propose a general hard example mining method named Loss Rank Mining (LRM) to fill the gap. LRM is a general method for real-time detectors, as it utilizes the final feature map which exists in all real-time detectors to mine hard examples. By using LRM, some elements representing easy examples in final feature map are filtered and detectors are forced to concentrate on hard examples during training. Extensive experiments validate the effectiveness of our method. With our method, the improvements of YOLOv2 detector on auto-driving related dataset KITTI and more general dataset PASCAL VOC are over 5% and 2% mAP, respectively. In addition, LRM is the first hard example mining strategy which could fit YOLOv2 perfectly and make it better applied in series of real scenarios where both real-time rates and accurate detection are strongly demanded.

In recent years cloud computing provides a new way to address the constraints of limited energy, capabilities, and resources. Distributed hash table (DHT) based distributed networks have become increasingly important for efficient communication in large-scale cloud systems. Previous studies mainly focus on improving the performance such as latency, scalability and robustness, but seldom consider the security demands on the routing paths, for example, bypassing untrusted intermediate nodes. Inspired by Internet source routing, in which the source nodes specify the routing paths taken by their packets, this paper presents CSR, a tag-based, Classified Source Routing scheme in distributed networks to satisfy the security demands on the routing paths. Different from Internet source routing which requires some map of the overall network, CSR operates in a distributed manner where nodes with certain security level are tagged with a label and routing messages requiring that level of security are forwarded only to the qualified next-hops. We show how this can be achieved efficiently, by simple extensions of the traditional routing structures, and safely, so that the routing is uniformly convergent. The effectiveness of our proposals is demonstrated through theoretical analysis and extensive simulations.

The modular datacenter networks (MDCN) comprise inter- and intra-container networks. Although it simplifies the construction and maintenance of mega-datacenters, interconnecting hundreds of containers and supporting online data-intensive services is still challenging. In this paper, we present meGautz, which is the first inter-container network that isolates inter- and intra-container traffic, and it has the following advantages. First, meGautz offers uniform high capacity among servers in the different containers, and balances loads at the container, switch, and server levels. Second, it achieves traffic isolation and allocates bandwidth evenly. Therefore, even under an all-to-all traffic pattern, the inter- and intra-container networks can deal with their own flows without interfering with each other, and both can gain high throughput. meGautz hence improves the performance of both the entire MDCN and individual servers, for there is no performance loss caused by resource competition. Third, meGautz is the first to achieve as graceful performance degradation as computation and storage do. Results from theoretical analysis and experiments demonstrate that meGautz is a high-capacity, fault-tolerant, and traffic isolated inter-container network.

The density peak (DP) algorithm has been widely used in scientific research due to its novel and effective peak density-based clustering approach. However, the DP algorithm uses each pair of data points several times when determining cluster centers, yielding high computational complexity. In this paper, we focus on accelerating the time-consuming density peaks algorithm with a graphics processing unit (GPU). We analyze the principle of the algorithm to locate its computational bottlenecks, and evaluate its potential for parallelism. In light of our analysis, we propose an efficient parallel DP algorithm targeting on a GPU architecture and implement this parallel method with compute unified device architecture (CUDA), called the ‘CUDA-DP platform’. Specifically, we use shared memory to improve data locality, which reduces the amount of global memory access. To exploit the coalescing accessing mechanism of GPU, we convert the data structure of the CUDA-DP program from array of structures to structure of arrays. In addition, we introduce a binary search-and-sampling method to avoid sorting a large array. The results of the experiment show that CUDA-DP can achieve a 45-fold acceleration when compared to the central processing unit based density peaks implementation.

High dimensional data arising from diverse scientific research fields and industrial development have led to increased interest in sparse learning due to model parsimony and computational advantage. With the assumption of sparsity, many computational problems can be handled efficiently in practice. Structured sparse learning encodes the structural information of the variables and has been quite successful in numerous research fields. With various types of structures discovered, sorts of structured regularizations have been proposed. These regularizations have greatly improved the efficacy of sparse learning algorithms through the use of specific structural information. In this article, we present a systematic review of structured sparse learning including ideas, formulations, algorithms, and applications. We present these algorithms in the unified framework of minimizing the sum of loss and penalty functions, summarize publicly accessible software implementations, and compare the computational complexity of typical optimization methods to solve structured sparse learning problems. In experiments, we present applications in unsupervised learning, for structured signal recovery and hierarchical image reconstruction, and in supervised learning in the context of a novel graph-guided logistic regression.

In-memory storage has the benefits of low I/O latency and high I/O throughput. Fast failure recovery is crucial for large-scale in-memory storage systems, bringing network-related challenges, including false detection due to transient network problems, traffic congestion during the recovery, and top-of-rack switch failures. In order to achieve fast failure recovery, in this paper, we present CubicRing, a distributed structure for cube-based networks, which exploits network proximity to restrict failure detection and recovery within the smallest possible one-hop range. We leverage the CubicRing structure to address the aforementioned challenges and design a network-aware in-memory key-value store called MemCube. In a 64-node 10GbE testbed, MemCube recovers 48 GB of data for a single server failure in 3.1 s. The 14 recovery servers achieve 123.9 Gb/s aggregate recovery throughput, which is 88.5% of the ideal aggregate bandwidth and several times faster than RAMCloud with the same configurations.

In this paper, we consider a class of constrained nonconvex regularized minimization problems, where the constraints is linearly constrained. It was reported in the literature that nonconvex regularization usually yields a solution with more desirable sparse structural properties beyond convex ones. However, it is not easy to obtain the proximal mapping associated with nonconvex regularization, due to the imposed linearly constraints. In this paper, the optimization problem with linear constraints is solved by the Linearized Alternating Direction Method of Multipliers (LADMM). Moreover, we present a detailed convergence analysis of the LADMM algorithm for solving nonconvex compositely regularized optimization with a large class of nonconvex penalties. Experimental results on several real-world datasets validate the efficacy of the proposed algorithm.

We consider a wide spectrum of regularized stochastic minimization problems, where the regularization term is composite with a linear function. Examples of this formulation include graph-guided regularized minimization, generalized Lasso and a class of ℓ1 regularized problems. The computational challenge is that the closed-form solution of the proximal mapping associated with the regularization term is not available due to the imposed linear composition. Fortunately, the structure of the regularization term allows us to reformulate it as a new convex-concave saddle point problem which can be solved using the Primal-Dual Hybrid Gradient (PDHG) approach. However, this approach may be inefficient in realistic applications as computing the full gradient of the expected objective function could be very expensive when the number of input data samples is considerably large. To address this issue, we propose a Stochastic PDHG (SPDHG) algorithm with either uniformly or non-uniformly averaged iterates. Through uniformly averaged iterates, the SPDHG algorithm converges in expectation withrate for general convex objectives and O(log (t)/t) rate for strongly convex objectives, respectively. While with non-uniformly averaged iterates, the SPDHG algorithm is expected to converge with O(1/t) rate for strongly convex objectives. Numerical experiments on different genres of datasets demonstrate that our proposed algorithm outperforms other competing algorithms.

Internet-based virtual computing environment (iVCE) has been proposed to combine data centers and other kinds of computing resources on the Internet to provide efficient and economical services. Virtual machines (VMs) have been widely used in iVCE to isolate different users/jobs and ensure trustworthiness, but traditionally VMs require a long period of time for booting, which cannot meet the requirement of iVCE’s large-scale and highly dynamic applications. To address this problem, in this paper we design and implement VirtMan, a fast booting system for a large number of virtual machines in iVCE. VirtMan uses the Linux Small Computer System Interface (SCSI) target to remotely mount to the source image in a scalable hierarchy, and leverages the homogeneity of a set of VMs to transfer only necessary image data at runtime. We have implemented VirtMan both as a standalone system and for OpenStack. In our 100-server testbed, VirtMan boots up 1000 VMs (with a 15 GB image of Windows Server 2008) on 100 physical servers in less than 120 s, which is three orders of magnitude lower than current public clouds.

Fingerprint has been widely used in a variety of biometric identification systems in the past several years due to its uniqueness and immutability. With the rapid development of fingerprint identification techniques, many fingerprint identification systems are in urgent need to deal with large-scale fingerprint storage and high concurrent recognition queries, which bring huge challenges to the system. In this circumstance, we design and implement a distributed and load-balancing fingerprint identification system named Pegasus, which includes a distributed feature extraction subsystem and a distributed feature storage subsystem. The feature extraction procedure combines the Hadoop Image Processing Interface (HIPI) library to enhance its overall processing speed; the feature storage subsystem optimizes MongoDB’s default load balance strategy to improve the efficiency and robustness of Pegasus. Experiments and simulations are carried out, and results show that Pegasus can reduce the time cost by 70% during the feature extraction procedure. Pegasus also balances the difference of access load among front-end mongos nodes to less than 5%. Additionally, Pegasus reduces over 40% of data migration among back-end data shards to obtain a more reasonable data distribution based on the operation load (insertion, deletion, update, and query) of each shard.

This paper introduces a topology-independent software-defined edge control framework named FRINGE to scale out the Ethernet Datacenter Network (DCN). FRINGE exploits programmable OpenFlow-enabled switches deployed at the edge of DCN to aggregate the forwarding rules without introducing extra packet headers. We implement the proposed FRINGE framework in an SDN prototyping environment and validate it under three typical DCN topologies including Multi-Root Tree, HyperX and Jellyfish, where three different types of DCN workloads are applied. Evaluation results reveal that FRINGE can significantly reduce the total number of rules in all network devices and suppress most of the useless broadcast packets in the DCN.

Virtualization is the foundation for cloud computing, and the virtualization can not be achieved without software defined, elastic, flexible and scalable virtual layers. Unfortunately, if multiple virtual storage devices are chained together, the system may be subject to severe performance degradation. While the read-ahead (RA) mechanism in storage devices plays a very important role to improve I/O performance, RA may not be effective as expected for multiple virtualization layers, since it is originally designed for one layer only. When I/O requests are passed through a long I/O path, they may trigger a chain reaction and lead to unnecessary data transmission and thus bandwidth waste. In this paper, we study the dynamic behavior of RA through multiple I/O layers and demonstrate that if controlled well, RA can greatly accelerate I/O speed. We present RAFlow, a RA control mechanism, to effectively improve I/O performance by strategically expanding RA window at each layer. Our real-world experiments show that it can achieve 20% to 50% performance improvement in I/O paths with up to 8 virtualized storage devices.

Infrastructure as a service (IaaS) allows users to rent resources from the Cloud to meet their various computing requirements. The pay-as-you-use model, however, poses a nontrivial technical challenge to the IaaS cloud service providers: how to fast provision a large number of virtual machines (VMs) to meet users' dynamic computing requests? We address this challenge with VMThunder, a new VM provisioning tool, which downloads data blockson demandduring the VM booting process and speeds up VM image streaming by strategically integrating peer-to-peer (P2P) streaming techniques with enhanced optimization schemes such as transfer on demand, cache on read, snapshot on local, and relay on cache. In particular, VMThunder stores the original images in a share storage and in the meantime it adopts a tree-based P2P streaming scheme so that common image blocks are cached and reused across the nodes in the cluster. We implement VMThunder in CentOS Linux and thoroughly test its performance. Comprehensive experimental results show that VMThunder outperforms the state-of-the-art VM provisioning methods, with respect to scalability, latency, and VM runtime I/O performance.

The networked application environment has motivated the development of multitasking operating systems for sensor networks and other low-power electronic devices, but their multitasking capability is severely limited because traditional stack management techniques perform poorly on small-memory systems without virtual memory support. In this paper, we show that combining binary translation and a new kernel runtime can lead to efficient OS designs on resource constrained platforms. We introduce SenSmart, a multitasking OS for sensor networks, and present new OS design techniques for supporting preemptive multitask scheduling, memory isolation, and adaptive stack management. Our solution provides memory isolation and automatic stack relocation on usual sensornet platforms. The adaptive stack management frees programmers from the burden of estimating tasks' stack usage, yet it enables SenSmart to schedule and run more tasks than other multitasking OSes for sensor networks. We have implemented SenSmart on MICA2/MICAz motes. Evaluation shows that SenSmart has a significantly better capability in managing concurrent tasks than other sensornet operating systems.

Traditional BGP implementation is based on single process or single thread model and not fit for cluster architecture of future core router. We have developed SDBGP, a distributed BGP implementation for future core router that provides excellent performance, reliability and scalability. SDBGP is designed on a fully distributed architecture, which gives equal chance for router nodes to participate in BGP routes computing and storage. SDBGP distributes BGP neighbors among cluster router nodes in a balanced way and improves BGP's performance by parallel processing of BGP neighbors. We deploy SDBGP on a software cluster router with four nodes. Performance testing shows that SDBGP can achieve great scalability in neighbor number and routes computation. It can get almost linear speedup with the increasing of cluster route size.

Requirement Engineering (RE) has become an attractive field in both industry and academic. Many RE approaches have been presented in the past years to support eliciting, modeling, analyzing and specifying requirements of system to be built. However, requirement characteristics of kinds of systems like large scale software intensive systems pose several issues to requirements analysis and therefore challenge the extant RE approaches. This paper investigates a number of important metaphors in RE and proposes a novel RE approach that adopts capability as requirement metaphor. We discuss the requirements challenges coming from the changes of system-to-be and argue the necessity to introduce new abstraction and technology into RE to deal with the problems. The notions of capability and the reason to adopt capability as requirement metaphor are analyzed. The meta-model and framework of capability-based requirement engineering is proposed. A case is also studied in order to illustrate our approach. Capability as new abstraction in RE provides a new way to represent, analyze and tradeoff requirements.

Abstract Distributed Hash Tables (DHTs) are scalable, self‐organizing, and adaptive to underlying topology changes, thus being a promising infrastructure for hosting large‐scale distributed applications. The ever‐wider use of DHT infrastructures has found more and more applications that require support for range queries. Recently, a number of DHT‐based range query schemes have been proposed. However, most of them suffer from high query delay or imbalanced load distribution. To address these problems, in this paper we first present an efficient indexing structure called Balanced Kautz (BK) tree that uniformly maps them‐dimensional data space onto DHT nodes, and then propose a BK tree‐based range query scheme called ERQ that processes range queries in a parallel fashion and guarantees to return the results in a bounded delay. In a DHT withNnodes, ERQ can answer any range of query in less thanrmlog N(2loglog N+ 1) hops in a load‐balanced manner, irrespective of the queried range, the whole space size, or the number of queried attributes. The effectiveness of our proposals is demonstrated through experiments. Copyright © 2010 John Wiley & Sons, Ltd.

Network-based signature generation (NSG) has been proposed as a way to automatically and quickly generate accurate signatures for worms, especially polymorphic worms. In this paper, we propose a new NSG system-PolyTree, to defend against polymorphic worms. We observe that signatures from worms and their variants are relevant and a tree structure can properly reflect their familial resemblance. Hence, in contrast to an isolated view of generated signatures in previous approaches, PolyTree organizes signatures extracted from worm samples into a tree structure, called signature tree, based on the formally defined "more specific” relation of simplified regular expression signatures. PolyTree is composed of two components, signature tree generator and signature selector. The signature tree generator implements an incremental signature tree generation algorithm from worm sample clustering, up-to-date signature refinement to efficient tree construction. The incremental signature tree construction gives insight on how the worm variants evolve over time and allows signature refinement upon a new worm sample arrival. The signature selector chooses a set of signatures for worm detection from a benign traffic pool and the current signature tree constructed by the signature tree generator. Experiments show that PolyTree cannot only generate accurate signatures for polymorphic worms with noise, but these signatures are well organized in the signature tree to reflect the inherent relations of worms and their variants.

The networked application environment has motivated the development of multitasking operating systems for sensor networks and other low-power electronic devices, but their multitasking capability is severely limited because traditional stack management techniques perform poorly on small memory systems. In this paper, we show that combining binary translation and a new kernel runtime can lead to efficient OS designs on resource-constrained platforms. We introduce SenSmart, a multitasking OS for sensor networks, and present new OS design techniques for supporting preemptive multi-task scheduling, memory isolation, and versatile stack management. We have implemented SenSmart on MICA2/MICAz motes. Evaluation shows that SenSmart performs efficient binary translation and demonstrates a significantly better capability in managing concurrent tasks than other sensor net operating systems.

The efficiency of communication is a key factor to the performance of networking applications, and concurrent communication is an important approach to the efficiency of communication. However, many concurrency opportunities are very difficult to exploit because they depend on some undeterministic conditions. If these conditions are highly predictable, speculative execution can be a very effective approach to cope with the uncertainties. Existing researches on speculation seldom target at networking systems, and none of them can handle the event-driven model that is very popular in such systems. In this paper, we propose Nexus, a novel speculation scheme that supports event-driven networking applications. Nexus analyzes the dependence relationship of events, and performs speculation according to the duality of events and threads. Evaluation on a prototype implementation of nexus shows that this approach can significantly reduces the time needed to complete an event-driven program.

In many practical applications of wireless sensor networks, it is crucial to accomplish the localization of sensors within a given time bound. We find that the traditional definition of relative localization is inappropriate for evaluating its actual overhead. To address this problem, we define a novel problem called essential localization, and present the first rigorous study on the essential localizability of a wireless sensor network within a given time bound. We propose an efficient distributed algorithm for time-bounded essential localization over a sensor network, and evaluate the performance of our algorithm with extensive simulations.

Transactional Memory (TM) research has focused on multi-core processors; limited research has been aimed at the clusters, leaving the area of NUMA (Non-Uniform Memory Access) system unexplored. The NUMA system's memory is physically distributed which brings the different access latency between local and remote memory. The existing TM design is not NUMA-aware which makes significant performance degradation on NUMA system. We introduce the latency-based conflict detection process and the forecasting-based conflict preventing method. The NUMA-aware strategies provide a good practical TM performance on NUMA system.

DHTs are scalable, self-organizing, and adaptive to underlying topology changes, thus being a promising infrastructure for realizing autonomic communications in distributed systems. To provide the above advantages, however, DHTs sacrifice flexibility, that is, all messages are routed by using a common algorithm in a DHT on the assumption that all participant nodes are homogeneous. In practice, nodes in large-scale systems might be heterogeneous with respect to their capabilities, reputations, affiliations of administrative domains, and so on, which consequently makes it preferable to distinguish the heterogeneity of participant nodes and enable flexible control of routing destinations and paths. To achieve this, in this paper we propose a novel approach that supports organizing nodes into groups and enables routing control in a DHT. The effectiveness of our proposals is demonstrated through theoretical analysis and extensive simulations.

Memory accesses limit the performance of stream processors. By exploiting the reuse of data held in the Stream Register File (SRF), an on-chip, software controlled storage, the number of memory accesses can be reduced. In current stream compilers, reuse exploitation is only attempted for simple stream references, those whose start and end are known. Compiler analysis, from outside of stream processors, does not directly enable the consideration of other more complex stream references. In this article, we propose a transformation to automatically optimize stream programs to exploit the reuse supplied by loop-dependent stream references. The transformation is based on three results: lemmas identifying the reuse supplied by stream references, a new abstract representation called the Stream Reuse Graph (SRG) depicting the identified reuse, and the optimization of the SRG for our transformation. Both the reuse between the whole sequences accessed by stream references and between partial sequences is exploited in the article. In particular, partial reuse and its treatment are quite new and have never, to the best of our knowledge, appeared in scalar and vector processing. At the same time, reusing streams increases the pressure on the SRF, and this presents a problem of which reuse should be exploited within limited SRF capacity. We extend our analysis to achieve this objective. Finally, we implement our techniques based on the StreamC/KernelC compiler that has been optimized with the best existing compilation techniques for stream processors. Experimental results show a resultant speed-up of 1.14 to 2.54 times using a range of benchmarks.

Extensible processors are increasingly becoming popular as they allow for incorporating custom instructions to meet design constraints. However, identifying custom instructions under architectural input/output ports constraint is a time consuming process particularly when large applications are considered. To rapidly identify the most profitable custom instructions with large inputs and outputs, this paper proposes a novel identification algorithm for enumerating maximal convex subgraphs containing no invalid node (i.e., maximal valid subgraphs). The proposed enumerating strategy is based on divide-and-conquer with a top-down manner, rather than the bottom-up manner utilized in the state-of-the-art. The division operation only considers invalid inner nodes of the given DFG, rather than taking all the invalid nodes into account, and thus accelerates enumeration of the maximal valid subgraphs. Experimental results show that, the improvement over the latest work is more than 90% for 60% DFG instances of the acknowledged benchmarks.

Transactional memory (TM) research has focused on multi-core processors; limited research has been aimed at the clusters. The intention of deploying TM on clusters is using more processors to solve big problems with this convenient technique. But the performance of the existing cluster's TM is poor because of the expensive remote access. The conflict detection, which is the most frequent operation of TM, is highly depending on the remote memory access. The remote memory access is usually 10 to 100 times slower than the local one in a cluster. We introduce the two-phase conflict detection strategy. By dividing the conflict detection process into two levels, the hierarchical strategy provides a good practical performance.

Most Software Transactional Memory (STM) research has focused on multi-core processors and small SMP machines; limited research has been aimed at the clusters, leaving the area of big SMP machines unexplored. Big SMP machine usually use Non-Uniform Memory Access (NUMA) to unburden the overloading between CPUs and the memory. In this paper, we evaluate several STM implementations on big SMP machine with cache coherent NUMA (ccNUMA) architecture. We found the remote memory access latency is the key factor influencing the STM performance. We also analyze the different design choices of STM. Finally, we conclude a specific design choice to achieve high performance in this domain.

DHTs are scalable, self-organizing, and adaptive to underlying topology changes, thus being a promising infrastructure for realizing efficient Web service discovery. Range queries play an important role in service discovery, and in recent years a number of DHT-based range query schemes have been proposed. However, most of them suffer from high query delay and high processing cost. This paper presents ERQ, an Efficient scheme for delay bounded Range Query processing over DHTs. We first emulate the PHT structure and design a balanced Kautz (BK) tree to uniformly map the m-dimensional data space onto DHT nodes, and then present a novel algorithm that processes range queries in a parallel fashion, where an on-the-fly space pruning mechanism is adopted to reduce the processing cost. In a DHT with N nodes, ERQ can answer any range query in less than logN (2loglogN+1) hops with low processing cost, irrespective of the queried range, the whole space size, or the number of queried attributes. The effectiveness of ERQ is demonstrated through extensive experiments.

The complexity of channel scheduling in Multi- Radio Multi-Channel (MR-MC) wireless networks is an open research topic. This problem asks for the set of edges that can support maximum amount of simultaneous traffic over orthogonal channels under a certain interference model. There exist two major interference models for channel scheduling, with one under the physical distance constraint, and one under the hop distance constraint. The complexity of channel scheduling under these two interference models serves as the foundation for many problems related to network throughput maximization. However, channel scheduling was proved to be NP-Hard only under the hop distance constraint for SR-SC wireless networks. In this paper, we fill the void by proving that channel scheduling is NP-Hard under both models in MR-MC wireless networks. In addition, we propose a polynomial-time approximation scheme (PTAS) framework that is applicable to channel scheduling under both interference models in MR-MC wireless networks. Furthermore, we conduct a comparison study on the two interference models and identify conditions under which these two models are equivalent for channel scheduling.

With the increasing popularity of the peer-to-peer (P2P) computing paradigm, many general range query schemes for distributed hash table (DHT)-based P2P systems have been proposed in recent years. Although those schemes can provide range query capability without modifying the underlying DHTs, they have the query delay depending on both the scale of the system and the size of the query space or the specific query, and thus cannot guarantee to return the query results in a bounded delay. In this paper, we propose Armada, an efficient range query processing scheme to support delay-bounded single-attribute and multiple-attribute range queries. It is the first delay-bounded general range query scheme on constant-degree DHTs, and can return the results for any range query within 2logN hops in a P2P system with N peers. Results of analysis and simulations show that the average delay in Armada is less than logN, and the average message cost of single-attribute range queries is about logN+2n 2 (n is the number of peers that intersect with the query). These results are very close to the lower bounds on delay and message cost of range queries over constant-degree DHTs.

We transform the 3D underwater sensor network (USN) localization problem into its 2D counterpart by employing sensor depth information and a simple projection technique. We first prove that a nondegenerative projection preserves network localizability. We then prove that given a network and a constant k, all of the geometric k-lateration localization methods are equivalent. Based on these results, we design a purely distributed bilateration localization scheme for 3D USNs termed as underwater sensor positioning (USP). Through extensive simulations, we show that USP has the following nice features: (1) improved localization capabilities over existing 3D methods, (2) low storage and computation requirements, (3) predictable and balanced communication overhead, and (4) robustness to errors from the underwater environment.

Most proposed DHTs have their unique maintenance mechanisms specific to the static graphs on which they are based. In this paper we propose distributed line graphs (DLG), a universal framework for building DHTs based on arbitrary constant-degree graphs. We prove that in a DLG-enabled, N-node DHT, the out-degree is d, the in-degree is between 1 and 2d, and the diameter is less than 2(logdN-logdN0+D0+1), where d, D0and N0represent the degree, diameter and number of nodes of the initial graph, respectively. The maintenance cost of DLG-enabled DHTs is O(logdN). We show the power of DLG technique by applying it to Kautz graphs to propose a new DHT scheme.

We study the localization problem in sparse 3D underwater sensor networks. Considering the fact that depth information is typically available for underwater sensors, we transform the 3D underwater positioning problem into its two- dimensional counterpart via a projection technique and prove that a non-degenerative projection preserves network localizability. We further prove that given a network and a constantk, all of the geometrick-lateration localization methods are equivalent. Based on these results, we design a purely distributed localization framework termed USP. This framework can be applied with any ranging method proposed for 2D terrestrial sensor networks. Through theoretical analysis and extensive simulation, we show that USP preserves the localizability of the original 3D network via a simple projection and improves localization capabilities when bilateration is employed. USP has low storage and computation requirements, and predictable and balanced communication overhead.

Multipath routing is attractive for load-balancing, fault-tolerance, and security enhancement. However, constructing and maintaining a set of node-disjoint paths between the data source and sink is non-trivial in a dynamic environment. In this paper, we study the problem of route recovery in vertex-disjoint multipath routing for sensor networks with many-to-one traffic patterns. We identify the sufficient conditions for multipaths to be recovered when the existing node-disjoint paths are broken, and provide a simple framework for multipath maintenance. This framework is very efficient in time when multipath source routing is employed. Our findings can help to conserve network resource by not launching any route discovery when the data source realizes that a new route may not exist, to guide mobile data sources to relocate themselves in order to reconstruct the new multipaths, and to help newly-deployed data sources quickly determine whether the required number of multipaths exist for sure or not and then compute them. The technique proposed in this paper is a good complement to the classic max-flow algorithm when node-disjoint multipaths are needed.

In most DHTs proposed so far, all nodes are assumed to be homogeneous, and all messages are routed using a common algorithm. In practice, however, nodes in large-scale systems might be heterogeneous with respect to their capabilities, reputations, affiliations of administrative domains, and so on, which consequently makes it preferable to distinguish the heterogeneity of participant nodes. To achieve this, in this paper we present Grouped Tapestry (GTap), a novel Tapestry-based DHT that supports organizing nodes into groups and allows flexible DHT routing. The effectiveness of our proposals is demonstrated through theoretical analysis and extensive simulations.

experimental Mbone for a number of years. The practical pricing mechanism is the foundation for the deploying of IP multicast in the inter-domain Internet. The IP multicast service model and its pricing mechanism are discussed in this paper. Three models are proposed for all applications in the real environments. They are ICP-USER model, ICP-ISP model and ICP-ISP-USER model. Here, the Internet is considered as an ecosystem, and the entities construct a supply chain with the welfare maximum purpose. Our work gives a general discussion on the practical pricing mechanism for the stability of the economic relationship between ICPs, ISPs and users in the Internet. Key Words—IP multicast, pricing mechanism, Cost-sharing mechanism

As an innovative distributed computing technique for sharing the memory resources in high-speed network, RAM Grid exploits the distributed free nodes, and provides remote memory for the nodes which are short of memory. One of the RAM Grid systems named DRACO, tries to provide cooperative caching to improve the performance of the user node which has mass disk I/O but lacks local memory. However, the performance of DRACO is constrained with the network communication cost. In order to hide the latency of remote memory access and improve the caching performance, we proposed using push- based prefetching to enable the caching providers to push the potential useful memory pages to the user nodes. Specifically, for each caching provider, it employs sequential pattern mining techniques, which adapts to the characteristics of memory page access sequences, on locating useful memory pages for prefetching. We have verified the effectiveness of the proposed method through system analysis and trace-driven simulations.

As an application of large scale distributed network computing system, RAM Grid tries to solve the problem of memory resource sharing and utilization. Due to the special properties of memory, traditional resource information management approaches cannot be adapted easily. This paper proposes a clustering based resource aggregating scheme under the background of RAM Grid, which can reduce the scale of resource information management efficiently. With analogy to the force field and potential energy theory in physics, the basic model, the force field-potential energy model, and the corresponding distributed algorithms are proposed, respectively. The model and algorithms are also evaluated by real network topologies based simulation.

Searching in large-scale unstructured peer-to-peer networks is challenging due to the lack of effective hint information to guide queries. In this paper, we propose POP, a Parallel, collaborative and Probabilistic search mechanism, in which query messages are viewed as search units to collaborate with each other and aggregate the distributed hints during the search process. A scheme called distributed Bloom filter (DBF) is presented to propagate the hints with a bandwidth-aware manner, in which a node divides the received Bloom filter vector into subvectors and disseminates the fragments to its neighbors according to their bandwidth capacity. The effectiveness of POP is demonstrated through theoretical analysis and extensive simulations.

In this paper, we present a kernel-based least squares policy iteration (KLSPI) algorithm for reinforcement learning (RL) in large or continuous state spaces, which can be used to realize adaptive feedback control of uncertain dynamic systems. By using KLSPI, near-optimal control policies can be obtained without much a priori knowledge on dynamic models of control plants. In KLSPI, Mercer kernels are used in the policy evaluation of a policy iteration process, where a new kernel-based least squares temporal-difference algorithm called KLSTD-Q is proposed for efficient policy evaluation. To keep the sparsity and improve the generalization ability of KLSTD-Q solutions, a kernel sparsification procedure based on approximate linear dependency (ALD) is performed. Compared to the previous works on approximate RL methods, KLSPI makes two progresses to eliminate the main difficulties of existing results. One is the better convergence and (near) optimality guarantee by using the KLSTD-Q algorithm for policy evaluation with high precision. The other is the automatic feature selection using the ALD-based kernel sparsification. Therefore, the KLSPI algorithm provides a general RL method with generalization performance and convergence guarantee for large-scale Markov decision problems (MDPs). Experimental results on a typical RL task for a stochastic chain problem demonstrate that KLSPI can consistently achieve better learning efficiency and policy quality than the previous least squares policy iteration (LSPI) algorithm. Furthermore, the KLSPI method was also evaluated on two nonlinear feedback control problems, including a ship heading control problem and the swing up control of a double-link underactuated pendulum called acrobot. Simulation results illustrate that the proposed method can optimize controller performance using little a priori information of uncertain dynamic systems. It is also demonstrated that KLSPI can be applied to online learning control by incorporating an initial controller to ensure online performance.

Many general range query schemes for DHT-based peer-to-peer (P2P) systems have been proposed, which do not need to modify the underlying DHTs. However, most existing works have the query delay depending on both the scale of the system and the size of the query space or the specific query, and thus cannot guarantee to return the query results in a bounded delay. In this paper, we propose Armada, an efficient general range query scheme to support single-attribute and multipleattribute range queries. Armada is the first delaybounded range query scheme over constant-degree DHTs, and can return the results for any range query within 2logN hops in a P2P system with N peers. Results of analysis and simulations show that the average delay of Armada is less than logN, and the average message cost of single-attribute range queries is about logN+2n..2 (n is the number of peers that intersect with the query). These results are very close to the lower bounds on delay and message cost of range queries over constant-degree DHTs.

Memory-intensive applications often suffer from the poor performance of disk swapping when memory is inadequate. Remote memory sharing schemes, which provide a remote memory that is faster than the local hard disk, are able to improve the performance of such applications. Due to the limitation of being applicable within single clusters only, however, most of the previous remote memory mechanisms, such as the network memory scheme, fail to be extendable into a large scale, distributed, heterogeneous, and dynamic environment. In this work, we propose a service-oriented grid memory sharing scheme, distributed paging RAM grid (DPRG). We study the properties and criteria of large scale memory sharing, and then design major operations and optimizations to fit the usage of grid systems. We collect trace from our grid environment, and evaluate DPRG through comprehensive trace-driven simulations. Results show that DPRG significantly outperforms existing remote memory sharing schemes and supports grid computing applications effectively

This paper analyzes the relationship between BGP convergence and the power-law of the Internet. The inter-domain routing system is classified into three hierarchies based on the power-law and commercial relations of autonomous systems. The relation of network topology and three convergence parameters-convergence time T, affected ASs set Nc and affected paths factor mu is presented for all sorts of convergence events in different layers. The result shows that the power-law nature of network influences the BGP convergence greatly

Random walks are an excellent search mechanism in unstructured P2P network. However, it suffers long delay when searching files, especially for uncommon files. An efficient search mechanism - ARW is presented. ARW utilizes path information carrying and walker self-replication technologies to increase the number of different peers all walkers visit and reduces the delay which random walks spends on searching files especially for uncommon files greatly. Experimental results show that ARW reduces the delay of random walks on searching uncommon files by 63.7% with almost no extra overhead in a Gnutella-like overlay network and gets a good tradeoff between performance and overhead.

The distributed hash table (DHT) scheme has become the core component of many large-scale peer-to-peer networks. Degree, diameter, and congestion are important measures of DHT schemes. Many proposed DHT schemes are based on traditional interconnection topologies, one being the Kautz graph, which is a static topology with many good properties such as optimal diameter, optimal fault-tolerance, and low congestion. In this paper, we propose FISSIONE: the first effective DHT scheme based on Kautz graphs. FISSIONE is constant degree, O(log N) diameter, and (1 + o(1))-congestion-free. FISSIONE shows that a DHT scheme with constant degree and constant congestion can still achieve O(log N) diameter, which is better than the lower bound /spl Omega/(N/sup 1/d/) conjectured before. The average degree of FISSIONE is 4, the diameter is less than 2 log N, and the maintenance message cost is less than 3 log N. The average routing path length is about log N and is shorter than CAN or Koorde with the same degree when the peer-to-peer network is large-scale. FISSIONE can achieve good load balance, high performance, and low congestion and these properties are carefully evaluated by formal proofs or simulations in the paper.

Numerous studies have shown the difficulty for a routing protocol to scale to large mobile ad hoc networks. This article proposes a cluster-based multipath dynamic source routing in MANET (CMDSR) that is designed to be adaptive according to network dynamics. It uses the hierarchy to perform route discovery and distributes traffic among diverse multiple paths. The CMDSR is based on a 2-level hierarchical scheme: the 1-cell cluster and 2-server cluster. The main idea of our proposition is to transfer the route discovery procedure to the 2-server level to prevent the network flooding due to the DSR route discovery. Thus, route discovery does not require flooding mechanism and overhead is minimized and improve the networks scalability.

Within data grid environments, data replication is a general mechanism to improve performance and availability for distributed applications. However, it is a challenging problem to find the physical locations of multiple replicas of desired data efficiently in large-scale wide area data grid systems. In this paper, we proposed a new dynamic self-adaptive distributed replica location method - DSRL to solve the problem. In DSRL, each data element has a home node, which maintains the indices of the location information replicas. Home nodes are used to support locating multiple replicas of the same data element efficiently. Meanwhile, DSRL employs local location nodes which maintain the local replica information of data elements to support local query for local replicas. A dynamic mapping technique that can adapt to the joining or departing of home nodes is utilized to spread global replica location information evenly on location nodes. The correctness and properties of DSRL are presented and proved. Analysis and experiments show that DSRL can achieve low latency, good scalability, reliability, adaptability and ease of implementation.

Flooding in mobile ad hoc networks has poor scalability as it leads to serious redundancy, contention and collision. We propose an efficient approach to reduce the broadcast redundancy. In our approach, local topology information and the statistical information about the duplicate broadcasts are utilized to avoid unnecessary rebroadcasts. Simulation is conducted to compare the performance of our approach and flooding. The simulation results demonstrate the advantages of our approach. It can greatly reduce the redundant messages, thus saving much network bandwidth and energy. It can also enhance the reliability of broadcasting. It can be used in static or mobile wireless networks to implement scalable broadcast or multicast communications.