Joint Scheduling Of Tasks And Communications In Distributed Computing System Over Optical Networks

Distributed computing organizes the interaction of geographically dispersed computing and storage resources to solve complex scientific problems when stronger computer power is required. Many of these advanced applications are both computation-intensive and data-intensive. Large volumes of datasets will be generated and transmitted between computing resources frequently, so the availability of large amounts of bandwidth coupled with low latency is required. As the best-effort nature of traditional IP networks cannot supply sufficient QoS guarantees, scientists expect to build distributed computing system directly over the optical networks in order to support the data-intensive scientific applications.In distributed computing a submitted job is splitted into sub-tasks which are scheduled onto suitalble computing resources communicating over a network. Distributed task scheduling has been studied intensively. Most of the efforts are based on packet switched network, i.e., IP network, and assume an ideal communication system in which the resources are fully connected and the communication between any two resources can be provisioned whenever they need. However, in the circuit-switched optical network scenario, a lightpath must be established before each data communication and the reserved bandwidth can not be used by other traffic until it is released. Therefore, there will be blocking probability for the lightpath establishment due to communication contention. Traditional task scheduling scheme can not be employed directly under the optical network scenario. We have to take into consideration the lightpath establishment when allocating tasks onto computing resources.The dissertation studies the joint scheduling of both task allocation and lightpath establishment, which is a new research problem. We first study the joint scheduling model and algorithm under dedicated optical networks, and then study the optimization for communication contention reduction. Next we study the joint scheduling problem with dynamic shared OVPN provisioning under public optical networks. Finally we design and implement a multi-domain OVPN service architecture for the distributed computing applications.In chaper 1, we first introduce the background for the distributed computing built on optical networks. Next, we survey the task scheduling in the distributed computing systems and lightpath scheduling in the optical networks, respectively. And then we analyse the necessity of joint scheduling of task allocation and lightpath establishment.Chaper 2 studies joint scheduling model and algorithm. Advanced scientific applications are often structured as workflows that express an application (or a job) by specifying a set of interdependent tasks, which can be represented by directed acyclic graph (DAG). Our target problem is abstracted as an optical network aware DAG scheduling problem. List scheduling algorithm, which is the most common heuristic for DAG scheduling, is extended to achieve joint scheduling by incorporating edge scheduling into task scheduling.Chaper 3, based on the proposed extended lisht scheduling algorithm, studies the optimization for communication contention reduction from two aspects: routing scheme and computing resource selection scheme. For the routing scheme, we proposed an adaptive route algorithm which can detour the heavey traffic and find an earliest start route for each lightpath request during scheduling. For the computing resource selection scheme, we proposed to map the task onto the nearby resource to reduce link contention by avoiding long-hop lightpath. Simulation shows that the computing resource selection scheme contributes in lower resource utilization, while the adaptive routing scheme has the advantage in the reduction of schedule length. When the two schemes are combined together, better performance can be achieved.Chapter 4 investigates how to make joint scheduling over public optical networks. The above proposed joint scheduling is based on static strategies with assumption that scheduler can acquire accurate resource information. However, in practice, network carriers may not expose detail network information to clients due to business confidentiality. We propose to employ OVPN to solve the problem. The OVPN resource can be dedicated or shared. The static joint scheduling approaches can be directly employed in the dedicated resource scenario, but occupies more network resources. Provisioning shared OVPN improves network resource usage efficiency, but introduces bandwidth variation. To deal with the resource dynamics in shared manner, we proposed a low-cost rescheduling scheme. Simulation shows that rescheduling under dynamic shared OVPN can achieve schedule performance close to static scheduling based on the whole network.In chapter 5, we design and develope a multi-domain OVPN (MD-OVPN) service architecture for distributed computing applications. The proposed MD-OVPN service hides the underlying complex multi domain connection and constructs an OVPN for its client in a single domain view. We analysed the new requirements for the MD-OVPN service and proposed a hierachical service model. Unlike the previous OVPN service implementation, in our proposed architecture, network resource virtualization is achieved by Tanffic Engineering Database (TED) partition maintained by a TED virtualization layer and management isolation is realized by encapsulating OVPN TED information and associated operations as an OVPN object. We implemented the MD-OVPN service based on Web service. The scheduler can create OVPN, acquire OVPN resource information and setup lightpath in the OVPN through the Web service interface. Finally a DAG modeled distributed computing application is scheduled on different OVPN partition scenarios across two ASON domains in 3TNet testbed.