Dccast.java

package dccast;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeMap;

/**
 *
 * @author Mohammad Noormohammadpour
 */

public class Dccast {
    
    // network topology
    public static int Nodes;
    public static Topology topo;
    
    public static final Distribution dist = new Distribution();
    public static final int latest_arrival = 1000;
    
    // traffic arrival
    public static double copies_per_request; // destinations per P2MP
    public static double network_lambda; // lambda * (n)
    public static double lambda; 
    
    // job size
    public static final double mu = 0.1;
    public static final double kappa = 0.5;
    public static double demand_min = 0.1; 
    public static double demand_max = 0.9; 
    
    // global statistics and data    
    private static double worst_finish = 0, avg_finish = 0, median_finish = 0;
    private static double total_bw = 0.0;
    private static long time = 0; // time marker (real-time)
    private static long req_count = 0;
    private static double total_demand = 0;
    
    public static TreeMap<Long, Double> req_finishes = new TreeMap<>();
    public static TreeMap<Long, Double> req_arrivals = new TreeMap<>();
    public static TreeMap<Long, Double> req_demands = new TreeMap<>();
    public static TreeMap<Long, Double> req_demands_org = new TreeMap<>();
    
    ///////////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) 
    {
        // generate a topology or use a fixed topology
        // sets # of nodes
        getTopo(20); 
        
        // # of destinations per P2MP transfer
        copies_per_request = 5;

        // arrival rate at central controller
        network_lambda = 1;

        // used by traffic generator
        lambda = network_lambda / Nodes;

        Requests_P2MP reqs = genTraffic_P2MP(Nodes, lambda);
        
        do_simulation_dccast(reqs.clone());
    }
    
    public static Topology getTopo5FullMesh() {
        Nodes = 10;
        topo = new Topology(Nodes);
        
        // setup network topology
        topo.add(0, 5);
        topo.add(1, 6);
        topo.add(2, 7);
        topo.add(3, 8);
        topo.add(4, 9);
        
        topo.add(5, 0);
        topo.add(6, 1);
        topo.add(7, 2);
        topo.add(8, 3);
        topo.add(9, 4);
        
        topo.add(5, 6);
        topo.add(6, 5);
        topo.add(5, 7);
        topo.add(7, 5);
        topo.add(8, 5);
        topo.add(5, 8);
        topo.add(9, 5);
        topo.add(5, 9);
        topo.add(7, 6);
        topo.add(6, 7);
        topo.add(8, 6);
        topo.add(6, 8);
        topo.add(9, 6);
        topo.add(6, 9);
        topo.add(8, 7);
        topo.add(7, 8);
        topo.add(9, 7);
        topo.add(7, 9);
        topo.add(8, 9);
        topo.add(9, 8);
        
        return topo;
    }
    
    public static Topology getTopoGscale() {
        Nodes = 12;
        topo = new Topology(Nodes);
        
        // simulate the GScale Network from Google       
        // new topology & flows list
        // 12 nodes and 19 bidirectional links
        topo.add(0, 1);
        topo.add(1, 2);
        topo.add(0, 4);
        topo.add(2, 3);
        topo.add(2, 5);
        topo.add(3, 4);
        topo.add(4, 5);
        topo.add(5, 7);
        topo.add(3, 6);
        topo.add(3, 7);
        topo.add(5, 6);
        topo.add(6, 7);
        topo.add(8, 10);
        topo.add(8, 9);
        topo.add(9, 10);
        topo.add(7, 9);
        topo.add(6, 10);
        topo.add(9, 11);
        topo.add(10, 11);
        topo.add(1, 0);
        topo.add(2, 1);
        topo.add(4, 0);
        topo.add(3, 2);
        topo.add(5, 2);
        topo.add(4, 3);
        topo.add(5, 4);
        topo.add(7, 5);
        topo.add(6, 3);
        topo.add(7, 3);
        topo.add(6, 5);
        topo.add(7, 6);
        topo.add(10, 8);
        topo.add(9, 8);
        topo.add(10, 9);
        topo.add(9, 7);
        topo.add(10, 6);
        topo.add(11, 9);
        topo.add(11, 10);
        
        return topo;
    }
    
    public static Topology getTopo(int n) {
        Nodes = n;
        topo = new Topology(Nodes);
        Random rand = new Random();
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 2; j++) {
                int k = Math.abs(rand.nextInt()) % (n-1);
                topo.add(i, (i + k + 1) % n);
                topo.add((i + k + 1) % n, i);
            }
            
