Communications

YouTube video flow control actually causes packet loss (and retransmission)

There's an interesting article in the April 2011 issue of ACM SIGCOM Computer Communications Review. The study by Shane Alcock and Richard Nelson (also accessible here) looks at the way application level algorithms on YouTube's video servers interact with TCP and the actual buffers in a retail DSL delivery system.  I found this particularly interesting as I had already looked into the burstiness of other kinds of traffic in a set of posts in late 2009 (this post in particular).

Here's the way YouTube servers deliver data (at least as of January 2010) to high capacity clients:

By high capacity client I mean the client device has enough buffer space to absorb whatever data the video server wants to send and the client's broadband Internet access service has enough capacity to avoid congestion during delivery of these video bursts.  Unfortunately, the delivery rate YouTube was using in January 2010 was enough to overwhelm the data buffers in typical DSL infrastructure as this graph illustrates.

It appears the YouTube servers send data in blocks of 64 KBytes or 128 KBytes (or multiples thereof) and these blocks can exceed the available buffer space in the DSL delivery infrastructure - mostly likely the buffers in Broadband Remote Access Server (BRAS).  At least one BRAS I was familiar with in 2004-2005 had 200 ms of buffering, obviously not enough for one burst per second.

The good news is the net effect was only a 1% increase in the total data (due to retransmission) so this isn't a big problem and the authors discussed the issue with Google where engineers were working on a solution (in 2010).  What's interesting to me is the extent to which the sizing of buffers for IP infrastructure is still a complex issue and the ease with which a simple application level decision can go wrong.

 

Why there is no Internet QoS

In 2006, I wrote a short blog post on why there is no Internet QoS and likely never will be.  That post is a continuing source click throughs and email inquiries so, when Jon Arnold asked me to write a guest article for IP Convergence TV, I thought I'd tackle the definitive story on Internet QoS.

Here is the new article: Why there is no Internet QoS.  It may or may not be definitive, but I have filled in the engineering and economic background, and I investigate where QoS has been deployed in networks in order to identify where there may be QoS related opportunities for ISPs.

My conclusions:

• There is no Internet QoS today, and it’s unlikely any complex QoS scheme will ever be added to the Internet as a whole.
  
• To the extent next generation networks with rich QoS are deployed, this will only happen within walled gardens, not as part of the public Internet.
  
• But there may be opportunities for ISPs to create a simple premium service that could generate incremental revenue.

Woman in High Tech — Is it getting better?

Woman's Radio News has a great interview with Dr. Dawn Nafus about her upcoming appearance at eComm 2008.

Dawn Nafus, Ph.D., an anthropologist at Intel, discusses why a technology company would have an anthropologist on staff, and exactly what she does for them. Dawn will be speaking at the eComm Conference being held March 12 - 14, 2008 at the Computer History Museum in Mountain View, CA. Her topic will be “Context Aware Technologies” and how they can assist different cultures and countries around the world.

About 4:30 minutes into the interview, Pat Lynch asks Dr. Nafus why there are only a few women on the program at eComm and indeed at most high tech conferences.  She doesn't have a simple answer but she does point out it's a myth that women's position in high tech is getting better gradually over time, at least in Silicon Valley.  Silicon Valley is very young in the grand scheme of things, it has little or no history.  And yet, it has reproduced the male dominated culture that was a characteristic of older industries.  Now older industries are improving at a greater rate than high tech.

I just recently read Herman Goldstine's classic history of the early days of computing, The Computer from Pascal to von Neumann.  Interestingly, some women play key roles, not just Ada Byron (Lady Lovelace), but multiple women during and after WWII.  And when I think back to the Association for Computing Machinery (ACM) that I joined as a student in the early 1970s, there were more women involved in programming, and the mathematical side of the computer industry than in traditional industries.  Also my first part time job was with a small company where 25% of the software staff (1 out of 4) were women.  :-)

Recent counts by VC Christine Herron of women at high tech conferences range from 13% to 18%.  Many old line industries have changed.  But not high tech?

I look forward to hearing Dr. Nafus speak on "Context Aware Technologies" at eComm this coming week.  Hopefully I'll also get a chance to talk with her, as she mentioned some references to recent literature on women in high tech.

Tracing Internet connections by inter-packet timing correlation

Susan Crawford's post The Auction, the Cops, and Comcast, highlights a request from the US Department of Justice to the FCC that is likely to result in an FCC Notice of Proposed Rule Making (NPRM).  As I read her post, I recalled an interesting paper on surveillance.  Here's the relevant part of Susan's post (bold italic highlighting is mine):

