Statistics
| Branch: | Tag: | Revision:

sssimulator / overlay.c @ cac522ea

History | View | Annotate | Download (6.12 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
        //fprintf(stderr, "[DEBUG] set neigh of %d, of size %d\n", peers[n].id, neigh_cnt);
59
        neigh_cnt = 0;
60
        for(i = 0; i < matrix_num_rows(A); i++)
61
                if (matrix_element_get(A, i, n) > 0)
62
                {
63
                        peers[n].neighbour[neigh_cnt] = &(peers[i]);
64
                        peers[n].neighbour_prob[neigh_cnt] = matrix_element_get(A, i, n);
65
                        //fprintf(stderr, "[DEBUG] neigh_prob: %f\n", matrix_element_get(A, i, n));
66
                        neigh_cnt++;
67
                }
68
}
69

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

    
79
        strcpy(input, graphfile);
80
        inputfile = tokens_create(input, ',', &ntok);
81
        A = matrix_from_edgefile(inputfile[0]);
82
        if (A)
83
        {
84
                *npeers = matrix_num_rows(A); 
85
                matrix_make_bidir(A);
86

    
87
                for(n = 0; n < *npeers; n++) // we do not want edges to the source
88
                        matrix_element_set(A, source_id, n, 0);
89

    
90
                matrix_stochastify(A);
91
                if (tokens_check(inputfile, ntok, "optimize") >= 0)
92
                {
93
                        fprintf(stderr, "Optimizing overlay..\n");
94
                        offers = matrix_eigencentrality(A, NULL);
95
                        overlay_matrix_optimize(&A, &offers);
96
                } else
97
                {
98
//                        fprintf(stderr, "[DEBUG] uniform overlay..\n");
99
                        offers = matrix_ones(matrix_num_rows(A), 1);
100
                }
101
                tokens_destroy(&inputfile, ntok);
102

    
103
                *neigh_size = -1;
104
                peers = malloc((*npeers) * sizeof(struct peer));
105
                if (peers == NULL) {
106
                        perror("MAlloc");
107
                        return NULL;
108
                }
109
                memset(peers, 0, (*npeers) * sizeof(struct peer));
110

    
111
                *playout_delay = ilogb(2*(*npeers)-1)+1;
112
                #ifdef NO_BUFFER
113
                    *buffer = nchunks;
114
                #else
115
                    if (*buffer == 0) {
116
                      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));
117
                    }
118
                #endif
119
                for (n = 0; n < *npeers; n++) {
120
                        peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
121
                        peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
122
                        peers[n].num_chunks = nchunks;
123
                        peers[n].buf_size = *buffer;
124
                        peers[n].buf_mask = peers[n].buf_size - 1;
125
                        for (c = 0; c <  *buffer; c++) {
126
                                peers[n].chunks[c] = NULL;
127
                                peers[n].recv_chunks[c] = NULL;
128
                                peers[n].latest_not_needed = -1; //CACHE latest_not_needed
129
                        }
130
                        peers[n].id = n;
131
                        peers[n].offer_rate = 1.0/matrix_element_get(offers, n, 0);
132
                        //fprintf(stderr, "[DEBUG] offer_rate: %f\n", matrix_element_get(offers, n, 0));
133
                        overlay_matrix_set_neighbourhood(A, peers, n);
134
                }
135

    
136
                (*npeers) -= 1; // we take off one peer to be used as source
137
                memmove(source, &(peers[source_id]), sizeof(struct peer));
138
                memmove(&(peers[source_id]), &(peers[*npeers]), sizeof(struct peer));
139
                source->id = -1;
140
                source_set(source->neighbour, source->neigh_size, source->neighbour_prob,  nchunks);
141
                printf("N=%d\n", *npeers); // one is the source..
142
                if (trace) fprintf(trace,"\n N=%d\n", *npeers);
143
                matrix_destroy(&A);
144
                matrix_destroy(&offers);
145
        }
146
        return peers;
147
}
148

    
149
struct peer * overlay_from_parameters(int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source)
150
{
151
  int n, c;
152
  struct peer * peers;
153
  printf("N=%d\n", *npeers);
154
  if (trace) fprintf(trace,"\n N=%d\n", *npeers);
155
  peers = malloc((*npeers) * sizeof(struct peer));
156
  if (peers == NULL) {
157
    perror("MAlloc");
158
    return NULL;
159
  }
160
  memset(peers, 0, (*npeers) * sizeof(struct peer));
161

    
162
    *playout_delay = ilogb(2*(*npeers)-1)+1;
163
#ifdef NO_BUFFER
164
    *buffer = nchunks;
165
#else
166
    if (*buffer == 0) {
167
      *buffer = pow(2, 1 + ilogb(2*(*playout_delay)-1));
168
    }
169
#endif
170
    for (n = 0; n < *npeers; n++) {
171
      peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
172
      peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *));
173
      peers[n].num_chunks = nchunks;
174
      peers[n].buf_size = *buffer;
175
      peers[n].buf_mask = peers[n].buf_size - 1;
176
      for (c = 0; c < /*num_chunks*/ *buffer; c++) {
177
        peers[n].chunks[c] = NULL;
178
        peers[n].recv_chunks[c] = NULL;
179
        peers[n].latest_not_needed = -1; //CACHE latest_not_needed
180
      }
181
      peers[n].id = n;
182
      peers[n].offer_rate = 1;
183
      peers[n].neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, n);
184
      peers[n].neighbour_prob = malloc((*neigh_size) *sizeof(double));
185
      for(c = 0; c < *neigh_size; c++)
186
      {
187
              (peers[n].neighbour_prob)[c] = 1.0/(*neigh_size);
188
        //fprintf(stderr, "[DEBUG]: loading prob for peer %d -> %f\n", peers[n].id, (peers[n].neighbour_prob)[c]);
189
      }
190
      peers[n].neigh_size = *neigh_size;
191
    }
192
    source->neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, -1);
193
    source->neigh_size = *neigh_size;
194
    source->neighbour_prob = malloc((*neigh_size) *sizeof(double));
195
    for(c = 0; c < *neigh_size; c++)
196
    {
197
            (source->neighbour_prob)[c] = 1.0/(*neigh_size);
198
        //fprintf(stderr, "[DEBUG]: loading prob for source %d -> %f\n", source->id, (source->neighbour_prob)[c]);
199
    }
200
    source_set(source->neighbour, source->neigh_size, source->neighbour_prob,  nchunks);
201
    return peers;
202
}