BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Neda Aboutorab

Neda Aboutorab appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITNetworking and Internet Architecture

Catalog footprint

What is connected

16works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2022arXiv

On the Optimality of Linear Index Coding over the Fields with Characteristic Three

It has been known that the insufficiency of linear coding in achieving the optimal rate of the general index coding problem is rooted in its rate's dependency on the field size. However, this dependency has been described only through the two well-known matroid instances, namely the Fano and non-Fano matroids, which, in turn, limits its scope only to the fields with characteristic two. In this paper, we extend this scope to demonstrate the reliance of linear index coding rate on fields with characteristic three. By constructing two index coding instances of size 29, we prove that for the first instance, linear coding is optimal only over the fields with characteristic three, and for the second instance, linear coding over any field with characteristic three can never be optimal. Then, a variation of the second instance is designed as the third index coding instance of size 58. For this instance, it is proved that while linear coding over any field with characteristic three cannot be optimal, there exists a nonlinear code over the fields with characteristic three, which achieves its optimal rate. Connecting the first and third index coding instances in two specific ways, called no-way and two-way connections, will lead to two new index coding instances of size 87 and 91, for which linear coding is outperformed by nonlinear codes. Another main contribution of this paper is the reduction of the key constraints on the space of the linear coding for the first and second index coding instances, each of size 29, into a matroid instance with the ground set of size 9, whose linear representability is dependent on the fields with characteristic three. The proofs and discussions provided in this paper through using these two relatively small matroid instances will shed light on the underlying reason causing the linear coding to become insufficient for the general index coding problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Independent User Partition Multicast Scheme for the Groupcast Index Coding Problem

The groupcast index coding (GIC) problem is a generalization of the index coding problem, where one packet can be demanded by multiple users. In this paper, we propose a new coding scheme called independent user partition multicast (IUPM) for the GIC problem. The novelty of this scheme compared to the user partition multicast (UPM) (Shanmugam \textit{et al.}, 2015) is in removing redundancies in the UPM solution by eliminating the linearly dependent coded packets. We also prove that the UPM scheme subsumes the packet partition multicast (PPM) scheme (Tehrani \textit{et al.}, 2012). Hence, the IUPM scheme is a generalization of both PPM and UPM schemes. Furthermore, inspired by jointly considering users and packets, we modify the approximation partition multicast (CAPM) scheme (Unal and Wagner, 2016) to achieve a new polynomial-time algorithm for solving the general GIC problem. We characterize a class of GIC problems with $\frac{k(k-1)}{2}$ packets, for any integer $k\geq 2$, for which the IUPM scheme is optimal. We also prove that for this class, the broadcast rate of the proposed new heuristic algorithm is $k$, while the broadcast rate of the CAPM scheme is $\mathcal{O}(k^2)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Secure Index Coding with Security Constraints on Receivers

Index coding is concerned with efficient broadcast of a set of messages to receivers in the presence of receiver side information. In this paper, we study the secure index coding problem with security constraints on the receivers themselves. That is, for each receiver there is a single legitimate message it needs to decode and a prohibited message list, none of which should be decoded by that receiver. To this end, our contributions are threefold. We first introduce a secure linear coding scheme, which is an extended version of the fractional local partial clique covering scheme that was originally devised for non-secure index coding. We then develop two information-theoretic bounds on the performance of any valid secure index code, namely secure polymatroidal outer bound (on the capacity region) and secure maximum acyclic induced subgraph lower bound (on the broadcast rate). The structure of these bounds leads us to further develop two necessary conditions for a given index coding problem to be securely feasible (i.e., to have nonzero rates).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Network-Coded Macrocell Offloading in Femtocaching-Assisted Cellular Networks

