Slide 1Growing traffic vs. network performanceScale link capacities by eliminating redundancyUniversal need to scale capacitiesIP layer RE using router packet cachesRE as a network service: Why?Implications example: Performance benefitsImplications example: New protocolsTalk outlineRedundancy in network traffic*Empirical study of REAnalysis approachRE algorithms: MODPRE algorithms: MAXPComparison of RE algorithmsComparison of RE algorithmsZipf-like distribution for chunk matchesCache sizeEmpirical study: SummarySmartRE: Effective router-level RE*Realizing RE as a network serviceHop-by-hop RE revisitedRE at the network edgeSmartRE: Motivating questionSmartRE: Key ideasCache constraintsCoordinated cachingProcessing constraintsCoordinating processingSmartRE systemIngress/Encoder AlgorithmInterior/Decoder AlgorithmCoordinating cachingNetwork-wide optimizationCache consistencyValid encodingsSlide 37Results: Performance benchmarksNetwork-wide benefits (ISPs)SmartRE: Other resultsSummary and future directionsRedundancy elimination as a network serviceAditya AkellaUW-MadisonGrowing traffic vs. network performanceNetwork traffic volumes growing rapidlyAnnual growth: overall (45%), enterprise (50%), data center (125%), mobile (125%)*Growing strain on installed capacity everywhereCore (Asian ISPs – 80-90% core utilization), enterprise access, data center, cellular, wireless…How to sustain robust network performance?* Interview with Cisco CEO, Aug 2007, Network worldEnterprisesEnterprises Mobile usersHome usersVideoData centersWeb contentOther svcs(backup)ISPcoreStrain on installed link capacitiesStrain on installed link capacities2EnterprisesEnterprisesScale link capacities by eliminating redundancy•Popular idea: duplicate suppression or redundancy elimination (RE)–Popular objects, partial content matches, backups, app headers–Effective capacity improves ~2X•Many approaches to RE–Application-layer caches–Protocol-independent redundancy elimination (RE)•Below app-layer•WAN accelerators, de-duplication–Content distribution, bittorrent•Point solutions apply to specific link, protocol, or appMobile usersHome usersVideoData centersWeb contentOther svcs(backup)Wan OptWan OptWan OptWan OptDedup/archivalDedup/archivalDedup/archivalDedup/archivalISP HTTPcacheISP HTTPcacheCDNCDN3Universal need to scale capacities4Wan OptWan OptWan OptWan OptDedup/archivalDedup/archivalDedup/archivalDedup/archivalISP HTTPcacheISP HTTPcacheNetwork RedundancyElimination ServiceNetwork RedundancyElimination ServicePoint solutions inadequatePoint solutions inadequateCandidate: RE as a primitive operation supported inherently in the networko RE the new narrow waist o Applies transparently to all links, flows (long/short), apps, unicast/multicast, protocolsCandidate: RE as a primitive operation supported inherently in the networko RE the new narrow waist o Applies transparently to all links, flows (long/short), apps, unicast/multicast, protocolsArchitectural support to address universal need to scale capacities? Architectural support to address universal need to scale capacities? BittorrentBittorrent✗ Point solutions:Little or no benefit in the core✗ Point solutions:Little or no benefit in the core ✗ Point solutions:Other links must re-implement specific RE mechanisms ✗ Point solutions:Other links must re-implement specific RE mechanisms ✗ Point solutions: Only benefit system/app attached ✗ Point solutions: Only benefit system/app attachedInternet2Internet2Packet cache at every routerPacket cache at every routerApply protocol-indep RE at the packet-level on network links IP-layer RE serviceApply protocol-indep RE at the packet-level on network links IP-layer RE service5WisconsinWisconsinBerkeleyBerkeleyCMUCMURouter upstream removes redundant bytesRouter downstream reconstructs full packetRouter upstream removes redundant bytesRouter downstream reconstructs full packetIP layer RE using router packet cachesLeverage rapidly declining storage/memory costsLeverage rapidly declining storage/memory costsRE as a network service: Why?•Improved performance everywhere even if partially enabled–Generalizes point deployments and app-specific approaches•Benefits all network end-points, applications, scales capacities universally–Benefits network core•Improved switching capacity, responsiveness to sudden overload•Other application domains: data centers, multi-hop wireless•Architectural benefits–Enables new protocols and apps•Min-entropy routing, RE-aware traffic engineering (intra- and inter-domain)•Anomaly detection, in-network spam filtering–Improves apps: need not worry about using network efficiently•App headers can be verbose better diagnostics•Controlling duplicate transmission in app-layer multicast is a non-issue6Internet2Internet27Network RE 12 pkts (ignoring tiny packets)Network RE 12 pkts (ignoring tiny packets)Without RE 18 pkts33% lowerWithout RE 18 pkts33% lowerWisconsinWisconsinBerkeleyBerkeleyCMUCMUGeneralizes pointdeploymentsGeneralizes pointdeploymentsBenefits the network: improves effective switching capacityBenefits the network: improves effective switching capacity62 packets62 packets32 packets32 packets32 packets32 packetsImplications example: Performance benefitsWisconsinWisconsinInternet2Internet28RE + routing 10 pktsRE + routing 10 pktsSimple RE 12 pktsSimple RE 12 pktsBerkeleyBerkeleyCMUCMU✓ Verbose control messages ✓ New video adaptation algorithms✓ Anomaly detectors ✓ Spam filtering ✓ Content distribution schemes✓ Verbose control messages ✓ New video adaptation algorithms✓ Anomaly detectors ✓ Spam filtering ✓ Content distribution schemes✓ Minimum-entropy routing✓ New, flexible traffic engineering mechanisms✓ Inter-domain protocols✓ Minimum-entropy routing✓ New, flexible traffic engineering mechanisms✓ Inter-domain protocolsImplications example: New protocolsTalk outline•Is there promise today? Empirical study of redundancy in network traffic–Extent, patterns–Implications for network RE•Is an IP-level RE service achievable today? Network-wide RE architecture–Getting RE to work on ISP routers•What next?Summary and future directions9Redundancy in network traffic*10*Joint work with: Ashok Anand, Chitra Muthukrishnan (UW-Madison)Ram Ramjee (MSR-India)Empirical study of RE•Upstream cache = content table +
View Full Document