Untrusting network coding

In networks that perform linear network coding, an intermediate network node may receive a much larger number of linear equations of the source symbols than the number of messages it needs to send. For networks constructed by untrusted nodes, we propose a relaxed measure of security: we want to be untrusting, and allow each intermediate node to only learn as much information as the number of independent messages it needs to send. In this paper we formulate this problem and provide sufficient and necessary conditions for classes of combination networks. ©2012 IEEE.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Yasin Buyukalp, Christina Fragouli, Ghid Maatouk, Vinod Malathidevi Prabhakaran
2012
Article de conférence

Résumé

Official source

https://infoscience.epfl.ch/record/185108?ln=fr

À propos de ce résultat

Concepts associés (8)

Concepts associés

Chargement

Publications associées (6)

Publications associées

Chargement

Information Flow Decomposition for Network Coding

Christina Fragouli, Emina Soljanin

The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. The main idea in this paper is the identification of structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition allows us to show that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size and calculate the throughput improvement network coding can offer for different configurations. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.

2006

Chargement

Information Flow Decomposition for Network Coding

Christina Fragouli, Emina Soljanin

2004

Chargement

Bottleneck Discovery and Overlay Management in Network Coded Peer-to-Peer Systems

Suhas Diggavi, Christina Fragouli, Mahdi Jafari Siavoshani

The performance of peer-to-peer (P2P) networks depends critically on the good connectivity of the overlay topology. In this paper we study P2P networks for content distribution (such as Avalanche) that use randomized network coding techniques. The basic idea of such systems is that peers randomly combine and exchange linear combinations of the source packets. A header appended to each packet specifies the linear combination that the packet carries. In this paper we show that the linear combinations a node receives from its neighbors reveal structural information about the network. We propose algorithms to utilize this observation for topology management to avoid bottlenecks and clustering in network-coded P2P systems. Our approach is decentralized, inherently adapts to the network topology, and reduces substantially the number of topology rewirings that are necessary to maintain a well connected overlay. Moreover, this is done passively during the normal content distribution. This work demonstrates another value of using network coding and complements previous work that showed network coding achieves high utilization of the network resources.

2007

Chargement

Nombre

Un nombre est un concept permettant d’évaluer et de comparer des quantités ou des rapports de grandeurs, mais aussi d’ordonner des éléments en indiquant leur rang. Souvent écrits à l’aide d’un ou pl

Équation linéaire

Une équation à coefficients réels ou complexes est dite linéaire quand elle peut être présentée sous la forme : ax = b ou, de manière équivalente : ax – b = 0, où x est l'inconnue, a et b sont deux

Linear network coding

In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations. Linear network coding may be use