Add initial support for SFB qdisc, still needs tuning

13 files changed, 231 insertions, 3 deletions

diff --git a/lib/Vyatta/Qos/FairBlue.pm b/lib/Vyatta/Qos/FairBlue.pm
new file mode 100644
index 0000000..57060f0
--- /dev/null
+++ b/lib/Vyatta/Qos/FairBlue.pm
@@ -0,0 +1,132 @@
+# Random Detect
+#
+# This Qos module uses DSMARK and GRED to provide a policy
+# similar to Cisco Weighted Random Detect.
+#
+# See Almesberger, Werner; Hadi Salim, Jamal; Kuznetsov, Alexey
+# "Differentiated Services on Linux"
+# http://www.almesberger.net/cv/papers/18270721.pdf
+#
+# **** License ****
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License version 2 as
+# published by the Free Software Foundation.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+# General Public License for more details.
+#
+# This code was originally developed by Vyatta, Inc.
+# Portions created by Vyatta are Copyright (C) 2008 Vyatta, Inc.
+# All Rights Reserved.
+# **** End License ****
+
+package Vyatta::Qos::FairBlue;
+use strict;
+use warnings;
+
+require Vyatta::Config;
+use Vyatta::Qos::Util qw/getRate getAutoRate getTime/;
+
+my %qdiscOptions = (
+    'priority'      => \&prioQdisc,
+    'fair-queue'    => \&sfqQdisc,
+    'drop-tail'     => \&fifoQdisc,
+);
+
+# Create a new instance based on config information
+sub new {
+    my ( $that, $config, $name ) = @_;
+    my $level = $config->setLevel();
+
+    my $target = $config->returnValue("queue-target");
+    die "queue-target configuration missing\n" unless $target;
+    my $limit = $config->returnValue("queue-limit");
+    die "queue-limit configuration missing\n" unless $limit;
+    my $type = $config->returnValue("queue-type");
+    $type = "fair-queue" if (!defined($type));
+ 
+    my $pburst = $config->returnValue("penalty burst");
+    my $prate = $config->returnValue("penalty rate");
+
+    my $self = {};
+    my $class = ref($that) || $that;
+    bless $self, $class;
+
+    $self->{_target} = $target;
+    $self->{_limit}  = $limit;
+    $self->{_type}   = $type;
+    $self->{_pburst} = $pburst;
+    $self->{_prate}  = $prate;
+
+    sfqValidate($self, $level) if ($self->{_type} eq "fair-queue");
+
+    return $self;
+}
+
+sub sfqValidate {
+    my ( $self, $level ) = @_;
+    my $limit = $self->{_limit};
+
+    if ( defined $limit && $limit > 127 ) {
+        die "queue limit must be between 1 and 127 for queue-type fair-queue\n";
+    }
+}
+
+sub prioQdisc {
+    my ( $self, $dev ) = @_;
+    my $prio_id = 0x4000 + $self->{id};
+    my $limit   = $self->{_limit};
+
+    printf "handle %x: prio\n", $prio_id;
+
+    if ($limit) {
+        foreach my $i (qw/1 2 3/) {
+            printf "qdisc add dev %s parent %x:%x pfifo limit %d\n",
+              $dev, $prio_id, $i, $limit;
+        }
+    }
+}
+
+sub sfqQdisc {
+    my ( $self, $dev ) = @_;
+
+    print "sfq perturb 10";
+    print " limit $self->{_limit}" if ( $self->{_limit} );
+    print "\n";
+}
+
+sub fifoQdisc {
+    my ( $self, $dev ) = @_;
+
+    print "pfifo";
+    print " limit $self->{_limit}" if ( $self->{_limit} );
+    print "\n";
+}
+
+sub gen_leaf {
+    my ( $self, $dev, $parent ) = @_;
+    my $qtype = $self->{_type};
+    return unless $qtype;    # default is okay
+
+    my $q = $qdiscOptions{$qtype};
+    die "Unknown queue-type $qtype\n"
+      unless $q;
+
+    printf "qdisc add dev %s parent %x:%x ", $dev, $parent, 0;
+    $q->( $self, $dev );
+}
+
+sub commands {
+    my ( $self, $dev ) = @_;
+    my $root = 1;
+    printf("qdisc add dev %s root handle %x:0 sfb limit %d target %d ",
+             $dev, $root, $self->{_limit}, $self->{_target});
+    printf(" penalty_rate %d ", $self->{_prate}) if (defined $self->{_prate});
+    printf(" penalty_burst %d", $self->{_pburst}) if (defined $self->{_pburst});
+    print("\n");
+    gen_leaf( $self, $dev, $root);     
+}
+
+1;
diff --git a/lib/Vyatta/Qos/ShaperClass.pm b/lib/Vyatta/Qos/ShaperClass.pm
index 4afd90c..8da2a54 100644
--- a/lib/Vyatta/Qos/ShaperClass.pm
+++ b/lib/Vyatta/Qos/ShaperClass.pm
@@ -111,10 +111,67 @@ sub prioQdisc {
     }
 }
 
