CMPE 150 Introduction to Computer Networks Dr Chane L Fullmer chane cse ucsc edu Spring 2003 UCSC cmpe150 1 Class Information Class web site www soe ucsc edu classes cmpe150 Spring03 Class Newsgroup ucsc class cmpe150 TA Section Mondays 5 00PM Thurdays 10 00AM Spring 2003 Baskin White Boards area UCSC cmpe150 2 Optional Class Project Network programming project In lieu of taking final examination Goal Build an FTP client server from scratch Using C language Details on web page now Due by June 4th Spring 2003 UCSC cmpe150 3 Homework Assignments Homework assignment 2 Due by May 1 Spring 2003 UCSC cmpe150 4 CMPE 150 Introduction to Computer Networks LECTURE 4 Medium Access Control Part II Spring 2003 UCSC cmpe150 5 Throughput of ALOHA Protocol packet overlaps with start of packet from node i packet overlaps with end of packet from node i interfering frame node i frame time interfering frame t0 1 t0 1 t0 Node i s frame is vulnerable from any arrival in the time interval t0 1 t0 1 Highest throughput when we have one packet for each 2 packet time period Spring 2003 UCSC cmpe150 6 Slotted ALOHA The throughput of ALOHA can be improved by reducing the time a packet is vulnerable to interference from other packets Slotted ALOHA works in a slotted channel providing discrete time slots Stations can start transmitting only at the beginning of time slots The time synchronization needed for slotting is accomplished at the physical layer and some synchronization is required in many cases anyway Spring 2003 UCSC cmpe150 7 Slotted ALOHA Protocol Packet ready no yes Wait for start of next slot transmit delay packet transmission k times wait for a round trip time quantized in slots yes Spring 2003 positive ack UCSC no compute random backoff integer k cmpe150 8 Slotted ALOHA user i P NEW user j RET NEW time slot NEW sum time RET time collision NEW NEW I B time I B B I B Propagation delay is part of time slot only in terrestrial nets Spring 2003 UCSC cmpe150 9 Throughput of Slotted ALOHA The vulnerability period of a packet is a slot time i time Any arrivals in prior slot collide with packet i arrivals The probability that a node transmits in a given time slot is p and there are N users We then have N P pkt from any node succeeds p 1 p N 1 Np 1 p N 1 1 With G Np and taking the limit as N tends to infinity as we did before G S Ge We double the capacity of the channel because we reduce in half the vulnerability period of a packet Spring 2003 UCSC cmpe150 10 CSMA Carrier Sense Multiple Access The capacity of ALOHA or slotted ALOHA is limited by the large vulnerability period of a packet By listening before transmitting stations try to reduce the vulnerability period to one propagation delay This is the basis of CSMA Kleinrock and Tobagi UCLA 1975 Same assumptions made for ALOHA are made now for CSMA Spring 2003 UCSC cmpe150 11 CSMA Protocol Packet ready Channel Busy yes no Assume non persistent carrier sensing Requires a maximum propagation delay much smaller than packet lengths transmit delay packet transmission k times wait for a round trip time yes Spring 2003 positive ack no UCSC compute random backoff integer k cmpe150 12 CSMA Throughput A virtual secondary channel used to send ACKs reliable and in 0 time Same assumptions made for pure ALOHA analysis All stations are at one propagation delay from each other and that equals Peer to peer communication No base station or transponder Explicit feedback to sender Spring 2003 UCSC cmpe150 13 CSMA Protocol is critical P user i RET NEW time user j NEW sum RET time collision RET NEW NEW I B I B I B time I An interesting difference compared to ALOHA is that busy periods are bounded B P 2 Spring 2003 RET UCSC cmpe150 14 CSMA Throughput Because prop delay is much smaller than packet length slotted and pure CSMA have very similar performance When MAC protocol requires small prop delays we can use slotted version to predict performance of unslotted version Analytical Results 1 Reminder These results are only an upper bound on performance because we did not take into account the effect of ACKs sent from receivers Slotted CSMA 0 9 Pure CSMA 0 8 0 7 0 6 S Throughput 0 5 0 4 Slotted Aloha 0 3 Pure Aloha 0 2 0 1 Spring 2003 UCSC 0 3 10 10 2 10 1 10 0 cmpe150 1 10 Offered Load G 10 2 10 3 10 4 10 5 15 CSMA CD CSMA with Collision Detection CSMA improves on the performance of ALOHA tremendously The remaining limitation is that once a packet is sent feedback occurs a roundtrip time after the entire packet is transmitted The solution to improve on the performance of CSMA is to listen to the channel while a packet is being sent This is called collision detection R M Metcalfe and D R Boggs Ethernet Distributed Packet Switching for Local Computer Networks Comm ACM Vol 19 1976 Xerox PARC Spring 2003 UCSC cmpe150 16 CSMA CD Protocol Non persistent transmission strategy Collision detection serves as a NACK Packet ready Channel busy Assumption are All stations hear one yes delay packet transmission k times no another Propagation delay is much smaller than packets transmit no compute random backoff integer k Collision detected yes send jamming signal abort transmission Spring 2003 UCSC cmpe150 Station listens to channel while transmitting Collision is detected when signals sent and heard differ Jamming signal sent to ensure all stations know of the collision 17 CSMA CD collision detection Spring 2003 UCSC cmpe150 18 Throughput of CSMA CD Same assumptions as with CSMA Jamming signal lasts J sec packets last P sec and propagation delay tau is much smaller than P first packet starts D first interfering packet starts C C starts hearing D aborts its packet and jams J D starts hearing C aborts its packet and jams D C NEW Z time J collision interval C 3 J Spring 2003 P idle period idle period 1 I 1 1 q N UCSC cmpe150 successful packet P 19 Throughput of CSMA CD Notes The average length of a collision interval is much smaller than in CSMA because J P This length is determined by the time between the first packet in the busy period and the first packet that interferes in contrast in CSMA it is the last interfering packet that counts A packet is successful with probability PS P one station xmits in and others do not in 2 Nq 1 q 2 N 1 For P we can approximate B Ps P 1 Ps J 3 The utilization period is only that portion of a packet transmission that has no overhead that is U P Ps Spring 2003 UCSC cmpe150 20 Throughput of CSMA CD Formula for throughput Throughput S Utilization U Busy Idle
View Full Document
Unlocking...