Building Web services middleware with predictable execution times

Predictability of execution has seldom been considered important in the design of Web services middleware. However, with the paradigm shift brought by cloud computing and with offerings of Platforms and Infrastructure as services, execution level predictability is mandating an increased importance. Existing Web services middleware are optimised for throughput with unconditional acceptance of requests and execution in a best-effort manner. While achieving perceived levels of throughput, they also result in highly unpredictable execution times. This paper presents a generic set of guidelines, algorithms and software engineering techniques that enable service execution to complete within a given deadline. The proposed algorithms accept requests for execution based on their laxity and executes them to meet requested deadlines. An introduced admission control mechanism results in a large range of laxities, enabling more requests to be scheduled together by phasing out their execution. Specialised development libraries and operating systems empower them with increased control over execution. Two widely used Web services middleware products were enhanced using these techniques. The two systems are compared with their unmodified versions to measure the predictability gain achieved. Empirical evidence confirms that the enhancements made enable these systems to achieve more than 90% of the deadlines under any type of traffic, while the unmodified versions achieve less than 10% of the deadlines in high traffic conditions. Predictability of execution achieved through these techniques, would open up new application areas such as industrial control systems, avionics, robotics and financial trading systems to the use of Web services as a middleware platform.     

Differentiated Real-Time Data Services for E-Commerce Applications

The demand for real-time e-commerce data services has been increasing recently. In many e-commerce applications, it is essential to process user requests within their deadlines, i.e., before the market status changes, using fresh data reflecting the current market status. However, current data services are poor at processing user requests in a timely manner using fresh data. To address this problem, we present a differentiated real-time data service framework for e-commerce applications. User requests are classified into several service classes according to their importance, and they receive differentiated real-time performance guarantees in terms of deadline miss ratio. At the same time, a certain data freshness is guaranteed for all transactions that commit within their deadlines. A feedback-based approach is applied to differentiate the deadline miss ratio among service classes. Admission control and adaptable update schemes are applied to manage potential overload. A simulation study, which reflects the e-commerce data semantics, shows that our approach can achieve a significant performance improvement compared to baseline approaches. Our approach can support the specified per-class deadline miss ratios maintaining the required data freshness even in the presence of unpredictable workloads and data access patterns, whereas baseline approaches fail.     

Dynamic real-time scheduling strategies for interactive continuous media servers

In this paper, we propose and study a dynamic approach to schedule real-time requests in a video-on-demand (VOD) server. Providing quality of service in such servers requires uninterrupted and on-time retrieval of motion video data. VOD services and multimedia applications further require access to the storage devices to be shared among multiple concurrent streams. Most of the previous VOD scheduling approaches use limited run-time,0 information and thus cannot exploit the potential capacity of the system fully. Our approach improves throughput by making use of run-time information to relax admission control. It maintains excellent quality of service under varying playout rates by observing deadlines and by reallocating resources to guarantee continuous service. It also reduces start-up latency by beginning service as soon as it is detected that deadlines of all real-time requests will be met. We establish safe conditions for greedy admission, dynamic control of disk read sizes, fast initial service, and sporadic services. We conduct thorough simulations over a wide range of buffer capacities, load settings, and over varying playout rates to demonstrate the significant improvements in quality of service, throughput and start-up latency of our approach relative to a static approach.     

Scheduling on-demand data broadcast in mixed-type request environments

In many on-demand broadcast environments, there can be a mix of requests, in which some of the requests have real-time constraints, while other requests have no time constraints associated with them. We refer to such environments as mixed-type environments. Existing strategies for on-demand data in broadcast systems typically only consider how to minimize the wait time of the requests, while scheduling strategies for real-time requests typically only consider how to minimize the number of deadlines missed. How to satisfy both of these constraints is a challenging problem whose solution can benefit many applications. In this paper, we present an on-demand broadcast cost model that is more general than existing broadcast cost models because it considers both response time and number of deadlines missed. An analysis of the system is presented as a Markov decision process to ascertain the feasibility of an optimal policy. We propose two scheduling strategies for mixed-type broadcast systems that are based on our cost model: maximum paid cost first and maximum value gained first. The simulation results show that both of our strategies always achieve the best result, when compared to existing broadcast strategies, for varying request arrival rates, real-time to non-real-time request ratios, missed deadline weight values, wait-time bounds on the non-real-time requests, and varying broadcast rates.     

