View source for Internet Scale Overlay Hosting

Network overlays have become a popular tool for implementing Internet applications. 
While content-delivery networks provide the most prominent example of the commercial application 
of overlays, systems researchers have developed a variety of experimental 
overlay applications, demonstrating that the overlay approach can be an effective method 
for deploying a broad range of innovative systems.
Rising traffic volumes in overlay networks make the performance of overlay 
platforms an issue of growing importance.
Currently, overlay platforms are constructed using general purpose servers, 
often organized into a cluster with a load-balancing switch acting as a 
front end. 
This project explores more integrated and scalable architectures suitable
for supporting large-scale applications with thousands to many millions of
end users.
In addition, we are studying various network level issues relating to the
control and management of large-scale overlay hosting services.

== Overvew ==

An ''Overlay Hosting Service'' (OHS) is a shared infrastructure that supports
multiple overlay networks. There are two major physical components to an OHS,
the ''Overlay Hosting Platforms'' (OHP) and the links joining OHPs to one another.
These links are expected to have provisioned bandwidth, allowing the OHS to
deliver provisioned capacity to the overlay networks that operate within it.
Access to the OHS infrastructure uses the Internet for the final hop.
This traffic can be carried over UDP tunnels, or virtual links,
depending on the deployment context (e.g. MPLS or VLAN).

[[Image:ohs.gif|frame|right|Overlay Hosting Service]]

The OHPs contain flexible processing resources that can be allocated to
different overlays. The resources allocated to an overlay node can range from
a small fraction of a general-purpose server, up to hundreds
of high performance multi-core processor subsystems.
To enable a wide range of overlay network architectures and service models,
it's important for OHSs to be as flexible as possible.
Overlay network providers should be free to define their own
protocols, packet formats and service models, within the framework provided by the OHS.

The use of provisioned links between OHPs allows OHS providers to deliver provisioned
overlay links to the overlay providers, making it possible for overlay networks
to provide consistent performance to their users. For access over UDP tunnels,
true QoS may be difficult to achieve, but even here there is the potential for 
significantly better performance than can be achieved over end-to-end connections
in the public Internet.

To clarify the role of various elements of an OHS, it's helpful to introduce some terminology.
The infrastructure and core services provided by the OHS are referred to as the
''substrate''. We also use substrate to refer to the core services provided by
the OHPs. We use ''overlay'' to refer to each overlay network hosted by an OHS,
and we use the term ''overlay node'' to refer to the individual nodes within the
overlay network. For brevity, we sometimes use ''platform'' in place of overlay
hosting platform, and ''node'' in place of overlay node.

== Design Principles ==

We start by articulating some core design principles to provide a framework
in which to consider more detailed design issues.

=== Architectural Neutrality ===

The architectural neutrality principle states that the OHS should be neutral
with respect to the architectures and service models implemented by the overlays.
The motivation behind this is that we want to support the widest possible range
of overlay services, and to encourage innovation and creativity in the design
of new overlays. A successful OHS may operate for a period of many years,
making it likely that future overlays will have requirements that are very
different from those of current overlays.

One important consequence of the architectural neutrality principle is that
the substrate should provide only the most essential services.
Because the substrate provides common elements used by all overlays,
any capability provided by the substrate is likely to become difficult
to change in the future. Consequently, any capability that we are likely to
want to change in the future, is best implemented in overlays rather than
in the substrate.

=== Resource Provisioning Model ===

There are two very different approaches that one can take to providing a
flexible overlay hosting capability. The ''resource provisioning'' approach seeks
to make resources available, without imposing any specific usage model on
those resources. In this approach, there may be a variety of different resources
provided for use by overlays, and the specific kinds of resources can change over time.

The alternative ''abstract programming interface'' approach attempts to shield overlay
overlay developers from the characteristics of the underlying hardware
components, by providing a system level abstraction through which users
can implement new functionality. This has some obvious appeal, since it can
allow developers to work at a higher level of abstraction, and to readily port their overlay
network functionality to take advantage of new hardware subsystems, without
a major new development effort.

In deference to the architectural neutrality principle, we favor the resource
provisioning approach. However, it is important to recognize that this does
not rule out higher level development processes for overlays. It just separates
the provision of higher level APIs from the OHS substrate. One can certainly
envision higher level programming environments that target specific resources
that may be available within an OHS. While the introduction of new hardware
resources may require the development of new code generators for compilers,
and/or runtime environments, developers of overlay networks can still be
insulated from the idiosyncrasies of specific hardware configurations,
to a large degree.

