DOC PREVIEW
CMU 15441 Computer Networking - Lecture

This preview shows page 1-2-3-4 out of 13 pages.

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

Unformatted text preview:

115-441 Computer NetworkingLecture 5 – EthernetBrainstorming• One of class goals: learning how to design systemssystems• Take a look at problem and come up with your own solutions first Æ look at actual designs later• Learn to appreciate solution tradeoffsLecture 7: 9-13-07 2pp• Build confidence in your skillsProblem 1 – Sharing a WireBhif h?Learned how to connect hosts• … But what if we want more hosts?SwitchesWires for everybody!Lecture 7: 9-13-07 3• Expensive! How can we share a wire?SwitchesWires for everybody!Problem 2 – Listen and Talkyak yak…• Natural scheme – listen before you talk…• Works well in practiceLecture 7: 9-13-07 4p2Problem 2 – Listen and Talkyada yada…• Natural scheme – listen before you talk…• Works well in practiceLecture 7: 9-13-07 5pProblem 2 – Listen and Talkyada yada…yak yak…• Natural scheme – listen before you talk…• Works well in practiceLecture 7: 9-13-07 6p• But sometimes breaks down• Why? How do we fix/prevent this?Prob. 3 – Who is this packet for?• Need to put an address on the packet• What should it look like?• How do you determine your own address?•How do you know what address you want toLecture 7: 9-13-07 7How do you know what address you want to send it to?Outline • Aloha• Ethernet MAC• CollisionsLecture 7: 9-13-07 8• Ethernet Frames• “Taking Turns” MAC and Other LANs3MAC Protocols: A TaxonomyThree broad classes:• Channel partitioning• Divide channel into smaller “pieces” (time slots, frequency)• Allocate piece to node for exclusive use• Random access• Allow collisions•“Recover”from collisionsLecture 7: 9-13-07 9•Recover from collisions• “Taking turns”• Tightly coordinate shared access to avoid collisionsGoal: efficient, fair, simple, decentralizedRandom Access Protocols• When node has packet to send• Transmit at full channel data rate RTransmit at full channel data rate R• No a priori coordination among nodes• Two or more transmitting nodes Æ “collision”• Random access MAC protocol specifies: • How to detect collisions• How to recover from collisions (e.g., via delayed tii)Lecture 7: 9-13-07 10retransmissions)• Examples of random access MAC protocols:• Slotted ALOHA• ALOHA• CSMA and CSMA/CDAloha – Basic Technique• First random MAC developed•For radio-based communication in Hawaii (1970)•For radio-based communication in Hawaii (1970)• Basic idea:• When you’re ready, transmit• Receiver’s send ACK for data• Detect collisions by timing out for ACK•Recover from collision by trying after random delayLecture 7: 9-13-07 11Recover from collision by trying after random delay• Too short Æ large number of collisions• Too long Æ underutilizationSlotted Aloha• Time is divided into equal size slots (= pkt trans. time)• Node (w/ packet) transmits at beginning of next slot (p ) g g• If collision: retransmit pkt in future slots with probability p, until successfulLecture 7: 9-13-07 12Success (S), Collision (C), Empty (E) slots4Pure (Unslotted) ALOHA• Unslotted Aloha: simpler, no synchronization• Pkt needs transmission:• Send without awaiting for beginning of slot• Collision probability increases:• Pkt sent at t0collide with other pkts sent in [t0-1, t0+1]Lecture 7: 9-13-07 13Outline • Aloha• Ethernet MAC• CollisionsLecture 7: 9-13-07 14• Ethernet Frames• “Taking Turns” MAC and Other LANsEthernet• First practical local area network, built at Xerox PARC in 70’s• “Dominant” LAN technology: • Cheap• Kept up with speed race: 10, 100, 1000 Mbps Lecture 7: 9-13-07 15Metcalfe’s EthernetsketchEthernet MAC – Carrier Sense• Basic idea:• Listen to wire before HiddEdste to e be o etransmission• Avoid collision with active transmission• Why didn’t ALOHA have this?•In wireless, relevantNYCMUSt.LouisChicagoCMUHiddenExposedLecture 7: 9-13-07 16In wireless, relevant contention at the receiver, not sender• Hidden terminal• Exposed terminalChicagoNY5Ethernet MAC – Collision Detection• Note: ALOHA has collision detection also, should really be called “Fast Collision Detection”y• Basic idea:• Listen while transmitting• If you notice interference Æ assume collision• Why didn’t ALOHA have this?• Very difficult for radios to listen and transmitLecture 7: 9-13-07 17• Signal strength is reduced by distance for radio• Much easier to hear “local, powerful” radio station than one in NY• You may not notice any “interference”Ethernet MAC (CSMA/CD)• Carrier Sense Multiple Access/Collision DetectionPacket?Sense CarrierDiscardSendDetect CollisionNoYesLecture 7: 9-13-07 18Discard PacketJam channel b=CalcBackoff(); wait(b);attempts++;attempts < 16attempts == 16Ethernet’s CSMA/CD (more)Jam Signal: make sure all other transmitters are aware of collision; 48 bits; ;;Exponential Backoff:• If deterministic delay after collision, collision will occur again in lockstep• Why not random delay with fixed mean?• Few senders Æ needless waitingLecture 7: 9-13-07 19• Too many senders Æ too many collisions• Goal: adapt retransmission attempts to estimated current load• heavy load: random wait will be longerEthernet Backoff Calculation• Exponentially increasing random delay•Infer senders from # of collisions•Infer senders from # of collisions• More senders Æ increase wait time• First collision: choose K from {0,1}; delay is K x 512 bit transmission times• After second collision: choose K from {0123}Lecture 7: 9-13-07 20{0,1,2,3}…• After ten or more collisions, choose K from {0,1,2,3,4,…,1023}6Outline • Aloha• Ethernet MAC• CollisionsLecture 7: 9-13-07 21• Ethernet Frames• “Taking Turns” MAC and Other LANsCollisionsABCTimeLecture 7: 9-13-07 22Minimum Packet Size• What if two people sentpeople sent really small packets• How do you find collision?Lecture 7: 9-13-07 23Ethernet Collision Detect• Min packet length > 2x max prop delayIf A B t it id f li k d B t t•If A, B are at opposite sides of link, and B starts one link prop delay after A• Jam network for 32-48 bits after collision, then stop sending• Ensures that everyone notices collisionLecture 7: 9-13-07 24y7End to End Delay• c in cable = 60% * c in vacuum = 1.8 x 10^8 m/s•Modern 10Mb Ethernet {•Modern 10Mb Ethernet {• 2.5km, 10Mbps • ~= 12.5us delay• +Introduced repeaters (max 5 segments)• Worst case – 51.2us round


