Ness B. Shroff
Research Subjects
Ness B. Shroff has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Xiaojun Lin
Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong, Hong Kong
4 shared publications - Bo Ji
Virginia Tech, Blacksburg, Virginia, USA
2 shared publications - Changhee Joo
Department of Computer Science and Engineering, Korea University, Seoul, South Korea
2 shared publications - Do Young Eun
Dept. of Electr. & Comput. Eng., North Carolina State Univ., Raleigh, NC, USA
2 shared publications Prasun Sinha
Department of CSE, Ohio State University
2 shared publications- Sonia Fahmy
Purdue University, West Lafayette, IN, USA
2 shared publications
Latest Publications
- 1 April 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1042-1050
When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds
Storage clouds, such as Amazon S3, are being widely used for web services and Internet applications. It has been observed that the delay for retrieving data from and placing data into the clouds is quite random, and exhibits weak correlations between different read/write requests. This inspires us to investigate a key problem: can we reduce the delay by transmitting data replications in parallel or using powerful erasure codes? In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is., each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Real traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be accurately approximated as an i.i.d. exponentially distributed random variable. We show that any work-conserving scheme is delay-optimal when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal, which appears surprising.
- 1 April 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1042-1050
When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds
Storage clouds, such as Amazon S3, are being widely used for web services and Internet applications. It has been observed that the delay for retrieving data from and placing data into the clouds is quite random, and exhibits weak correlations between different read/write requests. This inspires us to investigate a key problem: can we reduce the delay by transmitting data replications in parallel or using powerful erasure codes? In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is., each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Real traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be accurately approximated as an i.i.d. exponentially distributed random variable. We show that any work-conserving scheme is delay-optimal when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal, which appears surprising.
- 1 February 2014
- Published by Elsevier in Ad Hoc Networks
- Vol. 13, 107-109
Special issue on models and algorithms for wireless mesh networks
- 1 February 2014
- Published by Elsevier in Ad Hoc Networks
- Vol. 13, 107-109
Special issue on models and algorithms for wireless mesh networks
- 5 December 2013
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 22 (6) , 1911-1924
Low-Complexity Scheduling Policies for Achieving Throughput and Asymptotic Delay Optimality in Multichannel Wireless Networks
In this paper, we study the scheduling problem for downlink transmission in a multichannel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general nonasymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of O(n 2.5 log n), where n is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of O(n 5 ). Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput-optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results.
- 5 December 2013
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 22 (6) , 1911-1924
Low-Complexity Scheduling Policies for Achieving Throughput and Asymptotic Delay Optimality in Multichannel Wireless Networks
In this paper, we study the scheduling problem for downlink transmission in a multichannel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general nonasymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of O(n 2.5 log n), where n is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of O(n 5 ). Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput-optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results.
- 11 July 2012
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 21 (2) , 634-647
Throughput-Optimal Scheduling in Multihop Wireless Networks Without Per-Flow Information
In this paper, we consider the problem of link scheduling in multihop wireless networks under general interference constraints. Our goal is to design scheduling schemes that do not use per-flow or per-destination information, maintain a single data queue for each link, and exploit only local information, while guaranteeing throughput optimality. Although the celebrated back-pressure algorithm maximizes throughput, it requires per-flow or per-destination information. It is usually difficult to obtain and maintain this type of information, especially in large networks, where there are numerous flows. Also, the back-pressure algorithm maintains a complex data structure at each node, keeps exchanging queue-length information among neighboring nodes, and commonly results in poor delay performance. In this paper, we propose scheduling schemes that can circumvent these drawbacks and guarantee throughput optimality. These schemes use either the readily available hop-count information or only the local information for each link. We rigorously analyze the performance of the proposed schemes using fluid limit techniques via an inductive argument and show that they are throughput-optimal. We also conduct simulations to validate our theoretical results in various settings and show that the proposed schemes can substantially improve the delay performance in most scenarios.
- 11 July 2012
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 21 (2) , 634-647
Throughput-Optimal Scheduling in Multihop Wireless Networks Without Per-Flow Information
In this paper, we consider the problem of link scheduling in multihop wireless networks under general interference constraints. Our goal is to design scheduling schemes that do not use per-flow or per-destination information, maintain a single data queue for each link, and exploit only local information, while guaranteeing throughput optimality. Although the celebrated back-pressure algorithm maximizes throughput, it requires per-flow or per-destination information. It is usually difficult to obtain and maintain this type of information, especially in large networks, where there are numerous flows. Also, the back-pressure algorithm maintains a complex data structure at each node, keeps exchanging queue-length information among neighboring nodes, and commonly results in poor delay performance. In this paper, we propose scheduling schemes that can circumvent these drawbacks and guarantee throughput optimality. These schemes use either the readily available hop-count information or only the local information for each link. We rigorously analyze the performance of the proposed schemes using fluid limit techniques via an inductive argument and show that they are throughput-optimal. We also conduct simulations to validate our theoretical results in various settings and show that the proposed schemes can substantially improve the delay performance in most scenarios.
- Open Access
- 1 January 2008
- Published by Defense Technical Information Center (DTIC)
On Maximizing the Lifetime of Delay-Sensitive Wireless Sensor Networks with Anycast
Sleep-wake scheduling is an effective mechanism to prolong the lifetime of energy-constrained wireless sensor networks. However, it incurs an additional delay for packet delivery when each node needs to wait for its next-hop relay node to wake up, which could be unacceptable for delay-sensitive applications. Prior work in the literature has proposed to reduce this delay using anycast, where each node opportunistically selects the first neighboring node that wakes up among multiple candidate nodes. In this paper, we study the joint control problem of how to optimally control the sleep-wake schedule, the anycast candidate set of next-hop neighbors, and anycast priorities, to maximize the network lifetime subject to a constraint on the expected end-to-end delay. We provide an efficient solution to this joint control problem. Our numerical results indicate that the proposed solution can substantially outperform prior heuristic solutions in the literature, especially under the practical scenarios where there are obstructions in the coverage area of the wireless sensor network.
- 1 January 2008
- Published by Defense Technical Information Center (DTIC)
Open AccessOn Maximizing the Lifetime of Delay-Sensitive Wireless Sensor Networks with Anycast
Sleep-wake scheduling is an effective mechanism to prolong the lifetime of energy-constrained wireless sensor networks. However, it incurs an additional delay for packet delivery when each node needs to wait for its next-hop relay node to wake up, which could be unacceptable for delay-sensitive applications. Prior work in the literature has proposed to reduce this delay using anycast, where each node opportunistically selects the first neighboring node that wakes up among multiple candidate nodes. In this paper, we study the joint control problem of how to optimally control the sleep-wake schedule, the anycast candidate set of next-hop neighbors, and anycast priorities, to maximize the network lifetime subject to a constraint on the expected end-to-end delay. We provide an efficient solution to this joint control problem. Our numerical results indicate that the proposed solution can substantially outperform prior heuristic solutions in the literature, especially under the practical scenarios where there are obstructions in the coverage area of the wireless sensor network.
- 1 June 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 52 (21578095) , 121-125
Beyond the Butterfly ¿ A Graph-Theoretic Characterization of the Feasibility of Network Coding with Two Simple Unicast Sessions
The problem of network coding with two simple unicast sessions is considered for general directed acyclic graphs. An explicit graph-theoretic characterization is provided for the feasibility of whether two symbols at different sources can be simultaneously transmitted to the designated sinks via network coding. The existence of a routing scheme is equivalent to finding edge-disjoint paths. Similarly, in this paper it is proven that the existence of a network coding scheme is equivalent to finding paths with controlled edge overlaps, and the characterization includes the well-studied butterfly graph as a special case. Various generalizations and implications are discussed based on the constructive nature of the flow-based conditions. For example, it is shown that a linear network coding scheme using only six paths is as effective as any non-linear network coding scheme.
- 1 June 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 52 (21578095) , 121-125
Beyond the Butterfly ¿ A Graph-Theoretic Characterization of the Feasibility of Network Coding with Two Simple Unicast Sessions
The problem of network coding with two simple unicast sessions is considered for general directed acyclic graphs. An explicit graph-theoretic characterization is provided for the feasibility of whether two symbols at different sources can be simultaneously transmitted to the designated sinks via network coding. The existence of a routing scheme is equivalent to finding edge-disjoint paths. Similarly, in this paper it is proven that the existence of a network coding scheme is equivalent to finding paths with controlled edge overlaps, and the characterization includes the well-studied butterfly graph as a special case. Various generalizations and implications are discussed based on the constructive nature of the flow-based conditions. For example, it is shown that a linear network coding scheme using only six paths is as effective as any non-linear network coding scheme.
- Open Access
- 1 May 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 37-42
A Black-box Router Profiler
Simulation, emulation, and wide-area testbeds exhibit different strengths and weaknesses with respect to fidelity, scalability, and manageability. Fidelity is a key concern since simulation or emulation inaccuracies can lead to a dramatic and qualitative impact on the results. For example, high-bandwidth denial of service attack floods of the same rates have very different impact on the different platforms, even if the experimental scenario is supposedly identical. This is because many popular simulation and emulation environments fail to account for realistic commercial router behaviors, and incorrect results have been reported based on experiments conducted in these environments. In this paper, we describe the architecture of a black-box router profiling tool which integrates the popular ns-2 simulator with the Click modular router and a modified network driver. We use this profiler to collect measurements on a Cisco router. Our preliminary results demonstrate that routers and other forwarding devices cannot be modeled as simple output port queues, even if correct rate limits are observed. We discuss our future work plans for using our data to create high-fidelity network simulation/emulation models that are not computationally prohibitive.
- 1 May 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 37-42
Open AccessA Black-box Router Profiler
Simulation, emulation, and wide-area testbeds exhibit different strengths and weaknesses with respect to fidelity, scalability, and manageability. Fidelity is a key concern since simulation or emulation inaccuracies can lead to a dramatic and qualitative impact on the results. For example, high-bandwidth denial of service attack floods of the same rates have very different impact on the different platforms, even if the experimental scenario is supposedly identical. This is because many popular simulation and emulation environments fail to account for realistic commercial router behaviors, and incorrect results have been reported based on experiments conducted in these environments. In this paper, we describe the architecture of a black-box router profiling tool which integrates the popular ns-2 simulator with the Click modular router and a modified network driver. We use this profiler to collect measurements on a Cisco router. Our preliminary results demonstrate that routers and other forwarding devices cannot be modeled as simple output port queues, even if correct rate limits are observed. We discuss our future work plans for using our data to create high-fidelity network simulation/emulation models that are not computationally prohibitive.
- 1 June 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2008 16th Interntional Workshop on Quality of Service
- p. 102-111
Optimal Sleep/Wake Scheduling for Time-Synchronized Sensor Networks with QoS Guarantees
We study sleep/wake scheduling for low-duty cycle sensor networks. Our work is different from previous work in that we explicitly consider the effect of the synchronization error. We study a widely used synchronization scheme and show that the synchronization error is non-negligible, and using a conservative guard time is energy wasteful. Hence, we formulate an optimization problem to minimize the expected energy consumption, with the constraint that the message capture probability should be no less than a threshold. We find that the problem is non-convex, hence cannot be solved by conventional convex optimization techniques. By investigating the unique structure of the problem, we transform the problem into a convex equivalent, and solve it using an efficient search method. Simulations show that our scheme significantly outperforms schemes that do not intelligently consider the synchronization error. We also remove the assumption that the capture probability threshold is given, and study how to decide it to meet the quality of services (QoS) requirements of the application
- 1 June 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2008 16th Interntional Workshop on Quality of Service
- p. 102-111
Optimal Sleep/Wake Scheduling for Time-Synchronized Sensor Networks with QoS Guarantees
We study sleep/wake scheduling for low-duty cycle sensor networks. Our work is different from previous work in that we explicitly consider the effect of the synchronization error. We study a widely used synchronization scheme and show that the synchronization error is non-negligible, and using a conservative guard time is energy wasteful. Hence, we formulate an optimization problem to minimize the expected energy consumption, with the constraint that the message capture probability should be no less than a threshold. We find that the problem is non-convex, hence cannot be solved by conventional convex optimization techniques. By investigating the unique structure of the problem, we transform the problem into a convex equivalent, and solve it using an efficient search method. Simulations show that our scheme significantly outperforms schemes that do not intelligently consider the synchronization error. We also remove the assumption that the capture probability threshold is given, and study how to decide it to meet the quality of services (QoS) requirements of the application
- 1 January 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10586393,p. 1937-1941
Performance of Random Access Scheduling Schemes in Multi-hop Wireless Networks
The performance of scheduling schemes in multi- hop wireless networks has attracted significant attention in the recent literature. It is well known that optimal scheduling solutions require centralized information and lead to impractical implementations due to their enormous complexity (high-degree polynomial or NP-hard, depending on the interference scenario). Further, an important characteristic in many multi-hop scenarios is the need for distributed algorithms that operate on local information. Thus, in this paper we develop a constant-time random access distributed algorithm for scheduling in multi- hop wireless networks. An important feature of this scheme is that it achieves a 2-approximation efficiency ratio and can be implemented in an entirely distributed manner with low overhead.
- 1 January 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10586393,p. 1937-1941
Performance of Random Access Scheduling Schemes in Multi-hop Wireless Networks
The performance of scheduling schemes in multi- hop wireless networks has attracted significant attention in the recent literature. It is well known that optimal scheduling solutions require centralized information and lead to impractical implementations due to their enormous complexity (high-degree polynomial or NP-hard, depending on the interference scenario). Further, an important characteristic in many multi-hop scenarios is the need for distributed algorithms that operate on local information. Thus, in this paper we develop a constant-time random access distributed algorithm for scheduling in multi- hop wireless networks. An important feature of this scheme is that it achieves a 2-approximation efficiency ratio and can be implemented in an entirely distributed manner with low overhead.
- 1 November 2005
- Published by Springer Nature in Wireless Networks
- Vol. 11 (6) , 661-676
Channel Sharing Scheme for Packet-Switched Cellular Networks
- 1 November 2005
- Published by Springer Nature in Wireless Networks
- Vol. 11 (6) , 661-676
Channel Sharing Scheme for Packet-Switched Cellular Networks