Elastic precision quantization enables multi-bit deployment via a single optimization pass, fitting diverse quantization scenarios. Yet, the high storage and optimization costs associated with the Transformer architecture, research on elastic quantization remains limited, particularly for large language models. This paper proposes QuEPT, an efficient post-training scheme that reconstructs block-wise multi-bit errors with one-shot calibration on a small data slice. It can dynamically adapt to various predefined bit-widths by cascading different low-rank adapters, and supports real-time switching between uniform quantization and mixed precision quantization without repeated optimization. To enhance accuracy and robustness, we introduce Multi-Bit Token Merging (MB-ToMe) to dynamically fuse token features across different bit-widths, improving robustness during bit-width switching. Additionally, we propose Multi-Bit Cascaded Low-Rank adapters (MB-CLoRA) to strengthen correlations between bit-width groups, further improve the overall performance of QuEPT. Extensive experiments demonstrate that QuEPT achieves comparable or better performance to existing state-of-the-art post-training quantization methods.

Cross-chain swaps are a crucial application that facilitates the transfer of digital assets across different blockchains, thereby enhancing the flexibility and availability of asset circulation. Ensuring atomicity is a fundamental objective for cross-chain swaps. The Hashed TimeLock Contract (HTLC) protocol is one of the primary solutions for cross-chain swaps. It ensures atomicity by statically partitioning execution actions for swap submission and asset refund along the time dimension. Such designs rely on a predictable upper bound on transaction confirmation time. However, this assumption does not hold in practical blockchain environments, leading to atomicity violations. To address this limitation, we propose Chuchu, a hashlock group protocol for cross-chain swaps. Chuchu abandons static partitioning along the time dimension and instead distinguishes swap submission and asset refund through explicitly defined asset locking states and their dynamic transitions. To cope with divergent execution progress across blockchains, Chuchu bounds execution progress divergence and introduces an exit-proof mechanism, ensuring that locked assets always have well-defined and consistent unlocking paths under all execution scenarios. The effectiveness and feasibility of Chuchu are demonstrated through theoretical analysis and formal verification using TLA+. Meanwhile, experiment results show that Chuchu reduces execution time by over 98% compared to the HTLC protocol in the case of swap rollbacks.

Federated Prompt Learning (FPL) enhances federated learning by exchanging optimized prompt vectors instead of full model parameters, reducing communication costs and privacy risks. However, existing methods like PromptFL struggle under Non-IID conditions, where heterogeneous client data distributions cause local drift, slow convergence, and catastrophic forgetting. While federated personalization improves local adaptation by optimizing client-specific prompts, it lacks emphasis on global prompt optimization, limiting generalization to new clients. To address these challenges, we propose FedPTR (Federated Prompt Tuning with Retraining), which leverages server-side prompt retraining to enhance global prompt generalization. By integrating feature distillation for drift control and template prompt alignment for forgetting reduction, FedPTR enhances global prompt stability and generalization. Experimental results show that FedPTR significantly improves stability in Non-IID settings. Especially on CIFAR-10, FedPTR consistently achieves stable accuracy (89.62%–92.95%), outperforming existing methods and providing an effective solution for federated prompt learning under Non-IID conditions.

With the development of blockchain applications, demand for cross-chain technology has been increasing. Relay chain mode is the state-of-the-art and mainstream solution nowadays. However, the relay chain mode suffers from poor performance, which stems from its core facility – the relay chain. Therefore, guiding its improvement and parameters configuration is vital. Currently, there is no specialized performance model of the relay chain. The cross-chain scenario involves receiving transactions from blockchains and uniformly verifying them, while general blockchain models are not applicable for it. Relay chains are characterized by the following features: transaction arrival in batches with uncertain sizes, updating block headers for simplified payment verification (SPV), Byzantine fault tolerance (BFT) type protocol, and different packaging rules. This work first proposes an analytical framework for relay chain performance. It captures the mentioned features by constructing a batch-arrival and bulk-service model. We give a concrete calculation of the relay chain with practical BFT (PBFT) consensus and develop a method to arrive at the computational forms of two essential performance descriptors: system throughput and cross-chain transaction confirmation delay. Through this model, we can judge accurately whether the relay chain is overloaded, and eliminate the overload state by tuning the parameters; and we can evaluate the system performance under different traffic and design parameters. Finally, we verify the model through experiments. With our study, operators can configure the system parameters effectively and improve the relay chain to meet the requirements of practical use.

The ability of model quantization with arbitrary bit-width to dynamically meet diverse bit-width requirements during runtime has attracted significant attention. Recent research has focused on optimizing large-scale training methods to achieve robust bit-width adaptation, which is a time-consuming process requiring hundreds of GPU hours. Furthermore, converting bit-widths requires recalculating statistical parameters of the norm layers, thereby impeding real-time switching of the bit-width. To overcome these challenges, we propose an efficient Post-Training Multi-bit Quantization (PTMQ) scheme that requires only a small amount of calibration data to perform block-wise reconstruction of multi-bit quantization errors. It eliminates the influence of statistical parameters by fusing norm layers, and supports real-time switching bit-widths in uniform quantization and mixed-precision quantization. To improve quantization accuracy and robustness, we propose a Multi-bit Feature Mixer technique (MFM) for fusing features of different bit-widths to enhance robustness across varying bit-widths. Moreover, we introduced the Group-wise Distillation Loss (GD-Loss) to enhance the correlation between different bit-width groups and further improve the overall performance of PTMQ. Extensive experiments demonstrate that PTMQ achieves comparable performance to existing state-of-the-art post-training quantization methods, while optimizing it speeds up by 100$\times$ compared to recent multi-bit quantization works. Code can be available at https://github.com/xuke225/PTMQ.

Neighbor discovery (ND) is a critical network initialization stage, particularly challenging for highly-dynamic unmanned aerial vehicle (UAVs) with directional antennas. Considering that directional antennas focus signal energy in one direction, successful ND requires a pair of UAVs to point antennas towards each other simultaneously. However, due to the inherent constraints of autonomous UAVs (e.g., high mobility and decentralized coordination), spatial alignment of directional beams is difficult. Existing works resort to ideal assumptions (e.g., clock synchronization, assistance of omni-directional antennas and prior information) for simplification. Moreover, previous ND algorithms assume unlimited switching capability for directional antennas, often unrealistic for traditional mechanically steered antennas. In this paper, we proposeSkyOrbs, a fast directional ND algorithm for UAV networks without these ideal assumptions. To reduce ND latency,SkyOrbspresents a skip scanning strategy, dynamically adjusting antenna rotation speed to enhance discovery probability. Furthermore, to mitigate the uncertain rotation overhead induced by time-variant angular speed,SkyOrbsdesigns a novel antenna scanning path that accommodates limited mechanical rotation capacity. We analyze the theoretical delay performance ofSkyOrbs, and expand its applicability to broader scenarios. Evaluation results show thatSkyOrbscan reduce discovery latency by 40.8% and rotation overhead by 55.0% compared to the baseline method.

Unmanned Aerial Vehicles (UAVs) exhibit great advantages in data collection from ground sensors in vast tracts of fields. Due to their limited power supply, most works assume that the UAV simply traverses each sensor’s fixed transmission range to collect data, thereby shortening the flight path. However, they neglect the quality of collected data, which may deteriorate dramatically as the transmission distance increases. In this paper, by leveraging the physical-layer protocol – LoRa, we propose a Packet Reception Ratio (PRR)-based probabilistic coverage model to evaluate the quality of data transmission, which directly determines the data acquisition efficiency. On this basis, to minimize the energy consumption of UAV and sensors while ensuring high-quality data acquisition, we formulate the UAV trajectory planning as a joint Energy Consumption and data Acquisition Efficiency (ECAE) optimization problem. To tackle the ECAE problem, we propose a Deep Reinforcement Learning (DRL)-based two-stage scheme. First, an attention-based encoder-decoder model is trained to generate an initial trajectory. Then an intuitive optimization algorithm is devised to further explore the optimal trajectory. Evaluation results show that our scheme can reduce the total energy cost of UAV and sensors by 27.1% as compared to the best baseline’s policy while maintaining a promising PRR.

As the requirements of different application scenarios vary, numerous blockchains have been developed. Among them, chains using Byzantine Fault Tolerance consensus (BFT chains for short) occupy a dominant position. Performance modeling is the most common method for guiding chain design and configuration. However, many lack specific models due to the large number of BFT chains. Providing a general framework for them is promising and should demonstrate two important features that BFT chains may differ in: different consensus stages and different packaging rules. This paper is the first to propose a general framework applicable to various BFT chains. We use the bulk-service model in queuing theory to reflect the above two features of various BFT chains and provide calculation methods for them. We give an expression for the confirmation delay of transactions (TXs for short) in the chain and verify it through experiments on various BFT chains. We also use the model for a brief analysis to assist designers in configuring and designing BFT chains.

With the emergence of various application scenarios, various chains have been developed to meet their requirements. Among them, chains with fixed block intervals (fixed chains for short) occupy an increasingly significant position. Performance has always been a key bottleneck of blockchains and modeling for them is the most common method for performance analysis. But til now, few models for fixed chains exist and they are not precise and applicable enough. This paper proposes a model for fixed chains via the bulk-service queuing theory, which can reflect the real scenario more precisely and apply to the high load. We consider the continuous time and the transaction (TX for short) pool with limited capacity and reflect the chains’ features of fixed intervals and empty blocks to improve accuracy and applicability. We give an expression for three significant measurements: the average confirmation delay of TXs, the blockchain throughput, and the TX rejection rate. We use Ethereum to validate our model. And moreover, we use the model for analysis to assist designers in operating chains.

Industrial cognitive radio sensor networks (ICRSNs) extend channel resources by occupying the vacant licensed channels in the absence of licensed users. In ICRSNs, industrial devices should switch to a common available channel to set up a communication link. However, channel switching leads to severe energy consumption. As the energy resources of battery-powered industrial devices are limited, it is crucial to carefully allocate channels to prolong the network lifetime of multi-hop ICRSNs. This paper is the first work that studies the channel allocation problem to optimize the network lifetime by considering the channel-switching (CS) energy consumption and the time-critical requirements of industrial applications. The problem is formulated to maximize the minimum residual energy at each round of data transmission, which is linearized as integer linear programming. As the channel allocation results will affect the residual energy at subsequent rounds, we propose a switching distance-optimized channel allocation (SDOCA) scheme that shortens the CS distances to improve the residual energy of each device. Moreover, we analyze the characteristics of SDOCA, i.e., convergent CS distance and guaranteed end-to-end delay. Extensive simulation results show that SDOCA can adaptively allocate channels according to the end-to-end delay requirement and significantly prolong the network lifetime.

