Time series data analysis, employing dynamic time warping (DTW) algorithms, has a wide range of applications in fields such as medicine and economics. Given the widespread distribution of data across different domains, integrating and analyzing these datasets through outsourced cloud computing can enhance analytics, though privacy concerns arise. Privacy preserving data analysis, underpinned by secure multi-party computing, emerges as a crucial approach to address this challenge. However, existing efforts face high communication costs and increased interactions, resulting in significant efficiency constraints in practical applications. In this paper, we propose a function secret sharing (FSS)-based framework for secure collaborative analysis of time series data using the DTW algorithm. Utilizing the distributed comparison function, we develop efficient building blocks with minimal online interaction and communication, enhancing the practicability of security protocols. To address the challenges of FSS key generation due to uncertain computational topology when cascading multiple distances, we adopt a modular design and decompose the analysis process into several critical modules. Furthermore, our framework efficiently supports various constraint methods for DTW. We implement and evaluate our framework using publicly available datasets. The results demonstrate a significant reduction in communication costs and the number of interactions during the online phase.

Authentication and Key Agreement (AKA) are essential for UAV networks operating in open and hostile environments, as they assist in preventing common threats such as impersonation and replay attacks. However, traditional protocols often rely on a centralized server for key and identity management, creating risks of key leakage and a single point of failure. To address these issues, we propose a blockchain-based decentralized authentication mechanism that remains effective even under partial node compromise. Our design adopts Physical Unclonable Functions (PUFs) in place of key-based authentication to mitigate key leakage risk. To mitigate machine learning (ML) attacks inherent in existing PUF-based protocols, we design a lightweight Encrypted Randomized Challenge-Response Pair (ERCRP) structure, which incorporates external randomness to obfuscate underlying PUF mapping. Meanwhile, to address CRP leakage in prior centralized schemes, we combine Shamir's Secret Sharing and blockchain for secure CRP management. Specially, we introduce a decoupled design that separates interaction-intensive secret reconstruction process from blockchain consensus to ensure high efficiency. Finally, we develop a lightweight commitment-based management mechanism to prevent unauthorized CRP consumption and reuse from malicious authentication attempts. Additionally, the protocol provides UAV identity untraceability via dynamic identity updates. Comprehensive formal and informal security analyses, together with comparative performance evaluations, demonstrate the protocol's strong security guarantees and practical efficiency.

Intelligent Transportation System (ITS) applications rely on reliable data exchange, supported by the WAVE protocol through vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communications. In single-radio configurations, nodes alternate between a control channel (CCH) and service channels (SCHs), leading to a burst of queued transmissions at the start of each SCH interval. This results in the start-of-interval contention (SIC) issue, characterized by high collision rates and reduced delivery performance. Therefore, we propose a centralized contention window (CW) adaptation mechanism based on the Quantile Regression Deep Q-Network (QR-DQN), where a Roadside Unit (RSU)-hosted agent adjusts CW using only PHY-layer observations. We further combine this deep reinforcement learning (DRL)-based method with the Skip-CCH mechanism and evaluate both individual and combined solutions through simulation. Results show notable improvements in packet delivery and channel efficiency compared to legacy WAVE and Skip-CCH.

Electronic voting plays a crucial role in facilitating democratic and convenient decision-making in people’s lives. However, implementing an electronic voting system poses challenges, such as meeting the stringent security requirements for anonymity, fairness, and verifiability. Another concern is the performance degradation when dealing with a large number of voters. In this paper, we propose$S^{3}$Voting, a blockchain sharding-based e-voting scheme that addresses these challenges. By combining robust security and scalability,$S^{3}$Voting provides reliable technical support for conducting large-scale elections. Utilizing advanced technologies such asHomomorphic Time-Lock Puzzle (HTLP)andone-time ring signature, the system safeguards voters’ privacy and ballot confidentiality. The approach involves dividing voters and miners into smaller shards, and implementing shard managing mechanisms to ensure security and enhance system efficiency. Through thorough security analysis, we demonstrate that$S^{3}$Voting not only meets the fundamental security requirements of e-voting but also offers verifiability and strong robustness-essential elements for successful large-scale elections. Moreover, experimental results indicate that$S^{3}$Voting significantly reduces the computational burden on individual miners and minimizes system processing time compared to existing blockchain-based e-voting solutions.

Mobile users often prefer to sense only a subset of tasks based on their preferences or physical conditions, which distinguishes sparse crowdsensing from traditional crowdsensing. Sparse crowdsensing not only introduces a potential risk of privacy leakage regarding users’ preferences or conditions—due to the revelation of specific sensed objects—but also results in reduced accuracy of truth estimation. To address these challenges, we propose a Privacy-Preserving Truth Discovery (PPTD) scheme, named S-PPTD, that enables accurate and efficient PPTD for sparse crowdsensing. Our approach leverages edge nodes to geographically group users and introduces an effective padding strategy based on Bloom filters and mixed secret sharing. This strategy allows users to obfuscate the objects they sense, preventing adversaries from determining the specific objects being sensed. To improve accuracy, we design new protocols for precise and efficient approximation of nonlinear functions, enabling the use of commonly applied kernel functions to capture spatial and temporal correlations between objects, and incorporate these into the truth estimation process. Through extensive experiments and security analysis, we demonstrate that S-PPTD is secure, accurate, and efficient in the context of sparse mobile crowdsensing.

Crowdsourcing has emerged as an effective paradigm for large-scale data collection and statistical analysis. However, the paramount concern about worker privacy has driven the development of privacy-preserving statistical analysis methods. We propose PSAC, a novel framework that leverages histograms to facilitate privacy-preserving statistical analysis in crowdsourcing. PSAC integrates secure statistical analysis protocols based on homomorphic encryption and secure two-party computation, addressing the limitations of a single cryptographic technique. It introduces innovative algorithms using histograms for statistical operations, including functions such as quantile estimation, outlier elimination, contingency table construction for$\chi ^{2}$test, and the Mann-Whitney$U$test. These algorithms exhibit minimal overhead growth with respect to data volume, demonstrating exceptional scalability for large numbers of data. Moreover, through a key-separation design, PSAC ensures that only the requester can decrypt the final results independently, even if the ciphertexts of data are exposed. Comprehensive evaluations validate the security, efficiency, and scalability of the PSAC framework.

Clustering is a crucial unsupervised machine learning algorithm extensively used in various practical applications, such as patient refinement and fraud detection, which often involve vertically distributed data across multiple data centers. However, sharing datasets directly is typically prohibited under GDPR due to potential privacy breaches. Therefore, privacy-preserving joint clustering for vertically distributed datasets is highly desired. In this paper, we propose Privacy-Preserving Vertically Federated Clustering (PPVFC), a solution that not only achieves this goal but also significantly reduces computational and communication overhead for each data owner (DO). Unlike most previous works that achieve the goal with a single privacy-enhancing technology, PPVFC jointly leverages multiparty homomorphic encryption (MHE) and multiparty computation (MPC) to efficiently interleave communication-lightweight homomorphic computations on the local dataset with operations over collectively secret-shared intermediate data. Specifically, we design a coefficient-wise encoding for MHE to pack large datasets and minimize communication costs. Additionally, we develop a round-efficient bit extraction protocol for determining the minimum distance. Through extensive experiments and security analysis, we demonstrate the practical performance and robust security guarantees of PPVFC.

Harnessing the benefits of blockchain, such as decentralization, immutability, and transparency, to bolster the credibility and security attributes of federated learning (FL) has garnered increasing attention. However, blockchain-enabled FL (BFL) still faces several challenges. The primary and most significant issue arises from its essential but slow validation procedure, which selects high-quality local models by recruiting distributed validators. The second issue stems from its incentive mechanism under the transparent nature of blockchain, increasing the risk of privacy breaches regarding workers’ cost information. The final challenge involves data eavesdropping from shared local models. To address these significant obstacles, this paper proposes a Blockchain-enabled Incentivized and Secure Federated Learning (BIT-FL) framework. BIT-FL leverages a novel loop-based sharded consensus algorithm to accelerate the validation procedure, ensuring the same security as non-sharded consensus protocols. It consistently outputs the correct local model selection when the fraction of adversaries among validators is less than$1/2$with synchronous communication. Furthermore, BIT-FL integrates a randomized incentive procedure, attracting more participants while guaranteeing the privacy of their cost information through meticulous worker selection probability design. Finally, by adding artificial Gaussian noise to local models, it ensures the privacy of trainers’ local models. With the careful design of Gaussian noise, the excess empirical risk of BIT-FL is upper-bounded by$\mathcal {O}(\frac{\ln n_{\min}}{ n_{\min}^{3/2}}+\frac{\ln n}{n})$, where$n$represents the size of the union dataset, and$n_{{\min}}$represents the size of the smallest dataset. Our extensive experiments demonstrate that BIT-FL exhibits efficiency, robustness, and high accuracy for both classification and regression tasks.

Multipath TCP (MPTCP) has gained popularity to enhance data transmission. From the last decade, proposed MPTCP enhancement schemes for congestion control, path management, and packet scheduling, have been used to benefit transmission performance. However, despite their efforts, they are exigent with a comprehensive understanding of real-world performance to guide the implementation of MPTCP to a more complex wireless network. To that end, we conduct a measurement-driven study of MPTCP enhancement schemes, providing insights and in-depth demonstrations of their performance with a comprehensive real-world platform. Our finding indicates that the enhancement schemes struggle to consistently maintain high performance at all times. One can achieve optimal efficiency in its specific scenarios, but suffers extreme degradation at times. To eliminate this transmission uncertainty in wireless networks, we further propose an adaptive control framework OLSch to integrate different schemes, emphasizing their strengths to provide consistently high performance. To be specific, OLSch is implemented with different scheduling schemes and leverages an online-learning-driven approach to choose one that best fits the current network conditions. Evaluations show that OLSch obviously improves the stability of transmission in harsh network scenarios, eliminates performance degradation, and increases the 95% tail throughput by 1.45×-2.39×.

