Subject: [idn] Report from the ACE design team

From: Paul Hoffman / IMC <[email-masked]>
Date: Fri, 15 Jun 2001 07:51:07 -0700

Greetings again. This report from the ACE design team was turned in 
yesterday and will appear in the official Internet Drafts directory 
on Monday.

Internet Draft                                   Paul Hoffman, Editor
draft-ietf-idn-ace-report-00.txt
June 14, 2001
Expires in six months

                 Report of the IDN ACE Design Team

Status of this memo

This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.

Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups. Note that other groups
may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

Abstract

This document is a summary of the work of the ACE design team of the
Internationalized Domain Name (IDN) Working Group. If the IDN WG selects
a single ACE, the design team suggests DUDE. There are many factors that
the IDN WG might consider that may lead it to choose a different ACE;
those factors and proposals that some of the design team members favored
are also described in this document.

1. Introduction

The chairs of the IDN WG appointed an ACE design team to study the many
ACE proposals that had come to the working group and to make a
recommendation based on that study. The design team consisted of Adam
Costello, Paul Hoffman, Makoto Ishisone, David Lawrence, Brian
Spolarich, and Rick Wesson. There were three advisors: Marc Blanchet,
Patrik Faltstrom, and Erik Nordmark.

The design team evaluated the large number of ACEs that have been
proposed in the IDN WG. In comparing them, we looked primarily at two
factors:

- how easy they are to understand and implement

- whether they would restrict long names that are likely to be used

Our discussions led us to discover that neither factor was particularly
easy to measure. Given that it was hard to measure either factor, it was
also difficult to decide how to weigh the two of them against each
other.

2. Recommendation

Based on the two factors, the design team recommends to the IDN WG that
it picks the DUDE algorithm as the ACE to be used in its protocol. There
was general agreement that DUDE was fairly easy to implement
(particularly with the design changes starting with the -02 draft) and
did not restrict long names that were likely to be used in domain names.

There was not complete agreement in the design team on recommending
DUDE. Members disagreed about how much less complex DUDE was
compared to the other proposed ACEs. In addition, some members felt that
price of higher complexity of other proposed ACEs was worth the greater
compression that they give.

The design team chose the DUDE algorithm after the release of the -02
draft, which has some significant design changes from earlier drafts.
Even among the DUDE supporters, there was not universal acclaim. Some
felt that the discussion of "mixed-case annotation" should be removed,
but were willing to recommend the protocol anyway and ask the IDN WG to
remove that optional part of the protocol later.

It is important to note that the ACEs we considered most strongly do not
provide for special treatment of any particular script or language. The
design team members felt that there was no way to provide for such
handling that would not dramatically increase the complexity of the
protocol, and the apparent benefits in efficiency were relatively
modest. All the algorithms provide for relatively efficient treatment of
all scripts, and do not impose unreasonable limitations on label size
for users of particular scripts; the variation for particular scripts is
small in the proposed ACEs.

3. Weighing the Design Goals

3.1 Complexity

It is very difficult to analyze how complex an algorithm is. The
proposed ACE algorithms had different types of complexity and were
therefore difficult to compare accurately. For example, it is not clear
how to compare the complexity of a two-pass algorithm such as RACE or
LACE with one-pass algorithm with binary arithmetic such as DUDE. It was
pointed out that other algorithms that are quite complex have been
implemented well on the Internet.

It is not clear how important complexity is in the long run. One
argument says that most applications that use ACE will use an ACE
conversion toolkit supplied by an outside source, and there is likely to
be only a small number of such toolkits. An opposing argument is that,
even if that is true in most cases, there still has to be dozens if not
hundreds of toolkits for the various platforms on which IDN will be
supported. Further, many companies insist on writing all their own
software, even when it is complex (the IPsec market is a good example of
this).

3.2 Restrictions on long names that are likely to be used

The IDN WG had earlier agreed with the statement that the purpose of
compression is not to reduce the number of octets on the wire, but to
allow longer sensible name parts within the 63-octet limit.
Unfortunately, it is impossible to determine how long "sensible name
parts" would be in various scripts and languages. Some of what makes a
name part sensible is its usefulness in non-computer environments such
as on billboards, business cards, and radio commercials. Stringing
together many words is common in most languages, but it reduces the
reproducibility of a name.

The other side of this argument is that the domain name system requires
every name at a particular level of the name hierarchy to be unique. It
is quite common to see English names in the .com zone that clearly are
not the first choice of the companies or people who got them, most
likely because the desired (shorter) name was already taken. Because of
name exhaustion and the currently tightly-restricted choice in the TLD
zone, the length of sensible names is higher than it might be with more
TLDs available.

After asking many language experts, some of the people on the design
team came to the conclusion that 15 characters for Han-based languages
and 30 characters for alphabetic-based languages would put very few
restrictions on names that would reasonably be expected to be used. Of
course, any limit can be viewed as too restrictive, even the 63
character limit for current names. For example, the name:

computerengineeringdepartmentatuniversityofcaliforniasantabarbara

makes linguistic sense, but is unlikely to be used because it runs
together too many words, and would be unwieldy to type.

4. Analysis of the ACEs

The ACE drafts considered by the design team are listed here.
Note that these are not long-term documents and are therefore
not listed in the references section of this document.

4.1 All ACE proposals

draft-ietf-idn-altdude-00.txt -- AltDUDE. Withdrawn by author.

draft-ietf-idn-amc-ace-*-00.txt -- A series of one-step encodings with
varying degrees of complexity and compression.

draft-ietf-idn-brace-00.txt -- BRACE: Bi-mode Row-based ASCII-Compatible
Encoding for IDN. Withdrawn by author.

draft-ietf-idn-dude-02.txt -- Differential Unicode Domain Encoding
(DUDE). Uses a one-step encoding that uses the binary XOR of successive
characters, encoded with Base32.

draft-ietf-idn-dunce-00.txt -- DUNCE: A proposal for a Definitely
Unencumbered New Compatible [ACE] Encoding. Specifies multiple different
ways to encode strings directly but does not say how to make the
encoding unique. Also, does not specify a compression mechanism.

draft-ietf-idn-lace-01.txt -- LACE: Length-based ASCII Compatible
Encoding for IDN. Uses a two-step encoding: first compress (using a
simple run-length encoding algorithm), then use Base32 on the compressed
string.

draft-ietf-idn-race-03.txt -- RACE: Row-based ASCII Compatible Encoding
for IDN. This document expired.

draft-ietf-idn-sace-01.txt -- Simple ASCII Compatible Encoding (SACE).
This document expired.

draft-ietf-idn-step-00.txt -- StepCode- A User Access Oriented IDN
Encoding. Denotes Chinese characters with their phonetic elements. It
does not apply to other languages or scripts and is not based on the
ISO/IEC 10646 character repertoire.

draft-ietf-idn-utf6-00.txt -- UTF-6 - Yet Another ASCII-Compatible
Encoding for IDN. This document expired.

draft-ietf-idn-vidn-01.txt -- Virtually Internationalized Domain Names
(VIDN). Uses phonetic transliteration to create ACEs. There were many
problems for many languages that were pointed out on the WG mailing
list. The proposal is at least partially covered by a patent.

A draft on MACE, Modal ASCII-Compatible Encoding, is expected to be
published soon. The design team considered a preliminary version of the
encoding described my Makoto Ishisone.

4.2 Primary choices

The design team focused on three classes of ACE: LACE, DUDE, and the AMC
series. The ACEs had different levels of complexity and different
amounts of compression for mixes of one-row and multi-row input.

The following table summarizes the maximum length for an input string
for two cases: the entire string is a typical mix from one row (such as
a single-row script), and the entire string is in Han, which usually is
a mix of widely-divergent rows. Other comparisons are possible, of
course; you might compare how well each ACE does for primarily Latin
names (which use a mix from two rows), or names that are mostly
non-ASCII characters but use an occasional ASCII character such as a
dash.

           Equation for    Max for     Equation  Max for Han
           all one row   all one row   for Han     typical
             typical       typical     typical
DUDE         1.5n           39          3.8n        15
AMC-W        1.5n           39          1+3n        19
AMC-V        1.5n           39          1+3n        19
LACE       3.2+1.6n         34        1.6+3.2n      17

Two observations come out of this:

- All of the proposals give 34 or more characters for one row typical.
Except for strung-together names and some very long German or Thai
nouns, that is probably sufficient for most typical names.

- All of the proposals give 15 or more characters for Han typical.
Again, that is probably be fine for the vast majority of names, even
those with a few sub-names strung together.

Although LACE allows names with two more Han characters than DUDE, the
authors of LACE feel that the two-step process is indeed more
complicated and therefore did not warrant its use when compared to DUDE.

When compared to DUDE, AMC-W, and AMC-V get four more Han characters
with no loss of one-row characters. However, they are both more
complicated than DUDE. The members of the group disagreed as to how much
more complicated they were, with one group saying that they were "much
more complicated" and another group saying "only a little more
complicated".

5. Security Considerations

The design team did not perform security reviews on the ACE candidates.
A cursory review was done to see whether every Unicode string could
result in only one ACE string, and every ACE string could result in zero
or one Unicode strings. It is assumed that the authors of each ACE
proposal did more intense testing for the one-to-one correspondence.

6. References

References to particular ACE implementations are not given here because
none are currently RFCs and it is assumed that only one (or a small
number) will eventually reach RFC status.

7. Editor Contact Information

Paul Hoffman
Internet Mail Consortium and VPN Consortium
127 Segre Place
Santa Cruz, CA  95060 USA
[email-masked] and [email-masked]

---

From: Eric Brunner-Williams in Portland Maine <[email-masked]>
Date: Mon, 25 Jun 2001 13:04:07 -0400

Makoto San,

Thank you.

For Central African, a syllabary effort only recently begun, several of the
characters are in the Latin scripts, and several are not, and several more
are presently in the private use area. Can you comment on DUDE and smaller
sets of characters with this distribution property (two or more "clusters",
some low-range, some mid-range and/or some private-use range)?

Eric

---

From: "Jim Fleming" <[email-masked]>
Date: Mon, 25 Jun 2001 12:36:23 -0500

http://www.ntia.doc.gov/ntiahome/domainname/130dftmail/unir.txt
??? DUDE
??? ACE
4:86 RACE

Jim Fleming
http://www.unir.com
Mars 128n 128e
http://www.unir.com/images/architech.gif
http://www.unir.com/images/address.gif
http://www.unir.com/images/headers.gif
http://msdn.microsoft.com/downloads/sdks/platform/tpipv6/start.asp
http://www.ietf.org/mail-archive/ietf/Current/msg12213.html
http://www.ietf.org/mail-archive/ietf/Current/msg12223.html

----- Original Message ----- 
From: "Makoto Ishisone" <[email-masked]>
To: <[email-masked]>
Sent: Monday, June 25, 2001 11:32 AM
Subject: Re: [idn] Report from the ACE design team

> In message <p0510032cb74fd055e43c@[165.227.249.18]>,
> Paul Hoffman / IMC <[email-masked]> wrote:
> > ...
> As draft-ietf-idn-ace-report-00 says, the current recommendation of the
> ACE design team is DUDE.  However, as stated in the draft, the design
> team has not yet come to a complete agreement on DUDE, and I'm one of
> the members who is not convinced of the recommendation.
> 
> My opinion is certainly reflected in the draft, but I'd like to
> explain here the reason why I think DUDE may not be the best choice.
> 
> What I'm worrying about DUDE is its relative inefficiency for CJK
> scripts.
> 
> DUDE's compression algorithm (variable-length differential encoding)
> seems to work very efficiently when the code points of the characters
> in a name are clustered in a small range.  It is the case for most of
> Western scripts.
> 
> However, for languages with large number of characters (such as CJK),
> the algorithm tends to work poorly.  In the worst case DUDE encodes
> one Unicode character (in the Basic Multilingual Plane) as 4-octet
> sequence.  This happens frequently for CJK Han or Hangul names because
> the characters in these scripts are scattered in the Unicode code
> point space.
> 
> This means that in the worst case a name of 15 characters might not
> fit into a 63-octet label (assuming 4-octet prefix such as 'dq--').
> We expect that typically up to 15 character name can be encodable by
> DUDE.
> 
> The following points are my main concern:
> 
> 1) Is 14-15 character is enough?
>    At least for Japanese domain names, name of a company or an
>    organization is sometimes quite long.  My question is whether the
>    maximum of 14-15 character name for CJK is enough or not.  If it
>    is, DUDE would be fine.  But if it isn't, other ACE which is
>    more efficient (in dealing long names) but less simple might be
>    better.
> 
> 2) Potential migration problem
>    Many NICs has already begun registering internationalized domain
>    names using RACE as the ACE.  In RACE, any names up to
>    17-characters can be fit in 63-octet label.  So it is possible that
>    some of the registered names suddenly become invalid when migration
>    from RACE to DUDE take place.  Of course it is a risk that they
>    have to take, but if choosing other ACE can prevent it, or lower
>    the possibility, it might be a better choice.
> 
> -- [email-masked]
>

---

From: Makoto Ishisone <[email-masked]>
Date: Tue, 26 Jun 2001 01:32:16 +0900

-- [email-masked]

---

From: Maurizio Codogno <[email-masked]>
Date: Mon, 25 Jun 2001 20:31:31 +0200

> the characters in these scripts are scattered in the Unicode code

This is a factual statement, of course.

>    organization is sometimes quite long.

When I was younger, some Japanese friend explained me that usually a single
ideogram is the equivalent of a word in a Latin language. Now you seem to
imply something different. Could you please give some example of a name of
a Japanese organization with a long string of characters? (actually the
number of characters in Japanese and a rough translation will suffice,
since I cannot read Japanese).

>    names using RACE as the ACE.  

That's a problem of those NICs, and of the people who registered with RACE
before it was sanctioned as a standard... 

ciao, .mau.

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Mon, 25 Jun 2001 13:36:34 -0700

At 1:32 AM +0900 6/26/01, Makoto Ishisone wrote:
>    maximum of 14-15 character name for CJK is enough or not.

There is an assumption in those statements, which is that a Japanese 
or Chinese company with a very long name would need a DNS name that 
is as long as their very long name. As we have discussed on this list 
many times, companies and organizations with "difficult" names (such 
as very long or hard to remember) often would prefer to use shorter 
domain names that are more useful to end users. These might be 
abbreviations or pseudonyms, but the result is the same: a domain 
name that end users can transcribe more easily. So, the question of 
maximum 15 characters is not "are there names that are this long" 
because certainly there are (just as there are European company names 
that are too long for any ACE encoding), but "are there names that 
this long that people would actually want end users to enter". This, 
of course, is a judgement call.

>2) Potential migration problem

I agree with the others who have said that this should not be an 
issue. If we try to balance with RACE, we must also balance with all 
the other pre-standard encodings, some of which can handle CJK names 
that are longer than any ACE could possibly achieve.

--Paul Hoffman, Director
--Internet Mail Consortium

---

From: Dave Crocker <[email-masked]>
Date: Sun, 24 Jun 2001 17:59:57 -0400

Folks,

At 04:36 PM 6/25/2001, Paul Hoffman / IMC wrote:
>I agree with the others who have said that this should not be an issue. If 
>we try to balance with RACE, we must also balance with all the other 
>pre-standard encodings,

The question of whether to support "pre-standards" technology is -- by 
definition -- a question of whether to spend energy on proprietary history.

There are probably some cases where the answer should be yes.  However it 
is difficult to believe that this is one of them.

The only serious argument that gets used for such support is "installed 
base".  That is, a concern that there is such a large installed base of 
users that it is necessary to the success of the standard, that transition 
support be provided.

Without in any way demeaning the pre-standards IDN efforts, it is difficult 
to believe that it can claim that large an installed base or that 
"essential" an installed base.

d/

----------
Dave Crocker  <mailto:[email-masked]>
Brandenburg InternetWorking  <http://www.brandenburg.com>
tel +1.408.246.8253;  fax +1.408.273.6464

---

From: Yoshiro YONEYA <[email-masked]>
Date: Tue, 26 Jun 2001 11:42:13 +0900 (JST)

Hi,

