15-441 Computer NetworkingOutlineAreasSingle TCP Flow Router with large enough buffers for full link utilizationExampleIf flows are synchronizedIf flows are not synchronizedDelay Tolerant Networks: MotivationInternet vs. DTNDTN Research IssuesRouting on Dynamic GraphsTwo Extremes: Flooding versus Direct ContactReplicationIllustrationErasure CodesSlide 17Summary: Forwarding AlgorithmsEvaluation MethodologySummaryBig PictureMechanical Backhaul*ChallengesArchitecture overviewSlide 26Common Case in the Future InternetTrends: Density & ManagementTrends: Growing Application DiversityTrends: Spectrum ScarcityNew DirectionsSlide 32Available BandwidthMeasurement TechniquesPacket Pair Probing: IntuitionPacket Pair Probing for Available BandwidthA Simple ExperimentEstimating the Available BandwidthAccuracyMeasurement TimeYes, but Where Is the Bottleneck?Recursive Packet Train (RPT)Transmission of RPTExample: 139.82.0.1Detecting the BottleneckBut Not So Fast15-441 Computer NetworkingLecture 27 – Research Directions2Outline•Transport•Wireless•Probing3Areas•Router interactions•FQ, RED Blue, CHOKe, CSFQ, XCP…•Small buffer routers•New congestion control designs•Delay based (Vegas)•Long-term TCP fair (TFRC)•Others: bionomial, BIC/CUBIC•Other issues•Large bandwidth-delay product networks•Delay Tolerant Networks (DTN)•Congestion control outside TCP (congestion controlled UDP, general congestion management)4Single TCP FlowRouter with large enough buffers for full link utilization6Example•10Gb/s linecard•Requires 300Mbytes of buffering.•Read and write 40 byte packet every 32ns.•Memory technologies•DRAM: require 4 devices, but too slow. •SRAM: require 80 devices, 1kW, $2000.•Problem gets harder at 40Gb/s•Hence RLDRAM, FCRAM, etc.•Rule-of-thumb makes sense for one flow•Typical backbone link has > 20,000 flows•Does the rule-of-thumb still hold?7If flows are synchronized•Aggregate window has same dynamics•Therefore buffer occupancy has same dynamics•Rule-of-thumb still holds.2maxWtmax2W�maxW�maxW8If flows are not synchronizedProbabilityDistributionB0Buffer SizeWDelay Tolerant Networks:Motivation•Rural area (buses, mail trucks, infostations)•Mobile routers w/disconnection (e.g., ZebraNet)•Sensor networks (e.g., Data mules)•Deep space•Underwater•…Internet vs. DTNUnstated Internet assumptions•Exist some end-to-end paths•End-to-end RTT is low•At most a few seconds, and typically less than 500 ms•Use retransmission for reliability•Packet switching is the right abstractionDTN characteristics•Contact connectivity is intermittent and hard to predict•May not exist e2e paths•Large delay (can be hours or even days!)•High link error and low capacity•Resource budget can limit transmissions•Different network architectures (e.g., TCP/IP won’t work)DTN Research Issues•Naming, addressing, location management•Routing on dynamic graphs•Scheduling•Security•Applications•Practical deployment issues •…Routing on Dynamic Graphs•DTN routing runs over a time-varying topology•Links come and go, sometimes predictably•Inputs•Time varying topologies (S, D, c(t), d(t))•Traffic demands, vertex buffer limits, mobility patterns•Goal: determine route and schedule to optimize some metric•E.g., delay, throughput, resource consumption•Consider two scenarios:•Nodes move randomly•Node movement is predictableTwo Extremes:Flooding versus Direct Contact•Flooding: each node forwards any non duplicated message to any other node it encounters•Pros: low delay•Cons: high transmission overhead•Direct contact: the source holds the data until it comes in contact with the destination•Pros: minimal resources•Cons: long delay•Can we do better?•Some degree of replication (obvious)•Replication + erasure codesReplication•Source sends r identical copies over the first r contacts•Relay nodes directly send to the destination•Improve by using history information:•Each node keeps track of the probability a given node will be able to deliver its message•It replicates to r highest ranked relays based on delivery probabilityIllustration232312341 2 3Erasure Codes•Rather than seeking particularly “good” contacts, we “split” messages and distribute to more contacts to increase chance of delivery•Same number of bytes flowing in the network, now in the form of coded blocks•Partial data arrival can be used to reconstruct the original message•Given a replication factor of r, (in theory) any 1/r code blocks received can be used to reconstruct original data•Potentially leverage more contacts opportunity reduce worse-case latency•Reduces “risk” due to outlier bad contactsErasure CodesMessage n blocksEncoding (to m blocks, where m > n)Split message blocks among r*k relaysDecoding (Require n+alpha blocks)Message n blocksSummary: Forwarding AlgorithmsAlgorithm Who When To whomFlood All nodes New contact All newDirect Source only Destination DestinationSimple Replication(r)Source only New contact r first contactsHistory (r) All nodes New contact r highest rankedErasure Coding (ec-r)Source only New contactkr (k>=1) first contacts (k is related to coding algorithm)Evaluation Methodology•Use a real-world mobility trace collected from the initial ZebraNet test deployment in Kenya, Africa, July, 2004•Only one node returned 32-hour uninterrupted movement data•Weather and waterproofing issues•Semi-synthetic group model•Statistics of turning angles and walking distanceSummaryAverage-case DelayOverheadDirectFloodingHRECSRBig Picture•Goal: bring Internet connectivity to rural areas•Approach: rural kiosks•150,000+ operational in India•Ministry of Info. Tech. plans to set up 100,000 more in next two years•Kiosks connectivityDial-upslow (28 kbps)flaky (due to harsh environment)Very Small Aperture Terminalexpensive (satellite link)spare parts are hard to getLong range WiFistill experimentalexpensive up front cost (for 18m tower)Mechanical Backhaul*A bus carrying a 802.11 access point(Daknet project)Picture from Daknet project*Term suggested by A.A. PenziasChallengesBoth ends of a ‘connection’ are not simultaneously presentCan’t use standard TCP/IP, DNS, SSLMostly disconnected, rarely connectedOpposite of usual assumptionsfor example, made by Mobile IP, HIP, I3, PCMP etc.Low cost, high reliability, and secureNeed to share resources without compromising
View Full Document
Unlocking...