Link-flooding attacks (LFAs) pose a significant challenge to Internet availability by attacking critical network links with high volumes of seemingly legitimate traffic. In response, researchers have developed network topology obfuscation (NTO) to safeguard critical links. However, state-of-the-art NTO defenses are coarse-grained, leading to less efficient security and usability. In addition, once under attack, NTO schemes cannot identify the attacker’s bot and launch counter-defensive measures. To address these issues, this paper introduces SpiderNet, which employs advanced obfuscation techniques to secure critical links while using strategically created honeypot links for effective bot identification. When adversaries probe the network, SpiderNet captures their probing behavior and deliberately feeds back misinformation about honeypot links. By analyzing the attack patterns directed at these decoy targets, SpiderNet correlates them with adversarial probing activities to effectively identify the bots. Our experiments demonstrate that SpiderNet is more robust than state-of-the-art NTO schemes in terms of security and usability, while also being capable of identifying LFA bots.

Named Data Networking (NDN) has emerged as a promising network paradigm for the future Internet. It revolutionizes content retrieval by decoupling it from specific locations, thereby overcoming the limitations of traditional IP addressing and significantly enhancing data delivery efficiency. Additionally, NDN’s stateful forwarding plane for routers enables robust aggregation of identical requests, bolstering resistance against Distributed Denial of Service (DDoS) attacks. Despite these advancements, NDN remains vulnerable to the Interest Flooding Attack (IFA), wherein excessive requests from attackers can compromise transmission quality by depleting router resources. In the current landscape, researchers have proposed various strategies aimed at improving the accuracy, timeliness, and cost-effectiveness of defenses against IFA attacks, presuming stable user behavior. However, several challenges persist in effectively countering IFA attacks, including the need to ensure transmission quality throughout users’ lifecycles, eliminate attacks at their origin, and adapt to dynamic user behaviors. In response to these challenges, this paper presents the Hybrid Proactive Reactive Defense Scheme (HPR-DS). HPR-DS employs distinct proactive and reactive modules for resource management and user behavior analysis, respectively, at intermediate and edge nodes. It employs time series analysis to gauge evolving resource requirements and maintains separate resource pools for each content. Additionally, HPR-DS utilizes multidimensional data clustering to accurately identify attackers. Simulation results demonstrate the superior performance of HPR-DS in safeguarding user transmission quality throughout the entirety of their lifecycle and in enhancing detection precision in dynamic network environments.

Due to the progress in computer hardware and network technologies, federated learning (FL), a decentralized training method in machine learning, has garnered widespread attention. In this approach, individuals share local model parameters rather than raw training data to protect their privacy. However, the inherent heterogeneity of practical computing devices poses challenges to the efficiency and performance of FL. In this paper, we explore the landscape of heterogeneous FL frameworks and introduce ChronusFed, a reinforCement-based adaptive partial training method for heterogeneous Federated learning. ChronusFed employs a dynamic epoch adjustment mechanism (DEA) and a customizable partial training framework (CPT) to optimize model training efficiency. By integrating DEA and CPT, ChronusFed effectively tackles the straggler issues that arise from limited hardware resources, while simultaneously enhancing the model performance. More specifically, DEA leverages deep reinforcement learning (DRL) to model the current state of the global model and determine optimal local training epochs, while CPT utilizes our proposed maximum coverage algorithm to handle device heterogeneity and accelerate model convergence. Theoretical analysis of training convergence validates the effectiveness of ChronusFed, and comprehensive experimental evaluations demonstrate that ChronusFed outperforms state-of-the-art methods across various learning tasks, showcasing its robustness and superiority in heterogeneous FL scenarios.

Cancer is a complex cellular ecosystem where malignant cells coexist and interact with immune, stromal and other cells within the tumor microenvironment (TME). Recent technological advancements in spatially resolved multiplexed imaging at single-cell resolution have led to the generation of large-scale and high-dimensional datasets from biological specimens. This underscores the necessity for automated methodologies that can effectively characterize molecular, cellular and spatial properties of TMEs for various malignancies. This study introduces SpatialCells, an open-source software package designed for region-based exploratory analysis and comprehensive characterization of TMEs using multiplexed single-cell data. The source code and tutorials are available at https://semenovlab.github.io/SpatialCells. SpatialCells efficiently streamlines the automated extraction of features from multiplexed single-cell data and can process samples containing millions of cells. Thus, SpatialCells facilitates subsequent association analyses and machine learning predictions, making it an essential tool in advancing our understanding of tumor growth, invasion and metastasis.

The utilization of Multi-path TCP (MPTCP) has been demonstrated to provide superior transport-layer support for data center networks (DCNs) due to its exceptional resource utilization and load-balancing capabilities. However, the substantial path diversity can make it challenging to utilize network resources to their full potential in DCNs. This paper focuses on studying the resource allocation issue of MPTCP from a resource optimization perspective. Based on theoretical analysis, we propose FMPTCP, which uses a feedback-based congestion control algorithm (FCC) and a feedback-based multi-path routing algorithm (FMP) to jointly achieve high bandwidth utilization and low round-trip time (RTT) in DCNs. The FCC algorithm utilizes probabilistic explicit congestion notification (ECN) to provide feedback on path congestion degree, and uses a gradient descent method to adjust the congestion window for optimal resource utilization and load balancing under a fixed routing topology. On the other hand, the FMP algorithm employs a hop-by-hop feedback mechanism to notify in-network congestion and path delay information, allowing for transparent multi-path routing for MPTCP flows. Our extensive simulations demonstrate that FMPTCP enables effective network resource utilization, which not only enhances overall throughput but also reduces transmission latency for DCNs.

Searchable Symmetric Encryption (SSE) is a valuable cryptographic tool that allows a client to retrieve its outsourced data from an untrusted server via keyword search. Initially, SSE research primarily focused on the efficiency-security trade-off. However, in recent years, attention has shifted towards range queries instead of exact keyword searches, resulting in significant developments in the SSE field. Despite the advancements in SSE schemes supporting range queries, many are susceptible to leakage-abuse attacks due to volumetric profile leakage. Although several schemes exist to prevent volume leakage, these solutions prove inefficient when dealing with large-scale datasets. In this paper, we highlight the efficiency-security trade-off for range queries in SSE. Subsequently, we propose a volume-hiding range SSE scheme that ensures efficient operations on extensive datasets. Leveraging the order-weighted inverted index and bitmap structure, our scheme achieves high search efficiency while maintaining the confidentiality of the volumetric profile. To facilitate searching within large-scale datasets, we introduce a partitioning strategy that divides a broad range into disjoint partitions and stores the information in a local binary tree. Through an analysis of the leakage function, we demonstrate the security of our proposed scheme within the ideal/real model simulation paradigm. Our experimental results further validate the practicality of our scheme with real-life large-scale datasets.

Set-valued data are commonly used to represent subsets of a universal set and are frequently utilized in online services, such as online shopping preferences, website browsing records, and recently visited places. By collecting set-valued data from users, service providers can perform statistical analysis to obtain a joint distribution of service usage data and subsequently learn the association between different kinds of set-valued data to improve the quality of service. However, collecting set-valued data raises privacy concerns about the potential misuse of records to infer individuals’ identities and preferences. Although some privacy-preserving aggregation mechanisms for set-valued data have been proposed, they have not yet achieved joint distribution analysis with high accuracy. In this paper, we propose a joint distribution analysis method for set-valued data with local differential privacy (LDP). We design a scalable perturbation mechanism under$\epsilon $-LDP by limiting the range of users’ responses in the collection process and cyclically shifting the set-valued data in an encoded uniform format, ensuring that the size of the universal set does not influence the accuracy of the results. Based on the perturbation method, we develop an analysis method to efficiently obtain association information between two sets. By performing specific bitwise operations on the perturbed data matrices, the computational overhead is linear with respect to the cardinality of the item set. In addition to theoretically analyzing the error bound and proving the security of our work, extensive experimental results on synthetic and real-world datasets demonstrate that our scheme achieves better utility than existing state-of-the-art approaches.

Entanglement distribution between distant quantum nodes plays an essential role in realizing quantum networks’ capabilities. In addition to path selection, remote entanglement distribution involves two pivotal quantum operations, i.e., entanglement generation and entanglement swapping. The existing studies mainly adopt two methods, i.e., Tell-and-Generation (TAG) and Tell-and-Swapping (TAS), to manage these two quantum operations on a selected path. However, both methods fatally introduce redundant stop-and-wait processes, which are detrimental to the performance of remote entanglement distribution in terms of latency and fidelity. To achieve low-latency and high-fidelity entanglement distribution between far-off quantum nodes, we propose a segment-based method consisting of an entanglement generation algorithm and a segment design to diminish the unnecessary stop-and-wait processes. The entanglement generation algorithm adopts a concurrent design to establish entanglement links using the one-demand generation model, thus effectively reducing waiting time compared to hop-by-hop and parallel designs. The segment design is proposed to split a long-distance path into multiple short-haul segments with the similar ability to swap entanglement, and these segments build multi-hop entanglement connections in parallel. Extensive simulations show that the segment-based method significantly outperforms the existing methods, including TAG and TAS, in entanglement distribution latency and effectively mitigates fidelity attenuation.