Consensus algorithm is the core component of consortium blockchains. Equality, Unpredictability and Scalability are three important demands for the consensus algorithms of consortium blockchain. Existing deterministic consensus algorithms (e.g. PBFT) can ensure Equality, but cannot meanwhile meet Unpredictability and Scalability; probabilistic consensus algorithms (e.g. PoW) can achieve Scalability and guarantee a decent Unpredictability, but cannot meet the Equality requirement. In this paper, we propose a new consensus algorithm, namely Themis, which takes the three properties into account. Themis independently adjusts the block-producing difficulty of each node through a self-adaptive node election mechanism, effectively reducing the correlation between the block-producing frequency and the invested computing power of each node. Besides, a GEOST main chain consensus rule is proposed to handle forks and further improve the performance of the algorithm. If a fork occurs, consensus nodes will choose the sub-chain with the highest Equality to join the main chain. Evaluations show that Themis achieves outstanding performance in Equality and Unpredictability while ensuring Scalability, compared with the existing algorithms.

Hashed Timelock Contract (HTLC) is a widely-used protocol for cross-chain asset swaps. However, it relies on serial asset-locking to guarantee atomicity, which causes high latency and poor fairness. Aiming at the drawbacks of HTLC, we propose Lilac, a cross-chain asset swap protocol that supports parallel asset-locking. Lilac replaces the unique asset-unlocking credential in HTLC with multiple sub-credentials generated by all participating users, and the sequence of sub-credentials is used as the complete asset-unlocking credential. Users obtain the complete credential only when all assets have been locked, and the credential construction process is independent of the order in which assets are locked, so atomicity can be guaranteed when users lock their assets in parallel. Experiments show when a swap involves 2 to 4 blockchains, Lilac reduces the swap latency by 36.75% to 62.20%. Moreover, Lilac reduces the waiting time gap between different users so the fairness of a swap is improved.

In cognitive radio networks (CRNs), due to the external interference from primary users, secondary users (SUs) cannot reserve a common control channel (CCC). Hence, it is essential to consider the impact of channel rendezvous on the end-to-end delay in multi-hop CRNs. For this reason, we propose a High Probabilistic Transmission Efficiency Multi-hop Routing (HPTEMR) protocol without utilizing a CCC. In HPTEMR, we design an efficient waiting channel hopping sequence to achieve fast channel rendezvous between neighborhood SUs. We then propose a novel link metric, i.e., transmission efficiency, which characterizes the transmission distance and channel-rendezvous delay. Based on the link metric, a sender SU transmits data packets to the receiver SU with the highest probability that data packets can be forwarded to the destination SU with the shortest end-to-end delay. Evaluation results verify the effectiveness of HPTEMR and show its superiority in end-to-end delay and ratio of effective packets.

With the increasing demands for data, the subscription scheme came into being in the face of pricing for an extensive and unfixed number of data items. However, in the existing subscription scheme, a diversity of customers in the real market may lead to the lack of stability, which means risking the failure of pricing. Additionally, the study involves arbitrage-free, an essential economics concept, which is not reasonable on data items. To address these problems, this paper provides insights for designing an improved subscription scheme that includes two components: the calculation and the specific validity. On the one hand, the calculation improves the existing scheme by building a new structure that combines different customers' behaviours instead of the separated calculation in the existing scheme, and can steadily set prices for subscriptions to maximise the sellers' profit even in a real market. On the other hand, the specific validity shows the improvement towards arbitrage-free by taking the characteristics of data subscriptions into account. In other words, the specific validity endows the scheme with more rationality.

Full-duplex (FD) wireless is an attractive PHY technology with high potential to improve the throughput of WLAN due to bidirectional transmissions. However, existing FD MACs fail to fully take advantage of bidirectional transmissions because of neglecting a feature of FD wireless that whether to build bidirectional transmissions relies on the queuing state of peers. In this paper, we design PQ-MAC, the first FD MAC which exploits more bidirectional transmission opportunities by leveraging peers' queuing information. Since PQ-MAC seizes the neglected but important feature, PQ-MAC can improve the performance with a slight transmission overhead. Simulations show that, in a 1-cell FD WLAN, PQ-MAC can achieve higher throughput than existing MACs when the buffer of AP is relatively small (≤200 frames). When the buffer of AP is relatively large (>200 frames), PQ-MAC can reduce the queuing delay without the loss of throughput.

As it is difficult for power-restricted wireless sensor nodes to achieve rapid neighbor discovery under the scenarios of asynchronous clocks, misaligned time slots, and asymmetric duty-cycle (i.e., wake-up/sleep) scheduling periods, we propose a low-power neighbor discovery algorithm termed Pharos by alternately utilizing the fully and the partially awake time slots. The partially awake time slots of one node are certain to detect the counterpart's awake slots while reducing the power consumption as compared to the fully awake time slots. We analyze the theoretical neighbor discovery latency and derive the optimal parameters for both symmetric and asymmetric duty-cycle schedules. We also verify the effectiveness of the Pharos algorithm through extensive simulations. Evaluation results display that Pharos costs much less discovery latency and power than the state-of-the-art neighbor discovery algorithms.

In distributed Internet of Things (IoTs), channel hopping (CH) is an effective scheme for neighbor nodes to achieve blind rendezvous over common available channels and to establish communication links. When nodes are unaware of each other's local clocks and the global channels and have no pre-assigned CH strategies or identifiers (IDs), it is particularly challenging to guarantee blind rendezvous within a finite period of time, which has not been solved yet by using only one radio. In this paper, we propose a novel quaternary-encoding-based CH (QECH) algorithm to tackle the above issue. The QECH algorithm encodes a randomly selected channel into a quaternary string according to the 6B/8B encoding. We also append a common prefix string as well as the randomly selected channel before the quaternary string to guarantee overlaps in the asynchronous scenario. For all kinds of quaternary digits, we construct four mutually co-prime numbers to enumerate all possible combinations of the common available channels. We theoretically analyze the deterministic rendezvous principle and the upper bounded rendezvous latency of the QECH algorithm. We also verify the effectiveness of the QECH algorithm through extensive simulations. Evaluation results show the superiority of the QECH algorithm in terms of rendezvous latency.

In today's society, there are plenty of services available, and customers are facing bigger challenge in choosing them than ever before. Therefore, it is important to build a reliable reputation mechanism for selecting a credible service. To address the challenges of reputation evaluation, including the diverse and dynamic natures of services, incompleteness of user feedback, and intricacy of malicious ratings, a High-reliability Multi-faceted Reputation evaluation mechanism for online services (HMRep) is proposed. First, HMRep starts with addressing the incomplete feedback and estimates missing ratings based on both the service quality and a user's rating behavior. Second, HMRep identifies and removes malicious collusive raters and irresponsible raters to improve the accuracy of reputation calculation. Further, the reputation calculation is based on the user credibility and incorporates historical information to reflect the change of the services. Finally, we provide a multi-faceted evaluation method to satisfy some specific needs of customers who are only concerned about a subset of a services features. Experimental results verify the design of HMRep, and reveal HMRep can effectively defend against malicious ratings, and accurately calculate the reputation values of services. HMRep can be applied in lots of sectors for different kinds of services, especially those complex ones.

Channel qualities between UAVs vary drastically due to the mobility of UAVs. Conventional channel coding relies on channel state information (CSI) estimation and active bit rate selection and thus cannot adapt well to such varying channel conditions. In contrast, rateless codes can achieve almost optimal bit rate under varying channel conditions without CSI estimation and explicit rate selection. In rateless codes, Spinal codes are one of the most prominent solutions and perform much better than other rateless codes over the mobile fading channel between UAVs. However, Spinal codes still face the challenge of error accumulation effect, which largely hurts the transmission efficiency. In this paper, we for the first time analyze the error accumulation effect and its impact on the performance of Spinal codes under mobile fading channel conditions between UAVs. Furthermore, we propose a model for helping the decoder estimate the quality of each received symbol. Based on such model, trust function based Spinal codes (TFSC) are then proposed. Its main idea is to treat received symbols differently according to their qualities so that those symbols with better qualities can contribute more to the decoding process. Simulation results demonstrate that TFSC can significantly mitigate the error accumulation effect and improve the efficiency of Spinal codes, which achieves 1.1x to 4.4x overall performance improvement when compared with Spinal codes over the mobile fading channel between UAVs.

Neighbor discovery is a significant communication primitive for adjacent unmanned aerial vehicles (UAVs) to construct a flying ad hoc network (FANET). The multi-channel nature of FANETs makes channel hopping (CH) a feasible rendezvous method for UAVs to hop to the same available channel simultaneously and initiate a connection. However, due to the intrinsic uncoordinated constraints of dispersed UAVs (e.g., lack of clock synchronization, heterogeneous local channels, symmetric roles, and oblivious identifiers), it is challenging to design a performant CH algorithm that can achieve fast neighbor discovery in dynamic FANETs. In this paper, we present a fully uncoordinated matrix-based CH algorithm termed ABIO, which consists of one fixed Anchor column and several variable Binary (i.e., I/O-bit) extended columns in each CH period. The deterministic overlaps as well as the co-primality property of channel numbers among different kinds of columns provide the rendezvous guarantee. Furthermore, for the case with frequently varying channel status, we present a probability-based dynamic discovery (PDD) algorithm. By virtue of the cumulative probability estimation and selection of the qualified channels, the PDD algorithm can achieve timely rendezvous in the unstable environment with high probability. We rigorously analyze the theoretical neighbor discovery latency. We also validate the feasibility and efficiency of the proposed algorithms through extensive simulations. Evaluation results demonstrate the superiority of our algorithms in both stable and unstable communication environments.

Resource isolation of the computation and storage in the cloud is relatively mature, but the network resource is still shared among tenants leading to variable and unpredictable network performance when bandwidth guarantees are not enforced. Currently most of the bandwidth guarantee approaches are based on the idea of single-path reservation without fully exploiting the multipath resource, which leads to poor network utilization. In this paper, we propose a multi-path bandwidth guarantee approach called MultiBand, which provides bandwidth guarantees by allocating bandwidth across multiple paths. We utilize label-based routing technique to explicitly control the packets' transmission paths, and design a MHTB rate limiter model to split and schedule the traffic over the multiple reserved paths. Besides, Our Multiband solution has the work-conserving property. We evaluated our approach through simulations with realistic topologies and typical traffic patterns. Our results show that MultiBand is able to provide multipath bandwidth guarantees and to achieve higher network utility and tenant throughput compared with those of current approaches.

Resource competition and conflicts in datacenter networks (DCNs) are frequent and intense. They become inevitable when mixing elephant and mice flows on shared transmission paths, resulting in arbitration between throughput and latency and performance degradation. We propose a novel flow scheduling scheme, Freeway, that leverages on path diversity in the DCN topology to guarantee, simultaneously, mice flow completion within deadline and high network utilization. Freeway adaptively partitions the available paths into low latency and high throughput paths and provides different transmission services for each category. A M/G/1-based model is developed to theoretically obtain the highest value of average delay over the path that will guarantee for 99% of mice flows their completion time before the deadline. Based on this bound, Freeway proposes a dynamic path partitioning algorithm to adjust dynamically with varying traffic load the number of low latency and high throughput paths. While mice flows are transmitted over low latency paths using a simple equal cost multiple path (ECMP) scheduling, Freeway load balances elephant flows on different high-throughput paths. We evaluate Freeway in a series of simulation on a large scale topology and use real traces. Our evaluation results show that Freeway significantly reduces the mice flows completion time within deadlines, while achieving remarkable throughput compared with current schemes. It is remarkable that Freeway does not need any change of DCN switch fabrics or scheduling algorithms and can be deployed easily on any generic datacenter network with switches implementing VLANs and trunking.

