Abstract:
An ergonomical pillow to be worn around the waist of a woman, supporting infant in a nursing position. The front pillow ( 10 ) has a front portion and adjacent left and right side portions.  
     The front pillow ( 10 ) has an attaching mean ( 30   a ) attached to the left side and an attaching means ( 30   b ) attached right side of the front pillow ( 10 ).  
     The nursing pillow ( 10 ) further comprises a webbing ( 45 ) with ends connected to the attaching means ( 30   a ) and ( 30   b )  
     A webbing ( 45 ) is laced around users back so that the ends of the webbing are over-passing the distal ends ( 13 ) and ( 13   b ) of the front pillow ( 10 ). The over-passing webbing is keeping distal end ( 13   a ) and ( 13   b ) down when a weight is placed on top of the front portion.  
     The nursing pillow further comprises back support ( 32 ), supporting nursing woman&#39;s back against the seat.

Description:
FIELD OF THE INVENTION  
       [0001]     The following description relates generally to resource allocation, and more specifically to a system and method for allocating, by distributed schedulers, service by distributed resources to competing consumers according to a weighted proportional-share algorithm.  
       DESCRIPTION OF RELATED ART  
       [0002]     Various systems exist in which allocation of resources are managed by a scheduling system. For instance, shares of resources may be allocated, by a scheduler, to various competing consumers (e.g., workloads) in attempt to satisfy performance goals of the consumers. That is, the consumers may be considered as “competing” because they all desire use of the resource, and the scheduler may allocate shares of utilization of such resource among the consumers. The scheduler may use some algorithm for determining an appropriate share of the resource to allocate to each consumer at any given time, such as a weighted proportional-share algorithm described further below. The performance goals of consumers, such as response time bounds and minimum throughput requirements, are typically expressed in the form of Service Level Agreements (SLAs). The performance level achieved by consumers may be controlled by varying the shares of resources available to each consumer. Proportional-share schedulers are known in the art for controlling the shares of resources that are allocated to consumers. Proportional-share schedulers are most commonly implemented using variants of Weighted Fair Queuing (WFQ). The use of WFQ schedulers for meeting SLAs is based on the premise that the performance of a workload varies in a predictable way with the amount of resources available to execute it.  
         [0003]     WFQ schedulers have been used to ensure sharing of a computing resource or “service” (e.g., network link, CPU, file server, data storage, etc.) in proportion to an explicitly specified “weight” for each of the “flows” (or “consumers”) that compete for the resource. In this regard, a “flow” refers to a sequence of tasks (network packets, instructions, I/O requests, etc.) that are using the shared resource(s). Because each flow desires use of the shared resource(s), a flow may be considered as a “resource consumer.” Weights can be assigned to each consumer (e.g., each flow) to define respective priorities for allocating resource access among various competing consumers. Existing WFQ schedulers are “fair” in the sense that active flows share the available resource capacity proportionally to their weights, within some tolerance that is bounded by a constant over any time interval. Depending on the service desired, consumers (e.g., workloads) may compete for either physical resources (CPU cycles, disk I/O, network bandwidth, etc.) or virtual resources (web server bandwidth, database transactions per second, etc.), and the resources may be allocated by a WFQ scheduler to the competing consumers in proportion to the consumers&#39; respective weights.  
         [0004]     There are a number of known methods for performing proportional bandwidth sharing, i.e., maintaining the bandwidth between two backlogged workloads in proportion to their weights. Fair queuing methods, originally developed for network scheduling, are very popular. For example, YFQ, SFQ(D), and FSFQ(D) are scheduling algorithms that are based on start-time fair queuing, and SLEDS is a scheduling algorithm that uses a leaky bucket method. Jin et al. showed that when applying fair queuing algorithms to a storage system, the concurrent service capability of storage devices may result in arbitrary unfairness, and thus they developed SFQ(D) and FSFQ, variations of SFQ, to address this problem, see “Interposed proportional sharing for a storage service utility”,  Proceedings of the International Conference on Measurement and Modeling of Computer Systems  ( SIGMETRICS ), 2004.  
         [0005]     Weighted proportional-share scheduling algorithms, such as those identified above, have been implemented by a centralized scheduler (or “centralized controller”). For instance, there are several projects that aim to provide differentiated service to clients in a storage system with a centralized scheduler, that is, where all the input/output (“IO”) requests pass through some central point, which can then apply the algorithm to schedule service by the requested resource(s). A centralized scheduler can guarantee proportional sharing for each stream based on these priority queues, i.e., in proportion to the weights assigned to the competing streams.  
         [0006]     Such traditional solutions have been insufficient for providing differentiated service to consumers being serviced by distributed resources. For instance, the requirement of a centralized scheduler creates a bottleneck. Thus, schedulers may be implemented for each of the distributed resources. However, while the schedulers may be used in above-described manner to maintain prioritization of service among competing consumers as to the schedulers&#39; respective resource, the overall service provided to the competing consumers by the distributed resources is not maintained “fair” (i.e., in proportion to the competing consumers respective weights). Thus, the plurality of schedulers, while capable of using prior techniques for maintaining prioritization for their respective resources, are unable to maintain overall prioritization in proportion to weights assigned to the competing consumers. For example, suppose a first consumer makes a request for data from a first data storage resource, and the first consumer also makes a request for data from a second data storage resource. Further suppose that a second consumer makes a request for data from the first data storage resource. A first scheduler may be employed for scheduling the service of the requests made to the first data storage resource, and a second scheduler may be employed for scheduling the service of the requests made to the second data storage resource. The first scheduler may employ a weighted proportional-share algorithm for allocating shares of the first data storage resource to the first and second resources according to their respective weights. However, the first consumer, unbeknownst to the first scheduler, is also receiving service from the second data storage resource via the second scheduler. Therefore, the overall service obtained by the first and second consumers is not maintained in proportion to their respective weights by the distributed schedulers.  
         [0007]     A recent paper by A. Gulati and P. Varman (“Lexicographic QoS scheduling for parallel I/O”, in (SPAA), 2005) addresses multiple disks and distributed data. While this paper addresses the optimization problem of minimizing the unfairness among different clients, it proposes a solution that requires a centralized scheduler and the computation cost is undesirably high, which makes this solution impractical and/or unattractive for application to fully distributed high-performance systems. Also “Interposed proportional sharing for a storage service utility”,  Proceedings of the International Conference on Measurement and Modeling of Computer Systems  ( SIGMETRICS ), 2004, Jin et al. propose a decentralized scheduling algorithm, called RequestWindow (“RW”). Although the scheduler in RW is partly distributed, there is a point of centralization because there is only one server issuing windows. Also, RW is not fully work-conserving. In general, when a system is “work-conserving” a resource is never left idle when there is some request waiting that such resource can satisfied (i.e., resource capacity is not “reserved” for consumers that are not requesting use of such resource). Work-conserving is generally a desirable property in distributed high-performance systems.  
         [0008]     In view of the above, a desire exists for an improved solution for providing differentiated service to consumers in a distributed system. That is, a desire exists for a system and method for providing differentiated service to consumers using distributed schedulers, wherein the schedulers manage servicing of requests to maintain an overall proportionality of service between the competing consumers according to weights assigned to such consumers. Of course, the system is preferably work-conserving, whereby the schedulers enforce such proportionality only when capacity of the resources for servicing all of the competing requests is exceeded. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]      FIG. 1  shows an exemplary system according to one embodiment of the present invention;  
         [0010]      FIG. 2  shows another exemplary system according to one embodiment of the present invention;  
         [0011]      FIG. 3  shows an exemplary operational flow according to one embodiment of the present invention;  
         [0012]      FIG. 4  shows an exemplary operational flow according to another embodiment of the present invention;  
         [0013]      FIG. 5  shows an exemplary operational flow according to another embodiment of the present invention;  
         [0014]      FIG. 6  shows an exemplary operational flow for a scheduler in accordance with one embodiment of the present invention;  
         [0015]      FIG. 7  shows an exemplary Federated Array of Bricks (“FAB”) system in which an embodiment of the present invention is be employed;  
         [0016]      FIG. 8  shows an exemplary implementation of the FAB system of  FIG. 7  having n bricks with m streams;  
         [0017]      FIG. 9  shows an exemplary scenario in which streams of requests are received and a delay is added to the start time of certain requests to maintain overall service to the streams in proportion to their respective weights;  
         [0018]      FIG. 10  shows another exemplary scenario for scheduling requests in a FAB system in accordance with one embodiment of the present invention; and  
         [0019]      FIG. 11  shows an exemplary scenario for scheduling requests in a FAB system in which each client accesses multiple coordinators in a round-robin fashion in accordance with one embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0020]     As described further below, systems and methods for providing differentiated service to consumers being serviced by distributed resources are described. More specifically, systems and methods for providing differentiated service to consumers by a plurality of schedulers are described. According to certain embodiments herein, the plurality of schedulers are not required to communicate with each other in order to provide overall differentiated service to consumers in accordance with their respective assigned weights. Thus, efficiency can be enhanced and communication traffic required for implementing the solution is minimized (because the schedulers are not required to communicate with each other).  
         [0021]     In certain embodiments, a solution for scheduling requests in a distributed storage system that guarantees each client service proportional to its assigned weight is provided, wherein the clients can access the data through one or more coordinators and the data may be distributed, without requiring communication between schedulers or coordinators. Of course, as described further herein, application of embodiments of the present invention is not limited to distributed storage systems, but may likewise be applied to systems having any resources for servicing consumers. For instance, depending on the service desired, consumers may compete for either physical distributed resources (CPU cycles, disk I/O, network bandwidth, etc.) or virtual distributed resources (web server bandwidth, database transactions per second, etc.), and embodiments of the present invention may be employed for efficiently scheduling service by the resources to competing consumers based on the consumers&#39; respective weights.  
         [0022]      FIG. 1  shows an exemplary system  100  according to one embodiment of the present invention. System  100  comprises consumers  10 A and  10 B, coordinators  11 A and  11 B, schedulers  12 A and  12 B, and resources  14 A and  14 B. Schedulers  12 A and  12 B comprise weighted proportional-share algorithms  13 A and  13 B, respectively. While this exemplary system  100  shows two consumers, two coordinators, two schedulers, and two resources, this is merely intended as a simple example for ease of illustration and discussion. Embodiments of the present invention are not limited in this regard, but may be applied to systems having any number of consumers, coordinators, schedulers, and resources. Further, while the number of consumers, coordinators, schedulers, and resources are all the same in the exemplary system  100  of  FIG. 1  (i.e., two of each), in other embodiments different numbers of one or more (e.g., all) of these components may be employed in a given system. For instance, the number of consumers may differ from the number of coordinators, which may in turn differ from the number of schedulers, etc. that are implemented in a system.  
         [0023]     Consumers  10 A and  10 B may be any entity in a system that is capable of requesting service by a resource, such as any process or flow, as examples. Resources  14 A and  14 B may comprise any resources that are accessible for servicing requests from consumers  10 A and  10 B. In certain embodiments, resources  14 A and  14 B are data storage resources, but they are not so limited. For instance, resources  14 A and  14 B may be computing resources (e.g., CPUs), network resources (e.g., network links), web servers, etc.  
         [0024]     Coordinators  11 A and  11 B coordinate which one or more of resources  14 A and  14 B are to be used for servicing a given consumer request. For instance, in one embodiment, consumers  10 A and  10 B need not specify which ones of the plurality of resources  14 A and  14 B are to service the consumer&#39;s request, and in certain embodiments the consumers  10 A and  10 B may not even be aware of which of the plurality of resources  14 A and  14 B is capable of servicing its request. Further, in certain embodiments, consumers  10 A and  10 B may not even be aware that a plurality of resources  14 A and  14 B and/or a plurality of schedulers  12 A and  12 B exist, but rather coordinators  11 A and  11 B may make provide an appearance to the consumers  10 A and  10 B that a single resource with a corresponding scheduler exists.  
         [0025]     Schedulers  12 A and  12 B schedule service by their respective resources  14 A and  14 B for servicing the consumers&#39; requests. As described further herein, such schedulers  12 A and  12 B use weighted proportional-share algorithms  13 A and  13 B for scheduling service such that service is provided proportionally to weights assigned to the competing consumers. This proportionality is maintained for the total service that is provided to the consumers across the plurality of resources  14 A and  14 B. Thus, the schedulers do not simply maintain proportionality of service that is provided by their respective resource (i.e., “local proportionality”), but rather each scheduler manages the service provided by its respective resource such that overall proportionality (i.e., “global proportionality”) of service is maintained in accordance with the weights assigned to the competing consumers. In one embodiment, the weighted proportional share algorithms  13 A and  13 B implement the DSFQ algorithm described further herein. Further, any of a plurality of different variants of the DSFQ algorithm may be employed, including without limitation the below described T OTAL -DSFQ, S TRIPE -DSFQ, and Hybrid-DSFQ algorithms.  
         [0026]     As described further herein, in certain embodiments, the plurality of schedulers  12 A and  12 B are capable of maintaining the total service that is provided to the consumers in proportion to the consumers&#39; respective weights without requiring that the schedulers  12 A and  12 B communicate with each other. For instance, in certain embodiments, coordinators  11 A and  11 B communicate sufficient information to the schedulers regarding the overall requests for service that have been made for each consumer such that the schedulers can allocate the overall service by the resources  14 A and  14 B in proportion to the weights assigned to the consumers. Of course, the system  100  is preferably work-conserving, whereby the schedulers  12 A and  12 B enforce such proportionality only when capacity of the resources  14 A and/or  14 B for servicing all of the competing requests is exceeded.  
         [0027]      FIG. 1  illustrates an exemplary scenario where consumer  10 A communicates a request for service to coordinator  11 A, and consumer  10 B communicates a request for service to coordinator  11 B. Coordinator  11 A determines that consumer  10 A&#39;s request requires service by resources  14 A and  14 B, while coordinator  11 B determines that consumer  10 B&#39;s request requires service only by resource  14 B. Thus, because consumer  10 A&#39;s request is determined as requiring service by both resources  14 A and  14 B, coordinator  11 A sends a request for the service required for consumer  10 A to schedulers  12 A and  12 B. As shown, coordinator  11 A communicates request  101   1  to scheduler  12 A requesting service by resource  14 A to consumer  10 A, and coordinator  11 A communicates request  101   2  to scheduler  12 B requesting service by resource  14 B to consumer  10 A. Coordinator  11 B communicates request  102  to scheduler  12 B requesting service by resource  14 B to consumer  10 B.  
         [0028]     As described further herein, in certain embodiments of the present invention, the coordinators also communicate sufficient information to the schedulers regarding the overall requests for service that have been made for each consumer such that the schedulers can allocate the overall service by the resources  14 A and  14 B in proportion to the weights assigned to the consumers. For instance, in one embodiment, communication  101   1  includes information informing scheduler  12 A of the amount of service requested by coordinator  11 A from resource  14 B (via the request  101   2  made to scheduler  12 B). Likewise, communication  101   2  includes information informing scheduler  12 B of the amount of service requested by coordinator  11 A from resource  14 A (via the request  101   1  made to scheduler  12 A). Thus, schedulers  12 A and,  12 B are aware of the amount of service requested for a given consumer across the plurality of resources  14 A and  14 B. Further, the schedulers  12 A and  12 B are not required to communicate with each other in order to gain this information. Further still, in this example, the coordinators  11 A and  11 B are not required to communicate with each other. As described further herein, the weighted proportional-share algorithms  13 A and  13 B are operable to use this received information for maintaining the service provided by the plurality of distributed resources  14 A and  14 B proportional to the weights assigned to the competing consumers  10 A and  10 B. For instance, in one embodiment, a delay value is included in the information sent to a scheduler, where such delay value corresponds to the amount of service requested for the consumer from other scheduler(s). Thus, in this embodiment, the weighted proportional-share algorithm of each scheduler utilizes the received delay value in determining its allocation of service from its respective resource to the requesting consumer. As described further herein, the delay may indicate the amount of service requested by the coordinator for the consumer from other schedulers (e.g., as in the below-described T OTAL -DSFQ algorithm), an extrapolated proportion of service requested for this consumer from this scheduler relative to that requested for this consumer from other schedulers (e.g., as in the below-described S TRIPE -DSFQ algorithm), or the delay may be determined by the coordinator as in the below-described Hybrid-DSFQ algorithm, as examples.  
         [0029]     Turning to  FIG. 2 , another exemplary system according to one embodiment of the present invention is shown. System  200  provides an example in which the distributed resources are data storage resources  20 A and  20 B. Such data storage resources may comprise any suitable data storage devices now known or later discovered that are operable for storing digital information, including without limitation hard disks, optical disk drives, tape drives, magnetic data storage drives, databases, file servers, memory, etc. Further, the data storage resources  20 A and  20 B need not be the same type in certain embodiments (e.g., data storage resource  20 A may be a hard disk, while data storage resource  20 B may be an optical disk drive).  
         [0030]      FIG. 2  illustrates an exemplary scenario where consumer  10 A communicates a request for service to coordinator  11 A, and consumer  10 B communicates a request for service to coordinator  1 B. In this example, consumers  10 A and  10 B each requests access to data. Coordinator  11 A determines that consumer  10 A&#39;s request requires service by data storage resources  20 A and  20 B. That is, coordinator  11 A determines that consumer  10 A is requesting data  21   1  and  21   2 , which are stored to data storage resources  20 A and  20 B, respectively. Coordinator  11 B determines that consumer  10 B&#39;s request requires service only by resource  14 B. That is, coordinator  11 B determines that consumer  10 B is requesting data  22  that is stored to data storage resource  20 B.  
         [0031]     Thus, because consumer  10 A&#39;s request is determined as requiring data to be served by both data storage resources  20 A and  20 B, coordinator  11 A sends a request for the service required for consumer  10 A to schedulers  12 A and  12 B. As shown, coordinator  11 A communicates request  201   1  to scheduler  12 A requesting data  21   1  from data storage resource  20 A to be served to consumer  10 A, and coordinator  11 A communicates request  201   2  to scheduler  12 B requesting data  21   2  from data storage resource  20 B to be served to consumer  10 A. Coordinator  11 B communicates request  202  to scheduler  12 B requesting data  22  from data storage resource  20 B to be served to consumer  10 B.  
         [0032]     As described further herein, in certain embodiments of the present invention, the coordinators also communicate information to the schedulers indicating a delay that corresponds in some way to service requested by such coordinators for a given consumer from the other schedulers. For instance, in one embodiment, communication  201   1  includes information informing scheduler  12 A of the request  201   2  for data  21   2  made by coordinator  11 A to data storage resource  20 B for consumer  10 A. Likewise, communication  201   2  includes information informing scheduler  12 B of the request  201   1  for data  21  made by coordinator  11 A to data storage resource  20 A for consumer  10 A. Thus, schedulers  12 A and  12 B are aware of the amount of service requested for a given consumer across the plurality of data storage resources  20 A and  20 B. As described farther herein, the weighted proportional-share algorithms  13 A and  13 B are operable to use this received information for maintaining the service provided by the plurality of distributed data storage resources  20 A and  20 B proportional to the weights assigned to the competing consumers  10 A and  10 B. Again, in certain embodiments a delay value is included in the information provided from a coordinator to a scheduler, wherein the delay value corresponds to the service requested by such coordinator for the consumer from other scheduler(s).  
         [0033]     Turning to  FIG. 3 , an exemplary operational flow according to one embodiment of the present invention is shown. In operational block  301 , a first weight is assigned to a first consumer, and a second weight is assigned to a second consumer. In block  302 , a first scheduler receives a request for service by a first resource to a first consumer. For instance, in the example of  FIG. 1 , scheduler  12 A receives (from coordinator  11 A) a request for service by resource  14 A to consumer  10 A. In block  303 , a second scheduler receives a request for service by a second resource to the first consumer. For instance, in the example of  FIG. 1 , scheduler  12 B receives (from coordinator  11 A) a request for service by resource  14 B to consumer  10 A. In block  304 , the first scheduler receives a request for service by the first resource to the second consumer. In block  305 , the first and second schedulers schedule service from the first and second resources to the first and second consumers. The scheduling of block  305  maintains total service provided by the first and second resources to the first and second consumers in proportion to the respective weights of the first and second consumers, without requiring the first and second schedulers to communicate with each other.  
         [0034]     Turning to  FIG. 4 , an exemplary operational flow according to another embodiment of the present invention is shown. In operational block  41 , a first weight is assigned to a first consumer, and a second weight is assigned to a second consumer. In block  42 , a first coordinator receives a request from the first consumer for service. In block  43 , the first coordinator determines at least one of a plurality of resources for providing the requested service to the first consumer. In block  44 , a second coordinator receives a request from the second consumer for service. In block  45 , the second coordinator determines at least one of the plurality of resources for providing the requested service to the second consumer. In block  46 , overall service by the at least one resource is scheduled for the first and second consumers in proportion to the respective weights of the first and second consumers without requiring the first and second coordinators to communicate with each other.  
         [0035]     As described further herein, the resource used for servicing the consumers may comprise a plurality of distributed resources, such as the plurality of distributed data storage resources  20 A and  20 B shown in the exemplary system of  FIG. 2 . Thus, according to certain embodiments of the present invention, proportionality can be maintained for servicing consumers without requiring that coordinators communicate with each other. As described further herein, in certain embodiments, a plurality of schedulers are also employed, wherein the schedulers schedule service in a manner that enforces the proportionality of weights assigned to the competing consumers. Further, such schedulers are not required to communicate with each other in order to enforce such proportionality.  
         [0036]      FIG. 5  shows an exemplary operational flow according to another embodiment of the present invention. In operational block  51 , a plurality of coordinators are employed for enabling access to at least one of a plurality of resources for servicing requests from consumers, such as coordinators  11 A and  11 B for servicing requests from consumers  10 A and  10 B in the example of  FIG. 1 . In block  52 , a weighted proportional-share scheduler is employed for each of said plurality of resources, such as schedulers  12 A and  12 B for resources  14 A and  14 B in the example of  FIG. 1 . In block  53 , a coordinator receives a request from a consumer for service. In block  54 , the coordinator determines one or more of the plurality of resources to be accessed for servicing the received request. For instance, in the example of  FIG. 1 , coordinator  11 A receives a request for service from consumer  10 A, and coordinator  11 A determines that resources  14 A and  14 B are to be accessed for servicing consumer  10 A&#39;s request. In block  55 , the coordinator communicates to the corresponding scheduler of each of the resources to be used, a request for service and information indicating an amount of service requested by the coordinator from others of the plurality of schedulers for servicing the received request. Such information that indicates an “amount” of service requested from other schedulers may be an actual amount of service requested (as in the T OTAL -DSFQ algorithm), it may be an extrapolated amount (as in the S TRIPE -DSFQ algorithm) or it may be some other amount that corresponds in some way to the amount of service requested for this consumer from other schedulers. For instance, in the example of  FIG. 1 , coordinator  11 A communicates  101   1  a request to scheduler  12 A for service by resource  14 A, which includes information notifying scheduler  12 A of the requested service made by communication  101   2  from coordinator  11 A to scheduler  12 B for service by resource  14 B. In block  56 , the corresponding scheduler of each of the one or more resources determined to be accessed allocates an amount of service based on the information indicating the amount of service requested by the coordinator from others of the plurality of resources for servicing the received request.  
         [0037]     Accordingly, in certain embodiments, distributed schedulers provide service to consumers in accordance with a weighted proportional-share scheduling algorithm.  FIG. 6  shows an exemplary operational flow for a scheduler in accordance with one embodiment of the present invention. In operational block  61 , a plurality of weighted proportional-share schedulers are employed, where each of the schedulers is associated with a respective one of a plurality of distributed resources. In block  62 , a first of the schedulers receives a request for service to a consumer by the first scheduler&#39;s respective resource. In block  63 , a second of the schedulers receives a request for service to the consumer by the second scheduler&#39;s respective resource. For instance, in the example illustrated in  FIG. 1 , scheduler  12 A receives (from coordinator  11 A) a request for service to be provided by its resource  14 A to consumer  10 A, while scheduler  12 B receives (from coordinator  11 B) a request for service to be provided by its resource  14 B to consumer  10 A.  
         [0038]     In block  64 , the first scheduler receives information indicating an amount of service requested by the consumer from the second scheduler, and in block  65 , the second scheduler receives information indicating an amount of service requested by the consumer from the first scheduler. Again, this information indicating an amount may provide an actual amount, an extrapolated amount, or other amount that in some way corresponds to the service requeted for the consumer. For instance, in the example of  FIG. 1 , scheduler  12 A receives information  101   1  that indicates an amount of service requested (via request  101   2 ) from scheduler  12 B for servicing consumer  10 A. Likewise, scheduler  12 B receives information  101   2  that indicates an amount of service requested (via request  101   1 ) from scheduler  12 A for servicing consumer  10 A. In block  66 , the first and second schedulers use a weighted proportional-share algorithm for scheduling service for the consumer using the received information such that the total service provided by the respective resources of the first and second schedulers is governed by the weighted proportional-share algorithm.  
         [0039]     As discussed above, schedulers  12 A and  12 B utilize weighted proportional-share scheduling algorithms  13 A and  13 B, respectively. According to one embodiment, such algorithm is an adaptation of the known Start-time Fair Queuing (SFQ) algorithm. For instance, in one embodiment, the scheduling algorithm enforces an extra delay on scheduling each request. Different performance guarantees can be met by different delay functions. The delay functions can be calculated at coordinators locally so communication among schedulers is avoided.  
         [0040]     Before discussing exemplary embodiments of the present invention further, it is helpful to provide a brief description of traditional weighted proportional-share scheduling algorithms, such as SFQ(D). In SFQ(D) (as in SFQ) each job or IO request is assigned a Start-time tag and a Finish-time tag, and there is a global virtual time that is initially set to zero. The Start-time of each request is set to the virtual-time at its arrival or the finish-time tag of the previous job from this client, whichever is larger. The finish time tag of each request is set to the start time plus the cost of the request (say, its size in bytes if we are trying to do a proportional sharing of the bandwidth (bytes/second) received by each client) divided by the weight assigned to the client. Virtual time is set to be the start-time tag of the request in service. At the end of each request, the request with the smallest start-time tag is added to the execution queue. If requests from all clients pass through this controller, it is guaranteed that the service they receive will be in proportion to their weights so long as there are enough requests to serve from each client. Fair queuing algorithms are discussed further hereafter.  
         [0041]     According to one embodiment of the present invention, a scheduling algorithm (e.g., the DSFQ algorithm described further below) is proposed. This algorithm is based on fair queuing, which refers to a class of scheduling algorithms to allocate resources among competing consumers. Many variants of fair queuing exist for different purposes. Consider the following: each stream f has a sequence of requests p f   0  . . . p f   i  arriving at the server. A request p f   i  has an associated cost c f   i . For example, if bandwidth sharing is the interest, the cost might be the size of the package; and if the interest is the scheduling of CPU time, the predicted service time of a request might be a good choice for the cost. Fair queuing allocates the capacity of the resource in proportion to weights assigned to the competing consumers.  
         [0042]     A stream is considered “active” if it has one or more requests in process or queued. The stream is considered “backlogged” if it has requests queued. Fair queuing algorithms are work-conserving, i.e. there are no surplus resources if some stream is backlogged.  
         [0043]     Formally, if W f (t 1 ,t 2 ) is the aggregate cost of the requests from stream f served in the time interval [t 1 ,t 2 ], then a fair scheduling algorithm guarantees that:  
                          W   f     ⁡     (       t   1     ,     t   2       )         ϕ   f       -         W   g     ⁡     (       t   1     ,     t   2       )         ϕ   g              ≤     H     f   ,   g               (   1   )             
 
 where f and g are any two streams continuously backlogged with requests during [t 1 ,t 2 ], and H f,g  is a constant that depends on the stream and system characteristics, e.g., maximum cost c f   max  of a request. φ f  and φ g  refer to the weights assigned to streams f and g, respectively. 
 
         [0044]     Depending on how the cost is defined in a given system, predicting it may be difficult. It should be understood, however, that known techniques exist for determining such cost, and any technique now known or later discovered may be used in accordance with embodiments of the present invention. For example, the cost of a storage service request may be affected by cache hits, disk scheduling, sequential/random access, etc. This feature of storage service requests narrows the choice of fair queuing algorithms or other scheduling algorithms.  
         [0045]     The Virtual Clock (VC) algorithm is a known fair queuing algorithm, which works as follows. Each stream or workload f maintains a Virtual Clock VC f . Initially, VC f  equals the real time. When the j th  request p f   j  of stream f arrives, VC f  is updated as follows:  
               VC   f     ←       VC   f     +       c   f   j       ϕ   f                 (   2   )             
 
 where c f   j  is the cost of request p f   j  to be served (assume it is proportional to the service time), and φ f  is the weight assigned to stream f. Every request of a stream is stamped with its current VC value and the server serves requests in the order of increasing stamp values. 
 
         [0046]     If the VC f  lags behind the real time because stream f is inactive, the VC algorithm synchronizes VC with the real time. If two streams f and g start with the same VC value, the VC algorithm guarantees proportional sharing according to formula (1) above between f and g as long as they are both backlogged. However, if g is temporarily inactive and f is served faster, VC f  can be arbitrarily ahead of the real time and f cannot receive any service later on when g becomes active again. So, a drawback of the VC algorithm for certain systems is that a stream is punished heavily for consuming idle resource, resulting in unfairness.  
         [0047]     Start-time Fair Queuing (SFQ) is another known fair queuing algorithm, which overcomes the above problem of the VC algorithm by synchronizing the virtual clock at each stream, i.e., there is only one global virtual clock, called Virtual Time v(t). Formally, SFQ works as follows. It assigns two tags for every request: when the j th  request p f   j  of stream f arrives, it is assigned a start tag S(p f   j ) and a finish tag F(p f   j ). The tag values represent the time at which each request should start and complete according to a system notion of virtual time v(t). Virtual time always advances monotonically and is approximately equal to real time under ideal conditions: all streams are backlogged, the server completes work at a fixed ideal rate, request costs are accurate, and the weights sum to the service capacity. In practice, virtual time may diverge arbitrarily from real time without compromising fairness if the scheduler dispatches requests in virtual time order. For example, v(t) advances faster than real time whenever surplus resources allow the active streams to receive service at a faster rate than their configured shares would allow.  
         [0048]     SFQ assigns tags as follows:  
                 S   (     p   f   j     )     =     max   ⁢     {       v   (     A   (     p   f   j     )     )     ,     F   (     p   f     j   -   1       )       }         ,     j   ≥   1             (   3   )                   F   (     p   f   j     )     =       S   (     p   f   j     )     +       c   f   j       ϕ   f           ,     j   ≥   1             (   4   )             
 
 where A(p f   j ) is the actual arrival time of request p f   j , F(p f   0 )=0, v(0)=0. Again, φ f  is the weight assigned to stream f. During a busy period, v(t) is defined to be equal to the start tag of the request in service at time t. When the server is idle, v(t) is defined to be equal to the maximum finish tag of any request that has been serviced by time t. A key advantage of SFQ is that it determines v(t) efficiently. 
 
         [0049]     The following theorem has been derived for SFQ: 
    Theorem 1 For any interval [t 1 ,t 2 ] in which streams f and g are backlogged during the entire interval.  
                          W   f     ⁡     (       t   1     ,     t   2       )         ϕ   f       -         W   g     ⁡     (       t   1     ,     t   2       )         ϕ   g              ≤         c   f   max       ϕ   g       +       c   g   max       ϕ   g                 (   5   )             
     where W f (t 1 ,t 2 ) is the aggregate cost of requests served from stream f in the interval [t 1 ,t 2 ].    
 
         [0052]     SFQ and other fair queuing algorithms are similar to the VC algorithm in that the request tags for each stream advance according to the progress of that stream. The start tag of the stream&#39;s most recent request may be viewed as the stream&#39;s virtual clock. Flows with smaller tag values are “behind” and receive priority for service; streams with larger tag values are “ahead” and may be penalized. However, unlike the VC algorithm, the tag values of newly active streams advance to the global virtual clock v(t) in the SFQ algorithm, so that their newly arriving requests compete fairly with other active streams. This avoids unfairly penalizing active streams for consuming surplus resources left idle by inactive streams.  
         [0053]     If there is no global Virtual Time v(t), SFQ degrades to the VC algorithm, which can be arbitrarily unfair. However, the idea of maintaining locally at each stream may be preferable in a distributed system, where global synchronization of virtual time is impossible or computationally expensive.  
         [0054]     Another fair queuing algorithm that is known is SFQ(D), which guarantees proportional sharing of the service with a bound that is a function of the queue depth D. SFQ(D) is described further below. SFQ is attractive to performance guarantees in storage systems in part because it is fair even with fluctuating service capacity. However, the virtual time v(t) is not well- defined in this setting because of internal concurrency of storage servers, i.e., it may have multiple requests in service simultaneously in order to maximize the utilization of disks. Jin et al. pointed out (in “Interposed proportional sharing for a storage service utility”, in  Proceedings of the International Conference on Measurement and Modeling of Computer Systems  ( SIGMETRICS ), 2004) that if v(t) is defined to be equal to the minimum start tag of requests in service (Min-SFQ), it can be arbitrarily unfair. The reason is that an active stream may hold back the virtual time v(t) if it generates an insufficient number of concurrent requests to consume its assigned share.  
         [0055]     Instead, one can define the virtual time as the start-time tag of the last request dispatched to the disk, i.e., the queued request with the lowest start tag at the time of the last dispatch. Arriving requests are assigned start and finish tags according to Equations (3) and (4) above. The resulting algorithm is known as depth-controlled start-time fair queuing (SFQ(D)), a variation of SFQ. D here means the queue depth at the server, i.e., number of outstanding requests. The fairness guarantee of SFQ(D) is proved by the following theorem: 
    Theorem 2 During any interval [t 1 ,t 2 ], the difference between the amount of work completed by an SFQ(D) server for two backlogged streams f and g is bounded by:  
                          W   f     ⁡     (       t   1     ,     t   2       )         ϕ   f       -         W   g     ⁡     (       t   1     ,     t   2       )         ϕ   g              ≤       (     D   +   1     )     *     (         c   f   max       ϕ   f       +       c   g   max       ϕ   g         )               (   6   )             
   
 
         [0057]     A more complicated algorithm, called FSFQ(D), is presented by Jin et al. in “Interposed proportional sharing for a storage service utility”,  Proceedings of the International Conference on Measurement and Modeling of Computer Systems  ( SIGMETRICS ), 2004, the disclosure of which is hereby incorporated herein by reference. One embodiment of a scheduling algorithm used in the present invention is described below as based on the SFQ(D) algorithm. However, in other embodiments, such scheduling algorithm may instead be based on another fair queuing algorithm now known or later developed, including without limitation the FSFQ(D) algorithm.  
         [0058]     According to one embodiment, a weighted proportional-share scheduling algorithm referred to as DSFQ is employed by the schedulers. DSFQ is an extension of the SFQ(D) algorithm that has been proposed for a centralized controller. DSFQ is described further hereafter with reference to an exemplary distributed storage system, shown in  FIG. 7 . Of course, it should be understood that reference to such distributed storage system is merely for ease of discussion, and application of the DSFQ scheduling algorithm is not limited to the exemplary system of  FIG. 7  but may likewise be applied to other systems for scheduling resources (which may be resources other than data storage resources). Before describing the DSFQ algorithm, the exemplary distributed storage system  700  of  FIG. 7  is briefly described.  
         [0059]     One embodiment of the present invention is employed for use on a Federated Array of Bricks (FAB). The FAB system is generally built from commodity hardware. It utilizes a number of individual storage nodes, or “bricks,” to present a single, highly-available, storage store. An exemplary FAB system  700  is shown in  FIG. 7 . Such FAB system  700  is an example of a distributed storage system. System  700  comprises symmetrical bricks  70 A,  70 B, and  70 C. Each brick may run the same set of software modules and manage the same types of data structures. In the example of  FIG. 7 , bricks  70 A,  70 B, and  70 C comprise data storage  20 A,  20 B, and  20 C, respectively. Further, bricks  70 A,  70 B, and  70 C comprise schedulers  12 A,  12 B, and  12 C, respectively, which schedule service to requests by their respective data storage. Clients  10 A,  10 B, and  10 C are operable to request service by submitting requests to coordinators  11 A,  11 B, and  11 C. In certain embodiments, each client may always submit requests via a single coordinator. It is not necessary that each client use a different coordinator from all other clients, but certain systems may be implemented such that each client always makes requests for service to one coordinator. For instance, client  10 A may submit all of its requests to coordinator  11 A, client  10 B may submit all of its requests to coordinator  11 B, and client  11 C may likewise submit all of its requests to coordinator  11 B. As discussed further herein, in certain embodiments, each client may submit requests to any of the coordinators  11 A- 11 C, and may submit different requests to different ones of the coordinators.  
         [0060]     While the coordinators  11 A- 11 C are shown in this example as being external to bricks  70 A- 70 C, in certain embodiments a brick may act both as a storage center and a coordinator, i.e., a gateway for the request. In other words, in certain embodiments, coordinators  11 A- 11 C may be implemented on bricks  70 A- 70 C, respectively. In this exemplary architecture of system  700 , different requests, even from the same client, can be coordinated by different bricks. It should be recognized that in this exemplary system  700  coordinators  11 A- 11 C are distributed. A coordinator schedules requests possibly without the knowledge of requests sent to other coordinators. Also, the data is distributed. A logical volume in a distributed storage system might be replicated or erasure-coded across many bricks. Requests from a client could possibly spread on different bricks. An embodiment of the present invention provides a distributed scheduler framework that can provide service guarantees regardless of the data layout.  
         [0061]     According to this exemplary embodiment, a distributed proportional sharing algorithm (e.g., the DSFQ algorithm described below) is utilized by the schedulers. With proportional sharing, the system reserves for each flow some specified minimum share of the server&#39;s capacity to handle requests, encoded as a weight. Surplus resources are shared among active flows in proportion to their shares. The service capacity to be proportionally shared could be throughput or service time, as examples. Taking into account that the data is distributed, the algorithm of this exemplary embodiment allows total service capacity proportional sharing, local brick proportional sharing, or mixed sharing.  
         [0062]     Thus, the scheduling algorithms are employed on distributed schedulers in this architecture, rather than utilizing a centralized scheduler. The data assessed by the clients is distributed over some number of back-end storage servers (bricks); each client accesses the data through some number of coordinators that know where the data is stored and can retrieve the data for the request on behalf of the client. However, if the back-end bricks were to schedule the requests using the standard SFQ(D) scheduler, it would not take into account the service that the flow receives at other bricks, and this would result in sharing the local resources proportionately, rather than total proportional sharing.  FIG. 9  shows that in order to achieve total proportional resource sharing between streams f ( 901 ) and g ( 902 ), where stream g receives service from bricks A and B, the scheduler  12 A for brick A ( 70 A) adds an extra delay to the start time of requests from stream g corresponding to the amount of service g has received from brick B, as shown in the resulting stream  903  for Brick A. In this exemplary embodiment, the coordinator computes a delay for each request based on its cost and on other information it has, and passes it to the brick along with the request.  
         [0063]     In one embodiment, each back-end brick runs an SFQ(D) scheduler (e.g., schedulers  12 A- 12 C in  FIG. 7 ) for the requests it serves, but adds the supplied delay to the finish-time tag of the previous request from this client in computing the start-time tag. An example of this is illustrated in  FIG. 10 , where coordinator  11 A receives requests  1001  from flow f, and coordinator  11 B receives requests  1002  from flow g. Coordinator  11 A computes the delay for each request from flow f, resulting in the requests with accompanying delay information  1003  for flow f, which is communicated to scheduler  12 A of brick  70 A. Coordinator  11 B computes the delay for each request from flow g, resulting in the requests with accompanying delay information  1004  for flow g, which is communicated to scheduler  12 A of brick  70 A. As shown in  FIG. 10 , this can be thought of as adding to the stream of requests sent to brick A all the requests sent to brick B as well; these additional requests would act as “virtual requests” at brick A, consuming no resources but taken into account for the scheduling of the requests actually intended for brick A.  
         [0064]     In one embodiment, each of the schedulers  12 A- 12 C are running the DSFQ algorithm, which is now described with reference to  FIG. 8 .  FIG. 8  shows an exemplary implementation of the FAB system  700  of  FIG. 7 , wherein there are n bricks B 1 , B 2 , . . . , B n  and m clients or streams f 1 , f 2 , . . . , f m . In this example, brick B 1  is shown as brick  70 A of  FIG. 7 , and brick B n  is shown as brick  70 B of  FIG. 7 . Each back-end brick has m queues for the m streams. The scheduler (e.g., scheduler  12 A of brick  70 A) dispatches requests to the brick&#39;s data storage resource (e.g., disk) in the order of some priority, e.g., start-time tag in the case of SFQ. Each coordinator has mn FIFO queues, one for every (stream, brick) pair. The coordinator dispatches a request in queue f i,j  to queue f i  at brick B j  immediately once f i  has an empty spot.  
         [0065]     It can be seen that if SFQ(D) is implemented at each scheduler of this architecture, it guarantees individual brick proportional sharing. In terms of total service proportional sharing, a brick has to discount the service rate of a stream that is requesting service at other bricks simultaneously. This concept can be integrated into the SFQ algorithm with a delay function that delays the start-time tag of a request, as discussed below.  
         [0066]     If the ith request of stream f, p f   i  is serviced at brick A, and it is the jth request of f on A, rename it as p f,A   j . The cost of request p f,A   j , denoted as c f,A   j , is the same as c f   j . The back-end (e.g., brick or scheduler of a brick) maintains a Virtual Time v(t) and a Start-time Fair Queue. The Distributed Start-time Fair Queuing (DSFQ) algorithm is summarized as follows:  
               S   (     p     f   ,   A     j     )     =     max   ⁢     {         v   A     (     A   (     p     f   ,   A     j     )     )     ,     
     ⁢       F   (     p     f   ,   A       j   -   1       )     +       Delay   (     p     f   ,   A     j     )       ϕ   f           }               (   7   )                 F   (     p     f   ,   A     j     )     =       S   (     p     f   ,   A     j     )     +       c     f   ,   A     j       ϕ   f                 (   8   )             
 
 where A(p f,A   j ) is the actual arrival time at the scheduler for brick A of request p f,A   j , F(p f,A   0 )=0, v A (0)=0. Again, φ f  is the weight assigned to stream f. In this embodiment, each brick&#39;s scheduler dispatches requests in increasing order by their start-time tags. v A (t) is defined to be equal to the start-time tag of the last request dispatched to the data storage resource (e.g., disk) before or at a time t. It should be noted that this is the same as SFQ(D). v(t) is not defined in SFQ when the server has concurrent service capability. However, we refer to the above embodiment of the distributed scheduling algorithm as DSFQ instead of DSFQ(D) for simplicity. If the delay function is always zero, DSFQ degenerates to SFQ(D). 
 
         [0067]     Depending upon how the coordinator computes the delay, different proportionality properties can be enforced. Let us first assume requests from one stream is always processed by a fixed coordinator. Different streams may have different coordinators and a stream may request service at different bricks simultaneously. The performance goal is that the total amount of service each client receives should be proportional to the client&#39;s respective weight.  
         [0068]     If p f   i  is the ith request of stream f and is the jth request of stream f that requests service on brick A, function index(p f,A   j ) returns i as p f,A   j &#39;s global index of stream f. The delay function that guarantees total service proportional sharing is as follows.  
               Delay   (     p     f   ,   A     j     )     =       ∑     i   =       index   (     p     f   ,   A       j   -   1       )     +   1           index   (     p     f   ,   A     j     )     -   1       ⁢           ⁢     c   f   i               (   9   )             
 
 The exemplary scheduling algorithm defined by formulae (7-9) is a distributed start-time fair queuing algorithm with respect to total service capacity, called T OTAL -DSFQ. 
 
         [0069]     The delay function (9) provides that the amount of delay at one brick equals the total service cost of requests sent to other bricks since the last request on this brick. Thus, a request on brick A should be delayed by a duration proportional to the service its stream is receiving on other bricks.  
         [0070]     In the above discussion of the exemplary DSFQ algorithm, we have assumed that a stream requests service through one coordinator only. This is not true in some high-end storage systems, where concurrency at the coordinator level is necessary for high performance. Thus, as discussed below, certain embodiments of the present invention allow for a single-client multi-coordinator setting. As discussed further below, the above-described DSFQ algorithm works for maintaining sufficient fairness when the client&#39;s access the multiple coordinators in some regular fashion, such as a round-robin sequence of accesses, as opposed to accessing them in an arbitrary or random fashion.  
         [0071]     First, let us assume that each client accesses multiple coordinators in a round-robin fashion, and let us examine the effect of delay function (9) under this setting.  FIG. 11  is an example.  FIG. 11  shows an exemplary stream f  1101 , which makes requests to bricks A-E in the order shown. Supposing each request has unit cost, with one coordinator, delay of the four requests to brick A are 9, 2, 2 and 0, as shown in stream  1102 . With two round-robin coordinators on the other hand, delay of two requests dispatched by one coordinator is 0 and 2, delay of the other two requests dispatched by another coordinator is 1 and 1, as shown by streams  1103 . Therefore, delay of individual requests has changed, but the total amount remains the same. If we reorder the virtual stream as stream  1104  of  FIG. 11 , at brick A, the requests received from two coordinators look exactly the same as the reordered virtual stream dispatched by one coordinator.  
         [0072]     Definition: A sequence of requests is R-balanced with respect to brick A if and only if the total cost of requests between any two consecutive requests to A is at most R.  
         [0073]     A synchronous stream, i.e., a new request waits until requests to other bricks are processed, is R-balanced. An asynchronous stream may not be R-balanced, such as stream g in Example 1. It is worth noting that for an asynchronous stream, a coordinator may not be able to dispatch requests in their arriving order, unless the back-end has infinite queue depth. With a finite queue depth, the coordinator may have to hold requests whose destination brick has a full queue.  
         [0074]     As can be seen from the above example of  FIG. 11 , multi-coordinator is just a matter of reordering streams. If in the request sequence each coordinator receives, the amount of requests between two consecutive requests to one brick is bounded, the reordered stream is R-balanced. T OTAL -DSFQ still works in this case.  
         [0075]     On the other hand, if a client deliberately sends same-destination requests through one coordinator only, the reordered steam is not R-balanced and these requests all have zero delay. Therefore, the algorithm is no longer fair. In this case, communication among coordinators might be necessary to prevent malicious clients from overusing services.  
         [0076]     Even the above extreme case is left out, it is difficult to guarantee an absolute bound on the balance after reordering. We seek statistical results instead, in this exemplary embodiment. The problem is formulated as follows. In the original stream, the number of requests between two consecutive requests to brick A is an independent, identically distributed random variable X, with expectation E(X) and variance Var(X). There are k coordinators C l  . . . C k . The scheduling of requests is a mapping from an individual request to the k coordinators. Coordinator C i  would receive a sequence of requests, let the number of requests between two consecutive requests to A be another random variable Y i  with expectation E(Y i ) and variance Var(Y i ). 
    Theorem 3: If requests are independently mapped to all coordinators with equal probability, we have  
               E   ⁡     (     Y   i     )       =     E   ⁡     (   X   )               (   10   )                 Var   ⁡     (     Y   i     )       =           k   -   1     k     ⁢     (         (     E   ⁡     (   X   )       )     2     +     E   ⁡     (   X   )         )       +       1   k     ⁢     Var   ⁡     (   X   )                   (   11   )             
   
 
         [0078]     If Var(X) is relatively large, Var(Y i ) would be less and it goes down as the number of coordinators increases. The intuition is that multi-coordinator equalized the variance of X and result in a well-balanced stream. This implies that although the total share remains the same, the difference between normalized service of two streams varies less with multiple coordinators.  
         [0079]     Different performance guarantees can be met by different delay functions. The delay functions can be calculated at coordinators locally so communication among schedulers is avoided. Various delay functions are possible, some of which are discussed further below.  
       EXAMPLE 1  
       [0080]     Suppose the service cost equals the throughput, if stream f requests service at brick A only, another equally weighted stream g requests service at brick A and many other bricks. Requests to different bricks are independent such that each can be sent at an arbitrary rate. Under T OTAL -DSFQ, eventually g would be completely blocked at A because the delay keeps increasing as more and more requests are sent to other bricks. Therefore, f and g are continuously backlogged at A but the total throughput of them are not equal. This Example 1 indicates that some restriction on streams and bricks may be implemented for total cost fair sharing.  
         [0081]     In Example 1, if stream g received too much bandwidth on other bricks, delay of requests to brick A would keep increasing and eventually be blocked completely. This is not desirable in many cases. Thus, it may be desirable to guarantee a minimum bandwidth so the consumer can always make progress.  
         [0082]     The problem can be solved under the above-described DSFQ framework, i.e., formulae (7-8), with a different delay function. If the delay function has an upper bound, there is a minimum bandwidth guarantee that is linear to the bound. 
    Theorem 4: Assume the delay function in formula (7) is non-negative and bounded by D f  for stream f. Let weights be normalized, i.e., 0≦φ f ≦1 and  
         ∑           ⁢     ϕ   f       =   1.       
 
 If f is backlogged on a brick, the aggregate cost of requests dispatched between two consecutive requests from f is at most  
             1   -     ϕ   f         ϕ   f       *     D   f       +       ∑   g     ⁢           ⁢     c   g   max           
   
 
         [0084]     Proof: We prove the theorem using virtual streams. Let the new delay function be interpreted as a sequence of small virtual requests with total cost equal to the delay. If the last request of f is dispatched at t 1  and the next requests is dispatched at t 2 , we have W f′ (t 1 ,t 2 )≦D f .  
         [0085]     For any virtual stream g′,
 
 W   g′ ( t   1   ,t   2 )≦φ g ( v   2   −v   1 )+ c   g   max   (12)
 
 for backlogged virtual stream f′,
 
