系统方法课件-chap2-1

1、Outline Nodes known as single mode fiber,Spring 2000,CS 461,18,Optical Fiber - Benefits,Greater capacity Data rates of hundreds of Gbps Smaller size stay at current signal to encode a zero solves the problem of consecutive ones Manchester transmit XOR of the NRZ encoded data and the clock only 50% e

2、fficient (bit rate = 1/2 baud rate),Spring 2000,CS 461,39,Encodings (cont),Spring 2000,CS 461,40,Encodings (cont),4B/5B(P83 T2.4) every 4 bits of data encoded in a 5-bit code 5-bit codes selected to have no more than one leading 0 and no more than two trailing 0s thus, never get more than three cons

3、ecutive 0s resulting 5-bit codes are transmitted using NRZI achieves 80% efficiency,Spring 2000,CS 461,41,Framing,Break sequence of bits into a frame Typically implemented by network adaptor,Spring 2000,CS 461,42,Frame Format, Source address - address of the sending station Destination address - add

4、ress of the receiving station Frame number - Each frame is numbered starting with 0. Typical Frame Format,Spring 2000,CS 461,43,Frame Format (cont.), ACK - An integer value designating the frame being acknowledged. It can be sent with data. Type of frame - data, ACK, NAK Data - the information being

5、 transmitted CRC - error checking bits,Spring 2000,CS 461,44,Error Detection,How do we detect a bit error? Simple technique: Send a copy of data in addition to the data. Compare copies at receiver. If different, then: Theres been an error Know the bit position of that error,Problems? Two errors in t

6、he same bit = cannot detect error, 0110 0110 - 0110 Error All error detection techniques can miss errors and therefore have a probability of error,Error Detection (2),Problems (cont.) Cant correct error Inefficient doubling of bandwidth P94 F2.19 A better error detection technique: checksum Achieves

7、 same/better prob. of error than copying the data with much less overhead just one field 010010 Start-of-Packet length checksum data Checksum is computed by binary addition of the packets contents The checksum can be computed over the data only, the header only (IP) or both (TCP) Can be located in h

8、eader or at end of packet,Spring 2000,CS 461,46,Error Detection (3),010010 Start-of-Packet length checksum data,If link-layer checksum is summed over the header only, how do we detect errors in data? Higher layer protocol can insert its own checksum What if there is a bit error in the checksum? Disc

9、ard the packet at the receiver Limitations of checksum: Cant tell position of bit error A bit error twice in the same offset position within the 16-bit segment will go undetected,Spring 2000,CS 461,47,Error Detection (4),The Internet checksum: Divide your data into 16-bit segments Add each of the 16

10、-bit segments, using ones complement binary addition, call it SUM1 Take the ones complement of SUM1, call it SUM2. Then SUM2 is your 16-bit IP checksum At receiver, take ones complement sum of entire header, including checksum. Should add to all ones if there are no errors. An alternative checksum:

11、XOR instead of ones complement Checksums are relatively weak compared to general error detection techniques but are easy to compute,P94,Spring 2000,CS 461,48,Error Detection (5),General technique: Add redundancy to the data in order to detect bit errors 010010 Start-of-Packet length err. det. data T

12、he error detection field can be computed over the data only, the header only (IP) or both (TCP) Can be located in header or at end of packet,The error detection field is also called a Cyclic Redundancy Check (CRC) Most link-layer protocols use CRCs for error detection, e.g. HDLC, PPP A checksum is a

13、 special case of a CRC where the CRC is computed using binary addition,Spring 2000,CS 461,49,Error Correction,Correct an error, rather than just detecting an error Simple technique: Send two copies of data in addition to the data, and then do majority logic decoding at the receiver,Problems? Ineffic

14、ient 2 errors in the same bit = cannot correct error, 0100 0110 0110 - 0110 Error,Spring 2000,CS 461,50,Error Correction (2),Forward Error Correction (FEC): Many types, e.g. Reed-Solomon coding on CDs Add K bits of redundancy to N bits, to form a (N+K)-bit long packet, or vector,N dimensions - N+K d

15、imensions 2N patterns or vectors mapped into 2N+K possibilities Spread out these vectors as far away from neighbors as possible in (N+K)-dimensional space N=2, K=3, N+K=5 Receive 01111 - closest to 11111, so decode “11” and correct one bit error,Spring 2000,CS 461,51,Reliable Protocols,Error detecti

16、on and error correction are not enough Receiver drops a packet when errors detected Receiver cant correct errors in some packets Receiver never receives a packet,Solution: Retransmit lost or corrupt packets Also called ARQ (Automatic-Repeat-Request) Protocols Useful for communicating non-delay-sensi

