Information-Centric Networking (ICN) is a promising future network architecture that shifts the host-based network paradigm to a content-oriented one. Over the past decade, numerous ICN congestion control (CC) schemes have been proposed, tailored to address congestion issues based on ICN’s transmission characteristics. However, several key challenges still need to be addressed. One critical issue is that most existing CC studies for ICN do not consider the diverse Quality of Service (QoS) requirements of modern network applications. This limitation hinders their applicability across various applications with different network performance preferences. Another ongoing challenge lies in improving transmission performance, particularly considering how to appropriately coordinate congestion control participants to enhance content retrieval efficiency and ensure reasonable resource allocation, especially in multipath scenarios. To tackle these challenges, we propose QSCCP, a QoS-aware congestion control protocol built upon NDN (Named Data Networking), a well-known ICN architecture. In QSCCP, diverse QoS preferences of various traffic are supported within a collaborative congestion control framework. A novel multi-level, class-based scheduling and forwarding mechanism is designed to ensure varied and fine-grained QoS guarantees. A distributed congestion notification and precise feedback mechanism is also provided, which efficiently collaborates with an adaptive multipath forwarding strategy and consumer rate adjustment to rationally allocate network resources and improve transmission efficiency, particularly in multipath scenarios. Extensive experimental results demonstrate that QSCCP satisfies diverse QoS requirements while achieving outstanding transmission performance. It outperforms existing schemes in throughput, fairness, delay, and packet loss, with a rapid convergence rate and excellent stability.

As a subset of distributed systems, blockchain technology is equally bound by the CAP trilemma. Specifically, no distributed system can satisfy consistency, availability, and partition tolerance simultaneously. Informally, the innovative blockchain trilemma has been theorized to include security, scalability, and decentralization. While many software approaches on blockchains claim to solve the trilemma problem, almost all known approaches have been proven to involve tradeoffs and fail to reach the upper bounds, meaning they do not achieve the theoretical limit value in each term of a trilemma. In this article, we propose a general trilemma based on the above two trilemmas. For permissioned blockchains, we then describe a system framework called GBT-CHAIN to solve the G eneral B lockchain T rilemma. In the proposed framework, the consensus and data layer, the network layer, and the physical layer work in cooperation. According to our theoretical proof and experimental analysis, the three properties of the trilemma consisting of consistency, scalability, and partition tolerance are perfectly satisfied without tradeoffs. Our results demonstrate that the general blockchain trilemma is resolved by combining consensus algorithms and physical topologies, in particular for permissioned blockchains.

The metaverse gradually evolves into a virtual world containing a series of interconnected sub-metaverses. Diverse digital resources, including identities, contents, services, and supporting data, are key components of the sub-metaverse. Therefore, a Domain Name System (DNS)-like system is necessary for efficient management and resolution. However, the legacy DNS was designed with security vulnerabilities and trust risks due to centralized issues. Blockchain is used to mitigate these concerns due to its decentralized features. Additionally, it supports identity management as a default feature, making it a natural fit for the metaverse. While there are several DNS alternatives based on the blockchain, they either manage only a single type of identifiers or isolate identities from other sorts of identifiers, making it difficult for sub-metaverses to coexist and connect with each other. This article proposes a M ulti- I dentifier management and resolution S ystem (MIS) in the metaverse, supporting the registration, resolution, and inter-translation functions. The basic MIS is portrayed as a four-tier architecture on a consortium blockchain due to its manageability, enhanced security, and efficiency properties. On-chain data is lightweight and compressed to save on storage while accelerating reading and writing operations. The resource data is encrypted based on the attributes of the sub-metaverse in the storage tier for privacy protection and access control. For users with decentralization priorities, a modification named EMIS is built on top of Ethereum. Finally, MIS is implemented on two testbeds and is available online as the open-source system. The first testbed consists of 4 physical servers located in the UK and Malaysia while the second is made up of 200 virtual machines (VMs) spread over 26 countries across all 5 continents on Google Cloud. Experiments indicate that MIS provides efficient reading and writing performance than the legacy DNS and other public blockchain-based workarounds including EMIS and Ethereum Name Service (ENS).

