Shijing Li
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Shijing Li has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Tian Lan
George Washington University, Washington, DC, USA
3 shared publications - Moo-Ryong Ra
AT&T Labs Research, Atlanta, GA, USA
2 shared publications - Bharath Balasubramanian
AT&T Labs Research, Atlanta, GA, USA
1 shared publication Hee Won Lee
AT&T Labs Research, Atlanta, GA, USA
1 shared publicationMoo-Ryong Ra
1 shared publicationRajesh Krishna Panta
AT&T Labs Research, Atlanta, GA, USA
1 shared publication
Latest Publications
- 2 August 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 9 (6) , 4075-4086
From Network Inference Errors to Utility Suboptimality: How Much Is the Impact?
Accurate and timely network inference, known as network tomography, is a vital ingredient in efficient network operation, supporting more sophisticated and ambitious traffic optimization algorithms. In practice, however, precise knowledge of the dynamic internal network bottlenecks/states can be impossible to obtain under restricted network visibility on network edge where only end-to-end measurements are available without cooperation of internal network components. In this paper, we acknowledge that network tomography on the edge is often imperfect, leading to dynamic, time-varying inference errors that could change from iteration to iteration on the same time-scale as distributed network optimization algorithms. We quantify the impact of such imperfect bottleneck/state inference on algorithm convergence and optimality. In particular, we show that under arbitrary, bounded inference errors (belonging to three common classes including absent and incorrect bottlenecks, and inaccurate capacity), the solution of the distributed optimization algorithm still converges to a bounded neighborhood of the optimal solution. The resulted optimality gap is quantified in closed form and shown to be proportional to average inference errors. These results are evaluated using extensive network simulations and on real-world IoT data sets. The work provide a theoretical support for understanding the impact of imperfect inference on distributed network optimization.
- 2 August 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 9 (6) , 4075-4086
From Network Inference Errors to Utility Suboptimality: How Much Is the Impact?
Accurate and timely network inference, known as network tomography, is a vital ingredient in efficient network operation, supporting more sophisticated and ambitious traffic optimization algorithms. In practice, however, precise knowledge of the dynamic internal network bottlenecks/states can be impossible to obtain under restricted network visibility on network edge where only end-to-end measurements are available without cooperation of internal network components. In this paper, we acknowledge that network tomography on the edge is often imperfect, leading to dynamic, time-varying inference errors that could change from iteration to iteration on the same time-scale as distributed network optimization algorithms. We quantify the impact of such imperfect bottleneck/state inference on algorithm convergence and optimality. In particular, we show that under arbitrary, bounded inference errors (belonging to three common classes including absent and incorrect bottlenecks, and inaccurate capacity), the solution of the distributed optimization algorithm still converges to a bounded neighborhood of the optimal solution. The resulted optimality gap is quantified in closed form and shown to be proportional to average inference errors. These results are evaluated using extensive network simulations and on real-world IoT data sets. The work provide a theoretical support for understanding the impact of imperfect inference on distributed network optimization.
- 1 March 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 9 (4) , 2110-2122
Pushing Collaborative Data Deduplication to the Network Edge: An Optimization Framework and System Design
Edge computing has become a new computing paradigm with explosive growth in recent years. We consider the problem of pushing data deduplication to the network edge and propose a new framework for distributed edge-facilitated deduplication (EF-dedup). Deduplication at the network edge allows us to exploit the high degree of geographic- and temporal-correlation in edge data to achieve space efficiency. By leveraging distributed computing power available on the edge in a collaborative fashion, the edge nodes can effectively suppress duplicated edge data, consuming considerably less space and WAN bandwidth. To this end, we partition the edge nodes into disjoint collaborative clusters, maintain a deduplication index structure across them using a distributed key-value store and perform deduplication within those clusters. However, this partitioning problem is very challenging and requires the optimization of a novel tradeoff: edge nodes with highly correlated data may not always be within the same edge cloud, with non-trivial network cost among them. We formulate a joint storage and network optimization problem with different design objectives, such as arbitrary partitioning and balanced partitioning of edge nodes. The problem is shown to be NP-Hard in general. Then, an optimization framework with efficient algorithms is developed and is proven to achieve a closed-form competitive ratio. Our experiments, performed on edge nodes in a corporate lab 1 and a central cloud at AWS, demonstrate that EF-dedup achieves 67.4 $\sim$ 133.7% better deduplication throughput than sole cloud-based techniques and achieves 20.0-62.6 $\%$ lesser aggregate cost in terms of the network-storage trade-off as compared to approaches that solely favor one over the other.
- 1 March 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 9 (4) , 2110-2122
Pushing Collaborative Data Deduplication to the Network Edge: An Optimization Framework and System Design
Edge computing has become a new computing paradigm with explosive growth in recent years. We consider the problem of pushing data deduplication to the network edge and propose a new framework for distributed edge-facilitated deduplication (EF-dedup). Deduplication at the network edge allows us to exploit the high degree of geographic- and temporal-correlation in edge data to achieve space efficiency. By leveraging distributed computing power available on the edge in a collaborative fashion, the edge nodes can effectively suppress duplicated edge data, consuming considerably less space and WAN bandwidth. To this end, we partition the edge nodes into disjoint collaborative clusters, maintain a deduplication index structure across them using a distributed key-value store and perform deduplication within those clusters. However, this partitioning problem is very challenging and requires the optimization of a novel tradeoff: edge nodes with highly correlated data may not always be within the same edge cloud, with non-trivial network cost among them. We formulate a joint storage and network optimization problem with different design objectives, such as arbitrary partitioning and balanced partitioning of edge nodes. The problem is shown to be NP-Hard in general. Then, an optimization framework with efficient algorithms is developed and is proven to achieve a closed-form competitive ratio. Our experiments, performed on edge nodes in a corporate lab 1 and a central cloud at AWS, demonstrate that EF-dedup achieves 67.4 $\sim$ 133.7% better deduplication throughput than sole cloud-based techniques and achieves 20.0-62.6 $\%$ lesser aggregate cost in terms of the network-storage trade-off as compared to approaches that solely favor one over the other.
- 11 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 29 (12) , 2826-2837
Joint Scheduling and Source Selection for Background Traffic in Erasure-Coded Storage
Erasure-coded storage systems have gained considerable adoption recently since they can provide the same level of reliability with significantly lower storage overhead compared to replicated systems. However, background traffic of such systems — e.g. repair, rebalance, backup and recovery traffic — often has large volume and consumes significant network resources. Independently scheduling such tasks and selecting their sources can easily create interference among data flows, causing severe deadline violation. We show that the well-known heuristic scheduling algorithms fail to consider important constraints, thus resulting in unsatisfactory performance. In this paper, we claim that an optimal scheduling algorithm, which aims to maximize the number of background tasks completed before deadlines, must simultaneously consider task deadline, network topology, chunk placement, and time-varying resource availability. We first show that the corresponding optimization problem is NP-hard. Then we propose a novel algorithm, called Linear Programming for Selected Tasks (LPST) to maximize the number of successful tasks and improve overall utilization of the datacenter network. It jointly schedules tasks and selects their sources based on a notion of Remaining Time Flexibility, which measures the slackness of the starting time of a task. We evaluated the efficacy of our algorithm using extensive simulations and validate the results with experiments in a real cloud environment. Our results show that, under certain scenarios, LPST can perform $7\times\;\sim\;10\times$ better than the heuristics which blindly treat the infrastructure as a collection of homogeneous resources, and $21.7\%\sim65.9\%$ better than the algorithms that only take the network topology into account.- 11 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 29 (12) , 2826-2837
Joint Scheduling and Source Selection for Background Traffic in Erasure-Coded Storage
Erasure-coded storage systems have gained considerable adoption recently since they can provide the same level of reliability with significantly lower storage overhead compared to replicated systems. However, background traffic of such systems — e.g. repair, rebalance, backup and recovery traffic — often has large volume and consumes significant network resources. Independently scheduling such tasks and selecting their sources can easily create interference among data flows, causing severe deadline violation. We show that the well-known heuristic scheduling algorithms fail to consider important constraints, thus resulting in unsatisfactory performance. In this paper, we claim that an optimal scheduling algorithm, which aims to maximize the number of background tasks completed before deadlines, must simultaneously consider task deadline, network topology, chunk placement, and time-varying resource availability. We first show that the corresponding optimization problem is NP-hard. Then we propose a novel algorithm, called Linear Programming for Selected Tasks (LPST) to maximize the number of successful tasks and improve overall utilization of the datacenter network. It jointly schedules tasks and selects their sources based on a notion of Remaining Time Flexibility, which measures the slackness of the starting time of a task. We evaluated the efficacy of our algorithm using extensive simulations and validate the results with experiments in a real cloud environment. Our results show that, under certain scenarios, LPST can perform $7\times\;\sim\;10\times$ better than the heuristics which blindly treat the infrastructure as a collection of homogeneous resources, and $21.7\%\sim65.9\%$ better than the algorithms that only take the network topology into account.- 1 June 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 2025-2030
S3: Joint Scheduling and Source Selection for Background Traffic in Erasure-Coded Storage
Erasure-coded storage systems have gained considerable adoption recently since they can provide the same level of reliability with significantly lower storage overhead compared to replicated systems. However, background traffic of such systems - e.g. repair, rebalance, backup and recovery traffic - often has large volume and consumes significant network resources. Independently scheduling such tasks and selecting their sources can easily create interference among data flows, causing severe deadline violation. We show that the well-known heuristic scheduling algorithms fail to consider important constraints, thus resulting in unsatisfactory performance. In this paper, we claim that an optimal scheduling algorithm that aims to maximizethe number of background tasks completed before deadlines must simultaneously consider deadline-aware scheduling, network topology, chunk placement, and time-varying resource availability. To solve this problem, we propose a novel algorithm, called Linear Programming for Selected Tasks (LPST) to maximize the number of successful tasks and improve overallutilization of the datacenter network. It jointly schedules tasks and selects their sources based on a notion of Remaining Time Flexibility, which measures the slackness of the starting time of a task. We evaluated the efficacy of our algorithm using extensive simulations. Our results show that, under certain scenarios, LPST can perform 7x~70x better than the heuristics which blindly treat the infrastructure as a collection of homogeneous resources, and 46.6%~65.9% better than the algorithms that take into accountthe network topology.
- 1 June 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 2025-2030
S3: Joint Scheduling and Source Selection for Background Traffic in Erasure-Coded Storage
Erasure-coded storage systems have gained considerable adoption recently since they can provide the same level of reliability with significantly lower storage overhead compared to replicated systems. However, background traffic of such systems - e.g. repair, rebalance, backup and recovery traffic - often has large volume and consumes significant network resources. Independently scheduling such tasks and selecting their sources can easily create interference among data flows, causing severe deadline violation. We show that the well-known heuristic scheduling algorithms fail to consider important constraints, thus resulting in unsatisfactory performance. In this paper, we claim that an optimal scheduling algorithm that aims to maximizethe number of background tasks completed before deadlines must simultaneously consider deadline-aware scheduling, network topology, chunk placement, and time-varying resource availability. To solve this problem, we propose a novel algorithm, called Linear Programming for Selected Tasks (LPST) to maximize the number of successful tasks and improve overallutilization of the datacenter network. It jointly schedules tasks and selects their sources based on a notion of Remaining Time Flexibility, which measures the slackness of the starting time of a task. We evaluated the efficacy of our algorithm using extensive simulations. Our results show that, under certain scenarios, LPST can perform 7x~70x better than the heuristics which blindly treat the infrastructure as a collection of homogeneous resources, and 46.6%~65.9% better than the algorithms that take into accountthe network topology.