The femtocaching idea was proposed as a solution to compensate for the weak backhaul capacity, by deploying coverage-limited nodes with high storage capacity called femtocaches (FCs). In this paper, the macrocell offloading problem in femtocaching-assisted cellular networks is investigated. The objective is to minimize the number of transmissions by the macrocell base station (MBS) given that all requests should be served simultaneously to satisfy quality-of-experience (QoE) of the clients. We first formulate this MBS offloading problem as an optimization problem over a network coding graph, and show that it is NP-hard. Therefore, we propose an ONC-broadcast offloading scheme that exploits both broadcasting and opportunistic network coding (ONC) to minimize the number of required MBS transmissions. We utilize a random graph model to approximate the performance of the proposed ONC-broadcast scheme in terms of the resultant average number of transmissions by the MBS. Moreover, despite the complexity of finding the optimal solution for each and every case, we prove that this ONC-broadcast scheme is asymptotically optimal, i.e., for large number of requests, the ONC-broadcast scheme achieves a similar macrocell offloading performance to that of the optimal solution. To implement the ONC-broadcast scheme, we devise a heuristic that employs a dual conflict graph or broadcasting at the FCs such that the remaining requests can be served using the minimum number of transmissions at the MBS. Simulations show that the dual graph scheme improves MBS offloading as compared to the traditional separate graph scheme. Furthermore, the simple heuristic proposed to implement the ONC-broadcast scheme achieves a very close performance to the optimal ONC-broadcast scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Graph Model for Opportunistic Network Coding

Recent advancements in graph-based analysis and solutions of instantly decodable network coding (IDNC) trigger the interest to extend them to more complicated opportunistic network coding (ONC) scenarios, with limited increase in complexity. In this paper, we design a simple IDNC-like graph model for a specific subclass of ONC, by introducing a more generalized definition of its vertices and the notion of vertex aggregation in order to represent the storage of non-instantly-decodable packets in ONC. Based on this representation, we determine the set of pairwise vertex adjacency conditions that can populate this graph with edges so as to guarantee decodability or aggregation for the vertices of each clique in this graph. We then develop the algorithmic procedures that can be applied on the designed graph model to optimize any performance metric for this ONC subclass. A case study on reducing the completion time shows that the proposed framework improves on the performance of IDNC and gets very close to the optimal performance.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Instantly Decodable Network Coding for Real-Time Scalable Video Broadcast over Wireless Networks

In this paper, we study a real-time scalable video broadcast over wireless networks in instantly decodable network coded (IDNC) systems. Such real-time scalable video has a hard deadline and imposes a decoding order on the video layers.We first derive the upper bound on the probability that the individual completion times of all receivers meet the deadline. Using this probability, we design two prioritized IDNC algorithms, namely the expanding window IDNC (EW-IDNC) algorithm and the non-overlapping window IDNC (NOW-IDNC) algorithm. These algorithms provide a high level of protection to the most important video layer before considering additional video layers in coding decisions. Moreover, in these algorithms, we select an appropriate packet combination over a given number of video layers so that these video layers are decoded by the maximum number of receivers before the deadline. We formulate this packet selection problem as a two-stage maximal clique selection problem over an IDNC graph. Simulation results over a real scalable video stream show that our proposed EW-IDNC and NOW-IDNC algorithms improve the received video quality compared to the existing IDNC algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Deterministic Linear Network Coded Broadcast and Its Relation to Matroid Theory

Deterministic linear network coding (DLNC) is an important family of network coding techniques for wireless packet broadcast. In this paper, we show that DLNC is strongly related to and can be effectively studied using matroid theory without bridging index coding. We prove the equivalence between the DLNC solution and matrix matroid. We use this equivalence to study the performance limits of DLNC in terms of the number of transmissions and its dependence on the finite field size. Specifically, we derive the sufficient and necessary condition for the existence of perfect DLNC solutions and prove that such solutions may not exist over certain finite fields. We then show that identifying perfect solutions over any finite field is still an open problem in general. To fill this gap, we develop a heuristic algorithm which employs graphic matroids to find perfect DLNC solutions over any finite field. Numerical results show that its performance in terms of minimum number of transmissions is close to the lower bound, and is better than random linear network coding when the field size is not so large.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Performance Characterization and Transmission Schemes for Instantly Decodable Network Coding in Wireless Broadcast

