Statistics
| Branch: | Tag: | Revision:

sssimulator / sched.c @ master

History | View | Annotate | Download (21.1 KB)

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

    
10
#include <limits.h>
11
#include <stdlib.h>
12
#include <stdio.h>
13

    
14
#include "config.h"
15
#include "core.h"
16
#include "sched.h"
17

    
18
FILE *trace;    //trace file
19
static struct peer source;
20

    
21
#define SCHED __attribute__ ((unused)) static inline
22

    
23
///==========================================================
24
///     helper functions
25
///==========================================================
26
//avoiding duplicate transactions
27
int needs(int k, const struct peer *p)
28
{
29
#ifdef NO_BUFFER
30
  return (!p->chunks[k] && !p->recv_chunks[k]);
31
#else
32
  register unsigned int idx = k & p->buf_mask;
33

    
34
  return ((!p->chunks[idx] || (p->chunks[idx]->chunk < k)) && !p->recv_chunks[idx]);
35
#endif
36
}
37

    
38

    
39
//latest chunk not needed by the given peer (owned or in arrival)
40
//  it is almost a "latest chunk", but it also contains the ones in arrival
41
//  we use it as a prediction for the destination node!
42
//  returns: -1 if the node has no chunks, not even arriving
43
//  parameters: "t" is passed only to speed up search
44
static int latest_not_needed(struct peer *p, int t)
45
{
46
  //CACHE latest_not_needed
47
  return p->latest_not_needed;
48
}
49

    
50
//LUCA style utility
51
static int utility(struct peer *p, int t)
52
{
53
  int i, c, u;
54

    
55
  u = 0;
56
  for (c = win_left(p, t); c < win_right(p, t); c++) {
57
    if (p->recv_chunks[win_idx(p, c)] || p->chunks[win_idx(p, c)]) {
58
      for (i = 0; i < p->neigh_size; i++) {
59
        u += needs(c, p->neighbour[i]);
60
      }
61
    }
62
  }
63

    
64
  return u;
65
}
66

    
67
/* 
68
static int utility_luca(struct peer *p)
69
{
70
  int c, u;
71

72
  u = 0;
73
  for (c = win_left(p, t); c < win_right(p, t); c++) {
74
    if (p->recv_chunks[win_idx(p, c)] || p->chunks[win_idx(p, c)]) {
75
      u += N - chunks[win_idx(p, c)].received;
76
    }
77
  }
78

79
  return u;
80
}
81
*/
82

    
83
//number of useful chunks owned by a peer
84
static int num_chunks(struct peer *p, int t)
85
{
86
  int i, tot;
87

    
88
  tot = 0;
89
  for (i = 0; i < p->num_chunks; i++) {
90
    if (p->chunks[i] || p->recv_chunks[i]) tot++;
91
//    if (!comp(i)) tot += (p->chunks[i] != NULL);
92
//    if (!comp(i)) tot += (p->recv_chunks[i] != NULL);
93
  }
94

    
95
  return tot;
96
}
97

    
98
static void order_chunks(struct chunk_instance *c[], int *ordered, int num_chunks)
99
{
100
  int i;
101

    
102
  //for (i = 0; i < num_chunks; i++) chunks[i].key = (i + 1) * (chunks[i].received + 1);
103
  //for (i = 0; i < num_chunks; i++) chunks[i].key = i + chunks[i].received;
104
  for (i = 0; i < num_chunks; i++) {
105
    if (c[i]) {
106
      c[i]->key = /*i + chunks[c[i]->chunk].received */ c[i]->dl;
107
      //c[i]->key = i + chunks[c[i]->chunk].received;
108
      //c[i]->key = num_chunks - i;
109
    }
110
  }
111
  
112
  for (i = 0; i < num_chunks; i++) {
113
    int j, k, min;
114

    
115
    min = INT_MAX; k = -1;
116
    for (j = 0; j < num_chunks; j++) {
117
      if (c[j] && (c[j]->key >= 0) && (c[j]->key < min)) {
118
        min = c[j]->key; k = j;
119
      }
120
    }
121
    ordered[i] = k;
122
    if (k != -1) {
123
      c[k]->key = -1;
124
    }
125
  }
126
}
127

    
128
int is_useful(int c, struct peer *p)
129
{
130
  int i;
131

    
132
  for (i = 0; i < p->neigh_size; i++) {
133
    if (needs(c, p->neighbour[i])) {
134
      return 1;
135
    }
136
  }
137

    
138
  return 0;
139
}
140

    
141
///==========================================================
142
///     chunk selection algorithms
143
///==========================================================
144

    
145
SCHED int ordered_sched(struct peer *p, int t, struct peer *dummy)
146
{
147
  int i, ii;
148
  int ordered_chunks[p->num_chunks];
149

    
150
  order_chunks(p->chunks, ordered_chunks, p->num_chunks);
151
  for (ii = win_left(p, t); ii < win_right(p, t); ii++) {
152
    i = ordered_chunks[ii];
153
    if ((i >= 0) && p->chunks[i] && is_useful(i, p)) {
154
      return i;
155
    }
156
  }
157

    
158
  /* No useful chunk... */
159
  return -1;
160
}
161

    
162
SCHED int dl_sched(struct peer *p, int t, struct peer *dummy)
163
{
164
  int i;
165
  int max = INT_MAX, winner = -1;
166

    
167
  for (i = win_left(p, t); i < win_right(p, t); i++) {
168
    if (p->chunks[win_idx(p, i)] &&
169
        in_buffer(p, i, t) &&
170
        is_useful(i, p) && (p->chunks[win_idx(p, i)]->dl < max)) {
171
      max = p->chunks[win_idx(p, i)]->dl;
172
      winner = i;
173
    }
174
  }
175

    
176
  return winner;
177
}
178

    
179
//latest useful chunk
180
SCHED int latest_useful_chunk(struct peer *p, int t, struct peer *target)
181
{
182
  int c, j;
183
  for (c = win_right(p, t) - 1; c >= win_left(p, t); c--) {    //c:chunk to send
184
    if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {   
185
      for (j = 0; j < p->neigh_size; j++) { //j:destination node; TODO: neighbour set
186
        if (needs(c, p->neighbour[j])) {
187
          return c;
188
        }
189
      }
190
    }
191
  }
192
  //we don't have a useful chunk
193
  return -1;
194
}
195

    
196
//peer already selected, latest useful chunk
197
SCHED int dest_latest_useful_chunk(struct peer *p, int t, struct peer *target)
198
{
199
  int c;
200
  for (c = win_right(p, t) - 1; c >= win_left(p, t); c--) {    //c:chunk to send
201
    if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {   
202
      if (needs(c, target)) {
203
          return c;
204
      }
205
    }
206
  }
207
  //we don't have a useful chunk
208
  return -1;
209
}
210

    
211

    
212
//latest blind chunk
213
SCHED int latest_blind_chunk(struct peer *p, int t, struct peer *target)
214
{
215
  int c;
216
  for (c = win_right(p, t) - 1; c >= win_left(p, t); c--) {    //c:chunk to send
217
    if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {   
218
      return c;
219
    }
220
  }
221
  //we don't have a chunk
222
  return -1;
223
}
224

    
225
//earliest useful chunk
226
SCHED int earliest_useful_chunk(struct peer *p, int t)
227
{
228
  int c, j;
229
  for (c = win_left(p, t); c < win_right(p, t); c++) {    //c:chunk to send
230
    if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {   
231
      for (j = 0; j < p->neigh_size; j++) { //j:destination node; TODO: neighbour set
232
        if (needs(c, p->neighbour[j])) {
233
          return c;
234
        }
235
      }
236
    }
237
  }
238
  //we don't have a useful chunk
239
  return -1;
240
}
241

    
242
//peer already selected, earliest useful chunk
243
SCHED int dest_earliest_useful_chunk(struct peer *p, int t, struct peer *target)
244
{
245
  int c;
246
  for (c = win_left(p, t); c < win_right(p, t); c++) {    //c:chunk to send
247
    if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {   
248
      if (needs(c, target)) {
249
          return c;
250
      }
251
    }
252
  }
253
  //we don't have a useful chunk
254
  return -1;
255
}
256

    
257
//peer already selected, random useful chunk
258
SCHED int random_useful_chunk(struct peer *p, int t, struct peer *target)
259
{
260
  int c;
261
  int useful[p->num_chunks];
262
  int usefuls = 0;
263
  
264
  for (c = win_left(p, t); c < win_right(p, t); c++) {    //c:chunk to send
265
    if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
266
      if (is_useful(c, p)) {
267
        useful[usefuls++] = c;
268
      }
269
    }
270
  }