Commercial advertisement dissemination is one of the most promising applications in self-organizing mobile social networks (SMSN). Lightweight incentives are essential to encourage the participation of mobile users, given that only a few users are voluntary due to limited resources in mobiles. However, existing incentives overlook dishonest behaviors of relays in overstating their costs for higher payments, which in turn can reduce the revenues and utilities of disseminators. To this end, we design a sealed-auction-based incentive named DIBS. Effective algorithms utilizing lightweight information in DIBS encourage users to provide truthful information and to spread ads in differential places, where competition is less as fewer users carry the same ads in the same areas. Moreover, we prove that DIBS possesses attractive properties theoretically for auction-based incentives, i.e., lightweight, truthfulness and individual rationality. Extensive simulation results on both real and synthetic traces verify that DIBS can improve revenues and utilities of disseminators, and achieve efficient ad dissemination.

As a promising architectural design for future Internet, named data networking (NDN) relies on in-network caching to efficiently deliver name-based content. However, the in-network caching is vulnerable to cache pollution attacks (CPA), which can reduce cache hits by violating cache locality and significantly degrade the overall performance of NDN. To defend against CPA attacks, the most effective way is to first detect the attacks and then throttle them. Since the CPA attack itself has already imposed a huge burden on victims, to avoid exhausting the remaining resources on the victims for detection purpose, we expect a lightweight detection solution. We thus propose ELDA, an Efficient and Lightweight Detection scheme against cache pollution Attacks, in which we design a Lightweight Flajolet-Martin (LFM) sketch to monitor the interest traffic. Our analysis and simulations demonstrate that, by consuming a few computation and memory resources, ELDA can effectively and efficiently detect CPA attacks.

Poor scalability is a long standing problem in multi-user MIMO (MU-MIMO) networks: in order to select concurrent uplink users with strong channel orthogonality and thus high total capacity, channel state information (CSI) feedback from users is required. However, when the user population is large, the overhead from CSI feedback can easily overwhelm the actual channel time spent on data transmission. Moreover, due to spontaneous uplink traffic, uplink user selection cannot rely on the access point's central assignment and needs a distributed realization instead, which makes the problem even more challenging.

In virtualized data centers, live virtual machine (VM) migration can increase energy efficiency by consolidating VMs on fewer servers. This problem is usually considered as Bin Packing Problem with the server capacity constraints, such as CPU, memory and network bandwidth. In order to minimize the communication traffic in data center network, existing works proposed correlation-aware VM consolidation algorithms. VMs with high inter traffic will be consolidated as close as possible (e.g. Within a physical server). However, the traffic load of virtual switches causes a certain number of CPU cycles of physical servers to move traffic through virtual switches. This increases the risk that VMs running on servers are not allocated enough resource, and consequently reduces VMs' performance. In this work, we conduct experiments to estimate the server CPU overhead caused by virtual switching, and based on the experiment results, we propose virtual-switching-aware VM consolidation algorithm to solve this problem. Experiments on representative data center workloads show that the overhead can occupy 10% to 30% of server's CPU resources. Besides, our algorithm has a sharp decrease of the server capacity violation probability compared with the state-of-the-art baseline.

Cooperative content offloading is a promising technology to lessen heavy burden of wireless networks and improve the quality of downloading services. Since few users are voluntary in providing free assistance, auction-based incentive mechanisms are designed to encourage participation. In existing auction-based incentive mechanisms, each provider only acts as a service seller. However, a provider could also be a partner of the requestor if having interest in the requested content. This dual identity of the provider can improve the quality of its service and cut down the payment of requestor. Based on this observation, we propose an auction-based incentive mechanism named CADRE. To the best of our knowledge, CADRE is the first auction-based incentive mechanism that considers the provider's dual identity in cooperative content offloading applications. We prove that CADRE possesses attractive characteristics, i.e., truthfulness, lightweight and privacy protection. Besides, we also demonstrate that CADRE outperforms the traditional multi-attribute second-score sealed reverse auction. Our simulation results verify the theoretical analysis.

Information-centric networking (ICN) is designed to decouple contents from hosts at the network layer, using in-network caching as a key feature to improve the overall performance. However, the en-route caching strategy used in many ICN implementations generally yields redundancies in the cached contents across different routers. There are also some recent works focusing on cache optimization by respectively exploiting either application layer or network layer, which we think is not sufficient to increase cache hit rate and reduce traffic. In this paper, we propose a novel caching scheme (CRCache) that utilizes a cross-layer design to cache contents in a few selected routers based on the correlation of content popularity and the network topology. Specifically, through exploiting information available at both application and network layers, CRCache aims to improve the cache hit rate and reduce the overall network traffic. We conduct a large scale and real traces-driven simulation with an underlying real Internet topology in China, and show that by using CRCache, the overall cache hit rate is increased by 62.5% and network traffic reduction is improved by at least 42% compared with recent single layer schemes.

We consider the problem of online dynamic channel accessing in multi-hop cognitive radio networks. Previous works on online dynamic channel accessing mainly focus on single-hop networks that assume complete conflicts among all secondary users. In the multi-hop multi-channel network settings studied here, there is more general competition among different communication pairs. A simple application of models for single-hop case to multi-hop case with N nodes and M channels leads to exponential time/space complexity O (MN), and poor theoretical guarantee on throughput performance. We thus novelly formulate the problem as a linearly combinatorial multi-armed bandits (MAB) problem that involves a maximum weighted independent set (MWIS) problem with unknown weights. To efficiently address the problem, we propose a distributed channel access algorithm that can achieve 1/ρ of the optimum averaged throughput where each node has communication complexity O (r2+D) and space complexity O (m) in the learning process, and time complexity O (D mρr) in strategy decision process for an arbitrary wireless network. Here ρ = 1 + ε is the approximation ratio to MWIS for a local r-hop network with m <; N nodes, and D is the number of mini-rounds inside each round of strategy decision.

The network resource competition of today' data enters is extremely intense between long-lived elephant flows and latency-sensitive mice flows. Achieving both goals of high throughput and low latency respectively for the two types of flows requires compromise, which recent research has not successfully solved mainly due to the transfer of elephant and mice flows on shared links without any differentiation. However, current data enters usually adopt clos-based topology, e.g. Fat-tree/VL2, so there exist multiple shortest paths between any pair of source and destination. In this paper, we leverage on this observation to propose a flow scheduling scheme, Freeway, to adaptively partition the transmission paths into low latency paths and high throughput paths respectively for the two types of flows. An algorithm is proposed to dynamically adjust the number of the two types of paths according to the real-time traffic. And based on these separated transmission paths, we propose different flow type-specific scheduling and forwarding methods to make full utilization of the bandwidth. Our simulation results show that Freeway significantly reduces the delay of mice flow by 85.8% and achieves 9.2% higher throughput compared with Hedera.

Peer-to-peer (P2P) systems are imposing a heavy burden on internet services providers (ISPs). P2P caching is an effective way of easing this burden. We focus on the cache deployment problem as it has a significant impact on the effectiveness of caching. An ISP backbone network is usually abstracted to a graph comprising nodes representing core routers and links connecting adjacent core routers. While deploying P2P caches at nodes (NCD, node-based cache deployment) can reduce the amount of P2P traffic transmitted from access networks to the ISP backbone network, deploying P2P caches on links (LCD, link-based cache deployment) can directly reduce the amount of P2P traffic on the ISP backbone network. However, neither NCD nor LCD maximizes the performance of P2P caches. In this paper, we propose a node-link-based cache deployment method (NLCD), which optimally selects nodes or links as deployment locations during the cache deployment process. First, we propose an analysis model and define an optimal cache deployment problem for NLCD. Then, we prove that this problem is NP complete and develop a corresponding deployment algorithm. Experimental results show that the average link utilization of NLCD is 5–15% lower than that of LCD, and 7–30% lower than that of NCD.

In mobile ad-hoc cognitive radio networks (CRNs), end-to-end paths with available spectrum bands for secondary users may exist temporarily, or may never exist, due to the dynamism of the primary user activities. Traditional CRN routing algorithms, which typically ignore the intermittent connectivity of network topology, and traditional mobility-assisted routing algorithms, which generally overlook the spectrum availability, are obviously unsuitable. To tackle this challenge, we propose a Mobility-Assisted Routing algorithm with Spectrum Awareness (MARSA) to select relays based on not only the probability that a node meets the destination but also the chance at which there exists at least one available channel when they meet. To the best of our knowledge, this paper is the first to bring the idea of mobility-assisted routing to deal with the intermittently connected attribute of mobile ad-hoc CRNs, and the first to enhance the mobility-assisted routing by considering the temporal , spatial, and spectrum domains at the same time. Our simulation results demonstrate the superiority of MARSA over traditional algorithms in intermittently connected mobile CRNs.

We study throughput-optimum localized link scheduling in wireless networks. The majority of results on link scheduling assume binary interference models that simplify interference constraints in actual wireless communication. While the physical interference model reflects the physical reality more precisely, the problem becomes notoriously harder under the physical interference model. There have been just a few existing results on link scheduling under the physical interference model, and even fewer on more practical distributed or localized scheduling. In this paper, we tackle the challenges of localized link scheduling posed by the complex physical interference constraints. By integrating the partition and shifting strategies into the pick-and-compare scheme, we present a class of localized scheduling algorithms with provable throughput guarantee subject to physical interference constraints. The algorithm in the oblivious power setting is the first localized algorithm that achieves at least a constant fraction of the optimal capacity region subject to physical interference constraints. The algorithm in the uniform power setting is the first localized algorithm with a logarithmic approximation ratio to the optimal solution. Our extensive simulation results demonstrate performance efficiency of our algorithms.

As video applications are increasingly popular over smartphones, many cooperative video streaming mechanisms have been proposed. These mechanisms use cellular link as well device-to-device links simultaneously to provide higher quality video streaming to mobile users. However current works solely focus on throughput enhancement in static scenarios. Consequently these mechanisms result in unfairness since smartphones with higher download rate expend more cellular traffic and monetary costs. Additionally, previous works assume a static scenario that all smartpone users start to watch the same video at the same time. Obviously, the static scenario is unrealistic in actual mobile environments. Based on these insights, in this paper, we focus on a more practical dynamic cooperation scenario and propose a scheduling scheme to achieve efficient cooperative video streaming and guarantee fluent user experience. More importantly, the proposed scheduling scheme achieves a significant improvement in fairness among cooperators. Through extensive simulations across a wide range of scenarios, we show that the proposed scheme significantly outperforms other works by 52%, 24% and 27% respectively in terms of fairness, without sacrificing efficiency.

