Skip to content

Extending YATES

One of the primary objectives of YATES is to enable rapid prototyping of TE systems. This page will demonstrate how to implement a new TE algorithm with YATES.

Example: Valiant Load Balancing (VLB)

VLB: Suppose we want to implement a TE system based on Valiant Load Balancing (VLB) with YATES, and compare it with other TE approaches. Essentially, VLB routes traffic by forwarding flows from a source to a destination through random intermediate nodes. It takes the shortest paths to route from source to intermediate nodes, and from intermediate nodes to the destination.

Background

Most functionality for implementing TE algorithms in YATES resides in lib/routing. A TE algorithm module has the following interface:

module type Algorithm = sig
  (* Main function that computes the new routing scheme *)
  val solve : topology -> demands -> scheme

  (* Optionally, initialize a TE module with a routing scheme *)
  val initialize : scheme -> unit

  (* Optionally, augment the TE algorithm with a way to handle failures *)
  val local_recovery : scheme -> topology -> failure -> demands -> scheme
end

This interface uses types defined in lib/types/. The most essential function in this interface is the solve function. solve computes a routing scheme (of type scheme) given a topology (of type topology) and traffic matrices (of type demands). A routing scheme is a mapping from source-destination pairs to a probability distribution over paths between those pairs.

(* Map from source-destination pair to it's required bandwidth *)
type demands = float SrcDstMap.t

(* Map from source-destination pair to a probability distribution over paths *)
type scheme = (float PathMap.t) SrcDstMap.t

The weight (or probability) of path p in the distribution represents the relative fraction of the source-destination traffic that should be sent over p.

Implementation

We start with writing a YATES TE module (Vlb.ml) that implements the interface shown above.

The solve function for VLB first pre-computes all-pair shortest paths for every pair of nodes using existing implementations provided in YATES.

(* All shortest paths for all node pairs *)
let mpapsp = all_pairs_multi_shortest_path topo in

(* Get one shortest path per node pair *)
let spf_table = SrcDstMap.fold mpapsp ~init:SrcDstMap.empty
  ~f:(fun ~key:(v1,v2) ~data:_ acc ->
      match get_random_path v1 v2 topo mpapsp with
      | None -> acc
      | Some rand_path ->
        SrcDstMap.set acc ~key:(v1,v2) ~data:rand_path) in

(* Returns a shortest path from a given source to a given destination *)
let find_path src dst = SrcDstMap.find_exn spf_table (src,dst) in

Then, we iterate over the pairs of source-destination nodes and for each pair, we compute the set of paths through all possible detour nodes, and create a probability distribution over these paths, assigning uniform probability for each path.

(* A function that computes the shortest path through a given detour node.
   It returns the concatenation of shortest src -> det and det -> dst nodes. *)
let route_thru_detour src det dst =
  remove_cycles (find_path src det @ find_path det dst) in

(* Compute uniform probability distribution over paths through every possible
   intermediate node for a given source and destination. *)
let vlb_pps src dst =
  (* Find paths through all possible detours *)
  let (paths, num_detours) =
    Topology.fold_vertexes
      (fun v (p_acc, ns_acc) ->
         match device v with
         | Node.Switch ->
           (* Only route through switches *)
           ((route_thru_detour src v dst)::p_acc, ns_acc +. 1.)
         | _ ->
           (p_acc, ns_acc) ) topo ([], 0.) in
  (* Generate uniform probability distribution *)
  List.fold_left paths ~init:PathMap.empty ~f:(fun acc path ->
      add_or_increment_path acc path (1.0 /. num_detours)) in

Finally, we create a routing scheme that maps each source-destination pair to its corresponding distribution over paths.

(* Folding over mpapsp just to get all src-dst pairs *)
SrcDstMap.fold mpapsp ~init:SrcDstMap.empty ~f:(fun ~key:(v1,v2) ~data:_ acc ->
    match (device v1, device v2) with
    | (Node.Host, Node.Host) ->
      SrcDstMap.set acc ~key:(v1,v2) ~data:(vlb_pps v1 v2)
    | _ -> acc)

See lib/routing/Vlb.ml for the complete implementation.

To make the YATES simulator aware of the new TE algorithm, we need to perform a few more steps. We create an interface Vlb.mli for the new VLB module. This interface is basically the same as we showed earlier. We create an identifier Vlb for this module by adding it to Yates_Routing.ml and Yates_Routing.mli. The VLB routing module is now ready. For use within the simulator, we would also need to add VLB as a solver type (see here) and define any helper functions and a CLI flag. This new TE system can be used by simply specifying it's flag in the YATES CLI. For example, to compare ECMP and VLB on the example Abilene topology, we can run:

$ make && make install
$ yates data/topologies/abilene.dot \
  data/demands/actual/abilene.txt data/demands/predicted/abilene.txt \
  data/hosts/abilene.hosts -ecmp -vlb