Statistics
| Branch: | Tag: | Revision:

sssimulator / overlay.c @ 72616bda

History | View | Annotate | Download (5.15 KB)

1
/*
2
 * This is SSSim: the Simple & Stupid Simulator
3
 *
4
 *  Copyright (c) 2015 Luca Baldesi
5
 *
6
 *  This is free software; see gpl-3.0.txt
7
 */
8

    
9
#include <malloc.h>
10
#include <math.h>
11
#include <string.h>
12

    
13
#include <tokens.h>
14

    
15
#include "overlay.h"
16
#include "graph.h"
17
#include "sched.h"
18

    
19
void overlay_matrix_optimize(struct matrix ** A, struct matrix ** x)
20
{
21
        struct matrix * s, *IDx, *IDs, *Ds, *u, *tmp, *M, *t; 
22
        
23
        IDx = matrix_invdiag(*x);
24
        u = matrix_ones(1, matrix_num_rows(*A));
25
        tmp = matrix_multiply(IDx, *A);
26
        s = matrix_multiply(u, tmp);
27

    
28
        IDs = matrix_invdiag(s);
29
        M = matrix_multiply(tmp, IDs);
30
        Ds = matrix_diag(s);
31
        t = matrix_multiply(Ds, *x);
32

    
33
        matrix_destroy(&IDx);
34
        matrix_destroy(&u);
35
        matrix_destroy(&tmp);
36
        matrix_destroy(&s);
37
        matrix_destroy(&IDs);
38
        matrix_destroy(&Ds);
39

    
40
        matrix_destroy(A);
41
        matrix_destroy(x);
42
        *A = M;
43
        *x = t;
44
}
45

    
46
void overlay_matrix_set_neighbourhood(const struct matrix * A,struct peer * peers, int n)
47
{
48
        matsize i, neigh_cnt = 0;
49

    
50
        for(i = 0; i < matrix_num_rows(A); i++)
51
                if (matrix_element_get(A, i, n) > 0)
52
                        neigh_cnt++;
53

    
54
        peers[n].neigh_size = neigh_cnt;
55
        peers[n].neighbour = malloc(neigh_cnt * sizeof(struct peer *));
56
        peers[n].neighbour_prob = malloc(neigh_cnt * sizeof(double));
57

    
58
        neigh_cnt = 0;
59
        for(i = 0; i < matrix_num_rows(A); i++)
60
                if (matrix_element_get(A, i, n) > 0)
61
                {
62
                        peers[n].neighbour[neigh_cnt] = &(peers[i]);
63
                        peers[n].neighbour_prob[neigh_cnt] = matrix_element_get(A, i, n);
64
                        //fprintf(stderr, "[DEBUG] neigh_prob: %f\n", matrix_element_get(A, i, n));
65
                        neigh_cnt++;
66
                }
67
}
68

    
69
struct peer * overlay_from_edgefile(const char * graphfile, int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)
70
{
71
        struct matrix * A, *offers;
72
        char ** inputfile;
73
        char input[200];
74
        uint32_t ntok;
75
        struct peer * peers = NULL;
76
        int n, c;
77

    
78
        strcpy(input, graphfile);
79
        inputfile = tokens_create(input, ',', &ntok);
80
        A = matrix_from_edgefile(inputfile[0]);
81
        if (A)
82
        {
83
                matrix_stochastify(A);
84
                if (tokens_check(inputfile, ntok, "optimize") >= 0)
85
                {
86
//                        fprintf(stderr, "[DEBUG] optimizing overlay..\n");
87
                        offers = matrix_eigencentrality(A, NULL);
88
                        overlay_matrix_optimize(&A, &offers);
89
                } else
90
                {
91
//                        fprintf(stderr, "[DEBUG] uniform overlay..\n");
92
                        offers = matrix_ones(matrix_num_rows(A), 1);
93
                }
94
                tokens_destroy(&inputfile, ntok);
95

    
96
                *npeers = matrix_num_rows(A); 
97
                *neigh_size = -1;
98
                #ifdef NO_BUFFER
99
                    *buffer = nchunks;
100
                #else
101
                    if (*buffer == 0) {
102
                      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));
103
                    }
104
                #endif
105
                printf("\nN=%d\n", *npeers - 1); // one is the source..
106
                if (trace) fprintf(trace,"\n N=%d\n", *npeers);
107
                peers = malloc((*npeers) * sizeof(struct peer));
108
                if (peers == NULL) {
109
                        perror("MAlloc");
110
                        return NULL;
111
                }
112
                memset(peers, 0, (*npeers) * sizeof(struct peer));
113
                for (n = 0; n < *npeers; n++) {
114
                        peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
115
                        peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
116
                        peers[n].num_chunks = nchunks;
117
                        peers[n].buf_size = *buffer;
118
                        peers[n].buf_mask = peers[n].buf_size - 1;
119
                        for (c = 0; c <  *buffer; c++) {
120
                                peers[n].chunks[c] = NULL;
121
                                peers[n].recv_chunks[c] = NULL;
122
                                peers[n].latest_not_needed = -1; //CACHE latest_not_needed
123
                        }
124
                        peers[n].id = n;
125
                        peers[n].offer_rate = matrix_element_get(offers, n, 0);
126
                        //fprintf(stderr, "[DEBUG] offer_rate: %f\n", matrix_element_get(offers, n, 0));
127
                        overlay_matrix_set_neighbourhood(A, peers, n);
128
                }
129

    
130
                (*npeers) -= 1; // we take off one peer to be used as source
131
                memmove(source, &(peers[*npeers]), sizeof(struct peer));
132
                source->id = -1;
133
                source_set(source->neighbour, source->neigh_size, nchunks);
134
                matrix_destroy(&A);
135
                matrix_destroy(&offers);
136
        }
137
        return peers;
138
}
139

    
140
struct peer * overlay_from_parameters(int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)
141
{
142
  int n, c;
143
  struct peer * peers;
144
  printf("\nN=%d\n", *npeers);
145
  if (trace) fprintf(trace,"\n N=%d\n", *npeers);
146
  peers = malloc((*npeers) * sizeof(struct peer));
147
  if (peers == NULL) {
148
    perror("MAlloc");
149
    return NULL;
150
  }
151
  memset(peers, 0, (*npeers) * sizeof(struct peer));
152

    
153
    *playout_delay = ilogb(2*(*npeers)-1)+1;
154
#ifdef NO_BUFFER
155
    *buffer = nchunks;
156
#else
157
    if (*buffer == 0) {
158
      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));
159
    }
160
#endif
161
    for (n = 0; n < *npeers; n++) {
162
      peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
163
      peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
164
      peers[n].num_chunks = nchunks;
165
      peers[n].buf_size = *buffer;
166
      peers[n].buf_mask = peers[n].buf_size - 1;
167
      for (c = 0; c < /*num_chunks*/ *buffer; c++) {
168
        peers[n].chunks[c] = NULL;
169
        peers[n].recv_chunks[c] = NULL;
170
        peers[n].latest_not_needed = -1; //CACHE latest_not_needed
171
      }
172
      peers[n].id = n;
173
      peers[n].neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, n);
174
      peers[n].neigh_size = *neigh_size;
175
    }
176
    source->neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, -1);
177
    source->neigh_size = *neigh_size;
178
    source_set(source->neighbour, source->neigh_size, nchunks);
179
    return peers;
180
}