An MID-Based Load Balancing Approach for Topic-Based Pub-Sub Overlay Construction  

作　　者：Ruisheng Shi Fuqiang Liu Yang Zhang Bo Cheng Junliang Chen 

机构地区：[1]State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China [2]Naval Academy of Armament, Beijing 100073, China

出　　处：《Tsinghua Science and Technology》2011年第6期589-600,共12页清华大学学报（自然科学版（英文版）

基　　金：Supported by the National Key Basic Research and Development (973) Program of China (No. 2011CB302700);the National Natural Science Foundation of China (Nos. 61171102,61132001, and 61001118)

摘　　要：A large proportion of Internet of Things （loT） applications are internally publish/subscribe in nature, and traditional architecture cannot support them efficiently and flexibly. In essence, supporting efficient publish/subscribe systems requires data-oriented naming and efficient multicast. Since deployment of native IP-based multicast has failed, overlay-based multicast has become the practical choice. Since load balancing between heterogeneous nodes is an important issue, designing an optimal load balancing overlay net- work for publish/subscribe systems is a necessary endeavor. This study focuses on the optimal load balancing overlay design problem for topic-based publish/subscribe systems in a heterogeneous environment （in terms of node processing power, bandwidth, and reachability）. The Minimum Idle Degree （MID） model is introduced to capture the heterogeneity of overlay nodes. Based on the MID model, new node load measures are defined that can accommodate heterogeneous server capacities and capture the node load in publish/subscribe systems more accurately than traditional measures. A new optimization problem, Maximum Minimum Idle Degree Topic-Connected Overlay （MMID-TCO）, is established. This problem is NP-complete and a constant approximation algorithm does not exist for this problem （unless P=NP）. Based on MID metrics, the Maximum Minimum Idle Degree Overlay Design Algorithm （MMID-ODA）, which has polynomial time is introduced. To improve performance, an approach that breaks down the problem into several small-scale problems by exploiting the potential inherent disjoint characteristic in the subscription table is presented. Simulation results show that the proposed algorithm is able to achieve better load balance than MinMax-ODA in a heterogeneous environment.A large proportion of Internet of Things （loT） applications are internally publish/subscribe in nature, and traditional architecture cannot support them efficiently and flexibly. In essence, supporting efficient publish/subscribe systems requires data-oriented naming and efficient multicast. Since deployment of native IP-based multicast has failed, overlay-based multicast has become the practical choice. Since load balancing between heterogeneous nodes is an important issue, designing an optimal load balancing overlay net- work for publish/subscribe systems is a necessary endeavor. This study focuses on the optimal load balancing overlay design problem for topic-based publish/subscribe systems in a heterogeneous environment （in terms of node processing power, bandwidth, and reachability）. The Minimum Idle Degree （MID） model is introduced to capture the heterogeneity of overlay nodes. Based on the MID model, new node load measures are defined that can accommodate heterogeneous server capacities and capture the node load in publish/subscribe systems more accurately than traditional measures. A new optimization problem, Maximum Minimum Idle Degree Topic-Connected Overlay （MMID-TCO）, is established. This problem is NP-complete and a constant approximation algorithm does not exist for this problem （unless P=NP）. Based on MID metrics, the Maximum Minimum Idle Degree Overlay Design Algorithm （MMID-ODA）, which has polynomial time is introduced. To improve performance, an approach that breaks down the problem into several small-scale problems by exploiting the potential inherent disjoint characteristic in the subscription table is presented. Simulation results show that the proposed algorithm is able to achieve better load balance than MinMax-ODA in a heterogeneous environment.

关 键 词：optimal problem load balancing heterogeneity topic-based PUBLISH/SUBSCRIBE 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TS943.745[自动化与计算机技术—计算机科学与技术]