DOC PREVIEW
CMU CS 15441 - lecture

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 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 19 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 19 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 19 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 19 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 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

• •• •115-441: Computer NetworkingLecture 22: Sensors and Ad-HocNetworksLecture 22: 04-05-05 2Scenarios and Roadmap• Point to point wireless networks• Example: Your laptop to CMU wireless• Challenges:• Poor and variable link quality (makes TCP unhappy)• Many people can hear when you talk• Pretty well defined.• Ad hoc networks (wireless++)• Rooftop networks (multi-hop, fixed position)• Mobile ad hoc networks• Adds challenges: routing, mobility• Some deployment + some research• Sensor networks (ad hoc++)• Scatter 100s of nodes in a field / bridge / etc.• Adds challenge: Serious resource constraints• Current, popular, research.• •• •2Lecture 22: 04-05-05 3Wireless Challenges (review)• Need to share airwaves rather than wire• Don’t know what hosts are involved• Host may not be using same link technology• No fixed topology of interconnection• Interference• Other hosts: collisions, capture, interference• The environment (e.g., microwaves + 802.11)• Mobility -> Things change often• Environmental changes do too• How do microwaves work? Relate to 802.11 absorption.• Other characteristics of wireless• Noisy  lots of losses• Slow• Multipath interferenceLecture 22: 04-05-05 4Wireless Bit-ErrorsRouterComputer 2Computer 12322Loss  Congestion210Loss  CongestionWireless• •• •3Lecture 22: 04-05-05 5TCP Problems Over Noisy Links• Wireless links are inherently error-prone• Fading, interference, attenuation -> Loss & errors• Errors often happen in bursts• TCP cannot distinguish between corruption andcongestion• TCP unnecessarily reduces window, resulting in lowthroughput and high latency• Burst losses often result in timeouts• What does fast retransmit need?• Sender retransmission is the only option• Inefficient use of bandwidthLecture 22: 04-05-05Performance Degradation0.0E+005.0E+051.0E+061.5E+062.0E+060 10 20 30 40 50 60Time (s)Sequence number (bytes)TCP Reno(280 Kbps)Best possible TCP with no errors(1.30 Mbps)2 MB wide-area TCP transfer over 2 Mbps Lucent WaveLAN• •• •4Lecture 22: 04-05-05 7Performance Degredation 2• Recall TCP throughput / loss / RTT rel:• BW = MSS / (rtt * sqrt(2p/3))• = proportional to 1 / rtt * sqrt(p)• == ouch!• Normal TCP operating range: < 2% lossInternet loss usually < 1%Lecture 22: 04-05-05 8Proposed Solutions• Incremental deployment• Solution should not require modifications to fixed hosts• If possible, avoid modifying mobile hosts• Reliable link-layer protocols• Error-correcting codes (or just send data twice)• Local retransmission• End-to-end protocols• Selective ACKs, Explicit loss notification• Split-connection protocols• Separate connections for wired path and wireless hop• •• •5Lecture 22: 04-05-05 9Approach Styles (Link Layer)• More aggressive local rexmit than TCP• 802.11 protocols all do this. Receiver sends ACK after last bit of data.• Faster; Bandwidth not wasted on wired links. Recover in a few milliseconds.• Possible adverse interactions with transport layer• Interactions with TCP retransmission• Large end-to-end round-trip time variation• Recall TCP RTO estimation. What does this do?• FEC used in some networks (e.g., 802.11a)• But does not work well with burst lossesWired link Wireless linkARQ/FECLecture 22: 04-05-05 10Approach Styles (End-to-End)• Improve TCP implementations• Not incrementally deployable• Improve loss recovery (SACK, NewReno)• Help it identify congestion• Explicit Loss/Congestion Notification (ELN, ECN),• ACKs include flag indicating wireless loss• Trick TCP into doing right thing  E.g. send extra dupacks if youknow the network just burped (e.g., if you moved)Wired link Wireless link• •• •6Lecture 22: 04-05-05 11Next: CSMA/CD Does Not Work• Recall Aloha frommany lectures ago• Wireless precursor toEthernet.• Carrier sense problems• Relevant contention atthe receiver, not sender• Hidden terminal• Exposed terminal• Collision detectionproblems• Hard to build a radio thatcan transmit and receiveat same timeABCABCDHidden ExposedLecture 22: 04-05-05 12RTS/CTS Approach• Before sending data, send Ready-to-Send (RTS)• Target responds with Clear-to-Send (CTS)• Others who hear CTS defer transmission• Packet length in RTS and CTS messages• Why not defer on RTS alone?• If CTS is not heard, or RTS collides• Retransmit RTS after binary exponential backoff• (There are lots of cool details embedded in this lastpart that went into the design of 802.11 - if you’recurious, look up the “MACAW” protocol).• •• •7Lecture 22: 04-05-05 13Ad Hoc Networks• All the challenges of wireless, plus some of:• No fixed infrastructure• Mobility (on short time scales)• Chaotically decentralized (:-)• Multi-hop!• Nodes are both traffic sources/sinks andforwarders• The big challenge: RoutingLecture 22: 04-05-05 14Ad Hoc Routing• Find multi-hop paths through network• Adapt to new routes and movement /environment changes• Deal with interference and power issues• Scale well with # of nodes• Localize effects of link changes• •• •8Lecture 22: 04-05-05 15Traditional Routing vs Ad Hoc• Traditional network:• Well-structured• ~O(N) nodes & links• All links work ~= well• Ad Hoc network• N^2 links - but many stink!• Topology may be really weird• Reflections & multipath cause strange interference• Change is frequentLecture 22: 04-05-05 16Problems using DV or LS• DV loops are very expensive• Wireless bandwidth << fiber bandwidth…• LS protocols have high overhead• N^2 links cause very high cost• Periodic updates waste power• Need fast, frequent convergence• •• •9Lecture 22: 04-05-05 17Proposed protocols• Destination-Sequenced Distance Vector (DSDV)• Dynamic Source Routing (DSR)• Ad Hoc On-Demand Distance Vector (AODV)• Let’s look at DSRLecture 22: 04-05-05 18DSR• Source routing• Intermediate nodes can be out of date• On-demand route discovery• Don’t need periodic route advertisements• (Design point: on-demand may be betteror worse depending on traffic patterns…)• •• •10Lecture 22: 04-05-05 19DSR Components• Route discovery• The mechanism by which a sending nodeobtains a route to destination• Route maintenance• The mechanism by which a sending nodedetects that the network topology has changedand its route to destination