I/O issues in a multimedia system

In future computer system design, I/O systems will have to support continuous media such as video and audio, whose system demands are different from those of data such as text. Multimedia computing requires us to focus on designing I/O systems that can handle real-time demands. Video- and audio-stream playback and teleconferencing are real-time applications with different I/O demands. We primarily consider playback applications which require guaranteed real-time I/O throughput. In a multimedia server, different service phases of a real-time request are disk, small computer systems interface (SCSI) bus, and processor scheduling. Additional service might be needed if the request must be satisfied across a local area network. We restrict ourselves to the support provided at the server, with special emphasis on two service phases: disk scheduling and SCSI bus contention. When requests have to be satisfied within deadlines, traditional real-time systems use scheduling algorithms such as earliest deadline first (EDF) and least slack time first. However, EDF makes the assumption that disks are preemptable, and the seek-time overheads of its strict real-time scheduling result in poor disk utilization. We can provide the constant data rate necessary for real-time requests in various ways that require trade-offs. We analyze how trade-offs that involve buffer space affect the performance of scheduling policies. We also show that deferred deadlines, which increase buffer requirements, improve system performance significantly     

基于Web服务面向虚拟企业的柔性工作流管理技术研究

虚拟企业中盟员和其提供的服务是动态变化的．文中提出将工作流过程模型描述的活动规范中包含一个或多个Web服务请求,通过引入Web服务和Web服务请求的定义和约束,在活动实例的执行过程中实现Web服务请求与最佳Web服务提供企业动态的服务绑定和调用,由于虚拟企业内部的变化不会影响到各盟员业务过程的正常运行,因此具有较高的柔性和自适应性．     

Budget-Deadline Constrained Workflow Planning for Admission Control

In this paper, we assume an environment with multiple, heterogeneous resources, which provide services of different capabilities and of a different cost. Users want to make use of these services to execute a workflow application, within a certain deadline and budget. The problem considered in this paper is to find a feasible plan for the execution of the workflow which would allow providers to decide whether they can agree with the specific constraints set by the user. If they agree to admit the workflow, providers can allocate services for its execution in a way that both deadline and budget constraints are met while account is also taken of the existing load in the provider’s environment (confirmed reservations from other users whose requests have been accepted). A novel heuristic is proposed and evaluated using simulation with four different real-world workflow applications.     

A BiNoC architecture—aware task allocation and communication scheduling scheme

A novel real-time task allocation and scheduling scheme is proposed for a multi-core system incorporated in a Bidirectional Network-on-Chip (BiNoC) platform. Given a task graph, this scheme seeks to minimize the total execution time by allocating ready-to-execute tasks to as many available cores as possible subject to the real-time deadlines of each task. A refinement process is introduced to update the priority ranking of a task list so as to meet the timing constraints. In particular, the communication overhead is considered by incorporating the packet routing paths and delays into the overall optimization process. In doing so, the flexibility of bidirectional links of BiNoC is exploited to alleviate traffic congestion, such that more tasks could be executed concurrently at different cores and overall execution time be reduced. To validate the effectiveness of this proposed scheme, extensive simulations have been performed. The results clearly demonstrate the superior performance of this proposed scheme compared to existing approaches that did not exploit the flexibility of BiNoC.     

非固定双头镜像磁盘实时调度算法的研究

