Statistics
| Branch: | Tag: | Revision:

sssimulator / overlay.c @ master

History | View | Annotate | Download (7.29 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
#include <stdlib.h>
13

    
14
#include <tokens.h>
15

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

    
20
extern float netload;
21

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

    
31
        IDs = matrix_invdiag(s);
32
        M = matrix_multiply(tmp, IDs);
33
        Ds = matrix_diag(s);
34
        t = matrix_multiply(Ds, *x);
35

    
36
        matrix_destroy(&IDx);
37
        matrix_destroy(&u);
38
        matrix_destroy(&tmp);
39
        matrix_destroy(&s);
40
        matrix_destroy(&IDs);
41
        matrix_destroy(&Ds);
42

    
43
        matrix_destroy(A);
44
        matrix_destroy(x);
45
        *A = M;
46
        *x = t;
47
}
48

    
49
void overlay_matrix_set_neighbourhood(const struct matrix * A,struct peer * peers, int n)
50
{
51
        matsize i, neigh_cnt = 0;
52

    
53
        for(i = 0; i < matrix_num_rows(A); i++)
54
                if (matrix_element_get(A, i, n) > 0)
55
                        neigh_cnt++;
56

    
57
        peers[n].neigh_size = neigh_cnt;
58
        peers[n].neighbour = malloc(neigh_cnt * sizeof(struct peer *));
59
        peers[n].neighbour_prob = malloc(neigh_cnt * sizeof(double));
60

    
61
        // fprintf(stderr, "[DEBUG] set neigh of %d:%p, of size %d\n", peers[n].id, &(peers[n]), neigh_cnt);
62
        neigh_cnt = 0;
63
        for(i = 0; i < matrix_num_rows(A); i++)
64
                if (matrix_element_get(A, i, n) > 0)
65
                {
66
                        peers[n].neighbour[neigh_cnt] = &(peers[i]);
67
                        peers[n].neighbour_prob[neigh_cnt] = matrix_element_get(A, i, n);
68
                        // fprintf(stderr, "[DEBUG] neigh: %p, neigh_prob: %f\n", &(peers[i]), matrix_element_get(A, i, n));
69
                        neigh_cnt++;
70
                }
71
}
72

    
73
void overlay_matrix_set_source(const struct matrix * A, struct peer * source, struct peer * peers, int source_id)
74
{
75
        matsize i, j, neigh_cnt = 0;
76

    
77
        source->id = -1;
78
        for(i = 0; i < matrix_num_rows(A); i++)
79
                if (matrix_element_get(A, i, source_id) > 0)
80
                        neigh_cnt++;
81

    
82
        source->neigh_size = neigh_cnt;
83
        source->neighbour = malloc(neigh_cnt * sizeof(struct peer *));
84
        source->neighbour_prob = malloc(neigh_cnt * sizeof(double));
85

    
86
        // fprintf(stderr, "[DEBUG] set neigh of %d, of size %d\n", source->id, neigh_cnt);
87
        neigh_cnt = 0;
88
        for(i = 0; i < matrix_num_rows(A); i++)
89
                if (matrix_element_get(A, i, source_id) > 0)
90
                {
91
                        j = i <= source_id ? i : i - 1;
92
                        source->neighbour[neigh_cnt] = &(peers[j]);
93
                        source->neighbour_prob[neigh_cnt] = matrix_element_get(A, i, source_id);
94
                        // fprintf(stderr, "[DEBUG] neigh: %p, prob: %f\n", &(peers[j]), matrix_element_get(A, i, source_id));
95
                        // fprintf(stderr, "[DEBUG] neigh_prob: %f\n", matrix_element_get(A, i, source_id));
96
                        neigh_cnt++;
97
                }
98
}
99

    
100
struct peer * overlay_from_edgefile(const char * graphfile, int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)
101
{
102
        struct matrix * A, *offers;
103
        char ** inputfile;
104
        char input[200];
105
        uint32_t ntok;
106
        struct peer * peers = NULL;
107
        int n, c, source_id;
108

    
109
        strcpy(input, graphfile);
110
        inputfile = tokens_create(input, ',', &ntok);
111
        A = matrix_from_edgefile(inputfile[0]);
112
        if (A)
113
        {
114
                *npeers = matrix_num_rows(A); 
115
                source_id = tokens_check(inputfile, ntok, "random_source") >= 0 ? (rand() % *npeers) : 0;
116
                matrix_make_bidir(A);
117

    
118
                matrix_stochastify(A);
119
                if (tokens_check(inputfile, ntok, "optimize") >= 0)
120
                {
121
                        printf("Optimizing overlay..\n");
122
                        offers = matrix_eigencentrality(A, NULL);
123
                        overlay_matrix_optimize(&A, &offers);
124
                } else
125
                {
126
//                        fprintf(stderr, "[DEBUG] uniform overlay..\n");
127
                        offers = matrix_ones(matrix_num_rows(A), 1);
128
                }
129
                matrix_shrink(&offers, source_id);
130
                matrix_divide(offers, matrix_sum_values(offers)/((*npeers - 1)*netload));
131
//                printf("Total number of offers: %f\n", matrix_sum_values(offers)); 
132
                tokens_destroy(&inputfile, ntok);
133

    
134
                (*npeers) -= 1; // we take off one peer to be used as source
135
                peers = malloc((*npeers) * sizeof(struct peer));
136
                if (peers == NULL) {
137
                        perror("MAlloc");
138
                        return NULL;
139
                }
140
                memset(peers, 0, (*npeers) * sizeof(struct peer));
141

    
142
                overlay_matrix_set_source(A, source, peers, source_id);
143
                source_set(source->neighbour, source->neigh_size, source->neighbour_prob, nchunks);
144

    
145
                matrix_shrink(&A, source_id);
146

    
147
                *neigh_size = -1;
148
                *playout_delay = ilogb(2*(*npeers)-1)+1;
149
                #ifdef NO_BUFFER
150
                    *buffer = nchunks;
151
                #else
152
                    if (*buffer == 0) {
153
                      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));
154
                    }