P2P live streaming systems have been widely adopted nowadays. In such systems, flash crowds still remains a big challenge, which often occur when an enormous number of users suddenly arrive to view a newly released program. In a flash crowd scenario, users often suffer from a long startup delay and a high failure rate. In this paper, we propose a topology-construction-based algorithm to alleviate the flash crowd. Specifically, first the tracker server constructs a multiple tree topology with total new peers. Then according to the topology, all new peers join the current P2P system in form of multiple trees. When constructing the topology, the tracker server puts new peers with higher bandwidth and longer waiting time more closer to the root in each tree, in order to reduce the average waiting time of new peers. Moreover, a new analytical model is also devised to evaluate our algorithm. Model analysis and simulation indicate that our method can enhance the joining process of new peers and improve their startup delay and failure rate.

Mobile P2P networking is an enabling technology for mobile devices to self-organize in an unstructured style and communicate in a peer-to-peer fashion. Due to user mobility and/or the unrestricted switching on/off of the mobile devices, links are intermittently connected and end-to-end paths may not exist, causing routing a very challenging problem. Moreover, the limited wireless spectrum and device resources together with the rapidly growing number of portable devices and amount of transmitted data make routing even harder. To tackle these challenges, the routing algorithms must be scalable, distributed, and light-weighted. Nevertheless, existing approaches usually cannot simultaneously satisfy all these three requirements. In this paper, we propose two opportunistic routing algorithms for intermittently connected mobile P2P networks, which exploit the spatial locality, spatial regularity, and activity heterogeneity of human mobility to select relays. The first algorithm employs a depth-search approach to diffuse the data towards the destination. The second one adopts a depth-width-search approach in a sense that it diffuses the data not only towards the destination but also to other directions determined by the actively moving nodes (activists) to find better relays. We perform both theoretical analysis as well as a comparison based simulation study. Our results obtained from both the synthetic data and the real world traces reveal that the proposed algorithms outperform the state-of-the-art in terms of delivery latency and delivery ratio.

In recent years, virtualization technologies are applied to data centers for resource sharing. Virtual Machine Monitor (VMM) can consolidate virtual machines (VMs) running on multiple physical servers onto a single one via live VM migration, consequently improving energy efficiency of data centers. VM consolidation is usually modeled as a bin packing problem aiming at minimizing the number of servers being used. However, resource consumption overhead of consolidating VMs is seldom considered in existing approaches. In this paper, the overhead is defined as the resource consumption difference between the server and all the VMs running on it. We theoretically and experimentally prove that under the realistic constrains, this overhead exists and remains steady with the increasing of consolidating VMs. We also propose Margin Reserved Consolidation (MRC) algorithm to supplement existing works. Besides, we conduct experiments to validate the overhead. Experiments based on a representative benchmark show that 11.7% of the server's CPU resource is occupied by the overhead averagely.

People's growing dependency on the Internet makes them want to access the network anytime and anywhere, even while driving cars. Although 3G or 4G networks can be used to achieve this goal, roadside APs have the advantages of low cost and high bandwidth. At present, however, APs cannot cover all the areas, which cause intermittent connectivity. In this paper, we propose the DSRelay, a scheme of cooperative downloading. Unlike some studies that multiple cars download files from the Internet and different cars deliver different blocks of files like a P2P network, our work concentrates on the request of downloading respectively. Making use of the characters of the limited communication range of WIFI network, DSRelay schedules the Dark Areas (DA) out of AP coverage areas. If a mobile client leaves an AP coverage area without finishing its downloading, using the proposed scheme, APs calculate meeting time and communication duration between client car and other registered cars, and choose a series of cars to carry data client needed so that the data can be transmitted to it at different slot in DA. Also, we analyze the influence of change of car speed and a corresponding solution is presented. This scheme utilizes DAs for extending the downloading areas of the client as much as possible. Simulation results indicate the benefits of the proposed scheme in terms of increasing throughput and reducing delay.

Peer-to-Peer (P2P) live streaming systems are becoming popular and are imposing a heavy burden on Internet Services Providers (ISPs). Proxy caching has been shown to be an effective means of reducing operation costs for ISPs. Although many caching algorithms for conventional web applications and P2P file sharing systems have been proposed and deployed, there have been few works on the caching for P2P live streaming. Data requests in P2P live streaming have distinct characteristics; for example, they are concentrated in a limited window which progresses rapidly with time in a monotonic mode. In this paper, we propose a novel caching algorithm for P2P live streaming called Lazy Caching (LC), which is designed based on the characteristics of P2P live streaming. In LC, data requests that encounter cache misses are stored in a Request Buffer (RB) that is processed periodically. LC can better utilize the cache space than traditional caching algorithms at the cost of introducing a response latency which is at most one RB processing period. Experimental results show that the hit ratio of LC, at a processing period of 0.5 second, can be as much as 20 percent higher than that of SLW, and 9 percent higher than that of OPT. We believe that it is worthwhile to achieve this higher hit ratio at the cost of a small response latency increase.

Existing multipath routing protocols for MANET ignore the topology-exposure problem. This paper analyzes the threat of topology-exposure and proposes a Topology-Hiding Multipath Routing protocol (THMR). THMR doesn't allow packets to carry routing information, so malicious nodes cannot deduce topology information and launch various attacks based on that. The protocol can also establish multiple node-disjoint routes in a route discovery attempt and exclude unreliable routes before transmitting packets. We formally prove that THMR is loop-free and topology-hiding. Simulation results show that our protocol has better capability of finding routes and can greatly increase the capability of delivering packets in the scenario where there are attackers at the cost of low routing overhead.

We study distributed link scheduling for throughput maximization in wireless networks. The majority of results on link scheduling assume binary interference models for simplicity. While the physical interference model reflects the physical reality more precisely, the problem becomes notoriously harder under the physical interference model. There have been just a few existing results on centralized link scheduling under the physical interference model, though distributed schedulings are more practical. In this paper, by leveraging the partition and shifting strategies and the pick-and-compare scheme, we present the first distributed link scheduling algorithm that can achieve a constant fraction of the optimal capacity region subject to physical interference constraints in the linear power setting for multihop wireless networks.

P2P live streaming systems have been widely adopted nowadays. However, the flash crowd still poses challenges in such P2P systems, which often occurs when an enormous number of users suddenly arrive to view a newly released live program. Facing so many new users, a P2P streaming system usually can not provide reasonable quality of service and these new users often suffer from a long startup delay and a high service rejection rate. In this paper, we propose a bandwidth-aware peer selection method to alleviate the flash crowd. To use the rare available bandwidths more effectively, we let new peers send more requests to the high-bandwidth parents and less requests to the low-bandwidth parents, aiming to make the upload rate of each parent match well with its upload capacity. Moreover, two analytical models are also constructed to evaluate our method and the traditional random peer selection method. Both model analysis and simulation experiment reveal the merits of our method in tackling the flash crowd, in terms of growth of system scale, average startup delay and rejection rate, compared with the random peer selection method.

Recent studies reveal that the main cause of the well-known unfairness problem in wireless networks is the ineffective coordination of CSMA-based random access due to topology asymmetry. In this paper, we take a modeling-based approach to understand and solve the unfairness problem. Compared to existing works, we advance the state of the art in two important ways. First, we propose an analytical model called the G-Model, which accurately characterizes the ineffective coordination of medium access in asymmetrical topologies. The G-Model can estimate network performance under arbitrary parameter configurations. Second, while previous works decompose a wireless network into embedded basic asymmetric topologies and study each basic topology separately, we go beyond the basic asymmetrical topology and design a model-driven optimization method called Flow Level Adjusting (FLA) to solve the unfairness problem for larger wireless networks. Through extensive simulations, we validate the proposed G-Model and show that FLA can greatly improve the overall fairness of wireless networks in which basic asymmetric topologies are embedded.

One major problem of cross-layer control algorithms in multi-hop wireless networks is that they lead to large end-to-end delays. Recently there have been many studies devoted to solving the problem to guarantee order-optimal per-flow delay. However, these approaches also bring the adverse effect of sacrificing a lot of network utility. In this paper, we solve the large-delay problem without sacrificing network utility. We take a fundamentally different approach of delay differentiation, which is based on the observation that flows in a network usually have different requirements for end-to-end delay. We propose a novel joint rate control, routing and scheduling algorithm called CLC_DD, which ensures that the flow delays are proportional to certain pre-specified delay priority parameters. By adjusting delay priority parameters, the end-to-end delays of preferential flows achieved by CLC_DD can be as small as those achieved by delay-order-optimal algorithms. In contrast to high network utility loss in previous approaches, we prove that our approach achieves maximum network utility. Furthermore, we incorporate opportunistic routing into the cross-layer design framework to improve network performance under the environment of dynamic wireless channels.

Secondary interference constraints are important, because of representing the transmission constraints of the widespread and promising IEEE 802.11 wireless technology. Under secondary interference constraints, distributed link scheduling algorithms for multihop wireless networks can only achieve a fraction of the maximum possible throughput in general, but distributed Greedy Maximal Scheduling (GMS) algorithms can achieve optimal throughput in some network graph structures. It is possibly helpful for the improvement of distributed throughput to partition a network into subnetworks such that the subnetwork assigned to each frequency channel achieves distributed throughput maximization. In this paper, we investigate the structure characteristics of the subnetwork in which GMS achieves optimal throughput under secondary-interference constraints, and define a type of network subgraph structures meeting the requirement - special chordal subgraphs. Based on this, we propose a channel assignment algorithm, including a network partitioning algorithm and a topology balancing algorithm. By simulation, we evaluate the achievable throughput and fairness in a distributed matter using our algorithm, in comparison with the existing Max K-cut based channel assignment algorithm.

Peer-to-Peer (P2P) technology has been widely adopted by various live streaming systems recently, due to its better scalability and lower costs compared with the client-server architecture. However, P2P live streaming systems are still challenged by the flash crowd scenarios, which often occur when a great number of users suddenly arrive and compete for the limited upload bandwidth of a P2P system. In this case, users are usually subject to a long startup delay and are likely to retry multiple times before leave out of impatience. Current studies mainly focus on the measurement of practical systems and model analysis on flash crowd, but there are few specific approaches so far. In this paper, we develop a capacity-aware user access control algorithm to relieve the flash crowd problem. Firstly, we control the peers to enter the system at a proper rate, which avoids too high arrival rate slowing down the increase of system scale. Secondly, to increase the system service capacity as soon as possible, we let the peers with higher capacity enter the system ahead of the peers with lower capacity. Finally, we also consider the waiting time of peers with low capacity and let them in before they lose patience. To evaluate our algorithm, a new analysis model is also proposed. Simulation experiments and model analysis reveal that our algorithm is more effective to increase the system scale, and can achieve shorter user waiting time as well as lower reject rate.

