DOC PREVIEW
CMU CS 15744 - Lecture

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Making Friends with BroadcastAdministriviaFeedback FeedbackBack to Ad Hoc Networks1) “Hop-over” overhearing2) Bidirectional ReceptionExORWhy ExOR might increase throughput (1)Why ExOR might increase throughput (2)Design ChoicePriority orderingExOR batchingExOR: 2x overall improvementExOR moves packets fartherExOR discussionBack to BidirectionalCoding with Bidirectional trafficBuilding it: COPEWhat packets to code??COPE-ingGain: Theory and PracticeQuirk: Coding+MAC gainCan We COPE With It?If time permitsCreditsMaking Friends with BroadcastCMU 15-744David AndersenAdministrivia•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•#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•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•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 C90%90%0 < p < 45%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 advantageA B C“packet”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 pathWhy 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 distancesrc dstN1 N2 N3 N475%50%N525%Slide Credit: Biswas & MorrisWhy 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 lossesN1src dstN2N3N425%25%25%25%100%100%100%100%Slide Credit: Biswas & MorrisDesign 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 packetPriority 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 headersrcN1N2N3dstN4Slide Credit: Biswas & MorrisExOR 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 batchsrcN3dstN4tx: 23tx: 57 -23  24tx:  8tx: 100rx: 23rx: 57rx: 88rx: 0rx: 0tx: 0tx:  9rx: 53rx: 85rx: 99rx: 40rx: 22N1N2Slide Credit: Biswas & MorrisExOR: 2x overall improvement •Median throughputs: 240 Kbits/sec for ExOR, 121 Kbits/sec for TraditionalThroughput (Kbits/sec)1.00.80.60.40.200 200 400 600 800Cumulative Fraction of Node PairsExORTraditionalSlide Credit: Biswas & MorrisExOR moves packets farther•ExOR average: 422 meters/transmission•Traditional Routing average: 205 meters/txFraction of Transmissions00.10.20.6ExORTraditional Routing0 100 200 300 400 500 600 700 800 900 1000Distance (meters)25% of ExOR transmissions58% of Traditional Routing transmissionsSlide Credit: Biswas & MorrisExOR 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 challengesBack 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•4 “hops” in 3 transmissions:A B CTime 1: Pkt A->BTime 2: Pkt C->BTime 3: (Pkt C->B XOR Pkt A->B)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 ETXWhat 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•1x2: C gets 2•1x3: C=3, A=1•1x3x4: ABDC3 41 31 4Wants to send:1 -> A2 -> C3 -> C4 -> DGain: 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


View Full Document

CMU CS 15744 - Lecture

Documents in this Course
Lecture

Lecture

10 pages

Lecture

Lecture

10 pages

Lecture

Lecture

45 pages

Lecture

Lecture

48 pages

Lecture

Lecture

19 pages

Lecture

Lecture

97 pages

Lecture

Lecture

39 pages

Lecture

Lecture

49 pages

Lecture

Lecture

33 pages

Lecture

Lecture

21 pages

Lecture

Lecture

52 pages

Problem

Problem

9 pages

Lecture

Lecture

6 pages

03-BGP

03-BGP

13 pages

Lecture

Lecture

42 pages

lecture

lecture

54 pages

lecture

lecture

21 pages

Lecture

Lecture

18 pages

Lecture

Lecture

18 pages

Lecture

Lecture

58 pages

lecture

lecture

17 pages

lecture

lecture

46 pages

Lecture

Lecture

72 pages

Lecture

Lecture

44 pages

Lecture

Lecture

13 pages

Lecture

Lecture

22 pages

Lecture

Lecture

48 pages

lecture

lecture

73 pages

17-DNS

17-DNS

52 pages

Lecture

Lecture

10 pages

lecture

lecture

53 pages

lecture

lecture

51 pages

Wireless

Wireless

27 pages

lecture

lecture

14 pages

lecture

lecture

18 pages

Lecture

Lecture

16 pages

Lecture

Lecture

14 pages

lecture

lecture

16 pages

Lecture

Lecture

16 pages

Lecture

Lecture

37 pages

Lecture

Lecture

44 pages

Lecture

Lecture

11 pages

Lecture

Lecture

61 pages

Multicast

Multicast

61 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

81 pages

Lecture

Lecture

9 pages

Lecture

Lecture

6 pages

Lecture

Lecture

63 pages

Lecture

Lecture

13 pages

Lecture

Lecture

63 pages

Lecture

Lecture

50 pages

lecture

lecture

35 pages

Lecture

Lecture

47 pages

Lecture

Lecture

29 pages

Lecture

Lecture

92 pages

Load more
Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?