WIXLIB

LIU2 LAYOUT.qxp Layout 1 7/17/14 1:49 PM Page 7ProjectBegintimeDepartmentGoal1000 GenomesProject1/2008National Institutes ofHealthTo produce an extensive public catalog of human genetic variation,including SNPs and structural variants, and their haplotype contexts.ARM Project3/2012Department of EnergyTo collect and process climate data from all over the world to understand Earth’s climate and come up with answers to climate changeissues.XDATA3/2012Defense AdvancedResearch Projects Agency(DARPA)To develop new computational techniques and software programsthat can analyze structured and unstructured big data sets faster andmore efficiently.BioSense 2.03/2012Center for Disease Controland PreventionTo track public health problems and make data instantly accessible toend users across government departments.The Open ScienceGrid3/2012National ScienceFoundation (NSF) andDepartment of EnergyTo provide advanced fabric of services for data transfer and analysis toscientists worldwide for collaboration in science discovery.Big Data for EarthSystem Science3/2012U.S. Geological SurveyTo provide scientists with state-of-the-art computing capabilities andcollaborative tools to make sense of huge data sets and better understand the earth.Human Brain Project2/2013European CommissionTo simulate the human brain and model everything that scientistsknow about the human mind using a supercomputer.Unique IdentificationAuthority2/2009The Indian PlanningCommissionTo create a biometric database of fingerprints, photographs, and irisscan images of all 1.2 billion people for efficient resident identification in welfare service delivery.Table 1. Representative government-funded big data projects.BigQuery, a big data service platform that enables customersto analyze their data by exploiting the elastic computingresources in Google’s cloud; SAP also released its in-memorybig data platform HANA, which is capable of processing largevolumes of structured and unstructured data in real time.In both government-funded research projects and businessoriented services, the life cycle of big data consists of multiplestages, as illustrated in Fig. 1. At first, the user data are generated from a variety of devices and locations, which are collected by wired and wireless networks. The data are thenaggregated and delivered to data centers via the global Internet. In data centers, the big data are processed and analyzed.Finally, the results are delivered back to users or devices ofinterest and utilized.Obviously, networks play a critical role in bridging the different stages, and there is a strong demand to create a fastand reliable interconnected network for the big data to flowfreely on this digital highway. This network highway concernsnot only just one segment of data delivery, but rather thewhole series of segments for the life cycle of big data, fromaccess networks to the Internet backbone, and to intra- andinter-data-center networks. For each layer of the network, thespecific requirements big data transmission poses should besatisfied.Access networks, which are directly connected to enddevices such as personal computers, mobile devices, sensors,and radio frequency identification (RFID) devices, lie in theouter layer. On one hand, such raw data from fixed or mobiledevices are transmitted into the network system; on the otherhand, processed big data and analytics results are sent back to7“The Zettabyte Era—Trends and Analysis,” Cisco Visual NetworkingIndex white paper, 2013.IEEE Network July/August 2014devices and their users. With the rapid development of wireless networks, more data are now collected from mobiledevices that have limited battery capacity. As such, energyefficient networking is expected to make batteries in mobiledevices more durable. Wireless links also suffer from interference, which results in unstable bandwidth provisioning. Bigdata applications such as cinematic-quality video streamingrequire sustained performance over a long duration to guarantee the quality of user experience, which has become a critical challenge for wireless networking.The Internet backbone serves as the intermediate layerthat connects access networks and data center networks. Popular big data applications like photo sharing and video sharing allow users to upload multimedia contents to data centersand share them with their friends in real time. To enablegood user experience, the Internet backbone needs to forward massive geologically distributed data to data centerswith high throughput, and deliver processed data to usersfrom data centers with low latency. As such, high-performance end-to-end links are required for uploading, and efficient content distribution networks (CDNs) are required fordownloading.Within a data center, big data are processed and analyzedwith distributed computing tools such as MapReduce andDryad, which involve intensive data shuffle among servers. Ascalable, ultra-fast, and blocking-free network is thus neededto interconnect the server nodes. Multiple geologically distributed data centers can be exploited for load balancing andlow-latency service provisioning, which calls for fast networking for data exchange, replication, and synchronization amongthe data centers. Moreover, inter-data-center links are leasedfrom Internet service providers (ISPs) or dedicatedly deployedby cloud providers with nontrivial costs. Effective data transmission and traffic engineering schemes (e.g., using software7

LIU2 LAYOUT.qxp Layout 1 7/17/14 1:49 PM Page 8defined networking, SDN) that fully utilize the capacity ofsuch links are therefore expected. For instance, Google andMicrosoft both attempt to deploy SDN-based global data center WANs to achieve fault tolerance, utilization improvement,and policy control that can hardly be realized by traditionalWAN architectures.In summary, to attain full speed for big data transmissionand processing, every segment of the network highway shouldbe optimized and seamlessly concatenated. We proceed toinvestigate each part of the network system by identifying theunique challenges that big data applications pose and analyzing the state-of-the-art works that endeavor to build the network highway for big data.Access Network: Linking SourcesWith the fast progress of digitalization and the developmentof sensor networks, huge amounts of data are collected by allkinds of end devices like PCs, smartphones, sensors, and GPSdevices. Meanwhile, applications like online social networksand video streaming push rich content big data into userdevices. The access network plays a critical role here in gathering such distributed data and forwarding them through theInternet to data centers. While the last mile problem has beenaddressed well with today’s high-speed home and office network connections, the wireless connection remains a severebottleneck. Cisco predicts that traffic from wireless andmobile devices will exceed traffic from wired devices by 2016,which makes wireless network performance optimization ofparamount importance.Wireless broadband technologies have evolved significantlyin recent years; but when facing data-intensive applications,they are still insufficient to satisfy the bandwidth requirements. Yoon et al. exploit the wireless broadcast advantageand use it to bridge the gap between wireless networkingcapacity and the bandwidth demands of video applications.MuVi [1], a multicast delivery scheme, is proposed to optimize video distribution. By prioritizing video frames accordingto their importance in video reconstruction and exploiting aresource allocation mechanism that maximizes the system utility, MuVi improves the overall video quality across all users ina multicast group.Multiple-input multiple-output orthogonal frequency-division multiplexig (MIMO-OFDM) technologies, which can significantly increase wireless capacity, have become the defaultbuilding blocks in the next generation of wireless networks.Liu et al. [2] observe that in wireless video streaming applications, both the video coding scheme and the MIMO-OFDMchannel present non-uniform energy distribution among theircorresponding components. Such non-uniform energy distribution in both the source and the channel can be exploitedfor fine-grained unequal error protection for video delivery inerror-prone wireless networks. To this end, ParCast, an optimized scheme for video delivery in MIMO-OFDM channels,is proposed. It separates the video coding and wireless channel into independent components and allocates more important video components with higher-gain channel components.This leads to significantly improved quality for video overwireless.In addition to the aforementioned works, there are severalother promising approaches to improve the quality of wireless video streaming services. On the user’s side, an application-aware MIMO video rate adaptation mechanism can bedeployed. It detects changes in a MIMO channel and adaptively selects an appropriate transmission profile, therebyimproving the quality of the delivered video. On the server’sside, standard base station schedulers work on a fine-grained8per-packet basis to decrease the delivery delay of singlepackets. However, it is insufficient to guarantee video watching experience at a coarse granularity, such as a fixed videobit rate over several seconds, which would typically consist ofvideo content in thousands of packets. In response, a videomanagement system, which schedules wireless video deliveryat a granularity of seconds with knowledge of long-termchannel states, has the potential to further improve userexperience. Moreover, distortion and delay, which are twoimportant user experience metrics, conflict with each otherin wireless networks. The optimal trade-off between distortion and delay in wireless video delivery systems largelydepends on the specific features of video flows. As such, apolicy that smartly balances distortion and delay accordingto the features of video flows can also improve user experience.Internet Backbone: From Local to RemoteBeyond the access network, the user or device generated datawill be forwarded through the Internet backbone to data centers. For example, in mobile cloud computing services [3],where powerful cloud resources are exploited to enhance theperformance of resource-constrained mobile devices, datafrom geologically distributed mobile devices are transmittedto the cloud for processing. Given that the local data comeworldwide, the aggregated data toward a data center can beenormous, which creates significant challenges to the Internetbackbone. Table 2 summarizes the Internet backbone solutions for big data.End-to-End TransmissionWith the growing capacity of access links, network bottlenecksare observed to be shifting from the network edges in accessnetworks to the core links in the Internet backbone. Toimprove the throughput of end-to-end data transmission, pathdiversity should be explored, which utilizes multiple pathsconcurrently to avoid individual bottlenecks. A representativeis mPath [4], which uses a large set of geographically distributed proxies to construct detour paths between end hosts. Anadditive increase and multiplicative decrease (AIMD) algorithm similar to TCP is used to deal with congested proxypaths to adaptively regulate the traffic over them, or evencompletely avoid them.Besides uploading, the big data, after being processedby the data centers, also need to be downloaded by usersto appreciate the inside value. Downloading, however,poses different demands. For applications like onlinesocial networks, it is critical to deliver user required contents with low latency while providing a consistent serviceto all users. Wittie et al. [5] reverse engineered Facebook,investigating the root causes of its poor performance whenserving users outside of the United States. They suggestthat this can be improved by exploring the locality of interest, which, with proxy and caching, can dramatically reducethe backbone traffic of such online social networks as wellas its access delay.Content Delivery NetworkFor geologically distributed data consumers, CDNs can beexplored to serve them with higher throughput. High throughput is typically achieved in two ways: optimizing path selection to avoid network bottlenecks, and increasing the numberof peering points. Yu et al. [6] introduce a simple model toillustrate and quantify the benefit of them. Using both synthetic and Internet network topologies, they show thatincreasing the number of peering points improves theIEEE Network July/August 2014