271
  if (!usefuls) {
272
    return -1;
273
  } else {
274
    return useful[(int) (usefuls * (rand() / (RAND_MAX + 1.0)))];
275
  }
276
}
277

    
278
SCHED int dest_random_useful_chunk(struct peer *p, int t, struct peer *target)
279
{
280
  int c;
281
  int useful[p->num_chunks];
282
  int usefuls = 0;
283
  
284
  for (c = win_left(p, t); c < win_right(p, t); c++) {    //c:chunk to send
285
    if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
286
      if (needs(c, target)) {
287
        useful[usefuls++] = c;
288
      }
289
    }
290
  }
291
  if (!usefuls) {
292
    return -1;
293
  } else {
294
    return useful[(int) (usefuls * (rand() / (RAND_MAX + 1.0)))];
295
  }
296
}
297

    
298
//only chunk to send
299
SCHED int only_intime_chunk(struct peer *p, int t)
300
{
301
  int c, c2 = -1;
302
  for (c = min(t, p->num_chunks - 1); c >= max(t-PO_DELAY,0); c--) {    //c:chunk to send
303
    //printf("\t time %d: peer %d checking chunk %d\n", t, p, c);
304
    if (p->chunks[c]) {   
305
      return c;
306
      //if (c2 >= 0) 
307
      //  printf("Warning: time %d: peer %d has more chunks to send: %d and %d\n", t, p, c2, c);
308
      //else  
309
      //  c2 = c;
310
    }
311
  }
312
  return c2;
313
}
314

    
315

    
316
///==========================================================
317
///     peer selection algorithms
318
///==========================================================
319

    
320
//random peer
321
SCHED struct peer *random_peer(struct peer *p, int t)
322
{
323
  return p->neighbour[(int)(p->neigh_size * (rand() / (RAND_MAX + 1.0)))];
324
}
325

    
326
//most deprived peer
327
SCHED struct peer *most_deprived_peer(struct peer *p, int t)
328
{
329
  int n, k, i;
330
  n = p->num_chunks * p->neigh_size + 1; k = -1;
331
  
332
  for (i = 0; i < p->neigh_size; i++) {
333
    if (num_chunks(p->neighbour[i], t) < n) {
334
      n = num_chunks(p->neighbour[i], t);
335
      k = i;
336
    }
337
  }
338
  
339
  return p->neighbour[k];
340
}
341

    
342
//most deprived peer
343
SCHED struct peer *most_deprived_peer_random(struct peer *p, int t)
344
{
345
  int n, i, j, r;
346
  n = p->num_chunks * p->neigh_size + 1; j = 0;
347
  
348
  for (i = 0; i < p->neigh_size; i++) {
349
    if (num_chunks(p->neighbour[i], t) == n) j++; //j: number of peers on being most deprived
350
    if (num_chunks(p->neighbour[i], t) < n) {
351
      n = num_chunks(p->neighbour[i], t);
352
      j = 1;
353
    }
354
  }
355
  
356
  r = (int) (j * (rand() / (RAND_MAX + 1.0)));  //r: random choice
357

    
358
  for (i = 0, j = 0; i < p->neigh_size; i++) {
359
    if (num_chunks(p->neighbour[i], t) == n && j++ == r ) {
360
      return p->neighbour[i];
361
    }
362
  }
363
  exit(-1);
364
}
365

    
366
//chunk already selected, peer that needs it
367
SCHED struct peer *ch_useful_peer(struct peer *p, int t, int c)
368
{
369
  int i;
370
  
371
  for (i = 0; i < p->neigh_size; i++) {
372
    if (needs(c, p->neighbour[i])) {
373
      return p->neighbour[i];
374
    }
375
  }
376
  //fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
377
  //exit(-1);
378
  return NULL;
379
}
380

    
381
//chunk already selected, weighted random choice between peers that need it
382
SCHED struct peer *ch_useful_peer_weighted_random(struct peer *p, int t, int c)
383
{
384
  int i;
385
  double tot_prob, cum_prob;
386
  double rand_value;
387
  struct peer * neigh = NULL;
388
    
389
  for (tot_prob = 0, i = 0; i < p->neigh_size; i++) {
390
    if (needs(c, p->neighbour[i])) {
391
//        fprintf(stderr, "[DEBUG]: %d,%d -> %f\n", c, p->id, (p->neighbour_prob)[i]);
392
      tot_prob += (p->neighbour_prob)[i];
393
    }
394
  }
395
  
396
  rand_value = ((rand() / (RAND_MAX + 1.0)) * tot_prob); 
397
//  fprintf(stderr, "[DEBUG]: rand is: %f\n", rand_value);
398

    
399
  i = 0;
400
  cum_prob = 0;
401
  while(tot_prob && i < p->neigh_size && neigh == NULL)
402
  {
403
        if (needs(c, p->neighbour[i])) 
404
                cum_prob += (p->neighbour_prob)[i];
405
        if (cum_prob >= rand_value)
406
                neigh = (p->neighbour)[i];
407
        i++;
408
  }
409

    
410
  if (!tot_prob)
411
        fprintf(stderr, "[WARNING]: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p->id, t);
412
  else if (!neigh)
413
                fprintf(stderr, "[WARNING]: chunk %d was selected but no neighbours of %d can been selected!!\n", c, p->id);
414

    
415
  return neigh;
416
}
417

    
418
//chunk already selected, random choice between peers that need it
419
SCHED struct peer *ch_useful_peer_random(struct peer *p, int t, int c)
420
{
421
  int i, j, r;
422
    
423
  for (i = 0, j = 0; i < p->neigh_size; i++) {
424
    if (needs(c, p->neighbour[i])) {
425
      j++;
426
    }
427
  }
428
  
429
  if (!j) {
430
    //fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
431
    //exit(-1);
432
    return NULL;
433
  }
434
  
435
  r = (int) (j * (rand() / (RAND_MAX + 1.0)));  //r: random choice
436

    
437
  for (i = 0, j = 0; i < p->neigh_size; i++) {
438
    if (needs(c, p->neighbour[i]) && j++ == r ) {
439
      return p->neighbour[i];
440
    }
441
  }
442

    
443
  return NULL;
444
}
445

    
446
//chunk already selected, most deprived peer that needs it
447
SCHED struct peer *ch_most_deprived_peer(struct peer *p, int t, int c)
448
{
449
  int n, k, i;
450
  n = p->num_chunks * p->neigh_size + 1; k = -1;
451
  
452
  for (i = 0; i < p->neigh_size; i++) {
453
    if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) < n) {
454
      n = num_chunks(p->neighbour[i], t);
455
      k = i;
456
    }
457
  }