17、tive data, e.g. Web pages, files, email, even playback video Can incur too much delay for interactive audio/video,Spring 2000,CS 461,52,Reliable Protocols (2),How does sender know a packet has been received properly? Analogy: Send a package by mail. How do I know it got there? Certified mail sends b

18、ack a receipt. In reliable protocols, Acknowledgements are sent by receiver back to sender confirming receipt of a packet When an acknowledgment doesnt arrive, then retransmit,Sender,Receiver,Spring 2000,CS 461,53,Reliable Protocols (3),The communication channel can Lose packets (link layer and netw

19、ork layer) Delay packets (network layers) Reorder packets (network layers) Both the packet and the ACK can be lost,Sender,Receiver,Spring 2000,CS 461,54,Reliable Protocols (4),If the packet is lost, at what point does the protocol retransmit? After a timeout If the ACK is lost, at what point does th

20、e protocol retransmit? After the same timeout,Sender,Receiver,Spring 2000,CS 461,55,Reliable Protocols (5),How does receiver know that sender got its acknowledgment? Sender increments sequence number to #6 when acknowledgement #5 arrives. When receiver sees packet #6, it knows acknowledgement #5 mad

21、e it Sequence #s are also useful to send many packets at once,Sender,Receiver,Spring 2000,CS 461,56,Reliable Protocols Thus Far,To detect when a packet needs to be retransmitted, reliable/ARQ protocols must use both: Acknowledgements, and Timeouts, Sequence numbers: Sender labels packets with them F

22、or certain protocols, a receiver can infer correct reception of the acknowledgement for a packet with a lower sequence number,Spring 2000,CS 461,57,ACKs and NAKs,Types of Acknowledgments ACKs positive acknowledgements = “Ive received these packets” Cumulative Selective NAKs negative acknowledgements

23、 = “I have not received these packets” ACKs are more prevalent than NAKs,Sender,Receiver,#6,BACK,Spring 2000,CS 461,58,Timeouts,How would you choose the value of a timeout? If timeout is too long, then waste bandwidth and send slowly. “Too long” means timeout roundtrip time Lets approximate roundtri

24、p time RTT = 2*(propagation delay), “” means “much greater than” Example: if satellite link has prop. delay of 120 ms each way, then RTT = 240 ms. If timeout=1 min 240 ms, then send too slowly. If timeout is too short, then retransmit unnecessarily “Too short” means timeout roundtrip time Example: i

25、f timeout = 1 ms RTT = 240 ms, then retransmit unnecessarily Can have 2 or more copies of same packet in transit,BACK,Spring 2000,CS 461,59,Reliable Protocols: Other Points,Feedback loop allows receiver to send info about its state back to sender Which acknowledgements have been received Amount of r

26、oom in my receive buffer (flow control) Retransmission can work in conjunction with error detection/correction Each packet has CRC/checksum. At receiver, if calculated checksum doesnt match packets checksum, then discard packet. Alternative policy? Receiver caches noisy packet for future error corre

27、ction! Retransmission can occur both at link layer and transport layer,Spring 2000,CS 461,60,Designing Efficient Reliable Protocols,Already seen one way to improve efficiency: choose timeout wisely Another way to improve efficiency: “keep the pipe full” with new data packets and necessary retransmis

28、sions Stop-and-Wait Go-Back-N Selective Repeat (SRP),Spring 2000,CS 461,61,Unrestricted Protocol,The easiest protocol Assume the receiver either has an unlimited capacity to receive frames or processes them fast enough so that buffer space is always available The sender executes a loop repeatedly as

29、 long as there is information to send This approach does not consider any of damaged, lost, or delayed frames or to control the number of frames sent. It assumes every frame will arrive without damage and in the sent order.,Spring 2000,CS 461,62,Stop-and-Wait Protocol,After transmitting a packet/fra

30、me, the sender stops and waits for an ACK before transmitting the next frame If a timeout occurs before receiving an ACK, the sender retransmits the frame,Link layer RTT = send time + process time at receiver + ACK send time Here, timeout RTT,Spring 2000,CS 461,63,Stop-and-Wait Protocol (2),If a tim

31、eout occurs before receiving an ACK, the sender retransmits the frame.,time,Sender,Receiver,Frame,Frame,Ack,Timeout Period,OR,Spring 2000,CS 461,64,Stop-and-Wait Protocol (3),If a timeout occurs before receiving an ACK, the sender retransmits the frame.,time,Sender,Receiver,Frame,Frame,Ack,Timeout P

32、eriod,Spring 2000,CS 461,65,Stop-and-Wait Protocol (4),Want timeout = RTT to avoid spurious retransmissions of a frame/packet,time,Sender,Receiver,Frame,Frame,Ack,RTT,Ack,Unnecessary retransmission,Timeout,Spring 2000,CS 461,66,Stop-and-Wait Protocol (5),Label each packet and ACK with the proper seq

33、uence # to avoid confusion at receiver and sender,Sender,Receiver,Frame #1,ACK #1,Frame #2,ACK #2,Timeout Period,RTT,time,time,Spring 2000,CS 461,67,Problem with Stop-and-Wait,Only one outstanding packet at a time = waste of link bandwidth Example: 1.5 Mbps link with RTT 45 ms = a Delay*Bandwidth pr

34、oduct = 1.5Mbps*45ms=67.5 Kb 8 KB. “pipe size” If frame size = 1 KB, then use only 1/8 of bandwidth,Sender,Receiver,Frame #1,ACK #1,Frame #2,ACK #2,RTT,time,time,Spring 2000,CS 461,68,Protocol Efficiency, Channel Utilization: The percentage of time the channel is transferring data frames (i.e. not i

35、ncluding ACK frames) Effective Data Rate: The actual number of data bits (as opposed to the raw bit rate) sent per unit of time Parameters: R - transmission rate S - signal speed D - distance between sender and receiver T - time to create one frame F - number of bits in a data frame N - number of da

36、ta bits in a frame A - number of bits in an acknowledgment Time to send a frame to the receiver is T + F/R + D/S Time to send an acknowledgment to the sender is T + A/R + D/S,Spring 2000,CS 461,69,Protocol Efficiency (cont.), For Stop-and-Wait protocols The elapsed time between sending two consecuti

37、ve frames Stop and wait: (T+F/R+D/S) + (T+A/R+D/S) = 2(T+D/S) + (F+A)/R The channel utilization Stop and wait:100*(F/R)/(2(T+D/S)+(F+A)/R) Effective data rate Stop and wait: N/(2(T+D/S)+(F+A)/R),Spring 2000,CS 461,70,Example, Assumptions: R - 10 Mbps or 10 bits per sec S - 200 meters per sec D - 200

38、 meters T - 1 sec F - 200 bits N - 160 bits A - 40 bits,Spring 2000,CS 461,71,Example (cont.), The channel utilization Stop and wait: 100*(F/R)/(2(T+D/S)+(F+A)/R) = 71% Effective data rate Stop and wait N/(2(T+D/S)+(F+A)/R) = 5.7 Mbps,Spring 2000,CS 461,72,Designing Efficient Flow Control Protocols,

39、Already seen one way to improve efficiency: choose timeout wisely Another way to improve efficiency: “keep the pipe full” with new data packets and necessary retransmissions Go-Back-N Selective Repeat Protocol (SRP),Spring 2000,CS 461,73,Sliding Window,Allow multiple outstanding (un-ACKed) frames Up

40、per bound on un-ACKed frames, called window,Spring 2000,CS 461,74,“Keep the Pipe Full”,During one RTT, send N packets Example: 1.5 Mbps link with RTT 45 ms = a Delay*Bandwidth product = 67.5 Kb 8 KB. “pipe size” If frame size = 1 KB, and N=3, then can have 3 outstanding packets, 3/8 of BW, and tripl

41、e bandwidth utilization!,Sender,Receiver,RTT,time,time,Spring 2000,CS 461,75,Go-Back-N Sliding Window Protocol,Maintain a sliding window at both sender and receiver of unacknowledged packets Send Window Size (SWS) At sender: LAR (last ACK received), LFS (last frame sent),Sliding window: When ACK #(L

42、AR+2) arrives, slide LAR and LFS to right LFS LAR = SWS Retransmit entire window,LAR,LFS,SWS,Spring 2000,CS 461,76,Go-Back-N Sliding Window Protocol (2),At receiver: Maintain a Receive Window Size (RWS) At receiver: LAF (largest acceptable frame), LFR (last frame received),Sliding window: When frame

43、 arrives, keep it if its within window If frame #(LFR+1) arrives, then slide window to right (increment LFR and LAF) Send back Cumulative ACK = LFR+2, LAF LFR = RWS,LFR,LAF,RWS,Spring 2000,CS 461,77,Go-Back-N Sliding Window Protocol (3),Example: RWS = 4, LFR = 5, LAF = 9. Suppose at receiver frames

44、#7 and #8 arrive, but frames #6 or #9 either arrive out of order or are lost. When frame #7 arrives out of order, then send cumulative ACK with sequence #5 (same for frame #8) (alternative: delay ACKs until #6 arrives) When frame #6 arrives, slide window (LFR=8, LAF=12), and send cumulative ACK= #8.

45、,LFR=5,LAF=9,RWS=4,LFR=8,LAF=12,Spring 2000,CS 461,78,Go-Back-N Sliding Window Protocol (4),Meanwhile, back at the sender Example: suppose SWS=6, LAR=5, LFS=11 Each time sender gets a cumulative ACK of #5, it retransmits frame #6 through frame #11 When sender gets cumulative ACK #8, it slides window