文章给出一个实时非固定双头镜像磁盘系统的形式化模型.该磁盘模型中的每个双头磁盘都有两个相互独立的磁臂,能够独立地完成寻找磁道过程.针对该磁盘系统,文章研究了3种实时调度算法.模拟实验表明,“忽略超截止期调度算法”的性能最好,因为它忽略了对超截止期限实时请求的处理.文章同时分析了固定双头镜像磁盘与非固定双头镜像磁盘之间的性能差别.实验结果表明,由于非固定双头磁盘的两个磁头可以独立寻找磁道,因此非固定双头镜像磁盘的性能比固定双头镜像磁盘的性能要好.     

A simulation-based approach for dynamic process management at web service platforms

Web services technology is being adopted as a viable deployment approach for future distributed software systems that enable business-to-business and business-to-consumer interactions across the open and dynamic internet environment. Recent research is focused on developing support technologies for web service discovery, on-demand service composition, and robust execution to facilitate web services based deployment of business processes. Developing techniques to cope with the volatile and open nature of the web during execution of composite services at the service platform is essential for delivering reliable and acceptable performance in this new process delivery framework. In this paper, we propose a simulation-based framework to guide scheduling of composite service execution. Online simulation of the dynamics of the open environment is used for scheduling service requests at the service platform. Comparison of the look-ahead simulation for different scheduling policies with the current execution state provides guidelines for service execution in order to cope with system volatility. We have implemented a prototype of the proposed framework and illustrate the feasibility of our approach with experimental studies.     

An efficient job management of computing service using integrated idle VM resources for high-performance computing based on OpenStack

In recent years, various studies on OpenStack-based high-performance computing have been conducted. OpenStack combines off-the-shelf physical computing devices and creates a resource pool of logical computing. The configuration of the logical computing resource pool provides computing infrastructure according to the user’s request and can be applied to the infrastructure as a service (laaS), which is a cloud computing service model. The OpenStack-based cloud computing can provide various computing services for users using a virtual machine (VM). However, intensive computing service requests from a large number of users during large-scale computing jobs may delay the job execution. Moreover, idle VM resources may occur and computing resources are wasted if users do not employ the cloud computing resources. To resolve the computing job delay and waste of computing resources, a variety of studies are required including computing task allocation, job scheduling, utilization of idle VM resource, and improvements in overall job’s execution speed according to the increase in computing service requests. Thus, this paper proposes an efficient job management of computing service (EJM-CS) by which idle VM resources are utilized in OpenStack and user’s computing services are processed in a distributed manner. EJM-CS logically integrates idle VM resources, which have different performances, for computing services. EJM-CS improves resource wastes by utilizing idle VM resources. EJM-CS takes multiple computing services rather than single computing service into consideration. EJM-CS determines the job execution order considering workloads and waiting time according to job priority of computing service requester and computing service type, thereby providing improved performance of overall job execution when computing service requests increase.

     

多媒体服务器混合磁盘调度策略

基于多媒体服务器的性能要求，提出了一种自适应的混合磁盘调度策略DRT-window．它既能满足实时请求对实时性的要求，根据实时请求的截止期动态选择窗口大小；又能在其松弛度内尽努力(best-effort)地服务非实时请求，从而减少非实时请求的响应时间。DRT-window采用了两级层次调度方案：第一层为不同类型的请求采用各自适合的调度策略；第二层为混合请求调度嚣，混合调度第一层中的不同类型的请求。通过性能比较和理论证明，表明此混合磁盘调度策略能在保证实时请求无抖动执行的同时，尽量地减少非实时请求的响应时间。     

Disseminating data with time constraint based on multichannel over ubiquitous computing environments

Time-constrained service plays an important role in ubiquitous services. However, the resource constraints of ubiquitous computing systems make it difficult to satisfy timing requirements of supported strategies. In this study, we study scheduling strategies for mobile data program with timing constraints in the form of deadlines. Unlike previously proposed scheduling algorithms for mobile systems which aim to minimize the mean access time, our goal is to identify scheduling algorithms for ubiquitous systems that ensure requests meet their deadlines. We present a study of the performance of traditional real-time strategies, and demonstrate that traditional real-time algorithms do not always perform the best in a mobile environment. We propose an efficient scheduling algorithm, called scheduling priority of mobile data with time constraint(SPMT), which is designed for timely delivery of data to mobile clients. The experimental results show that our approach outperforms other approaches over performance criteria.     