The NPRM, if it follows the DOJ’s request, will suggest (among other things) that all of these providers should build their routers and network hardware to provide “packet activity reporting” for all packets crossing their networks, and physical location information for all of their customers at all times. It will also suggest that very fine-grained timing information is needed - something that the internet and its applications don’t provide at the moment. “Packet activity reporting” means that the broadband provider will need to know the destination IP address and port number for everything happening on its network.

The idea is that these designs will help law enforcement when they want to carry out a request for call-identifying information.

A few months ago I happen to read a 2002 paper by Xinyuan Wang, Douglas S. Reeves and S. Felix Wu entitled Inter-Packet Delay Based Correlation for Tracing Encrypted Connections Through Stepping Stones.

I should comment that, when I travel in China, I use TOR (The Onion Router)
to bypass the Great China Firewall.  TOR works by passing your traffic through a series of intermediate routers, with intermediate connections encrypted, so a third party observer can't tell whose traffic is going where.  This is mildly useful to me when I'm in China, but it can be life saving for dissident writers living in totalitarian states. 

So it was somewhat distressing when I read the paper by Wang et al.

From their abstract:

... we address the problem of tracing encrypted connections through stepping stones. The incoming and outgoing connections through a stepping stone must be correlated to accomplish this. We propose a novel correlation scheme based on inter-packet timing characteristics of both encrypted and unencrypted connections. We show that (after some filtering) inter-packet delays (IPDs) of both encrypted and unencrypted, interactive connections are preserved across many router hops and stepping stones.

and from their conclusion:

Our correlation metric does not require clock synchronization, and allows correlation of measurements taken at widely scattered points. Our method also requires only small packet sequences (on the order of a few dozen packets) for correlation. We have found that after some filtering, IPDs (Inter-Packet Delay) of both encrypted and unencrypted, interactive connections are largely preserved across many hops stepping-stones. We have demonstrated that both encrypted and unencrypted, interactive connections can be effectively correlated and differentiated based on IPD characteristics.

So it's clear what the Department of Justice has in mind.  Of course, if the Department of Justice gets this through, it will just be an added expense on all ISPs (and thus on their customers, i.e. you and me).  It won't actually work against the bad guys (or the good guys) as it's fairly simple to imagine an outbound packet scheduler that introduces jitter into each flow at each onion router.

Managed Storage Futures

Recently I wrote about differences in the exponential growth rates of computing and networking and promised to say more about how these differences cause substantial shifts in the technology landscape.  Managed storage is one example.  The relevant doubling rates (from that earlier post) are:

Doubling Rates

Technology Measure	Months
Computing performance	18
Storage capacity	12
Networking performance	15
Access connectivity	20-26

The increase in storage capacity per dollar has been phenomenal and is one of the reasons that Google can offer Gbytes of free storage for email and that Amazon can offer their Simple Storage Service (Amazon S3) at extremely low rates.

But it's also caused headaches for IT directors, as installed equipment becomes obsolete long before it's fully depreciated, and employees and department heads grip about inflated internal billing rates for storage.  Pity the IT staffer who sends a broadcast message justifying corporate email storage limits because "it costs the company X cents per megabyte per month."  I've seen such messages, and the employee ridicule they engender.

This sounds like a perfect opportunity for a managed service — provide an interface that looks a storage area network or network attached storage, using multiple (for reliability and arbitrage) Internet-based storage services to provide the actual storage.  But now differential growth rates become a factor.

Storage costs decline a bit more rapidly than the cost of Internet transit.  So, already it's the case that network-based storage is extremely low cost for backup but less affordable for transactions.

But the real problem is the cost of access connectivity.  If you're selling managed services to IT departments, you need to provide services at their premises.  Local connectivity is not fast, cheap or reliable, and the pace at which it improves is glacial in comparison with storage or Internet transit.

Has this prevented the emergence of managed storage solutions?  Of course not.  But most existing solutions focus on remotely managing equipment that's physically on the enterprise premises.

Is there opportunity for network-based managed services.  Also, yes.  But you will need considerable focus on local connectivity, both for the numbers you use in your business plan and for the specifics of how you implement the service.  Some thoughts:  interface your managed service via a remotely managed on-premise box that includes caching?  use a dedicated access link to guarantee QoS?  ???

In any event, three years from now, you can count of disk storage being ~8X more affordable, Internet transit being perhaps 4x more affordable, but local connectivity only 2x or 2.5x.  Don't give up your great  business idea, but plan accordingly.

Google bypasses Sun's Java licensing -- Dalvik VM

