ZBPFRC - Zero-buffer Path-flow Routing Control
==============================================

  Routing control is a traffic engineering methodology that unifies the
  advantages of dynamic and static routing. A routing controller periodically
  observes the network state and intervenes at the routers so that traffic
  always flows along optimal routes (where `optimality' is defined freely by
  the network operator) and without violating link capacities. The two
  fundamental building blocks of a routing controller are a network model,
  which describes the dynamic behavior of the network as the function of the
  ingress traffic, the topology and the routing action, plus a constrained,
  state feedback controller, which regulates traffic flows. A routing
  controller is completely precomputed: the state space is divided into
  disjunct control regions, each of which having a routing action associated
  with it, and the controller, after learning the network state, finds the
  region the actual network state resides in and applies the corresponding
  routing action.

  A powerful means of routing control is the ZBPFRC. It uses the Zero-buffer
  Path-flow model for capacitated networks (a linear, time-invariant,
  discrete, dynamic network model) and applies a constrained, linear, state
  feedback receding horizon controller to it. In this setting, the control
  regions are disjunct polyhedral partitions of the space of ingress traffic
  configurations (the throughput polytope), and the control action is a
  continuous, affine function of the state.

  This distribution contains the Matlab code that accompanies the paper

      Gábor Rétvári and Gábor Németh
      On Optimal Multipath Rate-adaptive Routing
      ISCC'10

  It contains network models, code for computing routing controllers and
  visualizing their behavior, sample inputs, etc., as referenced in the
  paper.


CONTENTS

  The distribution contains the following files

    -- README                    # this README file
    -- local                     # some local versions of files in MPT
       |-- mpt_getPWQLyapFct.m           (see CAVEATS)
       |-- mpt_getStabFeedback.m
       `-- mpt_plotTimeTrajectory.m
    -- networks                  # network topologies
       |-- nsf_2_1.ncf           # nsf.* is the National Science Foundation
       |-- nsf_2_10.ncf          # network as decribed in
       |-- nsf_2_2.ncf
       |-- nsf_2_3.ncf           # B. Chinoy and H. W. Braun, "The National
       |-- nsf_2_4.ncf           # Science Foundation Network", Tech. Rep.,
       |-- nsf_2_5.ncf           # CAIDA, 1992.
       |-- nsf_2_6.ncf
       |-- nsf_2_7.ncf           # The actual file format is a rather self-
       |-- nsf_2_8.ncf           # explanatory `Network Configuration Format'.
       |-- nsf_2_9.ncf
       |-- nsf_3_1.ncf           # In the name `nsf_P_K.ncf', P means the
       |-- nsf_3_10.ncf          # number of paths per source-destination pair,
       |-- nsf_3_2.ncf           # and K is the number of such source-
       |-- nsf_3_3.ncf           # destination pairs.
       |-- nsf_3_4.ncf
       |-- nsf_3_5.ncf
       |-- nsf_3_6.ncf
       |-- nsf_3_7.ncf
       |-- test1.ncf             # Sample network of Fig. 1 in NCF format
       `-- test2.ncf             # A slightly more interesting network
    -- networks_matlab           # The above topologies, converted to a format
       |-- nsf_2_1.m             # understandable by Matlab and the ZBPFRC code.
       |-- nsf_2_10.m            # The format is as follows:
       |-- nsf_2_2.m             # P{k}: the path-set for the k-th session,
       |-- nsf_2_3.m             #       a PxM matrix, where P is the number of
       |-- nsf_2_4.m             #       paths for this session and M is the
       |-- nsf_2_5.m             #       number of links. Every column holds the
       |-- nsf_2_6.m             #       path/arc incidence vector of a path
       |-- nsf_2_7.m             # u:    the capacity vector
       |-- nsf_2_8.m             # Options.Pbnd_A, Options.Pbnd_b: the throughput
       |-- nsf_2_9.m             #       polytope
       |-- nsf_3_1.m
       |-- nsf_3_2.m
       |-- nsf_3_3.m
       |-- nsf_3_4.m
       |-- nsf_3_5.m
       |-- nsf_3_6.m
       |-- nsf_3_7.m
       |-- test1.m
       `-- test2.m
    -- zbpfoc.m                  # Matlab code to compute ZBPFRCs
    -- prepare_zbpfoc.m          # Interface to MPT controllers
    -- goodness.m                # The goodness measure, as described in (3)

  The main function is `zbpfoc'. This function implements the method for
  computing the ZBPF routing controller as described in Section III. C) of
  the paper by solving the mp-LP (P)-(C3).  It takes a network topology (only
  implicitly, as it actually uses the set of paths assigned for the
  source-destination pairs instead of the topology per se) and capacity
  vector and computes the corresponding controller. The controller is a valid
  MPT controller, so all the built-in bells-and-whistles of MPT apply to it
  (`sim', `simplot', `mpt_studio', etc.). By default, it computes a 1-step
  ZBPFRC, but it can compute receding horizon controllers for arbitrary
  control horizon, has options to impose polyhedral constraints on the state
  space, multiple objective functions for path costs, weak terminal set
  constraints, etc.

  Auxiliary functions are `prepare_zbpfoc', which prepares the data
  structures for the built-in controller computation code of MPT, and
  `goodness', which measures the quality of a controller.

  For the exact parametrization of these functions, type `help zbpfoc', etc.
  at your Matlab prompt.

  Mind the name of the main utility: `zbpfoc'! This differs from the actual
  name used throughput the paper due to historical reasons that will not be
  detailed here.


INSTALLATION

  1. Install Matlab as usual. Install the Control System Toolbox and the
     Optimization Tooolbox (both are installed as default)

  2. Install the Multi-parametric Toolbox from here:

         http://control.ee.ethz.ch/~mpt

     as described in the corresponding install guide.

  3. Add the M-files from this distribution (`zbpfoc.m', `prepare_zbpfoc.m'
     and `goodness.m') to your Matlab working directory, or anywhere else
     under the Matlab path (see Matlab/File/Set Path).

  4. Copy some network topologies from the `networks_matlab' directory
     to somewhere under the Matlab path. Try `test1.m' for starter.

  5. If necessary, overwrite some of the original files in MPT with the
     versions given in the `local' directory of this distribution (see
     CAVEATS).