LIU2 LAYOUT.qxp Layout 1 7/17/14 1:49 PM Page 9Internet backboneApproachesNetworkinfrastructureBig dataapplicationGoalTechniqueEvaluation methodOverheadmPath leneckAIMD algorithmImplementation onPlanetLabProxy node deploymentWittie et al. ncyTCP proxy,cachingTrace-drivensimulationCache and proxydeploymentLiu et al. [7]CDNVideostreamingImproveQoSBit rateadaptionTrace-drivensimulationLow scalabilityJiang et al. [8]CDNVideostreamingReduceoperationalcostCDN extensionSynthetic andtrace-drivensimulationTrackerdeploymentIntra- and inter-data-center networksApproachesNetworkinfrastructureBig dataapplicationGoalTechniqueEvaluation methodOverheadHedera [9]Data tionFlowschedulingSimulation,implementation onPortland testbedCentralized control, lowscalabilityFlowComb [10]Data ationFlowschedulingImplementation onHadoop testbedMonitor and transferdemand informationOrchestra [11]Data centernetworksMapReduce/DryadReduce jobdurationTransferschedulingImplementation onAmazon EC2 andDETERlabModify the distributedframeworkRoPE [12]Data centernetworksMapReduce/DryadReduce jobdurationExecution planoptimizationImplementation onBing’s productionclusterPre-run jobs to acquirejob propertyCamdoop [13]Data ktrafficDataaggregationImplementation onCamCubeSpecial networktopology deploymentMordia [14]OCSdata , ware/topologydeployment3D Beamforming [15]Wirelessdata ioning60 GHzwireless linksLocal testbed,simulationPhysical antenna/reflector deploymentNetStitcher [16]Inter-datacenter linksData ndforwardalgorithmEmulation, livedeploymentPeriodical schedulerecomputationJetway [17]Inter-datacenter linksVideodeliveryMinimizelink on onAmazon EC2Centralized controller,video flow trackingTable 2. A taxonomy of Internet backbone, intra- and inter-data-center solutions for big data.throughput the most, while optimal path selection has onlylimited contribution. Liu et al. [7] further find that videodelivery optimized for low latency or high average throughputmay not work well for high-quality video delivery thatrequires sustained performance over a long duration. Thisleads to an adaptive design with global knowledge of networkand distribution of clients.IEEE Network July/August 2014To further reduce the operational cost of big data trafficover CDN, Jiang et al. [8] suggest that the CDN infrastructures can be extended to the edges of networks, leveragingsuch devices such as set-top boxes or broadband gateways.Their resources can be utilized through peer-to-peer communications with smart content placement and routing to mitigate the cross-traffic among ISPs.9