The immutability of blockchains is an important security feature, but applications and studies have shown that it poses some problems. For instance, harmful information and vulnerable programs can be permanently stored on public blockchains such as Bitcoin and Ethereum, causing continuous damage. Therefore, researchers proposed the redactable blockchain to delete or modify those harmful data. Existing schemes usually adopt the Chameleon hash function (CHF) to keep the block hash unchanged so that other blocks remain unaffected. However, these schemes suffer from two security problems: (i) (unknown-version) users cannot determine whether a received block is the up-to-date version because different versions have the same hash; and (ii) (lazy-redaction) miners have no motivations to update historical blocks, causing continuous spreading of data which should have been discarded. To solve the problems, we propose SEREDACT, a secure and efficient redactable blockchain protocol with verifiable modification. Specifically, we design a Merkle tree-based verification mechanism with efficient dynamic updating that supports quick version checks and forcible modification updates, and further integrate it with restricted redaction policies to guarantee security. Our security and performance analyses show that SEREDACT has adequate security as a redactable blockchain protocol and retains close efficiency compared with the immutable blockchain.

The quantum network is designed to connect numerous quantum nodes and support various ground-breaking quantum applications. Most of these applications require communicating parties to share entangled pairs. Therefore, entanglement routing, a technology distributing entangled pairs between distant quantum nodes, plays a vital role in realizing quantum networks’ capability. However, due to the limitation of quantum memory size and quantum decoherence, the entangled pairs shared by adjacent quantum nodes can hardly satisfy concurrent entanglement routing requests, thus leading to severe network congestion. In this paper, we propose a novel congestion mitigation (CM) scheme to tackle such bottleneck problems. The basic idea of CM is to “recycle” idle link-level entanglement resources from well-resourced links to bottleneck links utilizing a unique enabling technology of quantum networks, called entanglement swapping. CM can increase the capacity of each bottleneck link, thus overcoming resource limitations to improve resource utilization and network throughput. To complete our work, we also propose a swapping-based entanglement routing design, including path selection and resource allocation algorithms. Extensive simulations show that our design can significantly alleviate network congestion and improve the request service rate of quantum networks compared to the traditional entanglement routing designs.

Existing congestion control algorithms for MPTCP that care about only long flow transmission aim at the Congestion-Avoidance (CA) phase and they need a long time to reach convergence states. We verified that the exponential growth of congestion window (cwnd) in the uncoupled Slow-Start (SS) leads to not only unfairness to TCP but also buffer overflow due to burst data. Moreover, these algorithms cannot support fair bandwidth sharing among TCP/MPTCP flows before reaching convergence at the bottleneck, which may reduce the transmission efficiency of short flows and even hurts long flows. In this paper, we propose a Throughput Consistency Congestion Control (TCCC) algorithm consisting of Coupled Slow-Start (CSS) and Aggressive Congestion Avoidance (ACA). To prevent packet loss caused by excessive burst data, CSS couples the increment of subflows’ cwnd and reset the ssthresh value to safely move the flows to CA when it achieves expected throughput. Based on CSS, ACA periodically detects path states and allocates the same throughput increment as the best TCP to subflows to achieve fair bandwidth share in CA. Finally, we implement TCCC in both NS3 and real testbed. The results show that TCCC reduces retransmissions, improves transmission efficiency, and maintains better fairness.

The upgrade of network devices to be equipped with multiple network interfaces makes it possible to improve network throughput performance through multipath transmission protocols, especially multipath TCP (MPTCP). However, so far the mostly used MPTCP protocols have a common limitation, namely the rigid and conservative method. They have been designed with little consideration of the fact that real networks are dynamic and the network status changes frequently, thus leading to the poor performance of current MPTCP in many realistic scenarios. In this paper, we propose a lightweight multipath congestion control algorithm based on online learning, named MP-OL. MP-OL models congestion control as a multi-armed bandit problem, and adjusts the sending rate of each subflow flexibly and adaptively through online learning. Therefore, MP-OL possesses the capability of suiting various network scenarios, and can achieve fairness and high performance in dynamic network environment. It can also flexibly switch between online learning and traditional method, which reduces the computational complexity while ensuring the learning efficiency, thus making MP-OL easy to deploy and use. As the experimental results demonstrated, compared with the leading MPTCP variants, MP-OL achieves significant improvements in fairness and link utilization, and shows better resilience to non-congestion loss and better adaptability to unstable network conditions. In real networks, MP-OL also obtains better throughput performance.

Multipath TCP is designed to utilize multiple network paths to achieve improved throughput and robustness against network failure. These features are supposed to make MPTCP preferable to single-path TCP in mobile networks. However, it fails to achieve the expected performance in practice. A key challenge of using MPTCP in mobile networks is how to effectively spread packets over heterogeneous and unstable network paths to mobile devices with limited buffers. If packets are not sent in an effective way, MPTCP may only provide equal or even lower throughput than single-path TCP. Several packet scheduling algorithms have been designed to tackle this challenge. Unfortunately, they still cannot achieve the expected performance in dynamic scenarios such as mobile networks. In this paper, we propose an Online-Learning Assisted Packet Scheduler (OLAPS) to solve the packet scheduling problem by modeling it as a multi-armed bandit problem. Over time, OLAPS can adaptively learn from current network conditions to make the best scheduling policy to provide the highest possible throughput in a dynamic environment. Moreover, when the inbuilt reward monitor detects the mismatch between network conditions and the learned policy, OLAPS aborts the outdated policy and switches to a new one swiftly. We implement OLAPS as a Linux kernel module and evaluate it over a wide range of ns-3 -simulated network conditions. The results show that OLAPS retains MPTCP’s ability to provide higher throughput and also significantly improves the throughput performance of MPTCP when other in-kernel schedulers suffer a dramatic throughput decline.

A QUIC (Quick UDP Internet Connections) protocol is designed to improve Hypertext Transfer Protocol (HTTP) traffic and carries a non-negligible portion of the traffic in the current Internet. As its extension, Multipath QUIC (MPQUIC) provides higher bandwidth and smoother network handover by using multiple network interfaces simultaneously. However, to improve HTTP traffic, there are still some issues not yet carefully addressed in the existing MPQUIC, and packet scheduling is a vital one among the issues. Specifically, existing methods fail to respond to the stream prioritization of HTTP Version 2 (HTTP/2), leading to unsatisfying web page load performance. Besides, managing asymmetric and dynamic network paths is also a challenging issue, which may result in Head-of-Line (HoL) blocking and excessive buffer usage if not effectively handled. In this paper, we present a stream-aware per-packet scheduler, HoL Blocking Eliminating Scheduler (HBES), to improve the performance of MPQUIC in mobile networks. Firstly, HBES provides a fair allocation of aggregated bandwidth for different streams based on their priority. Then, it keeps stream data arriving at the receiver in order by estimating packet arrival time to mitigate HoL blocking and excessive buffer usage. We implement HBES and evaluate its performance in various network scenarios. Experimental results verify the superiority of HBES in reducing stream completion time and buffer occupation over those existing MPQUIC schedulers.

As the voucher for identity, digital certificates and the public key infrastructure (PKI) system have always played a vital role to provide the authentication services. In recent years, with the increase in attacks on traditional centralized PKIs and the extensive deployment of blockchains, researchers have tried to establish blockchain-based secure decentralized PKIs and have made significant progress. Although blockchain enhances security, it brings new problems in scalability due to the inherent limitations of blockchain’s data structure and consensus mechanism, which become much severe for the massive access in the era of 5G and B5G. In this paper, we propose ScalaCert to mitigate the scalability problems of blockchain-based PKIs by utilizing redactable blockchain for "on-cert" revocation. Specifically, we utilize the redactable blockchain to record revocation information directly on the original certificate ("on-cert") and remove additional data structures such as CRL, significantly reducing storage overhead. Moreover, the combination of redactable and consortium blockchains brings a new kind of attack called deception of versions (DoV) attack. To defend against it, we design a random-block-node-check (RBNC) based freshness check mechanism. Security and performance analyses show that ScalaCert has sufficient security and effectively solves the scalability problem of the blockchain-based PKI system.

Under the assumption of honest-but-curious cloud service provider, various cryptographic techniques have been used to address the issues of data access control and confidentiality in public cloud storage. Among which, attribute-based encryption (ABE) has been shown to be an attractive scheme. Although the technique of ABE brings in various benefits, its onerous overhead should not be ignored. In this article, based on an improved LSSS (linear secret sharing scheme) matrix expression integrated in CP-ABE (Ciphertext-Policy Attribute-Based Encryption) algorithm, we present an efficient and secure attribute-based access control scheme for the scenarios where multiple data are shared and encrypted with frequently used sub-policies. In the scheme, a user can store the parameters about a specific sub-policy in his/her first decryption, which can be reused in the subsequent data decryptions whose embedded access policies include the same sub-policy so as to significantly reduce the computation cost. Our proposed scheme is proved to be semantically secure under chosen plaintext attacks and can well preserve the confidentiality of the data sharing system. Our analysis and experimentation also show that our scheme does significantly reduce the decryption time and while trades in only very little storage overhead, and thus effectively promotes the efficiency.

As a new architecture of Internet infrastructure, Information-Centric Networking (ICN) is mainly designed to effectively handle the rapidly increasing user demand for content delivery through in-network caching. While facilitating the dissemination of content to users and making better use of the network resources, ICN is also vulnerable in that attackers can inject poisoned content into the network and isolate users from valid content sources. The introduction of signature verification in each router can effectively prevent this attack, but it also introduces great computation overhead. Existing schemes in ICN reduce verification overhead from a single routing perspective but do not consider integrating resources within ICN for collaborative content authentication and cyber self-defense. In this paper, we propose a collaborative, secure, and efficient content validation protection framework, named CSEVP, to implement a multi-router collaborative defense mechanism for ICN. On the one hand, we conduct content verification by probabilistically choosing one router involved in the transmission path to offload the computation overhead of content verification from a single router to multiple ones. On the other hand, we adopt bloom filters for routers to record and share verification results to further facilitate a more efficient content validity verification. The security and efficiency analysis shows that our proposed CSEVP can achieve efficient content validity verification among multiple routers with acceptable low communication and storage overhead.

