1 /*

     2  *    Copyright 2005-2006 Intel Corporation

     3  * 

     4  *    Licensed under the Apache License, Version 2.0 (the "License");

     5  *    you may not use this file except in compliance with the License.

     6  *    You may obtain a copy of the License at

     7  * 

     8  *        http://www.apache.org/licenses/LICENSE-2.0

     9  * 

    10  *    Unless required by applicable law or agreed to in writing, software

    11  *    distributed under the License is distributed on an "AS IS" BASIS,

    12  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

    13  *    See the License for the specific language governing permissions and

    14  *    limitations under the License.

    15  */

    16 

    17 #include <vector>

    18 #include <oasys/util/IntUtils.h>

    19 #include <oasys/debug/Log.h>

    20 

    21 #define CONTACT(s, d) { s, d }

    22 #define absdiff(x,y) ((x<y)?((y)-(x)):((x)-(y)))

    23 

    24 #define WARPING_WINDOW .02

    25 #define PERIOD_TOLERANCE .02

    26 #define MAX_DIST 1<<30

    27 

    28 namespace dtn {

    29     

    30 /**

    31  *    Given a log on the form (start1, duration1), ... ,(startN,

    32  *    durationN), the LinkScheduleEstimator algorithm figures out a

    33  *    periodic schedule that this log conforms to.

    34  *

    35  *    The schedule computed can then be used to predict future link-up

    36  *    events, and to inform far-away nodes about the future predicted

    37  *    availability of the link in question.

    38  *

    39  *    Usage:

    40  *      Log* find_schedule(Log* log);

    41  *

    42  *    Returns the best schedule for the given log. If there's no

    43  *    discernible periodicity in the log, the return value will be

    44  *    NULL.

    45  */

    46 class LinkScheduleEstimator : public oasys::Logger {

    47 public:

    48     typedef struct {

    49       unsigned int start;

    50       unsigned int duration;

    51     } LogEntry;

    52     

    53     typedef std::vector<LogEntry> Log;

    54     

    55     static Log* find_schedule(Log* log);

    56 

    57     LinkScheduleEstimator();

    58 private:

    59     unsigned int entry_dist(Log &a, unsigned int a_index, unsigned int a_offset,

    60                             Log &b, unsigned int b_index, unsigned int b_offset,

    61                             unsigned int warping_window);

    62 

    63     unsigned int log_dist_r(Log &a, unsigned int a_index, unsigned int a_offset,

    64                             Log &b, unsigned int b_index, unsigned int b_offset,

    65                             unsigned int warping_window);

    66     

    67        

    68     unsigned int log_dist(Log &a, unsigned int a_offset,

    69                  Log &b, unsigned int b_offset,

    70                  unsigned int warping_window, int print_table);

    71     

    72     unsigned int autocorrelation(Log &log, unsigned int phase, int print_table);    

    73     void print_log(Log &log, int relative_dates);

    74     

    75     Log* generate_samples(Log &schedule,

    76                           unsigned int log_size,

    77                           unsigned int start_jitter,

    78                           double duration_jitter);

    79     

    80     unsigned int estimate_period(Log &log);       

    81     unsigned int seek_to_before_date(Log &log, unsigned int date);                

    82     unsigned int closest_entry_to_date(Log &log, unsigned int date);

    83     Log* clone_subsequence(Log &log, unsigned int start, unsigned int len);

    84         

    85     unsigned int badness_of_match(Log &pattern,

    86                                   Log &log,

    87                                   unsigned int warping_window, 

    88                                   unsigned int period);

    89     

    90     Log* extract_schedule(Log &log, unsigned int period_estimate);    

    91     unsigned int refine_period(Log &log, unsigned int period_estimate);

    92     Log* find_schedule(Log &log);    

    93 };

    94 

    95 

    96 }