Subject: CPL: Summary of what it is

From: Jonathan Lennox <[email-masked]>
Date: Wed, 8 Aug 2001 13:53:23 -0400 (EDT)

I'm not in London at the IETF, but I've heard reports from those who are.
Apparently there was some discussion of the CPL issue there, and I've been
asked to do several things.

The first of these was to give a brief summary of what CPL is, and why
iCalendar should care about it, for newcomers or those who've lost track of
the discussion.

CPL is the Call Processing Language.  It is a simple language for
representing telephone call handling.  It allows a user to specify how their
calls should be handled, in an intelligent, extensible way.  This includes
things like controlling who's allowed to call you, what time they're allowed
to call you, which of your several locations should be alerted for any given
call, and so forth.

The language is designed to be run in large IP telephony servers.  Customers
are trusted to specify the handling of their own calls, but aren't
necessarily trusted not to try to perform hostile or stupid actions which
could potentially disable the server.  Thus, one of the design goals of the
language is that script processing should not force a server to use
arbitrary amounts of CPU time, memory, or related issues.

One of the conditions which can affect call treatment is by the current
time-of-day, day-of-week, and so forth.  This is the area where iCalendar
becomes relevant to CPL.  The consensus was that since the IETF already has
a standard for representing repeating events and periods of time (RFC 2445),
CPL should re-use that existing work rather than inventing something new.
This allows, among other things, call processing scripts to be derived from
calendar book entries.

However, there is a conflict between this desire to re-use existing
technology, and the requirement that script processing not impose unlimited
processing requirements on a server.  In some pathological cases, iCalendar
recurring events can describe items that can take very large amounts of
processing in order to resolve correctly.

I summarized these issues before, about two weeks ago, in a message to this
list.  It's archived at the address
<http://www.imc.org/ietf-calendar/mail-archive/msg02946.html>.  This message
lists the specific details of the problems, and my proposed solutions.

I hope this clears up the current situation.  I'd really like to reach
closure on this issue very soon.

-- 
Jonathan Lennox
[email-masked]

---

From: John Stracke <[email-masked]>
Date: Thu, 09 Aug 2001 09:17:36 +0100

Jonathan Lennox wrote:

> Thus, one of the design goals of the

Something that came up in the meeting: what about disk space? This arises from
the idea of expanding the first, say, 90 days' worth of instances, and then
rerunning the expansion every 90 days.  In theory, someone could have a
recurrence rule that would expand to up to, er, 7,776,000 instances; but that
can be detected easily when the rule is submitted.

Basically, this changes the expensive resource consumed from CPU time (which is
hard to measure in advance) to disk space (which is easy--just give the users a
disk quota).

--
/=================================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.   |
|Chief Scientist |================================================|
|eCal Corp.      |"If there's anything The Flintstones have taught|
[email-masked]|us, it's that pelicans can be used to mix       |
|                |cement." -- Homer Simpson                       |
\=================================================================/

---

From: Henning Schulzrinne <[email-masked]>
Date: Thu, 09 Aug 2001 04:49:50 -0700

I'm not sure if you're saying that complexity in CPU doesn't matter with
pre-expansion or if disk space is another, additional concern. In any
event, pre-expansion is done by the same CPU as the checking, so I don't
see the advantage of pre-expansion. (In all likelihood, big servers will
keep all scripts/calsch in main memory, given that we're talking about
acceptable processing delays on the order of 1-10 ms.) In either case,
you have the problem that submitting a CPL script or calsch becomes a
crapshoot. Depending on the server, it will sometimes work and sometimes
not, possibly depending on how many rules you have. Note that unlike
regular calendaring, it is quite likely that the CPL script changes
frequently, so that precomputation may not necessarily be most
efficient, since there may not be any uses of the information until the
next update.

---

From: John Stracke <[email-masked]>
Date: Thu, 09 Aug 2001 10:29:46 +0100

Henning Schulzrinne wrote:

> event, pre-expansion is done by the same CPU as the checking,

See, I was assuming that that wouldn't be the case; that the expansion would be done
by a separate CPU, outside the fast path, like with IP routers that do BGP in a CPU
and then have ASICs to use the resulting data.

Even if it's on the same CPU, it can be done at a lower priority.

> so I don't

> acceptable processing delays on the order of 1-10 ms.)

Um.  How big are we talking about? A thousand users? A million users?

> In either case,
> not, possibly depending on how many rules you have.

Yes, but, with the pre-expansion route, you can tell people what their budget is,
and how much they've used up; people understand budgeting.

> Note that unlike
> frequently,

Really? Why? Do you expect users to be changing their rules hourly?

> so that precomputation may not necessarily be most

I'm not talking about precomputing the whole thing, just expanding the recurrence
rules.  The result would be that you'd have a database of on-recurring events;
searching that database would be faster than applying the recurrence rules on the
fly.

--
/==============================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.|
|Chief Scientist |=============================================|
|eCal Corp.      |Speak softly and carry an Illudium Q-32      |
[email-masked]|Explosive Space Disintegrator.               |
\==============================================================/

---

From: Henning Schulzrinne <[email-masked]>
Date: Thu, 09 Aug 2001 05:52:32 -0700

> and then have ASICs to use the resulting data.

There is no ASIC that can process calsch data; this is not lookup (like
packet processing), but rather real processing.

> Even if it's on the same CPU, it can be done at a lower priority.

Doesn't help, as load bursts are sufficiently long to not leave
additional capacity. It is not helpful if my update of logic doesn't
show up for five minutes - yields very strange failure scenarios.

> Um.  How big are we talking about? A thousand users? A million users?

Thousands to millions. A typical mobile switching center can easily
support a million users.

> and how much they've used up; people understand budgeting.

Each new script is a complete one, so all you get is failure or success,
except that I have no way to predict in advance whether a script will
fail or not. 

> Really? Why? Do you expect users to be changing their rules hourly?

Yes, not all or even most of them, but since these are generated
automatically, this is not implausible.

> searching that database would be faster than applying the recurrence rules on the

What matters is the total computation of expansion + lookup. If you do a
small number of lookups for each expansion (as is probably typical), you
don't save much, even ignoring the storage space issue. Thus, this may
help in some circumstances, but not others.

I do agree that, if we can't agree on reasonable restrictions of rule
expansion, precomputation is about the only viable route, so that errors
can be generated when the calendaring information is submitted. I
suspect what will happen is that instead of expanding and then
discovering that the rule expands to 37 million entries, of which the
36,995,457th is needed, servers will apply the same rules we've been
talking about to reject "suspicious" BYSETPOS.

---

From: John Stracke <[email-masked]>
Date: Thu, 09 Aug 2001 11:09:59 +0100

> packet processing), but rather real processing.

I didn't say it had to be an ASIC; it could be a separate full-power CPU.

> show up for five minutes - yields very strange failure scenarios.

OK, good point.

> Thousands to millions. A typical mobile switching center can easily

Hmm.  A million users, 10 ms response time...how many calls per second? How many rules
per user?

I'm thinking that, if you precompute 90 days (or whatever) at a time, putting the rules
onto disk, and then load today's rules off the disk at midnight, you need only enough RAM
to hold today's rules.  But I need some numbers to know what that'll cost.

> Each new script is a complete one,

<blink> So I can't update individual rules separately? OK, that makes precomputation
harder.  (Mind you, it seems to me that it'll also make a lot of other things harder; I
can't add someone to my ruleset without downloading the whole thing, modifying it, and
sending it back up again--in which case you need locking to prevent lost-write problems.)

> automatically, this is not implausible.

See, I was assuming that the rules could be updated independently, in which case you
wouldn't have to precompute the ones that didn't change.

As a side note, if you're expecting agents to generate the rules automatically, then
independent updates become more important, since someone may have multiple agents.

> don't save much, even ignoring the storage space issue.

If you can do incremental precomputation, then each precomputation gets amortized over a
much larger set of lookups.

In addition, using the database approach means that you can spread the computation work
across different systems: the CPUs in set A expand the rules and write to the database;
those in set B read from the database (N hours of data at a time) and apply the rules.
Of course, when a rule comes in that changes the contents of the next N hours, the rules
need to be propagated into set B's RAM.

|eCal Corp.      |This sentance has threee errors.             |
[email-masked]|                                             |

---

From: Henning Schulzrinne <[email-masked]>
Date: Thu, 09 Aug 2001 07:46:18 -0700

> I didn't say it had to be an ASIC; it could be a separate full-power CPU.

Sure; with sufficient thrust, anything will fly...

> to hold today's rules.  But I need some numbers to know what that'll cost.

About 100 calls/second seems a typical number for a single host
(Netra-class), take or leave a factor of two or three. I don't have a
good idea as to the number of rules, as that depends on the model: for
example, the client could upload only the rules that match the day plus
recurrences or dump the whole calendar, past, present and future. If you
figure five events a day for a typical user (I suspect that others have
much better guesses here) and two years, you get about 3000
events/person. Multiply by user count as appropriate.

> sending it back up again--in which case you need locking to prevent lost-write problems.)

There actually is a versioning mechanism that deals with some of this,
but that's probably out of scope of this discussion.

> independent updates become more important, since someone may have multiple agents.

Definitely.

---

From: John Stracke <[email-masked]>
Date: Thu, 09 Aug 2001 14:00:05 +0100

Henning Schulzrinne wrote:

> If you
> much better guesses here)

5/day is probably a little high, but not much; let's take it as accurate.

> and two years, you get about 3000
> events/person.

OK, now assume each event takes about 50 bytes (that's probably a little high--it's assuming
each date-time is stored as an iCalendar string, so that start&end take 30 bytes).  So storing
all those in RAM will take 150K/person, or about 150G for a million users.  Obviously too
high.

However, I did not suggest storing two years' worth of events at a time; I suggested 90 days
on disk and one day in memory.  One day's worth of data for one million users would then be 5
million events; at 50 bytes apiece, that's 250M.  250M of RAM costs about $50.  Meanwhile, 90
days on disk would take about 22.5G--something like $100.  Obviously, RAM and storage costs
are not a serious limitation here.

(I realize that the costs will be higher for the kind of reliable hardware that telcos need;
but even a factor of 5 only comes to $750.)

> > independent updates become more important, since someone may have multiple agents.

Actually, I've just realized that having a monolithic ruleset doesn't imply that
precalculation has to be done from scratch, *provided* the individual rules carry sequence
numbers (as in iCalendar).  Then the server can compare the old and new rules and preserve the
events whose sequence numbers haven't changed.  How about it? Does CPL have sequence numbers?
If not, would you be willing to add them?

|eCal Corp.      |But this one goes to 11x.                    |

---

From: "Paul B. Hill" <[email-masked]>
Date: Thu, 9 Aug 2001 10:18:03 -0400

Hi,

We are urged to read draft-ietf-idn-idna, Internationalizing Host Names In
Applications (IDNA), which is coming out the idn (Internationalized Domain
Name) working group in the  Internet Area.

If we allow UTF-8 for the UPN or other identifiers that we might want to
query on we will have some real problems. UTF-8 introduces problems when
trying to perform matching, or sorting.

Paul

---

From: John Stracke <[email-masked]>
Date: Thu, 09 Aug 2001 16:37:51 +0100

> trying to perform matching, or sorting.

I think it's not so much that it introduces problems; it's that it, on its
own, does nothing to solve the problems that exist.

A quick overview of the problems (based on what I remember from sitting in on
IDN in Pittsburgh): when you search for a string, users usually don't want to
do an exact bitwise match.  Some things they may want to ignore:

   * In a language using the Roman alphabet: case, accents.
   * In Hebrew: vowels.  Vowels, in Hebrew, are not considered letters; they
     are small decorations added to consonants.  They are often omitted when
     writing quickly--for example, when entering a search string.  (Come to
     think of it, this may be closely analogous to accents in Roman-alphabet
     languages.)
   * In Chinese: distinction between different encoding systems.  Chinese
     computer users have the Traditional system and the Simplified system; in
     Unicode, the Simplified characters are a proper subset of the
     Traditional characters; a Simplified character may represent different
     Traditional characters in different contexts.  So, if someone enters an
     event with Traditional text, and then someone else enters a Simplified
     search string (or vice versa), then the server needs to map the
     Traditional string into Simplified before looking for a match.

I'm sure there are other subtleties, too.

Now, UPNs probably don't have quite the same problems (they're not human
text; they're computer identifiers, and need to match exactly); but it does
pose a problem for queries against the CS.

--
/==============================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.|
|Chief Scientist |=============================================|
|eCal Corp.      |"We can't duplicate the bug." "Have you tried|
[email-masked]|the Xerox machine?"                          |
\==============================================================/

---

From: Lawrence Greenfield <[email-masked]>
Date: Thu, 9 Aug 2001 11:52:15 -0400

Date: Thu, 09 Aug 2001 16:37:51 +0100
   From: John Stracke <[email-masked]>

One thing to strongly consider is use of the ACAP (now also used in
Sieve) comparator registry, which was created to help solve these
problems.  We don't want to tackle these problems protocol by
protocol.  It would be nice if people who feel strongly about these
issues would create new comparators for use.

Larry

---

From: John Stracke <[email-masked]>
Date: Thu, 09 Aug 2001 17:05:31 +0100

Lawrence Greenfield wrote:

> protocol.

No argument there.  Do you have a URL, or an RFC number?

I think we may have it easier than IDN, which had to consider these problems in
an existing protocol with no room for, say, specifying which comparator to use.

--
/=================================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.   |
|Chief Scientist |================================================|
|eCal Corp.      |"A dog will eat pretty much anything; one major |
[email-masked]|reason why there are no restaurants for dogs is |
|                |that the customers would eat the menus." -- Dave|
|                |Barry                                           |
\=================================================================/

---

From: Lawrence Greenfield <[email-masked]>
Date: Thu, 9 Aug 2001 18:13:20 -0400

Date: Thu, 09 Aug 2001 17:05:31 +0100
   From: John Stracke <[email-masked]>

The ACAP RFC is 2244.  Comparators are discussed in section 3.4.

A future specification should probably specify a comparator based on
Unicode Technical Recommendation #10 as another baseline comparator
that will work for UTF-8 and probably include it as a must implement.

Larry

---

From: "David L. Nicol" <[email-masked]>
Date: Fri, 10 Aug 2001 16:54:22 -0500

> spread the computation work

Please delete now if you don't want to get yelled at.

How or what ever, these discussions are off topic!  A standard
is an inclusive minimum!  The preferability of different 
implementation options is off topic! Provide support for multiple
methods (such as error messages on recurrance expression complexity)
and let the CS implementors decide how they want to do it!

-- 
                                           David Nicol 816.235.1187