+sub sfbQdisc {
+    # Like RED, SFB can be quite complex. 
+    # However, unlike RED, the values for SFB can be approximated 
+    # with a better degree of success.
+    
+    # This is an attempt to get as close to optimal SFB options 
+    # it currently doesn't tune for increment and decrement so for large bandwidths
+    # this may not be optimal. 
+    # It is currently setup for 1000 byte packets and a 50 ms RTT.
+
+    my ( $self, $dev, $rate ) = @_;
+    my $sfb_id = 0x4000 + $self->{id};
+    my $avgpkt = 1000 * 8; # avgpkt in bits
+    my $limit = $self->{_limit};
+    my $latency = 0.1; # 50ms
+
+    my $target = ($rate * $latency)/$avgpkt; #target queue size in packets
+    $target = sprintf "%d", ($limit * 0.78) if ($target >= $limit);
+    $target = 1 if ($target < 1);
+
+    my $packet_rate = $rate/$avgpkt;
+    my $maxrate = $target/($latency); # use this value to keep penalty rate sane
+#    if ($maxrate < $packet_rate){
+#       print STDERR "Warning: queue-limit isn't long enough for desired bandwidth\n";
+#    }
+    $target = sprintf "%d", $target;
+
+    my $max = sprintf "%d", $target * 1.25;
+    $max = $limit if ($max >= $limit);
+
+    my $penalty_rate = sprintf "%d", ($maxrate)*0.1; # 10% of rate in pps
+    $penalty_rate = 1 if ($penalty_rate < 1);
+
+    my $penalty_burst = sprintf "%d", ($penalty_rate * $latency);
+    $penalty_burst = sprintf "%d", ($penalty_burst * 0.1)if ($penalty_burst >= $limit);
+    $penalty_burst = 1 if ($penalty_burst < 1);
+
+    printf "handle %x: sfb", $sfb_id; 
+    print  " target $target";
+    print  " max $max";
+    print  " limit $limit";
+    print  " penalty_rate $penalty_rate";
+    print  " penalty_burst $penalty_burst";
+    print  " increment 0.001";
+    print  " decrement 0.0002";
+    print  "\n";
+    printf STDERR "pktrate %d, maxrate %d, qtarget %d, qmax %d, prate %d, pburst %d",
+                    $packet_rate, $maxrate, $target, $max, $penalty_rate, $penalty_burst;
+
+    # Use SFQ where possible
+    if ($limit < 128){
+      printf "qdisc add dev %s parent %x: sfq perturb 10 limit %d\n", $dev, $sfb_id, $limit;
+    } else {
+      printf "qdisc add dev %s parent %x: pfifo limit %d\n", $dev, $sfb_id, $limit;
+    }
+}
+
 sub sfqQdisc {
     my ( $self, $dev, $rate ) = @_;
 
-    print "sfq";
+    print "sfq perturb 10";
     print " limit $self->{_limit}" if ( $self->{_limit} );
     print "\n";
 }
