home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_n_r / draft-rampal-flow-delay-service-00.txt < prev    next >
Text File  |  1996-12-17  |  25KB  |  611 lines
  1. INTERNET-DRAFT                                        Sanjeev Rampal,
  2. Expires June 20th 1997                       IBM Corpn.
  3.                                                       December 20th, 1996.
  4.  
  5.  
  6.     Flow Grouping For Reducing Reservation Requirements for 
  7.             Guaranteed Delay Service 
  8.         <draft-rampal-flow-delay-service-00.txt>
  9.  
  10.  
  11. Status of this Memo
  12.  
  13.    This document is an Internet-Draft.  Internet-Drafts are working
  14.    documents of the Internet Engineering Task Force (IETF), its areas,
  15.    and its working groups.  Note that other groups may also distribute
  16.    working documents as Internet-Drafts.
  17.  
  18.    Internet-Drafts are draft documents valid for a maximum of six months
  19.    and may be updated, replaced, or obsoleted by other documents at any
  20.    time.  It is inappropriate to use Internet- Drafts as reference
  21.    material or to cite them other than as ``work in progress.''
  22.  
  23.    To learn the current status of any Internet-Draft, please check the
  24.    ``1id-abstracts.txt'' listing contained in the Internet- Drafts
  25.    Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
  26.    munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
  27.    ftp.isi.edu (US West Coast).
  28.  
  29.  
  30. Abstract
  31.  
  32.    The guaranteed service class of the Integrated Services model 
  33.    is based on the Weighted Fair Queueing model and requires 
  34.    rate reservation in order to provide end-to-end delay guarantees.  
  35.    Often, the amount of reservation needed to satisfy specified 
  36.    delay bounds can be quite high leading to low network utilization. 
  37.    This draft demonstrates a property of the Weighted Fair Queueing 
  38.    formulation which enables grouping of flows (which use the 
  39.    guaranteed service and are routed over the same path) in such a 
  40.    way that a lower reservation is needed than would be required if 
  41.    each flow were treated individually, and the delay bounds of each 
  42.    flow can still be provably satisfied.  
  43.  
  44.  
  45. 1.0 Introduction 
  46.  
  47.    This draft presents a technique for improving the bandwidth 
  48.    utilization for connections/ flows belonging to the guaranteed 
  49.    service class [1] of the integrated services (IntServ) internet 
  50.    specification [2]. 
  51.  
  52. Rampal             Expires 20th June, 1997                   [Page 1]
  53.  
  54. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  55.  
  56.  
  57.    The guaranteed service class ensures no packet loss and provides 
  58.    a strict upper bound on the end-to-end delay that will be 
  59.    experienced by any packet of a flow belonging to this class. This 
  60.    service requires each network element in the path of a flow to 
  61.    reserve a certain bandwidth for this flow. One problem with 
  62.    supporting this service class is that the amount of bandwidth 
  63.    reservation required can be quite high (and could be much greater
  64.    than even the peak data arrival rate of the flow). This results 
  65.    in poor network utilization.
  66.  
  67.    This draft addresses this utilization problem for guaranteed service 
  68.    flows.  A method is presented for reducing the amount of bandwidth
  69.    reservation needed to support such flows (thereby improving network
  70.    utilization). This is done while retaining the same delay guarantees
  71.    that the service already provides to each flow. The reduction in
  72.    reservation is achieved through grouping some of the guaranteed 
  73.    service flows in a network in such a way that the amount of 
  74.    bandwidth needed to be reserved for a group is less than the sum 
  75.    of the reservations that would be required for each flow 
  76.    individually.
  77.  
  78.  
  79.    In this draft, first, we outline how to perform this flow grouping.
  80.    We then show that utilization can be improved while still provably 
  81.    satisfying delay guarantees for each flow. The main contribution 
  82.    of this draft is to demonstrate this property of Weighted Fair 
  83.    Queueing. We then outline an approach for implementing this 
  84.    technique in an internetwork. 
  85.  
  86.    Note.  The proposed flow grouping technique is completely 
  87.    independent of the reservation merging using filters such as 
  88.    "wild card filters" proposed in RSVP specifications. 
  89.  
  90.  
  91. 2.0 Outline of Flow Grouping 
  92.  
  93.    The proposed approach works by forming groups from among flows
  94.    which use the guaranteed service and which are routed over the
  95.    same path in a network (that is flows which use the exact same 
  96.    set of links for their path in the network). Current IP routing 
  97.    algorithms do not account for dynamic link loads and in the absence
  98.    of failures, most or all traffic between any two nodes will usually
  99.    be routed over the same set of links. With the use of more QoS or 
  100.    load sensitive routing algorithms in the future this technique can 
  101.    still be used however, additional state will need to be maintained 
  102.    in routers to indicate which flows are using the same path. This 
  103.    draft does not concentrate  on such implementaiton details at 
  104.    this time. 
  105.  
  106. Rampal             Expires 20th June 1997                    [Page 2]
  107.  
  108. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  109.  
  110.  
  111.    The reason for choosing only flows which use the same 
  112.    path is that the delay bound calculated by the Guaranteed Service 
  113.    is an end-to-end value. If we try to group flows whose paths share 
  114.    some links initially but subsequently diverge for example, we will 
  115.    need to recharacterize the traffic of each flow after the paths 
  116.    diverge, possibly using reshaping and adding delay. We do not 
  117.    address that problem. The main contribution of this draft is to 
  118.    introduce the grouping technique. Even if grouping is restricted 
  119.    only to flows which share the same path, this will always result
  120.    in some improvement in the utilization over existing approaches
  121.    which do not employ any grouping at all.  
  122.  
  123.    We show that by grouping some (but not all) of such flows 
  124.    appropriately and assigning a bandwidth reservation to the entire 
  125.    group instead of to the individual flows, we can reserve a lower 
  126.    amount of bandwidth for the group than the total that would be 
  127.    required if this grouping were not to be performed. Further we can 
  128.    still satisfy the delay bounds that are provided for each flow 
  129.    when such a grouping is not performed.  For a given set of flows, 
  130.    a simple test procedure is outlined using which the network 
  131.    determines whether the reservation with grouping will be less than 
  132.    without grouping. Accordingly flows will be grouped only if there 
  133.    is some bandwidth savings as compared to assigning a separate 
  134.    reservation for each flow as recommended by the specification [1].  
  135.  
  136.  
  137. 2.1 Flow grouping technique
  138.  
  139.    The achievable improvement in utilization using flow grouping is 
  140.    explained first using some examples. Next a procedure for 
  141.    implementing this in an internetwork is outlined.
  142.  
  143.    Consider two flows(F1 and F2) using the guaranteed service class in
  144.    a network as defined in [1] and [2]. These two flows are between the
  145.    same source and receiver nodes and are routed over the exact 
  146.    same set of links (which we denote as L1, L2 ... Ln where n is the 
  147.    number of physical links/hops in the path). Let P denote the maximum 
  148.    packet size allowed for any connection in the network and let Cj 
  149.    denote the bandwidth of link Lj (j=1,2 ... n).
  150.  
  151.    Let the traffic characterization of these two flows be given as
  152.    (b1, r1, P1) and (b2, r2, P2) respectively where the b term 
  153.    is the bucket size and the r term is the token generation rate of
  154.    the leaky bucket characterizing the respective flows, while the P 
  155.    terms are the maximum packet sizes. Let D1 and D2 be the maximum
  156.    tolerable delay for the respective flows as specified by the 
  157.    application.
  158.  
  159. Rampal             Expires 20th June, 1997                   [Page 3]
  160.  
  161. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  162.  
  163.  
  164.    Consider a network in which separate rate reservations of R1 and
  165.    R2 have been assigned to these two flows (we assume that
  166.    the reservation for a flow is greater than its token generation rate 
  167.    which is a necessary condition for guaranteed service).  The total 
  168.    amount of bandwidth which needs to be reserved on each link in the 
  169.    path is hence R1 + R2.   In the guaranteed service formulation,
  170.    the delay bound is inversely related to the amount of the reservation.
  171.    Hence to minimize the amount of reservation for this case, the delay
  172.    guarantee provided by the network must equal that required by the 
  173.    flow (since any lower reservation will increase the delay bound 
  174.    provided by the network beyond the maximum tolerable limit 
  175.    specified by the application).
  176.  
  177.    Hence we have,
  178.  
  179.    D1 = (b1/R1) + (n-1) * (P1/ R1) + (sum from j=1 to n) P/Cj       (1)
  180.  
  181.    D2 = (b2/R2) + (n-1) * (P2/ R2) + (sum from j=1 to n) P/Cj      (2)
  182.  
  183.  
  184.    The quantities on the right hand sides of equations (1) and (2) 
  185.    are the formulation of the end-to-end queueing delay bound as 
  186.    specified in [4]. The formulation in [1] is slightly different but 
  187.    is derived from the same. We restrict ourselves to the strict WFQ
  188.    type formulation from [4] in this draft. The actual delay bound would 
  189.    equal the queueing delay bound plus the propagation delay. Given the 
  190.    route of a flow, the  propagation delay component is fixed and the 
  191.    same for all flows using the same route. Hence without any loss 
  192.    of generality, we restrict ourselves to queueing delay bounds in 
  193.    this draft.  
  194.  
  195.    Now consider a flow created by grouping these two flows into one 
  196.    flow group which is characterized by the traffic model 
  197.    (b_g, r_g, P_g) (the bucket size, token generation rate and maximum 
  198.    packet size repectively of the resultant flow after grouping). Let 
  199.    this flow group be assigned a reservation of Rg. Physically, packets 
  200.    from both flows are simply multiplexed first come first served into 
  201.    one flow.  Packets which arrive at the same instant are reordered 
  202.    arbitrarily. If the scheduler uses separate queues for different
  203.    flows for example, then we simply send packets from all flows in a
  204.    flow group to the same queue.
  205.  
  206.    Consider a set of traffic characterization parameters for the flow
  207.    group which are obtained as follows.
  208.  
  209.     b_g = b1 + b2                         (3)
  210.  
  211.     r_g = r1 + r2                         (4)
  212.  
  213.     Pg = max{P1, P2}                     (5)
  214.  
  215.  
  216. Rampal             Expires 20th June, 1997                   [Page 4]
  217.  
  218. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  219.  
  220.  
  221.    In the appendix, we show that these values are sufficient to 
  222.    characterize the traffic of the flow group (which is the aggregate
  223.    traffic consisting of packets from both flows). In other words, if 
  224.    the individual flows are deemed conforming by a leaky bucket derived
  225.    from the individual traffic models, then the traffic of the flow
  226.    group will also be deemed conforming by a leaky bucket based on
  227.    traffic values for the flow group calculated as above.
  228.  
  229.    The minimum value of the delay bound that can be guaranteed by 
  230.    the network to this combined flow can be calculated given this
  231.    reservation.  We note that if the worst case delay bound guaranteed
  232.    to the flow group is no more than the minimum of all delay bounds
  233.    guaranteed to each individual flow, then the delay seen by any
  234.    packet in the flow group is guaranteed to be less than the delay 
  235.    bound of the group and hence less than the delay bound guaranteed 
  236.    to its own flow.
  237.  
  238.    The table below shows the minimum delay bound for the individual 
  239.    and aggregate flows when Rg = R1 + R2 for two example values of
  240.    the traffic parameters (n=2 and P/Cj = 1, j=1,2 are assumed).
  241.  
  242.    In the first case, the minimum delay bound that can be guaranteed
  243.    for the combined flow with Rg = R1 + R2 (denoted
  244.    as D_(1,2) is less than each of the bounds (D1 and D2) that can be
  245.    guaranteed for the flows individually, using separate reservations. 
  246.    Hence a lower overall reservation (R') can be obtained
  247.    when the flows are grouped. As shown, this results in a reduction of
  248.    25 percent in the amount of bandwidth which needs to be reserved on
  249.    each link in the path of these flows. On the other hand, in the 
  250.    second case, with Rg = R1 + R2,  the minimum delay bound that
  251.    can be guaranteed for the combined flow is greater than that which 
  252.    can be guaranteed for flow F1 with separate reservations. In order 
  253.    for the combined flow to obtain a delay bound satisfactory for 
  254.    both flows, a reservation of greater than R1 + R2 would be required.
  255.    Hence there is no gain in grouping for this case and better 
  256.    utilization would be obtained by keeping the two flows separate and 
  257.    maintaining individual reservations.
  258.  
  259.  
  260.     Table 1: Examples of gain (or loss) using flow grouping
  261.  
  262. (b1, r1, P1)  (R1, D1)  (b2, r2, P2)   (R2, D2)   D_(1,2) R'   Percent 
  263.                                  gain 
  264. ------------  -------   -----------    -------    ------  -    -------
  265.  
  266. (10, .5, 10)  (1, 22)   (10, .5, 10)   (1, 22)    17      1.5  25 
  267.  
  268. (10, .5, 10)  (1, 22)   (10, .5, 100)  (1, 112)   62      -    Loss
  269.  
  270. ----------------------------------------------------------------------
  271. n=2, P/Cj = 1, j=1,2
  272.  
  273. percentage gain is defined as 100 * (R1 + R2 - R')/(R1 + R2)
  274.  
  275. Rampal             Expires 20th June, 1997                   [Page 5]
  276.  
  277. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  278.  
  279.  
  280.  
  281. 2.2. A procedure for testing whether grouping should be performed.
  282.  
  283.    As shown above, there may or may not be some gain in grouping 
  284.    two flows together. The procedure to test whether two flows can 
  285.    be grouped together is straightforward. The total reservations
  286.    required with and without grouping are compared. Grouping can be 
  287.    performed only if it results in lower total reservation than the 
  288.    sum of the reservations with no grouping.
  289.  
  290.    Given the two flows F1 and F2, and their traffic parameters and 
  291.    delay requirements as above, the procedure for testing whether
  292.    they should be combined into a group is as follows.
  293.  
  294.    1. Calculate the total reservation required with grouping using 
  295.    equation (6) (which simply inverts the standard delay bound 
  296.    equation which has the form like equations (1) and (2)).
  297.  
  298.  
  299.    Rg = max {r_g, (b_g+(n-1)* P_g)/(D_g - (sum j=1 to N) P/Cj)}     (6)
  300.  
  301.    where r_g, b_g and P_g are calculated according to equations (3) 
  302.    through (5).
  303.  
  304.    D_g = min(D1,  D2)                             (7)
  305.  
  306.  
  307.    2. Now calculate the total reservation required when grouping is not
  308.    performed. This is given by equation (8) below.
  309.  
  310.    R_tot = R1 + R2                                 (8)
  311.  
  312.    where
  313.  
  314.    R1 = max{r_1, (b_1 + (n-1) * P_1)/(D1 - (sum j=1 to n) P/Cj)}    (9)
  315.  
  316.    R2 = max{r_2, (b_2 + (n-1) * P_2)/(D2 - (sum j=1 to n) P/Cj)}   (10)
  317.  
  318.  
  319.    3. If the reservation with grouping (from equation (6)) is smaller,
  320.    grouping can be performed else it is better to provide individual
  321.    reservations.
  322.  
  323.    4. If it is decided to group two flows, then the new parameters of
  324.    the resultant flow group are calculated exactly as in equations (3) 
  325.    through (5) (and equation (7)).
  326.  
  327.  
  328. Rampal             Expires 20th June, 1997                   [Page 6]
  329.  
  330. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  331.  
  332.  
  333.  
  334. 3.0 Implementing flow grouping in a network
  335.  
  336.    In a network supporting guaranteed service, this technique is 
  337.    implemented as follows. At each source, corresponding to each 
  338.    receiver node r, and each unique path p between these two nodes 
  339.    which has at least one guaranteed service flow,  the following 
  340.    information is maintained. The triplet (b_i, r_i, P_i) and the 
  341.    delay requirement D_i is maintained for each such flow i. In addition, 
  342.    for each flow group between these nodes and using this path p, a 
  343.    list of flows is maintained which form this group. Flows that have 
  344.    not been combined with any other flow are treated as groups containing 
  345.    only one flow. For each flow group, an aggregated set of traffic 
  346.    parameters as well as amount of reservation and the delay guarantee 
  347.    (calculated according to equations (3), (4), (5) and (7) above) are 
  348.    maintained.  Note that the information needed to be maintained can 
  349.    be greatly reduced if there is always only one path between any two 
  350.    nodes as is the characteristic of most existing IP routing algorithms 
  351.    which are not load sensitive. 
  352.  
  353.    We now consider three possible cases that can cause the amount of 
  354.    reservation on a path to change.  
  355.  
  356.     1. A new flow enters the network.
  357.  
  358.     When a new flow enters the network and is routed over a specific 
  359.     path, it is tested whether it can be combined with each 
  360.     existing flow group between the same source receiver pair and 
  361.     using the same path (using the test outlined above). If it 
  362.     cannot be successfully combined with any existing group, then 
  363.     a separate reservation is created for this flow and a new group 
  364.     is created containing only this flow. Else, it is combined with 
  365.     that flow group which will result in the smallest overall 
  366.     increase in reservation. on this path.  Finally, the parameters 
  367.     of the selected flow group are updated to reflect the addition 
  368.     of the new flow to the group (again according to equations (3) 
  369.     through (7)). Hence the test for grouping will be performed 
  370.     with every existing flow group on the same path which in the 
  371.     worst case equals the number of flows in the path.
  372.  
  373.     2. An existing flow leaves the network.
  374.  
  375.     In practice, this may occur because the reservation refresh 
  376.     message for a particular flow was not received within a 
  377.     specified timeout period or an explicit `disconnect' message 
  378.     was received. Regardless of the disconnecting procedure 
  379.     the same techniques apply.
  380.  
  381.  
  382. Rampal             Expires 20th June, 1997                   [Page 7]
  383.  
  384. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  385.  
  386.  
  387.     The parameters of the group to which this flow was assigned are
  388.     recalculated taking into consideration only the flows which 
  389.     continue to exist in the group. The new token generation rate 
  390.     r_g and bucket size b_g are calculated by subtracting out the 
  391.     contribution of the flow which is leaving the group. The 
  392.     new P_g and D_g can be calculated by recomputing the maximum 
  393.     and minimum respectively over the remaining flows. An 
  394.     improvement in efficiency can be obtained by using a heap data 
  395.     structure (one each for the maximum packet size and tolerable 
  396.     delay for flows in a flow group).  This will speed up the 
  397.     calculations required everytime a flow enters or leaves a 
  398.     group.
  399.  
  400.     3. An existing flow changes its traffic parameters or 
  401.     delay requirements
  402.  
  403.     The case of a change in the traffic parameters of a flow can 
  404.     be treated simply as a combination of the above two cases 
  405.     (it is equivalent to a flow with the old parameters leaving 
  406.     the network and another flow with the new parameters 
  407.     subsequently entering the network).
  408.  
  409.  
  410. 3.1 Performance control policies
  411.  
  412.     In order to obtain maximal bandwidth reduction, the network 
  413.     should always attempt to re-assign resources in any of the 
  414.     three cases above so that overall reservation is kept as low 
  415.     as possible. However, this requires performing the test for 
  416.     grouping frequently.  Each such test can involve O(m) 
  417.     calculations where m is the number of flows in a path, since 
  418.     in the worst case, we have to compare an incoming or changing 
  419.     flow against all existing flows.
  420.  
  421.     The network can implement several policies which reduce the 
  422.     amount of calculations and resource re-allocations by 
  423.     compromising on the achievable reduction in reservation. For 
  424.     instance, if the only the tolerable delay for a flow increases, 
  425.     it may continue in its current group (thereby avoiding any
  426.     resource re-allocation or calculations), even though a greater
  427.     reduction in the amount of reservation could have been achieved
  428.     if this flow was now assigned to another flow group. As another
  429.     example, a network may choose to always perform separate 
  430.     reservations when a flow enters a network (in order to obtain
  431.     fast connection setup), but then, perform the calculations 
  432.     for optimally performing the flow grouping in the background 
  433.     once the flow has already been setup.
  434.  
  435.     Several such policies can be defined but are not the
  436.     main focus of this draft. This contribution of this draft is
  437.     the flow grouping technique to show that it will always result
  438.     in some improvement in the utilization for guaranteed service 
  439.     flows as compared to an implementation which does not perform 
  440.     grouping.
  441.  
  442. Rampal             Expires 20th June 1997                    [Page 8]
  443.  
  444. INTERNET DRAFT     Flow Grouping for Guaranteed Service      Dec, 1996
  445.  
  446.  
  447.     An additional comment is that the proposed scheme does not 
  448.     claim to achieve the optimal grouping of flows resulting in 
  449.     the absolute minimal possible reservation for a set of flows. 
  450.     The main point of this contribution is that
  451.     use of this technique will result in a reservation which 
  452.     is never greater and often lower than when it is not used. 
  453.  
  454. 3.2 Some Additional Issues
  455.  
  456.     There is nothing in the flow grouping technique that restricts 
  457.     it to be performed only in the case of source-initiated 
  458.     reservation environments (such as ATM [5]) or in 
  459.     receiver-initiated environments (such as RSVP signaling over 
  460.     IP [3]). In any environment where the Guaranteed Service as 
  461.     defined in [1] is provided, this technique can be used to 
  462.     improve utilization.
  463.  
  464.     Policing and Implementation Issues
  465.  
  466.     Even though flows are grouped, policing should still be 
  467.     performed on individual flows rather than on flow groups. This 
  468.     ensures that a flow which violates its traffic specification 
  469.     can be detected even if the combined traffic in a flow group may 
  470.     still be in comformance with the calculated parameters for 
  471.     the group.
  472.  
  473.     An additional issue is that the Guaranteed Service additionally
  474.     includes two parameters in the traffic specification viz. a 
  475.     minimum policed unit and a peak rate. These parameters are not 
  476.     involved in the delay calculations [1], hence have not been 
  477.     addressed in this draft. We note for the sake of completeness 
  478.     that if needed the peak rate of a flow group should be calculated
  479.     as being the sum of the peak rates of the individual flows in it, 
  480.     while the minimum policed unit should be calculated as the 
  481.     minimum of the corresponding quantity from all flows in the group.
  482.  
  483.  
  484. Rampal             Expires 20th June 1997                  [Page 9]
  485.  
  486. INTERNET DRAFT     Flow Grouping for Guaranteed Service       Dec, 1996
  487.  
  488.  
  489. 4.0 References
  490.  
  491.  
  492. [1] S. Shenker, C. Partridge, R. Guerin "Specification of Guaranteed 
  493. Service," draft-ietf-intserv-guaranteed-svc-06.txt,
  494. Integrated Services Working Group, Internet Engineering Task Force (IETF),
  495. August 1996.
  496.  
  497. [2] R. Braden, D. Clark, and S. Shenker, "Integrated Services 
  498. in the Internet Architecture: an Overview," RFC 1633, June 1994.
  499.  
  500. [3] R. Braden et. al., "Resource ReSerVation Protocol (RSVP) - 
  501. Version 1 Functional Specification," 
  502. draft-ietf-rsvp-spec-14.txt, November 1996.
  503.  
  504. [4] A.K. Parekh and R.G. Gallager, "A Generalized Processor Sharing 
  505. Approach to Flow Control in Integrated Services Networks - The 
  506. Multiple Node Case," Proc IEEE Infocom '93 pp.521-530.
  507.  
  508. [5] The ATM Forum, "User-Network Interface (UNI) Specification 
  509. v3.1,"  September 1994.
  510.  
  511.  
  512. 5.0 Appendix
  513.  
  514. We show here that the traffic parameters calculated using equations
  515. (3), (4),  (5) and the delay bound of (7) are sufficient to 
  516. characterize a flow group formed from two individual flows. Consider 
  517. the flows F1 and F2 with traffic parameters (b1, r1, P1) and 
  518. (b2, r2, P2) and delay upper bounds D1 and D2 as above.
  519.  
  520. If flow F1 conforms to its traffic specification,
  521. the amount of data provided by it to the source node over any time 
  522. interval (t1 , t2) is at most b1 + r1*(t2 - t1). Similarly the amount 
  523. of data provided by flow F2 in the same time interval cannot exceed 
  524. b2 + r2*(t2 - t1). 
  525. Now consider the flow obtained by grouping these two flows (Fg), 
  526. with traffic parameters (b_g, r_g, P_g) and delay bound
  527. D_g, where these quantities are calculated according to
  528. equations (3), (4), (5) and (7) above. Over time interval (t1, t2)
  529. hence, the aggregate flow is required to generate no more
  530. than b_g + r_g*(t2 - t1). However, this is easily true because when 
  531. equations (3) and (4) are true, we have
  532.  
  533. b_g + r_g*(t2 - t1) = (b1 + r1*(t2 - t1)) + (b2 + r2*(t2 - t1))
  534.  
  535. Also, the greater of P1 and P2 is clearly the
  536. maximum packet size of the combined flow. Finally, if every packet 
  537. of the combined flow is guaranteed an end to end delay which is the 
  538. minimum of the tolerable delays of all flows making up the flow group, 
  539. clearly, every flow will see an acceptable delay even when it is 
  540. combined with other flows in a group. Hence equations (3), (4), (5) 
  541. and (7) represent valid parameter values for the flow obtained by 
  542. grouping flows F1 and F2.
  543.  
  544. Rampal             Expires 20th June, 1997                   [Page 10]
  545.  
  546. INTERNET DRAFT     Flow Grouping for Guaranteed Service       Dec, 1996
  547.  
  548.  
  549. 6.0 Author Information 
  550.  
  551. Sanjeev Rampal
  552.  
  553. C305/B664, 
  554. IBM Networking Division, 
  555. Research Triangle Park, NC 27709.
  556.  
  557. Voice 919-254-4801
  558. email sanjeev@raleigh.ibm.com
  559.  
  560.  
  561.  
  562.  
  563.  
  564.  
  565.  
  566.  
  567.  
  568.  
  569.  
  570.  
  571.  
  572.  
  573.  
  574.  
  575.  
  576.  
  577.  
  578.  
  579.  
  580.  
  581.  
  582.  
  583.  
  584.  
  585.  
  586.  
  587.  
  588.  
  589.  
  590.  
  591.  
  592.  
  593.  
  594.  
  595.  
  596.  
  597.  
  598.  
  599.  
  600.  
  601.  
  602.  
  603.  
  604. Rampal             Expires 20th June, 1997                     [Page 11]
  605.  
  606. INTERNET DRAFT     Flow Grouping for Guaranteed Service        Dec, 1996
  607.  
  608.  
  609.  
  610.  
  611.