Based on energy consumption considerations, an ad hoc network node may reject other nodes' forwarding requests to save the limited battery power for its own data transmission. Therefore, a lot of incentive schemes have been proposed to promote the cooperation of the nodes. The utilization of the incentive schemes makes the nodes willing to cooperate with each other, because their non-cooperation can be punished in the future. However, the activities of the nodes in ad hoc networks have some inherent uncertainty. For example, the batteries of some nodes are exhausted or some nodes move to other regions. Under these situations, the existing incentive schemes are no longer effective and the nodes have to terminate their cooperation and stop forwarding packets for others. In this paper, we propose a power control mechanism in ad hoc networks under a dynamic repeated game-theoretic framework. A notion of nodes' evaluation levels for the future experiences is defined to take account of the non-cooperation due to the inherent uncertainty in the ad hoc network nodes' activities. The nodes achieve their optimal transmission efficiency by using a two-step power control mechanism. The simulation results show that compared with the existing schemes our power control mechanism considering non-cooperative packet forwarding improves the average transmission efficiency by approximately 25%.

Centralized WLANs widely deployed in enterprise environment or university campus often have high density of Access Point (AP). The high density leads to multi-AP diversity, which brings possibility to improve network performance. Previ ous studies have proposed different schemes to exploit multi-AP diversity, however, these schemes are all based on heuristic and cannot guarantee an optimal exploitation of multi-AP diversity. In this paper, we propose a Theory Based Centralized Scheduling (TBCS) to exploit the full potential of multi-AP diversity. TBCS is based on the well-known back-pressure scheduling. Although back-pressure scheduling is proved to be throughput-optimal, most of previous studies are purely theoretical. To make a practical use of the theoretical back-pressure scheduling, we design new mechanisms in TBCS to handle the problem caused by the wired/wireless mixed scenario of centralized WLANs and to synchronize the scheduling. We evaluate TBCS through NS 2 simulations and show that compared with previous methods, TBCS can support the largest capacity region and greatly improves the throughput of a network.

Spectrum allocation algorithms are able to improve the performance of wireless mesh networks by exploiting the frequency agility of modern radios, and several such algorithms have been proposed. However, their interference constraints are at a coarse-grained level, which results in a low spectrum efficiency. To achieve higher spectrum resource utilization, we use interference pairs as a finer granularity to model the interference constraints in wireless mesh networks, and derive a sufficient and necessary condition for interference-free spectrum allocation. Based on a set of rigorous models, we formulate spectrum allocation as an optimization problem and divide it into two subproblems, for which we propose a two-phase interference pair-based distributed spectrum allocation (IPDSA) algorithm. In IPDSA, a negotiation-based frequency hierarchy mechanism heuristically determines the relation between the center frequencies of links in each interference pair; and then a dual decomposition-based spectrum allocation algorithm converges to the optimal allocation of center frequencies and spectral widths of all links. Extensive simulation results show that IPDSA is able to significantly improve spectrum utilization and thus increase network utility and aggregate throughput, thanks to a high accuracy in modeling interference constraints.

Massive data dissemination is often disrupted by frequent join and departure or failure of client nodes in a peer-to-peer (P2P) network. We propose a new churn-resilient protocol (CRP) to assure alternating path and data proximity to accelerate the data dissemination process under network churn. The CRP enables the construction of proximity-aware P2P content delivery systems. We present new data dissemination algorithms using this proximity-aware overlay design. We simulated P2P networks up to 20,000 nodes to validate the claimed advantages. Specifically, we make four technical contributions: 1). The CRP scheme promotes proximity awareness, dynamic load balancing, and resilience to node failures and network anomalies. 2). The proximity-aware overlay network has a 28-50 percent speed gain in massive data dissemination, compared with the use of scope-flooding or epidemic tree schemes in unstructured P2P networks. 3). The CRP-enabled network requires only 1/3 of the control messages used in a large CAM-Chord network. 4) Even with 40 percent of node failures, the CRP network guarantees atomic broadcast of all data items. These results clearly demonstrate the scalability and robustness of CRP networks under churn conditions. The scheme appeals especially to web-scale applications in digital content delivery, network worm containment, and consumer relationship management over hundreds of datacenters in cloud computing services.

MIPv6 is one of the dominating protocols that enable a mobile node to maintain its connectivity to the Internet when moving from one access router to another. However, it suffers from long handoff latency and routing inefficiency. In this paper, we present a novel distributed mobility management scheme, ADA (Asymmetric Double-agents Architecture), which introduces two mobility agents to serve one end-to-end communication. One mobility agent is located close to the MN to limit the amount of MIPv6 signaling traffic outside the local domain. The other mobility agent is located close to the CN to minimize routing overheads. Quantitative analysis shows that ADA significantly outperforms the existing mobility management protocols.

In wireless mesh networks with frequency-agile radios, an algorithm of dynamically combining consecutive channels has recently been proposed. However, the available channel widths are limited in the algorithm. In order to further improve the fairness or the throughput under given fairness, we propose a joint variable width spectrum allocation and link scheduling optimization algorithm. Our algorithm is composed of time division multiple access for no interface conflict and frequency division multiple access for no signal interference. In the first phase, we use as few time slots as possible to assign at least one time slots to each radio link with Max-Min fairness. In the second phase, our design jointly allocates the lengths of time slots as well as the spectral widths and center frequencies of radio links in each time slot. Numerical results indicate that compared to the existing algorithm, our algorithm significantly increases the fairness or the throughput under given fairness.

As is known to us, the handover latency of FMIPv6 in its predictive mode is given little concerns. However our previous work [4] shows that FMIPv6 may suffer long handover latency in its predictive mode, and [4] identifies three key issues raising such problems. In this paper, we propose a practical cross-layer fast handover management mechanism (PCLF) to address these issues and improve success rate of mobility prediction. To solve the problem, PCLF includes a smart link layer trigger, a TBScan algorithm, a TBAPS algorithm, a buffering support Bi-Binding scheme and the smart link event notification policy. Experiment results show that our mechanism can achieve reasonable mobility prediction and seamless handover with no interruptions on upper layer applications (VoIP) in IEEE 802.11 WLANs. The average handover latency is less than 50ms, the success rate of mobility prediction is 97.7% and no packet loss is observed.

Multipath transfer utilizes multiple independent end-to-end paths to improve the total transmission throughput. Reliable transmission protocols as TCP and SCTP suffer resequencing delay due to asynchronous packet arrivals at the receiver as a result of packet reordering. The resequencing delay deteriorates the performance of some delay-sensitive applications. In this paper, we make an analysis of the mean resequencing delay for an average packet in a typical multipath transfer scenario. In the scenario, the path delay is assumed to be constant while distinct to each other. In consideration of path selecting probability, path delay and bandwidth, a model of the mean resequencing delay for an average packet in a long-term session is derived. The model is evaluated with the aid of SCTP CMT, which is a technically mature multipath transfer instance. It is shown that the results computed from the analytical model agree well with the output of the simulations. We expect the model can be used as a reference of resequencing delay estimation, aiding multipath transfer algorithms to get a better performance.

Most existing soft handoff approaches lead to plenty of out-of-order packets during downward vertical handoffs (VHOs). We have presented a soft VHO scheme, called SHORDER, to avoid packet reordering caused by downward VHOs. In this paper, we analyze the effects of our SHORDER scheme and another typical existing soft VHO method on the handoff latency and the received data size during a downward VHO for TCP applications. Then, we approximately derive the applicable conditions of the two approaches, and further propose a diagnosis-based soft vertical handoff (DSVH) mechanism which can self-adaptively deal with reordering packets. The mechanism has practical advantages of no changes to correspondent nodes and compatibility with various enhanced TCP variants. With numerical analysis and test-bed experiments, we show that the DSVH mechanism has better performance than the SHORDER scheme and the typical existing method. Furthermore, experimental and analytical results are consistent with each other.

Hybrid content distribution network (HCDN) makes use of the highly complementary advantages of conventional CDN (content distribution network) and pure P2P (peer-to-peer). In HCDN, clients can concurrently retrieve content from both CDN and P2P networks. In this paper, service differentiation is formulated as a constraint optimization problem, in which two critical factors are taken into consideration: quality factor of a link and demand factor of a file. With the convex optimization theory, two bandwidth allocation algorithms, HBAA-P for source peer and HBAA-S for surrogate server, are proposed and proved for service differentiation in the hybrid architecture. Some experimental results are illustrated to make sense of the performance features of our approaches.

The information of available bandwidth on an end-to-end path is important for various network applications, and several probing methods have been proposed to estimate it in recent years. However, previous methods are either based on fluid model or are only partially suitable for bursty real internet cross traffic; and the accuracy of their estimation degrades at different extents in multi-hop situations. Moreover, all previous PGM (Probing Gap Model) based methods require the knowledge of bottleneck link capacity, which may not be available in practice. In this paper, we extend the analysis of queuing behavior of probing packets from single-hop scenarios to multi-hop scenarios and propose a novel hybrid probing technique, called PATHCOS++, which integrates the advantages of both PRM (Probing Rate Model) and PGM based methods, to estimate the end-to-end available bandwidth. Unlike previous works, PATHCOS++ does not make fluid cross traffic assumption and does not require the information about bottleneck link capacity. Simulation results show that PATHCOS++ is quite efficient and provides end-to-end available bandwidth estimation that is significantly more accurate than current state-of-the-art techniques do. The accuracy of PATHCOS++ is nearly unaffected when there are multiple congestible links.

Experiments show that FMIPv6 may suffer long handover latency even in the predictive mode in the real IEEE 802.11 based WLANs. To figure out the latency reason and identify potential enhancement of FMIPv6, we analyze the handover latency of the predictive FMIPv6 from a cross layer perspective using data collected in a real IEEE 802.11 test-bed. We find that the key issues affecting the handover latency of the predictive FMIPv6 in IEEE 802.11 WLANs are the lack of assistance from the network entities, the ambiguous link layer triggering time and the inefficient interaction between the link layer and the network layer. And FMIPv6 can provide fast handover with no interruptions on the upper layer applications in IEEE 802.11 WLANs through some enhancements, which can resolve the above three issues.

The Hybrid CDN-P2P architecture, or HCDN, which combines the complementary advantages of CDN and P2P networks, has been proposed to reduce the deployment cost and to improve the quality of service in file sharing and video streaming applications. A replica placement algorithm (RPA) decides where to replicate the specific data. Existing RPAs for pure CDN do not work efficiently in the HCDN architecture because they do not take into consideration the contribution of the peers at the P2P distribution level. In this article, a heuristic RPA that takes into account the effects of P2P distribution is proposed for HCDN. The performance of our proposed algorithm is evaluated and the impact of some key metrics is analyzed. The experimental result shows the clear performance benefits of our approach.

Many RSS-based vertical handoff algorithms have recently been proposed. However, there are only a few models to evaluate the performance of vertical handoff algorithms and none of the existing models reflect the effect of a doorway on received signal strength (RSS). Considering that RSS from heterogeneous networks cannot be directly compared with each other, we firstly present an effective method to compare RSS of different networks, based on the corresponding bandwidth in each network. Then, we take into account signal abrupt attenuation near a doorway and construct a novel performance evaluation model for RSS-based vertical handoff algorithms. This model also reflects the correlation between RSS at two adjacent locations in a WLAN. Following that, we propose an integrative performance evaluation function based on two metrics - the decision delay and the number of handoffs. Furthermore, we analyze hysteresis and dwell-timer algorithms with our model. The results show a good match between simulation and analysis.

