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