=== Provisioned Resource Model ===

Overlay hosting services support provisioned resources, allowing overlays to
reserve both link bandwidth and processing resources in hosting platforms.
This is necessary to enable overlays to engineer their services to provide
satisfactory performance to their users. While it will often not be possible
to provide provisioned bandwidth on access links connecting users to their
first-hop OHP, provisioned bandwidth should generally be available on
backbone links joining OHPs to one another.

=== Packet Based Communication ===

Our interest is in overlay hosting services that support packet-based
communication, rather than circuits. While one can reasonably argue that
this is a violation of the architectural neutrality principle, we choose
to draw the line here. This choice does not rule out the provision of circuit-like
services, since these can be readily provided over a provisioned packet channel.
However, we do not support transparent access to underlying circuit services
(although the substrate may certainly use such services to provide packet
channels to overlays).

=== Technology Adaptability ===

Since a successful OHS can be expected to last for many years or decades,
it's important that it be able to easily accommodate new types of processing
and transmission resources. We anticipate a wide range of processing resources,
including general purpose processors running conventional operating systems,
Network Processor subsystems with minimal run-time support and FPGA subsystems
that are configured strictly by overlay providers. As new resource types are
developed, it should be possible to incorporate them into the OHS infrastructure
without disrupting ongoing operations.

----

The pages listed below provide more detailed discussion of specific issues
relating to internet-scale overlay hosting.

* [[Scalable Overlay Hosting Platforms|Scalable Overlay Hosting Platforms]]
* Supercharged PlanetLab Platform|Supercharged PlanetLab Platform

----

== Scalable Overlay Hosting Platforms ==

The purpose of an ''Overlay Hosting Platform'' (OHP) is to provide resources for use by
individual overlay. We seek to provide the greatest possible
flexibility to overlays, while maintaining appropriate separation among different overlays.
This of course includes separation of their use of memory and mass storage,
but also their use of network bandwidth and processing capacity.

=== High Level System Organization ===

Consideration of a conventional router or switch leads naturally to an OHP 
architecture in which line cards are replaced by ''virtualized line cards'' 
that include a substrate portion and generic processing resources that 
can be assigned to different virtual line cards. 
The substrate supports configuration of the generic processing resources 
so that different virtual line cards can co-exist without interference. 
On receiving data from the physical link, the substrate first determines 
which virtual line card it should be sent to and delivers it. 
Virtual line cards pass data back to the substrate, in order to 
forward it through the shared switch fabric, on input, 
or to the outgoing link, on output.

[[Image:virtualizedLineCard.gif|frame|right|Virtualized Line Card Architecture]]

One issue with this architecture concerns how to provide generic 
processing resources at a line card, in a way that allows the 
resources to be shared by different overlays. 
Conventional line cards are often implemented using Network Processors (NP),
programmable devices that include high performance IO and 
multiple processor cores to enable high throughput processing. 
It seems natural to take such a device and divide its internal 
processing resources among multiple overlays. 
For example, an NP with 16 processor cores could be used by up 
to 16 different overlays, by simply assigning processor cores. 
Unfortunately, current NPs are not designed to be shared. 
All processing cores have unprotected access to the same physical memory, 
making it difficult to ensure that different overlays don’t 
interfere with one another.

Also, each processor core has a fairly 
small program store. This is not a serious constraint in 
conventional applications, since processing can be pipelined 
across the different cores, allowing each to store only the program 
it needs for its part of the processing. 
However, a core implementing all the processing for one overlay must 
store the programs to implement all the processing steps for that overlays. 
The underlying issue raised by this discussion is that efficient 
implementation of an architecture based on virtualized line cards, 
requires components that support fine-grained virtualization and 
conventional NPs do not.

The virtualized line card approach is also problematic in other respects. 
Because it associates processing resources with physical links, 
it lacks the flexibility to support overlays with a wide range of processing needs.
Some overlays may require more processing per unit IO bandwidth than NPs provide,
and this is difficult to support with a virtualized line card approach.
The virtualized line card approach also does not easily accommodate alternate
implementation approaches for overlay nodes (such as configurable logic).

The above discussion leads us to the ''processing pool'' architecture,
in which the processing resources used by overlays are separated
from the physical link interfaces.
This allows a more flexible allocation of processing resources and reduces the 
need for fine-grained virtualization. This architecture, illustrated 
at right, provides a pool of Processing Engines (PE), that are 
accessed through the switch fabric. 

[[Image:ProcessingPool.gif|frame|right|Processing Pool Architecture]]