From: Paul Hoffman / IMC <[email-masked]>
Subject: Re: [idn] Report from the ACE design team
Date: Mon, 25 Jun 2001 13:36:34 -0700

> domain names that are more useful to end users. 

From my observation, many of long name organizations seem to register
both "exact" name and "shorter" name.  I agree that shorter domain
names are useful for end users.  While, I think it is also important
for IDN to maximize possibility of representing organization's exact
name.  The difficulty of remembering would depend on how much the name
is popular.

-- 
Yoshiro YONEYA <[email-masked]>
           aka <[email-masked]>

---

From: Tony Hansen <[email-masked]>
Date: Tue, 26 Jun 2001 08:41:37 -0400

Since there are pre-existing NIC RACE databases, can representatives
from those NICS give us a histogram for different CJK domain name
lengths? From the histogram, we can deduct a few things. For example, if
the number of 16 and 17 character names is 0, then there is no problem
migrating. The curve of the histogram can also provide probabilities for
those long names. (The 0.01% estimate bandied about may be high or it
may be low. It would be interesting to see real data from the NICs to
back up the estimate.)

	Tony Hansen
	[email-masked]

---

From: Makoto Ishisone <[email-masked]>
Date: Tue, 26 Jun 2001 22:27:40 +0900

In message <[email-masked]>,
Eric Brunner-Williams in Portland Maine <[email-masked]> wrote:
> Can you comment on DUDE and smaller

DUDE uses a kind of differential encoding -- that is, the encoding
length of a single character is solely dependent on the "difference"
between the code point of the character and the previous one. If the
difference is confined in their lower 4 bits, the encoding length is
one.  If it is confined in the lower 8 bits, the length is two, and so
on.

So, even if there are two clusters, as long as the switching between
clusters is not frequent, DUDE's compression algorithm is effective.

Also DUDE's algorithm (and other ACEs as well) is independent of
whether a character is in a private-use area or not.  However, I think
private-use characters are prohibited by NAMEPREP and cannot be used..

					      -- [email-masked]

---

From: Makoto Ishisone <[email-masked]>
Date: Tue, 26 Jun 2001 22:52:14 +0900

In message <[email-masked]>,
Maurizio Codogno <[email-masked]> wrote:
> ideogram is the equivalent of a word in a Latin language.

A single ideogram has a certain meaning(s) (that's what ideogram is),
but I don't think it is an equivalent of a Latin word.  If it is, the
number of Japanese words is so small :-)  It is more like a combination
of a few ideograms that is comparable to Latin word, I think.

> Could you please give some example of a name of

Sure.  I looked around and found two examples.  Both names exceed 15
characters and DUDE cannot encode them, but other more space efficient
ACEs can.

1. JPNIC (the registry of .jp domain)
JPNIC's official name consists of 25 characters.  Most of the characters
are phonograms (Katakana), though.

  U+793E U+56E3 U+6CD5 U+4EBA U+65E5 U+672C U+30CD U+30C3 U+30C8 \
  U+30EF U+30FC U+30AF U+30A4 U+30F3 U+30D5 U+30A9 U+30E1 U+30FC \
  U+30B7 U+30E7 U+30F3 U+30BB U+30F3 U+30BF U+30FC

2. A helth-insurance organization in Tokyo
This name also contains a few phonograms, but most are ideograms.

  U+6771 U+4EAC U+90FD U+60C5 U+5831 U+30B5 U+30FC U+30D3 U+30B9 \
  U+7523 U+696D U+5065 U+5EB7 U+4FDD U+967A U+7D44 U+5408

						   -- [email-masked]

---

From: Maurizio Codogno <[email-masked]>
Date: Tue, 26 Jun 2001 23:16:26 +0200

In die Tue, 26 Jun 2001 22:52:14 +0900
Makoto Ishisone <[email-masked]> scripsit:

> but I don't think it is an equivalent of a Latin word. 

You are right, I should have talked about a (rough) concept or idea. My fault.

> > a Japanese organization with a long string of characters? 

let's leave aside the fact that probably, since there are a lot of Katakana, DUDE 
could manage to encode it. I am still puzzled for a cultural difference.
If I understand it correctly, this name could be roughly seen as 
"JapaneseCenterForInternetNames". Are you hinting that people in Japan 
prefer to address it with such a long name, and not with an abbreviation?

The firm I work for is Telecom Italia Lab, for example, but we try not to use the 
long name telecomitalialab.com, and prefer the shorter tilab.com.
If this is not the case for countries which use Han-based characters, I fear 
that even other ACEs or UTF-8 are not the right solution, since the limit does
not rise significatively,

ciao ,.mau.

---

From: Eric Brunner-Williams in Portland Maine <[email-masked]>
Date: Wed, 27 Jun 2001 13:48:11 -0400

Makoto San,

Thank you for your informative comments.

It appears to me that on average every third character in the proposed
Central African Syllabary will switch between one of three clusers, so
broadly, this (very young) proposal and any in the same class:

	o using 2 or more distinct existing 8-bit or sub-8-bit repitoires,
or
	o using a single 8-bit or sub-8-bit repitoire and and using the
	  private use area to supplement that repitoire
or
	o both

and
	o little or no correlation between repitiores used by sequential
	  characters

should have the property you pointed out w.r.t. DUDE and larger contiguous
(super-8-bit) repitoires, e.g., marginal encoding compression.

Broadly, this is a property I've observed in more than once - as a repitoire
is constructed. Finding a set of pre-existing glyphs isn't the same thing as
creating a set of glyphs with some set of properties, e.g., order, contiguity,
etc.

The effect of disallowing private-use characters, at least in the CA Syllabary,
may be to restrict the repitoire to Latin, which probably isn't acceptable to
the interested parties, at least until the UNICODE Script WG and dependent
actors get their jobs done -- a set of subjects for a different list.

Again, thanks!
Eric

---

From: Eric Brunner-Williams in Portland Maine <[email-masked]>
Date: Wed, 27 Jun 2001 13:48:11 -0400

Makoto San,

and

Again, thanks!
Eric

---

From: "James Seng/Personal" <[email-masked]>
Date: Thu, 28 Jun 2001 09:00:59 +0800

1. both bq--aauf4326fe and bq--abpf6xq are invalid RACE if we follow
   the specification closely.

2. If you want to talk about "(^o^)" and "^_^" TLDs, the appropriate
   forum is not this WG.

Please keep to the technical discussion on topic. Thanks!

-James Seng

----- Original Message -----
From: "Jim Fleming" <[email-masked]>
To: "Makoto Ishisone" <[email-masked]>; "Eric Brunner-Williams in
Portland Maine" <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>
Sent: Thursday, June 28, 2001 8:43 AM
Subject: Re: [idn] Report from the ACE design team

> Are TLDs included ?
>
> http://root-dns.org/ZoneExchange/AIS.txt
>
> bq--aauf4326fe.   172800   TXT   "Manager : The Universal Registry"
> bq--aauf4326fe.   172800   TXT   "Established : 2001"
> bq--aauf4326fe.   172800   NS   us.universalroot.com.
> bq--aauf4326fe.   172800   NS   uk.universalroot.com.
> bq--aauf4326fe.   172800   NS   hk.universalroot.com.
>
> bq--abpf6xq.   172800   TXT   "Manager : The Universal Registry"
> bq--abpf6xq.   172800   TXT   "Established : 2001"
> bq--abpf6xq.   172800   NS   us.universalroot.com.
> bq--abpf6xq.   172800   NS   uk.universalroot.com.
> bq--abpf6xq.   172800   NS   hk.universalroot.com.
>
> From: "Eric Brunner-Williams in Portland Maine" <[email-masked]>
> To: "Makoto Ishisone" <[email-masked]>
> Cc: <[email-masked]>; <[email-masked]>; <[email-masked]>
> Sent: Wednesday, June 27, 2001 12:48 PM
> > is constructed. Finding a set of pre-existing glyphs isn't the same
thing
> as
> > may be to restrict the repitoire to Latin, which probably isn't
acceptable
> to

---

From: "Jim Fleming" <[email-masked]>
Date: Wed, 27 Jun 2001 19:43:48 -0500

Are TLDs included ?