Statistics
| Branch: | Tag: | Revision:

sssimulator / overlay.c @ 743e659d

History | View | Annotate | Download (7.5 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
#include "wuli.h"
20

    
21
extern float netload;
22

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
142
                (*npeers) -= 1; // we take off one peer to be used as source
143
                peers = malloc((*npeers) * sizeof(struct peer));
144
                if (peers == NULL) {
145
                        perror("MAlloc");
146
                        return NULL;
147
                }
148
                memset(peers, 0, (*npeers) * sizeof(struct peer));
149

    
150
                overlay_matrix_set_source(A, source, peers, source_id);
151
                source_set(source->neighbour, source->neigh_size, source->neighbour_prob, nchunks);
152

    
153
                matrix_shrink(&A, source_id);
154

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

    
181
                printf("N=%d\n", *npeers); // one is the source..
182
                if (trace) fprintf(trace,"\n N=%d\n", *npeers);
183
                matrix_destroy(&A);
184
                matrix_destroy(&offers);
185
        }
186
        return peers;
187
}
188

    
189
struct peer * overlay_from_parameters(int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)
190
{
191
  int n, c;
192
  struct peer * peers;
193
  printf("N=%d\n", *npeers);
194
  if (trace) fprintf(trace,"\n N=%d\n", *npeers);
195
  peers = malloc((*npeers) * sizeof(struct peer));
196
  if (peers == NULL) {
197
    perror("MAlloc");
198
    return NULL;
199
  }
200
  memset(peers, 0, (*npeers) * sizeof(struct peer));
201

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