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