Search

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 \mathcal 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 q < q' , based on a subgroup order criterion. In particular: 1) for every k\geq 2 ) but not over GF( 2^{2k+1} ) and 2) for arbitrary distinct primes p and p' , there are infinitely many k and k' ) but not over GF( p'^k' ) with p^k < p'^k' . [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 informarion 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. [ABSTRACT FROM AUTHOR]

Presents a detailed analysis of the maximum aperiodic autocorrelation of the original polyphase sequences. Equivalence relationships among Chu sequences, P3/P4 codes and Golomb sequences; Maximum autocorrelation of original Frank sequences; Maximum autocorrelation of original Chu sequences; Minimax correlation of two polyphase Barker sequences of length three; Minimax correlation of two polyphase sequences of length three; Conclusions.

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

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 refid="ref1"/, refid="ref2"/, 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. [ABSTRACT FROM AUTHOR]