13 broadcast

Information about 13 broadcast

Published on December 23, 2007

Author: cooper

Source: authorstream.com

Content

Making Friends with Broadcast:  Making Friends with Broadcast CMU 15-744 David Andersen Administrivia:  Administrivia Midterm Mean 66.5, Median 70, Stddev 13.7 Histo: 35-39 37 38 40-44 45-49 50-54 54 54 54 55-59 56 57 60-64 61 64 64 65-69 69 70-74 71 73 73 73 75-79 75 76 76 79 80-84 83 85-89 86 90-95 90 Correlation with PS1 scores: 0.7 This is a grad class. Expect As and Bs in the “normal” curve (stddev) If outlier, might want to talk with dga. Feedback Feedback:  Feedback Feedback #1 complaint: Post lecture notes earlier Answer: Okay! Second popularity group: Req. security topics Yes! Already planned; if suggestions, drop me a note. Security overview (problems, causes, challenges, definitions, packet floods, SYN floods, botnets, some defenses) DDoS control and traceback Worms Slides are sometimes hard to understand Will work on that. Many of them are brand new this semester Less “un-important” topics Need to clarify my emphasis. Every topic so far is important either because of practical impact, or because it’s intellectually important in terms of methods or the things that came from it, or because it illustrates open problems But very true that not everything is practical.  Thank you for the feedback! Back to Ad Hoc Networks:  Back to Ad Hoc Networks Recall that Transmissions interfere with many nodes, which constrains capacity of ad hoc nets Multiple receivers hear every transmission Delivery is probabilistic b/c of multipath interference [Roofnet sigcomm2005] Today’s papers: Past the cutting edge of what’s commonly used in wireless nets Will they be? We’ll see. 1) “Hop-over” overhearing:  1) “Hop-over” overhearing Observation 1: Best ETX/ETT path may have “overhearing”: What does p look like? If p > 0, can we take advantage of it when overhearing happens instead of having it interfere with C’s ability to talk concurrently? A B C 90% 90% 0 < p < 45% 2) Bidirectional Reception:  2) Bidirectional Reception Observation 2: When you Tx in a line, both sides can hear you: If sending from A  B  C A hearing (BC) is unwanted interference But we can turn it to our advantage A B C “packet” ExOR:  ExOR Let’s take advantage of the first observation, with an extra twist: Packets may hop over in a line Or may hop “sideways” as well Want to use the best route even if it goes off the “expected” best path Why ExOR might increase throughput (1):  Why ExOR might increase throughput (1) Best traditional route over 50% hops: 3(1/0.5) = 6 tx Throughput  1/# transmissions ExOR exploits lucky long receptions: 4 transmissions Assumes probability falls off gradually with distance src dst N1 N2 N3 N4 75% 50% N5 25% Slide Credit: Biswas & Morris Why ExOR might increase throughput (2):  Why ExOR might increase throughput (2) Traditional routing: 1/0.25 + 1 = 5 tx ExOR: 1/(1 – (1 – 0.25)4) + 1 = 2.5 transmissions Assumes independent losses N1 src dst N2 N3 N4 25% 25% 25% 25% 100% 100% 100% 100% Slide Credit: Biswas & Morris Design Choice:  Design Choice ExOR makes routing decision after packets have been received Lets you decide route based upon actual success instead of probability Requires a way of communicating to other nodes who actually received packet Priority ordering:  Priority ordering Goal: nodes “closest” to the destination send first Sort by ETX metric to dst Nodes periodically flood ETX “link state” measurements Path ETX is weighted shortest path (Dijkstra’s algorithm) Source sorts, includes list in ExOR header src N1 N2 N3 dst N4 Slide Credit: Biswas & Morris ExOR batching:  ExOR batching Challenge: finding the closest node to have rx’d Send batches of packets for efficiency Node closest to the dst sends first Other nodes listen, send remaining packets in turn Repeat schedule until dst has whole batch src N3 dst N4 tx: 23 tx: 57 -23  24 tx:  8 tx: 100 tx: 0 tx:  9 N1 N2 Slide Credit: Biswas & Morris ExOR: 2x overall improvement :  ExOR: 2x overall improvement Median throughputs: 240 Kbits/sec for ExOR, 121 Kbits/sec for Traditional Throughput (Kbits/sec) 1.0 0.8 0.6 0.4 0.2 0 0 200 400 600 800 Cumulative Fraction of Node Pairs ExOR Traditional Slide Credit: Biswas & Morris ExOR moves packets farther:  ExOR moves packets farther ExOR average: 422 meters/transmission Traditional Routing average: 205 meters/tx Fraction of Transmissions 0 0.1 0.2 0.6 ExOR Traditional Routing 0 100 200 300 400 500 600 700 800 900 1000 Distance (meters) Slide Credit: Biswas & Morris ExOR discussion:  ExOR discussion 2x improvement: Awesome! The cost? Look at Figure 6 in the paper. What’s the range of RTTs from src->N24? Up to 3.5 seconds. Ouch! Batching: Requires many pkts from srcdst Increases delay Interacts very poorly with TCP. (Translation: probably slower!) Solution: Proxy at edge, custom transport protocol across wireless network Awesome performance and nice design, but some serious deployment challenges Back to Bidirectional:  Back to Bidirectional When you Tx in a line, both sides can hear you: How do we make this work for us? A B C “packet” Coding with Bidirectional traffic:  Coding with Bidirectional traffic 4 “hops” in 3 transmissions: A B C Time 1: Pkt A->B Time 2: Pkt C->B Time 3: (Pkt C->B XOR Pkt A->B) Building it: COPE:  Building it: COPE Opportunistic listening (common to ExOR) Nodes listen all the time to all Tx (n.b. – would consume more power; assumption here is that you really want throughput) Periodic “reception reports” Tells neighbors what it’s heard Usually piggybacked on data Can also guess about reception using ETX What packets to code??:  What packets to code?? Node has some packets in Tx queue Which of them should it XOR together? Goal: max # of real packets delivered S.t. each nexthop can decode the real packet Let’s walk through an example… COPE-ing:  COPE-ing 1x2: C gets 2 1x3: C=3, A=1 1x3x4:  A B D C 3 4 1 3 1 4 Wants to send: 1 -> A 2 -> C 3 -> C 4 -> D Gain: Theory and Practice:  Gain: Theory and Practice Depends on topology. An “X”: middle node can xor 4 packets Each edge sends once Middle sends once = 8 pkts in 5 tx = 1.6 gain Max: ~2 But Overhead, loss, etc. Quirk: Coding+MAC gain:  Quirk: Coding+MAC gain Consider A-B-C topology w/out COPE: middle must send 2x as many packets If MAC is “fair”, middle only gets 1/3 of transmit time So packets build up and get lost BUT: TCP prevents too much packet buildup So this is achievable with UDP flows Can We COPE With It?:  Can We COPE With It? Overall: With symmetric, same-size UDP flows, COPE gain very nice With symmetric TCP, maybe 30%, but: COPE works best in a highly-loaded network (increases capacity) TCP performs very poorly with high loss rates! Requires lots of work to get TCP to work well over cope Fundamental and cool results, but may also need custom transport protocols to really use Could be great for software/multimedia/etc., dist over mesh network… If time permits:  If time permits TCP performance and wireless discussion Interesting RTS/CTS positive notes in COPE paper Application of cope and ExOR RTS-id Credits:  Credits Several of the ExOR slides (the pretty ones) are from “Opportunistic Routing in Multi-hop Wireless Networks”, Sanjit Biswas and Robert Morris, talk at SIGCOMM 2005. Aside: The Roofnet guys have a startup, Meraki (http://meraki.net/), doing mesh networks. They make cool little low-power mesh radios that implement many of the things we’ve read about in class. Fun stuff.