As a promising implementation of Information-Centric Networking (ICN), Named Data Networking (NDN) has potential advantages over the TCP/IP network in content distribution, mobility support, etc. However, the research on NDN is still in its infancy, and congestion control, NDN’s most important functional element, poses many challenges, such as congestion detection, excessive window reduction for non-congested paths, and unfairness. In this paper, we propose an Intelligent Edge-Aided Congestion Control (IEACC) scheme for the NDN network based on Deep Reinforcement Learning (DRL). The proposed IEACC provides a proactive congestion detector that utilizes intermediate routers to transmit accurate congestion information along the path to consumers through data packets. Furthermore, considering the multi-source transmission in NDN, IEACC divides data packets into different congestion degrees by a lightweight clustering algorithm and provides suitable inputs for DRL, thereby obtaining a reasonable transmission rate. Then, it distributes the estimated bandwidth resources to consumers with transmission needs to maintain fairness. Finally, we implement our proposed scheme in the simulation platform and evaluate the performance in different scenarios. The results show that it can improve data transmission rate, reduce packet loss, and maintain fairness compared with others.

As one of the promising next generation network architectures, information centric networking (ICN) is highly anticipated to improve the bandwidth usage of the Internet and reduce duplicate traffic. Since contents in ICN are disseminated in the whole network, ICN is much more vulnerable and the issue of how to deliver contents securely has been intensively discussed. However, the scalability of the existing schemes is limited. A scalable scheme is expected to be able to achieve fine-grained access control and at the same time also support multiple content providers scenario with efficient key management at user side. Besides, different content providers may publish some identical contents and these contents may be cached in the same intermediate routers, which causes high data redundancy and in turn exerts an adverse impact on the performance of ICN. In this paper, we propose a Secure Content Delivery and Deduplication scheme, called SCD2, to achieve secure and efficient fine-grained access control in ICN with multiple content providers. We first propose a scalable key-policy attribute-based encryption (SKP-ABE) to provide fine-grained access control and allow different attribute authorities to share some public attributes to simplify the key management. Furthermore, based on SKP-ABE, we design a simple but effective mechanism to conduct content deduplication. Finally, we implement a prototype of SCD2 to test its performance and compare it with some existing schemes. The results show that SCD2 has lower storage overhead, a higher degree of deduplication, and better retrieval efficiency.

Recently, truth discovery in crowdsensing systems has received considerable attention with its appealing features for extracting truthful information from multiple unreliable data sources. However, it also poses new challenges to the issues of privacy and security. On the one hand, workers' sensed data can be used to infer their privacy. On the other hand, workers may be selfish and lazy, especially in the Internet-of-Things environment, devices are usually resource constrained, so they may dishonestly execute the costly sensing task so as to reduce resource consumption, or even break the protocol to obtain illegal rewards. Although some privacy-preserving truth discovery schemes have been proposed, they still cannot achieve strong privacy protection while keeping efficiency on the worker side, and still has no efficient incentive mechanism to persuade workers to participate in the system operations. In this article, we propose an incentive-based privacy-preserving truth discovery framework, named InPPTD. By adopting the Paillier homomorphic cryptosystem and two noncolluding servers, InPPTD not only effectively protects workers' sensed data information but also preserves the privacy of these workers' weight information. Meanwhile, a weight-based incentive mechanism is introduced in InPPTD to reduce the number of lazy workers. Security and performance analysis shows that InPPTD can guarantee stronger security features, while also ensure efficiency in terms of computation and communication overhead.

Inspired by Bitcoin, many different kinds of cryptocurrencies based on blockchain technology have turned up on the market. Due to the special structure of the blockchain, it has been deemed impossible to directly trade between traditional currencies and cryptocurrencies or between different types of cryptocurrencies. Generally, trading between different currencies is conducted through a centralized third-party platform. However, it has the problem of a single point of failure, which is vulnerable to attacks and thus affects the security of the transactions. In this paper, we propose a distributed cryptocurrency trading scheme to solve the problem of centralized exchanges, which can achieve secure trading between different types of cryptocurrencies. Our scheme is implemented with smart contracts on an Ethereum blockchain and deployed on an Ethereum test network. In addition to implementing transactions between individual users, our scheme also allows transactions among multiple users. The experimental result proves that the cost of our scheme is acceptable.

To reduce the duplicated traffic and improve the performance of distributing massive volumes of multimedia contents, in-network caching has been proposed recently. However, as in-network content caching can be directly utilized to respond users’ requests, multimedia content retrieval is beyond content providers’ control and makes it hard for them to implement access control and service accounting. In this paper, we propose a Fine-grained Accountable and Space-Efficient access control scheme, called FASE, for multimedia content distribution. FASE allows content providers to be fully offline while making the best of in-network caching. In FASE, the attribute-based encryption at multimedia content provider side and access policy based authentication at the edge router side jointly ensure secure fine-grained access control. Our scheme is efficient in both space and time. By designing one time chameleon signature (OTCS), users can keep anonymous during the authentication, and their privileges can be conveniently revoked when needed. Besides, secure service accounting is implemented by letting edge routers collect service credentials generated during users’ request process. Through formal security analysis, we prove the security of our scheme. Simulation results demonstrate that our scheme is efficient with acceptable overhead.

Multipath TCP (MPTCP) utilizes multiple paths for simultaneous data transmission to enhance performance. However, existing MPTCP protocols are still far from satisfactory in wireless networks because of their loss-based congestion control and the difficulty of managing multiple subflows. To overcome these problems, we redesign the coupled congestion control algorithm and scheduler to boost MPTCP in wireless heterogeneous networks. The main purpose is to promote transmission rate under lossy networks, while also provide stability when networks suffer physical link changes and asymmetric links. In this paper, inspired by Bottleneck Bandwidth and Round-trip propagation time (BBR), we first propose Coupled BBR that utilizes detected bandwidth to adjust the sending rate within an MPTCP connection. Coupled BBR provides high loss tolerance as well as balanced congestion among MPTCP subflows. Then, to further improve the performance, we propose an Adaptively Redundant and Predictive packet (AR&P) scheduler to improve adaptability and keep in-order packet delivery in highly dynamic network scenarios. Based on Linux kernel implementation and experiments in both testbed and real network scenarios, we show that the proposed scheme not only provides high throughput in wireless networks, but also improves robustness and reduces out-of-order packets in some harsh circumstances.

Deep learning as a service has been widely deployed to utilize deep neural network models to provide prediction services. However, this raises privacy concerns since clients need to send sensitive information to servers. In this paper, we focus on the scenario where clients want to classify private images with a convolutional neural network model hosted in the server, while both parties keep their data private. We present FALCON, a fast and secure approach for CNN predictions based on fast Fourier Transform. Our solution enables linear layers of a CNN model to be evaluated simply and efficiently with fully homomorphic encryption. We also introduce the first efficient and privacy-preserving protocol for softmax function, which is an indispensable component in CNNs and has not yet been evaluated in previous work due to its high complexity.

The Internet of Things (IoT) has set off a new information technology revolution due to its convenience and efficiency. An IoT enables sharing economy, as more people are willing to share their own things (mostly mobile devices) to leverage the under-used value. In such a situation where owners and users are often not familiar with each other, an efficient access control mechanism is needed to deal with the trust issue and support service accountability to help owners accurately get their deserved profits. Besides, in such a sharing economy environment, the mobility of most shared IoT devices and their privacy preserving should also be taken into account. Regrettably, the existing schemes cannot achieve all of the aforementioned goals simultaneously and only few schemes were implemented to evaluate the claimed performance. In this article, we propose an efficient, accountable, and privacy-preserving access control solution for IoT in a sharing economy environment. In our scheme, we utilize the one-time signature to achieve anonymous authentication and let gateways store the signatures as service credentials for accountability. Meanwhile, we adopt the identity-based authentication to exclude malicious gateways and shared devices from the system and design a specialized protocol for those devices moving with the users. We conduct a detailed security analysis to show that our scheme can effectively defend against potential attacks, and also implement a prototype system to demonstrate that our design is indeed an efficient one.

Secure data aggregation has been widely studied in the area of the smart grid. Many existing schemes have studied protecting user's privacy in data aggregation by using advanced cryptographic tools. However, they usually introduce a large computation burden to smart meters in limited computing power or require a trusted authority. How to ensure the efficiency on the user side while preserving user's privacy still has not been well addressed. In this article, we consider the scenario where there does not exist a trusted authority and users in the smart grid may dynamically change, and propose an efficient and robust data aggregation scheme without a trusted authority for the smart grid. Our proposed scheme not only ensures user's privacy and efficiency but also supports flexible dynamic user management with no need of involving a trusted authority. Analysis of security and performance shows that our scheme can guarantee stronger security features, while ensuring efficiency in terms of computation, communication, and storage overhead.

With the advances of Software-Defined Networks (SDN) and Network Function Virtualization (NFV), Service Function Chain (SFC) has been becoming a popular paradigm to carry and complete network services. Such new computing and networking paradigm enables Virtual Network Functions (VNFs) to be placed in software entities/virtual machines over a network of physical equipments in elastic and flexible way with low capital and operation expenses. VNFs are chained together to steer traffic as needed. However, most of the existing traffic steering and routing path computation algorithms for SFC are complex, unscalable, and low time-efficiency. In this paper, we study the VNF Selection and Chaining Problem (VNF-SCP) in SDN/NFV-enabled networks. We formulate VNF-SCP as a Binary Integer Programming (BIP) model in order to compute routing path for each SFC Request (SFCR) with the minimum end-to-end delay. Then, a novel Deep Learning-based Two-Phase Algorithm (DL-TPA) is introduced, where VNF selection network and VNF chaining network are designed to achieve intelligent and efficient VNF selection and chaining for SFCRs. Performance evaluation shows that DL-TPA can achieve high prediction accuracy and time efficiency of routing path computation, and the overall network performance can be improved significantly.

