ECE544: Communication Networks-II, Spring 2006Today’s LectureShared Media NetworksEthernet OverviewEthernet (cont)Transmit AlgorithmAlgorithm (cont)CollisionsEthernet BridgingEthernet PerformanceToken Ring OverviewToken Ring (cont)Timed Token AlgorithmSlide 14Token MaintenanceMaintenance (cont)Wireless MACWireless LANsSpread SpectrumSpread Spectrum (cont)Collision AvoidanceRTS/CTS ProcedureSlide 23TDMA/TDD MACSupporting MobilityMobility (cont)Today’s HomeworkClass PresentationsECE544: Communication Networks-II, Spring 2006D. Raychaudhuri & Max OttLecture IIIncludes teaching materials from L. PetersonToday’s Lecture•Recap of network architecture & top-down design–architecture paper discussion•Shared media (MAC) protocols–Ethernet–Token ring–IEEE 802.11Shared Media NetworksCable (Ethernet)Token ring (FDDI)Wireless (802.11, DTDMA)Ethernet Overview•History–developed by Xerox PARC in mid-1970s–roots in Aloha packet-radio network–standardized by Xerox, DEC, and Intel in 1978–similar to IEEE 802.3 standard•CSMA/CD–carrier sense–multiple access–collision detection•Frame FormatDestaddr64 48 32CRCPreambleSrcaddrType Body1648Ethernet (cont)•Addresses–unique, 48-bit unicast address assigned to each adapter–example: 8:0:2b:e4:b1:2–broadcast: all 1s–multicast: first bit is 1•Bandwidth: 10Mbps, 100Mbps, 1Gbps•Length: 2500m (500m segments with 4 repeaters)•Problem: Distributed algorithm that provides fair accessTransmit Algorithm•If line is idle…–send immediately–upper bound message size of 1500 bytes–must wait 9.6us between back-to-back frames•If line is busy…–wait until idle and transmit immediately–called 1-persistent (special case of p-persistent)Algorithm (cont)•If collision…–jam for 32 bits, then stop transmitting frame–minimum frame is 64 bytes (header + 46 bytes of data)–delay and try again•1st time: 0 or 51.2us•2nd time: 0, 51.2, or 102.4us•3rd time51.2, 102.4, or 153.6us•nth time: k x 51.2us, for randomly selected k=0..2n - 1•give up after several tries (usually 16)•exponential backofCollisionsA BA BA BA BEthernet Bridging•Bridge device for scaling network spanBridgeEthernet AEthernet BPkt forwardingtable..can “learn”from packet source addrEthernet Performance•Max throughput <1 as a function of span–instability can occur unless load is reduced under congestion conditions–retransmission backof policy for stabilityOverloadregionNormal operatingpointCapacity Limit~0.8load linesOffered TrafficThruTrafficmarginstable policy(retx backoff)stable policy(backoff too high)unstable policy(no backoff)Token Ring Overview •Examples–16Mbps IEEE 802.5 (based on earlier IBM ring)–100Mbps Fiber Distributed Data Interface (FDDI)Token Ring (cont)•Idea–Frames flow in one direction: upstream to downstream –special bit pattern (token) rotates around ring–must capture token before transmitting–release token after done transmitting•immediate release•delayed release–remove your frame when it comes back around–stations get round-robin service•Frame FormatControl8 8 824CRCStart offrameEnd offrameDestaddrBody4848SrcaddrStatus32Timed Token Algorithm•Token Holding Time (THT)–upper limit on how long a station can hold the token•Token Rotation Time (TRT)–how long it takes the token to traverse the ring.–TRT <= ActiveNodes x THT + RingLatency•Target Token Rotation Time (TTRT)–agreed-upon upper bound on TRTAlgorithm (cont)•Each node measures TRT between successive tokens–if measured-TRT > TTRT: token is late so don’t send–if measured-TRT < TTRT: token is early so OK to send•Two classes of traffic–synchronous: can always send–asynchronous: can send only if token is early•Worse case: 2xTTRT between seeing token•Back-to-back 2xTTRT rotations not possibleToken Maintenance•Lost Token–no token when initializing ring–bit error corrupts token pattern–node holding token crashes•Generating a Token (and agreeing on TTRT)–execute when join ring or suspect a failure–send a claim frame that includes the node’s TTRT bid–when receive claim frame, update the bid and forward–if your claim frame makes it all the way around the ring:•your bid was the lowest•everyone knows TTRT•you insert new tokenMaintenance (cont)•Monitoring for a Valid Token–should periodically see valid transmission (frame or token)–maximum gap = ring latency + max frame < = 2.5ms–set timer at 2.5ms and send claim frame if it firesWireless MAC•Typically, three categories of radio MAC protocols :Simple packet-by-packet CSMA class protocols (802.11)Integrated packet/flow oriented protocols based on dynamic TDMA (Hiperlan, 802.16, ...)CDMA-based (HDR, 3G, etc.)Wireless LANs•IEEE 802.11a & b, Hiperlan2•Bandwidth: ~1-20 Mbps•Physical Media–spread spectrum radio (2.4, 5 GHz)–difused infrared (10m)Spread Spectrum•Idea–spread signal over wider frequency band than required–originally deigned to thwart jamming•Frequency Hopping–transmit over random sequence of frequencies–sender and receiver share…•pseudorandom number generator•seed–802.11 uses 79 x 1MHz-wide frequency bandsSpread Spectrum (cont)•Direct Sequence–for each bit, send XOR of that bit and n random bits–random sequence known to both sender and receiver –called n-bit chipping code –802.11 defines an 11-bit chipping codeRandom sequence: 0100101101011001Data stream: 1010XOR of the two: 1011101110101001000111Collision Avoidance•Similar to Ethernet•Problem: hidden and exposed nodesA B C DRTS/CTS Procedure•Sender transmits RequestToSend (RTS) frame•Receiver replies with ClearToSend (CTS) frame•Neighbors…–see CTS: keep quiet–see RTS but not CTS: ok to transmit•Receive sends ACK when has frame–neighbors silent until see ACK•Collisions–no collisions detection–known when don’t receive CTS–exponential backofRTS/CTS ProcedureRTSCTSlength (L)Data PacketACKLRTS collisionexponentialbackoffModempreambleTDM DownlinkFrame HeaderD-TDMA UplinkS-ALOHAcontrolUser BUser CTDMA Frame (~1-2 ms)Cell Sequence No.GFCVPIVPI VCIVCIVCIPTICLPHECStandard ATMPayload(48 bytes)CRC-16WATM CellBW Req/Alloc PktAP IdentifierTDMA Frame No.# Up contention slotsSuperframe size# Dn Control Slots# Dn data cellsReserved (8 Bytes)CRC-16# Slots Req/Start..Resvd/# Slots AllocTypeRSNMobile IDRT....SlotCRC-16# Data Cells# Control PktsReservedCRC-16Mobile IDUplink Subframe HeaderBurst from