Existing soft handoff techniques lead to plenty of out-of- sequence packets during downward vertical handoffs (DVHOs). In this paper, we present two new network-layer soft vertical handoff schemes, called SHORDER and E-SHORDER. The former can prevent mobile nodes from receiving reordered packets during DVHOs with a low overhead. The latter further hinders their correspondent nodes from receiving out-of-order packets caused by mobile nodes' DVHOs. Then, we analyze the performance of our proposed approaches. By experiments, we show that they have a good effect in practice.

In P2P multicast applications, membership management protocols are the basic utilities. In this context, gossip-based protocols have emerged as attractive ones for that they are highly reliable, scalable and simple. Existing gossip-based membership protocols either ignore the underlying topology and the heterogeneity nature of peer nodes or consume lots of control overhead. In this paper, first, we present a modified scalable membership protocol, MSCAMP, to account for node heterogeneity. Then a DHT-aid, gossip-based heterogeneous peer-to-peer membership protocol, called DIGOM, is proposed. DIGOM groups nearby nodes into clusters and takes advantage of MSCAMP as an intra-cluster membership protocol. A DHT structure is built to aid node subscription and inter-cluster link building. From the theoretical analysis and simulation results, both the inter-and intra-cluster fanout in DIGOM can satisfy the requirements for reliable dissemination. Specially, DIGOM achieves a good quality of load balance and requires no synchronization.

Trust relationship among multiple domains is the basis for inter-domain fast authentication. This paper proposes a fast authentication method combining inter-domain trust relationship for wireless mobile IPv6 networks. In order to implement inter-domain trust relationship, a dynamic trust maintenance mechanism is designed. Based on Combined Public Key (CPK) algorithm, a new signature and verification scheme is applied to accelerate the authentication process. This scheme supports the proposed trust-based mutual authentication between mobile node and the access network. Theoretical analysis and numerical results show that the proposed method is more effective in reducing authentication delay and signaling overhead. Additionally, the proposed method is proven to be tolerant of existential forgery and man-in-the-middle attacks.

Multihoming feature enables stream control transmission protocol (SCTP) to be a handover and mobility scheme for mobile users in multihomed environment. However, there are two flaws deteriorating SCTP handover performance. First, the congestion control mechanism of SCTP makes entire association experience a slow-start phase after handover, thus leading to a sudden-shrink of throughput. Second, the diversity of round-trip time (RTT) between separate paths incurs packet reordering and likely to trigger the spurious fast-retransmit, which degrades performance of reliable transport, too. This paper presents SHOP: an integrated scheme for SCTP handover optimization. By means of available bandwidth estimation technologies, SHOP avoids the slow-start phase after handover through configuring proper congestion control variables of new primary path. Meanwhile, postpone-handover based on RTT measurement is put forward in SHOP to minimize the negative effects of packet reordering. Detailed simulation results show the effectiveness of proposed scheme.

Previous Probe Gap Model (PGM) based available bandwidth (AB) estimation methods all request the "busy assumption" that probing packet pairs should be in the same busy period when transmitted on bottleneck link, which is hard to satisfy especially for the low utilization path. In this paper, we first present a new probabilistic methodology to estimate AB under "non busy assumption". The methodology is quite accurate on the low utilization network path. Secondly, we propose a metric to weigh the busyness of a network path based on the distribution of output probe gap. Using the metric, we combine our new methodology and previous methodology, and present a new AB estimation method called Adaptive Available Bandwidth Estimation (A_ABE) which is fit for both low utilization and high utilization paths. We use NS-2 simulation and reproduce traffic from real Internet links to evaluate A_ABE. Compared with previous methods, A_ABE shows its advantages in terms of accuracy, overhead, and also the robustness when confronted with non-persistent cross traffic in multiple hop situations.

P2P networks are considered to be the most important development for next generation Internet infrastructure. They always consist of large numbers of cooperative but dynamic member nodes. For these system to be effective, an efficient membership protocol is critical. This paper presents RLM which mainly focuses on locality-aware membership protocol in unreliable and heterogeneous P2P systems. RLM forms member nodes in a ring-based structure. Each node has a neighbor list whose length is proportional to its capacity. Member nodes self-adaptively optimize their neighborhood relations in terms of degree and link latency. To increase robustness, each node also has a successor list that consists of successor nodes down the ring. The successor list is with length of logarithm of the system size on average. Both the neighbor list and successor list are constructed in decentralized ways. Theoretical analysis and intensive simulations have shown the effectiveness of RLM. Specially, while the fault resilience is comparable to that of SCAMP in Ganesh, A.J., et al, (2003), RLM achieves up to 54.5% latency reduction.

In this paper, a singular value decomposition based signature matrix inversion (SVD-SI) scheme is proposed for downlink in multiuser MIMO systems, which is more efficient and able to reduce the feedback overhead by limited feedback. The wireless channels are decomposed into several eigenmodes with the right singular vectors as the spatial signatures, which are quantized and fed back to the base station. Then, the operating users are selected according to their signatures, and the multiuser interference is eliminated by the signature matrix inversion scheme. Finally, we characterize the performance of SVD-SI under limited feedback, and give the recommended feedback rate under different scenarios. Numerical results show that the proposed scheme achieves significant throughput improvement while reducing the feedback overhead.

The current interdomain routing protocol (BGP) used in the Internet tends to be restrictive limiting communication between source-destination pairs to one route, which may not fully utilize the potential Internet's connection redundancy. Although overlay routing could utilize redundant communication paths between endpoints to improve reliability and performance of the Internet, the studies of overlay network still suffer two handicaps: (i) lack of accurate Internet topology model which can be used for the large-scale overlay simulation eligibly and (ii) most existing overlay systems are inefficient in choosing the relay nodes to create the disjoint overlay path. In this paper, we first present an experimental study of resilience analysis on the Chinese Internet which we obtained through a large-scale active measurement recently and contains greater connectivity than what Skitter and Routeviews have discovered. Then we propose a heuristic strategy, called Degree Rank based Overlay relays Placement (DROP) to create the redundant disjoint overlay path between each source-destination pair. Simulations show that DROP can improve the entire Chinese Internet's resilience efficiently with less topological information acquired and can be put into practice easily.

More and more emerging P2P applications require support for multi-source data dissemination. However, existing schemes on data dissemination are either only suitable for single source systems or inefficient in terms of delivery delay or message redundancy. This paper presents REM, a reliable and efficient multi-source data dissemination scheme. REM organizes member nodes in a ring-based structure which is reliable, locality-aware and heterogeneity-aware. An undirected delivery tree is built on top of the overlay and used by all nodes. Data messages are first flooded on the overlay and then delivered on the tree. Thus, REM combines the advantages of flooding-based scheme and tree-based scheme. We analyze the reliability, average hop complexity and redundancy rate theoretically and evaluate the performance by simulations. Specially, in large scale systems, compared with a randomized scheme, REM reduces the average delivery delay by about 25% while the redundancy rate is reduced from about 16% to 1%.

In MIPv6, the home agent (HA) is the key entity to ensure a mobile nodepsilas (MN) reachability. A single HA on the home link will become a performance bottleneck. In order to enhance service availability and improve system performance, it is necessary to configure multiple HAs on the home link and efficiently balance load among these HAs. This paper proposes a dynamic multiple HA load balancing mechanism based on active overload prevention (DHALAOP). The solution actively prevents HA from overloading in advance, rather than just passively transferring excess load among HAs as previous load balancing mechanisms do. A novel dynamic weight load evaluation algorithm is introduced to provide the basis for optimal load balancing decision. In addition, DHALAOP utilizes single HA mirror image and load slicing scheme to achieve the transparency of load balancing and eliminate unnecessary additional overhead. The theoretical analysis results show that DHALAOP can be more efficient in enhancing service availability and improving system performance as compared with the previous mechanisms. At the same time it introduces a lower signaling cost.

In Mobile IPv6 networks, mutual authentication between mobile users and the network guarantees security of both sides. The integration of handoff procedure and authentication procedure may affect performance of the former while improving efficiency of the later. One important issue is to improve the overall efficiency of fast authentication. Based on the Combined Public Key (CPK) algorithm, a new signature and verification scheme is designed, which has a lower computational complexity than identity-based signature (IBS) scheme. Furthermore, a fast authentication method based on this scheme is proposed to realize mutual authentication in one round-trip. Theoretical analysis and numerical results show that the proposed method is more effective in reducing total handoff and authentication delay and the signaling overhead. Security analysis shows that the method is sufficient for privacy and unforgeability.

Membership protocols are the basic utilities for P2P multicast applications. Existing membership protocols always assume a homogeneous environment or bring non-negligible overhead to optimize the overlay topology. In this paper, we propose SAP2P, a self-adaptive and locality-aware P2P membership protocol for heterogeneous systems. SAP2P periodically optimizes the overlay in terms of node degree and link latency. In SAP2P, the degrees of member nodes are proportional to their capacities and neighbors are always physically close. To reduce the control overhead, SAP2P uses landmark based scheme to evaluate link latencies and takes advantage of a Markov chain based method to adoptively vary the optimization periods. Simulation study shows that SAP2P can achieve good qualities in terms of load balancing and locality awareness with relatively smaller overhead, while it still responds quickly to node churn. Specially, compared with randomized membership protocols, SAP2P achieves up to 53.7% latency reduction.

In heterogeneous wireless networks, handoff can be separated into two parts: horizontal handoff (HHO) and vertical handoff (VHO). VHO plays an important role to fulfill seamless data transfer when mobile nodes cross wireless access networks with different link layer technologies. Current VHO algorithms mainly focus on when to trigger VHO, but neglect the problem of how to synthetically consider all currently available networks (homogeneous or heterogeneous) and choose the optimal network for HHO or VHO from all the available candidates. In this paper, we present an analytical framework to evaluate VHO algorithms. Subsequently, we extend the traditional hysteresis based and dwelling-timer based algorithms to support both VHO and HHO decisions and apply them to complex heterogeneous wireless environments. We refer to these enhanced algorithms as E-HY and E-DW, respectively. Based on the proposed analytical model, we provide a formalization definition of the handoff conditions in E-HY and E-DW and analyze their performance. Subsequently, we propose a novel general handoff decision algorithm, GHO, to trigger HHO and VHO in heterogeneous wireless networks. Analysis shows that GHO can achieve better performance than E-HY and E-DW. Simulations validate the analytical results and verify that GHO outperforms traditional algorithms in terms of the matching ratio, TCP throughput and UDP throughput.