We consider broadcasting a block of packets to multiple wireless receivers under random packet erasures using instantly decodable network coding (IDNC). The sender first broadcasts each packet uncoded once, then generates coded packets according to receivers' feedback about their missing packets. We focus on strict IDNC (S-IDNC), where each coded packet includes at most one missing packet of every receiver. But we will also compare it with general IDNC (G-IDNC), where this condition is relaxed. We characterize two fundamental performance limits of S-IDNC: 1) the number of transmissions to complete the broadcast, and 2) the average delay for a receiver to decode a packet. We derive a closed-form expression for the expected minimum number of transmissions in terms of the number of packets and receivers and the erasure probability. We prove that it is NP-hard to minimize the decoding delay of S-IDNC. We also derive achievable upper bounds on the above two performance limits. We show that G-IDNC can outperform S-IDNC %in terms of the number of transmissions without packet erasures, but not necessarily with packet erasures. Next, we design optimal and heuristic S-IDNC transmission schemes and coding algorithms with full/intermittent receiver feedback. We present simulation results to corroborate the developed theory and compare with existing schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Random Linear Network Coding for Wireless Layered Video Broadcast: General Design Methods for Adaptive Feedback-free Transmission

This paper studies the problem of broadcasting layered video streams over heterogeneous single-hop wireless networks using feedback-free random linear network coding (RLNC). We combine RLNC with unequal error protection (UEP) and our main purpose is twofold. First, to systematically investigate the benefits of UEP+RLNC layered approach in servicing users with different reception capabilities. Second, to study the effect of not using feedback, by comparing feedback-free schemes with idealistic full-feedback schemes. To these ends, we study `expected percentage of decoded frames' as a key content-independent performance metric and propose a general framework for calculation of this metric, which can highlight the effect of key system, video and channel parameters. We study the effect of number of layers and propose a scheme that selects the optimum number of layers adaptively to achieve the highest performance. Assessing the proposed schemes with real H.264 test streams, the trade-offs among the users' performances are discussed and the gain of adaptive selection of number of layers to improve the trade-offs is shown. Furthermore, it is observed that the performance gap between the proposed feedback-free scheme and the idealistic scheme is very small and the adaptive selection of number of video layers further closes the gap.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

In Order Packet Delivery in Instantly Decodable Network Coded Systems over Wireless Broadcast

In this paper, we study in-order packet delivery in instantly decodable network coded systems for wireless broadcast networks. We are interested in applications, in which the successful delivery of a packet depends on the correct reception of this packet and all its preceding packets. We formulate the problem of minimizing the number of undelivered packets to all receivers over all transmissions until completion as a stochastic shortest path (SSP) problem. Although finding the optimal packet selection policy using SSP is computationally complex, it allows us to systematically exploit the problem structure and draw guidelines for efficient packet selection policies that can reduce the number of undelivered packets to all receivers over all transmissions until completion. According to these guidelines, we design a simple heuristic packet selection algorithm. Simulation results illustrate that our proposed algorithm provides quicker packet delivery to the receivers compared to the existing algorithms in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Inter-session Network Coding for Transmitting Multiple Layered Streams over Single-hop Wireless Networks

This paper studies the problem of transmitting multiple independent layered video streams over single-hop wireless networks using network coding (NC). We combine feedback-free random linear NC (RLNC) with unequal error protection (UEP) and our goal is to investigate the benefits of coding across streams, i.e. inter session NC. To this end, we present a transmission scheme that in addition to mixing packets of different layers of each stream (intra-session NC), mixes packets of different streams as well. Then, we propose the analytical formulation of the layer decoding probabilities for each user and utilize it to define a theoretical performance metric. Assessing this performance metric under various scenarios, it is observed that inter-session NC improves the trade-off among the performances of users. Furthermore, the analytical results show that the throughput gain of inter-session NC over intra-session NC increases with the number of independent streams and also by increasing packet error rate, but degrades as network becomes more heterogeneous.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Queued cross-bar network models for replication and coded storage systems

Coding techniques may be useful for data center data survivability as well as for reducing traffic congestion. We present a queued cross-bar network (QCN) method that can be used for traffic analysis of both replication/uncoded and coded storage systems. We develop a framework for generating QCN rate regions (RRs) by analyzing their conflict graph stable set polytopes (SSPs). In doing so, we apply recent results from graph theory on the characterization of particular graph SSPs. We characterize the SSP of QCN conflict graphs under a variety of traffic patterns, allowing for their efficient RR computation. For uncoded systems, we show how to compute RRs and find rate optimal scheduling algorithms. For coded storage, we develop a RR upper bound, for which we provide an intuitive interpretation. We show that the coded storage RR upper bound is achievable in certain coded systems in which drives store sufficient coded information, as well in certain dynamic coding systems. Numerical illustrations show that coded storage can result in gains in RR volume of approximately 50%, averaged across traffic patterns.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scheduling Advantages of Network Coded Storage in Point-to-Multipoint Networks

We consider scheduling strategies for point-to-multipoint (PMP) storage area networks (SANs) that use network coded storage (NCS). In particular, we present a simple SAN system model, two server scheduling algorithms for PMP networks, and analytical expressions for internal and external blocking probability. We point to select scheduling advantages in NCS systems under normal operating conditions, where content requests can be temporarily denied owing to finite system capacity from drive I/O access or storage redundancy limitations. NCS can lead to improvements in throughput and blocking probability due to increased immediate scheduling options, and complements other well documented NCS advantages such as regeneration, and can be used as a guide for future storage system design.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

From Instantly Decodable to Random Linear Network Coding

Our primary goal in this paper is to traverse the performance gap between two linear network coding schemes: random linear network coding (RLNC) and instantly decodable network coding (IDNC) in terms of throughput and decoding delay. We first redefine the concept of packet generation and use it to partition a block of partially-received data packets in a novel way, based on the coding sets in an IDNC solution. By varying the generation size, we obtain a general coding framework which consists of a series of coding schemes, with RLNC and IDNC identified as two extreme cases. We then prove that the throughput and decoding delay performance of all coding schemes in this coding framework are bounded between the performance of RLNC and IDNC and hence throughput-delay tradeoff becomes possible. We also propose implementations of this coding framework to further improve its throughput and decoding delay performance, to manage feedback frequency and coding complexity, or to achieve in-block performance adaption. Extensive simulations are then provided to verify the performance of the proposed coding schemes and their implementations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Improving the Balance between the Completion Time and Decoding Delay in Instantly Decodable Network Coded Systems

This paper studies the complicated interplay of the completion time (as a measure of throughput) and the decoding delay performance in instantly decodable network coded (IDNC) systems over wireless broadcast erasure channels with memory, and proposes two new algorithms that improve the balance between the completion time and decoding delay of broadcasting a block of packets. We first formulate the IDNC packet selection problem that provides joint control of the completion time and decoding delay as a statistical shortest path (SSP) problem. However, since finding the optimal packet selection policy using the SSP technique is computationally complex, we employ its geometric structure to find some guidelines and use them to propose two heuristic packet selection algorithms that can efficiently improve the balance between the completion time and decoding delay for broadcast erasure channels with a wide range of memory conditions. It is shown that each one of the two proposed algorithms is superior for a specific range of memory conditions. Furthermore, we show that the proposed algorithms achieve an improved fairness in terms of the decoding delay across all receivers.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Throughput and Decoding Delay Performance of Instantly Decodable Network Coding

In this paper, a comprehensive study of packet-based instantly decodable network coding (IDNC) for single-hop wireless broadcast is presented. The optimal IDNC solution in terms of throughput is proposed and its packet decoding delay performance is investigated. Lower and upper bounds on the achievable throughput and decoding delay performance of IDNC are derived and assessed through extensive simulations. Furthermore, the impact of receivers' feedback frequency on the performance of IDNC is studied and optimal IDNC solutions are proposed for scenarios where receivers' feedback is only available after and IDNC round, composed of several coded transmissions. However, since finding these IDNC optimal solutions is computational complex, we further propose simple yet efficient heuristic IDNC algorithms. The impact of system settings and parameters such as channel erasure probability, feedback frequency, and the number of receivers is also investigated and simple guidelines for practical implementations of IDNC are proposed.

0 citations0 reviewsNo code linkedOpen access