Tutorial

Getting Started

This section will show the basic usage of YATES using some TE algorithms, topologies and example demand traffic matrices already included with YATES.

Inputs

At the minimum, YATES needs the following inputs:

Topology: A topology is represented as a graph and expressed using the DOT file format in YATES. For illustration, we will use Abilene's backbone network topology. Our example topology is represented in DOT format as data/topologies/abilene.dot.
Demands: These are represented as a list (timeseries) of traffic matrices (TMs). Each TM represents the bandwidth requirement (bps) from a source to a destination at a given time. YATES expects TMs as a single file (example: data/demands/actual/abilene.txt), with each line corresponding to one TM. Each line represents the rows of the TM concatenated together. To identify which entry in the TM corresponds to a particular source and destination node pair, we also need to provide a mapping from rows/columns in the TM to the corresponding end-points in the topology (example: data/hosts/abilene.hosts. The line number of each node in this file is its index in the rows/columns of a TM). YATES supports specifying two timeseries for demands:
- one representing the operator's predicted demands based on observed traffic patterns
- the other represents the actual value of demands that occur in practice.
Each TM (one line in the demands file) corresponds to demands over a time interval (say, 5 minutes or an hour) depending on the granurality at which the operator wishes to perform traffic optimization.

For more details on inputs, see the documentation on GitHub.

Basic Usage

The following command shows how to run the YATES simulator for the above mentioned inputs and evaluates the performance of Equal-Cost Multi-Path (ECMP) based TE:

# yates <topology> <actual-demands> <predicted-demands> <host-mapping> \
#  [parameters for evaluation such as TE algorithms, budget etc.]
yates data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -ecmp

ECMP screenshot

The simulator will iterate over all the TMs in the specified demands file and generate a summary of the performance statistics in data/results/<topology>, which is data/results/abilene in this case. For instance, data/results/abilene/MaxCongestionVsIterations.dat will list the maximum link congestion (congestion or utilization of each link is the amount of traffic going over the link divided by the capacity of the link) for each TM when using ECMP. The format of all output files is almost the same - tab-separated columns with headers describing the meaning of each column.

Output files

For a complete description of the output and how to interpret various files, see README on GitHub.

Comparing TE systems

To compare multiple TE algorithms in the same run, they can be specified together as command line flags. For example, to compare ECMP, k-shortest paths (KSP) and multi-commodity flow based TE (MCF) using the same topologies and demands, we can run the following:

# yates <topology> <actual-demands> <predicted-demands> <host-mapping> \
#  [parameters for evaluation such as TE algorithms, budget etc.]
yates data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -ecmp -ksp -mcf

Note that you need to have Gurobi installed to run MCF. If you don't have Gurobi installed, skip the -mcf flag:

# yates <topology> <actual-demands> <predicted-demands> <host-mapping> \
#  [parameters for evaluation such as TE algorithms, budget etc.]
yates data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -ecmp -ksp

YATES will iterate over the sequence of TE algorithms and generate performance statistics with each TE algorithm in the same output directory as earlier.

comparison screenshot

Operational Constraints

YATES allows users to specify various operational constraints while evaluating the performance of TE algorithms. For example, one can constrain TE algorithms to use up to a specified maximum number of paths between every source-destination pair. The following command sets this path budget to 4:

yates [... CLI arguments ...] -budget 4

For instance, to run the previous comparison with a path budget of 4, we can run:

yates data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -ecmp -ksp -mcf -budget 4

Comparing Robustness

YATES can be used to simulate failures in the network and measure the robustness to TE systems to the failures. It allows specifying different (optional) mechanisms in which TE systems can react to failures, and records various performance statistics. Let's consider the same topology (abilene) again, and let's say we are interested in the case when each link is equally likely to fail. We can conduct an experiment in which we fail a unique link in the topology in each iteration, and measure the performance as follows:

yates data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -spf -ecmp -ksp -budget 4 -fail-num 1 -robust

This compared three TE systems: shortest path first (SPF), ECMP and k-shortest path (KSP) without allowing the systems to reach to failures. As a result, some fraction of traffic was dropped. This can be seen in data/results/abilene/TotalThroughputVsIterations.dat and data/results/abilene/FailureLossVsIterations.dat which show the fraction of total demand was successfully delivered or dropped due to failures, respectively.

TE systems can implement different ways to handle failures in the network. To illustrate one such approach, we can implement "local" recovery: when link failure(s) occur, we remove the paths containing the failed link(s) and re-distribute traffic over the remaining paths unaffected by failures in proportion to their original weights. YATES already implements this form of recovery. To enable this recovery to kick-in immediately on failures in the previous experiment, we can perform the following:

yates data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -spf -ecmp -ksp -budget 4 -fail-num 1 -robust \
   -lr-delay 0

More Options

YATES supports a lot of other options to specify different TE systems and generate different kinds of workloads and operational scenarios. See the help in CLI for the exhaustive list.

yates -h

Traffic Engineering Algorithms

YATES comes with various traffic engineering algorithms already implemented. Some of them include:

Name	Description
SPF	Shortest-path first
ECMP	Equal Cost Multipath
KSP	Distribute traffic equally over k-shortest paths between every source-destination pair
ED-KSP	Distribute traffic equally over edge-disjoint k-shortest paths between every source-destination pair
MCF	A multi-commodity flow based TE algorithms that minimizes the maximum link utilization (MLU)
VLB	Valiant load balancing
Räcke's oblivious routing	See "Optimal Hierarchical Decompositions for Congestion Minimization in Networks"
SMORE	Semi-oblivious traffic engineering using Räcke's oblivious routing for path selection.
and more ...	To see the complete list, run: yates -build-info

YATES allows composing modules together to build new TE systems. For example, by composing the k-shortest paths (KSP) with a restricted MCF module, one can build a TE system that uses k-shortest paths between every pair of nodes, and dynamically load balances over these set of paths depending on time-varying demands.

YATES SDN Controller

The controller performs the following functions:

compute the forwarding paths based on the TE algorithm and assign a physical network path identifier to each forwarding path,
install appropriate forwarding rules,
send the path-to-identifier mappings to each of the user-space end-host agents in the network, and
periodically gather traffic statistics from switches.

To use the controller, run it as follows:

# yates.ctrl <topology> <actual-demands> <predicted-demands> <host-mapping> \
#  [parameters for evaluation such as TE algorithms, budget etc.]
yates.ctrl data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -alg ecmp

This will compute the set of paths to be used, and start an OpenFlow SDN controller. As switches connect to the controller, it will populate the forwarding table with corresponding entries.

YATES SDN controller supports two kinds of source routing schemes: i) one uses a single tag per path; switches look at this tag to make forwarding decisions ii) and the other assigns and id to each link and encodes the path using a stack of VLAN tags; switches look at the outer most tag, and forward based on that after popping the tag header.

To see the complete description of all the options, run:

yates.ctrl -h