Subject: CPL & RECUR: Notes from phone call.

From: Eric Busboom <[email-masked]>
Date: Tue, 15 May 2001 09:14:01 -0700 (PDT)

I called Jonathan Lennox Monday afternoon to discuss how to resolve the
IPTEL group's issues with recurrence rules. Here are my notes from the
call.

1) Computational requirements for checking recurrence rules.

Jonathan and I believe that the critical computational requirement for
recurrence rules is that an implementation can operate on them in bounded
time. The operations that need to be bounded are:

	Checking that a given time is included in a recurrence set
	specified by DTSTART, DURATION and one or more of RRULE, RDATE,
	EXRULE and EXDATE. (For Telephony equipment)

	Expanding a recurrence rule set  ( DTSTART, and one or more of
	RRULE, RDATE, EXRULE and EXDATE) in to a set of occurrences.
	( For CAP servers )

By "bounded time" we mean that an implementation can perform the operation
in a known amount of time, or in a known amount of time determine how long
the operation will take to complete. Using this computational requirement
instead of O(1) means that iCalendar may be able to keep much of its
current expressiveness while CPL can ensure that the recurrence rule will
not pose excessive load on a server.

The time bound for a rule will, of course, vary with the complexity of a
rule. The goal is for implementations to be able to determine the time
bound for a rule in constant time, and then determine if the
implementation has the computing resources to actually process the rule.
If the rule is too complex, the implementation may reject it.

"Bounded time" is a weaker concept than O(1), but it will still require
that we reduce the complexity of iCalendar.

2) Complications in ensuring bounded time.

When an implementation is expanding a rule or checking existence of a time
in the set of occurrences generated by a rule, the form of the rule is
significant in determining how long it will take to perform the
operations. Some of the problems are:

	(1) BYSETPOS generally requires a rule to be expanded completely
	to check the non-existence of a time in the recurrence set.

	(2) BYSETPOS with negative valued arguments requires a rule to be
	expanded completely to get any elements in the occurrence set.

	(3) Many recurrence sets can be described by many different rules,
	some of which are potentially much more computationally intensive
	than others.

	(4) COUNT requires a rule to be expanded completely
        to check the non-existence of a time in the recurrence set.

3) Complications involving checking that a given time is in an occurrence
set.

If the duration of an event is allowed to be longer than timespan
associated with the frequency of a rule, it is difficult to check that a
given time is within the occurrences specified by the rrule.

The algorithm that Jonathan implemented for this check examines the parts
of a given time and checks that those parts all are accounted for by some
element in the recurrence rule.  Ie: That the day of month of the time
is either listed in the BYMONTHDAY rule part or (in a DAILY RULE) it is
N*INTERVAL days from the start time.

If the duration of the event was 2 days, then the given time could be in
the second day, and neither of the checks above would work.

The computationally least expensive way to solve this problem is to
restrict DURATIONs to be less than 1 day and remove some frequencies and
BYxxx rule parts. (Call it the algebraic method )

The other way is to check existence in the set by generating all
occurrences in the set, and checking that the time is in the set. ( Call
it the expansion method. )

I think that the restrictions required to make the algebraic method work
are a serious imposition on the recurrence rule specification; I don't
think we can get rid of intra-day occurrences.

But, Jonathan suggested that the expansion method may be acceptable, if
for the vast majority of cases, the computation time can be bounded into
acceptable limits.

Jonathan notes that the algebraic method can still work even if you
eliminate the limitation on duration and restore sub-day rules; you're
just no longer inherently time-bounded.  The running time is proportional
to ceil(duration / (smallest mentioned time interval)).

So, iCalendar could keep the H,M,S frequencies and rule parts, and allow
DURATIONS longer than a day, if nearly all expansions of rules can be very
fast, and an algorithm can quickly establish an upper bound on expansion time.

4) Other complications

A side issue, that we may as well address now, is that (anecdotally)
implementers are stymied by the problem of creating a GUI that can display
an arbitrary rule. I believe that this problem is particularly complicated
by problems (2) and (3) above.

4) Proposals

Jonathan and I discussed the following proposals:

	(1) Get rid of BYSETPOS. It is a major problem for the IPTEL
	folks, a PITA for iCalendar, and is rarely actually required.

	(2) iCalendar can probably keep COUNT, but CPL will have to
	convert it to UNTIL on the client side.

	(3) Ensure that expanding most common rules is computationally
	efficient.

Things in the original draft of IPTEL proposed changes to RECUR that we
discussed NOT implementing are:

	(4) Removal of BYHOUR, BYSECOND, BYMINUTE by rules

	(5) Removal of HOURLY, MINUTELY and SECONDLY frequencies

	(6) Restricting DURATION to less than 1 day.

(1) is something that the CalSch group will have to debate some more.
(Before we finally come to the correct conclusion and decide to remove it
:) )

(2) does not require any CalSch action.

(3) Will require further discussion and some new proposals. Jonathan will
send out some more information about guidelines for the computational
limits for recurrence rules to give us a guide for updating the RECUR
specification.

(4), (5) and (6) are contingent on a suitable solution to (3). That is, if
expanding recurrence rules can be very inexpensive in the general cases,
and easily bounded in the complex cases, then the CPL recurrence
operations can use an expansion method rather than an algebraic method
and (4), (5) and (6) are not necessary. But again, that is an "if"

eric.

---

From: Eric Busboom <[email-masked]>
Date: Wed, 16 May 2001 14:50:58 -0700 (PDT)

> 	(6) Restricting DURATION to less than 1 day.

Major faux pas here: these are things that the CPL draft suggested
removing, but which Jonathan and I sugessted would not really need to be
removed. That is, it should be "NOT removing" instead of "NOT
implementing"

Sorry for the confusion.

eric.