Consistency maintenance mechanism is necessary for the emerging Peer-to-Peer applications due to their frequent data updates. Centralized approaches suffer single point of failure, while previous decentralized approaches incur too many duplicate update messages because of locality-ignorant structures. To address this issue, we propose a scalable and efficient consistency maintenance scheme for heterogeneous P2P systems. Our scheme takes the heterogeneity nature into account and forms the replica nodes of a key into a locality-aware hierarchical structure, in which the upper layer is DHT-based and consists of powerful and stable replica nodes, while a replica node at the lower layer attaches to a physically close upper layer node. A d-ary update message propagation tree (UMPT) is dynamically built upon the upper layer for propagating the updated contents. As a result, the tree structure does not need to be maintained all the time, sav-ing a lot of cost. Through theoretical analyses and comprehensive simulations, we examine the efficiency and scalability of this design. The results show that, compared with previous designs, especially locality-ignorant ones, our approach is able to reduce the cost by about 25-67 percent.

In this paper, a practical eigenmode based scheduling algorithm with double loops (ESDL) is proposed for multi-user MIMO/OFDM systems. The wireless channels are decomposed into several eigenmodes, and the eigenmode based power allocation is formulated into an optimization problem, whose object is to maximize the system capacity while guaranteeing users' QoS requirements. By replacing the QoS constraints with penalty functions, the problem is reformulated to a penalty problem with a given penalty factor, which is solved by a greedy power allocation (GPA) scheme as the inner loop. The penalty factor is then updated in the outer loop according to QoS constraints. Numerical results show that compared with other algorithms proposed in the literature, ESDL can result in significant improvement in channel efficiency, while at the same time guaranteeing minimum data rates of users.

Replication and caching have been deployed widely in current P2P systems. In update-allowed P2P systems, a consistency maintenance mechanism is strongly demanded. Several solutions have been proposed to maintain the consistency of P2P systems. However, they either use too much redundant update messages, or ignore the heterogeneity nature of P2P systems. Moreover, they propagate updated contents on a locality-ignorant structure, which could consume unnecessary backbone bandwidth and delay the convergence of consistency maintenance. This paper presents a locality-aware consistency maintenance scheme for heterogeneous P2P systems. Taking the heterogeneity nature, we form the replica nodes into a locality-aware hierarchical structure: the upper layer is DHT-based and a node in the lower layer attaches to a physically close node in the upper layer. An efficient update tree is built dynamically upon the upper layer to propagate the updated contents. Theoretical analyses and simulation results demonstrate the effectiveness of our scheme. Specially, experiment results show that, compared with gossip-based scheme, our approach reduces the cost by about one order of magnitude.

With the development of Internet, many new applications with obvious multicast character come forth and become popular, which increase the importance of multicast in Internet especially in wireless access networks where the bandwidths of networks are very limited. In this paper, we consider the problem of channel assignment for multicast in multi-radio wireless mesh networks (WMNs), which have not been studied up to now. We propose a novel channel assignment strategy called UCAS based on unidirectional link model, and give an efficient greedy vertex coloring algorithm called BFVC. Finally, the results of simulations demonstrate the efficiency of the algorithms presented in this paper.

The random access scheme is used for initial and periodic ranging in the IEEE 802.16 protocol. The number of contention slots in the uplink subframe decides the system performance. However, how many contention slots should be allocated for ranging is not standardized in the protocol, so it is still necessary to determine the optimal number of contention slots. In this paper, the exact equations of the optimal numbers of initial ranging slots and periodic ranging slots are derived. An optimal dynamic allocator is also proposed to optimize the allocation of the initial and periodic ranging regions in the uplink subframe. The simulation results show that good system performance can be achieved with the optimal dynamic allocator.

In this paper, we propose a practically efficient Subcarrier Allocation scheme based on Lagrangian relaxation to solve the problem of subcarrier allocation in OFDMA wireless channels. The problem of subcarrier allocation is formulated into an Integer Programming (IP) problem, which is relaxed by replacing complicating constraints with Lagrange multipliers using Lagrangian Relaxation. A subgradient method is used to optimize the Lagrangian dual function and a heuristic is designed to obtain the feasible solution. Lagrangian Relaxation Subcarrier Allocation (LRSA) is proven to be of polynomial complexity and it provides bounds on the value of channel efficiency. Numerical results show that compared with other algorithms proposed in the literature, LRSA can result in a significant improvement in channel efficiency, while at the same time guaranteeing minimum data rates of users.

The next generation wireless networking (4G) is envisioned as a convergence of different wireless access technologies with diverse levels of performance. Vertical handoff (VHO) is the basic requirement for convergence of different access technologies and has received tremendous attention from the academia and industry all over the world. During the VHO procedure, handoff decision is the most important step that affects the normal working of communication. In this paper, we propose a novel vertical handoff decision algorithm, self- adaptive VHO algorithm (SAVA), and compare its performance with conventional algorithms. SAVA synthetically considers the long term movement region and short term movement trend of mobile hosts, and achieves a good integrative handoff performance.

In recent years, many research works have focused on vertical handoff (VHO) decision algorithms. However, evaluation scenarios in different papers are often quite different and there is no consensus on how to evaluate performance of VHO algorithms. In this paper, we address this important issue by proposing an approach for systematic and thorough performance evaluation of VHO algorithms. Firstly we define the evaluation criteria for VHO with two metrics: matching ratio and average ping-pong number. Subsequently we analyze the general movement characteristics of mobile hosts and identify a set of novel performance evaluation models for VHO algorithms. Equipped with these models and evaluation criteria, we evaluate and analyze two types of decision algorithms: hysteresis based and dwelling-timer based algorithms. The results show a good match between simulation and analytical results.

In this paper, we tackle the packet scheduling problem in IEEE 802.16e wireless metropolitan area network (WMAN), where the Sleep Mode is applied to save energy of mobile stations (MSs). Our objective is to design an energy efficient scheduling policy which works closely with the sleep mode mechanism so as to maximize battery lifetime in MSs. To the best of our knowledge no power saving scheduling algorithms based on sleep mode defined in IEEE 802.16e have been proposed so far in the literature. We propose a longest virtual burst first (LVBF) scheduling algorithm which schedules packets of MSs in a virtual burst mode where there is one primary MS and multiple secondary MSs sharing the wireless link resource. LVBF prolongs MSs' lifetime by reducing the average time when MSs stay in the idle state and the number of state transitions between the awake and sleep states. Simulation results show that, in comparison with the round robin scheduling scheme, LVBF can produce significant overall energy saving, while guaranteeing the QoS requirements of MSs in terms of their minimum data rates.

Access authentication is very important for deploying mobile IPv6 networks. In this paper, we design a two-level hierarchical identity-based signature scheme, based on which we propose a new hierarchical authentication scheme for mobile IPv6 networks. Our solution adopts multi-level network access identifier (NAI) as public key, which simplifies key management in wireless mobile environment. The handover procedure integrating authentication is also cut down by our hierarchical solution. And our solution accomplishes mutual authentication between terminal and network. We propose the handover latency analytical model to evaluate handover latency. The results show that our solution is more efficient than others, especially when a terminal is far away from its home domain and moves frequently. Security analysis shows that the proposed scheme is sufficient for privacy and unforgeability. An extended version for access authentication in multi-hierarchical mobile IPv6 networks is discussed.

Mobile IPv6 (MIPv6) protocol was released by IETF in 2004. Conformance testing is necessary to accelerate MIPv6 practicality. Formal description and test generation is the key issue in conformance testing. In order to describe and test MIPv6, we define finite state machine (FSM) and multi-node finite state machine (MN-FSM). We propose the method of hierarchical protocol description. MIPv6 is divided into four layers: network system layer, MIPv6 nodes layer, inner data structure management layer and discrete behaviors layer. We separately present the approaches to describe each layer by FSM and MN-FSM. We propose the test generation algorithm and generate MIPv6 test suite. The results of comparison show the validity of our proposed methods.

This paper addresses the throughput optimization problem in multihop ultra-wideband (UWB) networks by jointly considering network topology formation and routing. Given a spatial distribution of UWB devices and traffic requirement, we want to form piconets and select paths to maximize the network throughput. Although there have been several works considering the problem of selecting paths to achieve the optimal throughput in multihop wireless networks, to the best of our knowledge, none of them takes the topology formation into the consideration. In this paper, we use Boolean matrices to model role assignment in UWB networks and formulate the throughput optimization problem as a nonlinear programming (NLP) problem. Since the throughput optimization problem is NP-hard, we give an upper bound of the optimal throughput by relaxing some constraints and using pseudo-Boolean optimization to linearize the NLP. We prove that the solution of the upper bound is at most three times of the optimal throughput. Based on the topology formed by solving the upper bound, we formulate a lower bound of the optimal throughput as a linear programming problem and use column generation to solve the lower bound. Numerical results show that the lower bound is very close to the upper bound. Simulation results demonstrate the effectiveness of the scheme.

Packet delay is one of the most important Internet performance metrics. Many studies indicate that long-range dependence (LRD) exits in Internet packet delay, but the scaling behavior of packet delay is very complicated. This paper analyzes the Internet round-trip time (RTT) behavior based on small-interval (10 ms) measurements and finds that RTT series consist of two completely different components: spiky component and normal component. A bottleneck model is proposed to explain the phenomenon. By using detrended fluctuation analysis (DFA) method, it is found that the original RTT series don't exhibit simplex scaling behavior, and although the spiky component accounts for a little proportion of the original RTT series, it has a great impact on the scaling behavior. After removing the spiky component, RTT series show LRD, with Hurst exponent ranging from 0.55 to 0.8. And we discuss the implications of our findings on delay-boundary prediction algorithms of TCP

We propose a new coding method of limited global fault information in an n-cube. First, each node collects precise fault information within distance-d, and then fault information about nodes that are more than distance-d away is coded in a special way. Specifically, in our approach, each node in a cube-based multicomputer of dimension n is associated with an extended safety vector of n bits. In the extended safety vector model, each node knows fault information within distance-2; fault information outside distance-2 is coded in a special way based on the coded information of its neighbors. The extended safety vector of each node can be easily calculated through n-1 rounds of information exchanges among neighboring nodes. Therefore, each extended safety vector is an approximated measure of the number & distribution of faults in the neighborhood. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source & destination nodes. In addition, the extended safety vector can be used as a navigation tool to direct a message to its destination through a minimal path. A simulation study has been conducted based on different selections of d, and results have shown a significant improvement under the proposed model over the safety vector model in handling link faults, even for a small value of d as in the extended safety vector model where d=2.

Owing to the asymmetry of Internet paths, more and more studies have turned to the measurement for one-way metrics. However, since the clocks at end systems often behave diversely, the synchronization between the end hosts is what we care about all along. In this paper, we firstly propose a general model for clock skew estimation in one-way measurements, which turns the problem of clock skew estimation to the solution of n-dimension equation group, and give the equation group what it needs based on different presumptions. We then present a Piece-wise Reliable Clock Skew Estimation Algorithm (PRCSEA), which introduces the reliability test of estimation results and eliminates the extra presumptions needed by other algorithms, such as only one clock adjustment in the measurements. PRCSEA solves the skew estimation problem in a heuristic way, and it can handle many special cases affecting the estimation of clock skew, such as routing change, clock hiccup and network congestion. PRCSEA is the only algorithm that can handle non-constant clock skew to the best of our knowledge. The time complexity of PRCSEA is O(n*logn), which is the same as that of Paxson's algorithm.