Perhaps the most significant feature of Google's Android open source handset software is the way they've finessed the Java problem.  So far, Sun has totally controlled the Java ME code base.  Yes, they've offered Java source code under the GPL, but not the complete source code for Java ME.  Instead they offer PhoneME as an open source subset, ostensibly because Java ME incorporates components which Sun cannot provide under GPL.  Then there's the question of the rate at which the Java Community Process advances...

Google has bypassed all this by releasing the Google-created Dalvik Virtual Machine under the Apache license.  From ONLamp:

The development process is a standard one for Java developers: Java code is compiled into .JAR and .CLASS files. Google built a custom virtual machine to run these programs; it is called DALVIK (after one engineer's favorite location in Iceland.) The DALVIK VM is designed especially for Android to run on embedded systems and work well in low power situations; it's also tuned to the CPU attributes. The DALVIK VM creates a special file format (.DEX) that is created through build time post processing. The DEX files can be downloaded onto the mobile handsets and run.

Talk about energizing the Java community.  This one component may have more impact than anything else in the Android stack.

UPDATE (20 minutes later):  I just found this by Stefano Mazzocchi which describes Dalvik in more detail and, talk about energizing the developer community, just look at his last paragraph!

Making a significant contribution -- Hamming's career advice

While following an entirely different thread, I stumbled on a blog post by Giacomo 'Peldi' Guilizzoni which lead me to the transcript of this really significant talk that Richard Hamming gave in March 1986.  I printed it out a few weeks ago and just read it today. 

Wow!

His title is "You and Your Research" and he discusses what it takes to do really great work and what are the differences, among otherwise smart people, that cause some to do great work and others to be forgotten.  Hamming was a mathematician (familiar to EEs for Hamming codes and to DSP engineers for Hamming windows) and this talk is about what he saw among scientific colleagues at Los Alamos, Bell Labs and the Navel Post Graduate School.  However, what he says is broadly applicable to any field of endeavor.

Read "You and Your Research."

KDKA, not quite the first commercial radio station

Here's another piece of engineering history I stumbled on during my longer than normal return from Europe, i.e., Paris - Dublin - Boston.  A long time ago, I was general manager of the MIT college radio station (now WMBR, then WTBS but that's another story).  The history of broadcast radio as I understood it then (and up until last week) was that Westinghouse started broadcasting in Pittsburgh in 1920 under the call sign KDKA.

But a history article in the June issue of the Proceedings of the IEEE points out that Westinghouse only started after they noticed the success their employee, Frank Conrad, was having broadcasting music using recordings loaned to him by a local merchant on the condition that the store be mentioned during the broadcasts.

So now that I'm back online, I've looked at the history of KDKA and find, not only did Frank Conrad's private efforts predate KDKA, but a Canadian station (initially XWA, then CFCF and CIQC) actually started in 1919 and went to a regular schedule six months before KDKA.  There's a more complete history of Frank Conrad & KDKA on the KDKA site here.  The Canadians are quiet, as their successor station "940 Montreal" doesn't even list their call letters on their website, let alone their history.

In short, as with most human endeavors, there were multiple similar efforts happening, in parallel.

Vladimir Kotelnikov – Father of Sampling Theory

Actually one of several "fathers."  Caution: the following is for the DSP engineers among you.  :-)

When I learned communications theory it was attributed to Claude Shannon (his 1948 paper) and sampling theory to Nyquist.  I do remember my father once telling me that E. T. Whittaker had published the relevant mathematics long before Shannon, but I never looked up the history.  And I never asked my father to elaborate as he was pushing his copy of Whittaker and Watson at the time, together with the idea I should be a mathematician or a physicist – not an engineer!

But on the plane back from Paris I read the June issue of Communications Engineer from The Institution of Engineering and Technology which included an interesting article on V. A. Kotelnikov by Professor Chris Bissell. 

... in the late 1940s <Shannon> wrote that the sampling theorem was “common knowledge in the communication art, but in spite of its evident importance it seems not to have appeared explicitly in the literature of communication theory.”  But Shannon was only partly correct. Ideas about sampling were indeed common knowledge in the late 1940s, and the theorem in various forms had appeared in the mathematical literature. But the theorem had also been published in the ‘literature of communication theory’ as early as 1933. Trouble was, it was published in the proceedings of a conference in Stalinist Russia – and in Russian.

The article goes on to give Kotelnikov credit for putting the problem of sampling a continuous, band-limited signal into an engineering context. Now that I'm back home and on-line again, I've been able to track down more of the story and access an English translation of Kotelnikov's seminal 1933 paper, On the capacity of the 'ether' and cables in electrical communication.  Not surprisingly, Wikipedia has an even more complete historical background on sampling theory in communications.