φ f ( v   2   −v   1 )− c   f   max   ≦W   f′ ( t   1   ,t   2 )≦ D   f   (13)
 
 where v 1 =v(t 1 ) and v 2 =v(t 2 ) is the virtual time of SFQ. 
 
 Summing (12) up  
                 W   other     ⁡     (       t   1     ,     t   2       )       ≤         (     1   -     ϕ   f       )     ⁢     (       v   2     =     v   1       )       +       ∑     g   ≠   f               ⁢     c   g   max         ≤         (     1   -     ϕ   f       )     ⁢         D   f     +     c   f   max         ϕ   f         +       ∑     g   ≠   f               ⁢     c   g   max         ≤           1   -     ϕ   f         ϕ   f       *     D   f       +       ∑     g   ⁢                       ⁢           ⁢     c   g   max                 (   14   )             
 
         [0086]     If the cost of c f   i  is defined as the service time of request p f   i , the above theorem means the time interval between two consecutive requests dispatched at one brick is at most  
             1   -     ϕ   f         ϕ   f       *     D   f       +       ∑                     ⁢           ⁢       c   g   max     .           
 
 The average service interval is  
           1   -     ϕ   f         ϕ   f       *       D   f     .         
 
         [0087]     With theorem 4, given a minimum bandwidth requirement, we can calculate the bound and design delay functions within the bound. For example, any function of c f,A   j  that is continuous on domain [0,c f   max ] is bounded. The advantage of this function family is that it is based on c f,A   j  only and can be calculated at the back-end itself.  
         [0088]     Below, an exemplary, simple delay function in the family is presented and analyzed.
 
