Geography (Installment 4 of a series)

In the previous two installments of this series on SDN and NFV I discussed the virtualization and configuration of communications functionalities; this installment will deal with their placement. I call this aspect geography, and this time use the term in its most literal sense – where geographically a given function should be physically located.

Note that this aspect of a network function is independent of the previous ones. Even a nonvirtualized function implemented entirely in dedicated hardware can still be placed in various places along the communications path. Of course, most functions do have traditional locations - e.g., a firewall is generally placed at the customer network's ingress point, and a pseudowire interworking function is placed at the Provider Edge (PE). But, there is some flexibility in these placements. When the service provider provides the firewall function, it does so by moving this function from the customer premises to the service provider's. If the customer maintains the pseudowire the IWF is placed at the customer premises rather than at the PE.

SDN and NFV herald yet more flexibility. Virtualization of networking functionalities may expose many placement options by offering numerous locations with the resources required to run the Virtual Network Function (VNF). And SDN enables dissociating protocols from their conventional locations; e.g., routing protocols can be removed from routers and run on servers in remote datacenters instead.  CPRI goes even further by moving all eNodeB processing (except the antenna, mixer, and A/D) to dedicated hardware at a remote location.

In principle, all network functions can be virtualized. This statement derives from the computational universality (technically the Turing completeness) of CPUs. In practice, however, virtualization of certain functions is not practical (at least not at reasonably high data-rates). For example, while it is straightforward to perform L2 or L3 forwarding at Gigabit speeds on a CPU, at 10G rates utilizing dedicated hardware is more cost effective, and at 100G there is presently no option for virtualization. Similarly, certain intensive operations are more effectively left in dedicated hardware, for example bandwidth shaping, high-rate CCs for protection switching, and encryption. What about the geographic positioning of network functions? Can all network functions be, in principle, arbitrarily positioned? Should they be ?

The three most important factors in determining the desirability of a property are location, location, location.
-          incorrectly attributed to Harold Samuel, UK realtor

A residence that perfectly suits your needs can’t usually be moved it to the desired location. The same is true for certain networking functionalities. Not every function can be placed anywhere there are available resources. And even for those that can be placed anywhere, there are many reasons to select specific locations.

As an obvious example consider loopback functionality. Loopback diagnostic testing enables a remote administrator to verify connectivity to and from a remote site. Moving this function to a remote datacenter makes no sense at all! The same can be said for many security functionalities, such as encryption and Denial of Service (DoS) attack blocking. Moving encryption to the other side of an access network leaves unencrypted traffic exposed to all with access to that network, and conversely, blocking malicious traffic at the other side leaves the door open to attackers with access to the network.

Deep Packet Inspection (DPI) provides a slightly less obvious example. Moving a DPI function from the place where it is needed necessitates sending the packets to be inspected to a remote DPI engine, resulting in additional bandwidth consumption and increased processing delay. If the bandwidth is unavailable or too expensive, or if the added delay exceeds the budget for the applications involved, then DPI needs to remain in situ even if computational resources are less expensive elsewhere.  

Another placement constraint arises from regulatory issues. For example, certain databases must not be moved across commercial or jurisdictional boundaries. Traffic crossing certain borders may subject parties to taxation. Certain on-line activities may be legal in some jurisdictions but not in others. Requirements for lawful interception may also influence placement decisions.

On the other hand many functions can be placed in many different locations. The most credible cases are routing and path computation, as well as billing/charging. Other innovative placements are being extolled in the press and heatedly discussed in the forums. The security and privacy implications of such placements are only recently receiving attention.

When functions can be placed in many geographical locations, the final placement decision is usually based on economics. Service provider Points of Presence (POPs) and datacenters may be attractive due to the ability to exploit economies of scale. Real estate expenditures are minimized by colocating as many functions aspossible. Cooling costs may be minimized by running functions in riverside datacenters with water cooling. Placing multiple instances of a function in the same datacenter can hugely simplify management and maintenance.

In fact, many people equate NFV with moving all nontrivial control functionality to datacenters leaving no intelligence in the network. The CloudNFV initiative is based on the tenet that it is most efficient to run VNFs as SaaS. On the other hand RAD believes in Distributed NFV (D-NFV) wherein each function is placed at the position in the network where it can best fulfill its function. That position may be at a CPE, or an aggregation point, or in the network core, or in a data-center.