Suffice it to say, "Whittaker-Kotelnikov-Raabe-Shannon-Someya sampling theorem" would be a better name, as many people reached similar conclusions with varying degrees of parallelism.  Kotelnikov suffered from writing in Russian under Stalin and before the west started tracking Russian science.

Even with the English translation of Kotelnikov now available, Shannon's 1948 paper remains the best and most complete source for me.  I think it's only available in hardcopy forms, but other URLs of possible interest are here.

Performance per watt – Intel talks the talk

One thing that struck me at last week's AdvancedTCA Summit in Paris was Intel's Keate Despain's focus on performance per watt during his keynote address.  What a change from just a few years ago!  And it's not just Keate Despain, or the AdvancedTCA audience.  CPU performance per watt has finally become a significant competitive issue.  A quick Google search on "performance per watt" returns more than 2 million results including two paid ads, one by Intel and one by AMD.

Also at the Euro-ATCA Summit I had lunch with Stefan Ludwig who was promoting P.A. Semi's PWRficient processors, i.e. power optimized processors based on the PowerPC architecture.

I love it.  For years, I've pushed our engineers to focus on performance per watt and to this day I have a running argument with Texas Instruments over their C6x series DSPs (which are optimized for performance rather than performance per watt). 

This has nothing to do with being "green."   Every system and subsystem has to fit within some power budget.  At one time, a plug-in board for an IBM PC was risky if it dissipated more than 15 watts.  Until recently, carrier hotels (for example) had cooling for 50-150 watts per square foot.  3000 watts per rack was a big deal.  Try putting an IBM blade server in that!  You'd be hard pressed to support ten CPUs in an entire rack.  [Interesting discussion here (free but registration required).]

In my experience, if system architects focus on performance per watt, you end up with designs that are also competitive on density and cost, but it seldom works the other way around.

Good Analysis of xG Technology's claims for xMax Modulation

In late 2005, there was a flurry in the technical press about a Florida company, xG Technology, which claimed to have a new wireless technology with performance far surpassing 3G or anyone else’s 4G roadmap.  I happened to run into a friend who actually knew something (unfortunately under NDA) about the subject, so I got interested, scanned several patent applications filed by the founder, Joe Bobier, and wrote a blog post, xG Technology — Physics or Snake Oil?

At the time, I concluded that Joe Bobier might be well intentioned, but had no clue about digital communications theory.  On the other hand, he might have accidently stumbled on a loop hole in FCC regulations that might allow someone to legally transmit a spread spectrum signal that spreads across the entire spectrum below 3 GHz.

A few weeks ago, Phil Karn, commented on my blog post and pointed me at two excellent papers he’s written on the subject.  In xG Technology’s xMax, Phil examines the published information on xG’s November 2005 demonstration, works out the link budget including antenna gains, and taking account of the specified transmitter power and likely receiver performance, concludes:

The xMax demo may impress those who haven’t done the calculations and are unaware of how little power it takes to transmit digital data over a benign line-of-sight path.  But the same demonstrated performance could have been easily achieved with just about any conventional digital modulation scheme…

In his second paper, Bobier’s TriState Integer Cycle Modulation, Phil examines one of xG’s recent patents, US 7,003,047 and concludes it’s just frequency shift keying.  But Phil goes far beyond the cursory glance I did last year and provides a detailed analysis of this specific patent.  Although the title says “Tri-state” what is described is continuous phase, frequency shift keying with biphase coding.  Phil’s conclusion is simple and dead on:

… the techniques described in this patent are not novel, having been around for decades.  They cannot provide the advantages claimed by the inventor.

What’s more, while I haven’t gone back to scan the other Bobier patent filings, this one has zero chance of spreading the spectrum in any useful fashion.  The principal energy is on either side of the chosen carrier frequency — the patent suggests choosing two tones 30 KHz apart — and the resulting spectrum is very, very conventional.  So the one thought I had last year, about something neat they might be doing, doesn’t apply.

Packet-based processing -- DSP vendors still don't get it

I arrived at the Communications Developer Conference this afternoon in time to attend a talk by Dr. Huan-Yu Su of Mindspeed Technologies.  His talk had the curious title of Semiconductor Design Solutions for IMS and indeed it touched on multiple subjects and many layers, from IMS service objectives down to the evolution of semi-conductor processes.  But the interesting stuff was DSP related.  Mindspeed makes DSP chips and DSP software, which today might best be characterized as signal processing systems on silicon (SoC).

