Subject: [IPTEL] CPL time ranges

From: Henning Schulzrinne <[email-masked]>
Date: Thu, 28 Sep 2000 13:01:28 -0400

To help reaching closure by other than default, let me try to summarize
the options and concerns:

(1) Use crontab

My major concern here goes beyond the "import from calendar" issue. I
have a hard time picturing a user interface that is at all
understandable for somebody not steeped in Unix lore. Given that we want
CPL scripts to be portable and creatable by users, this process must be
reversible. I.e., it is not good enough that I can have a user interface
with a button that says "first Tuesday of the month" and then generate
some crontab specification based on that. I must be able to take CPL and
generate a user interface to change it, readily, to the first Wednesday
of the month. Since the way of expressing date is wholly unnatural, for
humans, for anything but trivial time ranges, I effectively force the UI
to have an interface that has a day slider, a month slider, a weekday
slider (or two, with ranges), etc., directly representing the crontab
fields.

No known user input for anything having to do with dates operates that
way (Jonathan L. has been looking at a variety of calendaring-style
programs and services recently and will report on his findings shortly).

Another problem is that even very simple date ranges like "from 5 pm to
7 am" are not directly expressible in crontab - you need two entries to
do this, which again is not exactly ideal when you're trying to build a
user interface that now has to reverse-engineer what the user meant.
Midnight-spanning time ranges are likely going to be very common.

(2) Use a subset of ical

This seems to solve the user input (including CPL-to-UI reversal)
problem, in the sense that this is a more natural representation of
common ways of expressing date ranges. It has been shown to be
implementable in O(1).

The only objection I remember (I'm sure somebody will point out the
other flaws) is that it may make importing full-fledged iCal difficult.
I don't buy this argument - it's even more difficult or impossible to
translate any reasonable subset of iCal to crontab, so this is no net
loss. For import from a calendar for those obscure cases, an enumeration
of date ranges is possible (it would then only have the disadvantage of
making re-import from CPL to a calendar lossy; importing CPL into a
calendar seems somewhat less likely, since this would only work for a
tightly constrained subset of CPL that only used time switches at the
top level). Given that most reasonable and currently used date
specifications are supported by the subset, this loss of information and
need for enumeration would appear to be an unlikely case. 

(3) Use full ical

It wasn't clear to me whether an implementation has been completed, but
unless there is one, it is probably a risky scheme, as Al Gore would
say. (No, he didn't invent ical, as far as I know.)

(4) Use ical later

This still has the same user interface issues as before, just more so,
plus it adds the usual complexity of finding out which version is
supported where.

-- 
Henning Schulzrinne   http://www.cs.columbia.edu/~hgs

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

---

From: Jonathan Lennox <[email-masked]>
Date: Thu, 28 Sep 2000 13:55:15 -0400 (EDT)

> programs and services recently and will report on his findings shortly).

The attached file lists my study of five user interfaces for calendaring
programs.  If other people have additional interfaces to contribute --
especially if they are substantially different -- I'd be interested to hear
of them.

The iCal-subset is capable of representing all the output of each of these
interfaces, though not necessarily of representing it "naturally" -- i.e. in
a way which (as Henning's mention recommended) can be back-translated to the
same UI.  I believe a somewhat broader iCal subset will be able to represent
all, or almost all, of these attributes naturally, and still be resolvable
in O(1) time with respect to (now - dtstart); more information will be
forthcoming soon.

-- 
Jonathan Lennox
[email-masked]

Sun cm

Appointment recurrence parameters:
Date
Start time
Stop time
Repeat:
        One Time
        Daily
        Weekly
        Every Two Weeks
        Monthly By Date
        Monthly By Weekday
        Yearly
        Monday through Friday
        Mon, Wed, Fri
        Tue, Thu
        Repeat Every...
                N (days | weeks | months)
For: N (days | weeks | biweeks | months | years)

The stop time can be earlier than the start time -- it asks you if
you want it to continue to the next day.

Time Zone: from /usr/share/lib/zoneinfo/.  In "View" menu, not appointment
setting.

Netcenter WebCalendar

Date
Time (5-minute intervals, 12:00 AM to 11:55 PM)
Duration (5-minute intervals, 0:05 - 12:55)
Repeat:
        * Does not Repeat
        * Repeats (every | every other | every third | every fourth)
                (day | week | month | year | MWF | TuTh | MW | M-F | SaSu)
        * Repeats on the (first | second | third | fourth | last)
                (Su | Mo | Tu | We | Th | Fr | Sa) every month
* No End date, or * End by [date]

Appointments do not carry past midnight -- duration is truncated.

Time Zone: GMT offset only.  In "Calendar Preferences".  Does not seem
to take DST into account?

SDR
How often it takes place: (Once | Daily | Weekly | Every Two Weeks |
        [Monthly By Date] | [Monday through Friday])
        from [Date] at [Time] for (30 minutes | 1 - 12 hours | 1 - 6 days)
Length of this series of sessions:
        (2 - 6 days | 1 week | 8 - 13 days | (2 - 4) weeks)
        [ "Week" parameters only for weekly; "4 weeks" only for biweekly ]

"Monthly by date" and "Monday through Friday" selections are disabled.
Bug list says 'Doesn't handle SDPv2 repeat times with units "M" and "Y"'

Microsoft Outlook

Start time: (Date) (Time) [X] All day event
ENd time: (Date) (Time)
Start - End can be arbitrarily long

Appointment Recurrence
Start:  [Time]    End:  [Time]    Duration: [Interval]
(Remebers dates of parent window, though they cannot be set here)

Recurrence pattern:
* Daily:    * Every [N] day(s)
	    * Every weekday

* Weekly:   Recur every [N] week(s) on:
            [] Su [] Mo [] Tu [] We [] Thu [] Fri [] Sa [] Su

* Monthly:  * Day [N] of every [N] month(s)
            * The (first | second | third | fourth | last) 
               (day | weekday | weekend day | Su - Sa)
               of every [N] month(s)

* Yearly:   * Every (Month) [day]
            * The (first | second | third | fourth | last) (day...) of (month)

Range of recurrence:
Start: [Date]      * No end date
		   * End after: [N] occurences
                   * End by: [Date]

Netscape Calendar

Main tab:
Date, Start Time, end time, duration.  (Duration cannot exceed 24h)

"Repeating..." tab:

Start: [date]
        * Until [date]
        * For [N] (Day(s) | Week(s) | Month(s) | Year(s)

Include: [X] Saturdays [X] Sundays [X] Holidays

Frequency: Daily:
	* Every day
	* Every [N] day(s)

Weekly:
        * Every week
        * Every [N] week(s)
        [Mo] [Tu] [We] [Th] [Fr] [Sa] [Su]

Monthly on date(s):
        * On the [N] of every month
        * On the [1st .. 31st] of every [N] months
                   ^ multi-choice

Monthly on day(s):
* On the (1st, 2nd, 3rd, 4th, last) (Su - Sa) of every [N] month(s)
         ^ multi-choice

Yearly:
* Every year
* Every [N] year(s)

---

From: Jay Batson <[email-masked]>
Date: Fri, 29 Sep 2000 00:56:31 -0400

I can speak to one other, very mature calendaring 
system:  MeetingMaker.  For reference, I was VP of Engineering of the team 
that built this client/server group calendaring product, which is still in 
wide use.  (E.g it is the group meeting scheduler at Cisco.)  I am proud to 
brag that MM a very sophisticated product that is targeted at high-end, 
very large, geographically diverse enterprises.

Following Jonathan L.'s outline, Meeting Maker provides:

Start time
Duration (from which stop time is calculated)
Frequency:
	Daily
	  - options: every day, every 'n' days, on specified days of the week
	Weekly
	  - options: on specified day of week, every week; every 'n' weeks; on 
specified week of month (e.g. 1st, 2nd, 3rd, 4th, last)
	Monthly
	  - options: Every month on this date, every other month on this date, 
29th day of every month, 29th day of every other month, and what to do if 
activity falls on weekend (don't move, move to previous weekday, move to 
next weekday, move to closest weekday)
	Quarterly
	  - options: What to do if activity falls on weekend (see previous choices)
	Annually
	  - options: What to do if activity falls on weekend (see previous choices)

Exception vector:
	(Not an explicit choice.  However, when a user sees a recurring meeting in 
their calendar, and they select the meeting and hit "delete," the program 
asks them if they want to cancel "the meeting on this (selected) date," 
"the meetings after this (selected) date," or "all occurrences of this 
meeting."  Note that the Palm desktop provides the same options.)

Time zone is attached to the meeting object by the server involved.  (Users 
are "associated" with a server within their time zone, and the server is 
told its time zone.  In MeetingMaker, when a meeting proposal is sent to a 
user on another server, the remote server adjusts for time zone 
differences, so that the proposal ends up being presented to the user in 
their "local" time.)  The meeting is stored in Zulu (GMT) time, along with 
storing the meeting proposer's time zone.  On servers, time zones are set 
in +/- GMT, and they know their local time zone rules (e.g. Arizona.)

Meetings/activities can span midnight, but for reasons I can't remember 
cannot exceed 24 hours.

For the record, I will claim substantial credit for getting the IETF iCal 
working group started.  I wanted to get calendaring products to provide the 
ability to propose meetings between companies, so I harangued other 
calendar vendors into getting the IETF to let us start the group.

As a non-technical contributor, I didn't chair the group, etc., but 
employees from my team contributed to the (never-completed) portion of iCal 
that was creating the "live" calendaring *protocol* for interactions 
between systems.  (Never completed because we couldn't solve some 
fundamental problems, e.g. information protection/security.)

The data representation portions of iCal -- which this group is mostly 
looking at -- is made up primarily of work done by Microsoft, and by 
Qualcomm (who was expecting to build a calendaring product, but never 
did.)  Much of the data representation decisions were made to suit 
Microsoft's then-current-product needs.

Note that there are various *calendaring* products out today which support 
parsing of iCal data, e.g. Outlook and Organizer.

For the record (again), I'm an old unix hack.  crontab was *maybe* okay in 
1986, but was and is maddening obtuse.  I always had the opinion that the 
crontab format was the bad idea of a junior programmer who hadn't thought 
through all the issues, and that we were all stuck with his/her bad 
ideas.  I even wrote a replacement for it when I was at BBN that we toyed 
with distributing as part of the OS release for our Mach-based massively 
parallel processor computers.  (It was a *tad* better, though not much.... ;-)

IMHO, I think the work done by the iCal WG was pretty good.  There are 
*many* subtleties that arise when you have to think about representing 
events and times, and you don't always know what they are till you've been 
there.  People who had "been there" built the iCal data representation, and 
did good work.

So I'm sad (nah -- happy!) to say that I can't provide "running code," I 
would place myself on the side of using iCal in some manner -- abbreviated 
or not -- when it comes to the "rough consensus" part.  Now if Jonathan L. 
can provide the running code.... ;-)

-jb
----------
Jay Batson
Pingtel Corp.
[email-masked]

781-938-5306 (office)
781-938-9650 (fax)

---

From: Jonathan Lennox <[email-masked]>
Date: Fri, 29 Sep 2000 19:48:12 -0400 (EDT)

On Thursday, September 28 2000, "Jonathan Lennox" wrote to "Henning Schulzrinne, [email-masked]" saying:

> I believe a somewhat broader iCal subset will be able to represent

Here it is.  This handles almost all of iCal -- and, I believe, all its
*useful* parts -- in O(1) time.

No running code yet, though implementation of this algorithm should be
straightforward.  

"Beware of bugs in the above code.  I have only proven it correct; I haven't
tried it yet." -- Donald Knuth

Comments *very* welcome.

-- 
Jonathan Lennox
[email-masked]

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. The duration of the event ("duration" or "dtend - dtstart") must be
        less than 24 hours.

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.  If the call time is less than 'duration' after dtstart, succeed MATCH.

4.  Determine the smallest unit specified in a "by*" rule or by the "freq".
    Call this the Minimum Unit.  Determine the previous instant (before
    the call time) when all the time units smaller than the minimum unit
    are the same as those of DTStart.  (For all minimum units, the
    time-of-day must be the same as dtstart.  If the minimum unit is a week,
    the day-of-the-week must be the same as dtstart.  If the minimum unit is
    a month, the day-of-the-month must be the same as dtstart.  If the
    minimum unit is a year, the month and day-of-month must both be the same
    as dtstart (unless the dtstart is February 29 in a leap year, in which
    case the month and day-of-month can also be March 1 in a non-leap year).

    Call this instant the Candidate Start Time.

5.  If the time between the candidate start time and the call time is more
    than the duration, fail NOMATCH.

6.  If the candidate start time is later than the 'until' parameter of the
    recurrence, fail NOMATCH.

7.  Call the unit of the 'freq' parameter of the recurrence the Frequency
    Unit.  Determine the frequency unit enclosing the Candidate Start Time,
    and that enclosing DTStart.  Calculate the number of frequency units
    that have passed between these two times.  If this is not a multiple
    of the "interval" parameter, fail NOMATCH.

8.  For every by* rule, confirm that the candidate start time matches one
    of the options specified by that by* rule.  If not, 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.  Durations longer than the minimum unit can result in multiple candidate
        start times being possible for a given call time.  The simplest way
        to resolve this is by forcing durations to be less than 24
        hours, while eliminating the sub-day frequencies and rules.  The
        algorithm would still work with just the weaker condition (duration
        < min unit), though this would be much harder to explain.

Notes on importing from full iCal:

In my experience, no actual calendaring implementations present a user
interface for creating sub-day-resolution recurrences.  Very few allow
appointments longer than 24 hours.

Converting from 'count' to 'until' parameters, for a client which must
enumerate the event listings anyway, is trivial.

'bysetpos', 'rdate', 'exrule', and 'exdate' can all be handled by
converting a single full iCal RRULE into multiple time-switches, linked
with sub's to the same output.