\documentclass[conference]{IEEEtran}
\IEEEoverridecommandlockouts
% The preceding line is only needed to identify funding in the first footnote. If that is unneeded, please comment it out.
\usepackage{cite}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{textcomp}
\usepackage{xcolor}
\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}    
\usepackage{makecell,rotating}
    \setcellgapes{5pt}
\pagestyle{plain}    
    
\begin{document}

\title{Wide Area Network Planning Drivers and Methods for Internet Services\\
%{\footnotesize \textsuperscript{*}Note: Sub-titles are not captured in Xplore and
%should not be used}
%\thanks{Identify applicable funding agency here. If none, delete this.}
}

\author{\IEEEauthorblockN{<NAME>}
\IEEEauthorblockA{\textit{School of Architecture} \\
\textit{Carnegie Mellon University}\\
Pittsburgh, PA USA \\
<EMAIL>}
}

\maketitle

\begin{abstract}
This paper considers global-scale wide area network (WAN) capacity planning methodologies for distributed storage systems in which compute and data store resources are geographically dispersed in remote data-centers (DCs). The disparate data-center resources are bridged together by the WAN spanning across continents and seas. There are several motivations for geographic distribution of internet services. Namely, higher system availability in cases of regional disasters and proximity to end-users are considered by this work. Both the failure recovery strategy and end-user proximity require redundant data that is consistent and always available. Thus data-replication over the WAN is a key enabler for distributed systems that collectively make World Wide Web. 

To economically meet the objectives noted above; compute, storage, and network resources need to be balanced with consideration of trade-offs between them. Of the three resources, the WAN is a relatively cheap asset. Due to the relative costs, over-building the WAN is often the naive choice with high absolute costs and long lead times \cite{Zhuang}. This work contributes a methodology to quantify the WAN demands with consideration of computational and storage nodes with-in the distributed system.
\end{abstract}

\begin{IEEEkeywords}
wide area network provisioning, replication, backbone networks, network capacity
\end{IEEEkeywords}

\section{Executive Summary}

Users of web services demand high availability of data in diverse sets of operational environments. Web services respond with databases that provide strongly consistent data for users regardless of their location. An online platform with distributed database architecture is also agnostic to component level failures. In these environments component failures are random and exponentially correlated with the scale of the systems. Compounding the equipment failures is the vulnerability presented when a network link is partitioned, preventing communication between fully functional nodes. 

Despite the need, it has been proven that Consistency, Availability, and Partition tolerance (CAP) can not co-exist against in distributed systems by the CAP Theorem \cite{CAP}. However, proper network planning with sufficient capacity and multi-path redundancy do mitigate the risk of network unavailability and minimize the chances of partitioning (cutting a link).

WANs are not just a diaster recovery mechanism. Strategic provisioning of WAN lifts the overall system performance as well. Reffering to Amdahl's law, which is based on that observation that when a process segment is sped up, the effect on the end to end process time is dependent on how significant the part originally was and the incremental speed gain. Table \ref{dean} lists the latency associated with different components in a distributed systems stack, \cite{Dean}. At global scale, improvements in network latency can contribute upto 10 factors of magnitude more significance to speed up the end to end process than L1 cache. It is also generally accepted that higher ranking components in the list have higher unit cost per bit of capacity \cite{Bryant}. Given the impact and cost per bit of network, this work aims to quantify the capacity ceiling which alleviates the WAN as constraining factor for distributed systems. Here the several long term planning methods that bin pack multiple communications flows are logically decoupled is explored. Logically decoupled flows, in this context, are service communications that share source and destination points yet their bandwidths are independent variables. In such cases, a collection of flows may have diverging patterns or may simultaneously converge as independent variables.
 
\begin{table}[htbp]
\caption{ Process Latency Scale, \cite{Dean}}
\begin{center}
\begin{tabular}{ll}
\hline
\textbf{Component} 					& \textbf{Latency} (ns)	\\
\hline
L1 cache reference					& 0.5					\\
Branch mispredict 					& 5					\\
L2 cache reference					& 7                     \\
Mutex lock/unlock					& 25					\\
Main memory reference				& 100					\\
Compress 1K bytes with Zippy 		& 3,000					\\
Send 2K bytes over 1 Gbps network	& 20,000				\\
Read 1 MB sequentially from memory	& 250,000				\\
Round trip within same datacenter	& 500,000				\\
Read 1 MB sequentially from disk	& 20,000,000			\\
Send packet from CA to Netherlands and back to CA 	& 150,000,000			\\
\hline
\end{tabular}
\label{dean}
\end{center}
\end{table}

Considering the CAP theorem and Amdahls law, service operators need to understand their networks. Operators need to sufficiently plan the size of the networks for normal and disaster recovery operations in the face of many failure modes of within the holistic system. This paper surveys several different data base systems and extracts their network dependency. It then evaluates three approaches to network planning based on traces obtained from Wikipedia.


\section{Introduction}

Web services are transactional and exhibit four key properties \cite{CAP}. (1) it is expected that transactions commit or fail entirely (atomic), (2) they always provide consistent data regardless of the location they are executed from, (3) uncommitted transactions are isolated, and (4) once committed they are persistent. For modern internet services, these properties and objectives are achieved with global scale data-replications strategies. The four service level properties are attributed to the three key design objectives listed below. 

\begin{itemize}
	\item Durability: Persistent in case of physical failures.
	\item Accessibility: Be able to use when needed.
	\item Performance: Get to it quickly.
\end{itemize}

Data-replication over the WAN facilitates redundant data to be cast into multiple nodes that are spread across geographically disparate locations. Disparately located redundant data allows a system to tolerate failure modes such as node outages or network partitions, making it an attractive choice when durability and availability of a system are design objectives. Replication strategies are also used to enhance performance of globally distributed internet services. First by allowing faster user access to data with minimum distance optimizations when serving requests. Secondly for distributing the read requests over more nodes and balancing the load on them. The former reduces communication latency and the latter reduces queing latency that would arise if all read requests were sent to a single node. However, when there are multiple copies of the same data there is a risk for them to not be consistent with each other due to communication latencies and failures in the system.

There are three methods for data-replication widely used today and each offers a different degree of trade-off between consistency and latency \cite{Abadi}. The first method has minimal latency where updates are multi-cast to all the replicas simultaneously. However, isolated clients (external consumers of the data-base) may send multiple updates that are received out of order due to communication delays leading to over-writes. The second scheme has updates routed to a designated master node which has the purest and most up-to date view of the data-base. The master node then replicates to all replicas either synchronously or asynchronously. The third scheme sends updates to an arbitrary node, which records that data and make to replicas and users with local access. One shortfall with this approach is upon failure of the arbitrary node, unrecorded and forwarded data maybe lost/

Given the dependence on replication for internet service and it's sensitivity to latency, it is crucial that WANs be properly provisioned with sufficient capacity and redundancy in order to negate congestion that leads to delays. In the motivational work section, several modern data-base systems and their replication strategies are reviewed. The review finds that the published DB system present an abstracted view of their network dependency. Therefore physical implementation of the network architecture may be proprietary and distinct from each other. To generalize the distinct implementations, the Background section first a develops a hierarchical clos topology to provide intuition about the rest of the paper. The Methodology section presents several approaches to estimating bandwidth requirements. These methodologies are then evaluated and compared to each other for a typical uses case in the results sections. This paper concludes with the Conclusion section. For brevity, this work only considers a single class of network traffic. 

\section{Motivational Works}

Wide area networks serve as the backbone for many internet applications that operate across regional data-centers. The traffic on the inter data center links are segregated into three classes; interactive, large file transfers, and background \cite{Zhang}. Interactive traffic are blocking operations; where the byte level transactions are required to keep things proceeding. Large file transfers entail transmission of requested resources by some deadline. Background traffic are workloads that are opportunistically using the link, and preempting them does not expose the system of any idempotent side effects. DB communications traffic typically consists of workloads that are bound by deadlines and also pseudo-interactive. This section presents a sample of specific database system that serve as back-ends for many modern online platform architectures. 

%MS-SD WAN

Megastore was the first large-scale system to use Paxos to replicate primary user data across regionally distributed data-centers for every write \cite{megastore}. Megastore enables applications to have fine grained control for partitioning and locality by Entity Groups. Several entity groups in Megastore are provisioned across a set of data-centers. Locally, the distinct entity groups have loose consistency requirements however common entity groups across data-centers maintain atomic, consistent, isolated, durable (ACID) data over the WAN. Megastore relies on the underlying Bigtable \cite{bigtable} instances at each of Google's data-centers. Megastore implements a multiple version concurrency control schema, that allows DB fields to have multiple versions isolated by time-stamps. This eliminates interference between reads and writes, as reads will be fetched from the most completed time-stamp DB. Megastores has several types of logical actors. Namely they are leader, full-replicas, witness, read-only. Witness actors vote in Paxos rounds and store write ahead logs, but are thrift on storage for entities. Read only actors provide present views of the data based on a near real time snapshot.

Spanner is a gloablly distributed database in which writes are committed with the Paxos protocol at single leader node. Reads access the data directly from any replica  that  is  sufficiently  up-to-date, which can have service garantees in terms of consistency classes.  The  set  of replicas is collectively a Paxos group \cite{Spanner}. As a globally distributed database, Spanner provides several interesting features, \cite{Spanner}. These features faclitate replication configurations to be dynamically controlled at by applications with . First, applications can specify constraints to control which data centers contain which data. Second, it allows application owners to specify how far data is from its users (to control read latency). Third, application owners to delegate how far replicas  are  from  each  other  (to  control  write  latency). Finally, applications can control  how  many  replicas  are maintained (to control durability, availability, and read performance). 

In the Google Cloud Platform Console, the most economical multi-region Spanner instance, nam3, notes the following specs. Nam3 consists of 3-way redundancy with-in North America. It provides an availability service level objective (SLO) target of 99.99\%. In contrast to a single region Spanner instance which yields a 99.9\% SLO. 


\textbf{Spanner Guidelines}
\begin{itemize}
 \item Each Cloud Spanner node in nam3 can provide up to 7,000 QPS (queries per second) per region, or 1,800 QPS of writes across all regions for writing 1 kB data per row with total storage capacity of 2TiB.
 \item For optimal performance in this configuration, it is recommended that CPU utilization be maintained at at or below 45\%.
 \item A minimum of 3 nodes is recommended for production environments; ie user facing.
 \item Cloud Spanner's performance is highly dependent on workloads, SQL schema design, and data-set characteristics. 
\end{itemize}

Cassandra is a NoSQL database open sourced by Facebook \cite{Cassandra}. Cassandra's architecture is based on a coordinator paradigm, where the consistency level is user defined and a coordinator node is responsible for forks and joins of the data to yield either a single view, quorum view ($(\frac{Nodes}{2} +1)$), or all views of the data. Each node in the Cassandra architecture is configured to directly communicate with clients. To illustrate, clients reading some data connect with a single Cassandra node. Upon receiving the request, the Cassandra node presumes the coordinator responsibility and retrieves data from its local storage and/or coordinates its retrieval based on the consistency level required by the request.

MongoDB Atlas is a open sourced MongoDB NoSQL database offered on the cloud \cite{Mongo}. Cloud distributed Atlas consists of a set of upto 50 replicas with one primary replica member and the balance serve in secondary replica member roles. Upon a failure of the primary, one of the secondary members is automatically upgraded to primary based on an election process. The promotion of a secondary node to primary takes on the order of a few seconds, at which point clients direct their connection to the new primary for writes. Reads are still facilitated at all available nodes without disruption. Atlas' primary election process is implemented with the Raft consensus protocol \cite{raft}. First, the protocol evaluates replica based on their state, biasing towards replicas that have the most recent updates applied. Second, Atlas' RAFT checks the heartbeat and connectivity status of a quorum of replica set members. Finally, the algorithm allows administrator to configure a deterministic preference of the replica set to promote. With a replicas promoted all secondary replicas redirect their connection to it. 