LIU2 LAYOUT.qxp Layout 1 7/17/14 1:49 PM Page 10Multi-rooted tree topologyData Center Networks: Where BigData Are Stored and ProcessedEqual-costPathBig data collected from end devices are storedand processed in data centers. Big data applicaData flowtions such as data analysis and deep learning usupredictionally exploit distributed frameworks likeIndividual.MapReduce and Dryad to achieve inflexibility. Data shufflingin MapReducedata flowand scalability. Data processing in those distributed frameworks consists of multiple computationalFigure 2. Data flow scheduling and data shuffling techniques in intra-datastages (e.g., map and reduce in the MapReducecenter networks.framework). Between the stages, massive amountsof data need to be shuffled and transferred amongservers. The servers usually communicate in anall-to-all manner, which requires high bisection bandwidth inRecently, optical circuit switching (OCS) has been suggestdata center networks. As such, data center networks oftened to accommodate the fast growing bandwidth demands inbecame a bottleneck for those applications, with data transdata center networks. The long circuit reconfiguration delayfers accounting for more than 33 percent of the running timeof OCSs, however, hinders their deployment in modern datain typical workloads. In Table 2, we summarize the state-ofcenters. To address this issue, Porter et al. [14] propose novelthe-art solutions toward engineering better intra- and intertraffic matrix scheduling (TMS), which leverages applicationdata-center networks.information and short-term demand estimates to computeshort-term circuit schedules, and proactively communicatesDynamic Flow Schedulingcircuit assignments to communicating entities. As such, it cansupport flow control in microseconds, pushing down theAs shown in Fig. 2, there are multiple equal-cost pathsreconfiguration time by two to three orders of magnitude. Onbetween any pair of servers in a typical multi-rooted treethe other hand, wireless links in the 60 GHz band are attractopology of a data center network. To better utilize the paths,tive to relieve hotspots in oversubscribed data center netHedera [9] is designed to dynamically forward flows alongworks. The 60 GHz wireless links require direct line of sightthese paths. It collects flow information from switches, combetween sender and receiver, which limits the effective rangeputes non-conflicting paths for flows, and instructs switches toof wireless links. Moreover, they can suffer from interferencereroute traffic accordingly. With a global view of routing andwhen nearby wireless links are working. To deal with these,traffic demands, Hedera is able to maximize the overall netZhou et al. [15] propose a new wireless primitive, 3D beamwork utilization with only small impact on data flows. Throughforming, for data centers. By bouncing wireless signals off themonitoring the flow information in switches, it schedules dataceiling, 3D beamforming avoids blocking obstacles, thusflows only after they cause congestion at certain location. Toextending the range of each wireless link. Moreover, the sigactually avoid congestion, however, the data flows should benal interference range is significantly reduced, allowing nearbydetected even before they occur. This is addressed in Flowlinks to work concurrently.Comb [10], which predicts data flows effectively by monitoringMapReduce applications on servers through software agents.Inter-Data-Center LinksA centralized decision engine is designed to collect data fromthe agents and record the network information.Big-data-based services such as social networks usually exploitseveral geographically distributed data centers for replicationTransfer Optimization in MapReduce-Like Frameworksand low-latency service provision. Those data centers areinterconnected by high-capacity links leased from ISPs. OperIn addition to scheduling individual flows, optimizing theations like data replication and synchronization require highentire data transfer has the potential to further reduce jobbandwidth transformation between data centers. It is thus critcompletion time. To this end, Orchestra [11] optimizes comical to improve the utilization or reduce the cost for suchmon communication patterns like shuffle and broadcast byinter-data-center links.coordinating data flows. When there are concurrent transfers,Laoutaris et al. [16] observe a diurnal pattern of userOrchestra enforces simple yet effective transfer schedulingdemand on inter-data-center bandwidth, which results in lowpolicies such as first-in first-out (FIFO) to reduce the averagebandwidth utilization in off-peak hours. They propose Nettransfer time. This is further enhanced in RoPE [12] by optiStitcher to utilize the leftover bandwidth in off-peak hours formizing job execution plans. An execution plan specifies thesuch non-real-time applications as backups and data migraexecution order of operations in a job, as well as the degree oftions. As illustrated in Fig. 3, NetStitcher exploits a store-andparallelism in each operation. RoPE em

Big Data: Architecture and Challenges Xiaomeng Yi, Fangming Liu, Jiangchuan Liu, and Hai Jin O Xiaomeng Yi, Fangming Liu, and Hai Jin are with the Services Computing Technology and System Lab, Cluster and Grid Computing Lab in the School of Com