A key trend of current network evolution is in the direction of network softwarization and virtualization. These technological paradigms aim to enable a network to be programmable in a way that makes the network more flexible, scalable, and reliable, and in turn leads to agile service deployment and lower capital and operational expenses. So far, two related widely adopted solutions are software defined networks (SDN) and network function virtualization (NFV). There is one main difference between these two new networking paradigms. SDN separates the control plane from the data plane through a well-defined programming interface, such that the centralized controller can have a complete view of the entire network, while NFV decouples network functions from dedicated physical equipment by means of virtualization technology, and runs the virtual network functions (VNFs) in the general purpose physical or virtual network appliances. Both approaches make the network programmable in order to have the aforementioned desired features. SDN and NFV do not depend on each other, and they actually complement each other. They can work well individually and can also work in tandem for performance reasons. Due to such advantages, both SDN and NFV have become key enabling technologies for 5G networks, and have also been used in a wide range of important areas including IoT, mobile edge computing, smart grid, cloud datacenters, and cognition-based networks.

F2C (fog-to-cloud) enables service providers to rent the low-cost cloud/fog resources to publish their services, and the fog nodes, which are deployed at the edge, can provide short-latency service to users. However, new security threats come along with this new computing paradigm, where the access control and trusted payment are concerned in this work. We propose a privacy-preserving authentication scheme. By integrating k-times anonymous authentication (k-TAA) and attribute-based access control, in our proposed scheme, service providers can autonomously determine a fine-grained access policy and the maximal access times for authorized users. Thus, users who satisfy the access policy can receive benefits of this service for certain number of times without leaking any private information. Our authentication phase has a low latency because it is offloaded to the fog as what the service does. This paper presents a lightweight and trusted billing mechanism using Merkle Hash Tree (MHT), which can detect the cloud's service forgery with high probability, without costing too much of service provider's bandwidth and computation. Rigorous security analysis proves that the proposed scheme is secure against malicious users, fogs, and cloud, and the experimental results show the significant performance advantage on both the delay reduction and service providers' cost saving.

Smart grid adopts two-way communication and rich functionalities to gain a positive impact on the sustainability and efficiency of power usage, but on the other hand, also poses serious challenges to customers' privacy. Existing solutions in smart grid usually use cryptographic tools, such as homomorphic encryption, to protect individual privacy, which, however, can only support limited and simple functionalities. Moreover, the resource-constrained smart meters need to perform heavy asymmetric cryptography in these solutions, and thus unnecessarily increases load on smart grid. In this paper, we present a practical and secure SGX-enabled smart grid system, named SecGrid. Our system leverages trusted hardware SGX to ensure that grid utilities can efficiently execute rich functionalities on customers' private data, while guaranteeing their privacy. With our well-devised security protocols in SecGrid, only the smart meters need to perform AES encryption. To validate the superiority of our design, we conduct security analysis and experimentation. Security analysis shows that SecGrid can thwart various attacks from malicious adversaries, and the experimental results show that SecGrid is much faster than the existing privacy-preserving schemes in smart grid.

In order to be TCP-friendly, the original Multipath TCP (MPTCP) congestion control algorithm is always restricted to gain no better throughput than a traditional single-path TCP on the best path. However, it is unable to maximize the throughput over all available paths when they do not go through a shared bottleneck. Also, bottleneck fairness based solutions detect the bottleneck and conduct different congestion control algorithms at different bottleneck sets to increase throughput while remaining fair to single TCP. However, existing solutions generally detect shared bottlenecks through delay correlation and loss correlation between two flows, which often lead to misjudgement in dynamic and complex network scenarios. Therefore, in this paper, we first propose a new Shared Bottleneck based Congestion Control scheme, called SB-CC, which leverages ECN (Explicit Congestion Notification) mechanism to detect shared bottlenecks among subflows and estimate the congestion degree of each subflow. Then, with the congestion degree, SB-CC balances the loads among all subflows, and smooths out congestion window fluctuation. Also, in order to prevent throughput degradation due to out-of-order packets, we propose a Shared Bottleneck based Forward Prediction packet Scheduling scheme, called SB-FPS. SB-FPS distributes data according to the window size changes of each subflow, and thus could more accurately schedule data in shared bottleneck scenarios. We implement our proposed scheme in the Linux kernel and simulation platform to evaluate the performance in different scenarios. Measurement results indicate that our scheme can detect the bottleneck more accurately and improve the overall network performance while still keeping bottleneck fairness.

The new paradigm of outsourcing data to the cloud is a double-edged sword. On the one hand, it frees data owners from the technical management, and is easier for data owners to share their data with intended users. On the other hand, it poses new challenges on privacy and security protection. To protect data confidentiality against the honest-but-curious cloud service provider, numerous works have been proposed to support fine-grained data access control. However, till now, no schemes can support both fine-grained access control and time-sensitive data publishing. In this paper, by embedding timed-release encryption into Ciphertext-Policy Attribute-based Encryption (CP-ABE), we propose a new time and attribute factors combined access control on time-sensitive data for public cloud storage (named TAFC). Based on the proposed scheme, we further propose an efficient approach to design access policies faced with diverse access requirements for time-sensitive data. Extensive security and performance analysis shows that our proposed scheme is highly efficient and satisfies the security requirements for time-sensitive data storage in public cloud.

In order to cope with the explosive growth of mobile traffic, many traffic offloading schemes such as heterogenous networks have been developed to enhance network capacity of the Radio Access Network (RAN). Among them, networking of Low-Earth Orbit (LEO) satellites promises to significantly improve the RAN performance due to its economical prospect and advantages in high bandwidth and low latency. In this paper, by introducing the cache-enabled LEO satellite network as a part of RAN, we propose an integrated satellite/terrestrial cooperative transmission scheme to enable an energy-efficient RAN by offloading traffic from base stations through satellite's broadcast transmission. Considering energy-constraints of satellites, we then formulate a nonlinear fractional programming problem aiming at optimizing transmission energy efficiency of the system. In order to effectively solve this problem, we transform it into an equivalent one, and then adopt iteration and sub-problem decomposition to obtain the optimal solution for each optimization variable, i.e., block placement, power allocation, and cache sharing variable. Numerical results show that compared with traditional terrestrial scheme, our cooperative transmission scheme achieves significant performance improvement in terms of traffic offloading and energy efficiency, especially in an environment of high request consistency degree.

With rapid advances in satellite technology, space information network (SIN) has been proposed to meet the increasing demands of ubiquitous mobile communication due to its advantages in providing extensive access services. However, due to satellites' resource constraint and SIN's highly dynamic topology, it poses a challenge on management and resource utilization in the development of SIN. There have been some works integrating the software defined network (SDN) into SIN, defined as software defined space information network (SD-SIN), so as to simplify the management and improve resource utilization in SIN. However, these works ignore the security issue in SD-SIN. Meanwhile, the existing security mechanisms in SDN are still unable to cope with the uniqueness of satellite network, and some other critical security issues still haven't yet been well addressed. In this paper, based on (t,n) secret sharing, an SIN-specific lightweight group key agreement protocol is proposed for SD-SIN to ensure both the security and applicability. Moreover, considering the highly dynamic network topology, we also design a group key-based secure handover authentication scheme to reduce the overhead of handover authentication. Security analysis shows that the handover authentication protocol can resist to various known attacks. In addition, further performance evaluation shows its efficiency in terms of computation and communication overheads. Finally, the simulation results of computing overhead to the network entities demonstrate that our protocol is feasible in practical implementation.

Information Centric Networking (ICN), a new paradigm of Internet infrastructure, aims to better accommodate users' rapid growing demand for content delivery and optimize bandwidth utilization. Although the in-network cache feature of ICN facilitates the dissemination of content to users, it also poses new challenges on access control for content and network resource. Moreover, it is common that the access privilege of content dynamically change over time. However, existing access control mechanisms in ICN cannot support the publication and distribution of such time-sensitive content. In this paper, we propose a time- sensitive, lightweight, and secure access control mechanism, called TSLS, to solve this problem. We introduce broadcast encryption combined with time tokens for content providers to protect content confidentiality, and only authorized users satisfying the time limitation have capability to decrypt and access the content. Besides, a fast lightweight challenge-response verification is implemented at the edge routers to block unauthorized request from injecting into the network. The responses of authorized users are forwarded to content providers for pre-distribute popular content at in-network caches in advance. Our security analysis shows that TSLS possesses the properties of data confidentiality, unforgeability, anonymity, and DoS/DDoS attacks resistance. Our simulation results indicate that our proposed TSLS is an efficient mechanism with low computation cost and network delay.

Space information network (SIN) makes it possible for any object to be connected to the Internet anywhere, even in the areas with extreme conditions, where a cellular network is not easy to deploy. Access authentication is the key to secure users' access control in SIN, mainly to prevent illegal adversaries from getting access to SIN services. However, the highly complicated communication environment of SIN (e.g., exposed links, higher signal delay, etc.) poses a challenging issue in the design of a secure and efficient authentication scheme. Although some authentication schemes have been proposed for SIN, they are unsuitable for Internet of Things (IoT) in SIN due to the high signaling overhead and insufficient security properties. Therefore, in this paper, we design a provably secure and efficient authentication protocol, along with an efficient handover mechanism, for IoT in SIN. In our design, we introduce a new authentication system model, where the satellites are given the ability to authenticate users to avoid the online involvement of the network control center (NCC) when authenticating users, thereby reducing long authentication delay and avoiding a single point of bottleneck in NCC. Furthermore, the support of batch verification in our design can significantly enhance handover efficiency when a group of users switch to another satellite. Our further analysis shows that our scheme is secure against various attacks and can meet a variety of security requirements. In addition, performance evaluation shows the superiority of our scheme on both delay and handover efficiency compared with existing schemes.

