Reimplementation of WRED

Make a simpler version of WRED that acts more like Cisco.
Use Diffserv on Linux paper for example of how to use DSMARK and GRED
to achieve similar result.

4 files changed, 163 insertions, 211 deletions

diff --git a/lib/Vyatta/Qos/RandomDetect.pm b/lib/Vyatta/Qos/RandomDetect.pm
new file mode 100644
index 0000000..155b669
--- /dev/null
+++ b/lib/Vyatta/Qos/RandomDetect.pm
@@ -0,0 +1,143 @@
+# 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::RandomDetect;
+use strict;
+use warnings;
+
+require Vyatta::Config;
+use Vyatta::Qos::Util qw/getRate getAutoRate getTime/;
+
+# default values for different precedence levels
+my @default_fields = (
+    { 'min-threshold' => 9,  'max-threshold' => 18, 'mark-probability' => 1/2 },
+    { 'min-threshold' => 10, 'max-threshold' => 18, 'mark-probability' => 5/9 },
+    { 'min-threshold' => 11, 'max-threshold' => 18, 'mark-probability' => .1 },
+    { 'min-threshold' => 12, 'max-threshold' => 18, 'mark-probability' => 2/3 },
+    { 'min-threshold' => 13, 'max-threshold' => 18, 'mark-probability' => .1 },
+    { 'min-threshold' => 14, 'max-threshold' => 18, 'mark-probability' => 7/9 },
+    { 'min-threshold' => 15, 'max-threshold' => 18, 'mark-probability' => 5/6 },
+    { 'min-threshold' => 16, 'max-threshold' => 18, 'mark-probability' => 8/9 },
+);
+
+# Create a new instance based on config information
+sub new {
+    my ( $that, $config, $name ) = @_;
+    my $level = $config->setLevel();
+
+    my $rate = $config->returnValue("bandwidth");
+    die "$level bandwidth configuration missing" unless $rate;
+    my @precedence = getPrecedence( $level );
+
+    my $self = {};
+    my $class = ref($that) || $that;
+    bless $self, $class;
+
+    $self->{_rate}       = $rate;
+    $self->{_precedence} = \@precedence;
+
+    return $self;
+}
+
+sub getPrecedence {
+    my ( $level ) = @_;
+    my $config = new Vyatta::Config;
+    my @precedence;
+
+    for ( my $i = 0 ; $i <= 7 ; $i++ ) {
+	my $defaults = $default_fields[$i];
+	my %param;
+	
+	$config->setLevel("$level precedence $i");
+	foreach my $field (keys %$defaults) {
+	    my $val = $config->returnValue($field);
+
+            if ( !defined $val ) {
+		$param{$field} = $defaults->{$field};
+            } elsif ( $field eq 'mark-probability' ) {
+		$param{$field} = 1 / $val;
+            }  else {
+		$param{$field} = $val;
+            }
+        }
+	$precedence[$i] = \%param;
+    }
+
+    return @precedence;
+}
+
+sub commands {
+    my ( $self, $dev ) = @_;
+    my $root = 1;
+    my $precedence = $self->{_precedence};
+    my $rate = getAutoRate( $self->{_rate}, $dev );
+
+    # 1. setup DSMARK to convert DSCP to tc_index
+    print "qdisc add dev eth0 root handle $root: dsmark indices 1 set_tc_index\n";
+
+    # 2. use tcindex filter to convert tc_index to precedence
+    print
+ "filter add dev $dev parent $root: protocol ip prio 1 tcindex mask 0xe0 shift 5\n";
+
+    print "qdisc add dev $dev parent $root: gred setup DPs 8 default 7\n";
+
+    # set VQ parameters
+    for ( my $i = 0 ; $i <= 7 ; $i++ ) {
+	my $param = $precedence->[$i];
+	my $qmin = $param->{'min-threshold'};
+	my $qmax = $param->{'max-threshold'};
+	my $prob = $param->{'mark-probability'};
+
+        print "qdisc change dev $dev parent $root:$i gred";
+        printf " limit %dK min %dK max %dK avpkt 1K", 4 * $qmax, $qmin, $qmax;
+        printf " burst %d bandwidth %d DP %d probability %f\n",
+          ( 2 * $qmin + $qmax ) / 3, $rate, $i, $prob;
+    }
+}
+
+# Walk configuration tree and look for changed nodes
+# The configuration system should do this but doesn't do it right
+sub isChanged {
+    my ( $self, $name ) = @_;
+    my $config = new Vyatta::Config;
+
+    $config->setLevel("qos-policy random-detect $name");
+
+    return 'bandwidth' if ( $config->isChanged('bandwidth') );
+
+    my %precedenceNodes = $config->listNodeStatus('precedence');
+    while ( my ( $pred, $status ) = each %precedenceNodes ) {
+        return "precedence $pred" if ( $status ne 'static' );
+
+	my $defaults = $default_fields[0];
+        foreach my $attr (keys %$defaults) {
+            return "precedence $pred $attr"
+              if ( $config->isChanged("precedence $pred $attr") );
+        }
+    }
+
+    return;    # false
+}
+
+1;
diff --git a/lib/Vyatta/Qos/ShaperClass.pm b/lib/Vyatta/Qos/ShaperClass.pm
index c3fae16..4e0ada1 100644
--- a/lib/Vyatta/Qos/ShaperClass.pm
+++ b/lib/Vyatta/Qos/ShaperClass.pm
@@ -21,7 +21,7 @@ use warnings;
 
 require Vyatta::Config;
 use Vyatta::Qos::Match;