458
  if ( k==-1 ){
459
    //fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
460
    //exit(-1);
461
  }
462
  return p->neighbour[k];
463
}
464

    
465
//chunk already selected, random choice between most deprived peers that need it
466
SCHED struct peer *ch_most_deprived_peer_random(struct peer *p, int t, int c)
467
{
468
  int n, i, j, r;
469
  n = p->num_chunks * p->neigh_size + 1;
470
  
471
  for (i = 0, j = 0; i < p->neigh_size; i++) {
472
    if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) == n) j++;
473
    if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) < n) {
474
      n = num_chunks(p->neighbour[i], t);
475
      j = 1;
476
    }
477
  }
478
  
479
  if ( j==0 ){
480
    //fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
481
    //exit(-1);
482
    return NULL;
483
  }
484

    
485
  r = (int) (j * (rand() / (RAND_MAX + 1.0)));  //r: random choice
486

    
487
  for (i = 0, j = 0; i < p->neigh_size; i++) {
488
    if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) == n && j++ == r ) {
489
      return p->neighbour[i];
490
    }
491
  }
492
  
493
  return NULL;
494
}
495

    
496
//node that has nothing to do in the next turn
497
SCHED struct peer *free_peer(struct peer *p, int t)
498
{
499
  int n, j, busy;
500
  
501
  for (n = 0; n < p->neigh_size; n++) {
502
    busy = 0;
503
    for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+2,0); j--) {
504
      //fprintf(trace,"\ttime %d: peer %d needs chunk %d? %d\n", t, n, j, needs(n,j));
505
      if (!needs(j,p->neighbour[n])) {
506
        //fprintf(trace,"\ttime %d: peer %d busy because of chunk %d\n", t, n, j);
507
        busy = 1;
508
        break;
509
      }
510
    }
