Monday, April 29, 2013

Physics (Installment 2 of a series)

In the previous installment of this series on NFV, SDN and related issues, I talked about the relationship between communications and computation (the merging of which I dubbed computications); now we are ready to take these ideas one step further.

A computational resource (such as a server or a laptop computer), as well as a communications resource (such as a router or a switch), may be a genuine physical entity. You can touch such resources with your hand; and thus we call such instantiations – hardware. On the other hand an algorithm or a protocol, as well as data input, output or transferred, can’t be held in your hand or seen with your eyes. So we fancifully call them (after Tukey) software. Software is more logic or mathematics (i.e., pure thought) than physics.

Hardware – the part of a malfunctioning computing system that you can kick.
Software - the part of a malfunctioning computing system that you can merely curse.
- Anonymous sage

However, it is commonplace to recognize that there is a spectrum between these two extremes. Closer to the software is the so-called firmware, which is software that is not frequently reprogrammed and lives in persistent memory.  Closer to the hardware is an FPGA which can be held in your hand, but whose true significance lies in its HDL programming. In between we can have a processor core in an FGPA, network and DSP processors that are programmed but can’t be efficiently replaced with software on a general purpose CPU, driver software, and so on.


Every time we plan implementation of a task, we need to consider where to instantiate it on this spectrum. Usually it is optimal to situate simple logic that needs to run at high speeds as close to the hardware as possible; while complex logic that needs to run at low speeds is best located close to the software end of the spectrum. However, in many cases multiple factors need to be considered before making a final placement decision.

Concretization (well, maybe the word is not often used in this way) is the act of moving a task usually implemented closer to the software end of the spectrum towards the hardware end (from right to left in the above figure). Thus when an algorithm originally coded in a general purpose programming language in order to run on a CPU is rewritten in assembler to run on a DSP, or when a task in DSP code is re-implemented in FPGA gates, or when an FPGA design is cast into discrete unprogrammable hardware, we have performed concretization of the task.

Virtualization is the opposite procedure, i.e., moving a task usually implemented closer to the hardware end of the spectrum towards the software end (from left to right in the aforementioned figure). Thus when a task originally carried out by analog circuitry is converted to a DSP-specific algorithm, or a task running on a DSP is transferred to a code running on a general purpose processor, we have virtualized the task. The term virtualization is frequently reserved for the extreme leap of taking hardware functionality directly to software.

The reasons for performing concretization are many, and mostly fairly obvious. When mass-produced, application specific hardware is less expensive than general purpose processing power; making the initial development investment worthwhile for functionality that is widely deployed. Special purpose hardware may be miniaturized and packaged in ways enabling or facilitating desired applications. Dedicated hardware may attain higher communications data-rates than its software emulation. Constrained designs may achieve higher energy efficiency and lower heat dissipation than more flexible instantiations of the same functionality.

The reasoning behind virtualization is initially harder to grasp. For functionality of limited scope it may not be economically worthwhile to expend the development efforts necessary to implement close to hardware. Flexibility is certainly another desirable attribute to be gained by implementing communications functionality in software; virtualization facilitates upgrading a communications device’s functionality, or even adding totally new functionality (due to new operational needs or new protocol developments).

Software Defined Radio (SDR) is a highly developed example of virtualization of physical layer processing. Transmitters and receivers were once exclusively implemented by analog circuitry, which was subsequently replaced by DSP code both for higher accuracy (i.e., lower noise) and to enable more sophisticated processing. For example, the primitive AM envelope detector and FM ring demodulator are today be replaced by digitally calculated Hilbert transforms followed extraction of instantaneous amplitude and frequency. This leads to consequent noise reduction and facilitation of advanced features such as tracking frequency drift and notching out interfering signals. The SDR approach leveraged this development and further allowed downloading of DSP code for the transmitter and/or receiver of interest. Thus a single platform could be an LF AM receiver, or an HF SSB receiver, or a VHF FM receiver, depending on the downloaded executable software. A follow-on development was cognitive radio, where the SDR transceiver can dynamically select the best communications channel available (based on regulatory constraints, spectrum allocation, noise present at particular frequencies, measured performance, etc.) and set its transmission and reception parameters accordingly.

A more recent example of virtualization is Network Functions Virtualization (NFV). Here the communications functionalities being virtualized are higher up the stack at the networking layer. This concept is being evangelized by the ETSI Industry Specification Group on NFV, based on service provider requirements. The specific pain being addressed is that each new service offered requires deploying one or more new hardware appliances throughout the service provider's network. This then engenders not only the capital expense of acquiring these new devices, but allocation of shelf space and power to accommodate them, and training staff to configure and maintain them. As the number of new services accelerates while their lifecycles shorten, acute pressure is placed on the service provider's bottom line. NFV proposes implementing new functionalities in industry standard servers (located in datacenters, POPs, or customer premises), thus reducing CAPEX, consolidating multiple equipment types, reducing time-to-market, and simplifying both initial deployment and maintenance. The network functions that may be virtualized may include packet forwarding devices such as switches and routers; security appliances such as firewalls, virus scanners, IDS, and IPsec gateways; network optimization functions such as NATs, CDNs, load balancers and application accelerators; cellular network nodes such as HLR, MME, and SGSN; etc. NFV proponents believe that it is the only way to keep up with explosion in nework traffic volumes and service types while restraining CAPEX.

Virtualization as we have just defined deals with the instantiation of the communications functionality itself; leaving open the issues of mechanisms used to configure and maintain devices implementing these functionalities. That topic will be the subject of the next installment.


Thursday, April 25, 2013

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.