Delay( p   f,A   j )= c   f,A   j *( n −1)  (15)
 
 where n is the number of bricks stream f accesses in a time period. We call the new distributed algorithm with equations (7-8) (15) as S TRIPE -DSFQ, because it works the same as T OTAL -DSFQ if the data is striped on n bricks. 
 
         [0089]     Essentially, S TRIPE -DSFQ is SFQ(D) at every single brick with discounted weights and provides proportional service at each brick, but not a guarantee of total proportional service. A mixed delay function of equations (9) and (15) may be employed in certain embodiments. That is, a Hybrid-DSFQ algorithm may be employed, such as a hybrid of the S TRIPE -DSFQ and T OTAL -DSFQ algorithms. For instance, such a Hybrid-DSFQ algorithm may determine the minimum of the delay computed for a request by the S TRIPE -DSFQ and T OTAL -DSFQ algorithms for a request directed to a given scheduler, and send to the given scheduler such minimum delay for the request.  
         [0090]     Equation (16) below provides an exemplary hybrid algorithm for computing a delay for a request, which may be performed by a coordinator, according to one embodiment of the present invention.  
               Delay   ⁡     (     p     f   ,   A     j     )       =     min   ⁢     {         ∑     i   =       index   ⁡     (     p     f   ,   A       j   -   1       )       +   1           index   ⁡     (     p     f   ,   A     j     )       -   1       ⁢     c   f   i       ,       c     f   ,   A     j     *     (     n   -   1     )                     (   16   )             
 
         [0091]     When implemented via computer-executable instructions, various elements of embodiments of the present invention are in essence the software code defining the operations of such various elements. The executable instructions or software code may be obtained from a readable medium (e.g., a hard drive media, optical media, EPROM, EEPROM, tape media, cartridge media, flash memory, ROM, memory stick, and/or the like) or communicated via a data signal from a communication medium (e.g., the Internet). In fact, readable media can include any medium that can store or transfer information. Thus, the exemplary scheduling operations described above may be implemented in a system via computer-executable software code. The software code may run on any suitable processor-based system, such as the exemplary system of  FIGS. 1, 2 , and  7 . The above-described operations for computing a delay to accompany a request made to a scheduler (according to certain embodiments) may be performed via computer-executable software code, which may be employed at a coordinator as discussed above. The exemplary operations described above as being performed by a scheduler, such as executing a DSFQ algorithm for scheduling service, may be performed via computer-executable software code, which may be employed at a scheduler as discussed above.