46、 right (LAR=8, LFS=14), and transmits entire window (frame #9 thru #14),LAR=5,LFS=11,LAR=8,LFS=14,Spring 2000,CS 461,79,Problem with Go-Back-N,What problem do you see with cumulative ACKs? Cumulative ACKs cause unnecessary retransmissions = inefficient Some packets are retransmitted even though they

47、ve already arrived at receiver Solution: acknowledge each packet individually, or selectively, rather than cumulatively,Spring 2000,CS 461,80,Concurrent Logical Channels,Multiplex 8 logical channels over a single link Run stop-and-wait on each logical channel Maintain three state bits per channel He

48、ader: 3-bit channel num, 1-bit sequence num 4-bits total same as sliding window protocol,Spring 2000,CS 461,81,Gedankenexperiment,How does communication work in real life? If there are lots of speakers/speaking? If there is little speaking? If there are “important” people? Can we map this to compute

49、r networks?,Spring 2000,CS 461,82,Shared-Media or Broadcast Networks,N senders and receivers connected by a shared medium (copper wire, atmosphere, water) Shared local access to the same media Local Area Network (LAN) Ethernet, Fast Ethernet, Gigabit Ethernet, Wireless Ethernet, or 802.11 b/a, or Wi

50、Fi,Ethernet (802.3),802.11/Wireless Ethernet,Spring 2000,CS 461,83,Summary of MAC protocols,What do you do with a shared media? Channel Partitioning, by time, frequency or code TDMA, FDMA, CDMA Random partitioning (dynamic), ALOHA pure ALOHA, slotted ALOHA CSMA persistent, non-persistent, p-persiste

51、nt CSMA/CD used in Ethernet (ch2.6) CSMA/CA used in Wi-Fi (ch2.8) Taking Turns (ch2.7) polling from a central site, token passing,Spring 2000,CS 461,84,Code Division Multiple Access (CDMA),Use multiple orthogonal codes to partition a range of spectrum Also called “spread spectrum technique” Each hos

52、t sends using a pre-determined code Two forms spread spectrum: Direct-Sequence Spread Spectrum DSSS Chipping sequences spread the signals spectrum CDMA is often used as synonym for DSSS Examples: 802.11b, cell Frequency-hopping spread spectrum FHSS Example: Bluetooth Advantage: simple, but not as ef

53、ficient,Spring 2000,CS 461,85,Code Division Multiple Access (CDMA) (2),Frequency hopping example,Bluetooth,Host 1s Code: 1342, Host 2s Code: 3214, Host 3s Code: 4123 Note that all 3 codes are orthogonal: at each instant in time, each host is on a different frequency,Host 1,Host 2,Host 3,F1,F2,F3,Fre

54、q (Hz),F4,Spring 2000,CS 461,86,Random Access/MAC Protocols,Multiple users share the same frequency band and/or same time and/or same code Analogy: conversation in a crowded room What protocol steps do people use to talk in the same room (shared media)? Important factors: Wait for silence Then talk

55、Listen while talking. What do we do if theres 2 talkers? Backoff. Repeat,Spring 2000,CS 461,87,Random Access: ALOHA Protocol,Developed at University of Hawaii in 1971 by Abramson Ground-based UHF radios connect computers on several island campuses to main university computer on Oahu “pure” ALOHA: ho

56、sts transmit whenever they have information to send form of random access Collision will occur when two hosts try to transmit packets at the same time Hosts wait a timeout=1 RTT for an ACK. If no ACK by timeout, then wait a randomly selected delay to avoid repeated collisions, then retransmit,Spring

57、 2000,CS 461,88,Random Access: ALOHA Protocol (2),Collision of packets can occur when a packet overlaps another packet,time,T0,Collision,Collision,Wasted Time Colliding with B,Wasted Time Due to a Collision 1 packet intervals,Spring 2000,CS 461,89,Random Access: Slotted ALOHA,Rather than sending a p

58、acket at any time, send along time slot boundaries Collisions are confined to one time slot,time,T0,Collision,No Collision,Wasted Time Due to a Collision = 1 packet interval,Spring 2000,CS 461,90,Random Access: Slotted ALOHA (2),How do hosts synchronize to begin transmitting along time slot boundari

59、es? One central station transmits a synchronization pulse or beacon Slotted ALOHA is more efficient than ALOHA because when there is a collision, the wasted time is confined to one time slot Assuming Poisson packet arrivals (memoryless), can compute the maximum throughput of ALOHA to be 18%. Maximum throughput of Slotted ALOHA is 37% Why are ALOHA & slotted ALOHA so inefficient?,Sprin