A Hard Real-Time Distributed Hash Table in Wide-Area Networks Project Team Tao Qian Introduction In theory, for a hard real-time system which utilizes a single computation unit, it is straightforward to perform schedulability test offline based on the system utilization/density, or the result of time-demand analysis (TDA) and general- TDA, given the details of the tasks to schedule, including their phases, periods, and execution times. However, other factors such as context switch costs, release time jitters, deviation of execution times also could impact the feasibility of a real-time system in realism. In addition, when real-time systems become distributed, multiple computation units need to cooperate. Thus, the communication cost between these units contributes significantly to the schedululability test result for a task set. Consider the distributed storage system in which the distributed nodes follow the Chord algorithm to communicate with each other. Our previous work has shown the feasibility of using stochastic models to address the probability deadline (soft deadline) and the quality of service in the situation that cyclic executives are employed to schedule tasks on these distributed nodes. The previous work is based on a few assumptions. First, the lookup data are of high probability evenly distributed on nodes, i.e. each node in a N-nodes system has 1/N of total data on average. Second, each node has a same pattern of lookup requests. Third, the network delay for a message transmission results in a Poisson message arrival pattern, which is realistic in networks of simple topology, e.g., all computation nodes in our previous work are connected by a single network switch. In order to schedule task sets with hard deadlines in distributed storage systems over wide-area networks, we plan to release these assumptions in this project. First, we shall provide a formal model to describe the task set in the distributed storage system. In the model, tasks released by one node will have less dependency on the tasks released on other nodes. This releases the first two assumptions in our previous work. Second, we shall provide a formal model to describe the underneath network which is utilized to transmit messages between nodes. This network model will include complex network topology as well. With these information, we will derive the end-to-end response time for each lookup task and determine whether tasks can be finished before their deadlines. We will employ a FIFO executive on each node. In general, the factors that impact the end-to-end response times could be divided into two parts: 1) the lookup demands to the system; 2) the resource that is available to the system, including the computation capacity and network bandwidth. Our model considers the end-to-end response time as an optimization problem. In one respective, given the lookup demands as well as the required deadlines, our model will provide an optimized requirement for the computation capacity and network bandwidth to meet the deadlines. In the other respective, given a specific set of resources the system can utilize, our model shall determine which requests, if any, cannot meet their deadlines under a specific scheduling algorithm. To build up a system to evaluate our model for the offline test, we propose the following details in the implementation and experiments. First, software-defined networks are used to guarantee the network resource for the system. Second, since nodes share network resource, we employ a traffic controller on each node, which acts like a cushion between the computation node and the network, to prevent the negative impact (congestion) to other nodes in the case that some nodes may try to send more data than modeled as a result of deviation of task execution times. In the experiments, we will evaluate our model and the implementation on a switch-connected cluster (simple network topology) as well as GENI (a platform provides computation nodes and wide-area network resources).
Timeline
Progress March 31, 2014 1. Decompose a request into different phases and derive the time cost in each phase. These phases include: message process phase, message waiting in the sending queue phase, and message transmission phase. 2. Use fix-point iteration to solve the equation for the time for message waiting in the sending queue.
3. Derive the algorithm to share the bandwidth. The algorithm should give feasible configurations of sharing the physic bandwidth so that bandwidth demand between each pair of nodes is guaranteed. Deliverables |