The line cards that terminate 
the physical links forward packets to PEs through the switch fabric, 
but do no processing that is specific to a particular overlay. 
There may be different types of PEs, including some implemented 
using network processors, others implemented using conventional 
microprocessors and still others implemented using FPGAs. 
The NP and FPGA based PEs are most appropriate for high throughput 
packet processing, the conventional processor for control functions 
that require more complex software or for overlays with a high ratio 
of processing to IO. An overlay node may be implemented using a single 
PE or multiple PEs. In the case of a single PE, data will pass 
through the physical switch fabric twice, once on input, once on 
output. In a node that uses multiple PEs to obtain higher
performance, packets may have to pass through the switch fabric a third time.

The primary drawback of the processing pool architecture is that it 
requires multiple passes through the switch fabric, increasing delay 
and increasing the switch capacity needed to support a given total IO bandwidth. 
The increase in delay is not a serious concern in wide area 
network contexts, since switching delays are typically 10 <math>\mu</math>s or less. 
The increase in capacity does add to system cost, but since a 
well-designed switch fabric represents a relatively small part 
of the cost of a conventional router (typically 10-20%), 
we can double, or even triple the capacity without a proportionally 
large increase in the overall system cost.
Also, since OHPs can be expected to have a higher ratio of processing
to IO than conventional network routers, the impact of the higher
bandwidth use is significantly reduced.

The great advantage of the processing pool architecture is that it 
greatly reduces the need for fine-grained virtualization within 
NP and FPGA-based subsystems, for which such virtualization is difficult. 
Because the processing pool architecture brings together the traffic 
for each individual overlay node, there is much less need for PEs to 
be shared among multiple nodes. The one exception to this is nodes
with such limited processing needs that they cannot 
justify the use of even one complete PE.  Such nodes can 
still be accommodated by implementing them on a general purpose 
processor, running a conventional operating system that supports a virtual machine environment.  
Later, we discuss another approach that allows such nodes to 
share an NP-based PE for fast path forwarding, while relying on a virtual
machine running within a general purpose processor to handle exception cases. 

Another advantage of the processing pool architecture is that it simplifies 
sharing of the switch fabric. The switch traffic must maintain 
traffic isolation among the different overlay nodes. 
One way to ensure this is to constrain the traffic flows entering 
the switch fabric so as to eliminate the possibility of 
internal congestion. This is difficult to do in all cases. 
In particular, nodes consisting of multiple PEs should be allowed 
to use their “share” of the switch fabric capacity in a flexible fashion, 
without having to constrain the pair-wise traffic flows among the PEs. 
However allowing this flexibility makes it possible for several PEs 
in a given metarouter to forward traffic to another PE at a rate 
that exceeds the bandwidth of the interface between the 
switch fabric and the destination PE. 

There is a straightforward solution to this problem in the processing pool 
architecture. To simplify the discussion, we separate the handling of 
traffic between line cards and PEs from the traffic among PEs in a 
common metarouter. In the first case, we can treat the traffic as 
a set of point-to-point streams that are rate-limited when they enter the fabric.
Rate-limiting these flows follows naturally from the fact that they 
are logical extensions of traffic flows on the external links. 
Because the external link flows must be rate limited to provide 
traffic isolation on the external links, the internal flows within 
the switch fabric can be configured to eliminate the possibility 
of congestion.

For PE-to-PE traffic, we cannot simply limit the traffic entering the switch, 
since it’s important to let PEs communicate freely with other PEs in the 
same node, without constraint. 
However, because entire PEs are allocated to nodes in the 
processing pool architecture, it’s possible to obtain good traffic 
isolation in a straightforward way, for this case as well. 
In general, we need two properties from the switch fabric. 
First, it must support constrained routing, so that traffic from 
one to node cannot be sent to PEs belonging to another node. 
Second, we need to ensure that congestion within one node
does not affect traffic within another node. 
The emergence of 10G Ethernet as a backplane switching technology 
provides the first property. Such switches support VLAN-based routing 
that can be used to separate the traffic from different nodes. 
The second property is satisfied by any switching fabric that is 
nonblocking at the port level. While some switch fabrics fail to a 
fully achieve the objective of nonblocking performance, 
this is the standard figure of merit for switching fabrics a
and most come reasonably close to achieving it.

== References ==

;[BA06]:Bavier, A., N. Feamster, M. Huang, L. Peterson, J. Rexford. “In VINI Veritas: Realistic and Controlled Network Experimentation,” ''Proc. of ACM SIGCOMM'', 2006.