Cloud computing provides users with cost-effective on-demand resource sharing, but the shared resources also creates additional security risks due to co-location with malicious tenants. In addition to static defensive technologies, Virtual Machine (VM) migration, a type of Moving Target Defense (MTD) technique, provides an alternative solution to mitigate co-resident attacks by dynamically migrating services/tasks among various servers. Although significant progress has been made in this area, critical gaps remain regarding the quantification of these techniques' synergistic effectiveness in cloud computing, as previous research focused on either evaluating the defensive capability of MTD or on examining the characteristics of static strategies. In this paper, we aim to use analytical modeling techniques to quantitatively evaluate the synergistic effectiveness of integrating MTD with VM allocation policies. We designed a synergistically defensive architecture and proposed a Stochastic Reward Net (SRN) model to describe the execution and attacking processes of tasks migrating among multiple servers under three commonly used allocation policies. Moreover, experiments were implemented using SimPy to verify the analytical results obtained from the SRN model and to broaden the evaluation scope. Our comprehensive assessment, using both SRN and experiments, evaluates the defensive capacity and corresponding features for different scenarios. The obtained simulation results were approximate, with an error rate of less than 3.40 %, reflecting the reliability of our methods. Several defensive suggestions were further summarized based on the evaluation.

MOTIVATION: DNA methylation is an important epigenetic mechanism in gene regulation and the detection of differentially methylated regions (DMRs) is enthralling for many disease studies. There are several aspects that we can improve over existing DMR detection methods: (i) methylation statuses of nearby CpG sites are highly correlated, but this fact has seldom been modelled rigorously due to the uneven spacing; (ii) it is practically important to be able to handle both paired and unpaired samples; and (iii) the capability to detect DMRs from a single pair of samples is demanded. RESULTS: We present DMRMark (DMR detection based on non-homogeneous hidden Markov model), a novel Bayesian framework for detecting DMRs from methylation array data. It combines the constrained Gaussian mixture model that incorporates the biological knowledge with the non-homogeneous hidden Markov model that models spatial correlation. Unlike existing methods, our DMR detection is achieved without predefined boundaries or decision windows. Furthermore, our method can detect DMRs from a single pair of samples and can also incorporate unpaired samples. Both simulation studies and real datasets from The Cancer Genome Atlas showed the significant improvement of DMRMark over other methods. AVAILABILITY AND IMPLEMENTATION: DMRMark is freely available as an R package at the CRAN R package repository. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

To reduce multiple‐failure repair traffic in erasure coded storage systems, Patrick Lee et al. introduce concurrent framework‐based minimal‐storage regenerating codes (RGCs). The approach is simpler and more practical than the cooperative mechanism in non‐fully distributed environment. This study unifies such class of codes as concurrent RGC and further studies the characteristics by analysing the cut‐based information flow graph. The authors present a general storage–bandwidth tradeoff and give closed‐form expressions for the points on the curve including the minimal‐bandwidth point. They show that the concurrent RGC can be constructed by reforming the existing single‐node RGC or multiple‐node cooperative RGC. Moreover, a connection to strong‐maximum distance separable is also analysed.

In order to guarantee data reliability, erasure codes have been used in distributed storage systems. Nevertheless, this mechanism suffers from the repair problem that excess data are needed to repair a single failure, causing both high bandwidth consuming for the network and heavy computing load on the replacement node. To reduce repair traffic, researchers pointed out the tradeoff between storage and repair traffic and proposed regenerating codes by combining network coding. However, the combination only focuses on the storage terminal and the construction of the codes is quite complicated. Therefore, this paper further combines network coding with network structure and proposes a repair tree model based on general erasure codes to simplify the repair procedure. By decomposing repair computing and distributing it among the tree nodes, our model can mitigate the computing tension. The performance of repair tree is analyzed and evaluated by preliminary emulation. The result shows it can make about three times faster computing than conventional measure and the repair throughput is doubled if there are network bottlenecks. For proper topology, it can significantly reduce the repair traffic. We present algorithms to generate trees across the network topology. At last, we present the idea of extending repair tree to repair multiple failures.

A fibre memory is a serial connection of fibre‐switch blocks , each combining fibre delay lines with one optical switch. With enhanced flexibility in processing fluid optical data, fibre memories allow ramified applications in the existing literature. This study concentrates on the implementations of timeslot interchangers (TSIs) by fibre memories based on a special type of low‐complexity switches, called rotators , under periodic switching control. The proposed TSI structure achieves an economic tradeoff between control and component complexities in the construction of large‐scale optical TSIs.