In power utility service outsourcing, some time-sensitive computations (e.g., dynamic prices prediction) are outsourced to a third-party service provider. This brings in new privacy threats to customers. Although some existing works focus on achieving privacy-preserving temporal and spatial aggregation for one center, they basically cannot be directly applied to the scenario of service outsourcing with multiple centers (e.g., with power utility and service providers). We thus propose a privacy-preserving service outsourcing scheme, called PPSO, for real-time pricing demand response in smart grid with fault tolerance and flexible customers' enrollment and revocation. In our proposed PPSO, power utility can outsource the dynamic pricing prediction to a service provider, while still preserving customers' privacy. Extensive experiment results demonstrate that PPSO has less computation overhead and lower transmission delay compared with existing schemes.

In public cloud storage services, data are outsourced to semi-trusted cloud servers which are outside of data owners' trusted domain. To prevent untrustworthy service providers from accessing data owners' sensitive data, outsourced data are often encrypted. In this scenario, conducting access control over these data becomes a challenging issue. Attribute-based encryption (ABE) has been proved to be a powerful cryptographic tool to express access policies over attributes, which can provide a fine-grained, flexible, and secure access control over outsourced data. However, the existing ABE-based access control schemes do not support users to gain access permission by collaboration. In this paper, we explore a special attribute-based access control scenario where multiple users having different attribute sets can collaborate to gain access permission if the data owner allows their collaboration in the access policy. Meanwhile, the collaboration that is not designated in the access policy should be regarded as a collusion and the access request will be denied. We propose an attribute-based controlled collaborative access control scheme through designating translation nodes in the access structure. Security analysis shows that our proposed scheme can guarantee data confidentiality and has many other critical security properties. Extensive performance analysis shows that our proposed scheme is efficient in terms of storage and computation overhead.

Information centric networking (ICN) has been regarded as an ideal architecture for the next-generation network to handle users' increasing demand for content delivery with in-network cache. While making better use of network resources and providing better service delivery, an effective access control mechanism is needed due to the widely disseminated contents. However, in the existing solutions, making cache-enabled routers or content providers authenticate users' requests causes high computation overhead and unnecessary delay. Also, the straight-forward utilization of advanced encryption algorithms makes the system vulnerable to DoS attacks. Besides, privacy protection and service accountability are rarely taken into account in this scenario. In this paper, we propose SEAF, a secure, efficient, and accountable edge-based access control framework for ICN, in which authentication is performed at the network edge to block unauthorized requests at the very beginning. We adopt group signature to achieve anonymous authentication and use hash chain technique to reduce greatly the overhead when users make continuous requests for the same file. At the same time, we provide an efficient revocation method to make our framework more robust. Furthermore, the content providers can affirm the service amount received from the network and extract feedback information from the signatures and hash chains. By formal security analysis and the comparison with related works, we show that SEAF achieves the expected security goals and possesses more useful features. The experimental results also demonstrate that our design is efficient for routers and content providers and bring in only slight delay for users' content retrieval.

Information Centric Networking (ICN) has been regarded as an ideal architecture for the next-generation network to handle users' increasing demand for content delivery with in-network cache. While making better use of network resources and providing better delivery service, an effective access control mechanism is needed due to wide dissemination of contents. However, in the existing solutions, making cache-enabled routers or content providers authenticate users' requests causes high computation overhead and unnecessary delay. Also, straightforward utilization of advanced encryption algorithms increases the opportunities for DoS attacks. Besides, privacy protection and service accountability are rarely taken into account in this scenario. In this paper, we propose a secure, efficient, and accountable access control framework, called SEAF, for ICN, in which authentication is performed at the network edge to block unauthorized requests at the very beginning. We adopt group signature to achieve anonymous authentication, and use hash chain technique to greatly reduce the overhead when users make continuous requests for the same file. Furthermore, the content providers can affirm the service amount received from the network and extract feedback information from the signatures and hash chains. By formal security analysis and the comparison with related works, we show that SEAF achieves the expected security goals and possesses more useful features. The experimental results also demonstrate that our design is efficient for routers and content providers, and introduces only slight delay for users' content retrieval.

Attribute-based encryption (ABE) has opened up a popular research topic in cryptography over the past few years. It can be used in various circumstances, as it provides a flexible way to conduct fine-grained data access control. Despite its great advantages in data access control, current ABE based access control system cannot satisfy the requirement well when the system judges the access behavior according to attribute comparison, such as “greater than x” or “less than x”, which are called comparable attributes in this paper. In this paper, based on a set of well-designed sub-attributes representing each comparable attribute, we construct a comparable attribute-based encryption scheme (CABE for short) to address the aforementioned problem. The novelty lies in that we provide a more efficient construction based on the generation and management of the sub-attributes with the notion of 0-encoding and 1-encoding. Extensive analysis shows that: Compared with the existing schemes, our scheme drastically decreases the storage, communication and computation overheads, and thus is more efficient in dealing with the applications with comparable attributes.

In cloud computing, the performance of applications is heavily dependent on resource services provided by the virtualized environment. However, in some virtualized environment, such as Xen, the accuracy of CPU proportional share and the responsiveness of I/O processing are heavily dependent on the proportion of the allocated CPU resource. In this paper, we study how inaccurate share ratio of CPU proportional share and proportion dependent responsiveness of I/O affect the performance of Xen, and discover that they lead to unstable performance and is thus not able to conform service-level agreements (SLA). We conclude that the scheduling scheme and the coarse grained time-slice are the major negative impacts on this issue. Therefore, we propose a novel scheduling scheme, named Predictable Resource Guarantee Scheduler (PRGS), that achieves accurate CPU proportional share and predictable I/O responsiveness. We implement a PRGS prototype on Xen virtualization platform and carry out a thorough evaluation via experimentation. The experimental results show that PRGS achieves accurate CPU proportional share and predictable I/O responsiveness. Also, with only slight overhead, PRGS controls PING packet delay to a specified fixed time threshold (e.g. 30 ms in our experiments).