View Full Document

CMU 15441 Computer Networking - Lecture

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

14 pages

Lecture

Lecture

78 pages

Lecture

Lecture

35 pages

Lecture

Lecture

4 pages

Lecture

Lecture

4 pages

Lecture

Lecture

29 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

44 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

13 pages

Lecture

Lecture

47 pages

Lecture

Lecture

49 pages

Lecture

Lecture

7 pages

Lecture

Lecture

18 pages

Lecture

Lecture

15 pages

Lecture

Lecture

74 pages

Lecture

Lecture

35 pages

Lecture

Lecture

17 pages

lecture

lecture

13 pages

Lecture

Lecture

21 pages

Lecture

Lecture

14 pages

Lecture

Lecture

53 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Lecture

Lecture

10 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

lecture

lecture

11 pages

lecture

lecture

7 pages

Lecture

Lecture

10 pages

lecture

lecture

46 pages

lecture

lecture

7 pages

Lecture

Lecture

8 pages

lecture

lecture

55 pages

lecture

lecture

45 pages

lecture

lecture

47 pages

lecture

lecture

39 pages

lecture

lecture

33 pages

lecture

lecture

38 pages

lecture

lecture

9 pages

midterm

midterm

16 pages

Lecture

Lecture

39 pages

Lecture

Lecture

14 pages

Lecture

Lecture

46 pages

Lecture

Lecture

8 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

9 pages

Lab

Lab

3 pages

Lecture

Lecture

53 pages

Lecture

Lecture

51 pages

Lecture

Lecture

38 pages

Lecture

Lecture

42 pages

Lecture

Lecture

49 pages

Lecture

Lecture

63 pages

Lecture

Lecture

7 pages

Lecture

Lecture

51 pages

Lecture

Lecture

35 pages

Lecture

Lecture

29 pages

Lecture

Lecture

65 pages

Lecture

Lecture

47 pages

Lecture

Lecture

41 pages

Lecture

Lecture

41 pages

Lecture

Lecture

32 pages

Lecture

Lecture

35 pages

Lecture

Lecture

15 pages

Lecture

Lecture

52 pages

Lecture

Lecture

16 pages

Lecture

Lecture

4 pages

lecture

lecture

27 pages

lecture04

lecture04

46 pages

Lecture

Lecture

46 pages

Lecture

Lecture

13 pages

lecture

lecture

41 pages

lecture

lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

Lecture

Lecture

38 pages

lecture

lecture

11 pages

Lecture

Lecture

42 pages

Lecture

Lecture

12 pages

Lecture

Lecture

36 pages

Lecture

Lecture

46 pages

Lecture

Lecture

35 pages

Lecture

Lecture

34 pages

Lecture

Lecture

9 pages

lecture

lecture

49 pages

class03

class03

39 pages

Lecture

Lecture

8 pages

Lecture 8

Lecture 8

42 pages

Lecture

Lecture

20 pages

lecture

lecture

29 pages

Lecture

Lecture

9 pages

lecture

lecture

46 pages

Lecture

Lecture

12 pages

Lecture

Lecture

24 pages

Lecture

Lecture

41 pages

Lecture

Lecture

37 pages

lecture

lecture

59 pages

Lecture

Lecture

47 pages

Lecture

Lecture

34 pages

Lecture

Lecture

38 pages

Lecture

Lecture

28 pages

Exam

Exam

17 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

9 pages

Project

Project

20 pages

Lecture

Lecture

40 pages

L13b_Exam

L13b_Exam

17 pages

Lecture

Lecture

48 pages

Lecture

Lecture

10 pages

Lecture

Lecture

52 pages

21-p2p

21-p2p

16 pages

lecture

lecture

77 pages

Lecture

Lecture

18 pages

Lecture

Lecture

62 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

Project

Project

20 pages

Lecture

Lecture

47 pages

Lecture

Lecture

38 pages

Lecture

Lecture

35 pages

Roundup

Roundup

45 pages

Lecture

Lecture

47 pages

Lecture

Lecture

39 pages

Midterm

Midterm

22 pages

Project

Project

26 pages

Lecture

Lecture

11 pages

Project

Project

27 pages

Lecture

Lecture

10 pages

Lecture

Lecture

50 pages

Lab

Lab

9 pages

Lecture

Lecture

30 pages

Lecture

Lecture

6 pages

r05-ruby

r05-ruby

27 pages

Lecture

Lecture

8 pages

Lecture

Lecture

28 pages

Lecture

Lecture

30 pages

Project

Project

13 pages

Lecture

Lecture

11 pages

Lecture

Lecture

12 pages

Lecture

Lecture

48 pages

Lecture

Lecture

55 pages

Lecture

Lecture

36 pages

Lecture

Lecture

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