511
    if (!busy) {
512
      return p->neighbour[n];
513
    }
514
  }
515
  return NULL;
516
}
517

    
518
//node that has nothing to do in the next turn
519
SCHED struct peer *ch_free_peer_or_deadline(struct peer *p, int t, int c)
520
{
521
  int n, n0, j, n_busy;
522
 
523
  //see if there is a node who will have nothing to send
524
  for (n0 = 0; n0 < p->neigh_size; n0++) {
525
    n = (p->id + n0) % p->neigh_size;
526
    n=n0;
527
    n_busy = 0;
528
    for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+2,0); j--) {
529
      //fprintf(trace,"\t\ttime %d: peer %d needs chunk %d? %d\n", t, n, j, needs(j,n));
530
      if (!needs(j,p->neighbour[n])) {
531
        //fprintf(trace,"\t\ttime %d: peer %d busy because of chunk %d\n", t, n, j);
532
        n_busy = 1;
533
        break; // cycle for chunks
534
      }
535
    }
536
    if (!n_busy && needs (c,p->neighbour[n])) {
537
      return p->neighbour[n];
538
    }
539
  }
540

    
541
  //see if there is a node who has only the oldest chunk to send
542
  for (n0 = 0; n0 < p->neigh_size; n0++) {
543
    n = (p->id + n0) % p->neigh_size;
544
    n=n0;
545
    n_busy = 0;
546
    for (j = min(t, p->num_chunks - 1); j > max(t-PO_DELAY+2,0); j--) {
547
      //fprintf(trace,"\t\ttime %d: peer %d needs chunk %d? %d\n", t, n, j, needs(j,n));
548
      if (!needs(j,p->neighbour[n])) {
549
        //fprintf(trace,"\t\ttime %d: peer %d busy because of chunk %d\n", t, n, j);
550
        n_busy = 1;
551
        break; // cycle for chunks
552
      }
553
    }
554
    if (!n_busy && needs (c,p->neighbour[n])) {
555
      return p->neighbour[n];
556
    }
557
  }