In MongoDB Atlas data is horizontally spread across physical servers by using sharding techniques. Sharding of values in a data set can be done locally with-in a single data-center, or distributed globally across the replica-sets. Each shard has a replica set consisting of primary and secondary members as shown in \ref{mongo_shards}. The shards are made transparent to clients with the use of local "Query Routes" as an abstraction layer. When reading, the default is to read from the primary member but users can set reads to be from the nearest replicas for minimum latency at the cost of consistency. Writes can be acknowledged from the primary only, a deterministic count of replicas, the quorum of replicas, or all replicas. There is an option for completely unacknowledged writes. To relieve the burden on the network demand, application layer data is compressed upto 80\% for transport across the network. Users can specify weight for writes to specific data-centers and apply higher relative weights to Primary DC's.

\begin{figure}[htbp]
\centering
\includegraphics[scale=.5]{mongo_shards.eps}
\caption{MongoDB Atlas Sharding Scheme \cite{Mongo}}
\label{mongo_shards}
\end{figure}

To appreciate the complexity of distributed systems quantitatively, the Storage Configuration Compiler (SCC) provides a broadview of the interaction between various componets of a distributed storage system \cite{scc}. The Storage Configuration Compiler is a tool that takes an application's service level objectives, storage hardware parameters, and compute server parameters along with their costs to suggest optimum cluster configurations. At the application level SCC separates tasks and data sets. Data-set accessibility is treated as a non-deterministic variable and each operation is modeled as a probability function. It is shown explicitly in SCC that network delays hang-up machine resources waiting for responses, wasting expensive resources. 

\textbf{Storage I/O throughput definitions for SCC:}
 \begin{itemize}
 \item read/write gap parameter for non-sequential seeks.
 \item $\frac{size}{rate}$ + gap is the latency to serve 
 \end{itemize}

\textbf{I/O operations definition for SCC:}
 \begin{itemize}
 \item Number of records read in an I/O operation
 \item Number of records written in an I/O operation
 \item Bytes count of each record
 \item Are the reads parallel
 \end{itemize}

\textbf{Task Dependencies:}
\begin{itemize}
\item The count of invocations being performed
\item are the invocations in parallel
\item is the whole dependency block or non-blocking
\end{itemize}

\textbf{Capacity Parameters:}
\begin{itemize}
\item data set size
\item does it need to be persistent
\item local or remote
\end{itemize}


\section{Background}
This section provides context about the current industry trends. The next paragraph argues that local costs optimization increases the reliability burden for global presence. The following subsection then presents the bounds of data communication networks is presented from the data-center level to the wide area networks that connect  data centers. 

The current data center market has two paradigms for cost savings, one is hardware based and another infrastrucutre based. The hardware based paradgim consists of the mentatlity that more of cheaper hardware are better than less of expensive ones. Parrallelsim is increased with more hardware node counts leading to faster end to end processes, compared to using few high cost machines yeild a performance/\$ efficiency gains. More hardware counts do allow more local redundanency. Replication at locally housed servers increases data availability in the presence of individual server failures, but only with diminishing returns \cite{megastore}. 

The infrastructure costs savings are based on relaxing tried and trued industrial practices, examples being free air cooling that introduces contamination or removing UPSes from the power delivery systems. The utility scale systems such as power, cooling, and long haul tele-communication networks introduce additional risk that is not offset by local replication. It has been pointed out that hyperscale internet data-centers are susceptible to construction value engineering that risk some level of facility-wide failure modes \cite{wsc}.

\subsection{Context Setting}

To motivate interest in the rest of this paper, let's visit some typical conisderations that are encountered in industry. First, applications need to understand their distributed process latencies. In the absense of network congestion, the ideal elapsed time ($t_e$) to transfer B, bytes, to R, replicas, is shown in equation \ref{replication_time}. $T$ is the network throughput rate in bytes per unit of time and $L$ is latency to transfer bytes between two machines\cite{GFS}. Network links are typically on the order of \textit{O}(xx)-Gbps (T), and $L$ is far below 1 ms as seen for component level contributions in Table \ref{dean}. Therefore, 1 MB can ideally be distributed in about 80 ms.

\begin{equation}
\label{replication_time}
t_e = B/T+RL
\end{equation}

Second, applications need to understand the statistical distribution of their communication capacities. To demonstrate this, it is most intuitive to consider a local data-center environment as seen by a server on a rack. Maximum bandwidth that server can send out of a rack is limited by the top of rack (TOR) outbound channels. As an example, if a rack consists of 35 servers, each connected to the TOR at 10 Gbps channels. With a TOR capacity of 100 Gbps to its external adjacencies, only 10 of the servers can sustain full bandwidth.  Equation \ref{TOR} indicates the limit of the flows from all servers in a rack must be equal to or less than the TOR's external facing capacity. However, servers with-in a rack can also communicate with each other and not be limited by the TOR's external limits. An depiction of the complete topology is shown in \ref{DCN}.

\begin{figure}[htbp]
\centering
\includegraphics[scale=.35]{rack_view.png}
\caption{Request Ingress and Responses from rack perspective.}
\label{DCN}
\end{figure}

Link saturation at rack level:
\begin{equation}
\label{TOR}
TOR \geq \sum{I_{i}}
\end{equation}

\begin{footnotesize}
Where: \\
\indent TOR: Rack level ingress and egress bandwidth to external adjacency.\\
\indent $I_{i}$: Server level ingress and egress network bandwidth.\\
\end{footnotesize}


