Computications (Installment 1 of a series)

We have been hearing a lot recently about Network Functions Virtualization (NFV), Software Defined Networking (SDN), and how communications could learn a lot from computer science. This is the first blog entry of a series in which I will attempt to impose some structure on these ideas by exploring five distinguishable trends, which I shall dub, respectively :

1. Computications (on the relationship between communications and computation)
2. Physics (a propos the spectrum of implementation options between hardware and software, and the trends called SDR and NFV)
3. Philosophy (concerned with touchless, configurable, and fully programmable devices, and the trend known as SDN)
4. Geography (about where a particular functionality is located, e.g., locally or remotely)
5. Politics (regarding distributed control planes and centralized management planes).

It was once simple and straightforward to distinguish between communications and computation, in fact the overlap was almost nonexistent. A telephone, a radio, and even a modem were solely for communications, while a slide-rule, a calculator, a mainframe and a minicomputer were for computation. And since most people don’t need to perform complex calculations in their everyday life, even the computer visionaries of the time believed computers to be hopelessly alien to the populace:

"I think there is a world market for maybe five computers."  - Thomas Watson, chairman of IBM (1943)

"There is no reason anyone would want a computer in their home."  - Ken Olson, president, chairman and founder of Digital Equipment Corp. (1977)

This has radically changed, mostly because the vast majority of computers are not used for computation at all. Most home computers are actually entertainment and communications devices, while those in professional environments are used almost exclusively for composing and reading documents. Of course the rendering of graphics and the decompression of videos and songs requires substantial computational power, but the average user has no idea that this computation is taking place.

In addition, telephones have been imbued with vastly more computational power than computers had ten years ago. A host of new devices such as ebook readers and tablets further blur the lines between computation, communications, and everyday life.

"Computing is not about computers any more. It is about living." - Nicholas Negroponte, founder of MIT’s Media Lab and One Laptop Per Child Association (1995)

I personally first appreciated this overlap of communications and computation when working on DSP for facsimile in the 1980s. A fax call starts with a set of tones to establish that both sides are fax machines, a handshake in which one side sends its capabilities and the other side sends its decisions as to which modes to use. This initial exchange is so similar to a human conversation that with a little experience anyone can follow it (and indeed many faxes let you hear the initial stages to diagnose problems). This exchange is a rather typical protocol (documented in ITU-T Recommendation T.30), and while both sides require software with a tremendously complex state machine, there isn’t really any computation in the usual sense of the term. However, the tone generators/detectors and modulator/demodulators do implement numerous numerical signal processing algorithms (sinusoid generation, spectral analysis, digital filtering, timing recovery, phased-lock loops, equalization, geometric slicing), and once the handshake is over the image is compressed and decompressed and error correction/detection is performed (as documented in ITU-T Recommendation T.4). So implementing the communications protocol requires implementing computation on both sides, and ITU documents may define algorithms in addition to protocols. All of this led me to wonder where to draw the dividing line between the protocol and the algorithms. My revelation was:

"Protocols are to communications as algorithms are to computation." - Y(J)S (circa 1985)

By that I meant that although both algorithms and protocols are step by step recipes for accomplishing a desired task, algorithms are logically carried out by a single actor (even when run on parallel computation devices), while protocols are used simultaneously by at least two distinct remotely situated actors. Of course, protocols require algorithms on each actor, but while non-communications algorithms interact with their environment solely via inputs and outputs, algorithms that support communications also interact with another instantiation of the same algorithm (or possibly an instantiation of a complementary algorithm) via the protocol.

Many years later, after I had delved more deeply into the fundamentals of telecommunications, I was confronted with an even more fundamental point of contact – the bit. In computation we use what I call the Tukey bit in contradistinction to the Shannon bit used in communications. The Tukey bit is simply a digit used to represent a number in binary representation. It is a contraction of “binary digit” and was coined by John Tukey, the Princeton statistics professor better known for having co-invented the FFT algorithm. Interestingly, Tukey also coined the word software.

