Network coding: A computational perspective

Michael Langberg, Alexander Sprintson, Jehoshua Bruck

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by performing algebraic operations on packets received over incoming links. We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V,E) in time O( E kh + V k2h2 + h4 k3 (k + H), where k is the number of destinations and h is the number of packets. Our algorithm improves the best known running time for network code construction. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is upperbounded by O(h3k2). Next, we address the problem of finding integral and fractional network codes with the minimum number of encoding nodes. We prove that in the majority of settings this problem is NP-hard. However, we show that if h = O(1), k O(1), and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time.

שפה מקוריתאנגלית
עמודים (מ-עד)147-157
מספר עמודים11
כתב עתIEEE Transactions on Information Theory
כרך55
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2009

הערה ביבליוגרפית

Funding Information:
Manuscript received July 17, 2006; revised January 21, 2008. Current version published December 24, 2008. This work was supported in part by the Caltech Lee Center for Advanced Networking. M. Langberg is with the Computer Science Division, The Open University of Israel, Raanana 43107, Israel (e-mail: mikel@openu.ac.il). A. Sprintson is with the Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77845 USA (e-mail: spalex@tamu.edu). J. Bruck is with the Department of Electrical Engineering, California Institute of Technology, Pasadena, California 91125 USA (e-mail: bruck@caltech.edu). Communicated by M. Médard, Associate Editor for Communications. Color versions of Figures 3 and 6–8 in this paper are available online at http:// ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2008.2008135

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Network coding: A computational perspective'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי