Rajiv Agarwal's Home Page

Towards minimizing read time for NAND Flash
Borja Peleato, Rajiv Agarwal, John Cioffi, Minghai Qin, Paul Siegel
IEEE Globecom 2012
( Abstract | Full Text | Talk )

On NAND Flash, a primary source of increased read time comes from the fact that in the presence of noise, the Flash medium must be read several times using different read threshold voltages to find the optimal read location, which minimizes bit-error-rate. This paper proposes an algorithm to estimate the optimal read threshold in a fast manner using a limited number of re-reads. Then it derives an expression for the resulting BER in terms of the minimum BER. It is also shown that minimizing BER and minimizing codeword-error-rate are competing objectives in the presence of limited number of allowed re-reads, and a trade-off between the two is proposed.
Analysis of Trade-offs in V2P-Table Design for NAND Flash
Borja Peleato, Rajiv Agarwal, John Cioffi
46th Asilomar Conference on Signals, Systems and Computers, Nov. 2012
( Abstract | Full Text )

Flash memory uses relocate-on-write, also called out-of-place write for performance reasons. Data files from the host are spread across several non-sequential NAND physical pages. In order to retrieve host data at a later point a virtual-to-physical address table mapping the files to their physical addresses must be maintained. This process entails two basic steps. The first is to divide the NAND physical space in a hierarchical manner for efficiency of address lookup. The second is to store the resulting address lookup table, also called a virtual-to-physical (V2P) table in an efficient manner on the flash. This paper explores different architectures for constructing such table and storing it, thereby characterizing the trade-off that they offer in terms of complexity, write speed, and endurance of the flash memory.
On the Distribution of Valid Pages with Greedy Garbage Collection for NAND Flash
Borja Peleato, Rajiv Agarwal, John Cioffi.
IEEE SSP 2012
( Abstract | Full Text | Poster )

Flash memory uses relocate-on-write, also called out-of-place write for performance reasons. Relocate-on-write requires a garbage-collection process, which results in additional write operations referred to as write-amplification. The reclaiming policy that selects the blocks to garbage-collect is greedy if it is based only on the amount of free space to be gained. Write amplification is a critical factor limiting the write performance and endurance in solid-state drives and the greedy garbage collection policy minimizes it. In this paper, we derive an expression for the steady-state distribution of validpages using a novel probabilistic model for flash-based SSDs for a greedy reclaiming policy. This distribution lends itself directly to evaluation of write-amplification and gives insight into designing newer garbage collection policies, which would further reduce write-amplification. Numerical evaluation of the derived expression matches the distribution obtained via Monte-Carlo simulation for several different drive configurations, thereby validating the derivation.
Probabilistic Graphical Model for the Programming of a Flash Memory
Borja Peleato, Rajiv Agarwal, John Cioffi
IEEE SSP 2012
( Abstract | Full Text | Poster )

Flash memory presents significant advantages over hard drives in terms of read speed and power efficiency; however its lifetime can be several orders of magnitude smaller. Thus increasing lifetime of flash memory via signal processing techniques is an important research area. The first half of the paper presents a statistical method for estimating the health of the cells in a Flash memory, based on which a variable error correction coding scheme can be used to increase lifetime. The second half of the paper proposes a statistical approach to increase lifetime when the flash controller can dynamically vary the program and erase operation strategy. This approach uses Markov Decision Processes (MDP) to choose the optimal program or erase strategy at any given point in the life of a Flash memory based on its current state or health. From a bigger picture stand-point, the paper presents a novel way of flash management using a Markov model for health of the memory at any given point in its lifetime.
Maximizing MLC Nand life-time and reliability in the presence of write noise
Borja Peleato, Rajiv Agarwal, John Cioffi
IEEE ICC 2012
( Abstract | Full Text )

The aggressive scaling of the NAND flash technology has led to write noise becoming the dominant source of disturbance in the currently shipping sub-30 nm MLC NAND memories. Write noise can be mitigated by reducing the magnitude of the voltage levels programmed into the cells, which additionally translates to longer flash memory lifetime. However, if all the target levels are small and close together, the probability of error could become excessively high. It is therefore necessary to optimize the target level placement in order to achieve a trade-off between flash lifetime and error probability. This paper proposes a method to maximize flash lifetime subject to reliability constraints, and vice versa. Simulation results show that the proposed method doubles flash lifetime in comparison to a naive scheme, for a 2% reliability constraint. It also comes very close to the optimal solution obtained by brute force search, while maintaining negligible computational complexity in comparison.
A closed-form expression for Write Amplification in NAND Flash
Rajiv Agarwal, Marcus Marrow
IEEE Globecom 2010
( Abstract | Full Text )

The log-structured filesystems typically used in current solid-state drive’s (SSD) exhibit write amplification, whereby multiple NAND writes are required for each host write. Write amplification negatively affects the SSD endurance and write throughput. This performance loss depends on the drive overprovisioning and the garbage collection method. This paper presents a novel probabilistic model to analytically quantify the impact of over-provisioning on write amplification under a uniformly-distributed random workload and a greedy garbage collection policy. The analysis shows write amplification approximately independent of NAND block size and number of blocks in the SSD. The analysis is verified by full drive simulations.
Optimal Resource Allocation in the OFDMA Downlink with Feedback of Buffer State Information
Rajiv Agarwal, Rath Vannithamby and John Cioffi
IEEE Globecom 2009
( Abstract | Full Text )

With the advent of new applications, one of the primary applications supported in downlink cellular systems is streaming video. QoS for streaming video entails data transmission to the mobile stations with limited latency and limited jitter. This requirement on latency and jitter can be mapped to the number of yet-to-be-played packets in a mobile station’s buffer, to always be above a certain minimum. Additionally, there should be no overflow of finite-size user buffers. This paper solves the problem of optimal resource allocation in a downlink OFDMA system with buffer constraints for all downlink users. The optimal strategy is shown to be a generalized version of water-filling and channel-inversion. Specifically, with infinite buffer size and no minimum constraint on buffer, it reduces to water-filling; and to channel-inversion in the absence of a buffer. It is shown that scheduling gains from the derived optimal strategy, in terms of number of users that the system can support, can be an orderof- magnitude higher than that of heuristic scheduling schemes.
Weighted Sum-Rate Maximization using Weighted MMSE for MIMO-BC Beamforming Design
S. S. Christensen, Rajiv Agarwal, Elisabeth de Carvalho, John Cioffi
IEEE ICC 2009
( Abstract | Full Text )

This paper studies linear transmit filter design for Weighted Sum-Rate (WSR) maximization in the Multiple Input Multiple Output Broadcast Channel (MIMO-BC). The problem of finding the optimal transmit filter is non-convex and intractable to solve using low complexity methods. Motivated by recent results highlighting the relationship between mutual information and Minimum Mean Square Error (MMSE), this paper establishes a relationship between weighted sum-rate and weighted MMSE in the MIMO-BC. The relationship is used to propose a low complexity algorithm for finding a local weighted sum-rate optimum based on alternating optimization. Numerical results studying sum-rate show that the proposed algorithm achieves high performance with few iterations.
User Profiling: A Method to Guarantee QoS in Limited Feedback OFDMA Systems
Rajiv Agarwal, V. Majjigi, Zhu Han, R. Vannithamby, John Cioffi
IEEE ICC 2009
( Abstract | Full Text )

In the OFDMA downlink, obtaining Channel State Information (CSI) from users is necessary for the Base Station (BS) to optimize network performance by intelligently allocating resources and scheduling mobile stations (MS). However, the overhead of obtaining CSI is a large burden and therefore, schemes to reduce CSI are necessary for a realizable system. By considering a MS’s coherence time Δt_coh and coherence bandwidth B_coh, and exploiting this redundancy in the MS’s CSI, the amount of feedback can be tailored to the specific user’s profile and greatly decreased. Typically, reducing feedback results in more uncertainty in CSIT and performance degradation. However, in the proposed scheme, the CSIT’s deviation from the true channel state is bounded, and thus can provide robust scheduling. Specifically, two BS schemes are suggested that either fix the average BER or the average outage probability regardless of user mobility or delay spread.
Beamforming Design for the MIMO Downlink for maximizing Weighted Sum-Rate
Rajiv Agarwal, John Cioffi
IEEE ISITA 2008
( Abstract | Full Text )

This work studies linear transmit filter design for Weighted Sum-Rate (WSR) maximization in the Multiple Input Multiple Output Broadcast Channel (MIMOBC). The problem of finding the optimal transmit filter is non-convex and intractable to solve. Motivated by the iterative algorithm that solves for the optimal transmit and receive filters for minimizing sum- Mean Square Error (MSE), this paper suggests to use Weighted Minimum Mean Square Error (WMMSE) optimization in the MIMO-BC. The paper presents an iterative algorithm to maximize WSR. Numerical results for sum-rate using the derived filter are provided under different system settings.
Optimal Allocation of Feedback Bits for Downlink OFDMA Systems
Rajiv Agarwal, Rath Vannithamby, John Cioffi
IEEE ISIT 2008
( Abstract | Full Text )

This paper studies the downlink Orthogonal Frequency Division Multiplexing (OFDM) setup with a single Base Station (BS) serving many users. The BS is assumed to have limited Channel State Information (CSI) obtained by feedback in a Time Division Duplexing (TDD) manner. Given that the feedback rate and the coherence time of the channel are fixed, the question asked in this paper is: how to allocate the feedback resources optimally? Specifically, what is the optimal number of tones grouped as a subchannel, the number of users that feedback for any subchannel and the number of bits used for quantization of CSI? Analytical expressions are derived for the i.i.d. Rayleigh fading case and it is shown that there is a definite hierarchy in the importance of the three design variables. Feedback resources are first allocated to create the maximum number of subchannels possible, then to allow for more users to feedback for any subchannel and lastly to increase the precision of the channel value. Monte-Carlo simulations are performed to verify the accuracy of the derived analytical expressions.
Optimal Throughput-Delay Tradeoff in Mammalian Ad Hoc Networks
Rajiv Agarwal, John Cioffi
41st Asilomar Conference on Signals, Systems and Computers, Nov. 2007
( Extended Abstract )
Persistent Resource Allocation in OFDMA Networks for Real-Time and Non-Real Time Traffic
Vinay Majjigi, Rajiv Agarwal, Rath Vannithamby, John Cioffi
41st Asilomar Conference on Signals, Systems and Computers, Nov. 2007
( Abstract | Full Text )

We consider optimal allocation of resources to users in a downlink OFDMA system to support heterogeneous applications consisting of both deadline-sensitive (DS) and besteffort (BE) users. Given the user rate-requirements and longterm statistics, the proposed persistent scheduling algorithm allocates the minimum resources to ‘just’ meet the deadlines for DS packets. The remaining resources are optimally split to maximize a rate objective for BE users. We resort to a greedy tone allocation algorithm to solve the optimization problem. By considering persistent scheduling instead of instantaneous scheduling, the proposed scheme’s complexity and required feedback overhead is significantly reduced, hence a practical algorithm for a real-system.
Efficient Scheduling for Heterogeneous Services in OFDMA Downlink
Rajiv Agarwal, Vinay Majjigi, Rath Vannithamby, John Cioffi
IEEE Globecom 2007
( Abstract | Full Text )

We consider optimal allocation of resources to users in a downlink OFDMA system to support heterogeneous applications consisting of both deadline-sensitive (DS) and best-effort (BE) data in a cross-layer manner. Given the user queue-states and long-term channel statistics, the proposed persistent scheduling algorithm allocates the minimum resources to ‘just’ meet the deadlines for DS packets (QoS guarantee). The remaining resources are optimally split between the users for their BE data to maximize sum-rate, minimize buffer holding cost or any general utility function. We formulate the resource allocation problem as a single geometric program (GP) that can be solved using standard convex optimization software tools. Simulation results are presented to compare the performance of different objectives for the BE applications in presence of DS traffic.
Opportunistic Feedback in OFDMA Downlink
Rajiv Agarwal, Vineet Abhishek, Rath Vannithamby, John Cioffi
IEEE Globecom 2007
( Abstract | Full Text )

This paper presents an opportunistic feedback (OF) protocol that reduces the amount of channel-state-information (CSI) feedback for the OFDMA downlink system. The OF protocol associates a channel value instead of a user to each feedback slot. The users access the slots opportunistically based on their channel state measurement for each tone. This allows the base station (BS) to deduce the channel state from the slot index without explicit channel-state feedback, and also solve the resource allocation problem on the fly. The OF protocol is designed to support heterogeneous traffic, where users with deadline-sensitive (DS) applications are prioritized over best-effort (BE) users. The proposed OF protocol (a) requires finite number of feedback slots upper bounded by a small number, (b) is fully distributed, and (c) provides QoS to the DS applications.
Opportunistic Feedback Protocol for Achieving Sum-Capacity of the MIMO Broadcast Channel
Rajiv Agarwal, Chan-Soo Hwang, John Cioffi
IEEE VTC Fall 2007
( Abstract | Full Text )

This paper presents an opportunistic feedback (OF) protocol that achieves the asymptotic sum-capacity of the fading broadcast channel (BC) with a limited amount of feedback. The OF protocol associates a channel value instead of a user to each feedback slot. The users access the slots opportunistically based on their channel state measurement. This allows the base-station to deduce the channel state from the slot index without explicit channel-state feedback. This protocol is then extended to the MIMO BC by using zero-forcing beamforming and random beamforming. The OF protocol is analytically shown to (a) require finite number of feedback slots upper bounded by a small number, (b) be fully distributed, (c) need minimal transmission energy during feedback and (d) asymptotically achieve the sum-capacity of the MIMO BC. Comparison with other opportunistic feedback schemes shows that the proposed scheme has substantially larger sum-rate with a lower feedback overhead.
Efficient Scheduling for Heterogeneous Traffic in Downlink
Rajiv Agarwal, Vinay Majjigi, Rath Vannithamby, John Cioffi
IEEE VTC Fall 2007
( Abstract | Full Text )

This paper studies optimal allocation of resources to users in a fading broadcast channel (BC) to support heterogeneous traffic. Resource allocation is done in a cross-layer manner for both deadline-sensitive (DS) and best-effort (BE) data to provide users guaranteed Quality of Service (QoS). Given the user queue-states, the proposed algorithm allocates the minimum resource to `just' meet the deadlines for DS packets a fixed % of time. The remaining resources are then optimally split between the users for their BE data to maximize sum-rate, minimize buffer holding cost or any general utility function. The resource allocation problem is formulated as a linear program (LP) followed by a geometric program (GP) which can be solved very efficiently. Simulation results are presented for Poisson packet arrivals and exponentially distributed packet lengths on a Rayleigh fading channel for both the DS and BE traffic.
Opportunistic Feedback Protocol for Minimizing Power in Uplink with Heterogeneous Traffic
Rajiv Agarwal, Vineet Abhishek, Rath Vannithamby, John Cioffi
IEEE VTC Fall 2007
( Abstract | Full Text )

This paper considers a wireless uplink, where some users have deadline-sensitive (DS) traffic and others have besteffort (BE) traffic. The objective is to meet the deadlines for DS packets a fixed percent of time (QoS guarantee), at the same time minimizing the sum-power used for transmission in a distributed manner without feedback from all users to the base station (BS). Given each user’s channel state and rate requirement, the optimal user ordering that minimizes sum-power is shown to be independent of the rate requirements and depends solely on the channel conditions. Based on this, using a limited amount of feedback, the proposed opportunistic feedback (OF) protocol guarantees QoS to DS data and minimizes sum-power. Numerical results show that (i) the OF protocol provides deadline-meeting guarantees and (ii) minimizes sum-power with a greatly reduced feedback overhead as compared to that of a central scheduler.
Achieving Sum-Capacity of the MIMO BC with Large Transmit Array using One-Shot Scalable Feedback Protocol
Rajiv Agarwal, John Cioffi
IEEE VTC Spring 2007
( Abstract | Full Text )

We consider a MIMO broadcast channel (BC) with large M and K, where M is the number of transmit antennas and K is the number of single-antenna users; and propose a scalable feedback protocol that achieves the sum-capacity with limited feedback of channel state information (CSI). In our earlier work, we showed that if feedback time slots correspond to channel gains and not to users, the sum-capacity M log log K can be achieved with feedback resources growing only as M log K, unlike linearly as MK for conventional schemes. In this work, we show that feedback requirement can further be reduced by half or more, while still achieving the sum-capacity. A scalable feedback (SF) protocol using Random Beamforming (RBF) is proposed, which a) requires finite number of feedback slots upper bounded by a constant, b) is fully distributed, c) needs finite transmission energy during feedback and d) achieves the sum-capacity. Numerical results show that feedback load is substantially reduced as compared to conventional schemes, as well as our own previously proposed SF scheme.
Capacity of Fading Broadcast Channels with One-Sided Feedback
Rajiv Agarwal, John Cioffi
40th Asilomar Conference on Signals, Systems and Computers, Nov. 2006
( Abstract | Full Text )

In this paper we study a 2-user fast fading broadcast channel, in which instanta- neous channel state information at the transmitter (CSIT) is available for only one of the users. We derive the achievable rate region using well-known broadcast trans- mission strategies - 1) dirty paper coding (DPC), 2) super-position coding (SPC) and 3) time-division multiplexing (TDM). For all three transmission strategies, we ¯nd closed-form expressions for the boundary of the achievable region. It is shown analytically that the achievable region with SPC contains that with DPC which in turn contains the TDM region in general. We also give su±cient conditions on the fading distribution under which the proposed achievable region with super-position coding is the capacity region. Numerical results are provided for a Rayleigh fading channel, where we compare the proposed achievable rate regions with the upper bound - `capacity region with perfect CSIT', inner bound `achievable rate region with no CSIT' and a recently proposed capacity region with transmitter ordering information.
Capacity of Fading Broadcast Channels with Limited Rate Feedback
Rajiv Agarwal, John Cioffi
Allerton 2006
( Abstract | Full Text )

In this paper, we study a fading broadcast channel (BC) with perfect channel state information at the receiver (CSIR) and only a quantized version of it at the transmitter due to limited-rate links for channel feedback at each user. We find an achievable region for the fading BC under this condition using super-position coding and show that it is sumrate optimal.We also derive a closed-form expression for finding channel partitioning, which turns out to be the same in form as that for water-filling of power over time in fading channels. Using the derived closed form expression with temporal waterfilling of power at the transmitter in an iterative manner, we show numerically that a single iteration is adequate to achieve most of the capacity. Thus the complexity of finding the optimal (global maximum) or close to optimal (local maximum) channel partitioning is greatly reduced as compared to using a searchbased k-mean clustering algorithm like Lloyd’s algorithm that requires multiple iterations.
Capacity of Fading Broadcast Channels with Transmitter Ordering CSI
Rajiv Agarwal, Yifan Liang, Andrea Goldsmith
Allerton 2005
( Abstract | Full Text )

We derive the ergodic capacity region for a fading broadcast channel when the transmitter knows only the channel ordering information of the users and the receiver knows its transmitter-receiver channel gain and the ordering information at any time instant. We show that superposition coding based on the ordering information achieves the ergodic capacity region. Moreover, we prove that as the number of users goes to infinity, the capacity region with just transmitter ordering information is the same as the capacity region with perfect channel knowledge at the transmitter. Numerical results are provided for a Rayleigh fading channel.
Joint Rate Allocation and Routing for Multihop Wireless Networks with Delay-Constrained Data
Rajiv Agarwal, Sanjay K. Bose
WNCG Symposium 2004
( Abstract | Full Text )

We develop a framework for optimal rate allocation and routing in multihop wireless networks. Each node in the network has delay-sensitive data to send to a unique destination and this data can be sent over a single (multihop) path through the network or via multiple paths. Sending over multiple paths can increase throughput and reduce congestion. Our goal is to optimize the rate sent over each possible source-destination path such that the average end-to-end delay per packet is minimized. We find that the optimal solution is a modified water-filling of rate relative to the number of hops in each path towards the destination, where each hop is weighted by its throughput.
Geolocation using Transmit and Receive Diversity
Pulkit Grover, Rajiv Agarwal, Ajit K. Chaturvedi
IEEE Globecom 2004
( Abstract | Full Text )

Geolocation using received signal strength (RSS) has large errors due to multipath fading, since fading results in high variations in RSS. We show how and when spatial diversity combined with channel knowledge at the receiver can be used to combat fading effects to increase accuracy in location estimate. We then propose a simple scheme for distance estimation, characterize the channels for which improvement in distance estimates can be thus obtained and prove that mean square error of distance estimate converges to zero with increasing diversity order. It is observed that the improvement can always be obtained for Rayleigh channel, and for Nakagami-m channel if the parameter m remains the same regardless of the distance.

Rajiv Agarwal

Collaborators

Publications

Contact