But, despite Powerpoint bullets about packet-based systems, when Dr. Su showed a timing diagram of how individual DSP cores were able to process multiple algorithms on many channels, he showed a TDM system.  Each media stream got a time slice in a 20 ms scheduling cycle.  This means each incoming flow has to hit a jitter buffer and be queued up for it's slice of the TDM cycle.  When I questioned this, Dr. Su replied that it was a hard problem and so far they had addressed it by shortening the 20 ms scheduling cycle to 5 ms.

None of this is to discredit Dr. Su who is a smart guy and gave an interesting presentation.  I have seen equivalent approaches from Texas Instruments and Freescale Semiconductor.  All of the DSP vendors are driven by the TDM-to-VoIP gateway application where 8 KHz (and 20 ms) operation is the norm and completely acceptable.  No one has addressed low latency packet processing.

It's not that hard — here is the answer!

Scheduling a DSP to handle packets, whose arrival is statistical in nature, with minimum latency while guaranteeing that all work gets done, is a lot like scheduling packet transmission over a fixed capacity link with QoS guarantees.  There was a ton of academic and practical work done on this subject as part of ATM switch development in the 90s.  Much of it is directly applicable to scheduling DSP processing.

Those who are really interested might read Leap Forward Virtual Clock: A New Fair Queuing Scheme with Guaranteed Delay and Throughput Fairness by Suri, Varghese and Chandranmenon in the proceedings of INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. This is not the only relevant paper but it is one I am familiar with in some detail.  Quoting from the abstract:

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds similar to WFQ, along with throughput fairness. Our scheme can be implemented with a worst-case time O(log log N) per packet (inclusive of sorting costs), which improves upon all previously known schemes that guarantee delay and throughput fairness similar to WFQ.

At light load, packets are scheduled immediately and experience minimum latency.  Under heavy load, packets are queued but get processed in a time that matches their allocated average arrival rate.  So at heavy processor load, individual flows experience some additional delay but they also have their jitter smoothed out (thus minimizing the required depth of the jitter buffer at the ultimate destination).

Power laws - 63 words account for half of everything said on TV

More specifically, an analysis of word frequencies done on 29,213,800 words, taken from TV and Movie scripts and transcripts that were available on the Internet in February 2006, shows that just 63 words account for 50% of the 29,213,800 words collected.

That's amusing.  What's more interesting is my source, the article A practical model for analyzing long tails by Kalevi Kilkki, Principal Scientist, Nokia Siemens Networks, in the May issue of First Monday.

I'm a fan of Chris Anderson, have read his article, skimmed his book and I have commented on the subject before. Kilkki's article is less anecdotal and more mathematical grounded than Chris Anderson (without being inaccessible).

Plus Kalevi Kilkki's got tons of interesting graphs.  :-)

DoCoMo uses MIMO to achieve 50 bps/Hz

That's 50 bits per second per Hertz of radio spectrum.

Under the title NTT DoCoMo Achieves World's First 5Gbps Packet Transmission in 4G Field Experiment DoCoMo announced a new level of modulation efficiency.  Their title is flashy, but they were using 100MHz of spectrum.  To find that much spectrum you have to look to very high frequencies and thus short ranges with poor penetration of buildings (or trees and shrubs). 

The benchmark to follow is modulation efficiency — how many bps can you cram through a limited amount of spectrum.  Today commercially deployed systems tend to achieve less than 10 bps.  Here's an excerpt from a picture of their setup.

The full image with explanation is in this pdf file.

In some sense, this is a brute force expansion of earlier work with an increased number of antennas at slightly different positions being used to send different information on the same frequency simultaneously and multiple receiving antennas used to resolve the individual transmitted signals, i.e. multiple inputs and multiple outputs (MIMO).  It also builds on the most current modulation scheme which is orthogonal frequency division multiplexing (OFDM), the modulation used in WiMAX.  None-the-less, it's an impressive achievement.  Thank you DoCoMo.

Everyone has heard of Moore's law describing the decades-long continuous exponential increase in performance of integrated circuit technology.  Fewer people comment on the continuous exponential increase in radio spectrum utilization that's been in progress for more than 100 years, i.e. since Marconi patented "resonant tuning" in 1900, showing how he could send multiple signals over the air at the same time (versus a single transmission in his initial system of 1896).

Great Engineers - Brunel

More specifically, Isambard Kingdom Brunel.  I've been holed up in meetings which finally ended an hour ago.  So, since we're at the Paddington Hilton in London, I went to pay respects.

Tunnels, bridges, railroads, ships, and the Paddington Station — he did it all, and in a relatively short life.

Being here is very timely as, for Christmas, I got a copy of Brunel: The Man Who Built the World by Steven Brindle and Dan Cruickshank.  It's an easy and enjoyable read.