Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. Algebraic algorithms for network information flow
 
doctoral thesis

Algebraic algorithms for network information flow

Ebrahimi Boroojeni, Javad  
2013

Ahlswede et al. in the seminal paper [1] have shown that in data transfer over networks, processing the data at the nodes can significantly improve the throughput. As proved by Li et al. in [2], even with a simple type of operation, namely linear operation, the throughput can still be vastly improved. In [3], it is shown that the multicasting problem over networks can be translated to an algebraic question about a polynomial associated to the network called network polynomial. In this thesis, we start from the algorithm of [3] and extend it in several directions. First, we generalize the framework of [3] to include the case where the messages can also be vectors over some fixed finite field. We also show that in contrast to the original algorithm, ours can be used to reduce the field size for the case of sending finite field elements. In both vector network code algorithm and finite field minimization, we translate the network code design problems into an algebraic problem about network polynomials. Because of the importance of the network polynomials, we investigate more properties of them and we study the relationship between these objects and the topological properties of the network. Then, we extend the result of [3] to the deterministic models for wireless relay networks, a very important class of networks that has been introduced in [4] by Avestimehr, Diggavi and Tse. Finally, for another class of networks, called broadcast networks, we introduce the transfer matrix and using its properties, we show that in the absence of public messages, processing the information at the nodes will not improve the throughput.

  • Files
  • Details
  • Metrics
Type
doctoral thesis
DOI
10.5075/epfl-thesis-5851
Author(s)
Ebrahimi Boroojeni, Javad  
Advisors
Fragouli, Christina  
Jury

F. Eisenbrand (président), A. Orlitsky, O.N.A. Svensson, A. Özgur Aydin

Date Issued

2013

Publisher

EPFL

Publisher place

Lausanne

Public defense year

2013-08-29

Thesis number

5851

Subjects

Network Coding

•

Information Flow

•

ADT Network

•

Vector Network Code

•

Algorithm

EPFL units
ARNI  
Faculty
IC  
School
IIF  
Doctoral School
EDIC  
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/94088
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés