SSSim

/*

 * This is SSSim: the Simple & Stupid Simulator

 *

 *  Copyright (c) 2015 Luca Baldesi

 *

 *  This is free software; see gpl-3.0.txt

 */

#include <malloc.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <tokens.h>

#include "overlay.h"

#include "graph.h"

#include "sched.h"

extern float netload;

void overlay_matrix_optimize(struct matrix ** A, struct matrix ** x)

{

        struct matrix * s, *IDx, *IDs, *Ds, *u, *tmp, *M, *t; 

        IDx = matrix_invdiag(*x);

        u = matrix_ones(1, matrix_num_rows(*A));

        tmp = matrix_multiply(IDx, *A);

        s = matrix_multiply(u, tmp);

        IDs = matrix_invdiag(s);

        M = matrix_multiply(tmp, IDs);

        Ds = matrix_diag(s);

        t = matrix_multiply(Ds, *x);

        matrix_destroy(&IDx);

        matrix_destroy(&u);

        matrix_destroy(&tmp);

        matrix_destroy(&s);

        matrix_destroy(&IDs);

        matrix_destroy(&Ds);

        matrix_destroy(A);

        matrix_destroy(x);

        *A = M;

        *x = t;

}

void overlay_matrix_set_neighbourhood(const struct matrix * A,struct peer * peers, int n)

{

        matsize i, neigh_cnt = 0;

        for(i = 0; i < matrix_num_rows(A); i++)

                if (matrix_element_get(A, i, n) > 0)

                        neigh_cnt++;

        peers[n].neigh_size = neigh_cnt;

        peers[n].neighbour = malloc(neigh_cnt * sizeof(struct peer *));

        peers[n].neighbour_prob = malloc(neigh_cnt * sizeof(double));

        // fprintf(stderr, "[DEBUG] set neigh of %d:%p, of size %d\n", peers[n].id, &(peers[n]), neigh_cnt);

        neigh_cnt = 0;

        for(i = 0; i < matrix_num_rows(A); i++)

                if (matrix_element_get(A, i, n) > 0)

                {

                        peers[n].neighbour[neigh_cnt] = &(peers[i]);

                        peers[n].neighbour_prob[neigh_cnt] = matrix_element_get(A, i, n);

                        // fprintf(stderr, "[DEBUG] neigh: %p, neigh_prob: %f\n", &(peers[i]), matrix_element_get(A, i, n));

                        neigh_cnt++;

                }

}

void overlay_matrix_set_source(const struct matrix * A, struct peer * source, struct peer * peers, int source_id)

{

        matsize i, j, neigh_cnt = 0;

        source->id = -1;

        for(i = 0; i < matrix_num_rows(A); i++)

                if (matrix_element_get(A, i, source_id) > 0)

                        neigh_cnt++;

        source->neigh_size = neigh_cnt;

        source->neighbour = malloc(neigh_cnt * sizeof(struct peer *));

        source->neighbour_prob = malloc(neigh_cnt * sizeof(double));

        // fprintf(stderr, "[DEBUG] set neigh of %d, of size %d\n", source->id, neigh_cnt);

        neigh_cnt = 0;

        for(i = 0; i < matrix_num_rows(A); i++)

                if (matrix_element_get(A, i, source_id) > 0)

                {

                        j = i <= source_id ? i : i - 1;

                        source->neighbour[neigh_cnt] = &(peers[j]);

                        source->neighbour_prob[neigh_cnt] = matrix_element_get(A, i, source_id);

                        // fprintf(stderr, "[DEBUG] neigh: %p, prob: %f\n", &(peers[j]), matrix_element_get(A, i, source_id));

                        // fprintf(stderr, "[DEBUG] neigh_prob: %f\n", matrix_element_get(A, i, source_id));

                        neigh_cnt++;

                }

}

struct peer * overlay_from_edgefile(const char * graphfile, int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)

{

        struct matrix * A, *offers;

        char ** inputfile;

        char input[200];

        uint32_t ntok;

        struct peer * peers = NULL;

        int n, c, source_id;

        strcpy(input, graphfile);

        inputfile = tokens_create(input, ',', &ntok);

        A = matrix_from_edgefile(inputfile[0]);

        if (A)

