Visible to the public Network Coding

SoS Newsletter- Advanced Book Block

Network Coding

Network coding methods are used to improve a network's throughput, efficiency and scalability. It can also be a method for dealing with attacks and eavesdropping. Research into network coding deals with finding optimal solutions to the general network problems that remain open. The articles cited here were presented or published between January and September 2014.

  • Shiyu Ji; Tingting Chen; Sheng Zhong; Kak, S., "DAWN: Defending Against Wormhole Attacks In Wireless Network Coding Systems," INFOCOM, 2014 Proceedings IEEE , vol., no., pp.664,672, April 27 2014-May 2 2014. doi: 10.1109/INFOCOM.2014.6847992 Network coding has been shown to be an effective approach to improve the wireless system performance. However, many security issues impede its wide deployment in practice. Besides the well-studied pollution attacks, there is another severe threat, that of wormhole attacks, which undermines the performance gain of network coding. Since the underlying characteristics of network coding systems are distinctly different from traditional wireless networks, the impact of wormhole attacks and countermeasures are generally unknown. In this paper, we quantify wormholes' devastating harmful impact on network coding system performance through experiments. Then we propose DAWN, a Distributed detection Algorithm against Wormhole in wireless Network coding systems, by exploring the change of the flow directions of the innovative packets caused by wormholes. We rigorously prove that DAWN guarantees a good lower bound of successful detection rate. We perform analysis on the resistance of DAWN against collusion attacks. We find that the robustness depends on the node density in the network, and prove a necessary condition to achieve collusion-resistance. DAWN does not rely on any location information, global synchronization assumptions or special hardware/middleware. It is only based on the local information that can be obtained from regular network coding protocols, and thus does not introduce any overhead by extra test messages. Extensive experimental results have verified the effectiveness and the efficiency of DAWN. Keywords: network coding; radio networks; synchronisation; telecommunication security; DAWN; collusion attacks; collusion-resistance; detection rate; distributed detection algorithm; flow directions; global synchronization assumptions; location information; node density; pollution attacks; regular network coding protocols; test messages; wireless network coding systems; wireless system performance; wormhole attacks; Encoding; Network coding; Probability; Protocols; Routing; Throughput; Wireless networks (ID#:14-2420) URL:
  • Shang Tao; Pei Hengli; Liu Jianwei, "Secure network coding based on lattice signature," Communications, China , vol.11, no.1, pp.138,151, Jan. 2014. doi: 10.1109/CC.2014.6821316 To provide a high-security guarantee to network coding and lower the computing complexity induced by signature scheme, we take full advantage of homomorphic property to build lattice signature schemes and secure network coding algorithms. Firstly, by means of the distance between the message and its signature in a lattice, we propose a Distance-based Secure Network Coding (DSNC) algorithm and stipulate its security to a new hard problem Fixed Length Vector Problem (FLVP), which is harder than Shortest Vector Problem (SVP) on lattices. Secondly, considering the boundary on the distance between the message and its signature, we further propose an efficient Boundary-based Secure Network Coding (BSNC) algorithm to reduce the computing complexity induced by square calculation in DSNC. Simulation results and security analysis show that the proposed signature schemes have stronger unforgeability due to the natural property of lattices than traditional Rivest-Shamir-Adleman (RSA)-based signature scheme. DSNC algorithm is more secure and BSNC algorithm greatly reduces the time cost on computation. Keywords: computational complexity; digital signatures; network coding ;telecommunication security; BSNC; DSNC; FLVP; boundary-based secure network coding; computing complexity; distance-based secure network coding; fixed length vector problem; hard problem; high-security guarantee; homomorphic property; lattice signature; signature scheme; Algorithm design and analysis; Cryptography; Lattices; Network coding; Network security; fixed length vector problem; lattice signature; pollution attack; secure network coding (ID#:14-2421) URL:
  • Keshavarz-Haddad, A; Riedi, R.H., "Bounds on the Benefit of Network Coding for Wireless Multicast and Unicast," Mobile Computing, IEEE Transactions on , vol.13, no.1, pp.102,115, Jan. 2014. doi: 10.1109/TMC.2012.234 In this paper, we explore fundamental limitations of the benefit of network coding in multihop wireless networks. We study two well-accepted scenarios in the field: single multicast session and multiple unicast sessions. We assume arbitrary but fixed topology and traffic patterns for the wireless network. We prove that the gain of network coding in terms of throughput and energy saving of a single multicast session is at most a constant factor. Also, we present a lower bound on the average number of transmissions of multiple unicast sessions under any arbitrary network coding. We identify scenarios under which network coding provides no gain at all, in the sense that there exists a simple flow scheme that achieves the same performance. Moreover, we prove that the gain of network coding in terms of the maximum transport capacity is bounded by a constant factor of at most $(pi)$ in any arbitrary wireless network under all traditional Gaussian channel models. As a corollary, we find that the gain of network coding on the throughput of large homogeneous wireless networks is asymptotically bounded by a constant. Furthermore, we establish theorems which relate a network coding scheme to a simple routing scheme for multiple unicast sessions. The theorems can be used as criteria for evaluating the potential gain of network coding in a given wired or wireless network. Based on these criteria, we find more scenarios where network coding has no gain on throughput or energy saving. Keywords: Gaussian channels; multicast communication; network coding; Gaussian channel models; arbitrary wireless network; constant factor; large homogeneous wireless networks; maximum transport capacity; multihop wireless networks; multiple unicast sessions; network coding scheme; single multicast session; wireless multicast; wireless unicast; Channel models; Energy consumption; Network coding; Throughput; Unicast; Wireless networks; Channel models; Energy consumption; Network coding; Network coding gain; Throughput; Unicast; Wireless networks; energy consumption; multicast throughput; transport capacity (ID#:14-2422) URL:
  • Tae-hwa Kim; Hyungwoo Choi; Hong-Shik Park, "Centrality-based Network Coding Node Selection Mechanism For Improving Network Throughput," Advanced Communication Technology (ICACT), 2014 16th International Conference on , vol., no., pp.864,867, 16-19 Feb. 2014. doi: 10.1109/ICACT.2014.6779083 The problem of minimizing the number of coding nodes is caused by network coding overhead and is proved to be NP-hard. To resolve this issue, this paper proposes Centrality-based Network Coding Node Selection (CNCNS) that is the heuristic and distributed mechanism to minimize the number of network coding (NC) nodes without compromising the achievable network throughput. CNCNS iteratively analyses the node centrality and selects NC node in the specific area. Since CNCNS operates with distributed manner, it can dynamically adapt the network status with approximately minimizing network coding nodes. Especially, CNCNS adjusts the network performance of network throughput and reliability using control indicator. Simulation results show that the well selected network coding nodes can improve the network throughput and almost close to throughput performance of a system where all network nodes operate network coding. Keywords: network coding; radio networks; NP hard problem; centrality based network coding node selection mechanism; coding nodes; distributed mechanism; heuristic mechanism; network coding overhead; network reliability; network status; network throughput improvement; Decoding; Delays; Encoding; Network coding; Receivers; Reliability; Throughput; Centrality; Degree; Network coding; Throughput; Weight (ID#:14-2423) URL:
  • Min Yang; Yuanyuan Yang, "Applying Network Coding to Peer-to-Peer File Sharing," Computers, IEEE Transactions on , vol.63, no.8, pp.1938,1950, Aug. 2014. doi: 10.1109/TC.2013.88 Network coding is a promising enhancement of routing to improve network throughput and provide high reliability. It allows a node to generate output messages by encoding its received messages. Peer-to-peer networks are a perfect place to apply network coding due to two reasons: the topology of a peer-to-peer network is constructed arbitrarily, thus it is easy to tailor the topology to facilitate network coding; the nodes in a peer-to-peer network are end hosts which can perform more complex operations such as decoding and encoding than simply storing and forwarding messages. In this paper, we propose a scheme to apply network coding to peer-to-peer file sharing which employs a peer-to-peer network to distribute files resided in a web server or a file server. The scheme exploits a special type of network topology called combination network. It was proved that combination networks can achieve unbounded network coding gain measured by the ratio of network throughput with network coding to that without network coding. Our scheme encodes a file into multiple messages and divides peers into multiple groups with each group responsible for relaying one of the messages. The encoding scheme is designed to satisfy the property that any subset of the messages can be used to decode the original file as long as the size of the subset is sufficiently large. To meet this requirement, we first define a deterministic linear network coding scheme which satisfies the desired property, then we connect peers in the same group to flood the corresponding message, and connect peers in different groups to distribute messages for decoding. Moreover, the scheme can be readily extended to support link heterogeneity and topology awareness to further improve system performance in terms of throughput, reliability and link stress. Our simulation results show that the new scheme can achieve 15%-20% higher throughput than another peer-to-peer multicast system, Narada, which does not employ network c- ding. In addition, it achieves good reliability and robustness to link failure or churn. Keywords: network coding; peer-to-peer computing; telecommunication network reliability; telecommunication network topology; Web server; combination network; decoding; deterministic linear network; encoding; file server; network topology; peer-to-peer file sharing; Network coding; file sharing; multicast; peer-to-peer networks; web-based applications (ID#:14-2424) URL:
  • Bourtsoulatze, E.; Thomos, N.; Frossard, P., "Decoding Delay Minimization in Inter-Session Network Coding," Communications, IEEE Transactions on , vol.62, no.6, pp.1944,1957, June 2014. doi: 10.1109/TCOMM.2014.2318701 Intra-session network coding has been shown to offer significant gains in terms of achievable throughput and delay in settings where one source multicasts data to several clients. In this paper, we consider a more general scenario where multiple sources transmit data to sets of clients over a wireline overlay network. We propose a novel framework for efficient rate allocation in networks where intermediate network nodes have the opportunity to combine packets from different sources using randomized network coding. We formulate the problem as the minimization of the average decoding delay in the client population and solve it with a gradient-based stochastic algorithm. Our optimized inter-session network coding solution is evaluated in different network topologies and is compared with basic intra-session network coding solutions. Our results show the benefits of proper coding decisions and effective rate allocation for lowering the decoding delay when the network is used by concurrent multicast sessions. Keywords: computer networks; decoding; delays; gradient methods; minimisation; network coding; overlay networks; stochastic processes; telecommunication network topology; client population; coding decisions; concurrent multicast sessions; decoding delay minimization; gradient-based stochastic algorithm; intermediate network nodes ;intersession network coding solution; intrasession network coding solutions; network topologies; randomized network coding; rate allocation; wireline overlay network; Decoding; Delays; Encoding; Network coding; Resource management; Throughput; Vectors; Network coding; decoding delay; inter-session network coding; overlay networks; rate allocation (ID#:14-2425) URL:
  • Yin, X.; Wang, Y.; Li, Z.; Wang, X.; Xue, X., "A Graph Minor Perspective to Multicast Network Coding," Information Theory, IEEE Transactions on , vol.60, no.9, pp.5375,5386, Sept. 2014. doi: 10.1109/TIT.2014.2336836 Network coding encourages information coding across a communication network. While the necessity, benefit and complexity of network coding are sensitive to the underlying graph structure of a network, existing theory on network coding often treats the network topology as a black box, focusing on algebraic or information theoretic aspects of the problem. This paper aims at an in-depth examination of the relation between algebraic coding and network topologies. We mathematically establish a series of results along the direction of: if network coding is necessary/beneficial, or if a particular finite field is required for coding, then the network must have a corresponding hidden structure embedded in its underlying topology, and such embedding is computationally efficient to verify. Specifically, we first formulate a meta-conjecture, the NC-minor conjecture, that articulates such a connection between graph theory and network coding, in the language of graph minors. We next prove that the NC-minor conjecture for multicasting two information flows is almost equivalent to the Hadwiger conjecture, which connects graph minors with graph coloring. Such equivalence implies the existence of (K_{4}) , (K_{5}) , (K_{6}) , and (K_{O(q/log {q})}) minors, for networks that require (mathbb {F}_{3}) , (mathbb {F}_{4}) , (mathbb {F}_{5}) , and (mathbb {F}_{q}) to multicast two flows, respectively. We finally pro- e that, for the general case of multicasting arbitrary number of flows, network coding can make a difference from routing only if the network contains a (K_{4}) minor, and this minor containment result is tight. Practical implications of the above results are discussed. Keywords: Color; Encoding; Network coding; Network topology; Receivers; Routing; Vectors; Network coding; graph minor ;multicast; treewidth (ID#:14-2426) URL:
  • Coondu, S.; Mitra, A; Chattopadhyay, S.; Chattopadhyay, M.; Bhattacharya, M., "Network-coded Broadcast Incremental Power Algorithm For Energy-Efficient Broadcasting In Wireless Ad-Hoc Network," Applications and Innovations in Mobile Computing (AIMoC), 2014, pp.42, 47, Feb. 27, 2014-March 1, 2014. doi: 10.1109/AIMOC.2014.6785517 An important operation in multi-hop wireless ad-hoc networks is broadcasting, which propagates information throughout the network. We are interested to explore the issue of broadcasting, where all nodes of the network are sources that want to transmit information to all other nodes, in an ad-hoc wireless network. Our performance metric is energy efficiency, a vital defining factor for wireless networks as it directly concerns the battery life and thus network longevity. We show the benefits network coding has to offer in a wireless ad-hoc network as far as energy-savings is concerned, compared to the store-and-forward strategy. Network coded broadcasting concentrates on reducing the number of transmissions performed by each forwarding node in the all-to-all broadcast application, where each forwarding node combines the incoming messages for transmission. The total number of transmissions can be reduced using network coding, compared to broadcasting using the same forwarding nodes without coding. In this paper, we present the performance of a network coding-based Broadcast Incremental Power (BIP) algorithm for all-to-all broadcast. Simulation results show that optimisation using network coding method lead to substantial improvement in the cost associated with BIP. Keywords: ad hoc networks; network coding; telecommunication network reliability; all-to-all broadcast application; battery life; energy-efficient broadcasting; energy-savings; forwarding node; multihop wireless ad hoc networks; network coding-based BIP algorithm; network longevity; network nodes; network-coded broadcast incremental power algorithm; store-and-forward strategy; vital defining factor; Ad hoc networks; Broadcasting; Encoding; Energy consumption; Network coding; Space vehicles; Wireless communication; Broadcast Incremental Power; Energy-Efficiency; Minimum Power Broadcast Problem; Network Coding; Wireless Ad-Hoc Network; Wireless Multicast Advantage (ID#:14-2427) URL:
  • Deze Zeng; Song Guo; Yong Xiang; Hai Jin, "On the Throughput of Two-Way Relay Networks Using Network Coding," Parallel and Distributed Systems, IEEE Transactions on , vol.25, no.1, pp.191,199, Jan. 2014. doi: 10.1109/TPDS.2013.187 Network coding has shown the promise of significant throughput improvement. In this paper, we study the network throughput using network coding and explore how the maximum throughput can be achieved in a two-way relay wireless network. Unlike previous studies, we consider a more general network with arbitrary structure of overhearing status between receivers and transmitters. To efficiently utilize the coding opportunities, we invent the concept of network coding cliques (NCCs), upon which a formal analysis on the network throughput using network coding is elaborated. In particular, we derive the closed-form expression of the network throughput under certain traffic load in a slotted ALOHA network with basic medium access control. Furthermore, the maximum throughput as well as optimal medium access probability at each node is studied under various network settings. Our theoretical findings have been validated by simulation as well. Keywords: access protocols; network coding; radio receivers; radio transmitters; relay networks (telecommunication); telecommunication traffic; NCCs; closed-form expression; medium access control; network coding clique; network traffic load; optimal medium access probability; receiver; slotted ALOHA network; transmitter; two-way relay wireless network; Encoding; Network coding;Receivers;Relays;Throughput;Transmitters;Unicast;Performance analysis; network coding; slotted ALOHA (ID#:14-2428) URL:
  • Lili Wei; Wen Chen; Hu, R.Q.; Geng Wu, "Network Coding In Multiple Access Relay Channel With Multiple Antenna Relay," Computing, Networking and Communications (ICNC), 2014 International Conference on , vol., no., pp.656,661, 3-6 Feb. 2014. doi: 10.1109/ICCNC.2014.6785414 Network coding is a paradigm for modern communication networks by allowing intermediate nodes to mix messages received from multiple sources. In this paper, we carry out a study on network coding in multiple access relay channel (MARC) with multiple antenna relay. Under the same transmission time slots constraint, we investigate several different transmission strategies applicable to the system model, including direct transmission, decode-and-forward, digital network coding, digital network coding with Alamouti space time coding, analog network coding, and compare the error rate performance. Interestingly, simulation studies show that in the system model under investigation, the schemes with network coding do not show any performance gain compared with the traditional schemes with same time slots consumption. Keywords: antenna arrays; decode and forward communication; network coding; radio access networks; relay networks (telecommunication);simulation; space-time codes; Alamouti space time coding; MARC; analog network coding; decode-and-forward transmission; digital network coding; direct transmission; multiple access relay channel; multiple antenna relay; transmission time slots constraint; Encoding; Erbium; Network coding; Relays; Slot antennas; Vectors; Wireless communication; cooperative; multiple access relay channel; network coding; space-time coding (ID#:14-2429) URL:
  • Ye Liu; Chi Wan Sung, "Quality-Aware Instantly Decodable Network Coding," Wireless Communications, IEEE Transactions on , vol.13, no.3, pp.1604,1615, March 2014. doi: 10.1109/TWC.2014.012314.131046 In erasure broadcast channels, network coding has been demonstrated to be an efficient way to satisfy each user's demand. However, the erasure broadcast channel model does not fully characterize the information available in a "lost" packet, and therefore any retransmission schemes designed based on the erasure broadcast channel model cannot make use of that information. In this paper, we characterize the quality of erroneous packets by Signal-to-Noise Ratio (SNR) and then design a network coding retransmission scheme with the knowledge of the SNRs of the erroneous packets, so that a user can immediately decode two source packets upon reception of a useful retransmission packet. We demonstrate that our proposed scheme, namely Quality-Aware Instantly Decodable Network Coding (QAIDNC), can increase the transmission efficiency significantly compared to the existing Instantly Decodable Network Coding (IDNC) and Random Linear Network Coding (RLNC). Keywords: broadcast channels; decoding; linear codes; network coding; QAIDNC; RLNC; SNR; erasure broadcast channel model; lost packet; quality of erroneous packets; quality-aware instantly decodable network coding; random linear network coding; retransmission schemes; signal-to-noise ratio; source packets; transmission efficiency; user demand; Decoding; Encoding; Network coding; Phase shift keying; Signal to noise ratio; Vectors; Broadcast channel; Rayleigh fading; instantly decodable network coding; maximal-ratio combining; network coding (ID#:14-2430) URL:
  • Amerimehr, M.H.; Ashtiani, F.; Valaee, S., "Maximum Stable Throughput of Network-Coded Multiple Broadcast Sessions for WirelessTandem Random Access Networks," Mobile Computing, IEEE Transactions on, vol.13, no.6, pp.1256,1267, June 2014. doi: 10.1109/TMC.2013.2296502 This paper presents an analytical study of the stable throughput for multiple broadcast sessions in a multi-hop wireless tandem network with random access. Intermediate nodes leverage on the broadcast nature of wireless medium access to perform inter-session network coding among different flows. This problem is challenging due to the interaction among nodes, and has been addressed so far only in the saturated mode where all nodes always have packet to send, which results in infinite packet delay. In this paper, we provide a novel model based on multi-class queueing networks to investigate the problem in unsaturated mode. We devise a theoretical framework for computing maximum stable throughput of network coding for a slotted ALOHA-based random access system. Using our formulation, we compare the performance of network coding and traditional routing. Our results show that network coding leads to high throughput gain over traditional routing. We also define a new metric, network unbalance ratio (NUR), that indicates the unbalance status of the utilization factors at different nodes. We show that although the throughput gain of the network coding compared to the traditional routing decreases when the number of nodes tends to infinity, NUR of the former outperforms the latter. We carry out simulations to confirm our theoretical analysis. Keywords: access protocols; broadcast communication; network coding; queueing theory; radio access networks; infinite packet delay; inter-session network coding; maximum stable throughput; multiclass queueing networks; multihop wireless tandem network; multiple broadcast sessions; network coding; network routing; network unbalance ratio; network-coded multiple broadcast sessions; slotted ALOHA-based random access system; theoretical analysis; wireless medium access; wireless tandem random access networks; Analytical models; Multicast communication; Network coding; Routing; Spread spectrum communication; Throughput; Wireless communication; Network coding; queueing networks; random access; routing; stable throughput; vehicular networks (ID#:14-2431) URL:
  • Gang Wang; Xia Dai; Yonghui Li, "On the Network Sharing of Mixed Network Coding and Routing Data Flows in Congestion Networks," Vehicular Technology, IEEE Transactions on , vol.63, no.5, pp.2420,2428, Jun 2014. doi: 10.1109/TVT.2013.2291859 In this paper, we study the congestion game for a network where multiple network coding (NC) and routing users sharing a single common congestion link to transmit their information. The data flows using NC and routing will compete network resources, and we need to determine the optimal allocation of network resources between NC and routing data flows to maximize the network payoff. To facilitate the design, we formulate this process using a cost-sharing game model. A novel average-cost-sharing (ACS) pricing mechanism is developed to maximize the overall network payoff. We analyze the performance of ACS in terms of price of anarchy (PoA). We formulate an analytical expression to compute PoA under the ACS mechanism. In contrast to the previous affine marginal cost (AMC) mechanism, where the overall network payoff decreases when NC is applied, the proposed ACS mechanism can considerably improve the overall network payoff by optimizing the number and the spectral resource allocation of NC and routing data flows sharing the network link. Keywords: game theory; network coding; radio networks; telecommunication congestion control; telecommunication network routing; anarchy price; congestion game; congestion networks; cost sharing game model; data flow routing; mixed network coding; network sharing; optimal network resource allocation; pricing mechanism; single common congestion link; Aggregates; Games; Nash equilibrium; Network coding; Pricing; Resource management; Routing; Affine Marginal Cost (AMC);Affine marginal cost (AMC); Average Cost Sharing (ACS) ;Network Coding (NC); Price of Ararchy (PoA); average cost sharing (ACS); network coding (NC); price of anarchy (PoA) (ID#:14-2432) URL:
  • Kramarev, D.; Yi Hong; Viterbo, E., "Software Defined Radio Implementation Of A Two-Way Relay Network With Digital Network Coding," Communications Theory Workshop (AusCTW), 2014 Australian, pp.120, 125, 3-5 Feb. 2014. doi: 10.1109/AusCTW.2014.6766439 Network coding is a technology which has the potential to increase network throughput beyond existing standards based on routing. Despite the fact, that the theoretical understanding is mature, there have been only a few papers on implementation of network coding and demonstration of a working testbed. This paper presents the implementation of a two-way relay network with digital network coding. Unlike previous work, where the testbeds are implemented on custom hardware, we implement the testbed on GNU Radio, an open-source software defined radio platform. In this paper we discuss the implementation issues and the ways to overcome the hardware imperfections and software inadequacies of the GNU Radio platform. Using our testbed we measure the throughput of the system in an indoor environment. The experimental results show that the network coding outperforms the traditional routing as predicted by the theoretical analysis. Keywords: network coding; public domain software; relay networks (telecommunication); software radio; GNU Radio platform; digital network coding; hardware imperfections; open-source software; radio implementation; software inadequacies; testbed; two-way relay network; Hardware; Network coding; Packet switching; Relays; Software; Synchronization; Throughput; GNU radio; Software-defined radio; network coding; network coding implementation; testbed; two-way relay network (ID#:14-2433) URL:
  • Carrillo, E.; Ramos, V., "On the Impact of Network Coding Delay for IEEE 802.11s Infrastructure Wireless Mesh Networks," Advanced Information Networking and Applications (AINA), 2014 IEEE 28th International Conference on , vol., no., pp.305,312, 13-16 May 2014. doi: 10.1109/AINA.2014.39 The distributed coordination function (DCF) may reduce the potential of network coding in 802.11 wireless networks. Due to the randomness of DCF, the coding delay, defined as the time that a packet must wait for a coding opportunity, may increase and degrade the network performance. In this paper, we study the potential impact of the coding delay in the performance of TCP over IEEE 802.11s infrastructure wireless mesh networks. By means of simulation, we evaluate the formation of coding opportunities at the mesh access points. We find that as TCP traffic increases, the coding opportunities rise up to 70% and the coding delay increases considerably. We propose to adjust dynamically the maximum time that a packet can wait in the coding queues to reduce the coding delay. We evaluate different moving-average estimation methods for this aim. Our results show that the coding delay may be reduced with these methods using at the same time an estimation threshold. This threshold increases the estimation's mean in order to exploit a high percentage of the coding opportunities. Keywords: moving average processes; network coding; transport protocols; wireless LAN; wireless mesh networks; DCF; IEEE 802.11s infrastructure wireless mesh networks; TCP traffic increases; coding delay; coding opportunity; coding queues; distributed coordination function; mesh access points; moving-average estimation methods; network coding; Delays; Encoding; IEEE 802.11 Standards; Markov processes; Network coding; Wireless networks; IEEE 802.11s;mesh networks; network coding (ID#:14-2434) URL:
  • Nabaee, M.; Labeau, F., "Bayesian Quantized Network Coding Via Generalized Approximate Message Passing," Wireless Telecommunications Symposium (WTS), 2014, pp.1,7, 9-11 April 2014. doi: 10.1109/WTS.2014.6834995 In this paper, we study message passing-based decoding of real network coded packets. We explain our developments on the idea of using real field network codes for distributed compression of inter-node correlated messages. Then, we discuss the use of iterative message passing-based decoding for the described network coding scenario, as the main contribution of this paper. Motivated by Bayesian compressed sensing, we discuss the possibility of approximate decoding, even with fewer received measurements (packets) than the number of messages. As a result, our real field network coding scenario, called quantized network coding, is capable of inter-node compression without the need to know the inter-node redundancy of messages. We also present our numerical and analytic arguments on the robustness and computational simplicity (relative to the previously proposed linear programming and standard belief propagation) of our proposed decoding algorithm for the quantized network coding. Keywords: Bayes methods; compressed sensing; iterative decoding; linear programming; message passing; network coding; Bayesian compressed sensing; Bayesian quantized network coding; distributed compression; internode compression; internode correlated messages; iterative message passing-based decoding; linear programming; network coded packets; Bayes methods; Decoding; Message passing; Network coding; Noise; Noise measurement; Quantization (signal);Bayesian compressed sensing; Network coding; approximate message passing (ID#:14-2435) URL:
  • Shalaby, A; Ragab, M.E.-S.; Goulart, V.; Fujiwara, I; Koibuchi, M., "Hierarchical Network Coding for Collective Communication on HPC Interconnects," Parallel, Distributed and Network-Based Processing (PDP), 2014 22nd Euromicro International Conference on, vol., no., pp.98,102, 12-14 Feb. 2014. doi: 10.1109/PDP.2014.58 Network bandwidth is a performance concern especially for collective communication because the bisection bandwidth of recent supercomputers is far less than their full bisection bandwidth. In this context we propose to exploit the use of a network coding technique to reduce the number of unicasts and the size of transferred data generated by latency-sensitive collective communication in supercomputers. Our proposed network coding scheme has a hierarchical multicasting structure with intra-group and inter-group unicasts. Quantitative analysis show that the aggregate path hop counts by our hierarchical network coding decrease as much as 94% when compared to conventional unicast-based multicasts. We validate these results by cycle-accurate network simulations. In 1,024-switch networks, the network reduces the execution time of collective communication as much as 64%. We also show that our hierarchical network coding is beneficial for any packet size. Keywords: network coding; parallel machines; parallel processing; HPC interconnects; hierarchical multicasting structure; hierarchical network coding technique; inter-group unicasts; intra-group unicasts; latency-sensitive collective communication; network bandwidth; supercomputers; Aggregates; Bandwidth; Network coding; Network topology; Routing; Supercomputers; Topology; Interconnection networks; collective communication; high-performance computing; multicast algorithm; network coding (ID#:14-2436) URL:


Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to SoS.Project (at) for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.