\section{Methodologies}

In this section three forecasting methods are are discussed. The methods are namely historical based, transaction based, and power based. Wikipedia page view data is used to demonstrate the application of each method presented. The approach described in this section resemble those used by aggregate network planners, where numerous independent services are bin packed into a network flow from a source node to a destination node. As is typically the case for network operators responsible for the Cloud, where service level network benchmarks are not exposed at time of planning. 

Having benchmarks that correlate to other resource dimensions may provide more robust signals for network capacity demands earlier. In a simple example, workers (computers) are required to generate network traffic. If benchmarks that correlated computer counts with a network limits, the correlation can be used to provision network capacity preemptively as more computers were ordered but not set in production. 

The problem is compounded further by the independent nature of the services. Network traffic is known to have Markovian properties \cite{Harchol-Balter}. Their simultaneous behavior is at best another layer of probabilistic functions.  

In Cloud enviroments agility is also a key criterion \cite{Spanner}. First agility is needed when new clients are on-boarded. Secondly, new features that increase network efficiency or new use cases of network are continuously added. Finally, the decoupling of physical resources from logical resources have enabled container type, elastic workloads. The containers not only dynamically change resource dimensions but can also physically migrate across the globe without much effort. 

Given the above, the coarse approaches explored in this work are sufficient to forecast IP network traffic in the leads times that operators are bound to. Specifically, the method used to identify the source of the traffic for the Wikipedia page view is heuristics based, yet since it is non-proprietary it suffices for academic research and demonstrates suitability for industrial research.

\subsection{Data Set}
Traffic to 145,063 Wikipedia Pages for 803 days from July 2015 through September 2017 is used demonstrate the scale of replication required for global services. The data will be used to train and test the models developed here. The training set will be partitioned to be inclusive of traffic from July 2015 to December 2016. The balance of the data will be used to test accuracy of the models. The pages are segregated into 7 different languages; namely English, Japanese, German, French, Chinese, Russian, and Spanish. The average volume of visits per language is shown in Figure \ref{average_use}. Figure \ref{95_tile} shows the distribution of the 95 percentile usage values per respective language.   

\begin{figure}[htbp]
\centering
\includegraphics[scale=.25]{average_use.jpg}
\caption{Average Daily Visits to Study Set of Pages by Language}
\label{average_use}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[scale=.25]{quantile95_use.jpg}
\caption{0.95 Quantile Visits to Study Set of Pages by Language}
\label{95_tile}
\end{figure}

After segregation of the pages by language and dropping pages without language indicators, the languages are mapped to countries in which they are the official tongue. Figure \ref{world} shows the mapping of languages to their respective countries by color groups; English(blue), Japanese(dark gray), German(yellow), French(red), Chinese(green), Russian(orange), and Spanish(magenta). Red markers indicate the locations of Wikipedia data centers from around the world as listed in Table \ref{wiki_dc}. Ashburn has the primary (P) data-center for application services, and Carrollton serves as the redundant (R) node. The remaining 3 sites are smaller edges of the Wikipedia network where user traffic ingresses and egresses Wikipedia network. 

Throughout this paper the associated set of Wikipedia data-centers will be used as the model network and several assumptions will be called out in regards to attributes of the system that are not in the public domain. Furthermore, some of the system complexity will be reduced for brevity and academic objectives of this work. The traffic generating in a particular country is associated with their closest ingress points as listed in Table \ref{ingress_lang} by using a minimum distance function of the respective geographical codes. This table shows that English is the most dominant language with traces appearing at all of Wikipedia's ingress sites. English is the most frequently searched language also (see figure \ref{average_use}), here it is shown to also be the most distributed globally.

\begin{figure}[htbp]
\centering
\includegraphics[scale=.15] {world.eps}
\caption{Countries where set of languages for Wiki Page is the primary language}
\label{world}
\end{figure}


\begin{table}[htbp]
\caption{Wikipedia Network Nodes}
\begin{center}
	\begin{tabular}{|c|c|c|c|c|}
		\hline
	{} &         ID &  Address                  & Power(kW) & Type \\
		\hline
	1 &       eqiad &  Ashburn, Virginia, USA   & 130-kW    & Applications-P \\
	2 &       codfw &  Carrollton, Texas, USA   & 77-kW     & Applications-R  \\
	3 &       esams &  Haarlem, Netherlands     & $<10$-kW  & Caching  \\
	4 &       ulsfo &  San Francisco, CA, USA   & $<5$-kW   & Caching  \\
	5 &       eqsin &  Singapore                & 10-kW     & Caching \\
	6 &       eqord &  Chicago                  & -         & Transit \\
	7 &       eqdfw &  Dallas                   & -         & Transit \\
	8 &       knams &  Amsterdam                & -         & Transit \\
		\hline
\end{tabular}
\label{wiki_dc}

\end{center}
\end{table} 

%this table is about 2 weeks of work
\begin{table}[htbp]
\caption{Languages to Ingress Sites}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
DC            &  en & ja & de &  fr & zh & ru &  es & \textbf{total} \\
\hline
Ashburn       &  18 &  - &  - &   5 &  - &  - &   8 & \textbf{31} \\
Carrollton    &   2 &  - &  - &   - &  - &  - &  11 & \textbf{13} \\
Haarlem       &  17 &  - &  4 &  16 &  - &  - &   1 & \textbf{38} \\
San Francisco &   3 &  - &  - &   1 &  - &  - &   - & \textbf{4}  \\
Singapore     &   9 &  1 &  - &   4 &  5 &  1 &   - & \textbf{20} \\
\hline
\end{tabular}
\label{ingress_lang}
\end{center}
\end{table}