EXAMPLE

  In the first example, we design a nice ZBPF Routing Controller for the
  sample network of `test1.ncf'. First, we initialize MPT, then we load the
  network (the function will put data structures describing the network to
  the WorkSpace), we compute the controller using `zbpfoc' and then plot some
  simulation results.

    % Initialize MPT, set debug level and verbosity according to your taste
    >> mpt_init('debug_level', 2, 'verbose', 2)
    % Load a network configuration (take care of setting your Matlab Path!)
    % and put path set 'P' an capacity vector 'u' to your Matlab Workspace
    >> test1
    % Compute the corresponding ZBPF Routing Controller
    >> ctrl = zbpfoc(P, u, Options)
    % Simulate the system and plot results, setting some random initial state
    >> simplot(ctrl, 2 * rand(2,1))
    % Compute the goodness of your controller
    >> goodness(ctrl,1)

  We can also use the original MPT functions to compute controllers. In this
  case, we use `prepare_zbpfoc' instead of `zbpfoc'. This does not compute
  the controller right away, it just prepares the data necessary for MPT and
  then we call `mpt_control'. For the exact parametrization of `mpt_control',
  see the excellent MPT Manual.

    >> mpt_init('debug_level', 2, 'verbose', 2)
    >> test1
    % sysStruct describes the system, probStruct the required controller
    >> [sysStruct, probStruct] = prepare_zbpfoc(P, u, Options)
    % MPT computes the corresponding controller
    >> ctrl = mpt_control(sysStruct, probStruct)
    % Simulate
    >> simplot(ctrl, 2 * rand(2,1))


PLATFORMS

  This software has been thoroughly tested on a Windows XP guest running on a
  VirtualBox/Linux host, using Matlab 7.5.0 (Release 2007b) and the
  Multi-Parametric Toolbox Version 2.6.2. It should run without problems
  natively on Linux (if you manage to compile the numerous MEX files in MPT)
  and any on any platforms as well (but see CAVEATS below).


CAVEATS

  For some still unknown reason, I have had several, perfectly reproducible
  hangs in SeDuMI (this may be due to me running Matlab in a Windows XP
  guest, or some other reason). If you keep on experiencing crashes when
  calling `mpt_control', then replace the following files with the ones from
  the `local' directory of this distribution:

    <MPT>/extras/analysis/mpt_getPWQLyapFct.m  -> local/mpt_getPWQLyapFct.m
    <MPT>/extras/control/mpt_getStabFeedback.m -> local/mpt_getStabFeedback.m

  where <MPT> is the directory where you installed MPT (typically,
  `matlab/toolbox/mpt').

  Additionally, if you want some nice simulation outputs, then overwrite

    <MPT>/extras/graphics/mpt_plotTimeTrajectory.m ->
                                               local/mpt_plotTimeTrajectory.m

  The local version will replace the 4th plot in the simulation output of
  `simplot'. This plot originally shows the evolution of a hybrid system as
  it transitions from one dynamics to another. Since we have only one
  dynamics, the local version rather shows the actual control region and
  control action as time passes.


CONTACT

  If in problem, contact <RETVARI <-AT-> TMIT <-DOT-> BME <-DOT-> HU>


COPYRIGHT AND LICENCE

  Copyright (C) 2008 Gabor Retvari. All rights reserved.

  This program is free software; you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by the Free
  Software Foundation; either version 2.1 of the License, or (at your option)
  any later version.

  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.

  You should have received a copy of the GNU General Public License along
  with this library; if not, write to the
  Free Software Foundation, Inc.,
  59 Temple Place, Suite 330,
  Boston, MA  02111-1307  USA




Download ZBPFRC

Back