Another issue complicating placement decisions is function chaining. In many cases there are multiple functions that need to be performed on packets somewhere along the end-to-end path, with restrictions on the order in which these functions need to be performed. These functions may include packet shaping, packet remarking, NAT, intrusion detection, and tunnel encapsulation. We certainly wouldn't want to send a packet to a remote datacenter for intrusion detection, return it for shaping, and then send it back to the datacenter for NAT.

Optimization of function chaining turns out to be more complex than that carried out by a Path Computation Element (PCE). The latter need only find acceptable paths through equivalent routers, while the former needs to handle much more complex paths and constraints. 

As an abstract example, imagine that functions A, B, C, D, and E all need to be performed on every packet belonging to a service before final delivery. Function A must be performed before either B or C; B and C can be performed in either order but must be performed before C or D; and E must be the last function performed before delivery. Imagine further that in the network there are numerous devices that are able to perform these functions, but not all devices can perform all functions. Furthermore, the services have delay cutoffs, bandwidth should not be needlessly wasted, and resource loading should be equalized in order to avoid bottlenecks and potential points of failure. Finally, the computation of the chaining order needs to be performed upon intializing a new service, and while changing the service chaining configuration of an existing service is possible, it should be avoided due to the negative impact on service quality.

How does the function chain orchestrator determine the optimal placement of each VNF? I'll discuss that in the next installment.

Y(J)S

Philosophy (Installment 3 of a series)

In the previous installments I discussed the assimilation of communications and computation, the spectrum linking hardware and software, and how to virtualize communications functionalities. This installment is all about configurability and programmability.

I entitled this blog entry philosophy, since philosophy is literally the "love of knowledge", and generally deals with what we can learn about the world about us and how best to function in this world. Indeed epistemology is concerned with the nature of knowledge and ontology deals with the nature of existence itself.

Knowledge concerning the surrounding world is often indispensable for the proper functioning of communications devices. For example, a transmitter must know the frequency on which to transmit and the modulation scheme to use. An IP host needs to know the destination address to which to send packets, and the protocol to use. But how do communications devices acquire this knowledge?

Let’s start by envisioning a network element that functions out-of-the-box without any configuration options. We can say that such a network element is “zero-touch”. For example, fiber converters, hubs and repeaters, and even simple learning bridges are essentially zero-touch. Devices can be zero-touch simply because they are very limited in functionality. Or they can be flexible and sophisticated but still zero-touch because they are capable of learning all they need to know from their environment. Paradoxically zero-touch devices are either exceedingly dumb or exceedingly intelligent.

Many devices designed to be used by unsophisticated end-users, such as televisions and cellphones, hypothetically function without being set up. But this is obviously an over-simplification of the true situation. Modern televisions have remote controls that only the tech-savvy can handle (Is the set-top box connected to HDMI-1 or 2?  Which of the five supported aspect ratio options is best for HD?). Cellphone users are often stymied when they need to change time-zone or select a network. Configuring home WiFi routers is a task well beyond the capabilities of most mortals (Does my ISP use EoPPP, or L2TP or PPTP? Should my WiFi security be based on WPA or WPA2 with LEAP or PEAP? How does one set up port blocking? What exactly is an 802.11 beacon anyway?)

Early Ethernet switches were essentially zero-touch; they learned everything they needed to know by conversing with each other; when they didn’t know how to handle a frame they simply flooded it and observed the consequences. But then along came VLANs and one needed to configure which VIDs were to be admitted/emitted for each port (or to dictate “admit all”) as well as the default VLAN identifier for untagged frames. And the situation has gotten a lot worse since then. Ethernet OAM requires defining and configuring MEPs and MIPs, MEF services bring with them a complex set of bundling and bandwidth profile parameters, configuring 1X authentication can be a nightmare even for experts, and a PhD may be insufficient qualifications to correctly set up multicast. And this is before MEF’s new bandwidth sharing feature!

Routers rely on a strong standardized control plane, and should thus be much simpler to set up, right ?  Ever heard of Cisco CareerCertifications? There are five levels of certification (Entry, Associate, Professional, Expert, and Architect) along with targeted certifications for in seven different subject areas (Routing and Switching, Design, Network Security, Service Provider, Storage Networking, Voice, and Wireless). All that just to configure a router…