No power capacity values for 'eqsin' data-center was exposed by Wikipedia. Therefore the power demand for the Singapore data-center has been estimated by doing a qualitative similarity analysis. The time-series plot of the hit rate at each of the ingress data-centers results in Figure \ref{ingress_hitrate}. Singapore's average page views per day visually appears to dominate other data-centers for ingress traffic, yet it is a caching site so is only comparable to other caching sites. Haarlem generally tracks Singapore well, with only slight divergence during their peak traffic period. When quantified, the average hit rate of Singapore is 3\% higher than Haarlem. The traffic allocation approach is indicated in Table \ref{ingress_sites}. Given the uncertainty of < 10kW conditional value provided by Wikipedia for Haarlem, Singapore is also determined to have a 10-kW demand. 


\begin{table}[htbp]
\caption{Method for Traffic Allocation to each ingress site}
\begin{center}
\begin{tabular}{cl}
Objective: & Determine the hit rate of each ingress site.                 \\
\hline 
Step 1:    & Map language to page.                                        \\
Step 2:    & Map languages to countries where they are the first tongue.  \\
Step 3:    & Map ingress sites to countries with minimum distance         \\
           & function.                                                    \\
Step 4:    & Get distribution of  number of countries served by each      \\
           & ingress site.                                                \\
Step 5:    & For each ingress site, sum up the daily views of pages by    \\
           & the language. Multiply to relative fraction from step 4 -    \\
           & origin countries  with language to site / total number of    \\
           & (Count countries with language).                             \\  
         

\end{tabular}
\label{ingress_sites}
\end{center}
\end{table}

\begin{figure}[htbp]
\centering
\includegraphics[scale=.35] {ingress_hitrate.jpg}
\caption{Traffic based on source country and its min(cost=distance) ingress site.}
\label{ingress_hitrate}
\end{figure}

In Table \ref{wiki_dc} there are three transit sites in the Wikipedia network also. These are considered as passive network nodes, in that no processing or storage is facilitated at the sites. Figure \ref{wiki_net} illustrates Wikimedia's autonomous network system. The nodes are per Table \ref{wiki_dc} and the colored lines indicate discrete network connections, annotated with their carrier and the latency. The adjacency matrix of source and destination locations as vertices is shown in Table \ref{adajacency_matrix}

The data-set from Kaggle does not provide an explicit flag indicating read or writes. In this work, all of the access tasks listed in Kaggle are considered to be reads. The write values are indicated by the content generated as a percentage of total Wikipedia article count in 2016. 

