Subject: RE: [IPTEL] Proposed resolution of CPL time-switch issue

From: Jonathan Rosenberg <[email-masked]>
Date: Fri, 15 Sep 2000 01:44:01 -0400

> -----Original Message-----
> From: Jonathan Lennox [mailto:[email-masked]]
> Sent: Thursday, September 14, 2000 10:17 PM
> To: Henning Schulzrinne
> Cc: [email-masked]
> Subject: Re: [IPTEL] Proposed resolution of CPL time-switch issue
> 
> 
> On Thursday, September 14 2000, "Henning Schulzrinne" wrote 
> to "Jonathan Lennox, [email-masked]" saying:
> 
> > Jonathan Lennox wrote:
> > > 
> > > There was enough dismay over the whole iCal time-switch 
> issue that I've
> > > (semi-reluctantly) agreed that it's too complicated for 
> the base CPL spec.
> > 
> > I disagree strongly. I thought we had agreed that a 
> simplified version
> > of the ical syntax, minus some of the by-rules, would be an 
> easier road
> > to upgrade later, rather than having two completely different
> > specification rules.
> 
> One consideration that I think is very important, which held 
> true for the
> crontab-based proposal but which (as far as I can tell) 
> doesn't hold true
> for iCal, is that it should be possible to write (easily) an 
> O(1) algorithm
> that determines whether a given instant in time falls within 
> a given time
> range -- i.e., without having to iterate through all the time 
> positions
> prior to the current one.
> 
> I'm trying to work out what such an O(1) subset of iCal would 
> be.  It's
> clear that the "count" rule has to be eliminated, and 
> "bysetpos".  Probably,
> expanding by* rules would have to go as well, though I 
> *think* contracting
> ones can stay.  "interval" is tricky, but possibly doable; 
> I'm not sure.
> 
> I could make the argument, though, that we would actually 
> have an *easier*
> time with future upgrades if our two time syntaxes were completely
> different, rather than largely the same but with important and subtle
> semantic differences.  Given that (it seems) the implementation of
> iCal-subset and iCal-complete have to be quite different, and 
> the inevitable
> confusion of "okay, '<time freq="daily" byhour="5">' is 
> illegal, but '<time
> freq="daily" ical:byhour="5">' is fine"...well, it feels like an
> interoperability and documentation nightmare.
> 
> Additionally, as JR pointed out earlier in the time-switch 
> discussion, it's
> not possible to express "first monday of the month" or using only
> contracting rules; that needs an expanding rule.  By 
> contrast, it's trivial
> using the crontab syntax.
> 
> That said, if consensus is for a subset, we can subset, once we're
> algorithmically sure of what that subset should be.

We seem to keep rolling around in circles here. This is due, in part, to the
fact that only a few folks have expressed any opinion here (myself, Henning,
Jonathan L., and James U.), and of those, a few of us have waffled quite a
lot, including myself.

We need to make a decision already, and go with it. So, I will employ the
tools at hand for a working group chair - rough consensus and running code.
As for the first, James last spoke in favor of the crontab syntax, I
personally would prefer it, Jonathan seems on the fence, and Henning is
opposed. Rough consensus is for crontab. As for running code, I know of
numerous implementations of the crontab approach and none for iCal. 

SO, given rough consensus and running code speak in favor of the old syntax,
AND using the old syntax will help with compatibility with older CPL
implementations that did the crontab stuff, AND we can add in iCal stuff
later through extensions, AND the crontab stuff is similar to existing time
mechanisms and not something totally new, it seems reasonable to go that
path.

So, I am waving the wg chair wand and declaring this issue resolved. I will
only reconsider if someone (1) says I have misrepresented their opinion,
thus changing rough consensus, or (2) someone can demonstrate running code
for the iCal stuff, and argue that its really a piece of cake after all. 

-Jonathan R.
---
Jonathan D. Rosenberg                       72 Eagle Rock Ave.
Chief Scientist                             First Floor
dynamicsoft                                 East Hanover, NJ 07936
[email-masked]                     FAX:   (973) 952-5050
http://www.cs.columbia.edu/~jdrosen         PHONE: (973) 952-5000
http://www.dynamicsoft.com

_______________________________________________
IPTEL mailing list
[email-masked]
http://lists.bell-labs.com/mailman/listinfo/iptel

---

From: Jonathan Lennox <[email-masked]>
Date: Fri, 15 Sep 2000 10:07:50 -0400 (EDT)

> for the iCal stuff, and argue that its really a piece of cake after all. 

Round and round and round we go...I was thinking about this problem last
night after my last mail to the list, and I think I've come up with a useful
iCal subset, and a relatively simple O(1) algorithm for deciding time
switches.

Here are the restrictions I've imposed on iCal:

A. The "secondly", "minutely", and "hourly" recurrences, and the "bysecond",
        "byminute", and "byhour" rules, are eliminated.
B. The "count" and "bysetpos" rules are eliminated.
C. "Expanding" by* rules are eliminated.  Only the following by* rules are
        allowed:
    freq=daily:   byday, bymonthday, byyearday, byweekno, bymonth
    freq=weekly:  byweekno, bymonth
    freq=monthly: bymonth
    freq=yearly:  none
D. The duration of the event ("duration" or "dtend - dtstart") must be
        strictly less than the unit of "freq" times "interval".

Here is the algorithm:
1.  Compute the time of the call, in the timezone of the time switch.
    (No step after this needs to consider time zones -- all calculations
    are done using continuously-running standard Gregorian time.)

2.  If the call time is earlier than dtstart, fail NOMATCH.

3.  Determine the number of occurences of the recurrence frequency (the
    number of days, weeks, months, or years) that have passed between
    dtstart and the call time.  Call this fraction 'Repeats'.

4.  Round Repeats down to the nearest whole-number multiple of "interval".
    Call this rounded value 'WholeRepeats'.

5.  Determine the instant that is WholeRepeats occurences of the recurrence
    frequency from dtstart.  This instant is the 'Candidate Instant'.  If
    the current time falls within a recurrence interval, the Candidate
    Instant must be the starting point of this interval.

6.  If the Candidate Instant is later than the 'until' parameter of the
    recurrence, fail NOMATCH.

7.  If the time between the Candidate Instant and the current time is
    greater than the duration, fail NOMATCH.

8.  For each by* rule which is present in the recurrence and which is
    legal for the frequency, confirm that the Candidate Instant matches to
    the rule.  If any doesn't match, fail NOMATCH.

9.  Succeed MATCH.

Some notes on this algorithm:

The justifications for each of the eliminations above are as follows.

A.  When sub-day-resolution rules are present, issues of daylight-savings
        transitions come into play.  The number of, e.g., "nine hour"
        intervals since a given time isn't easily computable from a
        broken-down local time if a DST transition has occured in between.
        Since sub-day-resolution rules don't seem especially useful for
        recurring events anyway, we can avoid consideration of these
        issues by eliminating them.

B.  Barring very clever (and complex) algorithms that escape me, "count" and
        "bysetpos" rules both require that a set of recurrences be fully
        enumerated for them to be correctly resolved.

C.  Expanding rules add to the set of start times for a recurrence, making it
        impossible to find a unique candidate instant in O(1) time.

D.  Durations longer than a frequency will result in multiple candidate
        instants being possible for a given call time.

The correctness of this algorithm depends on the fact that a) the candidate
instant is unique, and b) we have computed it correctly.  Given these two
facts, the correctness of the rest of the algorithm should be obvious.
I'm reasonably convinced both these facts hold, but more eyeballs are always
good.

It is worth noting that (I believe) the crontab-style entries can be exactly
represented by a freq="daily" recurrence, except that multiple time-of-day
intervals cannot be given in a single rule.  (They can be expressed with
multiple time-switch rules connected by subs, of course.)

I was wrong, incidentally, about the "first monday of the month" rule
requiring expansion rules.  The following rule, which conforms to the
restrictions above, describes it:

<time dtstart="20000904T090000" duration="8H"
      recur="daily" byday="MO" bymonthday="1,2,3,4,5,6,7">

This is slightly clumsier than recur="monthly" byday="1MO", but it's a lot
easier to calculate.

Given the algorithm above, surprising things can happen during a
daylight-savings-time transition.  For instance, given a daily rule which
starts at 2:30 a.m. and lasts for an hour, in US-Eastern on the "fall back"
day a call at 2:45 daylight time will fall under the rule; a call half an
hour later at 2:15 standard time will not; and a call half an hour after
that at 2:45 standard time will.  For the common case of rules that don't
care about early-morning events, though, this model behaves as expected.
(I.e., a rule that starts at 5 pm and has a 16-hour duration will last until
9 am, even on days when there is a DST transition.)

I know this isn't *running* code, but this algorithm should be implementable
without too much work.

Given this, how do people think we should proceed?

-- 
Jonathan Lennox
[email-masked]