This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service ...This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.展开更多
Software performance evaluation in multimedia communication systems is typically formulated into a multi-layered client-server queuing network(MLCSQN) problem. However, the existing analytical methods to MLCSQN model ...Software performance evaluation in multimedia communication systems is typically formulated into a multi-layered client-server queuing network(MLCSQN) problem. However, the existing analytical methods to MLCSQN model cannot provide satisfactory solution in terms of accuracy, convergence and consideration of interlocking effects. To this end, this paper proposes a heuristic solving method for MLCSQN model to boost the performance prediction of distributed multimedia software systems. The core concept of this method is referred to as the basic model, which can be further decomposed into two sub-models: client sub-model and server sub-model. The client sub-model calculates think time for server sub-model, and the server sub-model calculates waiting time for client sub-model. Using a breadthfirst traversal from leaf nodes to the root node and vice versa, the basic model is then adapted to MLCSQN, with net sub-models iteratively resolved. Similarly, the interlocking problem is effectively addressed with the help of the basic model. This analytical solver enjoys advantages of fast convergence, independence on specific average value analysis(MVA) methods and eliminating interlocking effects.Numerical experimental results on accuracy and computation efficiency verify its superiority over anchors.展开更多
In this paper,a new architecture of optical networks—the optical network based on server system is considered.From the point of this new architecture,the network can be modeled as a server system with three type serv...In this paper,a new architecture of optical networks—the optical network based on server system is considered.From the point of this new architecture,the network can be modeled as a server system with three type servers—the access server,the node server and the link server. The network performances such as cost,energy consume and network capacity can be affected by the capability of these three type servers.New ILP formulations are proposed to analyze the network capacity under two types of node severs,with and without wavelength converter.Computer simulations are conducted to evaluate the effectiveness of these new formulations.The study has shown that the network can achieve the same throughput under the two types of node servers and the network throughput increases when the maximum allowed variation increases.展开更多
Mobile cloud computing （MCC） has become a promising technique to deal with computation- or data-intensive tasks. It overcomes the limited processing power, poor storage capacity, and short battery life of mobile dev...Mobile cloud computing （MCC） has become a promising technique to deal with computation- or data-intensive tasks. It overcomes the limited processing power, poor storage capacity, and short battery life of mobile devices. Providing continuous and on-demand services, MCC argues that the service must be available for users at anytime and anywhere. However, at present, the service availability of MCC is usually measured by some certain metrics of a real-world system, and the results do not have broad representation since different systems have different load levels, different deployments, and many other random factors. Meanwhile, for large-scale and complex types of services in MCC systems, simulation-based methods （such as Monte- Carlo simulation） may be costly and the traditional state-based methods always suffer from the problem of state-space explosion. In this paper, to overcome these shortcomings, fluid-flow approximation, a breakthrough to avoid state-space explosion, is adopted to analyze the service availability of MCC. Four critical metrics, including response time of service, minimum sensing time of devices, minimum number of nodes chosen, and action throughput, are def＇med to estimate the availability by solving a group of ordinary differential equations even before the MCC system is fully deployed. Experimental results show that our method costs less time in analyzing the service availability of MCC than the Markov- or simulation-based methods.展开更多
基金Project supported by the National Natural Science Foundation of China (No. 10271110) and the Teaching and Research Award Pro-gram for Outstanding Young Teachers in Higher Education, Institu-tions of MOE, China
文摘This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.
基金supported by the Application Research of the Remote Sensing Technology on Global Energy Internet(JYYKJXM(2017)011)the National Natural Science Foundation of China(61671332,41701518,41771452,41771454,U1736206)+4 种基金National key R&D Project(2016YFE0202300)Hubei Province Technological Innovation Major Project(2017AAA123)Applied Basic Research Program of Wuhan City(2016010101010025)Basic Research Program of Shenzhen(JCYJ20170306171431656)the Fundamental Research Funds for the Central Universities(2042016gf0033)
文摘Software performance evaluation in multimedia communication systems is typically formulated into a multi-layered client-server queuing network(MLCSQN) problem. However, the existing analytical methods to MLCSQN model cannot provide satisfactory solution in terms of accuracy, convergence and consideration of interlocking effects. To this end, this paper proposes a heuristic solving method for MLCSQN model to boost the performance prediction of distributed multimedia software systems. The core concept of this method is referred to as the basic model, which can be further decomposed into two sub-models: client sub-model and server sub-model. The client sub-model calculates think time for server sub-model, and the server sub-model calculates waiting time for client sub-model. Using a breadthfirst traversal from leaf nodes to the root node and vice versa, the basic model is then adapted to MLCSQN, with net sub-models iteratively resolved. Similarly, the interlocking problem is effectively addressed with the help of the basic model. This analytical solver enjoys advantages of fast convergence, independence on specific average value analysis(MVA) methods and eliminating interlocking effects.Numerical experimental results on accuracy and computation efficiency verify its superiority over anchors.
基金supported by China Post-doctoral Science Foundation funded project(20070420013)Open Fund of National Laboratory on Local Fiber-Optic Communication Networks & Advanced optical Communication Systems,(Pe-king University),PRChinaGuangxi Science Foundation(0731003)
文摘In this paper,a new architecture of optical networks—the optical network based on server system is considered.From the point of this new architecture,the network can be modeled as a server system with three type servers—the access server,the node server and the link server. The network performances such as cost,energy consume and network capacity can be affected by the capability of these three type servers.New ILP formulations are proposed to analyze the network capacity under two types of node severs,with and without wavelength converter.Computer simulations are conducted to evaluate the effectiveness of these new formulations.The study has shown that the network can achieve the same throughput under the two types of node servers and the network throughput increases when the maximum allowed variation increases.
基金Project supported by the National Natural Science Foundation of China （Nos. 61402127 and 61370212） and the Natural Science Foundation of Heilongjiang Province, China （No. F2015029）
文摘Mobile cloud computing （MCC） has become a promising technique to deal with computation- or data-intensive tasks. It overcomes the limited processing power, poor storage capacity, and short battery life of mobile devices. Providing continuous and on-demand services, MCC argues that the service must be available for users at anytime and anywhere. However, at present, the service availability of MCC is usually measured by some certain metrics of a real-world system, and the results do not have broad representation since different systems have different load levels, different deployments, and many other random factors. Meanwhile, for large-scale and complex types of services in MCC systems, simulation-based methods （such as Monte- Carlo simulation） may be costly and the traditional state-based methods always suffer from the problem of state-space explosion. In this paper, to overcome these shortcomings, fluid-flow approximation, a breakthrough to avoid state-space explosion, is adopted to analyze the service availability of MCC. Four critical metrics, including response time of service, minimum sensing time of devices, minimum number of nodes chosen, and action throughput, are def＇med to estimate the availability by solving a group of ordinary differential equations even before the MCC system is fully deployed. Experimental results show that our method costs less time in analyzing the service availability of MCC than the Markov- or simulation-based methods.