@@ -201,6 +258,7 @@ sub redValidate {
 my %qdiscOptions = (
     'priority'      => \&prioQdisc,
     'fair-queue'    => \&sfqQdisc,
+    'fair-blue'     => \&sfbQdisc,
     'random-detect' => \&redQdisc,
     'drop-tail'     => \&fifoQdisc,
 );
diff --git a/scripts/vyatta-qos.pl b/scripts/vyatta-qos.pl
index 469c50f..fa491a0 100755
--- a/scripts/vyatta-qos.pl
+++ b/scripts/vyatta-qos.pl
@@ -29,6 +29,7 @@ my %policies = (
     'out' => {
 	'shaper'           => 'TrafficShaper',
 	'fair-queue'       => 'FairQueue',
+	'fair-blue'        => 'FairBlue',
 	'rate-control'     => 'RateLimiter',
 	'drop-tail'        => 'DropTail',
 	'network-emulator' => 'NetworkEmulator',
diff --git a/templates/traffic-policy/fair-blue/node.def b/templates/traffic-policy/fair-blue/node.def
new file mode 100644
index 0000000..f49d59b
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.def
@@ -0,0 +1,8 @@
+tag:
+type: txt
+help: Stochastic Fair Blue policy
+syntax:expression: pattern $VAR(@) "^[[:alnum:]][-_[:alnum:]]*$"
+                   ; "only alpha-numeric policy name allowed"
+create: /opt/vyatta/sbin/vyatta-qos.pl --create-policy $VAR(.) $VAR(@)
+delete: /opt/vyatta/sbin/vyatta-qos.pl --delete-policy $VAR(@)
+end: /opt/vyatta/sbin/vyatta-qos.pl --apply-policy $VAR(@)
diff --git a/templates/traffic-policy/fair-blue/node.tag/description/node.def b/templates/traffic-policy/fair-blue/node.tag/description/node.def
new file mode 100644
index 0000000..c0e6cce
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.tag/description/node.def
@@ -0,0 +1,2 @@
+type: txt
+help: Description for queuing policy
diff --git a/templates/traffic-policy/fair-blue/node.tag/penalty/burst/node.def b/templates/traffic-policy/fair-blue/node.tag/penalty/burst/node.def
new file mode 100644
index 0000000..c4efacd
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.tag/penalty/burst/node.def
@@ -0,0 +1,4 @@
+type: u32
+help: Burst size (packets)
+syntax:expression: $VAR(@) > 0; "Burst must be greater than zero"
+val_help: u32:1-4294967295; Burst size in packets
diff --git a/templates/traffic-policy/fair-blue/node.tag/penalty/node.def b/templates/traffic-policy/fair-blue/node.tag/penalty/node.def
new file mode 100644
index 0000000..15b40ed
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.tag/penalty/node.def
@@ -0,0 +1 @@
+help: Penalty box for non-responsive aggregates
diff --git a/templates/traffic-policy/fair-blue/node.tag/penalty/rate/node.def b/templates/traffic-policy/fair-blue/node.tag/penalty/rate/node.def
new file mode 100644
index 0000000..c7e87a9
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.tag/penalty/rate/node.def
@@ -0,0 +1,4 @@
+type: u32
+help: Penalty rate (packets per second)
+syntax:expression: $VAR(@) > 0; "Penalty rate must be greater than zero"
+val_help: u32:1-4294967295; "Penalty rate in packets per second"
diff --git a/templates/traffic-policy/fair-blue/node.tag/queue-limit/node.def b/templates/traffic-policy/fair-blue/node.tag/queue-limit/node.def
new file mode 100644
index 0000000..9f2b313
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.tag/queue-limit/node.def
@@ -0,0 +1,4 @@
+type: u32
+help: Hard maximum queue size (packets)
+syntax:expression: $VAR(@) > 0;  "Queue limit must be greater than zero"
+val_help: u32:1-4294967295; Queue size in packets
diff --git a/templates/traffic-policy/fair-blue/node.tag/queue-target/node.def b/templates/traffic-policy/fair-blue/node.tag/queue-target/node.def
new file mode 100644
index 0000000..ed8ddf3
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.tag/queue-target/node.def
@@ -0,0 +1,4 @@
+type: u32
+help: Target queue size (packets)
+syntax:expression: $VAR(@) > 0;  "Queue target must be greater than zero"
+val_help: u32:1-4294967295; Target queue size in packets
diff --git a/templates/traffic-policy/fair-blue/node.tag/queue-type/node.def b/templates/traffic-policy/fair-blue/node.tag/queue-type/node.def
new file mode 100644
index 0000000..c3e613f
--- /dev/null
+++ b/templates/traffic-policy/fair-blue/node.tag/queue-type/node.def
@@ -0,0 +1,8 @@
+type: txt
+default: "fair-queue"
+syntax:expression: $VAR(@) in "fair-queue", "priority", "drop-tail";\
+                   "Unknown queue-type"
+help: Queue type for default traffic
+val_help: fair-queue; Stochastic Fair Queue (SFQ)
+val_help: drop-tail; First-In-First-Out (FIFO)
+val_help: priority; Priority queueing based on DSCP
diff --git a/templates/traffic-policy/shaper/node.tag/class/node.tag/queue-type/node.def b/templates/traffic-policy/shaper/node.tag/class/node.tag/queue-type/node.def
index 6b44648..2771022 100644
--- a/templates/traffic-policy/shaper/node.tag/class/node.tag/queue-type/node.def
+++ b/templates/traffic-policy/shaper/node.tag/class/node.tag/queue-type/node.def
@@ -1,6 +1,6 @@
 type: txt
 default: "fair-queue"
-syntax:expression: $VAR(@) in "fair-queue", "priority", "drop-tail", "random-detect";\
+syntax:expression: $VAR(@) in "fair-queue", "priority", "drop-tail", "random-detect", "fair-blue";\
                    "Unknown queue-type"
 help: Queue type for this class
 
@@ -8,4 +8,5 @@ val_help: fair-queue; Stochastic Fair Queue (SFQ)
 val_help: drop-tail; First-In-First-Out (FIFO)
 val_help: priority; Priority queueing based on DSCP
 val_help: random-detect; Random Early Detection (RED)
+val_help: fair-blue; Stochastic Fair Blue (SFB)
 
diff --git a/templates/traffic-policy/shaper/node.tag/default/queue-type/node.def b/templates/traffic-policy/shaper/node.tag/default/queue-type/node.def
index caf6818..ea3f280 100644
--- a/templates/traffic-policy/shaper/node.tag/default/queue-type/node.def
+++ b/templates/traffic-policy/shaper/node.tag/default/queue-type/node.def
@@ -1,9 +1,10 @@
 type: txt
 default: "fair-queue"
-syntax:expression: $VAR(@) in "fair-queue", "priority", "drop-tail", "random-detect";\
+syntax:expression: $VAR(@) in "fair-queue", "priority", "drop-tail", "random-detect", "fair-blue";\
                    "Unknown queue-type"
 help: Queue type for default traffic
 val_help: fair-queue; Stochastic Fair Queue (SFQ)
 val_help: drop-tail; First-In-First-Out (FIFO)
 val_help: priority; Priority queueing based on DSCP
 val_help: random-detect; Random Early Detection (RED)
+val_help: fair-blue; Stochastic Fair Blue (SFB)