Subject: Best practice for data encoding?

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 5 Jun 2006 23:43:45 +0200

I was wondering:

What is considered best practice for encoding data in protocols  
within the IETF's purview?

Traditionally, many protocols use text but obviously this doesn't  
really work for protocols that carry a lot of data, because text  
lacks structure so it's hard to parse. XML and the like are text- 
based and structured, but take huge amounts of code and processing  
time to parse (especially on embedded CPUs that lack the more  
advanced branch prediction available in the fastest desktop and  
server CPUs). Then there is the ASN.1 route, but as we can see with  
SNMP, this also requires lots of code and is very (security) bug  
prone. Many protocols use "hand crafted" binary formats, which has  
the advantage that the format can be tailored to the application but  
it requires custom code for every protocol and it's hard to get  
right, especially the simplicity/extendability tradeoff.

The ideal way to encode data would be a standard that requires  
relatively little code to implement, makes for small files/packets  
that are fast to process but remains reasonably extensible.

So, any thoughts? Binary XML, maybe?

_______________________________________________
Ietf mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ietf

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 6 Jun 2006 00:41:05 +0200

> within the IETF's purview?

The best practice is to choose an encoding that is appropriate for  
the protocol being designed.
(There is no single answer.)

Maybe you can be more specific in your question, then maybe people  
can be more specific in their answers?

Gruesse, Carsten

---

From: "Randy Presuhn" <[email-masked]>
Date: Mon, 5 Jun 2006 16:06:28 -0700

Hi -

> From: "Iljitsch van Beijnum" <[email-masked]>
> To: "IETF Discussion" <[email-masked]>
> Sent: Monday, June 05, 2006 2:43 PM
> Subject: Best practice for data encoding?
...
> Then there is the ASN.1 route, but as we can see with  
> prone.
...

Having worked on SNMP toolkits for a long time, I'd have to
strenuously disagree.  In my experience, the ASN.1/BER-related
code is a rather small portion of an SNMP protocol engine.
The code related to the SNMP protocol's quirks, such as Get-Next/Bulk
processing and the mangling of index values into object identifiers
(which is far removed from how ASN.1 intended object identifiers
to be used) require much more code and complexity.

I'm curious, too, about the claim that this has resulted in security
problems.  Could someone elaborate?

Randy

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 5 Jun 2006 19:09:47 -0400

> to be used) require much more code and complexity.

Yah -- measure first, then optimize.

> problems.  Could someone elaborate?
See http://www.cert.org/advisories/CA-2002-03.html

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: "Randy Presuhn" <[email-masked]>
Date: Mon, 5 Jun 2006 16:40:35 -0700

Hi -

> From: "Steven M. Bellovin" <[email-masked]>
> To: "Randy Presuhn" <[email-masked]>
> Cc: <[email-masked]>
> Sent: Monday, June 05, 2006 4:09 PM
> Subject: Re: Best practice for data encoding?
...
...

I remember that exercise.  I don't see it as convincing evidence that
the use of ASN.1 was the cause of the problems some implementations
had; I doubt that someone who had buffer overflow problems when
processing a BER-encoded octet string (where the length is explicitly
encoded) would have had any better results with XML or any other
representation.

Randy

---

From: "David Harrington" <[email-masked]>
Date: Mon, 5 Jun 2006 20:07:24 -0400

Hi 

The security problems identified in
http://www.cert.org/advisories/CA-2002-03.html "Multiple
Vulnerabilities in Many Implementations of the Simple Network
Management Protocol (SNMP)" are not caused by the protocol choice to
use ASN.1, but by vendors incorrectly implementing the protocol (which
was made worse by vendors using toolkits that had the problems).

If "Multiple Vulnerabilities in Implementations" were used to condemn
the encoding methods of protocols that have been incorrectly
implemented, then we would have to condemn an awful lot of IETF
protocols as being very (security) bug prone: 

CERT Advisory CA-2003-26 Multiple Vulnerabilities in SSL/TLS
Implementations
US-CERT Vulnerability Note VU#459371 Multiple IPsec implementations do
not adequately validate
 CERTR Advisory CA-2001-18 Multiple Vulnerabilities in Several