View Full Document

CMU CS 15441 - lecture

Documents in this Course
lecture

lecture

34 pages

lecture

lecture

38 pages

lecture

lecture

18 pages

lecture

lecture

28 pages

lecture

lecture

11 pages

Lecture

Lecture

64 pages

lecture

lecture

10 pages

Lecture 6

Lecture 6

43 pages

Exam

Exam

14 pages

lecture

lecture

38 pages

Debugging

Debugging

23 pages

lecture

lecture

60 pages

review

review

27 pages

lecture

lecture

12 pages

The Web

The Web

28 pages

Lecture

Lecture

40 pages

lecture

lecture

42 pages

lecture

lecture

9 pages

lecture

lecture

10 pages

lecture

lecture

49 pages

lecture

lecture

26 pages

Project

Project

5 pages

lecture

lecture

40 pages

lecture

lecture

9 pages

lecture

lecture

41 pages

lecture

lecture

32 pages

lecture

lecture

36 pages

lecture

lecture

34 pages

lecture

lecture

45 pages

lecture

lecture

26 pages

lecture

lecture

6 pages

lecture

lecture

51 pages

Project

Project

16 pages

lecture

lecture

44 pages

lecture

lecture

13 pages

lecture

lecture

42 pages

lecture

lecture

36 pages

Project

Project

13 pages

Project

Project

33 pages

lecture

lecture

43 pages

lecture

lecture

49 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?