DESIGN & IMPL COMP COM NETWK
DESIGN & IMPL COMP COM NETWK CDA 4506
University of Central Florida
Popular in Course
Popular in Computer Design Architecture
This 64 page Class Notes was uploaded by Genoveva Bogisich on Thursday October 22, 2015. The Class Notes belongs to CDA 4506 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 73 views. For similar materials see /class/227528/cda-4506-university-of-central-florida in Computer Design Architecture at University of Central Florida.
Reviews for DESIGN & IMPL COMP COM NETWK
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
CDA 4506 Design and Implementation of Data Communication Networks Lecture Set 2 Dr R Lent Chapter 5 outline 5 51 Introduction and l 56 HUbS bridges and services switches is 52 Error detection and W 57 Wireless links and LANs correction U 58 PPP L 53 Multiple access D 1 iii protocols l i l lquot 54 LAN addresses and ARP a 55 Ethernet Not an atypical LAN IP network WNW 1 a sewer ed1cated 11390 exhsmol 39 1 39 I Internet 39lIZZID Mbps Mail mm m Shared IUBuseT hub 39IIZIB seT hub 39 I i EmseT huh Egg g lquot h Elecrgicu l Enginaserir39g Campul er Science Sysrems Engimzering Chapter 5 The Data Link Layer Our goals understand principles behind data link layer services I error detection correction I sharing a broadcast channel multiple access I link layer addressing I reliable data transfer flow control Ch 3 I instantiation and implementation of various link layer technologies Layered Architecture Application SMTP FTP HTTP etc Transport TCP UDP Network IP ICMP Datagrams Link 2 PDU is often Ethernet WiFi PPP ATM 52ng Physical Frame Relay X25 datagram datalink layer has responsibility of transferring datagram from one node to adjacent node over a link Link layer context Datagram transferred by different link protocols over different links I eg Ethernet on first link frame relay on intermediate links 80211 on last link 1 Each link protocol provides different services I eg may or may not provide rdt over link transportation analogy l trip from Princeton to Lausanne I limo Princeton to JFK I plane JFKto Geneva I train Geneva to Lausanne tourist datagram transport segment communication link transportation mode link layer protocol travel agent routing algorithm Link Layer Services 1 Framing link access I encapsulate datagram into frame adding header trailer I channel access if shared medium I physical addresses used in frame headers to identify source dest different from IP address 2 Reliable delivery between adjacent nodes I seldom used on low bit error link fiber some twisted pair I wireless links high error rates Q why both linklevel and endend reliability Link Layer Services more 3 Flow Control I pacing between adjacent sending and receiving nodes 4 Error Detection I errors caused by signal attenuation noise I receiver detects presence of errors signals sender for retransmission or drops frame 5 Error Correction I receiver identifies and corrects bit errors without resorting to retransmission 6 Halfduplex or fullduplex I with half duplex nodes at both ends of link can transmit but not at same time Adaptors Communicating datagram rcving node link layer protocol sending A node K NIC NIC link layer implemented in a NIC network interface card I Ethernet card PCMCI card 80211 card sending side receiving side I looks for errors reliability flow control etc I extracts datagram passes to receiving node I encapsulates datagram In a adapter is semiautonomous frame link amp physical layers I adds error checking bits rdt flow control etc Chapter 5 outline 51 Introduction and services 56 Hubs bridges and 52 Error detection and SWitCheS correction 57 Wireless links and LANs L 53Multiple access protocols 58 PPP lquot 54 LAN addresses and ARP 11 59 ATM 55 Ethernet l 510 Frame Relay Error Detection EDC Error Detection and Correction bits redundancy D Data protected by error checking may include header elds Error detection not 100 reliable protocol may miss some errors but rarely larger EDC eld yields better detection and correction i39ldatagram Y gt detected error lt d data bits DI D EDC ll Parity Checking Single Bit Parity Two Dimensional Bit Parity Detect single bit errors Detect and correct single bit errors row arit parity lt ddata bits tlgit y d m dm d1j1 d21 39 39 39 d2j d2j1 I O111000110101011 OI columnl dij di j did1 parity di1 1 39 39 39 di lj di 1j l 10101 1 o 1 1 o oe parity error 01110 lelOlO no errors Parity error correctable single bit error Internet checksum Goal detect errors eg flipped bits in transmitted segment note used at transport layer only Sender Receiver compute checksum of received segment treat segment contents as sequence of 16bit integers check if computed checksum checksum addition 1 s equals checksum field value complement sum of segment contents I NO error detected sender puts checksum value I YES no error detected But into UDP checksum field maybe errors nonetheless More later Checksumming Cyclic Redundancy Check view data bits D as a binary number choose r1 bit pattern generator G goal choose r CRC bits R such that I ltDRgt exactly divisible by G modulo 2 I receiver knows G divides ltDRgt by G If nonzero remainder error detected I can detect all burst errors less than r1 bits widely used in practice ATM HDCL 4 d bits gtlt r bits r bit Ddata bits to be sentl R39CRC bits pattern D 2 r XOR R mathematical formula CRC Example Want D2r XOR R nG equivalently D2r nG XOR R equivalently if we divide D2r by G want remainder R R remainder l39 G 2 1 G 100 101011 01110000 D 1001 Chapter 5 outline i l 51 Introduction and services 56 Hubs bridges and o 52 Error detection and SWitCheS correction l 57 Wireless links and LANs D 53Multiple access protocols L 58 PPP 54 LAN addresses and ARP lquot 59 ATM l l 55 Ethernet I 510 Frame Relay U Multiple Access Links and Protocols Two types of links pointtopoint I PPP for dialup access I pointto point link between Ethernet switch and host broadcast shared wire or medium I traditional Ethernet I upstream HFC I 80211 wireless LAN 000 shared wire eg Ethernet XI Blah blah blah 9 U Q WW amok ZZZZZZZZZZZZZ Q Q Egg shared wireless eg Wavelan satellite cocktail party Multiple Access protocols single shared broadcast channel two or more simultaneous transmissions by nodes interference I only one node can send successfully at a time multiple access protocol distributed algorithm that determines how nodes share channel ie determine when node can transmit communication about channel sharing must use channel itself what to look for in multiple access protocols Ideal Multiple Access Protocol Broadcast channel of rate R bps 1 When one node wants to transmit it can send at rate R 2 When M nodes want to transmit each can send at average rate RM 3 Fully decentralized I no special node to coordinate transmissions I no synchronization of clocks slots 4 Simple MAC Protocols a taxonomy Three broad classes 39i Channel Partitioning I divide channel into smaller pieces time slots frequency code I allocate piece to node for exclusive use Random Access I channel not divided allow collisions I recover from collisions Taking turns I tightly coordinate shared access to avoid collisions Comparison of MAC protocols Channel partitioning MAC protocols I share channel efficiently and fairly at high load I inefficient at low load delay in channel access 1N bandwidth allocated even if only 1 active node Random access MAC protocols I efficient at low load single node can fully utilize channel I high load collision overhead Taking turns protocols look for best of both worlds Taking Turns MAC protocols Polling Token passing master node inViteSquot Slave control token passed from one node to nodes to transmit in turn next sequentially concerns token message I polling overhead l concerns I latency I token overhead I single point of failure I latency master I single point of failure token Channel Partitioning We ve studied TDMA and FDMA already CDMA Code Division Multiple Access unique code assigned to each user ie code set partitioning used mostly in wireless broadcast channels cellular satellite etc 1 all users share same frequency but each user has own chipping sequence ie code to encode data encoded signal original data X chipping sequence decoding innerproduct of encoded signal and chipping sequence allows multiple users to coexist and transmit simultaneously with minimal interference if codes are orthogonal CDMA EncodeDecode sender channel output 21m Z c data MT m b 1 0 1 1111 1 1 Its 111 1 111 1 1 1 1 slot 1 slot 0 COde 1 channel channel output output slot 1 slot 0 0 M d Z Cm I m1 1 111 11 1 1 GM 7111 1 111 39 a d1 4 Clo 1 slot 1 slot 0 received received input input receiver code1M1 1 1M1 1 11 1 1 111 CDMA twosender interference senders data 23m curlcn bits d 1 Q channeIZi m co e 39239 222 39239 H data 0 1 d31 2 bits code1111111111112VC2gt 22 1 i Zim d1 Cm M 1 H WI 2 222 2 2 1 321 M H H d d1 slot 1 slot 0 received received in ut in ut 39 p p receiver 1 11 1 1 1M1 1 COde 1114 1 1411 Random Access Protocols When node has packet to send I transmit at full channel data rate R I no a priori coordination among nodes two or more transmitting nodes gt collision random access MAC protocol specifies I how to detect collisions I how to recover from collisions eg via delayed retransmissions Examples of random access MAC protocols I slotted ALOHA I ALOHA I CSMA CSMACD CSMACA Slotted ALOHA Assumptions I Ogeration 7 81 frame am Slze when node obtains fresh frame it time IS diVided into equal size slots time to transmit 1 frame transm39ts 39n neXt SIOt nodes start to transmit frames ii no collision node can send new only at beginning of slots nodes are synchronized if colhsron node retransmits frame In if 2 or more nodes transmit in slot all nodes detect collision eaCh SUbsequent SIOt With PFOb l0 un lsuccess frame in next slot Slotted ALOHA I I I I I I I I I I I I I I I P 3390 I E C S E C E S 5 Pros Cons S39ngle aCt39Ve Ode can I collisions wasting slots continuously transmit at full rate I Idle slots of channel highly decentralized only slots 7 nodes may be able to detect collision in less than time to In nodes need to be In sync transmit packet Simple Slotted Aloha efficiency Efficiency is the longrun fraction of successful slots when there s many nodes each with many frames to send Suppose N nodes with many frames to send each transmits in slot with probability p prob that 1st node has success in a slot p1pN391 prob that any node has a success Np1pN1 For max efficiency with N nodes find p that maximizes Np1ION391 For many nodes take limit of Np1pN391 as N goes to infinity gives 1e 37 At best channel used for useful transmissions 37 of time Pure unslotted ALOHA x unslotted Aloha simpler no synchronization list when frame first arrives I transmit immediately ii collision probability increases I frame sent at t0 collides with other frames sent in to1t01 will overlap will overlap with start of with end of I lt i s frame i s frame Pure Aloha efficiency Psuccess by given node Pnode transmits Pno other node transmits in p01p0 Pno other node transmits in p01p0 IO1I0N3911PN391 p 1p2N391 Choosing optimum p and then letting n gt infty 12e 18 Even worse CSMA Carrier Sense Multiple Access CSMA listen before transmit 39 i If channel sensed idle transmit entire frame 1 If channel sensed busy defer transmission I Persistent CSMA retry immediately with probability p when channel becomes idle l Non persistent CSMA retry after a random time interval Human analogy don t interrupt others CSMA collisions spatial layout of nodes lt space gt collisions can still occur propagation delay means two nodes may not hear each other s transmission collision entire packet transmission time wasted lt time note 1 role of distance amp propagation delay in determining collision probability 2 Attenuation and distance Collision Detection CSMACD carrier sensing deferral as in CSMA I collisions detected within short time I colliding transmissions aborted reducing channel wastage collision detection I easy in wired LANs measure signal strengths compare transmitted received signals I difficult in wireless LANs receiver shut off while transmitting CD circuit operates by looking for voltage exceeding a transmitted voltage Want to ensure that a station does not complete transmission prior to 1st bit arriving at farthest away station Time to CD can thus take up to 2xmax prop delay CSMACD collision detection collision detectabort time CSMACD efficiency quot TIDrOID max prop between 2 nodes in LAN L t time to transmit maxsize frame trans 1 ef mency 1 StpmptHans Efficiency goes to 1 as tIDrOID goes to O i Goes to 1 as ttrans goes to infinity Much better than ALOHA but still decentralized simple and cheap LAN Addresses and ARP 32bit IP address networklayer address used to get datagram to destination IP network recall IP network definition LAN or MAC or physical or Ethernet address used to get datagram from one interface to another physicallyconnected interface same network 48 bit MAC address for most LANs burned in the adapter ROM LAN Addresses and ARP Each adapter on LAN has unique LAN address I adapter SCVBBVAEVBEIJSVW LAN Address more MAC address allocation administered by IEEE I manufacturer buys portion of MAC address space to assure uniqueness Analogy a MAC address like Social Security Number b IP address like postal address MAC flat address gt portability I can move LAN card from one LAN to another lP hierarchical address NOT portable I depends on IP network to which node is attached Example Starting at A given IP datagram addressed to B look up net address of B find B on same net as A link layer send datagram to B inside linklayer frame frame source datagram source dest address dest address B s MAC A s MAC addr addr datagram frame ARP Address Resolution Protocol Question how to determine MAC address of B knowing B s IP address SCVBBVABVQEIJSrBi 88752737504 AVEIF Each IP node Host Router on LAN has ARPtabIe ARP Table IPMAC address mappings for some LAN nodes lt 1 address Mm address mgt TTL Time To Live time a er which address mapping will be forgotten typically 20 min ARP protocol A wants to send datagram to B and A knows B s IP address Suppose B s MAC address is not in A s ARP table A broadcasts ARP query packet containing B39s IP address I all machines on LAN receive ARP query B receives ARP packet replies to A with its B39s MAC address I frame sent to A s MAC address unicast A caches saves IPtoMAC address pair in its ARP table until information becomes old times out I soft state information that times out goes away uness refreshed ARP is plugandplay I nodes create their ARP tables without intervention from net administrator Ethernet dominant LAN technology cheap 20 for 100Mbs first widely used LAN technology Simpler cheaper than token LANs and ATM Kept up with speed race 10 100 1000 Mbps Metcalfe s Ethernet Sketch 1976 L1 g g M ETHEK J Ethernet Frame Structure Sending adapter encapsulates IP datagram or other network layer protocol packet in Ethernet frame m Type Preamble 7 bytes with pattern 10101010 followed by one byte with pattern 10101011 used to synchronize receiver sender clock rates Ethernet Frame Structure more Addresses 6 bytes I if adapter receives frame with matching destination address or with broadcast address eg ARP packet it passes data in frame to net layer protocol I otherwise adapter discards frame Type indicates the higher layer protocol mostly lP but others may be supported such as Novell IPX and AppleTaIk CRC checked at receiver if error is detected the frame is simply dropped Ethernet uses CSMACD F No slots if adapter doesn t transmit if it senses that some other adapter is transmitting that is carrier sense transmitting adapter aborts when it senses that another adapter is transmitting that is collision detection Before attempting a retransmission adapter waits a random time that is random access Ethernet CSMACD algorithm 1 Adaptor gets datagram from and creates frame 2 If adapter senses channel idle it starts to transmit frame If it senses channel busy waits until channel idle and then transmits 3 If adapter transmits entire frame without detecting another transmission the adapter is done with frame 4 If adapter detects another 5 transmission while transmitting aborts and sends jam signal After aborting adapter enters exponential backoff after the mth collision adapter chooses a K at random from 01 2m1 Adapter waits K512 bit times and returns to Step 2 Capture Effect Given two stations A amp B an unfair strategy can cause A to continue to Assume A amp B always ready to send I if busy both wait send and collide I suppose A wins B backs off I next time B s chances of winning are halved Frame Size Minimum I With repeaters etc 8023 requires 51 us RTT corresponding to 512 bit times I Therefore the minimum frame size is 512 bits 64 Kbytes which is also called slot time Maximum I 1500 byte limitation on maximum frame transmission size MTU I Limits maximum buffers at receiver I Requires 96 bit InterPacketGap IPG Ethernet s CSMACD more Jam Signal make sure all other Exponential BaCkO i transmitters are aware of comsion 48 bits 7 Goal adapt retransmISSIon attempts to estimated current Bit time 01 microsec for 10 Mbps load Ethernet I heavy load random wait will belonger first collision choose K from 01 delay is K x 512 bit transmission times after second collision choose K from 01 23 for K1023 wait time is about 50 after ten collisions choose K msec from 012341023 Names Structure ratemodulationmedia or distance iOBase5 10Mbps baseband coax 500m iOBaseT 10Mbps baseband twisted pair iOOBaseTX iOOMbps baseband 2 pair iOOBaseFX iOOMbps baseband fiber iOOOBase CX for two pairs balanced copper cabling iOOOBaseLX for long wavelength optical transmission iOOOBase SX for short wavelength optical transmission Wireless WiFi I 80211 I Versions a b g Manchester encoding Manchester Encoding Bit steam Binary encoding L Used in lOBaseT lOBase2 l Each bit has a transition l Allows clocks in sending and receiving nodes to synchronize to each other I no need for a centralized global clock among nodes i Physicallayer stuff Ethernet Technologies 1OBase2 10 10Mbps 2 under 200 meters max cable length thin coaxial cable in a bus topology tee antimile packet connector terminator travels lll both directions 439 i adapter repeaters used to connect up to multiple segments repeater repeats bits it hears on one interface to its other interfaces physical layer device only has become a legacy technology 1OBaseT and 1OOBaseT 10100 Mbps rate latter called fast ethernet T stands for Twisted Pair Nodes connect to a hub star topology 100 m max distance between nodes and hub nodes hub Hubs are essentially physical layer repeaters I bits coming in one link go out all other links I no frame buffering I no CSMACD at hub adapters detect collisions I provides net management functionality Improvements Fast Ethernet 1995 adds I 10x speed increase 100m max cable length retains min 64 byte frames I replace Manchester with 4858 from FDDI I fullduplex operation using switches I speed amp duplex autonegotiation Gigabit Ethernet IEEE 8023zab 19989 adds 1000 Mbs 100x speed increase carrier extension invisible padding packet bursting Interconnecting LAN segments i U E Hubs Bhdges Switches I Remark switches are essentially multi port bridges I What we say about bridges also holds for switches Interconnecting with hubs Backbone hub interconnects LAN segments Extends max distance between nodes But individual segment collision domains become one large collision domain I if a node in CS and a node EE transmit at same time collision Can t interconnect 1OBaseT amp 1OOBaseT backbone nub lOBaSeT Electrical Engineering Computer science Engineering Bndges Link layer device I stores and forwards Ethernet frames I examines frame header and selectively forwards frame based on MAC dest address I when frame is to be forwarded on segment uses CSMACD to access segment transparent I hosts are unaware of presence of bridges f plugandplay selflearning I bridges do not need to be configured Bridges traffic isolation Bridge installation breaks LAN into LAN segments bridges filter packets I same LAN segment frames not usually forwarded onto other LAN segments I segments become separate collision domains collision collision I M3 domain 39 domain 0 host LAN segment LAN segment LAN IP network Forwarding 1088567 1088567 near Computer Erect Systems Engmeenng Screrrce Engmeenng How do determine to which LAN segment to forward frame Looks like a routing problem Self learning A bridge has a bridge table entry in bridge table I Node LAN Address Bridge Interface Time Stamp I stale entries in table dropped TTL can be 60 min bridges learn which hosts can be reached through which interfaces I when frame received bridge learns location of sender incoming LAN segment I records senderlocation pair in bridge table FilteringForwarding When bridge receives a frame index bridge table using MAC dest address if entry found for destination then if dest on segment from which frame arrived then drop the frame else forward the frame on interface indicated else flood fonvard on all but the interface on which the frame arrived Bridge example Suppose C sends frame to D and D replies back with frame to C Bridge receives frame from from C l notes in bridge table that C is on interface 1 I because D is not in table bridge sends frame into interfaces 2 and 3 frame received by D