00001
00002
00003 #include<stdio.h>
00004 #include<string.h>
00005 #include<stdlib.h>
00006 #include<assert.h>
00007
00008 #include "LinkScheduleEstimator.h"
00009
00010 namespace dtn {
00011
00012
00013 unsigned int **dist;
00014
00015 LinkScheduleEstimator::LinkScheduleEstimator()
00016 : Logger("LinkScheduleEstimator", "/dtn/route/linkstate/estimator")
00017 {}
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 unsigned int
00028 LinkScheduleEstimator::entry_dist(Log &a, unsigned int a_index, unsigned int a_offset,
00029 Log &b, unsigned int b_index, unsigned int b_offset,
00030 unsigned int warping_window)
00031 {
00032 unsigned int diff=absdiff(a[a_index].start-a_offset,b[b_index].start-b_offset);
00033 unsigned int minduration=oasys::min(a[a_index].duration, b[b_index].duration);
00034 if(diff > warping_window)
00035 return minduration;
00036 else return oasys::min(diff, minduration);
00037 }
00038
00039
00040
00041
00042 unsigned int
00043 LinkScheduleEstimator::log_dist_r(Log &a, unsigned int a_index, unsigned int a_offset,
00044 Log &b, unsigned int b_index, unsigned int b_offset,
00045 unsigned int warping_window)
00046 {
00047 unsigned int mindist;
00048
00049
00050
00051
00052
00053
00054
00055 if(dist[a_index][b_index]<MAX_DIST)
00056 return dist[a_index][b_index];
00057
00058
00059 else if(a_index==0)
00060 mindist=log_dist_r(a,a_index,a_offset,
00061 b,b_index-1,b_offset,
00062 warping_window);
00063
00064 else if(b_index==0)
00065 mindist=log_dist_r(a,a_index-1,a_offset,
00066 b,b_index,b_offset,
00067 warping_window);
00068
00069 else {
00070 mindist = oasys::min(oasys::min(log_dist_r(a,a_index-1,a_offset,
00071 b,b_index-1,b_offset,warping_window),
00072 log_dist_r(a,a_index-1,a_offset,
00073 b,b_index,b_offset,warping_window)),
00074 log_dist_r(a,a_index,a_offset,
00075 b,b_index-1,b_offset,warping_window));
00076 }
00077
00078 unsigned int entrydist=entry_dist(a,a_index,a_offset,
00079 b,b_index,b_offset,
00080 warping_window);
00081
00082 dist[a_index][b_index]=entrydist+mindist;
00083
00084 return dist[a_index][b_index];
00085 }
00086
00087
00088
00089
00090
00091 unsigned int
00092 LinkScheduleEstimator::log_dist(Log &a, unsigned int a_offset,
00093 Log &b, unsigned int b_offset,
00094 unsigned int warping_window, int print_table)
00095 {
00096
00097
00098
00099 dist=(unsigned int**)malloc(a.size()*sizeof(unsigned int));
00100 for(unsigned int i=0;i<a.size();i++)
00101 {
00102 dist[i]=(unsigned int*)malloc(b.size()*sizeof(unsigned int));
00103
00104 for(unsigned int j=0;j<b.size();j++)
00105 dist[i][j]=MAX_DIST;
00106 }
00107
00108 dist[0][0]=entry_dist(a,0,a_offset,b,0,b_offset,warping_window);
00109
00110
00111
00112
00113
00114 unsigned int d;
00115 for(unsigned int i=0;i<oasys::min(a.size(),b.size());i++)
00116 d=log_dist_r(a,i,a_offset,b,i,b_offset,warping_window);
00117
00118
00119 d=log_dist_r(a,a.size()-1,a_offset,
00120 b,b.size()-1,b_offset,
00121 warping_window);
00122
00123 if(print_table)
00124 {
00125 for(unsigned int i=0;i<a.size();i++)
00126 {
00127 log_debug("%d\t| ",a[a.size()-i-1].start-a_offset);
00128 for(unsigned int j=0;j<b.size();j++)
00129 {
00130 log_debug("%d\t",dist[a.size()-i-1][j]);
00131 }
00132 log_debug("\n");
00133 }
00134 log_debug("---------------------------------------------------\n\t ");
00135 for(unsigned int i=0;i<b.size();i++)
00136 log_debug("%d\t| ",b[i].start-b_offset);
00137 log_debug("\n\t ");
00138 for(unsigned int i=0;i<b.size();i++)
00139 log_debug("%d\t| ",b[i].duration);
00140 log_debug("\n\n");
00141 }
00142
00143 free(dist);
00144
00145 return d;
00146 }
00147
00148
00149
00150
00151
00152
00153 unsigned int
00154 LinkScheduleEstimator::autocorrelation(Log &log, unsigned int phase, int print_table)
00155 {
00156 Log clone(log.size());
00157 for(unsigned int i=phase;i<log.size();i++) {
00158 clone[i-phase].start=log[i].start-log[phase].start;
00159 clone[i-phase].duration=log[i].duration;
00160 }
00161
00162 for(unsigned int i=0;i<phase;i++) {
00163 clone[i+(log.size()-phase)].start=
00164 log[i].start+log[log.size()-1].start-log[phase-1].start;
00165 clone[i+(log.size()-phase)].duration=log[i].duration;
00166 }
00167
00168 unsigned int d = log_dist(log, log[0].start,
00169 clone, clone[0].start,
00170 (int)((log[log.size()].start+
00171 log[log.size()].duration)*WARPING_WINDOW),
00172 print_table);
00173
00174
00175 return d;
00176 }
00177
00178 void
00179 LinkScheduleEstimator::print_log(Log &log, int relative_dates)
00180 {
00181 unsigned int offset=0;
00182 if(relative_dates)
00183 offset=log[0].start;
00184
00185 for(unsigned int i=0;i<log.size();i++) {
00186 log_debug("(%d, %d)",log[i].start-offset,log[i].duration);
00187 if(i<log.size()-1)
00188 log_debug(", ");
00189 }
00190 log_debug("\n");
00191 }
00192
00193
00194
00195
00196
00197
00198
00199 LinkScheduleEstimator::Log* LinkScheduleEstimator::generate_samples(Log &schedule,
00200 unsigned int log_size,
00201 unsigned int start_jitter,
00202 double duration_jitter)
00203 {
00204 Log *output = new Log(log_size);
00205 unsigned int schedule_index = 0;
00206 unsigned int start_time_offset = 0;
00207 for(unsigned int i=0;i<log_size;i++)
00208 {
00209
00210
00211
00212
00213
00214 if(schedule_index == schedule.size() - 1) {
00215 start_time_offset = start_time_offset +
00216 schedule[schedule.size()-1].start +
00217 schedule[schedule.size()-1].duration;
00218 schedule_index = 0;
00219 }
00220
00221 (*output)[i].start = (unsigned int) oasys::max((unsigned int)0,(start_time_offset +
00222 schedule[schedule_index].start -
00223 start_jitter / 2 +
00224 (unsigned int)(random() % start_jitter)));
00225
00226 unsigned int duration_jitter_abs = (int)(duration_jitter*
00227 schedule[schedule_index].duration);
00228
00229 (*output)[i].duration=schedule[schedule_index].duration -
00230 duration_jitter_abs / 2 +
00231 random() % duration_jitter_abs;
00232 schedule_index++;
00233 }
00234
00235 return output;
00236 }
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246 unsigned int
00247 LinkScheduleEstimator::estimate_period(Log &log)
00248 {
00249 int* autoc=(int*)malloc(log.size()*sizeof(int));
00250 for(unsigned int i=1;i<log.size();i++) {
00251 autoc[i]=autocorrelation(log,i,0);
00252 }
00253
00254
00255 unsigned int candidate=1;
00256 for(unsigned int i=1;i<log.size();i++)
00257 if(autoc[i]<autoc[candidate])
00258 candidate=i;
00259
00260 unsigned int candidate2=1;
00261 for(unsigned int i=1;i<log.size();i++)
00262 if(i!=candidate && autoc[i]<autoc[candidate2])
00263 candidate2=i;
00264
00265
00266 double should_be_2=log[candidate2].start/(double)log[candidate].start;
00267
00268 if(absdiff(should_be_2,2)<2*PERIOD_TOLERANCE)
00269 return (int)(log[candidate2].start+log[candidate].start)/3;
00270 else
00271 return 0;
00272 }
00273
00277 unsigned int
00278 LinkScheduleEstimator::seek_to_before_date(Log &log, unsigned int date)
00279 {
00280 for( unsigned int i=0 ; i < log.size() ; i++ )
00281 if( log[i].start > date )
00282 return (unsigned int)oasys::max(0,(int)i-1);
00283 return 0;
00284 }
00285
00289 unsigned int
00290 LinkScheduleEstimator::closest_entry_to_date(Log &log, unsigned int date)
00291 {
00292 unsigned int i=seek_to_before_date(log, date);
00293
00294 if(absdiff(log[i].start,date)<absdiff(log[i+1].start,date))
00295 return i;
00296 else
00297 return i+1;
00298
00299 return 0;
00300 }
00301
00302
00303 LinkScheduleEstimator::Log*
00304 LinkScheduleEstimator::clone_subsequence(Log &log, unsigned int start, unsigned int len)
00305 {
00306 Log *out = new Log(len);
00307 for(unsigned int i=0;i<len;i++) {
00308 (*out)[i].start=log[i+start].start;
00309 (*out)[i].duration=log[i+start].duration;
00310 }
00311
00312 return out;
00313 }
00314
00315
00316
00317
00318
00319 unsigned int
00320 LinkScheduleEstimator::badness_of_match(Log &pattern,
00321 Log &log,
00322 unsigned int warping_window,
00323 unsigned int period)
00324 {
00325 unsigned int badness=0;
00326 for(unsigned int date=0; date<log[log.size()-pattern.size()].start; date+=period)
00327 {
00328 unsigned int start = closest_entry_to_date(log,date);
00329 Log* subsequence = clone_subsequence(log, start,
00330 closest_entry_to_date(log,date) -
00331 start+1);
00332
00333 unsigned int change=log_dist(pattern,
00334 pattern[0].start,
00335 *subsequence,
00336 date,
00337 warping_window,
00338 0);
00339
00340 delete subsequence;
00341 badness+=change;
00342 }
00343 return badness;
00344 }
00345
00346
00347
00348
00349
00350
00351 LinkScheduleEstimator::Log*
00352 LinkScheduleEstimator::extract_schedule(Log &log, unsigned int period_estimate)
00353 {
00354 Log* best_pattern=0;
00355 unsigned int best_pattern_badness=100000000;
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365 for(unsigned int date=0;
00366 date<=(log[log.size()-1].start-period_estimate);
00367 date+=period_estimate)
00368 {
00369 unsigned int pattern_index=closest_entry_to_date(log,date);
00370 unsigned int pattern_len = closest_entry_to_date(log,date+period_estimate) -
00371 pattern_index+1;
00372 Log* pattern = clone_subsequence(log, pattern_index, pattern_len);
00373
00374 unsigned int badness=badness_of_match(*pattern,
00375 log,
00376 (int)(period_estimate*WARPING_WINDOW),
00377 period_estimate);
00378
00379 if(badness < best_pattern_badness)
00380 {
00381 if(best_pattern)
00382 delete best_pattern;
00383
00384 best_pattern = pattern;
00385 best_pattern_badness = badness;
00386 }
00387 else delete pattern;
00388 }
00389
00390 log_debug("And the best pattern is (%d): \n",best_pattern_badness);
00391 print_log(*best_pattern, 1);
00392
00393 return new Log(*best_pattern);
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
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 unsigned int
00452 LinkScheduleEstimator::refine_period(LinkScheduleEstimator::Log &log,
00453 unsigned int period_estimate)
00454 {
00455 unsigned int sum=0;
00456 int count=-1;
00457 int count2=0;
00458
00459
00460 for(unsigned int date=0 ;
00461 date<=(log[log.size()-1].start-period_estimate) ;
00462 date+=period_estimate)
00463 {
00464 unsigned int pattern_index=closest_entry_to_date(log,date);
00465 sum+=log[pattern_index].start;
00466 count++;
00467 count2+=count;
00468 }
00469
00470 return sum/count2;
00471 }
00472
00476 LinkScheduleEstimator::Log*
00477 LinkScheduleEstimator::find_schedule(LinkScheduleEstimator::Log &log)
00478 {
00479
00480
00481
00482 unsigned int period = estimate_period(log);
00483
00484 if(period) {
00485
00486 period = refine_period(log, period);
00487
00488 return extract_schedule(log, period);
00489 }
00490 else return 0;
00491 }
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
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 }