Design and Implementation of Practical Schedulers for M2M Uplink Networks (eBook)

Akshay Kumar is currently a Systems Engineer in the ground systems architecture group at VT iDirect, USA. He received his Ph.D. in Electrical and Computer Engineering from Virginia Tech. in 2016. His research interests include designing efficient packet schedulers in wired/wireless networks, Quality-of-Service in cellular/satellite networks and network optimization for satellite networks.  Dr. Ahmed Abdelhadi is a Research Assistant Professor in the Department of Electrical and Computer Engineering at Virginia Tech. He leads research projects in the areas of wireless systems, cyber physical systems, and security. At Virginia Tech, he joined as a research faculty research groups working on research related to security and privacy such as Hume Center for National Security and Technology, and wireless systems such as Wireless@Virginia Tech research group. He received his Ph.D. in Electrical and Computer Engineering from the University of Texas at Austin. He coauthored more than 50 journal and conference papers, and 5 books in these research topics. He is also a senior member of IEEE. Dr. Charles Clancy is an Associate Professor, Bradley Department of Electrical and Computer Engineering, at Virginia Tech. He is also Director, Hume Center for National Security and Technology; Co-Director, NSF Security and Software Engineering Research Center; and L-3 Communications Faculty Fellow in Cybersecurity, College of Engineering.

