1A-2F-BB-76-09-AD 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 71-65-F7-2B-08-53 LAN (wired or wireless) 1!Ch5: Link Layer and LAN!! 5.1 Introduction and services!! 5.2 Error detection and correction !! 5.3 Multiple access protocols!! 5.4 Link-Layer Addressing!! 5.5 Ethernet!! 5.6 Hubs and switches!! 5.7 PPP!! 5.8 Link Virtualization: ATM!!LAN Inter-connect Multiple Access Control!! Why need control!" single shared broadcast channel !" two or more simultaneous transmissions: collision!! Ideal solution!" If only one node sends: can send at full speed!" If more than one send: share fairly!" No central controller to coordinate transmission!! 3 broad classes of solutions:!1. Channel partitioning, no collision!2. Taking turns: coordinated access to avoid collision!3. Random Access: no coordination; detect and resolve collisions!CS118!2!(1) Channel Partitioning: TDMA, FDMA!! Assuming 6 transmitters sharing one channel; 1, 3, 4 are sending; 2, 5, 6 idle!CS118!3!1 3 4 1 3 4 6-slot frame Time-Division Multiple Access frequency bands time FDM cable Frequency-Division Multiple Access (2) “Taking Turns” MAC protocols!! On-demand channel allocation!! Polling: !" master node asks slave nodes to transmit in turn!" Concerns!# polling overhead!# Latency!# single point of failure "(master)!CS118!4!master slaves poll data data(2) “Taking Turns” MAC protocols!! Token passing!" One token message passed thru nodes sequentially!" whoever gets the token can send one data frame before passing token to next node!! Concerns:!" latency!" single point of failure (token)!! A master station generates the token and monitors its circulation!" If token is lost, generate a new one!# How long does the master have to wait before declaring token is lost?!CS118!5!T data (nothing to send) T (3) Random Access protocols!! When node has packet to send!" transmit at full channel data rate R.!" no a priori coordination among nodes!! two or more nodes transmitting at the same time "--> collision!! random access MAC protocol specifies: !" how to detect collisions!" how to recover from collisions !! Examples of random access MAC protocols:!" ALOHA!" slotted ALOHA!" CSMA, CSMA/CD, CSMA/CA!CS118!6!ALOHA History!! Developed by Norm Abramson at the Univ. of Hawaii in 1970!" The world's first wireless packet-switched network!! Why ALOHA!" mountainous islands → wire-based network infeasible !" Radio communication → high error rate → centralized control infeasible!! Upload channel: contention-based random access!! Download channel: rebroadcasting all received packets!CS118!7!ALOHA!! If a node has data to send, send the whole frame immediately!" If collision: retransmits the frame again with the probability p!! collision probability: assume all frames of same size, frame sent at t0 may collide with other frames sent in [t0-1, t0+1]!CS118!8!probability of a successful transmision!CS118!9!P(success by a given node) = P(node transmits) $ P(no other node transmits in [t0-1,t0] $ P(no other node transmits in [t0,t0+1] = p $ (1-p)N-1 $ (1-p)N-1 P (success by any node) = N p . (1-p) 2(N-1) , choosing optimum p as n -> ! = 1/(2e) = 0.18 Assuming N nodes in the network: p = probability of a node transmitting Slotted Aloha!! Assumptions:!" Divide time into equal size slots (= frame transmission time) !" clocks in all nodes are synchronized!" If 2 or more nodes collide in one slot, all nodes detect collision!! Operations:!" Each node transmits only at beginning of next slot!" If no collision, node can send new frame in next slot!" If collision, retransmit in each subsequent slots with probability p, until succeed!CS118!10! S(uccess), C(ollision), E(mpty) slots Slotted Aloha efficiency!Q: what is the max fraction of successful slots?!" each node transmits in a slot with probability p!" prob. successful transmission S is!for a given node: S= p (1-p)(N-1)!by any of the N nodes: ! S = P(only one transmits)! = N p (1-p)(N-1), choosing optimal p as n!#! = 1/e = 0.37!CS118!11!throughput (success rate) G = offered load = N*p 0.5 1.0 1.5 2.0 0.1 0.2 0.3 0.4 Pure Aloha Slotted Aloha CSMA: Carrier Sense Multiple Access!! listen before transmit!! If channel sensed idle: transmit!! If channel sensed busy, wait until it becomes idle:!CS118!12!" 1-persistent CSMA: retry immediately!" p-persistent CSMA: retry immediately with probability p!" Non-persistent CSMA: retry after a random interval!! collisions still possible:!" two or more nodes may send simultaneously!" Chance of collision goes up with distance between nodes!To cut the loss early: CSMA/CD!CSMA/CD (Collision Detection) !! Collision Detection: compare transmitted with received signals!! Abort collided transmissions!CS118!13!saving No collision detection with collision detection Ethernet!! Dominant LAN technology till wireless showed up!! Kept up with speed race: 10 Mbps – 10 Gbps !! Bus topology popular through mid 90s!! Switch-based star topology prevailed as speed goes up!" Ethernet protocol runs on each wire!CS118!14!switch Bus topology Star topology Ethernet Frame Structure!! Sending adapter encapsulates IP datagram in Ethernet frame!! Preamble: 8bytes!" 7 bytes with pattern 10101010 followed by one byte with pattern 10101011!" used to synchronize receiver, sender clock rates!! Addresses: 6 bytes!" If received frame destination address matches NIC address, or is broadcast address, the adapter passes data to network layer protocol; otherwise, discards frame!! Type: 2 bytes !" indicates the higher layer protocol!" IEEE802.3 changed the “type” field to “length”, defined a separate type field carried in the data part!! CRC: 4 bytes checked at receiver, if error, drop the frame!CS118!15!46 – 1500 bytes Ethernet: Unreliable data delivery!! connectionless: No handshaking between sending and receiving NICs !! unreliable: receiving NIC doesn’t send acks or nacks to sending NIC!" stream of datagrams the receiving end passes to network layer can have gaps (missing datagrams)!! Ethernet’s MAC protocol:
View Full Document
Unlocking...