-use Vyatta::Qos::Util qw/getDsfield getRate RedParam/;
+use Vyatta::Qos::Util qw/getDsfield getRate/;
 
 
 sub new {
@@ -153,11 +153,27 @@ sub fifoQdisc {
 # make some assumptions to make this sane (based on LARTC)
 #   average size = 1000 bytes
 #   latency      = 100ms
+#
+#                       Bandwidth (bits/sec) * Latency (ms)
+# Maximum Threshold = -------------------------------------- 
+#   (bytes)                   8 bits/byte *  1000000 us/sec
+#
+# Minimum Threshold = Maximum Threshold / 3
+# Avpkt = Average Packet Length
+# Burst = ( 2 * MinThreshold + MaxThreshold) / ( 3 * Avpkt )
+# Limit = 4 * MaxThreshold
+#
+# These are based on Sally Floyd's recommendations:
+#  http://www.icir.org/floyd/REDparameters.txt
+#
 sub redQdisc {
     my ( $self, $dev, $rate ) = @_;
     my $avg = 1000;
     my $latency = 100000;
-    my ($qmin, $qmax, $burst, $maxp) = RedParam($rate, $latency, $avg);
+    my $qmax = ( $rate * $latency ) / 8000000;
+    my $qmin = $qmax / 3;
+    my $burst = ( 2 * $qmin + $qmax ) / ( 3 * $avg );
+    my $maxp = 0.1;
 
     my $limit = $self->{_limit};
     my $qlimit;
@@ -169,7 +185,7 @@ sub redQdisc {
 
     printf "red limit %d min %d max %d avpkt %d", $qlimit, $qmin, $qmax, $avg;
     printf " burst %d probability %f bandwidth %d ecn\n", 
-    	$prob, $burst, $maxp, $rate / 1000;
+    	$burst, $maxp, $rate / 1000;
 }
 
 my %qdiscOptions = (
diff --git a/lib/Vyatta/Qos/Util.pm b/lib/Vyatta/Qos/Util.pm
index ee1b722..7f5454d 100644
--- a/lib/Vyatta/Qos/Util.pm
+++ b/lib/Vyatta/Qos/Util.pm
@@ -21,7 +21,7 @@ use warnings;
 
 our @EXPORT =
   qw(getRate getPercent getBurstSize getProtocol getDsfield getTime getAutoRate);
-our @EXPORT_OK = qw(getIfIndex RedParam);
+our @EXPORT_OK = qw(getIfIndex);
 use base qw(Exporter);
 
 sub get_num {
@@ -319,26 +319,4 @@ sub ethtoolRate {
     return $rate;
 }
 
-# Compute parameters for RED algorithim based on bandwidth and latency
-#
-#                       Bandwidth (bits/sec) * Latency (ms)
-# Maximum Threshold = -------------------------------------- 
-#   (bytes)                   8 bits/byte *  1000000 us/sec
-#
-# Minimum Threshold = Maximum Threshold / 3
-# Avpkt = Average Packet Length
-# Burst = ( 2 * MinThreshold + MaxThreshold) / ( 3 * Avpkt )
-# Limit = 4 * MaxThreshold
-#
-# These are based on Sally Floyd's recommendations:
-#  http://www.icir.org/floyd/REDparameters.txt
-sub RedParam {
-    my ( $bandwidth, $latency, $avgpkt ) = @_;
-    my $qmax = ( $bandwidth * $latency ) / 8000000;
-    my $qmin = $qmax / 3;
-    my $burst = ( 2 * $qmin + $qmax ) / ( 3 * $avgpkt );
-
-    return ($qmin, $qmax, $burst, 0.1);
-}
-
 1;
diff --git a/lib/Vyatta/Qos/WeightedRandom.pm b/lib/Vyatta/Qos/WeightedRandom.pm
deleted file mode 100644
index 0b1dc37..0000000
--- a/lib/Vyatta/Qos/WeightedRandom.pm
+++ /dev/null
@@ -1,185 +0,0 @@
-# Weighted Random i.e. GRED (Generic Random Early Detect)
-#
-# **** 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::WeightedRandom;
-use strict;
-use warnings;
-
-require Vyatta::Config;
-require Vyatta::Qos::ShaperClass;
-use Vyatta::Qos::Util qw/getRate getAutoRate getTime RedParam/;
-
-my $wred = 'weighted-random';
-
-# Create a new instance based on config information
-sub new {
-    my ( $that, $config, $name ) = @_;
-    my $level = $config->setLevel();
-    my $rate  = $config->returnValue("bandwidth");
-    die "$level bandwidth configuration missing" unless $rate;
-
-    my @classes = _getClasses($level);
-
-    _checkClasses( $level, $rate, @classes );
-
-    my $self = {};
-    my $class = ref($that) || $that;
-    bless $self, $class;
-    $self->{_rate}    = $rate;
-    $self->{_level}   = $level;
-    $self->{_classes} = \@classes;
-
-    return $self;
-}
-
-sub _getClasses {
-    my $level = shift;
-    my @classes;
-    my $config = new Vyatta::Config;
-
-    $config->setLevel($level);
-    $config->exists("default")
-      or die "$level configuration not complete: missing default class\n";
-
-    $config->setLevel("$level default");
-    push @classes, new Vyatta::Qos::ShaperClass($config);
-    $config->setLevel($level);
-
-    foreach my $id ( $config->listNodes("class") ) {
-        $config->setLevel("$level class $id");
-        push @classes, new Vyatta::Qos::ShaperClass( $config, $id );
-    }
-
-    return @classes;
-}
-
-# Check constraints on class bandwidth values
-sub _checkClasses {
-    my $level   = shift;
-    my $rate    = shift;
-    my $default = shift;
-
-    # if auto, can't check at create must wait for policy to be applied
-    $rate = ( $rate eq "auto" ) ? undef : getRate($rate);
-    $default->rateCheck( $rate, "$level default" ) if $rate;
-
-    foreach my $class (@_) {
-        die "$class->{level} bandwidth not defined\n" unless $class->{_rate};
-        $class->rateCheck( $rate, "$level class $class->{id}" ) if $rate;
-    }
-}
-
-sub commands {
-    my ( $self, $dev ) = @_;
-    my $rate    = getAutoRate( $self->{_rate}, $dev );
-    my $classes = $self->{_classes};
-    my $default = shift @$classes;
-    my $maxid   = 1;
-
-    $default->rateCheck( $rate, "$self->{_level} default" );
-    foreach my $class (@$classes) {
-        $class->rateCheck( $rate, "$self->{_level} class $class->{id}" );
-
-        # find largest class id
-        if ( defined $class->{id} && $class->{id} > $maxid ) {
-            $maxid = $class->{id};
-        }
-    }
-
-    # fill in id of default
-    $default->{id} = ++$maxid;
-    push @$classes, $default;
-
-    print "qdisc add dev $dev handle 1: root gred";
-    printf " setup DPs %d default %d\n", $maxid+1, $maxid;
-
-    foreach my $class (@$classes) {
-        my $classbw = $class->get_rate($rate);
-        my $avg     = $class->{_avgpkt};
-        my $latency = getTime( $class->{_latency} );
-
-        my ( $qmin, $qmax, $burst, $maxp )
-	    = RedParam( $classbw, $latency, $avg );
-
-        print "qdisc change dev $dev root gred";
-	printf " prio %d", $class->{_priority} if $class->{_priority};
-        printf " limit %d min %d max %d avpkt %d probability %f", 
-		4 * $qmax, $qmin, $qmax, $avg, $maxp;
-        printf " burst %d bandwidth %d DP %d",
-		$burst, $rate, $class->{id};
-	print " probability 0.1\n";
-
-        foreach my $match ( $class->matchRules() ) {
-            $match->filter( $dev, 1, $class->{_priority} );
-            printf " flowid :%x\n", $class->{id};
-        }
-    }
-}
-
-# Walk configuration tree and look for changed nodes
-# The configuration system should do this but doesn't do it right
-sub isChanged {
-    my ( $self, $name ) = @_;
-    my $config = new Vyatta::Config;
-    my @attributes =
-      qw(bandwidth burst latency packet-length priority queue-limit);
-
-    $config->setLevel("qos-policy $wred $name");
-
-    return 'bandwidth' if ( $config->isChanged('bandwidth') );
-
-    foreach my $attr (@attributes) {
-	return "default $attr" if ( $config->isChanged("default $attr") );
-    }
-
-    my %classNodes = $config->listNodeStatus('class');
-    while ( my ( $class, $status ) = each %classNodes ) {
-        return "class $class" if ( $status ne 'static' );
-
-        foreach my $attr (@attributes) {
-            return "class $class $attr"
-              if ( $config->isChanged("class $class $attr") );
-        }
-
-        my %matchNodes = $config->listNodeStatus("class $class match");
-        while ( my ( $match, $status ) = each %matchNodes ) {
-            my $level = "class $class match $match";
-            return $level if ( $status ne 'static' );
-
-            foreach my $parm (
-                'vif',
-                'ether destination',
-                'ether source',
-                'ether protocol',
-                'interface',
-                'ip dscp',
-                'ip protocol',
-                'ip source address',
-                'ip destination address',
-                'ip source port',
-                'ip destination port'
-              )
-            {
-                return "$level $parm" if ( $config->isChanged("$level $parm") );
-            }
-        }
-    }
-
-    return;    # false
-}
-
-1;