sssimulator / sched.c @ 4123e0f7
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 |
} |