\begin{figure}[htbp]
\centering
\includegraphics[scale=.2]{wiki_net.png}
\caption{Wikimedia's AS14907 Network. Source \cite{wiki_network}}
\label{wiki_net}
\end{figure}

\begin{table}[htbp]
\caption{DC Adjacency Matrix}
\begin{center}
\begin{tabular}{p{1cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}}
{}    & \rothead[c]{EQIAD}& \rothead[c]{ESAMS} & \rothead[c]{EQORD} & \rothead[c]{KNAMS} & \rothead[c]{CODFW} & \rothead[c]{ULSF} & \rothead[c]{EQSIN} & \rothead[c]{EQDFW} \\
\hline
EQIAD &     - &     2 &     1 &     1 &     3 &     - &     - &     - \\ \hline
ESAMS &     2 &     - &     - &     1 &     - &     - &     - &     - \\ \hline
EQORD &     1 &     - &     - &     - &     1 &     1 &     - &     - \\ \hline
KNAMS &     1 &     1 &     - &     - &     - &     - &     - &     - \\ \hline
CODFW &     3 &     - &     1 &     - &     - &     1 &     1 &     1 \\ \hline
ULSFO &     - &     - &     1 &     - &     1 &     - &     1 &     1 \\ \hline
EQSIN &     - &     - &     - &     - &     1 &     1 &     - &     - \\ \hline
EQDFW &     - &     - &     - &     - &     1 &     1 &     - &     - \\ 

\end{tabular}
\label{adajacency_matrix}
\end{center}
\end{table}




\subsection{Historical Extrapolation}
In this approach, the past observation is indicative of future demand. 

Segregate data by consumer and application
Use existing capacity as baseline and compare to usage? *In a system like BwE usage may not represent demand, as flows get throttled at the TCP socket
Usage data sampling
	Get daily statistical representative.
	Level the daily data across the time range of study.
	Historical data is required for a representative range of time. Outliers n the data must be filters out.
	
Future projections are based on uniform multipliers by consumer or application. 
Consumer level forecasts are more robust than service due to spill over economic effects 


\subsection{Event based}


\begin{equation}
\label{replication_time}
F_l = f(src, dst)_a  
\end{equation}

\begin{equation}
\label{replication_time}
D_{l_i} = \sum{src_i * dst_j}
\end{equation}

\begin{center}
\begin{small}
$
\begin{array}{rcl}
 D   &=& demand        \\
 F   &=& flow        \\
 _l  &=& language    \\
 _i  &=& ith source    \\
 _j  &=& jth source    \\
 src &=& source      \\
 dst &=& destination \\
 a   &=& arc/{} between/ src and dst\\
\end{array}$
\end{small}
\end{center}


In this section, the Wikipedia traffic is correlated with data replication network demands. The spikes in Russian queries and the more pronounced English queries are seen around August 2016. Which does raise an interesting political connotation to the Trump election campaign. Regardless of the election coincidence, the Wikimedia Foundation attributes the anomaly to bugs in Chrome 41 and Windows 10/7 that inflated the Homepage statistics. 

With the ojective to determine the network requirements, the number of page views is converted to network flow rates first. The method used in this work determines the page size based on language. The language based sizes are upper bounded by Wikipedia's limit per page of 2048 kilobytes. Files about a subject that exceed this maximum value are split into multiple pages leading to a wider distribution of pages sizes \cite{wiki_size}. 

The size distribution of Wikipedia articles is not readily avaiable. Several resources were consulted to determined the page size \cite{wiki_avg_article, wiki_stats,xtools}. The page size is determined as noted in Table \ref{bytes_page}. Wikipedia Statistics site provided an incomplete set of data for the languages of interest \cite{wiki_stats}. In the Table the average English article consists of 640 words \cite{wiki_avg_article}. Aplhabetic characters translate to 1 Byte of data. As an example, English words have an average length of 8.23 characters by equality they are 8.23 Bytes long. The values obtained in Table \ref{bytes_page} were compared with the historical trends from \cite{wiki_stats}. The historical trend is shown in Figure \ref{art_size}. These values are spot checked for a small sample of articles at Xtools, a site for Wikipedia meta data \cite{xtools}. 

\begin{table}[htbp]
\caption{Typical byte of C language data types \cite{Bryant}}
\begin{center}
\begin{tabular}{llccc}
\hline\hline
\multicolumn{2}{c}{C declaration}  &{}&\multicolumn{2}{c}{Bytes}\\
\cline{1-2}
\cline{4-5}
Signed          &        Unsigned  &{}&  32-bit &  64-bit \\
\hline
 [signed]char   &  unsigned short  &{}&     1   &       1 \\
       short    &  unsigned short  &{}&     2   &       2 \\
          int   &        unsigned  &{}&     4   &       4 \\
         long   &        unsigned  &{}&     4   &       8 \\
       int32\_t &        uint32\_t &{}&     4   &       4 \\
       int64\_t &        uint64\_t &{}&     8   &       8 \\
         char*  &                  &{}&     4   &       8 \\
         float  &                  &{}&     4   &       4 \\
        double  &                  &{}&     8   &       8 \\
\hline
\end{tabular}
\label{Clang}
\end{center}
\end{table}

\begin{table}[htbp]
\caption{Languages to Page Size Classification}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
   &  Count &   Language &      Word &   Words/ &     Bytes/ &      Bytes/  \\
ID &        &            &    length &     page &  character &   page (ave) \\
\hline
zh &  17229 &   Mandarin &      1.00 &     1032 &          2 &         2064 \\
fr &  17802 &     French &     10.09 &      640 &          1 &         6457 \\
en &  24108 &    English &      8.23 &      640 &          1 &         5267 \\
ru &  15022 &    Russian &      9.97 &      640 &          1 &         6380 \\
de &  18547 &     German &     11.66 &      640 &          1 &         7462 \\
ja &  20431 &   Japanese &      1.00 &     1600 &          2 &         3200 \\
es &  14069 &    Spanish &      8.80 &      640 &          1 &         5632 \\
\hline
\end{tabular}
\label{bytes_page}
\end{center}
\end{table}

\begin{figure}[htbp]
\centering
\includegraphics[scale=.4]{art_size.png}
\caption{Wikipedia Article Sizes in Bytes. Source \cite{wiki_stats}}
\label{art_size}
\end{figure}

We can now sum up the packet counts also. The IP packets can be transmitted in 64k-Bytes sizes, however due to limitations of hardware the maximum size of packets are limited to be as low as 1500 Bytes\cite{Tanenbaum}. Packets also carry some overhead that don't scale with packet size, so net payload is lower. 

%ARIMA - Autoreggressive Integrated Moving Average
% Not suitable for long period seasonality
% Capacity planning needs hourly view, aggregation is not allowed

%Use seasonal index --> forecast the average per day of future with ARIMA --> use season index to forecast per hour

%Regression analysis is targetted for estaimating relationships among variables. Independent variable is time, dependent variable is traffic rate. 

%ACF - Autocorrection Function (ARIMA Model) 
%% def pearson_correlation(x, y):
   	 %return np.mean((x - x.mean()) * (y - y.mean())) / (x.std() * y.std())

% Time series consist of 3 components X_t = T_t + S_t + R_t. T_t : trend component gradual shift (organic). S_t : seasonal component (repeating patterns). R_t = random effect

%latency can be factored in basd on processing rates and ingress traffic.


\subsection{Power Allocation Method}

The power allocation method is an extension of the Gravity Model as proposed for capacity planning Internet backbone traffic in \cite{Gravity}. Strength of the interaction ($S$) between two cities is proportional to the product of their populations ($P$) divided by the distance between them squared ($d$), See equation \ref{Gravity_city}. It has been proven accurate for estimating telephone traffic exchange between area codes. 

\begin{equation}
\label{Gravity_city}
S = \frac{P}{d^2}
\end{equation}

Data-center capacity is typically measured in terms of nominal power supported by the facility \cite{wsc}. For performance, power translates linearly to the computational capability of the system for a given set of hardware architecture. Here nominal power values are considered in a network flow directed graph, where the data-centers are the nodes (vertices) and the network communication link between two nodes are edges (arcs) of the graph. The rest of this section describes a power allocation method for establishing node and edge weights.

Consider the network of Wikipedia data-centers listed in Table \ref{wiki_dc}. The caching sites consists of front-end services,  they only store fresh or the most popular copies of data for the local user base (see Figure \ref{world} and \ref{ingress_lang}). The data is presumed to be read only at the cache sites, and all writes are done in the primary application site. 

The average power use for each of Wikipedia's data-centers is shown in Table \ref{power_dist}. The power sums to 232-kW for all the data-centers. Notice that EQIAD constitutes 56\% of the total power since all data is processed at there. This is meaningful for network topology in that all data not cached locally at the ingress data-centers are sourced there. This drives the demand for sufficient bandwidth between EQIAD and all other sites for reads. Additional write traffic has not been accounted for in the Kaggle data-set, it will be factored in as a multiplier based on the the language specific corpus growth rates for this time period.

\begin{table}[htbp]
\caption{Power Distribution of DCs}
\begin{center}
\begin{tabular}{lcc}
\hline
{} &  avg\_power\_(kW) & fraction\_power \\
\hline
EQSIN &              10 &           0.04 \\
ULSFO &               5 &           0.02 \\
EQDFW &               0 &           0.00 \\
CODFW &              77 &           0.33 \\
EQORD &               0 &           0.00 \\
EQIAD &             130 &           0.56 \\
ESAMS &              10 &           0.04 \\
KNAMS &               0 &           0.00 \\
\hline
\end{tabular}
\label{power_dist}
\end{center}
\end{table}

Total average power of the data-center network. 

\begin{equation}
P_{T}=\sum{P_{dc_i}}\label{eq:total_power}
\end{equation}

\begin{equation}
p_{dc_i}=\frac{P_{dc_i}}{\sum{P_{dc_i}}} \Rightarrow \frac{P_{dc_i}}{P_{T}}\label{eq:percentage}
\end{equation}

\begin{equation}
BW_{T}=\sum{BW_{l_i}}\label{eq:total_network}
\end{equation}

\begin{equation}
bw_{l_i}=\Big(\frac{P_{dc_a} + P_{dc_z}}{P_{T}}\Big){BW_{T}} \\
 \Rightarrow \big(p_{dc_a}+p_{dc_a}\big)P_T \cdot BW_T \label{eq:link_percentage}
\end{equation}


Math consider total system power - 

  
Classes of Network QoS

Since nominal power represents a specific set of hardware architecture, the link requirement may change as the hardware evolves.

In the public domain, only the average power values have been found for Wikipedia's data-centers. To apply the power attribution method, power and traffic are considered to have a linear correlation. In this work mean traffic values are used as the controlled variable, where average power is the control variable. 

The size of the data table differ. tables with mean data were 8.6 KB and 95\% quantile  data were 28.6 KB
 
 
 
\section{Discussion}

The memory allocation of the data tables differ by more than 3 times. For example the dataframe with mean data was 8.6 KB and dataframe with 95\% quantile data was 28.6 KB for the ingress traffic series. However negligible trade-off is shown with time complexity. Time complexity is a metric that provides the relative execution time of an algorithm.   


\begin{table}[htbp]
\caption{Qualitative Evaluation Matrix}
\begin{center}
\begin{tabular}{l|l|l|l}
\textbf{Model}        &  \textbf{View}   &\textbf{Objective}    & \textbf{Use Case}\\
	\hline\hline
\textbf{Historical}   &   Non-Markovian  & Conservative         & Organic          \\
                      &                  &                      & Growth           \\
\textbf{Transaction } &   Fine Grained   & Precision            & Inorganic        \\
                      &                  &                      & Growth           \\
\textbf{Power}        &   Coarse         & Long Term            & Physical         \\
                      &                  & Stability            & Expansion        \\
                      
\end{tabular}
\label{qualitative_comps}
\end{center}
\end{table}

\section{Conclusion}

Temporal stability
Long Term Scale
Random Samples

\section{Future Work}
This work sets the foundations for an environmental footprint of global scale data center networks by establishing the logical dependencies between distributed facilities. The power demands of the Wikipedia data centers are negligible compared to the hyperscale, content rich services such as search engines and social media. However, the methodology presented here can scale to fit the hyperscale sites.

Each node has a a environmental vector. The values in the connection matrix indicate the degree of connection between two sites, where degree is the dependency for a pair of sites. With this approach, the redundancy and communications overheads head can be fully captured. 

\begin{table}[htbp]
\caption{Weighted Environmental Vector Matrix}
\begin{center}
\begin{tabular}{p{1cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}|p{0.3cm}}
{}    & \rothead[c]{EQIAD}& \rothead[c]{ESAMS} & \rothead[c]{EQORD} & \rothead[c]{KNAMS} & \rothead[c]{CODFW} & \rothead[c]{ULSF} & \rothead[c]{EQSIN} & \rothead[c]{EQDFW} \\
\hline
EQIAD &     - &     2 &     1 &     1 &     3 &     - &     - &     - \\ \hline
ESAMS &     2 &     - &     - &     1 &     - &     - &     - &     - \\ \hline
EQORD &     1 &     - &     - &     - &     1 &     1 &     - &     - \\ \hline
KNAMS &     1 &     1 &     - &     - &     - &     - &     - &     - \\ \hline
CODFW &     3 &     - &     1 &     - &     - &     1 &     1 &     1 \\ \hline
ULSFO &     - &     - &     1 &     - &     1 &     - &     1 &     1 \\ \hline
EQSIN &     - &     - &     - &     - &     1 &     1 &     - &     - \\ \hline
EQDFW &     - &     - &     - &     - &     1 &     1 &     - &     - \\ 

\end{tabular}
\label{X}
\end{center}
\end{table}



\begin{thebibliography}{00}

\bibitem{Abadi} <NAME>, "Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story," in Computer, vol. 45, no., pp. 37-42, 2012. 
doi:10.1109/MC.2012.33

\bibitem{bigtable}<NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME>, 2006. Bigtable: A Distributed Storage System for Structured Data  Google Inc

\bibitem{Bryant}<NAME> and <NAME>, Computer Systems: A Programeers Perspective. Pearson 2015 ISBN: 978-93-325-7390-1

\bibitem{CAP} <NAME> and <NAME>. 2002. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33, 2 (June 2002), 51-59. DOI: https://doi-org.proxy.library.cmu.edu/10.1145/564585.564601

\bibitem{Cassandra}<NAME>, <NAME>, <NAME>, 'A Queueing Network Model for Performance Prediction of Apache Cassandra', VALUETOOLS'16 proceedings of the 10th EAI International Conference on Performance Evaluation Methodologies and Tools on 10th EAI International Conference on Performance Evaluation Methodologies and Tools, Pages 186-193 

\bibitem{capital}Haskel, Jonathan; Westlake, Stian. 2018 Capitalism without Capital - The Rise of the Intangible Economy, Princeton University Press. 

\bibitem{Dynamo} <NAME>, <NAME>, <NAME>, <NAME>,  <NAME>, <NAME>, <NAME>, <NAME>  and <NAME>, 'Dynamo: Amazon’s Highly Available Key-value Store',SIGOPS Oper. Syst. Rev., vol. 41, no. 6, pp. 205-220, December 2007.

\bibitem{Dean} <NAME>, "Designs, Lessons and Advice from Building Large Distributed Systems", url: http://iepg.org/iepg/2009-11-ietf76/dean-keynote-ladis2009.pdf, 2009, Accessed 01/18/2019

\bibitem{Gravity} <NAME>, <NAME>, xperience in Measuring Backbone Traffic Variability: Models, Metrics, Measurements and Meaning, 2002 ACM, W'02, Nov. 6-8, 2002, Marseille, France

\bibitem{GFS}<NAME> and <NAME>, 'GFS: Evolution on Fast-forward', Commun. ACM, vol. 53, no. 10, pp. 42-49, March 2010.

\bibitem{Harchol-Balter} Mor Harchol-Balter Performance Modeling and Design of Computer Systems: Queueing Theory in Action, Cambridge University Press, 978-1-107-02750-3, 2013

\bibitem{JMT}M.Bertoli, G.Casale, G.Serazzi.
JMT: performance engineering tools for system modeling.
ACM SIGMETRICS Performance Evaluation Review, Volume 36 Issue 4, New York, US, March 2009, 10-15, ACM press

\bibitem{megastore} <NAME>, <NAME>, <NAME>, 2011. 'Megastore: Providing Scalable, Highly Avail{Harchol-Balter}able Storage for Interactive Services', 5
th Biennial Conference on Innovative Data Systems Research

\bibitem{Mongo}MongoDB, 'MongoDB Multi-Data Center Deployments A MongoDB Whitepaper', November 2017, url:$http://s3.amazonaws.com/info-mongodb-com/MongoDB_Multi_Data_Center.pdf$, accessed 1/25/2019

\bibitem{raft} <NAME> and <NAME>, In Search of an Understandable Consensus Algorithm
(Extended Version), Stanford University, 2014

\bibitem{scc} <NAME>, <NAME>, <NAME>, <NAME>. 'scc: Cluster Storage Provisioning Informed by Application Characteristics and SLAs', FAST'12 10th USENIX Conference on File and Storage Technologies, 2012

\bibitem{Spanner} <NAME>, <NAME>, <NAME>, et.al, 'Spanner: Google’s Globally Distributed Database' ACM Trans. Comput. Syst., vol. 31, ACM New York: Academic, August 2013, pp. 8:1--8:22.

\bibitem{Spanner_nam3} Google Cloud Platform, \\
https:\/\/cloud.google.com\/spanner\/docs\/instances\#available-configurations-multi-region,
accessed 1/30/2018

\bibitem{Tanenbaum}Tanenbaum, <NAME>. and Wetherall, <NAME>., 'Computer Networks 5th ed.', 2010, isbn = {0132126958, 9780132126953},
publisher = Prentice Hall Press, address = Upper Saddle River, NJ, USA

\bibitem{we_traffic}Kaggle: Web Traffic Time Series Forecasting, Forecast Future traffic to Wikipedia Pages, url:https://www.kaggle.com/c/web-traffic-time-series-forecasting (Accessed 12/09/2018)

\bibitem{wiki_avg_article}https://en.wikipedia.org/wiki/Wikipedia:Size\_comparisons, (Accessed 12/22/2018)

\bibitem{wiki_articles }https://en.wikipedia.org/wiki/Wikipedia:Size\_of\_Wikipedia, (Accessed 12/22/2018)

\bibitem{wiki_dash} Wikipedia Analytics 
https://analytics.wikimedia.org/dashboards/vital-signs/\#projects=eswiki,itwiki,enwiki,jawiki,dewiki,ruwiki,frwiki/metrics =Pageviews, (Accessed 12/22/2018)

\bibitem{wiki_network} Wikimedia servers https://wikitech.wikimedia.org/wiki/Network\_design, (Accessed 12/21/2018)

\bibitem{wiki_servers} Wikimedia servers https://meta.wikimedia.org/wiki/Wikimedia\_servers, (Accessed 12/20/2018) 

\bibitem{wiki_size} https://www.mediawiki.org/wiki/Manual:\$wgMaxArticleSize, (Accessed 12/22/2018)

\bibitem{wiki_stats} Wikipedia Statistics - Bytes per Article https://stats.wikimedia.org/EN/TablesArticlesBytesPerArticle.htm, (Accessed 12/30/2018)

\bibitem{xtools} Xtools, https://xtools.wmflabs.org/articleinfo, (Accessed 12/30/2018)

\bibitem{wsc}<NAME>, <NAME>, and <NAME>, 2018. The Datacenter as a Computer: Designing Warehouse-Scale Machines, Third Edition, Morgan \& Claypool Publishers. https://www.morganclaypool.com/doi/pdf/10.2200/  S00874ED3V01Y201809CAC046

\bibitem{Zhang}<NAME> et.al, "Guaranteeing Deadlines for Inter-DataCenter Transfers", IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 25, NO. 1, FEBRUARY 2017

\bibitem{Zhuang} <NAME>, <NAME> et al, Capacity Planning and Headroom Analysis for Taming Database Replication Latency- Experiences with LinkedIn Internet Traffic, ICPE’15, Jan. 31–Feb. 4, 2015, Austin, Texas, USA

\end{thebibliography}
\vspace{12pt}
\color{blue}
Eric is a Product Area Network Manager for Google Product Infrastructure at Google Inc. He provides WAN capacity planning and management for Search, Photos, Chrome, Geo-Local, Hardware, and Mobile Products along with a long tail of other services. He is also a self funded Doctors of Professional Practice Candidate at Carnegie Mellon University's School of Architecture with a focus on sustainability of internet scale data-center infrastructure. His research curiosity is driven by the systems inter-actions that are enabling the connected world.

\end{document}