        {

                *npeers = matrix_num_rows(A); 

                source_id = tokens_check(inputfile, ntok, "random_source") >= 0 ? (rand() % *npeers) : 0;

                matrix_make_bidir(A);

                matrix_stochastify(A);

                if (tokens_check(inputfile, ntok, "optimize") >= 0)

                {

                        printf("Optimizing overlay..\n");

                        offers = matrix_eigencentrality(A, NULL);

                        overlay_matrix_optimize(&A, &offers);

                } else

                {

//                        fprintf(stderr, "[DEBUG] uniform overlay..\n");

                        offers = matrix_ones(matrix_num_rows(A), 1);

                }

                matrix_shrink(&offers, source_id);

                matrix_divide(offers, matrix_sum_values(offers)/((*npeers - 1)*netload));

//                printf("Total number of offers: %f\n", matrix_sum_values(offers)); 

                tokens_destroy(&inputfile, ntok);

                (*npeers) -= 1; // we take off one peer to be used as source

                peers = malloc((*npeers) * sizeof(struct peer));

                if (peers == NULL) {

                        perror("MAlloc");

                        return NULL;

                }

                memset(peers, 0, (*npeers) * sizeof(struct peer));

                overlay_matrix_set_source(A, source, peers, source_id);

                source_set(source->neighbour, source->neigh_size, source->neighbour_prob, nchunks);

                matrix_shrink(&A, source_id);

                *neigh_size = -1;

                *playout_delay = ilogb(2*(*npeers)-1)+1;

                #ifdef NO_BUFFER

                    *buffer = nchunks;

                #else

                    if (*buffer == 0) {

                      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));

                    }

                #endif

                for (n = 0; n < *npeers; n++) {

                        peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));

                        peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));

                        peers[n].num_chunks = nchunks;

                        peers[n].buf_size = *buffer;

                        peers[n].buf_mask = peers[n].buf_size - 1;

                        for (c = 0; c <  *buffer; c++) {

                                peers[n].chunks[c] = NULL;

                                peers[n].recv_chunks[c] = NULL;

                                peers[n].latest_not_needed = -1; //CACHE latest_not_needed

                        }

                        peers[n].id = n;

                        peers[n].offer_rate = 1.0/matrix_element_get(offers, n, 0);

                        //fprintf(stderr, "[DEBUG] offer_rate: %f\n", matrix_element_get(offers, n, 0));

                        overlay_matrix_set_neighbourhood(A, peers, n);

                }

                printf("N=%d\n", *npeers); // one is the source..

                if (trace) fprintf(trace,"\n N=%d\n", *npeers);

                matrix_destroy(&A);

                matrix_destroy(&offers);

        }

        return peers;

}

struct peer * overlay_from_parameters(int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)

{

  int n, c;

  struct peer * peers;

  printf("N=%d\n", *npeers);

  if (trace) fprintf(trace,"\n N=%d\n", *npeers);

  peers = malloc((*npeers) * sizeof(struct peer));

  if (peers == NULL) {

    perror("MAlloc");

    return NULL;

  }

  memset(peers, 0, (*npeers) * sizeof(struct peer));

    *playout_delay = ilogb(2*(*npeers)-1)+1;

#ifdef NO_BUFFER

    *buffer = nchunks;

#else

    if (*buffer == 0) {

      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));

    }

#endif

    for (n = 0; n < *npeers; n++) {

      peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));

      peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));

      peers[n].num_chunks = nchunks;

      peers[n].buf_size = *buffer;

      peers[n].buf_mask = peers[n].buf_size - 1;

      for (c = 0; c < /*num_chunks*/ *buffer; c++) {

        peers[n].chunks[c] = NULL;

        peers[n].recv_chunks[c] = NULL;

        peers[n].latest_not_needed = -1; //CACHE latest_not_needed

      }

      peers[n].id = n;

      peers[n].offer_rate = 1;

      peers[n].neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, n);

      peers[n].neighbour_prob = malloc((*neigh_size) *sizeof(double));

      for(c = 0; c < *neigh_size; c++)

      {

              (peers[n].neighbour_prob)[c] = 1.0/(*neigh_size);

                //fprintf(stderr, "[DEBUG]: loading prob for peer %d (%d of %d) -> %f\n", peers[n].id, c, *neigh_size, (peers[n].neighbour_prob)[c]);

      }

      peers[n].neigh_size = *neigh_size;

    }

    source->neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, -1);

    source->neigh_size = *neigh_size;

    source->neighbour_prob = malloc((*neigh_size) *sizeof(double));

    for(c = 0; c < *neigh_size; c++)

    {

            (source->neighbour_prob)[c] = 1.0/(*neigh_size);

        //fprintf(stderr, "[DEBUG]: loading prob for source %d -> %f\n", source->id, (source->neighbour_prob)[c]);

    }

    source_set(source->neighbour, source->neigh_size, source->neighbour_prob,  nchunks);

    return peers;

}