The Shannon bit is the basic unit for quantifying information of any sort. Before Shannon’s work in information theory, it was not clear that any two bodies of information could be compared in the same way as the weights or lengths of physical bodies are compared. Shannon taught us that the information content of a song, a movie, a poem, and a thought can be quantified, and that the natural unit was the bit. The number of bits of information is the smallest number of yes/no answers one needs to provide to uniquely describe the information.

To understand why Tukey’s bit is a special case of Shannon’s bit, consider the special case in which I wish to communicate the value of a variable that can be from zero to fifteen, for instance 10. In Tukey terms such number can be described by 4 Tukey bits - 1010. In Shannon terms the minimum number of questions that I need to answer is four :

1. Is the number over 7 ? Answer YES encoded as 1 (the number is 8, 9, 10, 11, 12, 13, 14, or 15).
2. Is the number over 12? Answer NO encoded 0 (the number is 8, 9, 10, or 11).
3. Is the number over 9? Answer YES encoded 1 (the number is 10 or 11).
4. Is the number over 10? Answer NO encoded 0 (the number is 10).

The four answers are thus 1010, which indeed agrees with the Tukey representation.

However, the Shannon bit is still meaningful for arbitrary non-numerical information (think of game called “20 questions”) for which the Tukey bit is undefined. So information, the basic quantity transported by communications, generalizes the idea of number, the basic tenet of numerical computation.

However, there are certainly additional, possibly less subtle but more visible, connections between communications and computation. For example, dedicated communications hardware may be replaced by pure processing power, a trend embodied in Software Defined Radio (SDR) and Network Function Virtualization (NFV). Control and management plane protocols that discover and negotiate communications functionalities may be replaced by software running on servers, a trend called Software Defined Networking. We will visit these trends in the upcoming installments of this blog.

Y(J)S

Deployment, R&D, and protocols

In my last entry I discussed why the last mile is a bandwidth bottleneck while the backhaul network is a utilization bottleneck. Since I was discussing the access network I did not delve into the core, but it is clear that the core is where the rates are highest, and where the traffic is the most diverse in nature.

Based on these facts, we can enumerate the critical issues for deployment and R&D investment in each of these segments. For the last mile the most important deployment issue is maximizing the data-rate over existing infrastructures, and the area for technology improvement is data-rate enhancement for these infrastructures.

For the backhaul network the deployment imperative is congestion control, while development focuses on OAM and control plane protocols to minimize congestion and manage performance and faults.

For the core network the most costly deployment issue is large-capacity, fast and redundant network forwarding elements, along with rich connectivity. Future developments involve a huge range of topics, from optimized packet formats (MPLS) through routing protocols, to management plane functionality.

A further consequence of these different critical issues is the preference of protocols used in each of these segments. In the last mile efficiency is critical, but there no little need for complex connectivity. So physical-layer framing protocols rule. As there may be the need for multiplexing or inverse multiplexing, one sometimes sees non-trivial use of higher-layer protocols. However, these are usually avoided. For example, Ethernet has long had an inefficient inverse multiplexing mechanism (LAG), but this is being replaced with the more efficient sub-Ethernet PAF (EFM bonding) alongside physical layer (m-pair) bonding for DSL links.

In the backhaul network carrier-grade Ethernet has replaced ATM as the dominant protocol, although MPLS-TP advocates are proposing it for this segment. Carrier-grade Ethernet acquired all the required fault and performance mechanisms with the adoption of Y.1731, while the MEF has worked hard in developing the needed shaping, policing, and scheduling mechanisms.

In the core the IP suite is sovereign. MPLS was originally developed to accelerate IP forwarding, but advances in algorithms and hardware have made IPv4 forwarding remarkably fast. IP caters to a diverse set of traffic types, and the large number of RFCs attests to the richness of available functionality.

Of course it is sometimes useful to use different protocols. A service provider that requires out-of-footprint connectivity might prefer IP backhaul to Ethernet. An operator with regulatory constraints might prefer a pure Ethernet (PBBN) core to an IP one. Yet, understanding the nature and constraints of each of the segments helps us weigh the possibilities.

Y(J)S