;[BH06]:Bharambe, A., J. Pang, S. Seshan. “Colyseus: A Distributed Archi-tecture for Online Multiplayer Games,” In ''Proc. Symposium on Networked Systems Design and Implementation'' (NSDI), 3/06.

;[CH02]	:Choi, S., J. Dehart, R. Keller, F. Kuhns, J. Lockwood, P. Pappu, J. Parwatikar, W. D. Richard, E. Spitznagel, D. Taylor, J. Turner and K. Wong. “Design of a High Performance Dynamically Extensible Router.” In Proceedings of the DARPA Active Networks Conference and Exposition, 5/02.

;[CH03]	:Chun, B., D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawr-zoniak, and M. Bowman. “PlanetLab: An Overlay Testbed for Broad-Coverage Services,” ACM Computer Communications Review, vol. 33, no. 3, 7/03.

;[CI06]	:Cisco Carrier Routing System. At www.cisco.com/en/ US/products/ps5763/, 2006

;[DI02]	:Dilley, J., B. Maggs, J. Parikh, H. Prokop, R. Sitaraman, and B. Weihl. “Globally Distributed Content Delivery,” IEEE Internet Computing, September/October 2002, pp. 50-58.

;[FO07]	:Force 10 Networks. “S2410 Data Center Switch,” http:// www.force10networks.com/products/s2410.asp, 2007.

;[FR04]	:Freedman, M., E. Freudenthal and D. Mazières. “Democratizing Content Publication with Coral,” In Proc. 1st USENIX/ACM Sym-posium on Networked Systems Design and Implementation, 3/04.

;[GE06]	:Global Environment for Network Innovations. http://www.geni.net/, 2006.

;[HI98]	:Mike Hicks_ Pankaj Kakkar_ Jonathan T_ Moore_ Carl A_ Gunter_ and Scott Nettles. “PLAN, A packet language for active networks,” In Proceedings of the Third ACM SIGPLAN International Conference on Functional Programming Languages, 1998.

;[IXP]	:Intel IXP 2xxx Product Line of Network Processors. http://www.intel.com/design/network/products/npfamily/ixp2xxx.htm.

;[KA02]	:Karlin, Scott and Larry Peterson. “VERA: An Extensible Router Architecture,” In Computer Networks, 2002.
 
;[KO00]	:Kohler, Eddie, Robert Morris, Benjie Chen, John Jannotti and M. Frans Kaashoek. “The Click modular router,” ACM Transactions on Computer Systems, 8/2000.
 
;[KO04]	:Kontothanassis, L. R. Sitaraman, J. Wein, D. Hong, R. Kleinberg, B. Mancuso, D. Shaw and D. Stodolsky. “A Transport Layer for Live Streaming in a Content Delivery Network,” Proc. of the IEEE, Special Issue on Evolution of Internet Technologies, 9/04.

;[PA03]	:Pappu, P., J. Parwatikar, J. Turner and K. Wong. “Distributed Queueing in Scalable High Performance Routers.” Proceeding of IEEE Infocom, 4/03.

;[PE02]	:Peterson, L., T. Anderson, D. Culler and T. Roscoe. “A Blueprint for Introducing Disruptive Technology into the Internet,” Proceed-ings of ACM HotNets-I Workshop, 10/02.

;[RA05]	:Radisys Corporation. “Promentum™ ATCA-7010 Data Sheet,” product brief, available at http://www.radisys.com/files/ATCA-7010_07-1283-01_0505_datasheet.pdf.

;[RH05]	:Rhea, S., B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica and H. Yu. “OpenDHT: A Public DHT Service and Its Uses,” Proceedings of ACM SIGCOMM, 9/2005.

;[SP01]	:Spalink, T., S. Karlin, L. Peterson and Y. Gottlieb. “Building a Robust Software-Based Router Using Network Processors,” In ACM Symposium on Operating System Principles (SOSP), 2001.

;[ST01]	:Stoica, I., R. Morris, D. Karger, F. Kaashoek and H. Balakrishnan. “Chord: A scalable peer-to-peer lookup service for internet applica-tions.” In Proceedings of ACM SIGCOMM, 2001.

;[ST02]	:Stoica, I., D. Adkins, S. Zhuang, S. Shenker, S. Surana, “Internet Indirection Infrastructure,” Proc. of ACM SIGCOMM, 8/02.

;[TU06]	:Turner, J. “A Proposed Architecture for the GENI Backbone Plat-form,” In Proceedings of ACM- IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), 12/2006.

;[VS06]:Linux vServer. http://linux-vserver.org