So we have communications devices that should be zero-touch, but in practice may require extensive configuration. This configuration may be manual and local (historically via a textual “CLI” interface but more recently via a GUI), or may be network-wide via a sophisticated network management system (NMS).

Of course, if configuration is so complex, you may be wondering why manufacturers can’t simply pre-configure their network elements so that the user can just turn them on and use them. Unfortunately, this is rarely, if ever, possible, due to the dynamic environments in which network elements are required to function.

If we want things to stay as they are, things will have to change.
 - Giuseppe Tomasi di Lampedusa (in The Leopard)

So we have seen zero-touch devices, and those that require basic configuration. The second step on the road towards full programmability is to enable a single device to combine the capabilities of multiple conventional devices, and then to configure it to function as any or all of these devices. For example, we could embed the functionalities of a L2 switch, a L3 router, and a L4 NAT in a single box, and then select whichever functionality needed in a particular instance. We could even opt to simultaneously activate many functionalities, provided that they are performed in the appropriate order.

This second step is precisely what an OpenFlow switch offers. A single device can match L2 header fields (SA, DA, EtherType, VLAN ID, VLAN priority), or L3 header fields (SA, DA, protocol number, DSCP, ECN), or L4 header fields (source and destination ports) and perhaps MPLS header fields (label, S-bit), and any combination thereof. However, in reality OpenFlow is more limited than just implied, in that the matching criterion is constrained to be exact match with bitmasks. A true combined L2-L4 device would be able to perform longest prefix match and port range match; but these limitations can be overcome at the expense of replicating flows.

A short digression (well, rant) is now in order. While such a combined device is advantageous in that it saves shelf space, power, and inventory carrying costs, it suffers from a major drawback. In today’s world of distinct devices, each device processes only that part of the packet for which it is intended, with the hardware limitation imposing opaqueness to the rest of the packet. Thus layering enforces intrinsic scoping which not only indicates clean design (similar to data abstraction in software) but also secures business interests. Once a single device can observe, act upon, and modify arbitrary fields, the ensuing layer violations can wreak havoc with service provision. Client layers could compel server layers to incorrectly forward packets or could hide traffic from billing systems. Lower layers could divert traffic to hostile destinations, or modify messages in transit. And such mayhem is not necessarily due to deliberate hacking, it will necessarily arise from simple errors in configuration. It is somewhat surprising that such flaunting of clean layering is proposed by academics in the name of data abstraction. Rant over.

The third step on the road to full programmability is a device consisting of lego blocks of useful functionalities. One could imagine a farm of general matchers (exact match, range match, regular expression match), a collection of rewrite modules, and a set of forwarding engines, all of which could be flexibly interconnected. Such a device can provide true DPI, as compared to the relatively shallow packet inspection of the previous step. Many network processors and some IDS systems are designed according to this philosophy.

At the far end of the spectrum sits the general purpose computer. Reminiscent of the zero-touch communications device with which we started, it too is supposed to function out-of-the-box. However, this functioning is limited (e.g., displaying a desktop). We purchase a computer entirely due to our expectation that it to be completely reprogrammed to perform any task, (well, at last if it has the required interfaces to the outside world – it can’t make coffee if it doesn’t have access to water and coffee grinds). In fact, once purchased we tend to forget about the computer (or smartphone) altogether. It becomes merely a platform for hosting applications, which are the products in which we are really interested.

The general purpose CPU is truly stronger than even the lego block model in that it can perform arbitrary calculations on arbitrary fields and make arbitrary forwarding decisions. For example, we could program a CPU to multiply the MAC source address by the IP destination address, xor the result with the last 10 bytes in the packet, take the hyperbolic sine of this, quantize to two bits, and use this result to forward to one of four output ports. Presumably this generality could also be used for something even more useful.

In the Apology, Plato tells how the Delphic Oracle declares that no-one is wiser than Socrates. Socrates, believing the oracle but knowing that he was ignorant of knowledge, goes out to discover what the oracle meant. He visits people he initially believes to possess wisdom - politicians, poets, and craftsman. After failing to uncover true wisdom in any of these, he comes to the conclusion that whatever wisdom he has derives from his knowledge that he knows nothing.