Scheduling algorithms are crucial for most existing switches to improve the throughput. However, the delay of the switching fabric cannot be guaranteed with such scheduling algorithms. This paper aims to design a novel load-balanced wire-speed multicast switching fabric along with the attractive merits of network coding. We adopt a two-phase self-routing switching fabric constructed by Boolean-multicast concentrators (SRBMCs), where the first SRBMC distributes the incoming cells to its outputs uniformly and the second allows the distributed cells to be self-routed and multicast to their destinations concurrently. To further improve the switching performance, linear network coding is smoothly combined with SRBMC to reduce the packet loss rate. Theoretical analysis and numerical simulation demonstrate that the proposed switching fabric cannot only achieve wire-speed multicast switching but also be recursively constructed into an indefinite large-scale one with such merits as no internal buffers, low complexity, and guarantee in switching delay. Finally, we implement the proposed fabric on Field-Programmable Gate Array and verify its performance in multicast switching.

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class N of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil infinitely many new multicast networks linearly solvable over GF(q) but not over GF(q') with q2k) but not over GF(22k+1) and 2) for arbitrary distinct primes p and p', there are infinitely many k and k' such that an instance in N can be found linearly solvable over GF(pk) but not over GF(p'k') with pkk'.

A good switching fabric should be endowed with the properties of no internal buffers, delay guarantee, low component complexity and high-speed multicast, which are difficult for conventional switching fabrics to achieve, fueling the great interest in designing a new switching fabric that can support large-scale extension and high-speed multicast. Motivated by this, we reuse the self-routing Boolean concentrator network and embed a Multicast Packets Copy Separation (MPCS) in front to construct a load-balanced multicast switching fabric. Concretely, MPCS module replicates the multicast packets and forwards them according to the multicast addresses. The first phase of LB-MSNC is responsible for balancing the incoming traffic into uniform cells while the second phase is in charge of self-routing the cells to their final destinations. Differing from the existing fabrics, LB-MSNC is combined with the merits of network coding against the packet loss. Experimental results and analysis have verified that the proposed fabric is able to achieve high-speed multicast switching and suitable for building super large-scale switching fabric in Next Generation Network(NGN) with all the advantages mentioned above.

Fractional repetition (FR) codes are a family of repair‐efficient storage codes that provide exact and uncoded node repair at the minimum bandwidth regenerating point. The advantageous repair properties are achieved by a tailor‐made two‐layer encoding scheme which concatenates an outer maximum‐distance‐separable (MDS) code and an inner repetition code. In this study, the authors generalise the application of FR codes and propose heterogeneous fractional repetition (HFR) code, which is adaptable to the scenario where the repetition degrees of coded packets are different. The authors provide explicit code constructions by utilising group divisible designs, which allow the design of HFR codes over a large range of parameters. The constructed codes achieve the system storage capacity under random access repair and have multiple repair alternatives for node failures. Further, the authors take advantage of the systematic feature of MDS codes and present a novel design framework of HFR codes, in which storage nodes can be wisely partitioned into clusters such that data reconstruction time can be reduced when contacting nodes in the same cluster.

Fractional repetition (FR) codes are a family of storage codes that provide efficient node repair at the minimum bandwidth regenerating point. Specifically, the repair process is exact and uncoded, but table-based. Existing constructions of FR codes are primarily based on combinatorial designs such as Steiner systems, resolvable designs, etc. In this paper, we present a new explicit construction of FR codes, which adopts the theory of uniform group divisible designs, termed GDDFR codes. Our codes achieve the storage capacity of random access and are available for a wide range of parameters. In addition, our techniques allow for constructing FR codes with parameters that are not covered by Steiner systems, which answers an open question put forward in prior work.

A ‘fibre‐switch block’ is a switch with delay lines that feedback from some outputs to inputs. In every unit time, it receives and transmits a packet concurrently. A ‘fibre memory’ means a multi‐block serial connection. Its performance of time‐multiplexed operation is often said to ‘emulate’ a multistage interconnection network. This study formulates this concept of emulation. The formalised concept is useful in the design and validation of various switching functionalities, including timeslot interchanging, sorting, merging and concentration. For illustration, ‘banyan‐type networks’, ‘Clos network’ and several familiar multi‐stage sorting networks are all efficiently emulated.

We study the profit maximization problem of a cognitive virtual network operator in a dynamic network environment. We consider a downlink OFDM communication system with various network dynamics, including dynamic user demands, uncertain sensing spectrum resources, dynamic spectrum prices, and time-varying channel conditions. In addition, heterogeneous users and imperfect sensing technology are incorporated to make the network model more realistic. By exploring the special structural of the problem, we develop a low-complexity online control policies that determine pricing and resource scheduling without knowing the statistics of dynamic network parameters. We show that the proposed algorithms can achieve arbitrarily close to the optimal profit with a proper tradeoff with the queuing delay.

Network coding has been applied widely in wireless networks. In this paper, we focus on the cross-layer optimization of wireless networks with multiple unicast sessions and network coding. By exploiting broadcast advantage and one hop opportunistic listening, we develop a fully distributed solution including primal-dual flow control, Markov chain based hyperlink scheduling, session-decomposition coding scheme and session scheduling. We further study the convergence property of the distributed solution without time-scale separation assumption. We show the convergence to optimum with some time-dependent step sizes and update intervals. We also show the convergence to the bounded neighborhood of optimum with constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results. We emphasis that though the analysis for both cases is quite involved, the resulting distributed solutions are actually simple to implement.

Emerging as an important potential approach to the operation of lossy communication networks, Network Coding (NC) has been proposed to combine with TCP called TCP-NC by MIT. However, the key parameter R that is brought in for sending redundant packets against random loss is preseted and stays constant, therefore, chances are that it may fail to work. In this paper, we proposed a dynamic redundancy algorithm to control the number of sending packets. The algorithm is executed at the time of every arrival of feedback and makes redundancy approximate the loss rate as much as possible. All of these is done by the sender who is completely unconscious of the network situation. Simulation results under hybrid networks show that our new protocol retains all the advantages of TCP-NC over TCP-Reno and TCP-Westwood in terms of channel utilization and overall throughput, and simultaneously outperforms TCP-NC in time-varying light-load hybrid networks.

In this paper, we study a cognitive virtual network operator's profit maximization problem in a dynamic network environment. We consider various network dynamics, including dynamic user demands, unstable sensing spectrum resources, dynamic spectrum prices, and time-varying channel conditions. We develop a low-complexity on-line control policy that determines pricing and resource scheduling without knowing the distribution of dynamic network parameters. We show that the proposed algorithm can achieve arbitrarily close to the optimal profit with a proper trade-off of the queuing delay.

In this work, we define delay invariant convolutional network codes which guarantee multicast communication at asymptotically optimal rates in networks with arbitrary delay patterns. We show the existence of such a code over every symbol field. Moreover, the code can be constructed with high probability when coding coefficients are independently and uniformly chosen from a sufficiently large set of coding operations. On the other hand, if the symbol field is no smaller than the number of receivers, we devise a method to efficiently construct a delay invariant convolutional network code with scalar coding coefficients.

We consider network coding for networks experiencing worst-case bit-flip errors, and argue that this is a reasonable model for highly dynamic wireless network transmissions. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. We propose a new metric for errors under this model. Using this metric, we prove a new Hamming-type upper bound on the network capacity. We also show a commensurate lower bound based on GV-type codes that can be used for error-correction. The codes used to attain the lower bound are non-coherent (do not require prior knowledge of network topology). The end-to-end nature of our design enables our codes to be overlaid on classical distributed random linear network codes. Further, we free internal nodes from having to implement potentially computationally intensive link-by-link error-correction.

MOTIVATION: Repeats detection problems are traditionally formulated as string matching or signal processing problems. They cannot readily handle gaps between repeat units and are incapable of detecting repeat patterns shared by multiple sequences. This study detects short adjacent repeats with interunit insertions from multiple sequences. For biological sequences, such studies can shed light on molecular structure, biological function and evolution. RESULTS: The task of detecting short adjacent repeats is formulated as a statistical inference problem by using a probabilistic generative model. An Markov chain Monte Carlo algorithm is proposed to infer the parameters in a de novo fashion. Its applications on synthetic and real biological data show that the new method not only has a competitive edge over existing methods, but also can provide a way to study the structure and the evolution of repeat-containing genes. AVAILABILITY: The related C++ source code and datasets are available at http://ihome.cuhk.edu.hk/%7Eb118998/share/BASARD.zip. CONTACT: [email protected]

Network coding is a new paradigm in data transport that combines coding with data propagation over a network. Theory of linear network coding (LNC) adopts a linear coding scheme at every node of the network and promises the optimal data transmission rate from the source to all receivers. Linearity enhances the theoretic elegance and engineering simplicity, which leads to wide applicability. This paper reviews the basic theory of LNC and construction algorithms for optimal linear network codes. Exemplifying applications are presented, including random LNC. The fundamental theorem of LNC applies to only acyclic networks, but practical applications actually ignore the acyclic restriction. The theoretic justification for this involves convolutional network coding (CNC), which, however, incurs the difficulty of precise synchronization. The problem can be alleviated when CNC is generalized by selecting an appropriate structure in commutative algebra for data units. This paper tries to present the necessary algebraic concepts as much as possible in engineering language.

Peer-to-peer (P2P) systems have provided a scalable and cost effective way for file sharing and multimedia streaming in the past decade. The implementation of P2P systems usually involves two transmission schemes: routing (store-and-forward), and network coding. In this paper, we make a theoretical investigation of the rate that can be achieved by routing vs. network coding. We model P2P networks as node-capacitated networks with constraints on both node upload capacity and node download capacity. We compare routing and network coding for unicast, multicast and broadcast transmissions with both single-source scenario and multi-source scenario. Our results present not only a unification of existing results, but also extensions to new scenarios for node-capacitated networks.

The fundamental result of linear network coding asserts the existence of an optimal code on an acyclic single-source multicast network when the symbol field is sufficiently large. The restriction to acyclic networks turns out to stem from the customary structure of the symbol alphabet as a field. Adopting data units belonging to a discrete valuation ring (DVR), that is, a PID with a unique maximal ideal, much of the network coding theory extends to cyclic single-source multicast networks. Convolutional network coding is the instance of DVR-based network coding when the DVR consists of rational power series over the symbol field. Meanwhile, a field can be regarded as a degenerate DVR since it is a PID with the maximal ideal 0. Thus the conventional field-based network coding theory becomes a degenerate version of the DVR-based theory. This paper also delves into the issue of constructing optimal network codes on cyclic networks. Inspired by matroid duality theory, a novel method is devised to take advantage of all existing acyclic algorithms for network code construction. It associates every cyclic network with a quadratically large acyclic network so that essentially every optimal code on the acyclic network directly induces one on the cyclic network.

This paper considers a packet multiplexer (resp. de multiplexer) in the form of a queue with a single time-multiplexed input (resp. output) line, which is called a multiplexing queue (resp. demultiplexing queue). This queue is abstractly formulated in a way that allows recursive construction via 2-stage interconnection. The theoretic underpinning of this recursive construction is the preservation of two types of conditionally nonblocking switches through two versions of the 2-stage interconnection network. The recursive construction of a mux/demux queue emulates such switch preservation into a serial connection of fiber-switch blocks, which combine optical switches with fiber delay lines. Moreover, appropriate tandem connection between these two devices makes a FIFO queue. In terms of the physical structure, an instance of the FIFO queue so constructed coincides with the existing construction in the literature. The switching control mechanisms are different though. Inheriting the unique-routing characteristic of the 2-stage interconnection network, the present construction is under faster control, which distributes the computation task to individual blocks.

Cross-layer optimization is a key step in wireless network design that coordinates the resources allocated to different layers in order to achieve globally optimal network performance. Existing work on cross-layer optimization for wireless networks often adopts simplistic physical-layer models for wireless channels, such as treating interference as noise or interference avoidance. This crude modeling of physical layer often leads to inefficient utilization of resources. In this paper, we adopt a deterministic channel model proposed in,, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. This model allows us to go beyond “treating interference as noise” and as a consequence are able to achieve higher throughput and utility. Within the network utility maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-studied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks with both link-centric formulation and node-centric formulation. The convergence of algorithms is proved by applying Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results and show the advantage of deterministic channel model over simple physical layer models such as treating interference as noise.

Fluorescence in situ hybridization (FISH) is a powerful technique that localizes specific DNA sequences on chromosomes for use in physical and genetic maps assembling, genetic counselling, species identification, etc. Highly repetitive sequences are considered to be suitable FISH probes that can avoid many potential problems of using unique sequences as FISH probes. The distinct chromosomal distributions of these highly repetitive sequences are also ideal for labelling purposes such as karyotyping. In this paper, we present an automatic computational procedure for searching highly repetitive sequences from a whole genome as FISH probes, as well as an experimental protocol to use them in FISH analysis. We successfully applied the method on the newly released genome of Brachypodium distachyon (Brachypodium) and produced satisfactory results of FISH experiment.

Evolutionary Monte Carlo (EMC) algorithm is an effective and powerful method to sample complicated distributions. Short adjacent repeats identification problem (SARIP), i.e., searching for the common sequence pattern in multiple DNA sequences, is considered as one of the key challenges in the field of bioinformatics. A recently proposed Markov chain Monte Carlo (MCMC) algorithm has demonstrated its effectiveness in solving SARIP. However, high computation time and inevitable local optima hinder its wide application. In this paper, we apply EMC to parallelize the MCMC algorithm to solve SARIP. Our proposed EMC scheme is implemented on a parallel platform and the simulation results show that, compared with the conventional MCMC algorithm, EMC not only improves the quality of final solution but also reduces the computation time.

Existing work on cross-layer optimization for wireless networks adopts simple physical-layer models, i.e., treating interference as noise. In this paper, we adopt a deterministic channel model proposed in, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. Within the Network Utility Maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-applied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks. The convergence of algorithms is proved by Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant steps and constant update intervals. Our numerical evaluation validates the analytical results.

Multistage interconnection networks (MINs) are commonly deployed in sorting, switching, and other applications. Arithmetic over MINs for various applications is hereby unified in algebra. The key is to structure the signal alphabet as a distributive lattice instead of an ordered set. The theoretic unification enhances the mathematical understanding of properties of MINs and, in particular, demystifies various 0-1 principles. Conventional applications of MINs are all for point-to-point transmissions, while the unified theory applies to multicasting as well. The Multicast Concentrator Theorem is generalized into the Boolean Concentrator Theorem, which is useful in recursive construction of multicast switches with the feature of priority treatment. Meanwhile, the concomitant theory of cut-through coding is introduced for delay-free signal propagation through a MIN.

In this paper, we model and analyze the interactions between secondary users in a spectrum overlay cognitive system as a cognitive MAC game. In this game, each secondary user can sense (and transmit) one of several channels, the availability of each channel is determined by the activity of the corresponding primary user. We show that this game belongs to the class of congestion game and thus there exists at least one Nash Equilibrium. We focus on analyzing the worst case efficiency loss (i.e., price of anarchy) at any Nash Equilibrium of such a game. Closed-form expressions of price of anarchy are derived for both symmetric and asymmetric games, with arbitrary channel and user heterogeneity. Several insights are also derived in terms of how to design better cognitive radio systems with less severe efficiency loss.

We study the optimal usage-based pricing problem in a resource-bounded network with one profit-maximizing service provider and multiple groups of surplus-maximizing users. We first analytically derive the optimal pricing mechanism that the service provider maximizes the service provider's revenue under complete network information. Then we consider the incomplete information case, and propose two incentive compatible pricing schemes that achieve different complexity and performance tradeoff. Finally, by properly combining the two pricing schemes, we can show that it is possible to maintain a very small revenue loss (e.g., 0.5% in a two-group case) without knowing detailed information of each user in the network.

Node-capacitated networks are networks in which the capacity constraint is put on every node. They have recently attract attention as a good model for Peer-to-Peer (P2P) overlay networks. Existing work gives results on networks with constraints of node upload capacities. In this paper, we consider networks with constraints on both node upload and node download capacity. For such networks, we investigate the rate optimality of routing versus network coding. In general, network coding achieves a larger rate region than routing. However, for some important communication scenarios, routing achieves the same rate region as network coding.

Kernel learning is a powerful framework for nonlinear data modeling. Using the kernel trick, a number of problems have been formulated as semidefinite programs (SDPs). These include Maximum Variance Unfolding (MVU) (Weinberger et al., 2004) in nonlinear dimensionality reduction, and Pairwise Constraint Propagation (PCP) (Li et al., 2008) in constrained clustering. Although in theory SDPs can be efficiently solved, the high computational complexity incurred in numerically processing the huge linear matrix inequality constraints has rendered the SDP approach unscalable. In this paper, we show that a large class of kernel learning problems can be reformulated as semidefinite-quadratic-linear programs (SQLPs), which only contain a simple positive semidefinite constraint, a second-order cone constraint and a number of linear constraints. These constraints are much easier to process numerically, and the gain in speedup over previous approaches is at least of the order $m^{2.5}$, where m is the matrix dimension. Experimental results are also presented to show the superb computational efficiency of our approach.

A multistage interconnection network (MIN) consisting of 2 times 2 nodes constructs a nonblocking switch if the network is rearrangeable. When a 2ntimes 2nbit-permuting network is rearrangeable with the minimum depth of 2n-1, the initial (resp. final) n stages of the network form a banyan-type network and hence the network is equivalent to the tandem connection between two banyan-type networks. Let gamma denote the guide permutation of a 2ntimes 2nbanyan-type network and tau the trace permutation of another. These are permutations on numbers from 1 to n. This paper proves that, when the permutation gammatau-1is the transposition between the number n and some number k < n, the tandem connection between the two networks is rearrangeable. This sufficient condition for rearrangeability covers a wide class of tandem connections. For example, the first network in tandem can be the omega network appended with the banyan exchange of any rank while the second is the reversed omega network.

The 2-stage interconnection network is the most compact design in recursive construction of switches. Its 2X and X2 versions preserve several types of conditionally nonblocking switches and thereby enable recursive construction. This paper introduces hybrid preservation of new types of conditionally nonblocking switches. One application is in the construction of distributors.

This paper deals with matroids on the edge set of a network. Through the structure of edge-disjoint paths, a single-source network is associated with a network matroid, which turns out to be representable. A linear network code on an acyclic network assigns a coding vector to every edge. The linear independence among coding vectors naturally induces a matroid. It is shown that every independent set in the matroid so induced is also independent in the network matroid. Moreover, the two matroids coincide with each other if and only if the linear network code is a generic one. Furthermore, every representation for the network matroid of an acyclic network induces a generic linear network code. This offers a new characterization of generic linear network codes. For the network matroid of a cyclic network, an algorithm for finding a representation is also derived through the association with an acyclic network.

To enhance the access flexibility and logical elasticity in the use as delay lines, fibers are combined with optical switches into various types of fiber memories. One type belongs to recursively constructed packet buffers with single-stream I/O for such applications as queueing, multiplexing, demultiplexing, and flexible delay. The present paper considers the switching control speed over some of such fiber-memory applications.

The two-stage interconnection network is conceivably the most compact design for interconnecting small switches into a large switch. Switches so constructed typically can be controlled in the self-routing manner, because the route from an input to an output is unique. Different orderings of network input/output result in different versions of the two-stage interconnection network, two of which are known to preserve various classes of conditionally nonblocking switches. This paper adds Latin-square switches, rotators, reflectors, twisters, and untwisters to this set of classes with applications in load balancing, crosstalk-free optical switching, full connectivity among multiple users, etc. Knowledge of switch preservation under a certain style of multistage interconnection not only allows recursive construction of indefinitely large switches, but also provides insight, generality, and algorithmic flexibility in the construction

This paper deals with flexibility, rather than efficiency, in information propagation. When optical, electrical, or acoustical signals are guided through their transmission medium, it is possible to store and retrieve their analog form for the purposes of queueing, time slot interchanging, multiplexing, demultiplexing, flexible delay, etc. To harness the constantly progressing signals, the analog memory need be equipped with switches for access flexibility and logical elasticity. This paper proposes systematic algorithms for recursive construction of analog memory via most basic interconnection patterns. The mathematical underpinning is mainly the algebraic theory on 2-stage interconnection networks, over which the switching control is self-routing and fast

Convolutional network coding deals with the propagation of a message pipeline through a cyclic network. We formulate a Convolutional network code by associating every pair of adjacent channels with a rational power series over the base field, called the local encoding kernel, and every channel with a concomitant global encoding kernel, which is a vector of rational power series. Given a complete set of local encoding kernels, a close-form formula is derived for calculating the global encoding kernels. A convolutional multicast is a convolutional network code that every qualified receiving node can decode the message. We offer a construction algorithm for a convolutional multicast as well as a decoding algorithm

The 2-stage interconnection network is conceivably the most compact design for interconnecting small switches into a large switch. When a certain class of switches is preserved under 2-stage interconnection, recursive application of 2-stage interconnection then builds indefinitely large switches in this class from atomic ones. The present paper studies switches that are not preserved under 2-stage interconnection but are yet constructive from atomic elements through recursive 2-stage interconnection. The principle is "mixed preservation" based on the following two properties: first, the 2-stage interconnection network constructs a class-A switch when switches at nodes on one stage belong to class A and switches at nodes on the other stage belong to class B; second, class-B switches are preserved under 2-stage interconnection. A class of conditionally nonblocking switches for such mixed preservation are identified, which are useful in the recursive construction of distribution networks

This paper extends the part of the theory on linear network coding (S.-Y.R. Li et al., 2003) over an acyclic network. The extension also applies to "static linear network code" that is introduced by R. Koetter and M. Medard, (2003). Another objective is the rigorous clarification of fundamental concepts in linear network coding

The most compact pattern for interconnecting small switches into a large switch is conceivably the 2-stage interconnection network. A certain version of a 2-stage interconnection network is said to preserve switches with a certain attribute when the network constructs such a switch from smaller ones at nodes. Recursive application of this version of 2-stage interconnection then leads to the construction of indefinitely large switches with the same attribute. The present paper studies a few new classes of switches that are preserved under 2-stage interconnection and also identifies their applications. Different switch preservation theorems presented in the paper offer the advantages of both the algorithmic flexibility and the theoretic insight.

The cascade of two 2^n × 2^n baseline networks in tandem and the cascade of two omega networks through a special interconnection pattern are known to be rearrangeable. These belong to the general problem: for what two banyan-type networks (i.e., bitpermuting unique-routing network) are their tandem cascade a rearrangeable network? We relate the problem to the trace and guide of banyan-type networks. When the guide of one 2^n × 2^n banyan-type network and the trace of the other are represented by the permutations y and t on integers 1 to n, respectively, rearrangeability of their tandem cascade is solely determined by yt^-1, which is said to be a tandem rearrangeable permutation when the tandem cascade is indeed rearrangeable. We identify a few tandem rearrangeable permutations, each implying the rearrangeability of the tandem cascade of a wide class of banyan-type networks.

Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.

We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a "fluid" which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems.

The fast knockout (FKO) algorithm constructs self-route concentrators from multi-stage cascades of 2/spl times/2 sorters. It is an especially efficient technique for m-to-n concentration when m and n are within the practical range. The algorithm calls a sub-algorithm for pairing, where different choices of the sub-algorithm yield FKO concentrators of different efficiencies. The present paper provides a new sub-algorithm for pairing. The result complements the existing technique of "k-sorting" in generating a best-known m-to-n concentrator for all m and n within the range of ail practical purposes.

A detailed analysis of the maximum aperiodic autocorrelation of the original Chu sequences (equivalently, P3/P4 pulse compression codes) is presented. The result implies the best known upper bound on the minimax aperiodic autocorrelation for polyphase sequences except when the length is very small or a perfect square. It is well known that determining the minimax aperiodic correlation for polyphase sequence sets is an intractable task. The simplest nontrivial cases for Barker and general polyphase sequences are solved for the first time.

Through rigorous formalization of basic notions about interconnection networks, new and old constructions of interconnection networks are naturally organized into a systematic account. Meanwhile, generally known but vague facts about the theoretical properties of routing networks are stated precisely. "Reversible routing networks" form the basis of a class of output-buffer self-route ATM switches. Such networks can be used in error-correcting routing, and some are better choices over others in terms of the modularity of exchange patterns between stages of routing cells. The "Rotary switch" is designed over any reversible routing network. It corrects a misstep in routing without necessarily an exact reversion. This allows multiple paths for a deflected packet to proceed on and thereby reduces the probability of collision. Simulations have shown low packet loss rate vs. either the number of switching stages or the size of output multiplexers.>

This article introduces a slotted protocol for multi-user access to a LAN over parallel OR-type channels. An OR-type channel is defined as a digital communication channel such that, when a bit signal is injected into the channel, the channel content m at the bit position becomes logically ORed with the injected bit. The protocol applies a dynamic coding scheme to achieve 100% channel efficiency in the sense that, in each transmission session, an intended messages, or at least as many as the number of channels, are successfully broadcast. Message reception is through decoding from the OR composition of user injected bits. The coding scheme is a substitute for such approaches as slot reservation, permission token, and collision resolution that are used in most media access protocols.>

An algorithm for the decentralized control of traffic flow in multihop broadband ISDN and a concomitant algorithm for call setup are proposed. The approach in flow control is to strategically detain packets at points along their routes in anticipation of probable congestion ahead of them. The goal is to avoid buffer overflowing caused by concentrated packet accumulation at a single node on the network. A typical traffic control decision involves just two primitive operations: a READ and a logical AND. Hence, a submicrosecond execution time is expected. This quickness enables the traffic control to be implementable on the packet (or cell) level for broadband communications with a moderate packet size. This algorithm also strives for high utilization of broadband facilities and preserves the order among sequential packets. The concomitant algorithm for call setup is solely executed at the traffic originating node(s) and thus requires no internode communications. This leads to a simple process of calls setup that ensures the continuous flow of ongoing calls and, at the same time, avoids buffer overflowing.>

The basic model of packet switching based on a self-routing interconnection network is described. The theory of periodic contention is reviewed, showing that a broadband switch is nonblocking for the periodic traffic type if it is fast enough to avoid the phenomenon of persistent blocking, where an input buffer consistently transmits fewer packets than it is receiving. The necessary and sufficient switch rate for avoiding persistent blocking is determined. This rate turns out to be a more stringent requirement than if the traffic pattern had been Poisson, a usual assumption.>

This article introduces the concept of exchangeable stopping time and a technique of dynamic programming based upon this concept for fast computation of the expected Value of a payoff function upon stopping. One instance of an exchangeable stopping time is when a stopping time is defined by a threshold on the sequential sum of the process. Another instance is when a stopping time is defined by the occurrence of given patterns in observed values of the process. This new computation technique has applications in bin packing, casino blackjack, and random drawing for patterns.

The following model of a packet switch is considered: at each clock tick, the switch attempts to route the head-of-line packet at the buffer of every input port to its destination port. Each output port can receive only one packet at a time, but there may be packets from multiple inputs destined for common output. The switch first selects exactly one packet for each requested output and then routes all selected packets through a self-route interconnection network such as the Batcher-Banyan network. Based on the traffic assumption of periodic packet streams, the necessary and sufficient clock rate is determined in order for the switch to be nonblocking. This result has turned out to be quite different from analyses based on the assumption of random traffic.>

When there is no division circuit available, the arithmetical function of division is normally performed by a library subroutine. The library subroutine normally allows both the divisor and the dividend to be variables, and requires the execution of hundreds of assembly instructions. This correspondence provides a fast algorithm for performing the integer division of a variable by a predetermined divisor. Based upon this algorithm, an efficient division routine has been constructed for each odd divisor up to 55. These routines may be implemented in assembly languages, in microcodes, and in special-purpose circuits.