IPv6 is in its growing stage in which new protocols are being proposed and more and more IPv6 devices are being produced. Conformance testing is the most important method to improve the reliability of IPv6 implementations. With a view to provide test ability for IPv6, the features and the test requirements of IPv6 are analyzed. Two difficulties of the standard test framework applying to IPv6 conformance testing, test packets description and complicated algorithm implementation, are pointed out. IPv6 test framework is proposed to solve the two difficulties, in which a new IPv6 test suite specification language is defined. Two test methods, called the virtual test method and the low-layer congregating test method, are adopted to enhance single physical tester's test ability. IPv6 test suite is designed and four IPv6 implementations are tested. An example of test case is given to explain IPv6 test framework and IPv6 test suite specification language.

To develop an accurate parametric model for network characteristics is very difficult. We propose a fitting-based adaptive sampling methodology (FASM) trying to model some network metrics non-parametrically. The contributions of the paper are twofold: (1) adopting a piecewise linear function approximation scheme to provide more accurate approximation of the true metric model; (2) the statistical metric derived from the non-parametric model provides much more stable, lower variance and accurate estimation than other popular methodologies under the same sampling size. Experiments based on two measurement traces show that FASM dramatically reduces the number of samples while retaining the same approximating residual error than other methods.

We present an original end-to-end available bandwidth measurement method, called SMART (statistics measurement for avail-bw by random train). It resolves some of the problems common for many types of existing probing methods, e.g. the long latency and large probe traffic. Contrary to traditional estimates of available bandwidth, SMART is not a methodology based on packet dispersion in packet pair or packet train, but a completely new methodology in the light of probability and statistics. The fundamental idea is to send very small packets at random moment and calculate the proportion of minimal delay ion total test samples. To reach this purpose, we redefine the available bandwidth based on probability and statistics. We have evaluated our method in controlled and reproducible environment using NS2, and the simulations show our method is accurate, efficient, quick and non-intrusive.

This paper characterizes the end-to-end routing measurement infrastructure WTracer and discusses the crucial technologies. Although WTracer is a traceroute server based Internet measurement infrastructure, it can be used in many areas, such as measurement and analysis of end-to-end routing behavior of the Internet, the estimation of the global Internet host distances, the measurement of hop count in the Internet, the discovery of Internet topology at both router level and AS level so on.

The distribution characteristic of RTT (round-trip time) is an important part of Internet end-to-end behavior characteristics. People have made lots of studies of it, but many conclusions only adapt to the cases of small packet loss rate. We study the RTT characteristics on nearly 40 end-to-end paths in CSTNET and CERNET in China, and draw the following conclusions: (1) the distribution characteristics of RTT and loss rate are dependable; (2) when loss rate is small, RTT distribution is usually unimodal, but with the increase of loss rate, RTT distribution is no longer unimodal and it becomes more and more decentralized; (3) with the increase of loss rate, the occurring times of inherent RTT tend to decrease.

This paper presents a new level of description between behavioral and state descriptions of a finite-state machine (FSM). The description is termed behavioral phase clustering description. New concepts of behavioral phase and clustering of behavioral phases in an FSM are introduced. The new description simplifies functional analysis, verification and test of FSM designs. If an FSM is described at low level, some states can be clustered into behavioral phases directly. If it is described at behavioral level, behavioral phases can be extracted from the behavioral description, and clustering of behavioral phases can be performed through easy functional analysis. As one application of behavioral phase clustering descriptions, a new technique employed in a test generation system, ATCLUB, at Register Transfer (RT)-level based on a behavioral phase transition fault model is introduced in this paper. In ATCLUB, test generation process is accelerated through clustering of behavioral phases. Experimental results show that ATCLUB generates test sequence efficiently, with a sharp decrease in vector count at the penalty of a slightly decrease in fault coverage comparing to other ATPG tools.

This paper introduces a new technique employed in a test generation system, ATCLUB, at RT-level, based on clustering of circuit states. States or some sets of states in a low-level description are mapped to high levels in terms of a particular variable in a behavioral description, and termed behavioral phases. Further clustering of behavioral phases is performed to represent the function of a circuit more explicitly and refinedly. Such a refined representation is then used in the test generation algorithm to simplify and speed up search process of test sequences. Experimental results demonstrate the computational efficiency of the clustering process and test pattern generation.

IPv6, the next generation Internet protocol, has been seen as the best solution for the problems that current Internet protocol faced. In this paper, IPv6 is introduced, including main benefits of IPv6 and the transition mechanism from IPv4 to IPv6. In order to assure the new protocol implementation to be consistent to the standard and in turn to assure the interoperability between different IPv6 implementations, IPv6 protocol conformance test is required. The performance process of an IPv6 conformance test tool that was developed to test IPv6 protocol is introduced, and a formal specification language is used to describe the test suite. With the test tool and test suite, we test the IPv6 General Specification Protocol and ICMPv6 on a Linux IPv6 implementation and give the test report.

Reliable communication in cube-based multicomputers using the extended safety vector concept is studied. Each node in a cube-based multicomputer of dimension n is assorted with an extended safety vector of n bits, which is an approximated measure of the number and distribution of faults in the neighborhood. In the extended safety vector model, each node knows fault information within distance-2 and fault information outside distance-2 is coded in a special way based on the coded information of its neighbors. The extended safety vector of each node can be easily calculated through n-1 rounds of information exchanges among neighboring nodes. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source and destination nodes. In addition, the extended safety vector can be used as a navigation tool to direct a message to its destination through a minimal path. Simulation results show a significant improvement in terms of optimal routing capability in a hypercube with faulty links using the proposed model, compared with the one using the original safety vector model.

Presents a new concept - optimal path matrices (OPMs) - for fault-tolerant routing on hypercube multicomputers. OPMs stored on each node of a hypercube hold the fault information and indicate whether there is an optimal path from the node to a destination. Two fault-tolerant routing algorithms based on OPMs are proposed in order to maintain the matrices and to route messages from sources to destinations. One is a routing algorithm based on OPMs, which are filled with pre-collected information through information exchange between neighbors. It can easily establish a path for a message, and the length of the path is no greater than the Hamming distance between the source and the destination of the message plus two. The other routing algorithm is a modified depth-first search algorithm, which adopts a dynamic learning strategy to fill OPMs during normal message transmission and can find almost all the optimal paths. The memory overhead is n/sup 2/ words on each node of an n-dimensional hypercube.

Delay testing is important for high speed ICs. The main difficulty for delay testing comes from the huge number of paths and the large percentage of delay untestable paths. This paper presents an approach to delay testing with double observations, which provides a high path delay fault coverage by testing a small number of paths. But, for each test pair, it is necessary to sample the primary output twice, one before and another after the transition. The paper explains how to select the very limited number of paths, termed sample paths, and how to generate the test pair and the observation times for the sample paths. Furthermore, the number of sample paths is linear to the number of gates in the circuit under test, despite exponential growth in the number of single paths. Based on the analytical delay model, most of the paths are delay testable which makes the delay test generation easier than that based on single path sensitization.

In many designs a large portion of path delay faults is non-robustly untestable. This paper presents a new low-cost method for identifying non-robustly untestable path delay faults. Using an implication-based procedure, our method starts with a small number of path segments, called maximum fanout-free segments, to quickly locate lines which cannot construct non-robustly testable paths with them. After a large portion of faults is marked as untestable, only a small subset of faults remains for the ATPG procedure, which can effectively alleviate the problem of handling a huge number of path delay faults and reduce test generation time. Experimental results for ISCAS'85 benchmark circuits demonstrate that a significant portion of non-robustly untestable path delay faults was identified efficiently using our method. For most of these circuits, 90%-95% of non-robustly untestable path delay faults can be identified within a small amount of CPU time.

A memory efficient test pattern generator for path delay faults, DTPG, is presented in this paper, which uses the efficient path identifier to represent a path. A compact bit table, path information table, is proposed to store test information efficiently. Furthermore, DTPG is capable of identifying functional sensitizable paths, which account for large percent of paths in many circuits. The experimental results show that DTPG is memory efficient. It generates tests for C3540 with 57 million paths and preserves the testability information for all paths. Experimental results show the influence of stepwise mandatory sensitization, multiple backtrace, and backtracking limits on the cpu time consumed by delay test generation process.

The industry has accepted I/sub DDQ/ testing to detect CMOS IC defects. While I/sub DDT/ testing needs more research to be applicable in practice. However, it is noticed that observing the average transient current can lead to improvements in real defect coverage. This paper presents a formal procedure to identify I/sub DDT/ testable faults, and to generate input vector pairs to detect the faults based on Boolean process. It is interesting to note that those faults may not be detected by I/sub DDQ/ or other test methods, which shows the significance of I/sub DDT/ testing.

The paper presents an extension to OBDDs with timing information, called timed binary decision diagrams (TBDDs). TBDDs are also canonical and allow the symbolic manipulation of Boolean functions with timing information. A TBDD software package is implemented based on the existing CMU BDD package. Experimental results demonstrate the efficiency of the TBDDs in representing circuits with both functional and timing information.

This paper presents an efficient implication-based approach for identifying non-robustly untestable path delay faults. It starts from possible conflicts to find untestable faults by performing static implication. It is neither path-oriented nor space-search based. Experimental results for ISCAS'85 benchmark circuits demonstrate that a significant portion of non-robustly non-robustly untestable path delay faults is identified efficiently. The method can be combined easily with ATPG-based approaches for path delay testing to yield cost effective methods for path delay faults in large circuits.

A waveform polynomial for a digital circuit integrates both logic and timing information. It is applicable to design verification and test. This paper introduces a compact and manageable form, BPBDD, to represent and manipulate Boolean process based on BDDs, and shows how to construct a BPBDD representing a waveform polynomial for a given circuit. Experimental results show that BPBDD is capable of handling circuits of middle size efficiently. Although it is more complicated than OBDDs, more information about a circuit is available.

For pt. I see ibid. (1994). Incorporating performance factors in the physical and logical design of VLSI circuits is necessary for performance enhancement. Boolean process provides an analytical approach to circuit representation to precisely describe logical and timing behavior simultaneously. It allows input and output of circuits be described by waveform functions, which is consistant with common used intuitive waveforms. Waveform functions can be manipulated formally by using mathematical tools. This paper defines distance, difference and limit of waveform polynomials, and demonstrates that the concepts of sensitization and hazard should be redefined precisely when duration between input transitions is comparable to circuit delay. Based on these observations, many interesting results are driven.

Many ATPG algorithms are proposed every year. Evaluation of ATPG algorithms not only provides possibility to compare algorithms, but also predicts required computation resources for design and test of extra large circuits. The evaluation includes aspects of fault coverage, computation efficiency, and test set size. ISCAS 85 and ISCAS 89 benchmark circuits are available common examples for the evaluation. This paper presents a general methodology for the evaluation in spite of the difference of the computing environments that the algorithms run in. Eleven ATPG algorithms are evaluated, as a case study, based on the data of their experimental results published in the literature to show the feasibility and validation of the methodology presented.>