558

    
559
  for (n0 = 0; n0 < p->neigh_size; n0++) {
560
    n = (p->id + n0) % p->neigh_size;
561
    if (needs(c,p->neighbour[n])) {
562
      return p->neighbour[n];
563
    }
564
  }
565

    
566
  return NULL;
567
}
568

    
569

    
570
//node that has nothing to do in the next turn
571
SCHED struct peer *ch_free_peer_or_deadline2(struct peer *p, int t, int c)
572
{
573
  int n, j, n_busy;
574
 
575
  //otherwise, search for someone who needs it and has nothing to do in the next turn
576
  for (n = 0; n < p->neigh_size; n++) {
577
    n_busy = 0;
578
    for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+2,0); j--) {
579
      if (!needs(j,p->neighbour[n])) {
580
        n_busy = 1;
581
        break; // cycle for chunks
582
      }
583
    }
584
    if (!n_busy && needs (c,p->neighbour[n])) {
585
      if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: nothing to do in t+1\n", p->id, c, c-t, n);
586
      return p->neighbour[n];
587
    }
588
  }
589

    
590
  //otherwise, search for someone who needs it and has nothing to do in t+2
591
  for (n = 0; n < p->neigh_size; n++) {
592
    n_busy = 0;
593
    for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+3,0); j--) {
594
      if (!needs(j,p->neighbour[n])) {
595
        n_busy = 1;
596
        break; // cycle for chunks
597
      }
598
    }
