112 results on '"Malak, Derya"'
Search Results
2. Multi-Server Multi-Function Distributed Computation
- Author
-
Malak, Derya, Salehi, Mohammad Reza Deylam, Serbetci, Berksan, and Elia, Petros
- Subjects
Computer Science - Information Theory - Abstract
The work here studies the communication cost for a multi-server multi-task distributed computation framework, and does so for a broad class of functions and data statistics. Considering the framework where a user seeks the computation of multiple complex (conceivably non-linear) tasks from a set of distributed servers, we establish communication cost upper bounds for a variety of data statistics, function classes and data placements across the servers. To do so, we proceed to apply, for the first time here, K\"orner's characteristic graph approach -- which is known to capture the structural properties of data and functions -- to the promising framework of multi-server multi-task distributed computing. Going beyond the general expressions, and in order to offer clearer insight, we also consider the well-known scenario of cyclic dataset placement and linearly separable functions over the binary field, in which case our approach exhibits considerable gains over the state of art. Similar gains are identified for the case of multi-linear functions., Comment: Submitted to Entropy
- Published
- 2024
3. Distributed Structured Matrix Multiplication
- Author
-
Malak, Derya
- Subjects
Computer Science - Information Theory - Abstract
We devise achievable encoding schemes for distributed source compression for computing inner products, symmetric matrix products, and more generally, square matrix products, which are a class of nonlinear transformations. To that end, our approach relies on devising nonlinear mappings of distributed sources, which are then followed by the structured linear encoding scheme, introduced by K\"orner and Marton. For different computation scenarios, we contrast our findings on the achievable sum rate with the state of the art to demonstrate the possible savings in compression rate. When the sources have special correlation structures, it is possible to achieve unbounded gains, as demonstrated by the analysis and numerical simulations., Comment: Proc., IEEE ISIT 2024
- Published
- 2024
4. Distributed Computing of Functions of Structured Sources with Helper Side Information
- Author
-
Malak, Derya
- Subjects
Computer Science - Information Theory - Abstract
In this work, we consider the problem of distributed computing of functions of structured sources, focusing on the classical setting of two correlated sources and one user that seeks the outcome of the function while benefiting from low-rate side information provided by a helper node. Focusing on the case where the sources are jointly distributed according to a very general mixture model, we here provide an achievable coding scheme that manages to substantially reduce the communication cost of distributed computing by exploiting the nature of the joint distribution of the sources, the side information, as well as the symmetry enjoyed by the desired functions. Our scheme -- which can readily apply in a variety of real-life scenarios including learning, combinatorics, and graph neural network applications -- is here shown to provide substantial reductions in the communication costs, while simultaneously providing computational savings by reducing the exponential complexity of joint decoding techniques to a complexity that is merely linear., Comment: SPAWC2023
- Published
- 2023
5. Weighted Graph Coloring for Quantized Computing
- Author
-
Malak, Derya
- Subjects
Computer Science - Information Theory - Abstract
We consider the problem of distributed lossless computation of a function of two sources by one common user. To do so, we first build a bipartite graph, where two disjoint parts denote the individual source outcomes. We then project the bipartite graph onto each source to obtain an edge-weighted characteristic graph (EWCG), where edge weights capture the function's structure, by how much the source outcomes are to be distinguished, generalizing the classical notion of characteristic graphs. Via exploiting the notions of characteristic graphs, the fractional coloring of such graphs, and edge weights, the sources separately build multi-fold graphs that capture vector-valued source sequences, determine vertex colorings for such graphs, encode these colorings, and send them to the user that performs minimum-entropy decoding on its received information to recover the desired function in an asymptotically lossless manner. For the proposed EWCG compression setup, we characterize the fundamental limits of distributed compression, verify the communication complexity through an example, contrast it with traditional coloring schemes, and demonstrate that we can attain compression gains higher than $\% 30$ over traditional coloring., Comment: appeared in IEEE ISIT 2023
- Published
- 2023
6. FlEC: Enhancing QUIC with application-tailored reliability mechanisms
- Author
-
Michel, François, Cohen, Alejandro, Malak, Derya, De Coninck, Quentin, Médard, Muriel, and Bonaventure, Olivier
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
Packet losses are common events in today's networks. They usually result in longer delivery times for application data since retransmissions are the de facto technique to recover from such losses. Retransmissions is a good strategy for many applications but it may lead to poor performance with latency-sensitive applications compared to network coding. Although different types of network coding techniques have been proposed to reduce the impact of losses by transmitting redundant information, they are not widely used. Some niche applications include their own variant of Forward Erasure Correction (FEC) techniques, but there is no generic protocol that enables many applications to easily use them. We close this gap by designing, implementing and evaluating a new Flexible Erasure Correction (FlEC) framework inside the newly standardized QUIC protocol. With FlEC, an application can easily select the reliability mechanism that meets its requirements, from pure retransmissions to various forms of FEC. We consider three different use cases: $(i)$ bulk data transfer, $(ii)$ file transfers with restricted buffers and $(iii)$ delay-constrained messages. We demonstrate that modern transport protocols such as QUIC may benefit from application knowledge by leveraging this knowledge in FlEC to provide better loss recovery and stream scheduling. Our evaluation over a wide range of scenarios shows that the FlEC framework outperforms the standard QUIC reliability mechanisms from a latency viewpoint.
- Published
- 2022
7. The Interplay of Spectral Efficiency, User Density, and Energy in Grant-based Access Protocols
- Author
-
Malak, Derya
- Subjects
Computer Science - Information Theory - Abstract
We employ grant-based access with retransmissions for multiple users with small payloads, particularly at low spectral efficiency (SE). The radio resources are allocated via NOMA in the time into $T$ slots and frequency dimensions, with a measure of non-orthogonality $\eta$. Retransmissions are stored in a receiver buffer with a finite size $C_{\sf buf}$ and combined via HARQ, using Chase Combining (CC) and Incremental Redundancy (IR). We determine the best scaling for the SE (bits/rdof) and for the user density $J/n$, for a given number of users $J$ and a blocklength $n$, versus SNR ($\rho$) per bit, i.e., the ratio $E_b/N_0$, for the sum-rate optimal regime and when the interference is treated as noise (TIN), using a finite blocklength analysis. Contrasting the classical scheme (no retransmissions) with CC-NOMA, CC-OMA, and IR-OMA strategies in TIN and sum-rate optimal cases, the numerical results on the SE demonstrate that CC-NOMA outperforms, almost in all regimes, the other approaches. In the sum-rate optimal regime, the scalings of $J/n$ versus $E_b/N_0$ deteriorate with $T$, yet from the most degraded to the least, the ordering of the schemes is as (i) classical, (ii) CC-OMA, (iii) IR-OMA, and (iv) CC-NOMA, demonstrating the robustness of CC-NOMA. Contrasting TIN models at low $\rho$, the scalings of $J/n$ for CC-based models improve the best, whereas, at high $\rho$, the scaling of CC-NOMA is poor due to higher interference, and CC-OMA becomes prominent due to combining retransmissions and its reduced interference. The scaling results are applicable over a range of $\eta$, $T$, $C_{\sf buf}$, and $J$, at low received SNR. The proposed analytical framework provides insights into resource allocation in grant-based access and specific 5G use cases for massive URLLC uplink access., Comment: A short version in WiOpt'22, and this version in TCOM'24
- Published
- 2022
8. Fractional Graph Coloring for Functional Compression with Side Information
- Author
-
Malak, Derya
- Subjects
Computer Science - Information Theory - Abstract
We describe a rational approach to reduce the computational and communication complexities of lossless point-to-point compression for computation with side information. The traditional method relies on building a characteristic graph with vertices representing the source symbols and with edges that assign a source symbol to a collection of independent sets to be distinguished for the exact recovery of the function. Our approach uses fractional coloring for a b-fold coloring of characteristic graphs to provide a linear programming relaxation to the traditional coloring method and achieves coding at a fine-grained granularity. We derive the fundamental lower bound for compression, given by the fractional characteristic graph entropy, through generalizing the notion of K\"orner's graph entropy. We demonstrate the coding gains of fractional coloring over traditional coloring via a computation example. We conjecture that the integrality gap between fractional coloring and traditional coloring approaches the smallest b that attains the fractional chromatic number to losslessly represent the independent sets for a given characteristic graph, up to a linear scaling which is a function of the fractional chromatic number., Comment: Note: The author fully agrees with the independent set-based definition in Theorem 21.2 in "Network Information Theory", El Gamal and Kim
- Published
- 2022
9. Transmission Delay Minimization via Joint Power Control and Caching in Wireless HetNets
- Author
-
Malak, Derya, Mutlu, Faruk V., Zhang, Jinkun, and Yeh, Edmund M.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
A fundamental challenge in wireless heterogeneous networks (HetNets) is to effectively utilize the limited transmission and storage resources in the presence of increasing deployment density and backhaul capacity constraints. To alleviate bottlenecks and reduce resource consumption, we design optimal caching and power control algorithms for multi-hop wireless HetNets. We formulate a joint optimization framework to minimize the average transmission delay as a function of the caching variables and the signal-to-interference-plus-noise ratios (SINR) which are determined by the transmission powers, while explicitly accounting for backhaul connection costs and the power constraints. Using convex relaxation and rounding, we obtain a reduced-complexity formulation (RCF) of the joint optimization problem, which can provide a constant factor approximation to the globally optimal solution. We then solve RCF in two ways: 1) alternating optimization of the power and caching variables by leveraging biconvexity, and 2) joint optimization of power control and caching. We characterize the necessary (KKT) conditions for an optimal solution to RCF, and use strict quasi-convexity to show that the KKT points are Pareto optimal for RCF. We then devise a subgradient projection algorithm to jointly update the caching and power variables, and show that under appropriate conditions, the algorithm converges at a linear rate to the local minima of RCF, under general SINR conditions. We support our analytical findings with results from extensive numerical experiments., Comment: Supplementary material for conference submission
- Published
- 2021
10. Distributed Computation over MAC via Kolmogorov-Arnold Representation
- Author
-
Malak, Derya and Tajer, Ali
- Subjects
Computer Science - Information Theory - Abstract
Kolmogorov's representation theorem provides a framework for decomposing any arbitrary real-valued, multivariate, and continuous function into a two-layer nested superposition of a finite number of functions. The functions at these two layers, are referred to as the inner and outer functions with the key property that the design of the inner functions is independent of that of the original function of interest to be computed. This brings modularity and universality to the design of the inner function, and subsequently, a part of computation. This paper capitalizes on such modularity and universality in functional representation to propose two frameworks for distributed computation over the additive multiple access channels (MACs). In the first framework, each source encodes the inner representations and sends them over the additive MAC. Subsequently, the receiver computes the outer functions to compute the function of interest. Transmitting the values of the inner functions instead of the messages directly leads to compression gains. In the second approach, in order to further increase the compression rate, the framework aims to also bring computing the outer functions to the source sites. Specifically, each source employs a graph-coloring-based approach to perform joint functional compression of the inner and the outer functions, which may attain further compression savings over the former. These modular encoding schemes provide an exact representation in the asymptotic regime and the non-asymptotic regime. Contrasting these with the baseline model where sources directly transmit data over MAC, we observe gains. To showcase the gains of these two frameworks and their discrepancies, they are applied to a number of commonly used computations in distributed systems, e.g., computing products, $\ell_m$-norms, polynomial functions, extremum values of functions, and affine transformations.
- Published
- 2021
11. Hardware-Limited Task-Based Quantization in Systems
- Author
-
Malak, Derya, Yazicigil, Rabia, Médard, Muriel, Zhang, Xing, Eldar, Yonina C., Tietjen, Jill S., Series Editor, Greco, Maria Sabrina, editor, Cassioli, Dajana, editor, Ullo, Silvia Liberata, editor, and Lyons, Margaret J., editor
- Published
- 2023
- Full Text
- View/download PDF
12. Applications of Common Information to Computing Functions
- Author
-
Malak, Derya
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We design a low complexity distributed compression scheme for computing arbitrary functions of sources with discrete alphabets. We use a helper-based method that extends the definition of the G{\'a}cs-K{\"o}rner-Witsenhausen (GKW) common information to functional common information. The helper relaxes the combinatorial structure of GKW by partitioning the joint source distribution into nests imposed by the function, which ensures hierarchical cooperation between the sources for effectively distributed computing. By contrasting our approach's performance with existing efficient techniques, we demonstrate the rate savings in recovering function and source data. Permutation invariant functions are prevalent in learning and combinatorial optimization fields and most recently applied to graph neural networks. We consider the efficient compression for computing permutation invariant functions in a network with two sources and one decoder. We use a bipartite graph representation, where two disjoint sets of vertices (parts) denote the individual source graphs and the edge weights capture the joint source distribution. We compress bipartite graphs by creating connected components determined by the function's distribution, accounting for the edge symmetries, and eliminating the low probability edges. We separately encode those edges and send them as refinements. Our approach can substitute high complexity joint decoding techniques and inform neural networks to reduce the computing time and reduce complexity., Comment: submitted for possible publication
- Published
- 2021
13. A Distributed Computationally Aware Quantizer Design via Hyper Binning
- Author
-
Malak, Derya and Médard, Muriel
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We design a distributed function-aware quantization scheme for distributed functional compression. We consider $2$ correlated sources $X_1$ and $X_2$ and a destination that seeks an estimate $\hat{f}$ for the outcome of a continuous function $f(X_1,\,X_2)$. We develop a compression scheme called hyper binning in order to quantize $f$ via minimizing the entropy of joint source partitioning. Hyper binning is a natural generalization of Cover's random code construction for the asymptotically optimal Slepian-Wolf encoding scheme that makes use of orthogonal binning. The key idea behind this approach is to use linear discriminant analysis in order to characterize different source feature combinations. This scheme captures the correlation between the sources and the function's structure as a means of dimensionality reduction. We investigate the performance of hyper binning for different source distributions and identify which classes of sources entail more partitioning to achieve better function approximation. Our approach brings an information theory perspective to the traditional vector quantization technique from signal processing., Comment: IEEE Transactions on Signal Processing
- Published
- 2020
14. Function Load Balancing over Networks
- Author
-
Malak, Derya and Médard, Muriel
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
Using networks as a means of computing can reduce the communication flow or the total number of bits transmitted over the networks. In this paper, we propose to distribute the computation load in stationary networks, and formulate a flow-based delay minimization problem that jointly captures the aspects of communications and computation. We exploit the distributed compression scheme of Slepian-Wolf that is applicable under any protocol information where nodes can do compression independently using different codebooks. We introduce the notion of entropic surjectivity as a measure to determine how sparse the function is and to understand the limits of functional compression for computation. We leverage Little's Law for stationary systems to provide a connection between surjectivity and the computation processing factor that reflects the proportion of flow that requires communications. This connection gives us an understanding of how much a node (in isolation) should compute to communicate the desired function within the network without putting any assumptions on the topology. Our results suggest that to effectively compute different function classes that have different entropic surjectivities, the networks can be re-structured with the transition probabilities being tailored for functions, i.e., task-based link reservations, which can enable mixing versus separately processing of a diverse function classes. They also imply that most of the available resources are reserved for computing low complexity functions versus fewer resources for processing of high complexity ones. We numerically evaluate our technique for search, MapReduce, and classification functions, and infer how sensitive the processing factor for each computation task to the entropic surjectivity is., Comment: arXiv admin note: text overlap with arXiv:1912.03531
- Published
- 2020
15. Spatial Concentration of Caching in Wireless Heterogeneous Networks
- Author
-
Malak, Derya, Médard, Muriel, and Andrews, Jeffrey G.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We propose a decentralized caching policy for wireless heterogeneous networks that makes content placement decisions based on pairwise interactions between cache nodes. We call our proposed scheme {\gamma}-exclusion cache placement (GEC), where a parameter {\gamma} controls an exclusion radius that discourages nearby caches from storing redundant content. GEC takes into account item popularity and the nodes' caching priorities and leverages negative dependence to relax the classic 0-1 knapsack problem to yield spatially balanced sampling across caches. We show that GEC guarantees a better concentration (reduced variance) of the required cache storage size than the state of the art, and that the cache size constraints can be satisfied with high probability. Given a cache hit probability target, we compare the 95\% confidence intervals of the required cache sizes for three caching schemes: (i) independent placement, (ii) hard exclusion caching (HEC), and (iii) the proposed GEC approach. For uniform spatial traffic, we demonstrate that GEC provides approximately a 3x and 2x reduction in required cache size over (i) and (ii), respectively. For non-uniform spatial traffic based on realistic peak-hour variations in urban scenarios, the gains are even greater., Comment: to appear, IEEE TWC. arXiv admin note: text overlap with arXiv:1901.11102
- Published
- 2020
16. How to Distribute Computation in Networks
- Author
-
Malak, Derya, Cohen, Alejandro, and Medard, Muriel
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
In network function computation is as a means to reduce the required communication flow in terms of number of bits transmitted per source symbol. However, the rate region for the function computation problem in general topologies is an open problem, and has only been considered under certain restrictive assumptions (e.g. tree networks, linear functions, etc.). In this paper, we propose a new perspective for distributing computation, and formulate a flow-based delay cost minimization problem that jointly captures the costs of communications and computation. We introduce the notion of entropic surjectivity as a measure to determine how sparse the function is and to understand the limits of computation. Exploiting Little's law for stationary systems, we provide a connection between this new notion and the computation processing factor that reflects the proportion of flow that requires communications. This connection gives us an understanding of how much a node (in isolation) should compute to communicate the desired function within the network without putting any assumptions on the topology. Our analysis characterizes the functions only via their entropic surjectivity, and provides insight into how to distribute computation. We numerically test our technique for search, MapReduce, and classification tasks, and infer for each task how sensitive the processing factor to the entropic surjectivity is., Comment: to appear in IEEE International Conference on Computer Communications (INFOCOM), Beijing, China, Apr. 2020
- Published
- 2019
17. Adaptive Causal Network Coding with Feedback
- Author
-
Cohen, Alejandro, Malak, Derya, Bracha, Vered Bar, and Medard, Muriel
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We propose a novel adaptive and causal random linear network coding (AC-RLNC) algorithm with forward error correction (FEC) for a point-to-point communication channel with delayed feedback. AC-RLNC is adaptive to the channel condition, that the algorithm estimates, and is causal, as coding depends on the particular erasure realizations, as reflected in the feedback acknowledgments. Specifically, the proposed model can learn the erasure pattern of the channel via feedback acknowledgments, and adaptively adjust its retransmission rates using a priori and posteriori algorithms. By those adjustments, AC-RLNC achieves the desired delay and throughput, and enables transmission with zero error probability. We upper bound the throughput and the mean and maximum in order delivery delay of AC-RLNC, and prove that for the point to point communication channel in the non-asymptotic regime the proposed code may achieve more than 90% of the channel capacity. To upper bound the throughput we utilize the minimum Bhattacharyya distance for the AC-RLNC code. We validate those results via simulations. We contrast the performance of AC-RLNC with the one of selective repeat (SR)-ARQ, which is causal but not adaptive, and is a posteriori. Via a study on experimentally obtained commercial traces, we demonstrate that a protocol based on AC-RLNC can, vis-`a-vis SR-ARQ, double the throughput gains, and triple the gain in terms of mean in order delivery delay when the channel is bursty. Furthermore, the difference between the maximum and mean in order delivery delay is much smaller than that of SR-ARQ. Closing the delay gap along with boosting the throughput is very promising for enabling ultra-reliable low-latency communications (URLLC) applications.
- Published
- 2019
18. Spatial Soft-Core Caching
- Author
-
Malak, Derya, Médard, Muriel, and Yeh, Edmund
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We propose a decentralized spatial soft-core cache placement (SSCC) policy for wireless networks. SSCC yields a spatially balanced sampling via negative dependence across caches, and can be tuned to satisfy cache size constraints with high probability. Given a desired cache hit probability, we compare the 95% confidence intervals of the required cache sizes for independent placement, hard-core placement and SSCC policies. We demonstrate that in terms of the required cache storage size, SSCC can provide up to more than 180% and 100% gains with respect to the independent and hard-core placement policies, respectively. SSCC can be used to enable proximity-based applications such as device-to-device communications and peer-to-peer networking as it promotes the item diversity and reciprocation among the nodes., Comment: submitted, IEEE ISIT, 2019
- Published
- 2019
19. Multi-Server Multi-Function Distributed Computation
- Author
-
Malak, Derya, primary, Deylam Salehi, Mohammad Reza, additional, Serbetci, Berksan, additional, and Elia, Petros, additional
- Published
- 2024
- Full Text
- View/download PDF
20. ARQ with Cumulative Feedback to Compensate for Burst Errors
- Author
-
Malak, Derya, Medard, Muriel, and Yeh, Edmund M.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We propose a cumulative feedback-based ARQ (CF ARQ) protocol for a sliding window of size 2 over packet erasure channels with unreliable feedback. We exploit a matrix signal-flow graph approach to analyze probability-generating functions of transmission and delay times. Contrasting its performance with that of the uncoded baseline scheme for ARQ, developed by Ausavapattanakun and Nosratinia, we demonstrate that CF ARQ can provide significantly less average delay under bursty feedback, and gains up to about 20% in terms of throughput. We also outline the benefits of CF ARQ under burst errors and asymmetric channel conditions. The protocol is more predictable across statistics, hence is more stable. This can help design robust systems when feedback is unreliable. This feature may be preferable for meeting the strict end-to-end latency and reliability requirements of future use cases of ultra-reliable low-latency communications in 5G, such as mission-critical communications and industrial control for critical control messaging., Comment: GLOBECOM'18. arXiv admin note: substantial text overlap with arXiv:1806.05776
- Published
- 2018
21. Tiny Codes for Guaranteeable Delay
- Author
-
Malak, Derya, Médard, Muriel, and Yeh, Edmund M.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
Future 5G systems will need to support ultra-reliable low-latency communications scenarios. From a latency-reliability viewpoint, it is inefficient to rely on average utility-based system design. Therefore, we introduce the notion of guaranteeable delay which is the average delay plus three standard deviations of the mean. We investigate the trade-off between guaranteeable delay and throughput for point-to-point wireless erasure links with unreliable and delayed feedback, by bringing together signal flow techniques to the area of coding. We use tiny codes, i.e. sliding window by coding with just 2 packets, and design three variations of selective-repeat ARQ protocols, by building on the baseline scheme, i.e. uncoded ARQ, developed by Ausavapattanakun and Nosratinia: (i) Hybrid ARQ with soft combining at the receiver; (ii) cumulative feedback-based ARQ without rate adaptation; and (iii) Coded ARQ with rate adaptation based on the cumulative feedback. Contrasting the performance of these protocols with uncoded ARQ, we demonstrate that HARQ performs only slightly better, cumulative feedback-based ARQ does not provide significant throughput while it has better average delay, and Coded ARQ can provide gains up to about 40% in terms of throughput. Coded ARQ also provides delay guarantees, and is robust to various challenges such as imperfect and delayed feedback, burst erasures, and round-trip time fluctuations. This feature may be preferable for meeting the strict end-to-end latency and reliability requirements of future use cases of ultra-reliable low-latency communications in 5G, such as mission-critical communications and industrial control for critical control messaging., Comment: to appear in IEEE JSAC Special Issue on URLLC in Wireless Networks
- Published
- 2018
22. Analysis of Coded Selective-Repeat ARQ via Matrix Signal-Flow Graphs
- Author
-
Malak, Derya, Médard, Muriel, and Yeh, Edmund M.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We propose two schemes for selective-repeat ARQ protocols over packet erasure channels with unreliable feedback: (i) a hybrid ARQ protocol with soft combining at the receiver, and (ii) a coded ARQ protocol, by building on the uncoded baseline scheme for ARQ, developed by Ausavapattanakun and Nosratinia. Our method leverages discrete-time queuing and coding theory to analyze the performance of the proposed data transmission methods. We incorporate forward error-correction to reduce in-order delivery delay, and exploit a matrix signal-flow graph approach to analyze the throughput and delay of the protocols. We demonstrate and contrast the performance of the coded protocols with that of the uncoded scheme, illustrating the benefits of coded transmissions.
- Published
- 2018
23. Throughput Maximization for Delay-Sensitive Random Access Communication
- Author
-
Malak, Derya, Huang, Howard, and Andrews, Jeffrey G.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
Future 5G cellular networks supporting ultra-reliable, low-latency communications (URLLC) could employ random access communication to reduce the overhead compared to scheduled access techniques used in 4G networks. We consider a wireless communication system where multiple devices transmit payloads of a given fixed size in a random access fashion over shared radio resources to a common receiver. We allow retransmissions and assume Chase combining at the receiver. The radio resources are partitioned in the time and frequency dimensions, and we determine the optimal partition granularity to maximize throughput, subject to given constraints on latency and outage. In the regime of high and low signal-to-noise ratio (SNR), we derive explicit expressions for the granularity and throughput, first using a Shannon capacity approximation and then using finite block length analysis. Numerical results show that the throughput scaling results are applicable over a range of SNRs. The proposed analytical framework can provide insights for resource allocation strategies in general random access systems and in specific 5G use cases for massive URLLC uplink access.
- Published
- 2017
24. A Distributed Auction Policy for User Association in Device-to-Device Caching Networks
- Author
-
Malak, Derya, Al-Shalash, Mazin, and Andrews, Jeffrey G.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We propose a distributed bidding-aided Matern carrier sense multiple access (CSMA) policy for device-to-device (D2D) content distribution. The network is composed of D2D receivers and potential D2D transmitters, i.e., transmitters are turned on or off by the scheduling algorithm. Each D2D receiver determines the value of its request, by bidding on the set of potential transmitters in its communication range. Given a medium access probability, a fraction of the potential transmitters are jointly scheduled, i.e., turned on, determined jointly by the auction policy and the power control scheme. The bidding-aided scheduling algorithm exploits (i) the local demand distribution, (ii) spatial distribution of D2D node locations, and (iii) the cache configurations of the potential transmitters. We contrast the performance of the bidding-aided CSMA policy with other well-known CSMA schemes that do not take into account (i)-(iii), demonstrate that our algorithm achieves a higher spectral efficiency in terms of the number of bits transmitted per unit time per unit bandwidth per user. The gain becomes even more visible under randomized configurations and requests rather than more skewed placement configurations and deterministic demand distributions., Comment: Proc. IEEE PIMRC 2017
- Published
- 2017
25. The Interplay of Spectral Efficiency, User Density, and Energy in Grant-based Access Protocols
- Author
-
Malak, Derya, primary
- Published
- 2024
- Full Text
- View/download PDF
26. Spatially Correlated Content Caching for Device-to-Device Communications
- Author
-
Malak, Derya, Al-Shalash, Mazin, and Andrews, Jeffrey G.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We study optimal geographic content placement for device-to-device (D2D) networks in which each file's popularity follows the Zipf distribution. The locations of the D2D users (caches) are modeled by a Poisson point process (PPP) and have limited communication range and finite storage. Inspired by the Mat\'{e}rn hard-core (type II) point process that captures pairwise interactions between nodes, we devise a novel spatially correlated caching strategy called {\em hard-core placement} (HCP) such that the D2D nodes caching the same file are never closer to each other than the {\em exclusion radius}. The exclusion radius plays the role of a substitute for caching probability. We derive and optimize the exclusion radii to maximize the {\em hit probability}, which is the probability that a given D2D node can find a desired file at another node's cache within its communication range. Contrasting it with independent content placement, which is used in most prior work, our HCP strategy often yields a significantly higher cache hit probability. We further demonstrate that the HCP strategy is effective for small cache sizes and a small communication radius, which are likely conditions for D2D., Comment: a shorter version appeared in Proc. IEEE Intl. Symposium on Info. Theory, Barcelona, Spain, [arXiv:1608.07856]
- Published
- 2016
27. Optimizing The Spatial Content Caching Distribution for Device-to-Device Communications
- Author
-
Malak, Derya, Al-Shalash, Mazin, and Andrews, Jeffrey G.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
We study the optimal geographic content placement problem for device-to-device (D2D) networks in which the content popularity follows the Zipf law. We consider a D2D caching model where the locations of the D2D users (caches) are modeled by a Poisson point process (PPP) and have limited communication range and finite storage. Unlike most related work which assumes independent placement of content, and does not capture the locations of the users, we model the spatial properties of the network including spatial correlation in terms of the cached content. We propose two novel spatial correlation models, the exchangeable content model and a Mat\'{e}rn (MHC) content placement model, and analyze and optimize the \emph{hit probability}, which is the probability of a given D2D node finding a desired file at another node within its communication range. We contrast these results to the independent placement model, and show that exchangeable placement performs worse. On the other hand, MHC placement yields a higher cache hit probability than independent placement for small cache sizes., Comment: appeared in Proc. IEEE Intl. Symposium on Info. Theory, Barcelona, Spain, July 2016
- Published
- 2016
- Full Text
- View/download PDF
28. Optimizing Content Caching to Maximize the Density of Successful Receptions in Device-to-Device Networking
- Author
-
Malak, Derya, Al-Shalash, Mazin, and Andrews, Jeffrey G.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
Device-to-device (D2D) communication is a promising approach to optimize the utilization of air interface resources in 5G networks, since it allows decentralized opportunistic short-range communication. For D2D to be useful, mobile nodes must possess content that other mobiles want. Thus, intelligent caching techniques are essential for D2D. In this paper we use results from stochastic geometry to derive the probability of successful content delivery in the presence of interference and noise. We employ a general transmission strategy where multiple files are cached at the users and different files can be transmitted simultaneously throughout the network. We then formulate an optimization problem, and find the caching distribution that maximizes the density of successful receptions (DSR) under a simple transmission strategy where a single file is transmitted at a time throughout the network. We model file requests by a Zipf distribution with exponent $\gamma_r$, which results in an optimal caching distribution that is also a Zipf distribution with exponent $\gamma_c$, which is related to $\gamma_r$ through a simple expression involving the path loss exponent. We solve the optimal content placement problem for more general demand profiles under Rayleigh, Ricean and Nakagami small-scale fading distributions. Our results suggest that it is required to flatten the request distribution to optimize the caching performance. We also develop strategies to optimize content caching for the more general case with multiple files, and bound the DSR for that scenario., Comment: published in IEEE Transactions on Communications, 2016
- Published
- 2016
- Full Text
- View/download PDF
29. Optimizing Data Aggregation for Uplink Machine-to-Machine Communication Networks
- Author
-
Malak, Derya, Dhillon, Harpreet S., and Andrews, Jeffrey G.
- Subjects
Computer Science - Information Theory ,Computer Science - Networking and Internet Architecture - Abstract
Machine-to-machine (M2M) communication's severe power limitations challenge the interconnectivity, access management, and reliable communication of data. In densely deployed M2M networks, controlling and aggregating the generated data is critical. We propose an energy efficient data aggregation scheme for a hierarchical M2M network. We develop a coverage probability-based optimal data aggregation scheme for M2M devices to minimize the average total energy expenditure per unit area per unit time or simply the {\em energy density} of an M2M communication network. Our analysis exposes the key tradeoffs between the energy density of the M2M network and the coverage characteristics for successive and parallel transmission schemes that can be either half-duplex or full-duplex. Comparing the rate and energy performances of the transmission models, we observe that successive mode and half-duplex parallel mode have better coverage characteristics compared to full-duplex parallel scheme. Simulation results show that the uplink coverage characteristics dominate the trend of the energy consumption for both successive and parallel schemes., Comment: 33 pages, 10 figures
- Published
- 2015
30. An Achievable Low Complexity Encoding Scheme for Coloring Cyclic Graphs
- Author
-
Deylam Salehi, Mohammad Reza, primary and Malak, Derya, additional
- Published
- 2023
- Full Text
- View/download PDF
31. Distributed Computing of Functions of Structured Sources with Helper Side Information
- Author
-
Malak, Derya, primary
- Published
- 2023
- Full Text
- View/download PDF
32. Joint Optimization of Storage and Transmission via Coding Traffic Flows for Content Distribution
- Author
-
Malak, Derya, primary, Li, Yuanyuan, additional, Ioannidis, Stratis, additional, Yeh, Edmund M., additional, and Médard, Muriel, additional
- Published
- 2023
- Full Text
- View/download PDF
33. Weighted Graph Coloring for Quantized Computing
- Author
-
Malak, Derya, primary
- Published
- 2023
- Full Text
- View/download PDF
34. Joint Power Control and Caching for Transmission Delay Minimization in Wireless HetNets
- Author
-
Malak, Derya, Mutlu, Faruk Volkan, Zhang, Jinkun, and Yeh, Edmund M.
- Abstract
A fundamental challenge in wireless heterogeneous networks (HetNets) is to effectively utilize the limited transmission and storage resources in the presence of increasing deployment density and backhaul capacity constraints. To alleviate bottlenecks and reduce resource consumption, we design optimal caching and power control algorithms for multi-hop wireless HetNets. We formulate a joint optimization framework to minimize the average transmission delay as a function of the caching variables and the signal-to-interference-plus-noise ratios (SINR) which are determined by the transmission powers, while explicitly accounting for backhaul connection costs and the power constraints. Using convex relaxation and rounding, we obtain a reduced-complexity formulation (RCF) of the joint optimization problem, which can provide a constant factor approximation to the globally optimal solution. We then solve RCF in two ways: 1) alternating optimization of the power and caching variables by leveraging biconvexity, and 2) joint optimization of power control and caching. We characterize the necessary (KKT) conditions for an optimal solution to RCF, and use quasi-convexity to show that the KKT points are Pareto optimal for RCF. We then devise a subgradient projection algorithm to jointly update the caching and power variables under general SINR conditions. Finally, our analytical findings are supported by results from extensive numerical experiments.
- Published
- 2024
- Full Text
- View/download PDF
35. Spatially Correlated Placement Policies for Wireless Content Caching Networks
- Author
-
Chen, Shukai, Malak, Derya, Abouzeid, Alhussein, Rensselaer Polytechnic Institute (RPI), Eurecom [Sophia Antipolis], IEEE, and European Project: 101077361,SENSIBILITE
- Subjects
ICC ,Poisson network ,[INFO]Computer Science [cs] ,Edge caching ,hit probability ,optimization ,Edge caching Poisson network content popularity hit probability optimization ,content popularity - Abstract
International audience; We propose a geographic content placement policy for wireless caching networks. This policy, named Joint Caching Policy (JCP), jointly determines the caching strategy across the set of base stations (BSs) to improve the hit probability of an arbitrarily located user in the network versus caching policies where placement is independent and identically distributed across the BSs. To that end, JCP divides the BSs into groups, and executes a joint caching policy for each group, while content placement is independent across the groups. Existing joint caching policies require knowledge of user location to optimize content placement. On the other hand, JCP does not require any information on user location, and it provides a content placement policy that outperforms the one given by Independent Caching Policy (ICP), proposed by Błaszczyszyn and Giovanidis in 2015, under any user location distribution. We prove that the hit probability under JCP is lower bounded by that of ICP. We further propose an extension of JCP, named JCP-OPT, which improves the hit probability over JCP by solving a concave maximization problem, provided that there is side information about the user locations. We validate the performance of JCP and JCP-OPT via numerical evaluations and demonstrate that they can provide up to a 30% gain in hit probability over ICP.
- Published
- 2023
36. A Distributed Computationally Aware Quantizer Design via Hyper Binning
- Author
-
Malak, Derya, primary and Medard, Muriel, additional
- Published
- 2023
- Full Text
- View/download PDF
37. Joint Power Control and Caching for Transmission Delay Minimization in Wireless HetNets
- Author
-
Malak, Derya, primary, Mutlu, Faruk Volkan, additional, Zhang, Jinkun, additional, and Yeh, Edmund M., additional
- Published
- 2023
- Full Text
- View/download PDF
38. Fractional Graph Coloring for Functional Compression with Side Information
- Author
-
Malak, Derya, primary
- Published
- 2022
- Full Text
- View/download PDF
39. Throughput and Energy Tradeoffs for Retransmission-based Random Access Protocols
- Author
-
Malak, Derya, primary
- Published
- 2022
- Full Text
- View/download PDF
40. The Interplay of Spectral Efficiency, User Density, and Energy in Random Access Protocols with Retransmissions
- Author
-
Malak, Derya
- Subjects
FOS: Computer and information sciences ,Computer Science - Information Theory ,Information Theory (cs.IT) - Abstract
The fifth-generation of wireless communication networks is required to support a range of use cases such as enhanced mobile broadband (eMBB), ultra-reliable, low-latency communications (URLLC), massive machine-type communications (mMTCs), with heterogeneous data rate, delay, and power requirements. The 4G LTE air interface uses extra overhead to enable scheduled access, which is not justified for small payload sizes. We employ a random access communication model with retransmissions for multiple users with small payloads at the low spectral efficiency regime. The radio resources are split non-orthogonally in the time and frequency dimensions. Retransmissions are combined via Hybrid Automatic Repeat reQuest (HARQ) methods, namely Chase Combining and Incremental Redundancy with a finite buffer size constraint $C_{\sf buf}$. We determine the best scaling for the spectral efficiency (SE) versus signal-to-noise ratio (SNR) per bit and for the user density versus SNR per bit, for the sum-optimal regime and when the interference is treated as noise, using a Shannon capacity approximation. Numerical results show that the scaling results are applicable over a range of $\eta$, $T$, $C_{\sf buf}$, $J$, at low received SNR values. The proposed analytical framework provides insights for resource allocation in general random access systems and specific 5G use cases for massive URLLC uplink access., Comment: A short version will appear in WiOpt'22
- Published
- 2022
- Full Text
- View/download PDF
41. FlEC: Enhancing QUIC With Application-Tailored Reliability Mechanisms
- Author
-
Michel, Francois, primary, Cohen, Alejandro, additional, Malak, Derya, additional, Coninck, Quentin De, additional, Medard, Muriel, additional, and Bonaventure, Olivier, additional
- Published
- 2022
- Full Text
- View/download PDF
42. JSAIT Editorial for the Special Issue on “Beyond Errors and Erasures: Coding for Data Management and Delivery in Networks”
- Author
-
Erkip, Elza, primary, Gunduz, Deniz, additional, Ioannidis, Stratis, additional, Kliewer, Joerg, additional, Malak, Derya, additional, Medard, Muriel, additional, and Srikant, R., additional
- Published
- 2021
- Full Text
- View/download PDF
43. Opportunistic Overlapping: Joint scheduling of uplink URLLC/eMBB traffic in NOMA based Wireless Systems
- Author
-
Anand, Arjun, primary, de Veciana, Gustavo, additional, Malak, Derya, additional, Elezabi, Ayman, additional, and Venkatakrishnan, Aniruddh, additional
- Published
- 2021
- Full Text
- View/download PDF
44. Transmission Delay Minimization via Joint Power Control and Caching in Wireless HetNets
- Author
-
Malak, Derya, primary, Mutlu, Faruk V., additional, Zhang, Jinkun, additional, and Yeh, Edmund M., additional
- Published
- 2021
- Full Text
- View/download PDF
45. Function Load Balancing Over Networks
- Author
-
Malak, Derya, primary and Medard, Muriel, additional
- Published
- 2021
- Full Text
- View/download PDF
46. FlEC: Enhancing QUIC With Application-Tailored Reliability Mechanisms
- Author
-
Michel, Francois, Cohen, Alejandro, Malak, Derya, De Coninck, Quentin, Medard, Muriel, and Bonaventure, Olivier
- Abstract
Packet losses are common events in today’s networks. They usually result in longer delivery times for application data since retransmissions are the de facto technique to recover from such losses. Retransmissions is a good strategy for many applications but it may lead to poor performance with latency-sensitive applications compared to network coding. Although different types of network coding techniques have been proposed to reduce the impact of losses by transmitting redundant information, they are not widely used. Some niche applications include their own variant of Forward Erasure Correction (FEC) techniques, but there is no generic protocol that enables many applications to easily use them. We close this gap by designing, implementing and evaluating a new Flexible Erasure Correction (FlEC) framework inside the newly standardized QUIC protocol. With FlEC, an application can easily select the reliability mechanism that meets its requirements, from pure retransmissions to various forms of FEC. We consider three different use cases:
$(i)$ $(ii)$ $(iii)$ - Published
- 2023
- Full Text
- View/download PDF
47. Spatial Concentration of Caching in Wireless Heterogeneous Networks
- Author
-
Malak, Derya, primary, Medard, Muriel, additional, and Andrews, Jeffrey G., additional
- Published
- 2021
- Full Text
- View/download PDF
48. Adaptive Causal Network Coding With Feedback
- Author
-
Cohen, Alejandro, primary, Malak, Derya, additional, Bracha, Vered Bar, additional, and Medard, Muriel, additional
- Published
- 2020
- Full Text
- View/download PDF
49. How to Distribute Computation in Networks
- Author
-
Malak, Derya, primary, Cohen, Alejandro, additional, and Medard, Muriel, additional
- Published
- 2020
- Full Text
- View/download PDF
50. Discrete Water Filling Multi-Path Packet Scheduling
- Author
-
Schneuwly, Arno, primary, Malak, Derya, additional, and Medard, Muriel, additional
- Published
- 2020
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.