Toward effective service composition for real-time SOA-based systems

Many application domains are increasingly leveraging service-oriented architecture (SOA) techniques to facilitate rapid system deployment. Many of these applications are time-critical and, hence, real-time assurance is an essential step in the service composition process. However, there are gaps in existing service composition techniques for real-time systems. First, admission control is an essential technique to assure the time bound for service execution, but most of the service composition techniques for real-time systems do not take admission control into account. A service may be selected for a workflow during the composition phase, but then during the grounding phase, the concrete service may not be able to admit the workload. Thus, the entire composition process may have to be repeated. Second, communication time is an important factor in real-time SOA, but most of the existing works do not consider how to obtain the communication latencies between services during the composition phase. It is clear that maintaining a full table of communication latencies for all pairs of services is infeasible. Obtaining communication latencies between candidate services during the composition phase can also be costly, since many candidate services may not be used for grounding. Thus, some mechanism is needed for estimating the communication latency for composite services. In this paper, we propose a three-phase composition approach to address the above issues. In this approach, we first use a highly efficient but moderately accurate algorithm to eliminate most of the candidate compositions based on estimated communication latencies and assured service response latency. Then, a more accurate timing prediction is performed on a small number of selected compositions in the second phase based on confirmed admission and actual communication latency. In the third phase, specific concrete services are selected for grounding, and admissions are actually performed. The approach is scalable and can effectively achieve service composition for satisfying real-time requirements. Experimental studies show that the three-phase approach does improve the effectiveness and time for service composition in SOA real-time systems. In order to support the new composition approach, it is necessary to effectively specify the needed information. In this paper, we also present the specification model for timing-related information and the extension of OWL-S to support this specification model.     

A new real time disk-scheduling method based on GSR algorithm

Disk scheduling has an important role in QOS guarantee of soft real-time environments such as video-on-demand and multimedia servers. Since now, some disk-scheduling algorithms have been proposed to schedule real-time disk requests. One of the most recent algorithms is global seek-optimizing real-time (GSR) that schedules the disk requests with different ready times by a global regrouping scheme. In the present paper, we propose a real-time disk-scheduling algorithm based on GSR that is called IGSR (improved GSR). IGSR creates the scan-groups of the requests and tries to find a good feasible schedule by optimized grouping with considering another chance for tasks that miss their deadlines at initial grouping. With regard to the admission policy of tasks, two different version of proposed method are presented: the first one has been designed for the case that all the disk requests available simultaneously and second one has been designed for the case that requests are admitted dynamically (GSR does not support the second one). It means that in the second case, the request queue may change when a task is running but in the first one it does not change. Simulation results showed IGSR outperformed GSR and some other related works in terms of maximum supportable streams, number of missed deadlines, and disk throughput.     

硬实时软件建模与分析的进程代数方法

针对硬实时软件缺乏有效的系统动态行为建模机制,提出了一种用于硬实时软件建模与分析的进程代数方法。首先在时间通信顺序进程的基础上扩展硬实时语义得到硬实时通信顺序进程;然后提出时间调度算法,用于检查硬实时系统单个指令截止期的可满足性以及计算完成任务所需的最少时间;最后通过航空领域的一个实例来说明该方法如何应用于硬实时软件的建模与分析。该方法可以很大程度上提高硬实时软件执行时间计算的准确性,计算结果有助于硬实时系统截止期的量化分析和优化设计。     

一种新颖的带模糊截止时限的磁盘调度算法