Truly a zero-touch philosophy!

Y(J)S

 

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.

Y(J)S

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

CAPping routed and SDN networks

In my last blog entry I discussed two differences between SDN and conventional networking. The second was that SDN returns to centralized control as compared to a distributed control plane (I’ll return to the first difference in just a moment). And this means that there is a single point of failure, even if the controller itself has built-in redundancy.

There has been discussion in the OpenFlow community about failover (and even load balancing) between multiple controllers. The OF reference implementation includes a simple mechanism wherein an OF switch can be configured with a list of controllers, and if the master controller fails the OF switch selects the next on the list. Open vSwitch allows sending messages from OF switches to multiple controllers, and enables these controllers to elect a master.

What I want to elucidate here is why such solutions can never provide a complete resolution to the problem. My explanation is based on the CAP theorem for distributed computing systems.

A distributed computing system is composed of multiple computational resources (CPU, memory, storage) that are connected via a communications network and together perform a task. To make things more concrete consider a database, which can queried and into which new data can be entered, via a large number of servers around the world, connected over the public Internet.

There are three characteristics of distributed systems that are universally desirable:
• Consistency, meaning that the system responds identically to a query no matter which node receives the request (or does not respond at all);
• Availability, i.e., that the system always responds to a request (although the response may not be consistent or correct); and
• Partition tolerance, namely that the system continues to function even when nodes or the communications network fail.

In 2000 Eric Brewer conjectured that a distributed system can satisfy any two of these guarantees at the same time, but not all three. This conjecture was later proven by Gilbert and Lynch and is now called Brewer’s theorem, or the CAP theorem.

Without going into a formal proof, you can readily convince yourself of the correctness of the CAP theorem by requiring one of the characteristics and then proving that the other two can’t co-exist. For example, let's require consistency. There are basically two ways to handle data; we can have a single database that all nodes need to update and retrieve from, or maintain a local copies of the database at each node. If there is a single database, then consistency demands that once any node starts updating the database, all the other nodes must wait until the update is complete. If there are multiple copies, then each time one node updates its local copy, consistency demands it to send messages to all the others instructing them to update their copies, and to wait for acknowledgements from all the others. In the first case, a communications network failure that separates the node in question from the database immediately leads to lack of availability. In the second case a network failure that causes even a single node’s acknowledgement not to arrive also causes lack of availability. So availability and partition tolerance can’t be simultaneously achieved.

Now what does this have to do with networking? Well, SDN teaches us that packet forwarding is simply a computational problem. That was the first difference between SDN and conventional networks that I discussed in my last blog entry. And since the task of forwarding a packet from network ingress to network egress is obviously carried out by a large number of forwarding elements, the network of packet forwarding devices is a distributed computational system. And ergo the CAP theorem applies.

So which two of the three desirable characteristics of distributed systems do we want to achieve, and more importantly, which one are we willing to forego?

In conventional routed networks we forego consistency. Each router has its own local Forwarding Information Base (FIB), which is locally created and only weakly tied to the FIBs of the others. Lack of forwarding consistency means that packets can sometimes become misrouted or “black-holed” (go around in circles until they are dropped). That is the reason the IP packet header has a TTL field, and the reason TCP is layered over IP to retransmit lost packets. On the other hand, IP service unavailability is almost always due to a local break that physically disconnects the host from the IP network, and, as previously discussed, IP networks are extremely tolerant to partition failures.

At the other extreme is OpenFlow, which stresses consistency. The controller acts as a global database, and specific OF mechanisms ensure that a packet entering the network is handled consistently by all switches. OpenFlow also attempts to provide high availability, with mechanisms for handling the first packet of a new flow, and popular test suites examining scalability and availability. So, what must be sacrificed? The only remaining characteristic is partition tolerance.

So what is wrong with using multiple OF controllers? If you have read everything up to now you should understand that these controllers can’t be kept consistent even when the network connecting them fails without having them hang indefinitely.

Since you can't have your CAP and eat it too, every network architecture must decide which of consistency, availability, and partition tolerance it is willing to do without. On this issue conventional IP networks and SDN have taken different routes.

Y(J)S