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
مستوى الصوت68
رقم الإصدار7
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يوليو 2022
منشور خارجيًانعم

ملاحظة ببليوغرافية

Publisher Copyright:
© 1963-2012 IEEE.


أدرس بدقة موضوعات البحث “Latency and Alphabet Size in the Context of Multicast Network Coding'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا