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

From: Jonathan Rosenberg <[email-masked]>
Date: Mon, 18 Sep 2000 03:37:19 -0400

The question is - have we bought ourselves anything?

This won't be compatible with iCal, so you won't be able to drag and drop
your calendar appointments into CPL generators. I suspect its less complete
than the crontab definition, in that there is less you can describe with it.
Its definitely more difficult to use. We have probably made interop with
iCal harder, since if we do the full blown version later, its not clear from
the tag (its still called time-switch) whether it will work on a given
server. 

So, I'm taking a stand here and sticking by my proposal - back to the
crontab definition. If folks want, we can define the ical-switch tag as an
extension right away (and in this case, do the full version). 

Do we still have consensus on that?

-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

> -----Original Message-----
> From: Jonathan Lennox [mailto:[email-masked]]
> Sent: Friday, September 15, 2000 10:08 AM
> To: Jonathan Rosenberg
> Cc: 'Henning Schulzrinne'; [email-masked]'
> Subject: RE: [IPTEL] Proposed resolution of CPL time-switch issue
> 
> 
> On Friday, September 15 2000, "Jonathan Rosenberg" wrote to 
> "'Jonathan Lennox', 'Henning Schulzrinne', 
> [email-masked]'" saying:
> 
> > 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. 
> 
> 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]
> 

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

---

From: Emmanuel Bertrand <[email-masked]>
Date: Thu, 21 Sep 2000 05:21:24 +0200

> Do we still have consensus on that?

Hi,

I hope it's not too late to post on this thread.

Here at Indigo we have implemented both crontab and iCal.  Beside finding iCal
more powerful and flexible than crontab, we also found it easier to have it
turned into a GUI and to retrieve calendar information from popular
applications.

In our iCal implementation, on the server side we have used an algorithm quite
similar to Jonathan's (Lennox) one to avoid computing overhead.   The algorithm
is not designed to particular iCal subsets and works pretty well.

We also think that, as far as complexity is concerned, one can expect that, in
general, CPL editors/generators will not offer the full iCal possibilies on the
client side thus generating various subsets of iCal.  With this in mind, the
best way for a CPL server to be able to handle all these variants of
time-switches may be to provide full support of iCal.

In conclusion, why not keep the reference to iCal as it exists in the
time-switch paragraph of the 02 CPL draft ?

Not too sure that we have rough consensus on this one, but at least there is
already some running code.

Our two cents,

Cheers,

--
Emmanuel Bertrand
mailto:[email-masked]
http://www.indigosw.com

---

From: Jonathan Lennox <[email-masked]>
Date: Fri, 22 Sep 2000 09:48:11 -0400 (EDT)

> is not designed to particular iCal subsets and works pretty well.

When you say "not designed to particular iCal subsets", do you mean that it
supports the entire iCal specification -- including expanding by-rules,
'count', 'bysetpos', and arbitrary-length durations -- in such a way that
you can make the decision in constant-time, without enumerating the set?

If so, could you post at least rough pseudocode for this?  That'll make a
big difference to how we end up resolving this issue.

(My current incination: if we can manage the whole of iCal in constant time,
stick with it and add an appendix describing our algorithm; otherwise, go
with JR's suggestion to revert to crontab, and define ical-switch as an
extension.)

-- 
Jonathan Lennox
[email-masked]