Latency and Alphabet Size in the Context of Multicast Network Coding

Mira Gonen, Michael Langberg, Alex Sprintson

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


We study the relation between latency and alphabet size in the context of Multicast Network Coding. Given a graph G = (V, E) representing a communication network, a subset S \subseteq V of sources, each of which initially holds a set of information messages, and a set T \subseteq V of terminals; we consider the problem in which one wishes to design a communication scheme that eventually allows all terminals to obtain all the messages held by the sources. In this study we assume that communication is performed in rounds, where in each round each network node may transmit a single (possibly encoded) information packet on any of its outgoing edges. The objective is to minimize the communication latency, i.e., number of communication rounds needed until all terminals have all the messages of the source nodes. For sufficiently large alphabet sizes (i.e., large block length, packet sizes), it is known that traditional linear multicast network coding techniques (such as random linear network coding) minimize latency. In this work we seek to study the task of minimizing latency in the setting of limited alphabet sizes (i.e., finite block length), and alternatively, the task of minimizing the alphabet size in the setting of bounded latency. We focus on the establishing the computation complexity of the problem and present several intractability results. In particular, through reductive arguments, we prove that it is NP-hard to (i) approximate (and in particular to determine) the minimum alphabet size given a latency constraint; (ii) approximate (and in particular to determine) the minimum latency of communication schemes in the setting of limited alphabet sizes.

שפה מקוריתאנגלית
מספר המאמר7
עמודים (מ-עד)4289-4300
מספר עמודים12
כתב עתIEEE Transactions on Information Theory
מספר גיליון7
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 2022
פורסם באופן חיצוניכן

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

Publisher Copyright:
© 1963-2012 IEEE.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Latency and Alphabet Size in the Context of Multicast Network Coding'. יחד הם יוצרים טביעת אצבע ייחודית.

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