Live forensics is an important technique in cloud security but is facing the challenge of reliability. Most of the live forensic tools in cloud computing run either in the target Operating System (OS), or as an extra hypervisor. The tools in the target OS are not reliable, since they might be deceived by the compromised OS. Furthermore, traditional general purpose hypervisors are vulnerable due to their huge code size. However, some modules of a general purpose hypervisor, such as device drivers, are indeed unnecessary for forensics. In this paper, we propose a special purpose hypervisor, called ForenVisor, which is dedicated to reliable live forensics. The reliability is improved in three ways: reducing Trusted Computing Base (TCB) size by leveraging a lightweight architecture, collecting evidence directly from the hardware, and protecting the evidence and other sensitive files with Filesafe module. We have implemented a proof-of-concept prototype on the Windows platform, which can acquire the process data, raw memory, and I/O data, such as keystrokes and network traffic. Furthermore, we evaluate ForenVisor in terms of code size, functionality, and performance. The experiment results show that ForenVisor has a relatively small TCB size of about 13 KLOC, and only causes less than 10 percent performance reduction to the target system. In particular, our experiments verify that ForenVisor can guarantee that the protected files remain untampered, even when the guest OS is compromised by viruses, such as `ILOVEYOU' and Worm.WhBoy. Also, our system can be loaded as a hypervisor without needing to pause the target OS. This allows it to not only avoid destructing but also to gather the live evidence of the target OS. We also posted the source code of ForenVisor on Github.

Data access control is a challenging issue in public cloud storage systems. Ciphertext-policy attribute-based encryption (CP-ABE) has been adopted as a promising technique to provide flexible, fine-grained, and secure data access control for cloud storage with honest-but-curious cloud servers. However, in the existing CP-ABE schemes, the single attribute authority must execute the time-consuming user legitimacy verification and secret key distribution, and hence, it results in a single-point performance bottleneck when a CP-ABE scheme is adopted in a large-scale cloud storage system. Users may be stuck in the waiting queue for a long period to obtain their secret keys, thereby resulting in low efficiency of the system. Although multi-authority access control schemes have been proposed, these schemes still cannot overcome the drawbacks of single-point bottleneck and low efficiency, due to the fact that each of the authorities still independently manages a disjoint attribute set. In this paper, we propose a novel heterogeneous framework to remove the problem of single-point performance bottleneck and provide a more efficient access control scheme with an auditing mechanism. Our framework employs multiple attribute authorities to share the load of user legitimacy verification. Meanwhile, in our scheme, a central authority is introduced to generate secret keys for legitimacy verified users. Unlike other multi-authority access control schemes, each of the authorities in our scheme manages the whole attribute set individually. To enhance security, we also propose an auditing mechanism to detect which attribute authority has incorrectly or maliciously performed the legitimacy verification procedure. Analysis shows that our system not only guarantees the security requirements but also makes great performance improvement on key generation.

Symmetric Multi-Processing (SMP) virtual machine (VM), or virtual SMP for short, enables a single virtual machine to span multiple processors, thereby supporting the virtual machine to run resource-intensive applications. In addition to offering higher computing capacity, virtual SMP also offers the opportunity to alleviate the problem of unpredictable I/O responsiveness. To this end, we propose vINT (scheduling status based virtual INterrupt remapping adapTer), a scheme that leverages hardware-assisted interrupt mapping. vINT obtains high efficiency and flexibility by adding a lightweight module in virtual machine monitor (VMM) with no need of changing VMM scheduler and is transparent to guest OS. We implement the prototype in XEN 4.3.0 and conduct evaluations with both micro-benchmarks and macro-benchmarks. The experimental results show that vINT can increase the networking throughput by 5x and can reduce the required execute time of disk I/O by 17.5%, while introducing only a light overhead.

Mobile crowd-sensing applications produce useful knowledge of the surrounding environment, which makes our life more predictable. However, these applications often require people to contribute, consciously or unconsciously, location-related data for analysis, and this gravely encroaches users' location privacy. Aggregate processing is a feasible way for preserving user privacy to some extent, and based on the mode, some privacy-preserving schemes have been proposed. However, existing schemes still cannot guarantee users' location privacy in the scenarios with low density participants. Meanwhile, user accountability also needs to be considered comprehensively to protect the system from malicious users. In this paper, we propose a participant-density-aware privacy-preserving aggregate statistics scheme for mobile crowd-sensing applications. In our scheme, we make use of multi-pseudonym mechanism to overcome the vulnerability due to low participant density. To further handle sybil attacks, based on the Paillier cryptosystem and non-interactive zero-knowledge verification, we advance and improve our solution framework, which also covers the problem of user accountability. Finally, the theoretical analysis indicates that our scheme achieves the desired properties, and the performance experiments demonstrate that our scheme can achieve a balance among accuracy, privacy-protection and computational overhead.

A non-collaborative coexistence mechanism for wireless-fidelity (Wi-Fi) and bluetooth (BT) systems based on dynamic packet fragmentation is proposed in this work. The basic idea is to adapt the packet length of Wi-Fi in the MAC layer such that the fragmented packet has a better chance to survive the interference from the nearby BT devices. We first develop an analytical model that specifies the information required by the Wi-Fi MAC layer to decide the best fragmentation strategy. Then, this model is extended to analyze the throughput and transmission delay of the Wi-Fi device. The analytical model is validated by computer simulation. Furthermore, it is demonstrated by simulation results that the proposed coexistence mechanism improves the performance of Wi-Fi in throughput and transmission delay significantly while relatively smaller performance improvement is observed for BT.

C LOUD computing is the future but it will not be if users' security concerns remain unaddressed.Cloud security issues include data privacy, data integrity, and service availability, among others.Due to the extra computing involved, security controls often incur a certain amount of performance degradation in cloud computing where performance is crucial and its computation and communication complexities are already high.This poses challenges to system developers with regards to preventing privacy leaks, performing data auditing, and guaranteeing high availability in the face of various security attacks.On the other hand, should the task of addressing these security issues be solely placed on the shoulders of the cloud service providers, or indeed should both the service providers and the service users be responsible for this task?A number of studies have been carried out that investigate the fundamental properties of cloud security issues, including data auditing, searchable data encryption, hypervisor protection, cloud forensics, and disaster recovery, to name but a few.In fact, cloud security is driving how we define and develop cloud computing solutions.The objective of this special issue is to provide a forum for researchers working on cloud security to present their recent research results.This special issue attracted 58 submissions of high quality research from around the world.Through a rigorous review process, the following 10 papers were selected for publication.These papers present results of analysis, experimentation, simulation, advanced theories, and system implementation.More specifically, they cover the topics of Operating System (OS) Fingerprinting, Side-Channel Attacks, Attribute-Based Signatures (ABSs), Fuzzy Authorization for Cloud Storage, Secure Software-Defined Network (SDN) Architecture for Cloud, Self-Destructing Data, Secure Group Data Sharing, Data Access Control for Peer-to-Peer Storage Cloud, SQL Operations on Encrypted Data, and Linear Regression

In this paper, we study data gathering in wireless sensor networks where intermediary nodes perform data aggregation with total fusion. We focus on gathering tree construction (from a general network topology) and transmission scheduling in order to minimize gathering delay. We first propose an algorithm that calculates an optimal transmission schedule and the minimal delay, for any given gathering tree. Then, we prove a lower bound, in terms of the number of nodes in the network, on the optimal gathering delay for any graph. After analyzing the gathering trees formed by several popular tree constructing algorithms, we propose an algorithm that constructs the optimal gathering tree for a complete graph. We then conduct extensive simulations to show that the proposed algorithm is also a promising approximation algorithm for arbitrary graphs. We also propose an approximation algorithm that constructs a gathering tree that achieves a maximum-degree-optimal solution.

The articles in this special section focus on new applications that are supported by cloud computing.

The performance of several unstructured peer-to- peer (P2P) content discovery techniques over ad hoc networks was analyzed in this work. They include: query flooding, expanding ring search, random walk and Bloom filter(BF)-based probabilistic routing. The chosen performance metrics are the query success rate, the route stretch and the search cost. Mathematic analysis is conducted to predict their behavior in static ad hoc networks. Finally, extensive computer simulations is performed to validate our analytical results in the ad hoc network. It is concluded that the BF-based probabilistic routing outperforms flooding-based and random walk schemes in finding a good balance among various performance metrics. Its only potential disadvantage is that the control packet size increases as the number of shared objects increases, which may not impose a severe constraint on a middle-sized ad hoc network.

In this paper, we present an enhanced adaptive frequency hopping (EAFH) mechanism for improving the performance of frequency hopping-based wireless personal area networks (WPANs) under frequency-static and frequency-dynamic interference. The proposed mechanism monitors the overall packet error rate (PER) of the system to determine the right number of channels to be excluded from the hopset. Then based on the PER of individual channel, it decides whether to exclude a certain channel or not. Finally, proper packet length is associated with those channels remaining in the hopset. These decisions, which pertain to hopset size and packet length, are made so as to optimize the performance of the hopping system in a coexistence environment. We developed an analytical model to justify the behavior and performance of the proposed mechanism. Simulations are conducted under an environment of some collocated Bluetooth (BT) piconets and a Wi-Fi network to validate the developed model and show the superiority of EAFH. Simulation results show that, compared with those existing mechanisms including orthogonal hopset-based mechanisms, EAFH could provide much higher throughput while still maintaining reasonably good channel occupancy.

Dynamic spectrum access (DSA) is the key feature of cognitive radio (CR) networks, but it also poses many new challenges on the medium access control (MAC) design. One of key challenges is the fact that the secondary CR users can only borrow the licensed spectrum from the primary users for a short period of time. Hence, unlike many available multi-channel MAC protocols for ad hoc networks where throughput is the main performance issue, the DSA protocols in CR networks shall place more emphases on the access latency. Hence, one fundamental issue arises: how can the spectrum be dimensioned for control channels in order to minimize the access delay of DSA protocol in CR networks? In this paper, we provide a comparative study in an analytical manner on the latency performance of two DSA protocols: 1) dedicated control channel, and 2) embedded dedicated control channel approaches. Our results show that an optimal ratio of the control channel bandwidth over the total channel bandwidth can be found to minimize the latency of DSA with dedicated control channels. However, the delay performance of DSA with dedicated control channels is more sensitive to the variations of the data lengths than that of DSA with embedded control channels. Hence, we conclude that the way of dimensioning the spectrum for control frames for DSA in CR networks should be adaptive to the variations of the traffic characteristics and the number of users.

The MAC protocol of a cognitive radio (CR) device should allow it to access unused or under-utilized spectrum without (or with minimal) interference to primary users dynamically. To fulfill such a goal, we propose a cognitive MAC protocol using statistical channel allocation and call it SCA-MAC in this work. SCA-MAC is a CSMA/CA-based protocol, which exploits statistics of spectrum usage for decision making on channel access. For each transmission, the sender negotiates with the receiver on transmission parameters through the control channel. A model is developed for CR devices to evaluate the successful rate of transmission. A CR device should pass the threshold of the successful transmission rate via negotiation before it can begin a valid transmission on data channels. The operating range and channel aggregation are two control parameters introduced to maintain the MAC performance. To validate our ideas, we conducted theoretical analysis and simulations to show that SCA-MAC does improve the throughput performance and guarantee the interference to incumbents to be bounded by a predetermined acceptable rate. The proposed MAC protocol does not need a centralized controller, as the negotiation between the sender and the receiver is performed using the CSMA/CA-based algorithm.

An efficient anonymous communication protocol, called MANET Anonymous Peer-to-peer Communication Protocol (MAPCP), for P2P applications over mobile ad-hoc networks (MANETs) is proposed in this work. MAPCP employs broadcasts with probabilistic-based flooding control to establish multiple anonymous paths between communication peers. It requires no hop-by-hop encrypt ion/decryption along anonymous paths and, hence, demands lower computational complexity and power consumption than those MANET anonymous routing protocols. Since MAPCP builds multiple paths to multiple peers within a single query phase without using an extra route discovery process, it is more efficient in P2P applications. Through analysis and extensive simulations, we demonstrate that MAPCP always maintains a higher degree of anonymity than a MANET anonymous single-path routing protocol in a hostile environment. Simulation results also show that MAPCP is resilient to passive attacks.

The twenty-one papers in this special issue are devoted to peer-to-peer communications and their applications. Covers such topics as: overlay networks, searching, video streaming, files and servers, and theories and applications.

Wireless ad hoc networks are drawing increasing attention from the research community because of their potential applications. However, the fundamental capacity limits of these networks pose various technological challenges to designers of network protocols. In this paper, we attempt to capture the inherent constraints on information dissemination in a mobile wireless environment, with the emphasis on peer-to-peer (P2P) communications. More specifically, we introduce the notion of "replication-induced gain" to quantify the impact of data replication under the paradigm of P2P query-response mechanisms. Our major contribution lies in presenting several preliminary results with respect to the complexities and trade-offs involved in enhancing data availability. To the best of our knowledge, the data replication problems that arise because of scarce system resources in wireless ad hoc networks have not been investigated from this perspective. We believe that our results could provide additional insights and practical implications for P2P system designers.

An efficient anonymous communication protocol, called MANET anonymous peer-to-peer communication protocol (MAPCP), for P2P applications over mobile ad-hoc networks (MANETs) is proposed in this work. MAPCP employs broadcasts with probabilistic flooding control to establish multiple anonymous paths between communication peers. It requires no hop-by-hop encryption/decryption along anonymous paths and, hence, demands lower complexity of computation and power consumption than other anonymous routing protocols for MANETs. Since MAPCP builds multiple paths to multiple peers within a single query phase without using an extra route discovery process, it is more efficient in P2P applications. Through analysis and extensive simulations, we demonstrate that MAPCP always maintains a higher degree of anonymity than a MANET anonymous single-path routing protocol in a hostile environment. Simulation results also show that MAPCP is resilient to passive attacks in data forwarding for both one-to-one and one-to-many communications.

A power-aware approach in the context of topology control that allows the power consumption to be evenly distributed among network nodes, and thereby prolongs the network lifetime, is proposed in this research. Unlike power-aware routing schemes, where exact traffic flow and residual energy level of each node are required, our power-aware topology control only requires the residual energy levels and location information of the reachable neighboring nodes. When a node is making a decision on whether a wireless link between itself and a reachable neighboring node should be preserved in the topology being constructed, the decision is made based on not only the distance from its neighboring nodes but also the residual energy levels of itself and its neighboring nodes. Also, the topology is restructured from time to time based on the residual energy level of each node. The performance improvement by our power-aware topology control algorithm is shown through extensive simulations

In a Bluetooth piconet, the Master essentially controls the channel. Due to an absence of coordination between independent Masters while accessing the wireless medium, devices will encounter high packet interference if several piconets are simultaneously operating in the same area. Since even a headset and a mobile phone can be connected with a Bluetooth link forming a piconet, it may not be unusual to find tens of independent piconets in crowded places like airports, international conferences, shopping malls, and so on. Study of packet interference is important because interference affects the throughput of a piconet. Motivated by the fact that applications will benefit, in terms of higher available data rate in one direction, by using multiple-slot packets in an asymmetric manner, in this paper, we present an analytical model of packet interference in a cluster of piconets using multiple-slot packets. Also, considering that all the portable devices can have a Bluetooth interface and people are highly mobile these days, it will not be uncommon to find a cluster of piconets of both the 79-hop and the 23-hop types in the same area. We then present an analytical model of interference of multiple-slot packets in a heterogeneous cluster of Bluetooth piconets. By a heterogeneous cluster we mean some piconets are of the 23-hop type and the rest are of 79-hop type. We show how the aggregate throughput in a cluster of piconets degrade under various traffic scenarios, such as 1-slot, 3-slot, and 5-slot packets in symmetric and asymmetric modes in synchronous and asynchronous conditions of Master clocks. Our analytic model is based on the idea of probabilistic graphs, where a node denotes a piconet and an edge denotes the probability of interference between two nodes. Though the 23-hop system has been phased out, our work gives a general approach to model packet interference in multiple, frequency-hopping systems that need not be Bluetooth systems.

Study of packet interference is important because interference affects the throughput of a piconet. Motivated by the fact that applications will benefit, in terms of higher available data rate in one direction, by using multiple-slot packets in an asymmetric manner, in this paper, we present an analytical model of packet interference in a cluster of piconets using multiple-slot packets. Also, considering that all the portable devices can have a Bluetooth interface and people are highly mobile these days, it will not be uncommon to find a cluster of piconets of both the 79-hop and the 23-hop types in the same area. We then present an analytical model of interference of multiple-slot packets in a heterogeneous cluster of Bluetooth piconets. By a heterogeneous cluster we mean some piconets are of the 23-hop type and the rest are of 79-hop type. We show how the aggregate throughput in a cluster of piconets degrade under various traffic scenarios, such as 1-slot, 3-slot, and 5-slot packets in symmetric and asymmetric modes in synchronous and asynchronous conditions of master clocks. Our analytic model is based on the idea of probabilistic graphs, where a node denotes a piconet and an edge denotes the probability of interference between two nodes.

In this paper, we present a reservation-based medium access control (MAC) protocol with multicast support for wavelength-division multiplexing networks. Our system is based on the single-hop, passive optical star architecture. Of the available wavelengths (channels), one channel is designated as a control channel, and the remaining channels are used for data transmission. Each node is equipped with a pair of fixed transceiver to access the control channel, and a fixed transmitter and a tunable receiver to access data channels. For easy implementation of the protocol in hardware and for precisely computing the protocol's processing overhead, we give a register-transfer model of the protocol. We simulate the protocol to study its throughput behavior, and present its analytic model. For a node to be able to send data packets in successive data slots with no time gap between them, in spite of the situation that the protocol's execution time may be longer than data transmission time, we propose the idea of multiple MAC units at each node. Unicast throughput of our protocol reaches the theoretically possible maximum throughput for MAC protocols with distributed control, and the multicast throughput is at least as good as, and even better than, those delivered by existing MAC protocols with distributed control.

In this paper, we present a localized algorithm for constructing power efficient topology for wireless ad hoc networks. Each mobile node determines its own transmission power based only on local information. The proposed algorithm first constructs the constrained Gabriel graph from the given unit disk graph and then reduces the total transmission power by allowing each node individually excises some replaceable links. The constructed topology is sparse, has a constant bounded power stretch factor, and the total transmission power is lower than those obtained from other proposed algorithms. In addition, compared with others, our algorithm requires lower time complexity to generate a solution, and can thus further save the energy for each mobile node. We demonstrate the performance improvements of our algorithm through simulations.

The desired properties of a medium access control (MAC) protocol in mobile ad hoc network (MANET) include: (1) meet quality of service (QoS) requirements for real-time nodes, (2) be decentralized, (3) achieve fairness from viewpoint of throughput or energy consumption, and (4) be immune to the hidden node problem. Though there have been numerous proposed MAC protocols for the IEEE 802.11 WLAN, few of them possess all of the four properties mentioned above. Our protocol can support real-time traffic and satisfy QoS requirements, and can achieve fairness among non-real-time nodes. Also, without using any centralized control, it can be easily deployed in MANET. An analytic model of the protocol's throughput has also been developed. We compare the protocol's throughput obtained from its analytic model and simulation to validate each other.

We propose a reservation based multicast protocol for the single-hop passive optical star network. Of the available wavelengths (channels), one channel is designated as a control channel, and the remaining channels are used for data transmission. A node accesses the control channel using a fixed transmitter and a fixed receiver. A node sends data packets using a fixed transmitter and receives packets through a tunable receiver (filter). All the channels are viewed as sequences of frames. In addition, frames of the control channel are further divided into mini slots. Corresponding to each node in the network, there is a mini slot in a control frame. A node puts its multicast request in its designated mini slot in a control frame. At the end of a control frame, all nodes receive the multicast requests of all other nodes, and decide which nodes are going to transmit and/or receive during the following data slot. An easily implementable way of resolving destination and source conflicts is presented. We simulate the protocol to study its throughput behavior, and present its analytic model. Simulation results show that our protocol delivers maximum unicast throughput, and the protocol's multicast throughput is much better than existing protocols using a control channel.

In this paper, we first show that the degree four Cayley graph proposed in a paper appearing in the January 1996 issue of IEEE Transactions on Parallel and Distributed Systems is indeed isomorphic to the wrapped butterfly. The isomorphism was first reported by Muga and Wei in the proceedings of PDPTA '96. The isomorphism is shown by using an edge-preserving bijective mapping. Due to the isomorphism, algorithms for the degree four Cayley graph can be easily developed in terms of wrapped butterfly and topological properties of one network can be easily derived in terms of the other. Next, we present the first optimal oblivious one-to-one permutation routing scheme for these networks in terms of the wrapped butterfly. Our algorithm runs in time O(/spl radic/N), where N is the network size.

We consider the problems of routing and sorting on a de Bruijn network. First, we show that any deterministic oblivious routing scheme for permutation routing on a d-ary de Bruijn network with N=d/sup n/ nodes, in the worst case, will take /spl Omega/(/spl radic/N) steps under the single-port model. This improves the existing lower bounds provided d is not a constant. We also show that the lower bound is indeed a tight one. Second, we present a deterministic nonoblivious permutation routing algorithm which runs in O(d.n/sup 2/) time on a d-ary de Bruijn network with N=d/sup n/ nodes. This algorithm is currently the fastest known nonoblivious deterministic routing algorithm for de Bruijn networks of arbitrary degree. Finally, we present an efficient general sorting algorithm for the de Bruijn networks of arbitrary degree. This algorithm is the best sorting algorithm known so far. It runs in O((log d).d.n/sup 2/) time for directed de Bruijn network with d/sup n/ nodes, degree d, and diameter n. As a corollary, we show that on a binary de Bruijn network of Nnodes, our sorting scheme requires at most 2 log/sup 2/ Nsteps.

This paper addresses the problem of scheduling parallel programs represented as directed acyclic task graphs for execution on distributed memory parallel architectures. Because of the high communication overhead in existing parallel machines, a crucial step in scheduling is task clustering, the process of coalescing fine grain tasks into single coarser ones so that the overall execution time is minimized. The task clustering problem is NP-hard, even when the number of processors is unbounded and task duplication is allowed. A simple greedy algorithm is presented for this problem which, for a task graph with arbitrary granularity, produces a schedule whose makespan is at most twice optimal. Indeed, the quality of the schedule improves as the granularity of the task graph becomes larger. For example, if the granularity is at least 1/2, the makespan of the schedule is at most 5/3 times optimal. For a task graph with n tasks and e inter-task communication constraints, the algorithm runs in O(n(n lg n+e)) time, which is n times faster than the currently best known algorithm for this problem. Similar algorithms are developed that produce: (1) optimal schedules for coarse grain graphs; (2) 2-optimal schedules for trees with no task duplication; and (3) optimal schedules for coarse grain trees with no task duplication.

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nn nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.

An optimal parallel recognition/parsing algorithm is presented for languages generated by tree adjoining grammars (TAGs), a grammatical system for natural language. TAGs are strictly more powerful than context-free grammars (CFGs), e.g., they can generate $\{a'' b'' c'' | n \geqq 0\}$, which is not context-free. However, serial parsing of TAGs is also slower, having time complexity $O(n^{6})$ for inputs of length n (as opposed to $O(n^{3})$ for CFGs). The parallel algorithm achieves optimal speedup: it runs in linear time on a five-dimensional array of $n^5$ processors. Moreover, the processors are finite-state; i.e., their function and size depends only on the underlying grammar and not on the length of the input.