155
                #endif
156
                for (n = 0; n < *npeers; n++) {
157
                        peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
158
                        peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
159
                        peers[n].num_chunks = nchunks;
160
                        peers[n].buf_size = *buffer;
161
                        peers[n].buf_mask = peers[n].buf_size - 1;
162
                        for (c = 0; c <  *buffer; c++) {
163
                                peers[n].chunks[c] = NULL;
164
                                peers[n].recv_chunks[c] = NULL;
165
                                peers[n].latest_not_needed = -1; //CACHE latest_not_needed
166
                        }
167
                        peers[n].id = n;
168
                        peers[n].offer_rate = 1.0/matrix_element_get(offers, n, 0);
169
                        //fprintf(stderr, "[DEBUG] offer_rate: %f\n", matrix_element_get(offers, n, 0));
170
                        overlay_matrix_set_neighbourhood(A, peers, n);
171
                }
172

    
173
                printf("N=%d\n", *npeers); // one is the source..
174
                if (trace) fprintf(trace,"\n N=%d\n", *npeers);
175
                matrix_destroy(&A);
176
                matrix_destroy(&offers);
177
        }
178
        return peers;
179
}
180

    
181
struct peer * overlay_from_parameters(int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)
182
{
183
  int n, c;
184
  struct peer * peers;
185
  printf("N=%d\n", *npeers);
186
  if (trace) fprintf(trace,"\n N=%d\n", *npeers);
187
  peers = malloc((*npeers) * sizeof(struct peer));
188
  if (peers == NULL) {
189
    perror("MAlloc");
190
    return NULL;
191
  }
192
  memset(peers, 0, (*npeers) * sizeof(struct peer));
193

    
194
    *playout_delay = ilogb(2*(*npeers)-1)+1;
195
#ifdef NO_BUFFER
196
    *buffer = nchunks;
197
#else
198
    if (*buffer == 0) {
199
      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));
200
    }
201
#endif
202
    for (n = 0; n < *npeers; n++) {
203
      peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
204
      peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
205
      peers[n].num_chunks = nchunks;
206
      peers[n].buf_size = *buffer;
207
      peers[n].buf_mask = peers[n].buf_size - 1;
208
      for (c = 0; c < /*num_chunks*/ *buffer; c++) {
209
        peers[n].chunks[c] = NULL;
210
        peers[n].recv_chunks[c] = NULL;
211
        peers[n].latest_not_needed = -1; //CACHE latest_not_needed
212
      }
213
      peers[n].id = n;
214
      peers[n].offer_rate = 1;
215
      peers[n].neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, n);
216
      peers[n].neighbour_prob = malloc((*neigh_size) *sizeof(double));
217
      for(c = 0; c < *neigh_size; c++)
218
      {
219
              (peers[n].neighbour_prob)[c] = 1.0/(*neigh_size);
220
                //fprintf(stderr, "[DEBUG]: loading prob for peer %d (%d of %d) -> %f\n", peers[n].id, c, *neigh_size, (peers[n].neighbour_prob)[c]);
221
      }
222
      peers[n].neigh_size = *neigh_size;
223
    }
224
    source->neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, -1);
225
    source->neigh_size = *neigh_size;
226
    source->neighbour_prob = malloc((*neigh_size) *sizeof(double));
227
    for(c = 0; c < *neigh_size; c++)
228
    {
229
            (source->neighbour_prob)[c] = 1.0/(*neigh_size);
230
        //fprintf(stderr, "[DEBUG]: loading prob for source %d -> %f\n", source->id, (source->neighbour_prob)[c]);
231
    }
232
    source_set(source->neighbour, source->neigh_size, source->neighbour_prob,  nchunks);
233
    return peers;
234
}