Related presentations


Other presentations created by cooper

neil 6th
27. 09. 2007
0 views

neil 6th

tps quizzes chapter 4
10. 12. 2007
0 views

tps quizzes chapter 4

lesson4
15. 11. 2007
0 views

lesson4

Aztec Gods
20. 11. 2007
0 views

Aztec Gods

adolescent literature
29. 12. 2007
0 views

adolescent literature

PrimesSarahBonnell
30. 12. 2007
0 views

PrimesSarahBonnell

Sorghum PRH
31. 12. 2007
0 views

Sorghum PRH

Chapter 36
01. 01. 2008
0 views

Chapter 36

IGR
03. 01. 2008
0 views

IGR

Romeo and Juliet Act II Scene ii
03. 01. 2008
0 views

Romeo and Juliet Act II Scene ii

roboGames
04. 01. 2008
0 views

roboGames

Autonomous Presentation
07. 01. 2008
0 views

Autonomous Presentation

doc 19042001 pg2 Airec
07. 01. 2008
0 views

doc 19042001 pg2 Airec

Lecture 29 meteorites
02. 01. 2008
0 views

Lecture 29 meteorites

WWII Beginnings and Battles
28. 02. 2008
0 views

WWII Beginnings and Battles

36154629
03. 12. 2007
0 views

36154629

BioMalnutritionP1
04. 03. 2008
0 views

BioMalnutritionP1

ncd nutrition
06. 03. 2008
0 views

ncd nutrition

3510 IMG presentation
10. 03. 2008
0 views

3510 IMG presentation

Sherrard
14. 03. 2008
0 views

Sherrard

13 A1
18. 03. 2008
0 views

13 A1

Thorsten Mollmann
21. 03. 2008
0 views

Thorsten Mollmann

Light3
26. 03. 2008
0 views

Light3

01 Introduction v2
27. 03. 2008
0 views

01 Introduction v2

SYV Bohn
13. 04. 2008
0 views

SYV Bohn

Bismarck 1862 3
07. 12. 2007
0 views

Bismarck 1862 3

HGSS Chapter4 Epigenesis
04. 01. 2008
0 views

HGSS Chapter4 Epigenesis

giver
06. 11. 2007
0 views

giver

Shuttle Return2 Flight NASA
07. 11. 2007
0 views

Shuttle Return2 Flight NASA