00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #include<stdio.h>
00020 #include<string.h>
00021 #include<stdlib.h>
00022 #include<assert.h>
00023
00024 #include "LinkScheduleEstimator.h"
00025
00026 namespace dtn {
00027
00028
00029 unsigned int **dist;
00030
00031 LinkScheduleEstimator::LinkScheduleEstimator()
00032 : Logger("LinkScheduleEstimator", "/dtn/route/linkstate/estimator")
00033 {}
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043 unsigned int
00044 LinkScheduleEstimator::entry_dist(Log &a, unsigned int a_index, unsigned int a_offset,
00045 Log &b, unsigned int b_index, unsigned int b_offset,
00046 unsigned int warping_window)
00047 {
00048 unsigned int diff=absdiff(a[a_index].start-a_offset,b[b_index].start-b_offset);
00049 unsigned int minduration=oasys::min(a[a_index].duration, b[b_index].duration);
00050 if(diff > warping_window)
00051 return minduration;
00052 else return oasys::min(diff, minduration);
00053 }
00054
00055
00056
00057
00058 unsigned int
00059 LinkScheduleEstimator::log_dist_r(Log &a, unsigned int a_index, unsigned int a_offset,
00060 Log &b, unsigned int b_index, unsigned int b_offset,
00061 unsigned int warping_window)
00062 {
00063 unsigned int mindist;
00064
00065
00066
00067
00068
00069
00070
00071 if(dist[a_index][b_index]<MAX_DIST)
00072 return dist[a_index][b_index];
00073
00074
00075 else if(a_index==0)
00076 mindist=log_dist_r(a,a_index,a_offset,
00077 b,b_index-1,b_offset,
00078 warping_window);
00079
00080 else if(b_index==0)
00081 mindist=log_dist_r(a,a_index-1,a_offset,
00082 b,b_index,b_offset,
00083 warping_window);
00084
00085 else {
00086 mindist = oasys::min(oasys::min(log_dist_r(a,a_index-1,a_offset,
00087 b,b_index-1,b_offset,warping_window),
00088 log_dist_r(a,a_index-1,a_offset,
00089 b,b_index,b_offset,warping_window)),
00090 log_dist_r(a,a_index,a_offset,
00091 b,b_index-1,b_offset,warping_window));
00092 }
00093
00094 unsigned int entrydist=entry_dist(a,a_index,a_offset,
00095 b,b_index,b_offset,
00096 warping_window);
00097
00098 dist[a_index][b_index]=entrydist+mindist;
00099
00100 return dist[a_index][b_index];
00101 }
00102
00103
00104
00105
00106
00107 unsigned int
00108 LinkScheduleEstimator::log_dist(Log &a, unsigned int a_offset,
00109 Log &b, unsigned int b_offset,
00110 unsigned int warping_window, int print_table)
00111 {
00112
00113
00114
00115 dist=(unsigned int**)malloc(a.size()*sizeof(unsigned int));
00116 for(unsigned int i=0;i<a.size();i++)
00117 {
00118 dist[i]=(unsigned int*)malloc(b.size()*sizeof(unsigned int));
00119
00120 for(unsigned int j=0;j<b.size();j++)
00121 dist[i][j]=MAX_DIST;
00122 }
00123
00124 dist[0][0]=entry_dist(a,0,a_offset,b,0,b_offset,warping_window);
00125
00126
00127
00128
00129
00130 unsigned int d;
00131 for(unsigned int i=0;i<oasys::min(a.size(),b.size());i++)
00132 d=log_dist_r(a,i,a_offset,b,i,b_offset,warping_window);
00133
00134
00135 d=log_dist_r(a,a.size()-1,a_offset,
00136 b,b.size()-1,b_offset,
00137 warping_window);
00138
00139 if(print_table)
00140 {
00141 for(unsigned int i=0;i<a.size();i++)
00142 {
00143 log_debug("%d\t| ",a[a.size()-i-1].start-a_offset);
00144 for(unsigned int j=0;j<b.size();j++)
00145 {
00146 log_debug("%d\t",dist[a.size()-i-1][j]);
00147 }
00148 log_debug("\n");
00149 }
00150 log_debug("---------------------------------------------------\n\t ");
00151 for(unsigned int i=0;i<b.size();i++)
00152 log_debug("%d\t| ",b[i].start-b_offset);
00153 log_debug("\n\t ");
00154 for(unsigned int i=0;i<b.size();i++)
00155 log_debug("%d\t| ",b[i].duration);
00156 log_debug("\n\n");
00157 }
00158
00159 free(dist);
00160
00161 return d;
00162 }
00163
00164
00165
00166
00167
00168
00169 unsigned int
00170 LinkScheduleEstimator::autocorrelation(Log &log, unsigned int phase, int print_table)
00171 {
00172 Log clone(log.size());
00173 for(unsigned int i=phase;i<log.size();i++) {
00174 clone[i-phase].start=log[i].start-log[phase].start;
00175 clone[i-phase].duration=log[i].duration;
00176 }
00177
00178 for(unsigned int i=0;i<phase;i++) {
00179 clone[i+(log.size()-phase)].start=
00180 log[i].start+log[log.size()-1].start-log[phase-1].start;
00181 clone[i+(log.size()-phase)].duration=log[i].duration;
00182 }
00183
00184 unsigned int d = log_dist(log, log[0].start,
00185 clone, clone[0].start,
00186 (int)((log[log.size()].start+
00187 log[log.size()].duration)*WARPING_WINDOW),
00188 print_table);
00189
00190
00191 return d;
00192 }
00193
00194 void
00195 LinkScheduleEstimator::print_log(Log &log, int relative_dates)
00196 {
00197 unsigned int offset=0;
00198 if(relative_dates)
00199 offset=log[0].start;
00200
00201 for(unsigned int i=0;i<log.size();i++) {
00202 log_debug("(%d, %d)",log[i].start-offset,log[i].duration);
00203 if(i<log.size()-1)
00204 log_debug(", ");
00205 }
00206 log_debug("\n");
00207 }
00208
00209
00210
00211
00212
00213
00214
00215 LinkScheduleEstimator::Log* LinkScheduleEstimator::generate_samples(Log &schedule,
00216 unsigned int log_size,
00217 unsigned int start_jitter,
00218 double duration_jitter)
00219 {
00220 Log *output = new Log(log_size);
00221 unsigned int schedule_index = 0;
00222 unsigned int start_time_offset = 0;
00223 for(unsigned int i=0;i<log_size;i++)
00224 {
00225
00226
00227
00228
00229
00230 if(schedule_index == schedule.size() - 1) {
00231 start_time_offset = start_time_offset +
00232 schedule[schedule.size()-1].start +
00233 schedule[schedule.size()-1].duration;
00234 schedule_index = 0;
00235 }
00236
00237 (*output)[i].start = (unsigned int) oasys::max((unsigned int)0,(start_time_offset +
00238 schedule[schedule_index].start -
00239 start_jitter / 2 +
00240 (unsigned int)(random() % start_jitter)));
00241
00242 unsigned int duration_jitter_abs = (int)(duration_jitter*
00243 schedule[schedule_index].duration);
00244
00245 (*output)[i].duration=schedule[schedule_index].duration -
00246 duration_jitter_abs / 2 +
00247 random() % duration_jitter_abs;
00248 schedule_index++;
00249 }
00250
00251 return output;
00252 }
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262 unsigned int
00263 LinkScheduleEstimator::estimate_period(Log &log)
00264 {
00265 int* autoc=(int*)malloc(log.size()*sizeof(int));
00266 for(unsigned int i=1;i<log.size();i++) {
00267 autoc[i]=autocorrelation(log,i,0);
00268 }
00269
00270
00271 unsigned int candidate=1;
00272 for(unsigned int i=1;i<log.size();i++)
00273 if(autoc[i]<autoc[candidate])
00274 candidate=i;
00275
00276 unsigned int candidate2=1;
00277 for(unsigned int i=1;i<log.size();i++)
00278 if(i!=candidate && autoc[i]<autoc[candidate2])
00279 candidate2=i;
00280
00281
00282 double should_be_2=log[candidate2].start/(double)log[candidate].start;
00283
00284 if(absdiff(should_be_2,2)<2*PERIOD_TOLERANCE)
00285 return (int)(log[candidate2].start+log[candidate].start)/3;
00286 else
00287 return 0;
00288 }
00289
00293 unsigned int
00294 LinkScheduleEstimator::seek_to_before_date(Log &log, unsigned int date)
00295 {
00296 for( unsigned int i=0 ; i < log.size() ; i++ )
00297 if( log[i].start > date )
00298 return (unsigned int)oasys::max(0,(int)i-1);
00299 return 0;
00300 }
00301
00305 unsigned int
00306 LinkScheduleEstimator::closest_entry_to_date(Log &log, unsigned int date)
00307 {
00308 unsigned int i=seek_to_before_date(log, date);
00309
00310 if(absdiff(log[i].start,date)<absdiff(log[i+1].start,date))
00311 return i;
00312 else
00313 return i+1;
00314
00315 return 0;
00316 }
00317
00318
00319 LinkScheduleEstimator::Log*
00320 LinkScheduleEstimator::clone_subsequence(Log &log, unsigned int start, unsigned int len)
00321 {
00322 Log *out = new Log(len);
00323 for(unsigned int i=0;i<len;i++) {
00324 (*out)[i].start=log[i+start].start;
00325 (*out)[i].duration=log[i+start].duration;
00326 }
00327
00328 return out;
00329 }
00330
00331
00332
00333
00334
00335 unsigned int
00336 LinkScheduleEstimator::badness_of_match(Log &pattern,
00337 Log &log,
00338 unsigned int warping_window,
00339 unsigned int period)
00340 {
00341 unsigned int badness=0;
00342 for(unsigned int date=0; date<log[log.size()-pattern.size()].start; date+=period)
00343 {
00344 unsigned int start = closest_entry_to_date(log,date);
00345 Log* subsequence = clone_subsequence(log, start,
00346 closest_entry_to_date(log,date) -
00347 start+1);
00348
00349 unsigned int change=log_dist(pattern,
00350 pattern[0].start,
00351 *subsequence,
00352 date,
00353 warping_window,
00354 0);
00355
00356 delete subsequence;
00357 badness+=change;
00358 }
00359 return badness;
00360 }
00361
00362
00363
00364
00365
00366
00367 LinkScheduleEstimator::Log*
00368 LinkScheduleEstimator::extract_schedule(Log &log, unsigned int period_estimate)
00369 {
00370 Log* best_pattern=0;
00371 unsigned int best_pattern_badness=100000000;
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381 for(unsigned int date=0;
00382 date<=(log[log.size()-1].start-period_estimate);
00383 date+=period_estimate)
00384 {
00385 unsigned int pattern_index=closest_entry_to_date(log,date);
00386 unsigned int pattern_len = closest_entry_to_date(log,date+period_estimate) -
00387 pattern_index+1;
00388 Log* pattern = clone_subsequence(log, pattern_index, pattern_len);
00389
00390 unsigned int badness=badness_of_match(*pattern,
00391 log,
00392 (int)(period_estimate*WARPING_WINDOW),
00393 period_estimate);
00394
00395 if(badness < best_pattern_badness)
00396 {
00397 if(best_pattern)
00398 delete best_pattern;
00399
00400 best_pattern = pattern;
00401 best_pattern_badness = badness;
00402 }
00403 else delete pattern;
00404 }
00405
00406 log_debug("And the best pattern is (%d): \n",best_pattern_badness);
00407 print_log(*best_pattern, 1);
00408
00409 return new Log(*best_pattern);
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456 }
00457
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467 unsigned int
00468 LinkScheduleEstimator::refine_period(LinkScheduleEstimator::Log &log,
00469 unsigned int period_estimate)
00470 {
00471 unsigned int sum=0;
00472 int count=-1;
00473 int count2=0;
00474
00475
00476 for(unsigned int date=0 ;
00477 date<=(log[log.size()-1].start-period_estimate) ;
00478 date+=period_estimate)
00479 {
00480 unsigned int pattern_index=closest_entry_to_date(log,date);
00481 sum+=log[pattern_index].start;
00482 count++;
00483 count2+=count;
00484 }
00485
00486 return sum/count2;
00487 }
00488
00492 LinkScheduleEstimator::Log*
00493 LinkScheduleEstimator::find_schedule(LinkScheduleEstimator::Log &log)
00494 {
00495
00496
00497
00498 unsigned int period = estimate_period(log);
00499
00500 if(period) {
00501
00502 period = refine_period(log, period);
00503
00504 return extract_schedule(log, period);
00505 }
00506 else return 0;
00507 }
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609 }