Preface 5
Contents 7
Acronyms 10
1 Introduction 11
1.1 Organization 13
1.2 Current Trends in End-to-End QoS 13
1.2.1 QoS in Wired Networks 13
1.2.2 QoS in Wireless Networks 14
1.3 QoS in M2M Networks 14
1.4 Problem Statement 15
1.5 Contributions 15
2 Background Information 17
2.1 Delay Characterization Using Queuing Theory 18
2.1.1 G/G/1 Priority Queuing System 19
2.1.2 G/M/1 Priority Queuing System 19
2.1.3 M/G/1 Priority Queuing System 19
2.1.3.1 Special Case: M/D/1 Priority Queue 20
2.1.3.2 Special Case: M/M/1 Priority Queue 20
2.2 Packet Schedulers 20
2.2.1 FCFS Scheduling 21
2.2.2 Non-preemptive Resume Priority Scheduling 22
2.2.3 Preemptive Priority Scheduling 22
2.3 Fairness of Resource Allocation 23
2.3.1 Max-Min Fairness 23
2.3.2 Proportional Fairness 23
2.4 Convex Optimization: Lagrange Duality 24
3 Delay-Efficient Multiclass Packet Scheduler 25
3.1 Introduction 25
3.2 Contributions 26
3.3 M2M Uplink System Model 27
3.4 Problem Formulation 28
3.4.1 Application Utility Function 28
3.4.1.1 ED Utility 28
3.4.1.2 PU Utility 30
3.4.2 Proportionally Fair System Utility Metric 31
3.4.3 Optimization Problem 31
3.5 Proposed Scheduler 32
3.5.1 Service Order Between PU and ED Classes 32
3.5.2 Service Order Among PU Classes 32
3.5.3 Service Order Among ED Classes 33
3.5.4 Service Order Among Packets of a Given PU/ED Class 33
3.5.5 Optimization Search Space 33
3.6 Simulation Results 35
3.6.1 Toy Case 1: One PU and One ED Class 35
3.6.1.1 Impact of PU Latency Threshold lt and ED Utility Parameter, b 36
3.6.1.2 Impact of ED Utility Parameter, a 36
3.6.1.3 Impact of ED Arrival Rate 37
3.6.2 Toy Case 2: Two PU and Two ED Classes 37
3.6.2.1 Impact of QoS Heterogeneity of M2M Uplink 38
3.6.2.2 Impact of Choice of ED Threshold 40
3.6.2.3 Impact of Penalizing PU Failures 40
3.7 Chapter Summary 42
3.8 MATLAB Code 42
3.8.1 Utility Functions 42
3.8.2 Packet Schedulers: One PU and One ED Class 43
3.8.2.1 FCFS Policy 43
3.8.2.2 EDD Policy 44
3.8.2.3 Preemptive Priority Policy 46
3.8.2.4 Proposed Packet Scheduler Without PU Packet Drops 48
3.8.2.5 Proposed Packet Scheduler with PU Packet Drops 49
3.8.3 Impact of ED Utility Parameter, a: One PU and One ED Class 51
3.8.4 Impact of ED Utility Parameter, b: One PU and One ED Class 56
3.8.5 Impact of ED Arrival Rate: One PU and OneED Class 60
3.8.6 Packet Schedulers: Two PU and Two ED Classes 63
3.8.6.1 FCFS Policy: Two PU and Two ED Classes 63
3.8.6.2 EDD Policy: Two PU and Two ED Classes 64
3.8.6.3 Preemptive Priority Policy: Two PU and Two ED Classes 66
3.8.6.4 Proposed Packet Scheduler Without PU Packet Drops: Two PU and Two ED Classes 70
3.8.6.5 Proposed Packet Scheduler with PU Packet Drops: Two PU and Two ED Classes 76
3.8.7 Impact of QoS Heterogeneity and Penalizing PU Failures on Performance of Schedulers 82
4 Delay-Optimal Multiclass Packet Scheduler 91
4.1 Introduction 91
4.2 Contributions 93
4.3 System Model 93
4.4 Problem Formulation 95
4.4.1 Class-Wise Service Utility Function 95
4.4.2 Proportionally Fair System Utility Metric 97
4.4.3 Direct Optimization 97
4.4.4 Iterative Optimization Problem 99
4.5 Proof of Convexity of Optimization Problems 100
4.6 Delay-Optimal Packet Scheduler 102
4.6.1 Special Case 103
4.7 Complexity Analysis 104
4.7.1 Direct Optimization Problem 104
4.7.2 Iterative Optimization Problem 104
4.8 Simulation Results 105
4.9 Chapter Summary 108
4.10 MATLAB Code 109
4.10.1 Utility Function 109
4.10.2 State-of-the-Art Packet Schedulers 109
4.10.2.1 Weighted Round Robin 109
4.10.2.2 FCFS 112
4.10.2.3 Weighted Fair Scheduler 112
4.10.2.4 Max-Weight Scheduler 120
4.10.2.5 Preemptive Priority Scheduler (Priority Order Defined for All Classes) 123
4.10.2.6 Preemptive Priority Scheduler (Only Highest-Priority Class Defined) 126
4.10.3 Proposed Packet Scheduler 130
4.10.3.1 [Theory]: Delay-Efficient Scheduler for Three-Class Subsystem 130
4.10.3.2 [Theory]: System Utility Objective for Three-Class Subsystem 132
4.10.3.3 [Theory]: Delay-Efficient Scheduler for Two-Class Subsystem 133
4.10.3.4 [Theory]: System Utility Objective for Two-Class Subsystem 134
4.10.3.5 [Theory]: System Utility Objective for Four-Class System 135
4.10.3.6 [Theory]: Single-Stage Optimization 136
4.10.3.7 [Simulation]: Single-Stage Optimization 137
4.10.4 Main Program 142
5 Delay-Optimal Multitier Multiclass Packet Scheduler 155
5.1 Introduction 155
5.2 System Model 157
5.3 Problem Formulation 159
5.3.1 Class-Wise Service Utility Function 159
5.3.2 Proportionally Fair System Utility Metric 160
5.4 Joint MA-AS Packet Scheduler 161
5.4.1 Centralized Single-Stage Optimization 161
5.4.2 Distributed Iterative Optimization 163
5.4.2.1 Locally Delay-Optimal Scheduler at mth MA 164
5.4.2.2 Locally Delay-Optimal Scheduler at AS 165
5.5 Complexity Analysis 165
5.5.1 Centralized Optimization 166
5.5.2 Distributed Optimization 166
5.5.2.1 Information Exchange Overhead 167
5.6 Simulation Results 168
5.6.1 Convergence of Distributed Optimization 169
5.7 Chapter Summary 169
5.8 MATLAB Code 171
5.8.1 Proposed Joint Scheduler 172
5.8.1.1 Main MATLAB Program 172
5.8.1.2 [Theory]: Delay-Efficient Scheduler for Three Class Subsystem at MA 183
5.8.1.3 [Theory]: Delay-Efficient Scheduler for Three Class Subsystem at AS 186
5.8.1.4 [Theory]: Delay-Efficient Scheduler for Two Class Subsystem at MA 188
5.8.1.5 [Theory]: Delay-Efficient Scheduler for Two Class Subsystem at AS 189
5.8.1.6 [Theory]: System Utility Objective for Four Class Subsystem at MA 191
5.8.1.7 [Theory]: System Utility Objective for Three Class Subsystem at MA 192
5.8.1.8 [Theory]: System Utility Objective for Two Class Subsystem at MA 193
5.8.1.9 [Theory]: System Utility Objective for Four Class Subsystem at AS 193
5.8.1.10 [Theory]: System Utility Objective for Three Class Subsystem at AS 194
5.8.1.11 [Theory]: System Utility Objective for Two Class Subsystem at AS 195
5.8.1.12 [Theory]: Single-Stage Optimization 196
5.8.1.13 System Latency per Iteration of Distributed Scheduler 202
6 Conclusion and Future Work 208
6.1 Future Work 209
6.1.1 Analyze Trade-Off Between M2M Uplink Latency and Traffic Storage in M2M Core 209
6.1.2 Impact of Network Congestion in M2M Uplink 210
References 211
Index 219