In grid networks, distributed resources are interconnected by wide area network to support compute and data-intensive applications, which require reliable and efficient transfer of gigabits (even terabits) of data. Different from best-effort traffic in Internet, bulk data transfer in grid requires bandwidth reservation as a fundamental service. Existing reservation schemes such as RSVP are designed for real-time traffic specified by reservation rate, transfer start time but with unknown lifetime. In comparison, bulk data transfer requests are defined in terms of volume and deadline, which provide more information, and allow more flexibility in reservation schemes, i.e., transfer start time can be flexibly chosen, and reservation for a single request can be divided into multiple intervals with different reservation rates. We define a flexible reservation framework using time-rate function algebra, and identify a series of practical reservation scheme families with increasing generality and potential performance, namely, FixTime-FixRate, FixTime-FlexRate, FlexTime-FlexRate, and Multi-Interval. Simple heuristics are used to select representative scheme from each family for performance comparison. Simulation results show that the increasing flexibility can potentially improve system performance, minimizing both blocking probability and mean flow time. We also discuss the distributed implementation of proposed framework.
@cite_3: We present a polynomial time algorithm for constructing an optimal schedule, if a feasible schedule exists, for tthe following multimachine scheduling problem. There are n unit-time jobs, with arbitrary release times and deadlines, and m identical parallel machines. A feasible schedule is one in which no job is started before it is released, each job is completed by its deadline, and no job is interrupted once it begins to run.
@cite_4: We consider the online competitiveness for scheduling a single resource non-preemptively in order to maximize its utilization. Our work examines this model when parameterizing an instance by a new value which we term the patience. This parameter measures each job's willingness to endure a delay before starting, relative to this same job's processing time. Specifically, the slack of a job is defined as the gap between its release time and the last possible time at which it may be started while still meeting its deadline. We say that a problem instance has patience κ, if each job with length ||J|| has a slack of at least κ ċ ||J||.Without any restrictions placed on the job characteristics, previous lower bounds show that no algorithm, deterministic or randomized, can guarantee a constant bound on the competitiveness of a resulting schedule. Previous researchers have analyzed a problem instance by parameterizing based on the ratio between the longest job's processing time and the shortest job's processing time. Our main contribution is to provide a fine-grained analysis of the problem when simultaneously parameterized by patience and the range of job lengths. We are able to give tight or almost tight bounds on the deterministic competitiveness for all parameter combinations.If viewing the analysis of each parameter individually, our evidence suggests that parameterizing solely on patience provides a richer analysis than parameterizing solely on the ratio of the job lengths. For example, in the special case where all jobs have the same length, we generalize a previous bound of 2 for the deterministic competitiveness with arbitrary slacks, showing that the competitiveness for any κ ≥ 0 is exactly 1 + 1 (⌊κ⌋ + 1). Without any bound on the job lengths, a simple greedy algorithm is (2+ 1 κ)- competitive for any κ > 0. More generally we will find that for any fixed ratio of job lengths, the competitiveness of the problem tends towards 1 as the patience is increased. The converse is not true, as for any fixed κ > 0 we find that the competitiveness is bounded away from 1, no matter what further restrictions are placed on the ratio of job lengths.
@cite_12: An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| p j = 1, r j , d j |Σ w j U j . (We assume that r j and d j are integers.)
There is also a large literature of online job scheduling with deadline, for example, @cite_4 , @cite_12 , @cite_3 . A job monopolizes processor for the time it's being scheduled, which maps exactly to packet level scheduling, while in flow level, we must consider multiple flows share bandwidth concurrently, as represented by @math .