Netgate Discussion Forum
    • Categories
    • Recent
    • Tags
    • Popular
    • Users
    • Search
    • Register
    • Login

    Calculating the required bandwidth for ACK queues for asymetric link

    Scheduled Pinned Locked Moved Traffic Shaping
    53 Posts 10 Posters 99.7k Views
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • D
      dusan
      last edited by

      Hi,

      First of all I would say thank you to the pfSense developers for this great product.

      And I would request for comments on my calculation below. Any comment will be very appretiated.

      Thank you and best regards.

      Dusan

      –------------------------------------------
      Motivation

      I tried to setup Traffic Shaper for an asymmetric Internet link (uplink = 256 kb/s, downlink = 512 kb/s). The Traffic Shaper Wizard offer the same value of 10% bandwidth for both qWANack and qLANack queues.

      This would mean that an ACK queue's bandwidth for a network interface be directly related (proportional) to the total bandwidth of that interface. For me, this doesn't seem reasonable. Imo, as an ACK queue is queuing ACK packets for traffics in the opposite direction, its bandwith should be somehow related to that of the opposite interface. Not very satisfied with the default bandwidth by Traffic Shaper Wizard, I decided to calculate the bandwidths myself.

      Formulas

      I assume that ACK queues are queuing only ACK packets.

      Let A be bandwidth(qWANroot). Let B be bandwidth(qLANroot).
      Let X be bandwidth(qWANack). Let Y be bandwidth(qLANack).

      The bandwidth of uplink ACKs should be directly related to that of other traffic's downlink, and vice versa:

      (1)  X / (B - Y) = avg. packet size(qWANack) / avg. packet size(other incoming traffic)
      (2)  Y / (A - X) = avg. packet size(qLANack) / avg. packet size(other outgoing traffic)

      Average packet sizes are not known a priori, but it appears a good practice to use the same value, say, 1/R, for the right side of both the equations. R = 9 seems to be a good choice. As we'll see below, one should choose R = 9 to be consistent with the 10% default bandwidth set by the pfSense' Traffic Shaper Wizard in case of symetric (up = down) links. Thus

      (1') X / (B - Y) = 1/R
      (2') Y / (A - X) = 1/R

      The solution of these equations is

      (3)  X = (BR - A) / (R^2 - 1)
      (4)  Y = (A
      R - B) / (R^2 - 1)

      We prefer expressing things in ratios, so let K = B/A and the solution be re-written as

      (3') X = A * (R*K - 1) / (R^2 - 1)
      (4') Y = B * (R/K - 1) / (R^2 - 1)

      Examples

      For all examples, R = 9, thus R^2-1 = 9^2-1 = 80.

      Ex.1. For K = 1 (symetric link):
      X = A * (9*1-1)/80 = A * 0.1
      Y = B * (9/1-1)/80 = B * 0.1

      So, the default bandwidth 10% offered by Traffic Shaper Wizard would be good for symmetric (up = down) links.

      Ex. 2. For K = 2 (my "motivation" case)
      X = A * (9*2-1)/80 = A * 0.21
      Y = B * (9/2-1)/80 = B * 0.044

      So, I would increase bandwidth of qWANack to 21% and I might reduce qLANack to 5% or even 4%.

      Ex. 3. For K = 4.
      X = A * (9*4-1)/80 = A * 0.44 
      Y = B * (9/4-1)/80 = B * 0.017

      i.e. one should set qWANack to 44%, qLANack 2%.

      Ex. 4. For K = 8 (typical home ADSL/Cable link)

      X = A * (9*8-1)/80 = A * 0.89
      Y = B * (9/4-1)/80 = B * 0.0016

      One should set qWANack to 89%, qLANack 1%.

      Discussion

      The equations above only recommend bandwidth values, which are only used as m2, the second slope in a HFSC service curve, namely the linkshare curve. For better latency, one should set some enough high value to m1, the first slope, for a service curve (typically the realtime curve) as well.

      1 Reply Last reply Reply Quote 0
      • B
        billm
        last edited by

        I don't quite understand where the equations came from or the variables defined in them.  However, feel free to come up with a patch, or add this information to http://wiki.pfsense.com/wikka.php?wakka=HFSCBandwidthShapingNotes

        –Bill

        pfSense core developer
        blog - http://www.ucsecurity.com/
        twitter - billmarquette

        1 Reply Last reply Reply Quote 0
        • D
          dusan
          last edited by

          Well, R represents the ratio of amounts of service that should be allocated to all other traffics and ACK traffic in the same duration (say, 1s).

          Whether it is ratio of packet sizes (as shown in equations (1) and (2)) is not important. The point is the bandwidth 10% set by the Traffic Shaper Wizard, which corresponds to R = 9. I believed it is a good choice in the case of symmetric link, and tried to use it as a known parameter in the general case. ;)

          1 Reply Last reply Reply Quote 0
          • B
            billm
            last edited by

            @dusan:

            Well, R represents the ratio of amounts of service that should be allocated to all other traffics and ACK traffic in the same duration (say, 1s).

            Whether it is ratio of packet sizes (as shown in equations (1) and (2)) is not important. The point is the bandwidth 10% set by the Traffic Shaper Wizard, which corresponds to R = 9. I believed it is a good choice in the case of symmetric link, and tried to use it as a known parameter in the general case. ;)

            Ahh, see the 10% value is just a value chosen almost purely at random.  It works…I agree, it may not be optimal, but it's a value that seems to work for now.  If you can come up with a better method, by all means, I'm listening.  HFSC is enough of a black art that I certainly don't claim to fully understand it.

            --Bill

            pfSense core developer
            blog - http://www.ucsecurity.com/
            twitter - billmarquette

            1 Reply Last reply Reply Quote 0
            • D
              dusan
              last edited by

              Based on statistical data found via Google (confirmed by pftop on my own network traffic) I've re-calculated the maximum bandwidth of qWANack and qLANack. (I'm totally unfamiliar with traffic engineering and the likes, so please correct me if I'm wrong.) As shown below, the calculation supports our feeling that 10% is good in case of symmetric link, and shows that my figures in post #1 for asymmetric links were too aggressive.

              For the purpose of calculation we assume a simple model, with qWANroot consisting of only qWANack and qWANdef, and qLANroot consisting of only qLANack and qLANdef. Thus outgoing and incomming packets other than ACKs are all queued in qWANdef and qLANdef, respectively.

              A, B, X, Y are defined as above. Let C = bandwidth(qWANdef), D = bandwith(qLANdef). Thus A = C+X and B = D+Y. In post #1, calculation was based on the system of equations X/D = Y/C = 1/9, which was too simplified:

              • It characterizes some "imaginary" or "average" traffic, not uploading, downloading, web surf nor any other real-life traffic.

              • It establishes some relation between the amount of data in certain direction and ACKnowledges in the opposite direction, but not yet the relation between the amount of incomming and outgoing data.

              Now we fix both the problems by assuming every (type of) traffic be characterized by a pattern, which is a 4-dimensional vector (c,d,x,y), where c, d, x, y is the amount of data passing through qWANdef, qLANdef, qWANack, qLANack, respectively, in the same duration (say, 1s), of that particular traffic.

              For example, the traffic pattern for Web surfing is (0.11, 1, 0.075, 0.075), saying that in order to receive 1 kb of useful Web data, 0.11 kb must be transmitted, furthermore 0.075 kb of ACKs must be transmitted and other 0.075 kb of ACKs must be received in 1s.

              The actual activity of i-th traffic is then obtained simply by multiplying that vector with a non-negative variable. For example, v*(0.11, 1, 0.075, 0.075) shows how much bandwidth are required for each queue in order to surf Web at v kb/s.

              The (new) calculation is based on six types of traffic, corresponding to variables v0 through v5:

              v0 * (1, 0.40, 0.01, 0.04) is p2p upload activity
              v1 * (0.04, 1, 0.04, 0.01) is p2p download activity
              v2 * (1, 0.1, 0.015, 0.05) is other bulk upload activity
              v3 * (0.1, 1, 0.05, 0.15) is other bulk download activity
              v4 * (1, 0.11, 0.075, 0.075) is web server activity
              v5 * (0.11, 1, 0.075, 0.075) is web surf activity

              and constrained by:

              sum(v_i * a_i) <= A
              sum(v_i * b_i) <= B

              where a_i = c_i + x_i and b_i = d_i + y_i and i running in 0,…,5.

              Two further constraints are made, limiting p2p upload and download at 80% of uplink and downlink bandwidth, respectively:

              v_0 * c_0 <= A * 0.8
              v_1 * d_1 <= B * 0.8

              We are now ready to estimate X and Y, the required bandwidth of qWANack and qLANack, in a worst-case fashion:

              X = max(sum(v_i * x_i))
              Y = max(sum(v_i * y_i))

              One can find the max's using any linear programming solver. I used M$ Excel :-).

              Examples

              Recall that K = B/A. If (say) A=128 kb/s and B=1024 kb/s, then K=8.

              Ex 1. For K=1, namely A=1, B=1 [mb/s], X/A = Y/B = 11.90% at (v4 = v5 = 0.794, others v_i = 0, here and below, unshown v_i are zeros), both links saturated.

              Ex 2. For K=2, namely A=1, B=2 [mb/s], X/A = 17.86% and Y/B = 8.93% at (v4 = 0.629, v5 = 1.752), both links saturated.

              Ex 3. For K=4, namely A=1, B=4 [mb/s], X/A = 29.76% and Y/B = 7.44% at (v4 = 0.299 ; v5 = 3.67), both links saturated.

              Ex 4. For K=8, namely A=1, B=8 [mb/s], maximums of sum(v_ix_i) and sum(v_iy_i) are not reached at the same time:
              X/A = 43.58% while sum(v_iy_i) = 3.94% at (v1 = 4.016 ; v5 = 3.669), both links saturated.
              Y/B = 5.07% while sum(v_i
              x_i) = 40.54% at (v5 = 5.405), uplink is saturated (at A100%), while downlink is loaded at B72.64%.

              Notes

              The traffic patterns (c_i, d_i, x_i, y_i) used here are illustrative. Nevertheless, the examples of calculation suggest that 10% would suffice in the case of symmetric and nearly-symmetric link, and in the case of very asymmetric link, one might consider setting some larger bandwidth for qWANack (although not too large as suggested in my post#1 above).

              Game and VoIP clients do not figure here, as they typically use UDP which – I think -- does not use ACK queues. In a network with game and VoIP continuously backlogged, then ACK queues require -- in percentage -- yet lower bandwidth.

              This is a worst-case analysis. But it is possible to estimate the bandwidths more closely to the average case by further constraining with upper limits that shouldn't be much higher than the desired linkshare.

              1 Reply Last reply Reply Quote 0
              • H
                hoba
                last edited by

                Maybe you can try to verify your formulas with these " shot in the dark unscientific" testing on ACK queues and an asymetric 16000kbit/s down 800 kbit/s up line:

                When I used 10% acks up and down I was not able to get more than about 8 mbit down when up was saturated.

                I changed the qwan acks (were showing drops with the 10% setting) to 40% and my downloads raised to 12 mbit with saturated upload.

                I changed qwan acks to 60% and my downloads went up and down between 13 and 15 mbit/s with saturated upload.

                Link was saturated by running multiple bittorrents, 3 ftp downloads, 2 http downloads and listening to an internetstream (about 1300 states)

                Some more observations:

                When only running few downloads it needs about 400 kbit/s ack only traffic to download with 16 mbit/s

                Pings with no load are about 7 ms on my line, with full upload I have about 10-20 ms, with full up and down and 60% ack setting (only qwan acks btw) they are between 30 and 110 ms (with even some lost pings judging from the rrd's).

                status_rrd_graph_img.png
                status_rrd_graph_img.png_thumb
                status_rrd_graph_img_quality.png
                status_rrd_graph_img_quality.png_thumb
                status_rrd_graph_img.png_thumb
                status_rrd_graph_img_quality.png_thumb

                1 Reply Last reply Reply Quote 0
                • D
                  dusan
                  last edited by

                  Thank you for your data.

                  Based on the "400 kbit/s ack only traffic to download with 16 mbit/s", I added another pattern, "FTP client", which is (epsilon, 1, 0.025, epsilon/5), where epsilon is somewhat arbitrarily chosen (I let it be 2.5E-4).

                  I've tried using them as a next example of calculation:

                  K=20. A=0.8, B=16 [mb/s].
                  "p2p upload" and "p2p download" are constrained by an upper limit of 10%.
                  "other bulk upload" and "other bulk download" are constrained by an upper limit of 20%.
                  "web server" and "web surf" are excluded (i.e. upper limited by 0).

                  Let v7 be the "activity" variable for FTP client (unconstrained).

                  Given that, WAN acks reached its maximum = 60,59% (while LAN acks reached 0.34% which isn't its maximum) at (v1 = 1.6; v3=2.483; v7=11.863), both links saturated.

                  As noted, my traffic patterns are only illustrative ("bulk download" and "bulk download" was based on audio streaming), to be accurate one would collect his/her own FTP download traffic patterns, say, from the values shown by pftop in its "Queues" screen in "P/S" (packets/second) and "B/S" (bytes/second) columns for qWANack, qLANack, qWANothers, qLANothers, qFTPup, qFTPdown when running (almost) solely FTP at full load.

                  Where qWANothers (qLANothers) is the sum of all uplink (downlink) queues except qWANack (qLANack), qFTPup and qFTPdown are the queues containing FTP traffic.

                  1 Reply Last reply Reply Quote 0
                  • H
                    hoba
                    last edited by

                    If you want to calculate a trafficshapingsetup for my connection and give me advice how to configure it or even sending me the trafficshaperpart of the config.xml (you can backup only this part from your pfSense) I can test it for you and report back how well these settings work. If we get some good results we can start integrating your formulars into the wizard  ;D

                    1 Reply Last reply Reply Quote 0
                    • D
                      dusan
                      last edited by

                      As you can see, even with not-so-cool traffic patterns, my first attempt for an open formula (post#1) fails. For now, I can only offer closed formulas which must be solved by linear programming solvers.

                      Linear programming based on traffic patterns cannot answer the "What should I do" question, so it cannot recommend any optimal traffic shaping setup. It can only answer the "What if" questions. For example:

                      • What maximum % qWANack would reach if I run p2p limited by 80% bandwidth, surf Web and check email at most 50% bandwidth and download FTP unlimited?

                      • Isn't that maximum too overestimated if I want to exploit my downlink at 90%?

                      Note that if we want to predict the behavior with respect to linkshare setup, we must constrain not only the variables v_i but also ratios between some of them. Then the problem goes beyond the scope of linear programming. However, one can still analyze it with the same "traffic pattern" approach, using a non-linear solver (MS Excel, for example).

                      Can we still develop an (empirical) open formula? Yes we can, but much works must be done before any second attempt:

                      1. Collect more realistic traffic patterns.

                      2. Select several of them as representatives.

                      3. Analyze and estimate the maximum bandwidth of qWANack (maybe qLANack too) for K=2, 4, 8, 16, 20, 24 and 32 (if any).

                      4. Let people try them out. Listen to feedback.

                      If no problems are reported, build the formula and (if it's desired,) integrate it to the wizard.

                      –--------------------
                      Hoba,

                      Pls, PM me your email address and I'll send you my spreadsheet. (You'll need MS Windows and Excel.)

                      1 Reply Last reply Reply Quote 0
                      • S
                        sullrich
                        last edited by

                        What about a userland daemon that watches traffic and dynamically alters the HFSC profile as traffic patterns change?

                        Please send me a copy of your spreadsheet as well (sullrich@gmail.com).

                        Thanks!

                        1 Reply Last reply Reply Quote 0
                        • D
                          dusan
                          last edited by

                          Adaptive traffic shaping? Would be great. There is a software named QoSbox that change linkshare dynamically. Maybe you'll find it helpful. For more details, refer to http://www.cs.virginia.edu/~mngroup/projects/qosbox/docs.html.

                          In the context of ACK queues in HFSC, however, I think it's not so hot topic. Because it's almost surely harmless assigning some large value (say, 60%) to qWANack linkshare or realtime curve's m1. If that bandwidth is needed, it's used. Otherwise it is allocated to other traffics.

                          Just my opinion.

                          –----
                          to hoba, sullrich: spreadsheet sent.

                          1 Reply Last reply Reply Quote 0
                          • S
                            sullrich
                            last edited by

                            Sounds great.  You seem to know a lot more about HFSC than we do.  Want to adopt our code?  :)

                            1 Reply Last reply Reply Quote 0
                            • S
                              sullrich
                              last edited by

                              Attaching the spreadsheet mentioned prior in this thread.

                              qWanAck.xls

                              1 Reply Last reply Reply Quote 0
                              • D
                                david nordin
                                last edited by

                                the outcome of this topic sounds really interesting and potentially very useful :)
                                best of luck

                                1 Reply Last reply Reply Quote 0
                                • U
                                  unreal1024
                                  last edited by

                                  Hi, please help me! How much set LAN ack and WAN ack (into percent) for DSL line Upload 512Kbps and Download 8192Kbps. (asymetric line).
                                  Very thanks!!!

                                  1 Reply Last reply Reply Quote 0
                                  • S
                                    sullrich
                                    last edited by

                                    @unreal1024:

                                    Hi, please help me! How much set LAN ack and WAN ack (into percent) for DSL line Upload 512Kbps and Download 8192Kbps. (asymetric line).
                                    Very thanks!!!

                                    Download the excel document and plug your values in.

                                    1 Reply Last reply Reply Quote 0
                                    • U
                                      unreal1024
                                      last edited by

                                      where find cell for LAN ans WAN ack? I am not uderstand this sheet :-(
                                      Thanks!

                                      ack.JPG
                                      ack.JPG_thumb

                                      1 Reply Last reply Reply Quote 0
                                      • S
                                        sullrich
                                        last edited by

                                        A (UP)
                                        B (DOWN)

                                        1 Reply Last reply Reply Quote 0
                                        • D
                                          dusan
                                          last edited by

                                          Then

                                          • click Tools/Solver…
                                          • click Set Target Cell, click R15C12 (or R16C12), click Max, click Solve
                                          • click Keep Solver Solution, click OK
                                            The required X [kb/s or mb/s] is shown in R15C12. The required X/A [%] is shown in R16C12.
                                          1 Reply Last reply Reply Quote 0
                                          • E
                                            eri--
                                            last edited by

                                            dusan can you please explain the rationale behind this in a formal way.

                                            I want to integrate this in the shaper wizard and the excel is not easily readble/understandable.

                                            Thanks in advance.

                                            1 Reply Last reply Reply Quote 0
                                            • First post
                                              Last post
                                            Copyright 2025 Rubicon Communications LLC (Netgate). All rights reserved.