Implementations of the Lightweight Directory Access Protocol (LDAP) 
CERT Advisory CA-2002-36 Multiple Vulnerabilities in SSH
Implementations
 CERTR Advisory CA-2003-06 Multiple vulnerabilities in implementations
of the Session Initiation Protocol (SIP) 
Vulnerability Note VU#428230 Multiple vulnerabilities in S/MIME
implementations
Vulnerability Note VU#955777 Multiple vulnerabilities in DNS
implementations
Vulnerability Note VU#226364 Multiple vulnerabilities in Internet Key
Exchange (IKE) version 1 implementations
CERTR Advisory CA-2002-06 Vulnerabilities in Various Implementations
of the RADIUS Protocol
CERTR Advisory CA-2000-06 Multiple Buffer Overflows in Kerberos
Authenticated Services
Vulnerability Note VU#836088 Multiple vendors' email content/virus
scanners do not adequately check "message/partial" MIME entities

David Harrington
[email-masked] 
[email-masked]
[email-masked]

> -----Original Message-----
> From: Steven M. Bellovin [mailto:[email-masked]] 
> Sent: Monday, June 05, 2006 7:10 PM
> To: Randy Presuhn
> Cc: [email-masked]

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 5 Jun 2006 20:21:29 -0400

> protocols as being very (security) bug prone: 

Works for me....

More precisely -- when something is sufficiently complex, it's inherently
bug-prone.  That is indeed a good reason to push back on a design.  The
question to ask is whether the *problem* is inherently complex -- when the
complexity of the solution significanlty exceeds the inherent complexity of
the problem, you've probably made a mistake.  When the problem itself is
sufficiently complex, it's fair to ask if it should be solved.  Remember
point (3) of RFC 1925.

I'll note that a number of the protocols you cite were indeed criticized
*during the design process* as too complex.  The objectors were overruled.

---

From: "David Harrington" <[email-masked]>
Date: Mon, 5 Jun 2006 20:32:58 -0400

I agree that complexity breeds bug-prone implementations.

I wasn't around then; did anybody push back on SNMPv1 as being too
complex? http://www.cert.org/advisories/CA-2002-03.html is mainly
about SNMPv1 implementations. ;-)

dbh

> Sent: Monday, June 05, 2006 8:21 PM
> To: David Harrington
> Cc: [email-masked]; [email-masked]

---

From: "Fleischman, Eric" <[email-masked]>
Date: Mon, 5 Jun 2006 17:41:23 -0700

Let's not forget that the "S" in SNMP stands for "simple". "Simple" is a
relative term. In this case, SNMP is simple when compared to CMIP.

-----Original Message-----
From: David Harrington [mailto:[email-masked]] 
Sent: Monday, June 05, 2006 5:33 PM

I wasn't around then; did anybody push back on SNMPv1 as being too
complex? http://www.cert.org/advisories/CA-2002-03.html is mainly about
SNMPv1 implementations. ;-)

dbh

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 05 Jun 2006 20:51:08 -0400

On Monday, June 05, 2006 08:32:58 PM -0400 David Harrington 
<[email-masked]> wrote:

> complex?

I don't think anyone pushed back on SNMPv1 as being inherently insecure.

---

From: Michael Thomas <[email-masked]>
Date: Mon, 05 Jun 2006 17:54:16 -0700

>about SNMPv1 implementations. ;-)

I wasn't there to push back, but when I got asked to implement it back then
the Simple part such seemed like something between a fib and the Big Lie.
Did we really need ASN.1 to define a debug peek/poke-like protocol?

       Mike