599
    if (!n_busy && needs (c,p->neighbour[n])) {
600
      if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: nothing to do in t+2 \n", p->id, c, c-t, n);
601
      return p->neighbour[n];
602
    }
603
  }
604

    
605
  // send to anyone who needs it
606
  for (n = 0; n < p->neigh_size; n++) {
607
    if (needs(c,p->neighbour[n])) {
608
      if (trace) fprintf(trace,"\ttime %d: peer %d -(chunk %d,%d)-> %d, reason: remaining \n", t, p->id, c, c-t, n);
609
      return p->neighbour[n];
610
    }
611
  }
612

    
613
  return NULL;
614
}
615

    
616
//node that has nothing to do in the next turn
617
SCHED struct peer *ch_almost_free_peer(struct peer *p, int t, int c)
618
{
619
  int n;
620

    
621
  //send to the one who has nothing to send in the next turn (t+1)
622
  for (n = 0; n < p->neigh_size; n++) {
623
    if (needs (c,p->neighbour[n]) && latest_not_needed(p->neighbour[n], t) < max(t-PO_DELAY+2,0)) {
624
        if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: node has nothing to send \n", p->id, c, c-t, n);
625
        return p->neighbour[n];
626
    }
627
  }
628

    
629
  //has nothing to send in the turn after the next one (t+2)
630
  for (n = 0; n < p->neigh_size; n++) {
631
    if (needs (c,p->neighbour[n]) && latest_not_needed(p->neighbour[n],t) < max(t-PO_DELAY+3,0)) { 
632
        if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: node has nothing to send in t+2 \n", p->id, c, c-t, n);
633
        return p->neighbour[n];
634
    }
635
  }
636

    
637
  // send to anyone who needs it
638
  for (n = 0; n < p->neigh_size; n++) {
639
    if (needs(c,p->neighbour[n])) {
640
      if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: send anyway \n", p->id, c, c-t, n);
641
      return p->neighbour[n];
642
    }
643
  }
644

    
645
  return NULL;
646
}
647

    
648
SCHED struct peer *least_utility(struct peer *p, int t, int c)
649
{
650
  int n = INT_MAX, winner = -1;
651
  int i;
652

    
653
  for (i = 0; i < p->neigh_size; i++) {
654
    if (needs(c, p->neighbour[i])) {
655
      int u = utility(p->neighbour[i], t);
656
      if (u < n) {
657
        n = u;
658
        winner = i;
659
      }
660
    }
661
  }
662

    
663
  if (winner >= 0) {
664
    return p->neighbour[winner];
665
  }
666

    
667
  return NULL;
668
}
669

    
670
//nodes in order of when they will be free
671
SCHED struct peer *ch_earliest_free_peer(struct peer *p, int t, int c)
672
{
673
  int n, winner;
674
  int min_latest_not_needed = p->num_chunks;
675
  int l;        //cache latest_not_needed(n,t)
676

    
677
  winner = -1;  //the winner node
678
  for (n = 0; n < p->neigh_size; n++) {
679
    if (needs (c,p->neighbour[n])) {
680
      l = latest_not_needed(p->neighbour[n],t);
681
      if (l < min_latest_not_needed) {
682
        //if (trace) fprintf(trace,"\t\tPeer %d: (chunk %d,%d) latest_not_needed=%d  \n", n, c, c-t, l);
683
        min_latest_not_needed = l;
684
        winner = n;
685
      }
686
    }
687
  }
688
  if (winner >= 0) {
689
    if (trace) fprintf(trace,"\tPeer %d, t: %d: (chunk %d,%d) ---> %d\n", p->id, t, c, c-t,  p->neighbour[winner]->id);
690
    return p->neighbour[winner];
691
  }
692

    
693
  return NULL;
694
}
695

    
696

    
697

    
698
///==========================================================
699
///     peer & chunk selection algorithms
700
///==========================================================
701

    
702
//node: destination peer & chunk selection algorithm at peer p (push)
703
void peer_send_c_p(struct peer *p, int t, int *chunk, struct peer **target)
704
{
705
  *chunk = chunk_sched(p, t, NULL);
706
  if (*chunk < 0) {
707
    if (trace) fprintf(trace, "\tPeer %d: Idle (no chunk to send)\n", p->id);
708
    *target = NULL;
709

    
710
    return;
711
  }
712

    
713
  *target = peer_sched(p, t, *chunk);
714
  if (*target == NULL) {
715
    if (trace) fprintf(trace, "\tPeer %d: Idle (no peer that needs chunk %d)\n", p->id, *chunk);
716
    return;
717
  }
718
  
719
  if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, *chunk, (*target)->id);
