Re: iptel and iCalendar

[Jonathan Lennox <lennox@xxxxxxxxxxxxxxx>]

On Monday, February 12 2001, "Jonathan Lennox" wrote to "ietf-calendar@xxxxxxx, Jonathan Rosenberg, Henning Schulzrinne, John Stracke" saying:

> I'll comment on the motivations and justifications for CPL's RRULE subset in
> a follow-up message (I think this message is getting too long as-is).

As promised.

CPL's subset of RRULE is motivated by a single requirement: we need to be
able to tell, in O(1) time, whether a given instant falls within some
repetition of an RRULE.

At first, I thought I was going to have to give up a whole lot of RRULE to
satisfy this requirement, but I managed to come up with an algorithm
(Appendix A of the CPL spec draft-ietf-iptel-cpl-04) which satisfies it
while including *almost* all of RRULE.  There were only four restrictions: 

* We don't use COUNT 
* We don't use BYSETPOS
* Durations are limited to less than 24 hours
* We eliminated the FREQ rule parts and the BY* rule parts less than a day.

The first two of these are rules that (as near as I can tell) can't be
resolved without a full enumeration of the recurrence set.  I'd certainly
welcome any comments which correct me on this, though!

Of these two, the elimination of COUNT is significantly less of a semantic
loss.  It's largely interchangeable with UNTIL in semantics, and it's a lot
easier to write both code and user interfaces for UNTIL.

Basically, converting a recurrence which uses COUNT to a recurrence which
uses UNTIL is an off-line one-time cost of O(count). I was going to impose
this cost on the iCalendar-to-CPL conversion tool, but if interoperability
meant that the cost was imposed on a CPL server instead, I don't think it'd
be a huge problem.  (It'd mean that conversions back from CPL to iCalendar
wouldn't lose information.)

BYSETPOS is a lot more of a semantic loss, since there's no way (as far as I
can tell) to encode its semantics into other RRULE rule parts.  For at least
some BYSETPOS rules, you can transform them into a set of non-BYSETPOS-using
RRULE and EXRULE rules, but I'm not sure if this is possible in the general
case.  (CPL doesn't actually use EXRULE, but its first-match semantics for
time switches are effectively equivalent.  I'm using the iCalendar
terminology for this discussion to try to keep things clear for this mailing
list.)

I haven't studied this transformation very thoroughly, though -- I'm not
sure it's always possible, and at any rate a single BYSETPOS-using
recurrence will I believe have to be transformed into O(setsize)
non-BYSETPOS-using recurrences.  I feel this is probably the weakest point
of the subset right now; reactions are welcome.  I'd be a lot more concerned
about this fact if I thought that BYSETPOS were going to show up in its full
generality in actual calendaring rules, though.


The third and fourth restrictions are related.  The "Appendix A" algorithm I
worked out is actually O(d/i), where 'd' is the duration of the recurrence,
and 'i' is the "minimum interval" -- the smallest unit of FREQ or BY* in the
rule.  That is to say, in the algorithm, a six-week duration with a
BYMONTHDAY rule would have to iterate through the algorithm approximately 42
times.

To guarantee the O(1) requirement, we have to constrain 'd' to be less than
'i'.  I could have just imposed this as a specific requirement in the CPL
specification, but that seemed likely to be a user-interface
nightmare. Instead, I just gave a simple rule: 'd' must be less than a day,
and 'i' must be greater than or equal to a day.  This seems to reflect the
actual UI restrictions most calendaring programs impose.

There are, as I see it, five possible alternatives to this solution:
* Move the limit between d and i.  There's no obvious other position for it,
  though. 
* Make the d < i restriction explicit in the code.  Like I said, probably
  a user interface and documentation nightmare.
* Allow the full RRULE set of FREQ and BY* values, but let individual CPL
  servers reject CPL scripts with a d-over-i value higher than they're
  willing to support.  This will probably result in interoperability
  nightmares.
* Impose a maximum d-over-i value (greater than 1) in the CPL specification.
  This means we still lose full iCalendar compatibility, but not as badly.
* Come up with a cleverer algorithm which is still O(1) regardless of the
  value of d-over-i.  This is obviously the best solution. :-)

There are other reasons that I wanted to restrict intervals less than a day,
the primary one of which is that it's somewhat hard to resolve in O(1) time
the rule 'FREQ=MINUTELY;INTERVAL=734;BYDAY=TU' in a local timezone, when it
might cross a DST boundary an arbitrary number of times between DTSTART and
the current time.  I think this could probably be solved, or at least
finessed, however.


I'd certainly prefer to be able to incorporate all of iCalendar's RRULE spec
into CPL, so if people have ideas as to how we could improve our algorithm
so as to increase interoperability, I'd be all for it -- that's probably the
best solution all around.  Failing that, though, there needs to be a
reasonable set of compromises between the expressive power of RRULE and the
demand for an O(1) algorithm to resolve it.  I feel that CPL made these
reasonable compromises, but if this list/working group feels that different
compromises are appropriate I'm certainly open to them.

-- 
Jonathan Lennox
lennox@xxxxxxxxxxxxxxx