>>>Management Protocol (SNMP)" are not caused by the protocol choice
>>>      
>>>
>to
>  
>
>>>use ASN.1, but by vendors incorrectly implementing the 
>>>      
>>>
>>protocol (which
>>    
>>
>>>If "Multiple Vulnerabilities in Implementations" were used 
>>>      
>>>
>>to condemn
>>    
>>

---

From: "Randy Presuhn" <[email-masked]>
Date: Mon, 5 Jun 2006 21:20:18 -0700

Hi -

> From: "Fleischman, Eric" <[email-masked]>
> To: "David Harrington" <[email-masked]>; "Steven M. Bellovin" <[email-masked]>
> Cc: <[email-masked]>
> Sent: Monday, June 05, 2006 5:41 PM
> Subject: RE: Best practice for data encoding?
>
> relative term. In this case, SNMP is simple when compared to CMIP

We implemented both protocols.  The core protocol engine for SNMP
ended up being larger and more complex than that for CMIP.  The
complexity of GetNext, along with OID mangling, accounted for much
of the difference.   The "S" in SNMP was half marketing and half politics,
and had very little to do with actual implementation or use.

Randy

---

From: Eliot Lear <[email-masked]>
Date: Tue, 06 Jun 2006 08:50:01 +0200

Iljitsch van Beijnum wrote:
> I was wondering:
>
> What is considered best practice for encoding data in protocols within
> the IETF's purview?
One should always think about what one needs and choose the appropriate
solution to the task.  Of course sometimes it's hard to take into
account what level of performance one would need out of a protocol
implementation.  RAM is considerably cheaper now than it was twenty
years ago, and so one approach in protocol design would be to define
multiple encodings as they are required.  So, if you don't think
performance is crucial but toolset reuse is for an RPC-based approach,
perhaps XML is a good start, and if you need to optimize later, perhaps
consider something more compact like XDR.

As to whether ASN.1 was a good choice or a bad choice for SNMP, there
never was an argument.  It was THE ONLY CHOICE.  All three protocols
(CMIP, SGMP, HEMP)  under consideration made use of it.  Nobody
seriously considered anything else due to the practical limits of the
time.  Is it still a reasonable approach?  I think a strong argument
could be made that some sort of textual representation is necessary in
order to satisfy more casual uses and to accommodate tool sets that are
more broadly utilized, but that doesn't mean that we should do away with
ASN.1, archaic as it may seem.

Eliot

---

From: Tony Finch <[email-masked]>
Date: Tue, 6 Jun 2006 12:26:08 +0100

> Vulnerability Note VU#428230 Multiple vulnerabilities in S/MIME

Oh yes, I forgot those were ASN.1 too.

Tony.
-- 
f.a.n.finch  <[email-masked]>  http://dotat.at/
FORTIES CROMARTY FORTH TYNE DOGGER: VARIABLE 3 OR 4. MAINLY FAIR. MODERATE OR
GOOD.

---

From: Tony Finch <[email-masked]>
Date: Tue, 6 Jun 2006 12:19:24 +0100

> See http://www.cert.org/advisories/CA-2002-03.html

ASN.1 implementation bugs have also caused security problems for SSL,
Kerberos, ISAKMP, and probably others. These bugs are also not due to
shared code history: they turn up again and again.

Are there any other binary protocols that can be usefully compared with
ASN.1's security history?

Tony.
-- 
f.a.n.finch  <[email-masked]>  http://dotat.at/
THE MULL OF GALLOWAY TO MULL OF KINTYRE INCLUDING THE FIRTH OF CLYDE AND THE
NORTH CHANNEL: VARIABLE 2 OR 3 WITH AFTERNOON ONSHORE SEA BREEZES. FAIR
VISIBILITY: MODERATE OR GOOD WITH MIST OR FOG PATCHES SEA STATE: SMOOTH OR
SLIGHT.

---

From: "Christian Huitema" <[email-masked]>
Date: Tue, 6 Jun 2006 10:33:30 -0700

> ASN.1's security history?

There is indeed a lot of complexity in ASN.1. At the root, ASN.1 is a
basic T-L-V encoding format, similar to what we see in multiple IETF
protocols. However, for various reasons, ASN.1 includes a number of
encoding choices that are as many occasions for programming errors:

* In most TLV applications, the type field is a simple number varying
from 0 to 254, with the number 255 reserved for extension. In ASN.1, the
type field is structured as a combination of scope and number, and the
number itself can be encoded on a variable number of bytes.
* In most TLV applications, the length field is a simple number. In
ASN.1, the length field is variable length.
* In most TLV applications, structures are delineated by the length
field. In ASN.1, structures can be delineated either by the length field
or by an "end of structure" mark.
* In most TLV applications, a string is encoded as just a string of
bytes. In ASN.1, it can be encoded either that way, or as a sequence of
chunks, which conceivably could themselves be encoded as chunks.
* Most applications tolerate some variations in component ordering and
deal with optional components, but ASN.1 pushes that to an art form.
* I don't remember exactly how many alphabet sets ASN.1 does support,
but it is way more than your average application.
* Most applications encode integer values by reference to classic
computer encodings, e.g. signed/unsigned char, short, long, long-long.
ASN.1 introduces its own encoding, which is variable length.
* One can argue that SNMP makes a creative use of the "Object
Identifier" data type of ASN.1, but one also has to wonder why this data
type is specified in the language in the first place.

Then there are MACRO definitions, VALUE specifications, and an even more
complex definition of extension capabilities. In short, ASN.1 is vastly
more complex that the average TLV encoding. The higher rate of errors is
thus not entirely surprising.

-- Christian Huitema

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 06 Jun 2006 14:17:15 -0400

> encoding choices that are as many occasions for programming errors:

To be pedantic, ASN.1 is what its name says it is - a notation.
The properties you go on to describe are those of BER; other encodings have 
other properties.  For example, DER adds constraints such that there are no 
longer multiple ways to encode the same thing.  Besides simplifying 
implementations, this also makes it possible to compare cryptographic 
hashes of DER-encoded data; X.509 and Kerberos both take advantage of this 
property.  PER eliminates many of the tags and lengths, and my 
understanding is that there is a set of rules for encoding ASN.1 data in 
XML.

> type is specified in the language in the first place.

Well, I can't speak to the orignial motivation, but under BER, encoding the 
same sort of heirarchical name as a SEQUENCE OF INTEGER takes about three 
times the space the primitive type does, assuming most of the values are 
small.

> thus not entirely surprising.

There certainly is a rich set of features (read: complexity) in both the 
ASN.1 syntax and its commonly-used encodings.  However, I don't think 
that's the real source of the problem.  There seem to be a lot of ad-hoc 
ASN.1 decoders out there that people have written as part of some other 
protocol, instead of using an off-the-shelf compiler/encoder/decoder; this 
duplication of effort and code is bound to lead to errors, especially when 
it is done with insufficient attention to the details of what is indeed a 
fairly complex encoding.

I also suspect that a number of the problems found have nothing to do with 
decoding ASN.1 specifically, and would have come up had other approaches 
been used.  For example, several of the problems cited earlier were buffer 
overflows found in code written well before the true impact of that problem 
was well understood.  These problems are more likely to be noticed and/or 
create vulnerabilities when they occur in things like ASN.1 decoders, or 
XDR decoders, or XML parsers, because that code tends to deal directly with 
untrusted input.

-- Jeffrey T. Hutzelman (N3NHS) <[email-masked]>
   Sr. Research Systems Programmer
   School of Computer Science - Research Computing Facility
   Carnegie Mellon University - Pittsburgh, PA

---

From: Dean Anderson <[email-masked]>
Date: Tue, 6 Jun 2006 23:53:19 -0400 (EDT)

Some ASN.1 compilers have had some bugs, however, this does not to indicate that
ASN.1 is bug prone. Just the opposite: Once you have a secure compiler, you can
be assured that certain kinds of bugs don't exist.

Further, in the few cases of the bugs that were found, once the bug is fixed in
the ASN.1 compiler, the application just needs to be relinked (or given new
shared library) with the new generated runtime.  And any other application which
used a vulnerable runtime, but for which the vulnerability was unknown, is also
fixed.  So, users of compiled runtime benefit from usage experience by the
entire group.

Building tools that make trustable runtimes is a good approach to certain
classes of security problems. You can't get this by hand written protocol
encode/decode layers.

		--Dean

-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 344 9000

---

From: Theodore Tso <[email-masked]>
Date: Wed, 7 Jun 2006 07:52:55 -0400

> sufficiently complex, it's fair to ask if it should be solved.  Remember

One of the complaints about ASN.1 is that it is an enabler of
complexity.  It becomes easy to specify some arbitrarily complex data
structures, and very often with that complexity comes all sorts of
problems.  To be fair, though, the same thing can be said of XML (and
I'm not a big fan of a number of specifications utilizing XML either,
for the same reason), and ultimately, "you can write Fortran in any
language".

Ultimately, I have to agree with Steve, it's not the encoding, it's
going to about asking the right questions at the design phase more
than anything else, at least as far as the protocol is concerned.

As far as implementation issues, it is true that ASN.1 doesn't map
particularly well to standard programming types commonly in use,
although if you constrain the types used in the protocol that issue
can be relative easily avoided (so would using XML, or a simpler
ad-hoc encoding scheme).  I don't think there is any right answer
here, although my personal feelings about ASN.1 can still be summed up
in the aphorism, "Friends don't let friends use ASN.1", but that's
mostly due to psychic scars caused by my having to deal with the
Kerboers v5 protocol's use of ASN.1, and the feature and design bloat
that resulted from it.

						- Ted

---

From: Michael Thomas <[email-masked]>
Date: Wed, 07 Jun 2006 07:37:28 -0700

>Kerboers v5 protocol's use of ASN.1, and the feature and design bloat
Here's my down in the trenches observations about XML and to some degree 
ASN.1.
XML gives me the ability to djinn up a scheme really quickly with as 
much or as
little elegance as needed. If nothing else, XML quite rapidly allows me 
to hack up
intpreters that would otherwise been another parsed text file casuality 
residing in /etc.
And most likely, if they could read the previous text encoding, the XML 
is about as
transparent. This is a very nice feature as it allows common parsers, 
leads to common
practices about how to lay out simple things, and common understanding 
about what
is right and wrong. So, for my standpoint XML is "no more ad hoc 
parsers!", which
is good from a complexity standpoint, especially when you look at how 
spare the
base syntax is.

That said, anything that requires nested structure, etc XML is probably 
just as
inadequate as anything else. And who should be surprised? Don't blame the
Legos that they self-assemble into a rocket ship. One big plus about XML is
that I can just _read_ it and hack up pretty printers in trivial time. 
ASN.1 that is,
um, abstract necessasrily needs to go through a translation layer which IMO
is never as fun and convenient -- and absolutely discourages dilitante 
hacking (when
is the last time you fiddled with an XML file vs. the last time you 
fiddled with
ANS.1? never for the latter?).

I guess that what part of what this devolves into is who we're writing these
protocols/schemes for: machines or people? That, I think, is a huge false
dilemma. We clearly are writing things for _both_ (the executors and the
maintainers) ; the only question in my mind is whether an easy for human
to maintain encoding is too inefficient on the wire for its task. In some
cases it clearly is, but those cases are becoming the outliers -- especially
at app layer -- as the march of memory and bandwidth plods on.

So with all of these wars, the sexy overblown hype ("yes of course XML can
solve world hunger!") often eclipses the routine and mundane tasks of 
writing
and maintaining a system (golly, I need a config file for this, it's 
been a while
since I wrote a really crappy parser. woo woo!). C'est la vie.

       Mike

---

From: Dave Cridland <[email-masked]>
Date: Wed, 07 Jun 2006 21:38:51 +0100

> at app layer -- as the march of memory and bandwidth plods on.

I think it's worth noting that nobody is preventing you from using 
XML over a compressed channel, which tends to increase XML's 
efficiency rather sharply.

Compression also tends to make you look differently at protocol 
issues, because the repetitive, inefficient, protocol forms often 
compress equally well to, or even better than, a "better" structure - 
and they're also usually easier to handle.

Wire efficiency, for the most part, needs to take place by avoiding 
the transmission of information entirely, rather than trying to 
second-guess the compression.

As a rule, if you're moving strings around, or eliminating 
duplicates, within a single "send" of your protocol, you're probably 
wasting your time. In general, you want to be avoiding sending 
information at all.

The only reason you have for worrying about representation for wire 
efficiency is if resource shortage prevents you from compression 
entirely - bear in mind this implies that resource shortage has 
already prevented you from encryption - generally a bad thing.

As an example, IMAP and ACAP streams compress by around 70% on my 
client - and that's trying to be bandwidth efficient in its protocol 
usage. I've seen figures of 85% talked about quite seriously, too.

So in answer to the original question, I'd say that the current best 
practise for data encoding has to be RFC1952, Deflate - beyond that, 
it really doesn't matter all that much.

As an aside, whilst XMPP does provide a "pure" XML protocol, most 
protocols use XML as a payload, and use other forms to exchange 
protocol messages.

Dave.
-- 
Dave Cridland - mailto:[email-masked] - xmpp:[email-masked]
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 8 Jun 2006 00:19:29 +0200

> efficiency rather sharply.

[...]

> second-guess the compression.

Obviously adding compression doesn't help processing efficiency.

I've long harbored the suspicion that a large percentage of the  
cycles in today's fast CPUs are burned up parsing various types of  
text. Does anyone know of any processing efficiency comparisons  
between binary and text based protocols?

> client - and that's trying to be bandwidth efficient in its  
> protocol usage. I've seen figures of 85% talked about quite  
> seriously, too.

And you think that's a good thing? Now I understand why it takes me  
up to 10 minutes to download a handful of 1 - 2 kbyte emails with  
IMAP (+SSL) over a 9600 bps GSM data connection.

---

From: Dave Cridland <[email-masked]>
Date: Thu, 08 Jun 2006 08:50:14 +0100

On Wed Jun  7 23:19:29 2006, Iljitsch van Beijnum wrote:
>> Wire efficiency, for the most part, needs to take place by 
>> avoiding  the transmission of information entirely, rather than 
>> trying to  second-guess the compression.
> 
It does if you're doing encryption, unless the protocol itself is 
almost entirely uncompressible. Compression is a lot cheaper than 
encryption, and the more you compress, the less you have to encrypt.

> between binary and text based protocols?
But it's a clear trade-off between efficient representation and 
complexity for the developer - we've had this debate once already in 
this thread, I think. The more complex the representation, the harder 
it is to code correctly and debug.

I'm not saying there's no place for binary protocols, but I am saying 
that to go for a binary representation, you have to be working in a 
highly resource constrained environment where both bandwidth and CPU 
usage is highly limited.

> And you think that's a good thing?

No, it demonstrates that even protocols which have a reputation for 
chatter actually turn out to be efficient on the wire 
post-compression.

>  Now I understand why it takes me  up to 10 minutes to download a 
> handful of 1 - 2 kbyte emails with  IMAP (+SSL) over a 9600 bps GSM 
> data connection.

I can write an efficient IMAP client, and give it away for free, but 
I can't force you to use it. :-)

I can read a new message inside a minute over 9600bps with 1 second 
latency, without even using a local disk cache - including fetching 
configuration over ACAP to begin with. My INBOX contains 24,033 
messages currently - obviously I'm not downloading them all, and this 
is emulated bandwidth and latency, thus not entirely accurate.

IMAP can be extremely efficient; if it's taking you 10 minutes to 
read a handful of emails, you're using the wrong client, the wrong 
server, or quite possibly both. With Lemonade features coming into 
mainstream implementations, you really ought to be looking at your 
systems if you're using GSM data. Compression is not really one of 
these, oddly enough, but TLS deflate ought to be available to most 
clients and servers by now anyway.

Dave.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 8 Jun 2006 11:13:43 +0200

On 8-jun-2006, at 9:50, Dave Cridland wrote:

>> cycles in today's fast CPUs are burned up parsing various types  
>> of  text. Does anyone know of any processing efficiency  
>> comparisons  between binary and text based protocols?

> complexity for the developer - we've had this debate once already  
> in this thread, I think. The more complex the representation, the  
> harder it is to code correctly and debug.

Simple/complex isn't the same as text/binary. I'm pretty sure a  
programmer armed with nothing more than a standard issue C compiler  
and the basic libraries that come with it, would have a harder time  
parsing XML than something like the DNS protocol. But my point was  
that the resulting code would be slower. I know it's very old- 
fashioned to even consider such things, but there are places where  
performance is important beyond just philosophical objections against  
bloat.

>> handful of 1 - 2 kbyte emails with  IMAP (+SSL) over a 9600 bps  
>> GSM data connection.

> I can write an efficient IMAP client, and give it away for free,  
> but I can't force you to use it. :-)

It's not that I'm a huge fan of Apple's Mail but it's the only GUI  
mail application I've found so far that I can actually work with  
without the irresistible urge to chew through the mouse cable and  
dust off my VT420 terminal... (Which allows me to read my mail with  
Pine without any trouble over 9600 bps.)

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 09 Jun 2006 15:07:05 +0200

So how about concluding that there is no single
right answer to Iljitsch's question, but there may
be scope for defining considerations for the choice
of data encoding?

     Brian

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 12 Jun 2006 12:33:37 +0200

> performance is important beyond just philosophical objections  
> against bloat.

A little post script to this discussion: I wrote a few small test  
programs in C to evaluate the performance of reading integers from a  
text file using <stdio.h> versus doing the same with direct read()s  
from a binary file. The difference is between two and three orders of  
magnitude. See http://ablog.apress.com/?p=1146

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 12 Jun 2006 13:31:25 +0200

> programs in C to evaluate the performance of reading integers from  
> a text file using <stdio.h> versus doing the same with direct read() 
> s from a binary file. The difference is between two and three  
> orders of magnitude. See http://ablog.apress.com/?p=1146

Iljitsch,

in your original question to the list, you didn't quite make clear  
that your question was with respect to BGP-style transfer of large- 
scale routing information.

Right now, you seem to focus on decoding performance.  How much of  
the CPU time spent for BGP is decoding?
Does the CPU time spent for the entirety of BGP even matter*?  If  
yes, can a good data structure/encoding help with the *overall* problem?

The results from your test programs are not at all surprising.
Of course, a hand-coded loop where all data already is in the right  
form (data type, byte order, number of bits), no decisions need to be  
made, and you even know the number of data items beforehand, is going  
to be faster than calling the generic, pretty much neglected,  
parameterized, tired library routine fscanf that doesn't get much use  
outside textbooks.
(The "read" anomaly is caused by read(2) being an expensive system  
call; all other cases use a form of buffering to reduce the number of  
system calls.)
What this example shows nicely is that performance issues are non- 
trivial, and, yes, you do want to run measurements, but at the system  
level and not at the level of "test cases" that have little or no  
relationship to the performance of the real system.

If you really care about the performance of text-based protocols, you  
cannot ignore modern tools like Ragel.
If, having used them, you still manage to find the text processing  
overhead in your profiling data, I'd like to hear from you.

Still, for BGP, a binary protocol encoding may be a better fit  
because routing tables are so much about bits and prefixes and other  
numeric information already designed to be used in binary protocol  
encodings.
Also, it may be easier to reduce both data rate and processing by  
exploiting more of the structure of the BGP routing information.
(I.e., to make it redundantly clear, I would probably choose binary  
here, but not for the reasons given in your blog post.)

Gruesse, Carsten

*) Yes, that's a trick question to elicit responses :-)

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 12 Jun 2006 14:11:19 +0200

> scale routing information.

I didn't want to limit the scope of the discussion to one particular  
type of protocol.

> yes, can a good data structure/encoding help with the *overall*  

I can't answer the first question, because the only BGP we have uses  
binary. But I'm pretty confident that doing the same thing using a  
text based encoding isn't going to do us any favors performance wise.

> form (data type, byte order, number of bits), no decisions need to  
> be made, and you even know the number of data items beforehand, is  
> going to be faster than calling the generic, pretty much neglected,  
> parameterized, tired library routine fscanf that doesn't get much  
> use outside textbooks.

Byte order stuff and such isn't much of an issue compared to the time  
required for memory access. And I guess fscanf could be be a slow  
implementation, but this is just reading a value from a line of text,  
no hunting for tags and such that's required in HTML or XML. Also,  
the performance gap is just so huge, I don't think the details matter  
too much.

> trivial, and, yes, you do want to run measurements, but at the  
> system level and not at the level of "test cases" that have little  
> or no relationship to the performance of the real system.

Sure, but how are you going to do that kind of testing when designing  
a protocol? Creating two implementations just to see which variation  
is faster would be a good idea but I don't really see that happening...

> If you really care about the performance of text-based protocols,  
> you cannot ignore modern tools like Ragel.

Don't know it.

> overhead in your profiling data, I'd like to hear from you.

The problem with text is that you have to walk through memory and  
compare characters. A LOT. This is pretty much the worst thing you  
can do to a modern CPU: you don't use the logical and hardly the  
physical word width, and all those compares are hard to predict so  
you get massive numbers of incorrectly predicted branches.

But I guess this discussion can go on forever...

---

From: Ted Faber <[email-masked]>
Date: Mon, 12 Jun 2006 16:12:29 -0700

On Mon, Jun 12, 2006 at 02:11:19PM +0200, Iljitsch van Beijnum wrote:
> compare characters. A LOT.

That's not where your code spends its time.

Run gprof(1).  The majority of time your code spends is spent doing the
2 integer divides per text to integer conversion and in strtoimax
(called by fscanf). 

Multiplying or dividing is the worst thing you can do on a CPU in
general.  

-- 
Ted Faber
http://www.isi.edu/~faber           PGP: http://www.isi.edu/~faber/pubkeys.asc
Unexpected attachment on this mail? See http://www.isi.edu/~faber/FAQ.html#SIG
_______________________________________________
Ietf mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ietf

---

From: Harald Alvestrand <[email-masked]>
Date: Tue, 13 Jun 2006 09:23:42 +0200

>Multiplying or dividing is the worst thing you can do on a CPU in
Note that CPUs are different; some multiply faster than others, compared 
to the rest of the HW.

And if you really need to, you can optimize... a multiplication by 10, 
for instance, can be done by two left shifts and an addition (a*10 = a 
<<3 + a<<1); I have no idea why strtoimax would do divisions, but I 
haven't written decimal-number parsers for a very long time; I think 
Knuth had 3 different ones in "Seminumerical algorithms", but that was a 
VERY long time ago...

                     Harald

---

From: Masataka Ohta <[email-masked]>
Date: Tue, 13 Jun 2006 17:31:28 +0900

> I didn't want to limit the scope of the discussion to one particular  

Could you stop this abstract nonsense, then?

Many old protocols designed for old, slow computers such as
telnet/ftp/smtp, does use text. Their replies are structured
text mostly with 3 digits. That is, properly designed text
based protocols are fine. Note that all you need is EBNF, not
XML.

						Masataka Ohta

---

From: Ted Faber <[email-masked]>
Date: Tue, 13 Jun 2006 09:13:49 -0700

> Note that CPUs are different; some multiply faster than others, compared 

I am not a CPU designer, but my understanding is that the multiply
instructions are usually the ones that are most complex single
instructions, and in some sense determine the processor speed.  (All you
VAX guys can sit down; I know about your polynomial evaluation
instructions, I'm just speaking generally). 

Trying to extrapolate great truths about data encoding from 10 lines of
C will not be fruitful.

Yeah, this is mostly off topic for networking, but as Joe Touch
demonstrated, sometimes it matters:

http://www.isi.edu/touch/pubs/sigcomm95.html

---

From: Joe Touch <[email-masked]>
Date: Wed, 14 Jun 2006 17:17:11 -0700

Harald Alvestrand wrote:
> <<3 + a<<1);

You might not end up with the same set of condition codes at the end,
though...

Joe