720
}
721

    
722
//node: destination peer & chunk selection algorithm at peer p (push)
723
void peer_send_p_c(struct peer *p, int t, int *chunk, struct peer **target)
724
{
725
  *target = peer_sched(p, t, t);
726
  if (*target < 0) {
727
    if (trace) fprintf(trace, "\tPeer %d: Idle (no peer to send to)\n", p->id);
728
    return;
729
  }
730

    
731
  *chunk = chunk_sched(p, t, *target);
732
  if (*chunk < 0) {
733
    if (trace) fprintf(trace, "\tPeer %d: Idle (no chunk that %d needs)\n", p->id, (*target)->id);
734
    *target = NULL;
735
    return;
736
  }
737
  
738
  if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, *chunk, (*target)->id);
739
}
740

    
741
void peer_send_chunk(struct peer *p, int t, int *chunk, struct peer *target)
742
{
743
  *chunk = chunk_sched(p, t, target);
744
  if (*chunk < 0) {
745
    if (trace) fprintf(trace, "\tPeer %d: Idle (no chunk that %d needs)\n", p->id, (target)->id);
746
    return;
747
  }
748
  
749
  if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, *chunk, (target)->id);
750
}
751

    
752
/* Should be probably merged with peer_send_c_p */
753
void peer_send_utility(struct peer *p, int t, int *chunk, struct peer **target)
754
{
755
  int i, ii;
756
  int ordered_chunks[p->num_chunks];
757

    
758
  *target = NULL;
759
  order_chunks(p->chunks, ordered_chunks, p->num_chunks);
760
  for (ii = 0; ii < p->num_chunks; ii++) {
761
    i = ordered_chunks[ii];
762
    if ((i >= 0) && p->chunks[i]) {
763
      *target = least_utility(p, t, i);
764
      if (*target != NULL) {
765
        if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, i, (*target)->id);
766
        *chunk = i;
767
        break;
768
      } else {
769
      }
770
    }
771
  }
772

    
773
  if (*target == NULL) {
774
    if (trace) fprintf(trace, "\tPeer %d: Idle\n", p->id);
775
  }
776
}
777

    
778

    
779
///==========================================================
780
///     source: chunk & peer selection algorithms
781
///==========================================================
782
//source: destination peer & chunk selection algorithm
783
//latest chunk, generic (with 3 parameter dest case "ch_")
784
void source_send(int t, struct peer **peer)
785
{
786
  *peer = NULL;
787
  if (t >= source.num_chunks) {
788
    return;
789
  }
790

    
791
  *peer = peer_sched(&source, t, t);        //use N as source's peer ID. hope it works
792

    
793
  if (trace) fprintf(trace, "\tSource: %d ---> %d\n", t, (*peer)->id);
794
}
795

    
796
void source_set(struct peer **neigh, int size, double * neigh_prob, int num_chunks)
797
{
798
  source.neighbour = neigh;
799
  source.neigh_size = size;
800
  source.id = -1;
801
  source.num_chunks = num_chunks;
802
  source.neighbour_prob = neigh_prob;
803
}