设计了一种新的基于截止时限的磁盘调度算法,该算法支持带多优先级的请求。对于某些实时要求,其截止时限是不确定的或者不精确的,该算法采用模糊集来描述这类不确定性,模糊截止时限的隶属度函数表示对请求完成时间的满意程度。调度的目的是最优的指定优先级,使得截止时限的满意程度最大化。根据请求截止时限的不同,把满意程度划分为若干连续的区间。在每个不同的区间内,每个请求都对应有修正的截止时限,把请求按照其修正的截止时限非减的顺序分配优先级,才能实现请求优先级的最优配置。仿真结果表明该算法能有效的分配请求的优先级,降低请求的丢失率,保证了更多的请求得到满足。     

Towards IoT-enabled dynamic service optimal selection in multiple manufacturing clouds

With the Internet of Things, it is now possible to sense the real-time status of manufacturing objects and processes. For complex Service Selection (SS) in Cloud Manufacturing, real-time information can be utilized to deal with uncertainties emerging during task execution. Moreover, in the face of diversified demands, multiple manufacturing clouds (MCs) can provide a much wider range of choices of services with their real-time status. However, most researchers have neglected the superiority of multiple MCs and failed to make a study of how to utilize the abundant and diverse resources of multiple MCs, let alone the multi-MCs service mode under dynamic environment. Therefore, we first propose a new dynamic SS paradigm that can leverage the abundant services from multiple MCs, real-time sensing ability of the Internet of Things (IoT) and big data analytics technology for knowledge and insights. In this way, providing optimal manufacturing services (with high QoS) for customers can be guaranteed under dynamic environments. In addition, considering that a relatively long time might be spent to complete a complex manufacturing task after SS, a quantified approach, based on the Analytic Hierarchy Process and big data, is proposed to evaluate whether the intended cloud manufacturing services should be reserved to make sure that eligible services are ready to use without compromising cost or time. In this paper, the problem of IoT-enabled dynamic SS across multiple MCs is formulated in detail to enable an event-driven adaptive scheduling when the model is faced with three kinds of uncertainties (of the service market, service execution and the user side respectively). Experiments with different settings are also performed, which show the advantages of our proposed paradigm and optimization model.     

A design of RFTOG model for distributed real-time applications

In this paper, we design the Real-Time Fault-Tolerant Object Group (RFTOG) model that supports the grouping of distributed objects that are required for distributed application. The proposed model basically provides two services. One is the group management service, which supports both consistency maintenance and transparency of the replicated objects with a variety of replication mechanisms. It also provides the load balancing of distributed applications. The other is real-time service in an object group. When the clients request the service to the service object selected through the load balance, this service guarantees the service execution within deadline for the clients’ requests. We develop the Naval Air Defense System (NADS) simulator for verifying the effectiveness of the services proposed by the RFTOG model.     

Disk scheduling in video editing systems

Modern video servers support both video-on-demand and nonlinear editing applications. Video-on-demand servers enable the user to view video clips or movies from a video database, while nonlinear editing systems enable the user to manipulate the content of the video database. Applications such as video and news editing systems require that the underlying storage server be able to concurrently record live broadcast information, modify prerecorded data, and broadcast an authored presentation. A multimedia storage server that efficiently supports such a diverse group of activities constitutes the focus of this study. A novel real-time disk scheduling algorithm is presented that treats both read and write requests in a homogeneous manner in order to ensure that their deadlines are met. Due to real-time demands of movie viewing, read requests have to be fulfilled within certain deadlines; otherwise, they are considered lost. Since the data to be written into disk is stored in main memory buffers, write requests can be postponed until critical read requests are processed. However, write requests still have to be processed within reasonable delays and without the possibility of indefinite postponement. This is due to the physical constraint of the limited size of the main memory write buffers. The new algorithm schedules both read and write requests appropriately, to minimize the amount of disk reads that do not meet their presentation deadlines, and to avoid indefinite postponement and large buffer sizes in the case of disk writes. Simulation results demonstrate that the proposed algorithm offers low violations of read deadlines, reduces waiting time for lower priority disk requests, and improves the throughput of the storage server by enhancing the utilization of available disk bandwidth