115-441 Computer NetworkingLecture 27 – Research DirectionsOutline• Transport2• Wireless• ProbingAreas• Router interactions• FQ, RED Æ Blue, CHOKe, CSFQ, XCP…• Small buffer routers• New congestion control designs• Delay based (Vegas)3y(g)• 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)Single TCP FlowRouter with large enough buffers for full link utilization4Summary Buffered LinkWMinimum window for full utilizationBuffer5t• With sufficient buffering we achieve full link utilization• The window is always above the critical threshold• Buffer absorbs changes in window size• Buffer Size = Height of TCP Sawtooth• Minimum buffer size needed is 2T*C• This is the origin of the rule-of-thumbExample• 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.6q• 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?2If flows are synchronizedmax2W∑maxW∑maxW7• Aggregate window has same dynamics• Therefore buffer occupancy has same dynamics• Rule-of-thumb still holds.2maxWtIf flows are not synchronizedB0∑W8ProbabilityDistributionBuffer SizeDelay Tolerant Networks:Motivation• Rural area (buses, mail trucks, infostations)• Mobile routers w/disconnection (e.g., ZebraNet)• Sensor networks (e.g., Data mules)•Deep spaceDeep 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 abstraction•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•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 predictable3Two 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 probability Illustration3331 2 32 2124Erasure 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•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 Rliti()Source only New contact r first contactsReplication(r)History (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)4Evaluation 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 distanceSummaryOverheadFloodingHRAverage-case DelayDirectHRECSRBig 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 assumptionsOpposite of usual assumptionsfor example, made by Mobile IP, HIP, I3, PCMP etc.Low cost, high reliability, and secureNeed to share resources without compromising integrityDesign PrinciplesLower costs by sharingStore and forward self-describing dataSeparate locationing and addressingSeparate locationing and addressingUse all links, opportunistically, if necessarySeparate data and control planeProxies for legacy supportReplication for reliability5Architecture overview Outline• Transport26• Wireless• ProbingCommon Case in the Future
View Full Document
Unlocking...