            topo.add(i, (i + 1) % n);
            topo.add((i + 1) % n, i);
        }
        
        return topo;
    }
      
    public static long tik() {
        time = System.currentTimeMillis();
        return time;
    }
    
    public static long toc() {
        return (System.currentTimeMillis() - time);
    }
    
    public static Requests_P2MP genTraffic_P2MP(int Nodes, double lambda)
    {
        long req_id = 0;
        Requests_P2MP reqs = new Requests_P2MP();
        Random rand = new Random();
        rand.setSeed(System.nanoTime());
        
        for(int i = 0; i < Nodes; i++) 
        {
            // generate traffic as requested 
            double[][] ij_requests = dist.genPoisson(
                    lambda, 
                    mu, 
                    latest_arrival, 
                    demand_min, 
                    demand_max, 
                    kappa,
                    false); // exponential job size (true -> uniform)

            for(double[] req : ij_requests)
            {                
                HashSet<Integer> set = new HashSet<>();
                
                while(set.size() < copies_per_request) {
                    int rnd = ((i+1) + rand.nextInt(Nodes - 2))%(Nodes);
                    set.add(rnd);
                }
                              
                reqs.add(req_id, i, new ArrayList<>(set), req[1], req[0], 0);
                
                req_id++;
            } 
        }
        
        return reqs; 
    }
    
    public static void update_env(Requests_P2MP reqs) {
        Requests_P2MP cloned = reqs.clone();
        req_count = cloned.size();
        while(cloned.size() > 0) {
            Requests_P2MP.Req_P2MP p2mp = cloned.fetchReq();
            req_arrivals.put(p2mp.id, p2mp.arrival);
            req_demands.put(p2mp.id, p2mp.volume);
            req_demands_org.put(p2mp.id, p2mp.volume);
            total_demand += p2mp.volume;
        }
        worst_finish = 0;
        avg_finish = 0;
        median_finish = 0;
        req_finishes.clear();
    }
    
    public static void init()
    {
        // init
        total_bw = 0.0;
        req_count = 0;
        total_demand = 0;
        req_arrivals.clear();
        req_demands.clear();
        req_demands_org.clear();
    }
    
    //........................................................................
    
    public static void do_simulation_dccast(Requests_P2MP reqs)
    {        
        init();
        update_env(reqs);
                
        System.out.println("\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%");
        System.out.println("Total number of requests: " + req_count);
        System.out.println("Total demand: " + total_demand);
        System.out.println("Total links: " + topo.size());
        System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%");
                
        // the network
        NetworkP2MPWeighted net = new NetworkP2MPWeighted(); 
        net.compile(topo, Nodes); 

        tik();
        int loc_time = 0;
        while(reqs.size() > 0){           
            Requests_P2MP.Req_P2MP r = reqs.fetchReq();

            if(r == null)
                break;

            while(Math.ceil(r.arrival) > loc_time){
                loc_time++;
                net.walk(req_demands);
            }

            total_bw += net.allocate(r, req_finishes);
        }

        while(net.walk(req_demands)){
            loc_time++;
        }
        
        long runtime = toc();
        
        // verify correctness
        req_demands.keySet().stream().forEach((id) -> {
            if(req_demands.get(id) > 1E-10){
                System.out.println(id + " -> " + req_demands_org.get(id) + 
                        " -> " + 
                        req_demands.get(id) +
                        ", " +
                        req_arrivals.get(id));
            }
            
            assert((-1E-10 < req_demands.get(id)) && (req_demands.get(id) < 1E-10));
        });
        
        System.out.printf("\n --------- DCCAST OVERALL OUTPUT ----------- \n");
        System.out.printf("Total Bandwidth: %.2f units (unit = timeslot duration * link capacity)\n", total_bw);
        
        ArrayList<Double> median = new ArrayList<>();
        
        for(Entry<Long, Double> e : req_finishes.entrySet()){
            avg_finish += e.getValue();
            median.add(e.getValue());
        }
        
        avg_finish /= req_finishes.size();
        
        Collections.sort(median);
        median_finish = median.get(median.size() / 2); // 50th percentile
        worst_finish = median.get((int)(median.size() * 0.99)); // 99th percentile
        
        System.out.printf("Runtime: %d ms\n", runtime);
        System.out.printf("Median Finish: %.2f slots\n", median_finish);
        System.out.printf("Tail Finish: %.2f slots\n", worst_finish);
        System.out.printf("Avg Finish: %.2f slots\n", avg_finish);
                
        System.out.println("----------- Everything went well! ------------\n"); 
    }
}