Ch4 data_removed.pdf

Data Link Layer Data Link Layer Chapter Outline ⚫ Multiple Access Methods ⚫ Random Access ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ Local Area Networks Wireless Local Area Networks Scheduling Channelization Point-to-Point Protocols Error Control ⚫ ⚫ Error Detection Error Correction Dr. Atef Abdrabou 2 Data Link Layer D...

Data Link Layer Data Link Layer Chapter Outline ⚫ Multiple Access Methods ⚫ Random Access ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ Local Area Networks Wireless Local Area Networks Scheduling Channelization Point-to-Point Protocols Error Control ⚫ ⚫ Error Detection Error Correction Dr. Atef Abdrabou 2 Data Link Layer Data Link Layer Multiple Access Connections Point-to-Point Connections Multiple Access Methods Random Access Local Area Networks (e.g., Ethernet) Wireless Local Area Networks (WLANs) Scheduling Channelization Dr. Atef Abdrabou Point-to-Point Protocols (e.g. PPP protocol) 3 Medium Access Control Protocols and Local Area Networks Multiple Access Communications Multiple Access Communications ⚫ Shared media basis for broadcast networks ⚫ ⚫ ⚫ Inexpensive: radio over air; copper or coaxial cable M users communicate by broadcasting into medium Key issue: How to share the medium? 3 2 4 1 Shared multiple access medium M  Dr. Atef Abdrabou 5 5 Approaches to Media Sharing Medium sharing techniques Static channelization ⚫ ⚫ ⚫ Partition medium to channels Dedicated channel allocation to users Examples: ⚫ Satellite transmission ⚫ Cellular Telephone Dynamic medium access control Scheduling ⚫ ⚫ Random access Stations take turns to send data Examples: ⚫ Token ring ⚫ ⚫ ⚫ Loose coordination Send, wait, retry if necessary Examples: ⚫ ⚫ Dr. Atef Abdrabou Aloha CSMA ⚫ Ethernet ⚫ WiFi 6 Random Access Section 12.1 Multitapped Bus Crash!! Transmit when ready Simultaneous transmissions may occur; need retransmission strategy Dr. Atef Abdrabou 7 Medium Access Control Protocols and Local Area Networks Random Access 1- The pure ALOHA Protocol ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ Section 12.1.1 A station attempts to transmit whenever it has data to transmit Every frame has a frame transmit time Tfr = number of bits per frame / transmission rate in bits/sec If more than one frame are transmitted at the same time, they interfere with each other (collide) and are lost If the receiver station received a frame correctly, it sends an acknowledgement (ACK) to the transmitter station Every frame or ACK takes an average propagation time tprop to reach the other station If the transmitter station did not receive the ACK within timeout tout = 2 tprop, it retransmits the frame after a random backoff time B to avoid repeated collisions First transmission Retransmission Backoff period B t t0-Tfr t0 t0+Tfr Vulnerable period t0+Tfr+2tprop t0+Tfr+2tprop + B Time-out Dr. Atef Abdrabou 9 Frame Transmission Attempts in a pure Aloha Network Dr. Atef Abdrabou 10 Vulnerability Period ⚫ ⚫ Vulnerability period is the time duration in which a collision is possible In pure Aloha protocol, the vulnerability period equals to 2 Tfr Dr. Atef Abdrabou 11 Throughput of the Pure Aloha Protocol Section 12.1.1 Throughput S is defined as the ratio of successfully received frames to the number of frame transmission attempts 4 2 1 0.5 0.2 5 0.1 25 For pure Aloha protocol, S = G x e-2G where G is the number of transmission attempts per frame transmission time or 0.0 62 5 ⚫ Number of succesfully received frames Number of frame transmiss ion attempts 0.2 0.18 0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 0 0.0 07 81 25 0.0 15 62 5 0.0 31 25 S= 0.5e-1 = 0.184 S ⚫ G G = Number of frame transmission attempts per second x Tfr Dr. Atef Abdrabou 12 Example: Pure Aloha Throughput A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the network (all stations together) send a. 1000 frames per second b. 500 frames per second c. 250 frames per second ⚫ Solution The frame transmission time Tfr = 200 bit/ (200 kbps) = 1 ms a. There are 1000 frame transmission attempts per second, this means1 frame transmission attempt per millisecond. Therefore, G = 1000 x Tfr = 1 In this case, S = 1× e−2 or S = 0.135 (13.5 percent) This means that the number of successfully received frames is 1000 × 0.135 = 135 frames. Only 135 frames out of 1000 will be received correctly Dr. Atef Abdrabou 13 Example: Pure Aloha Throughput (cont) b. If the network stations send 500 frames per second, this means G = 500 x Tfr = 0.5 In this case, S = 0.5 × e −1 or S = 0.184 (18.4 %). This means that the number of successfully received frames = 500 × 0.184 = 92. (only 92 frames out of 500 will probably received correctly) Note that this is the maximum throughput case. ⚫ c. If the network stations send 250 frames per second, this means G = 250 x Tfr = 0.25 In this case, S = 0.25 × e-0.5 or S = 0.152 (15.2 %). This means that the number of successfully received frames is 250 × 0.152 = 38. (Only 38 frames out of 250 will be successfully received) ⚫ Dr. Atef Abdrabou 14 2. The Slotted ALOHA protocol ⚫ ⚫ ⚫ ⚫ Section 12.1.1 Time is slotted in Tfr seconds slots Stations synchronized to frame times Stations transmit frames in first slot after frame arrival Backoff intervals in integer multiple of slots Backoff period B t kTfr (k+1)Tfr Vulnerable period t0 +Tfr+2tprop t0 +Tfr+2tprop+ B Time-out Only frames that arrive during prior Tfr seconds collide Dr. Atef Abdrabou 15 Throughput of the Slotted Aloha protocol Section 12.1.1 ⚫ Throughput S is defined as the ratio of successfully received frames to the number of frame transmission attempts S= ⚫ Number of succesfully received frames Number of frame transmiss ion attempts For Slotted Aloha protocol, S = G x e-G where G is the number of transmission attempts per frame transmission time or G = Number of frame transmission attempts per second x Tfr Dr. Atef Abdrabou 16 Slotted Aloha Vulnerability Period ⚫ ⚫ Vulnerability period is the time duration in which a collision is possible In slotted Aloha protocol, the vulnerability period equals to Tfr Dr. Atef Abdrabou 17 Example: Slotted Aloha Throughput ⚫ ⚫ ⚫ A slotted ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the system (all stations together) produces a. 1000 frames per second b. 500 frames per second c. 250 frames per second Solution The frame transmission time Tfr = 200 bits/200 kbps = 1 ms a. If the system creates 1000 frames per second, this means G = 1000 x Tfr = 1 frame transmission attempt per frame transmission time. In this case, S = G× e−G or S = 0.368 (36.8%). This is the maximum throughput, why? This means that the number of successfully received frames is 1000 × 0.0368 = 368 frames. (Only 386 frames out of 1000 will be successfully received) Dr. Atef Abdrabou 18 Example: Slotted Aloha Throughput (cont) Slotted Aloha Ge-G 0.4 0.35 0.368 0.3 0.25 0.184 0.2 0.15 Pure Aloha Ge-2G 0.1 8 4 2 0.5 0.25 0.125 0.0625 0.01563 0.03125 0.05 c. If the system creates 250 frames per 0 second, this is (1/4) frame per millisecond. The load is (1/4). In this case S = G × e −G or S = 0.195 (19.5 percent). This means that the throughput is 250 × 0.195 = 49. Only 49 frames out of 250 will be successfully received Dr. Atef Abdrabou 1 b. If the system creates 500 frames per second, this means G = 500 X 0.001 = 1/2 frame transmission attempts per frame transmission time In this case, S = G × e−G or S = 0.303 (30.3 percent). This means that the number of successfully received frames is 500 × 0.0303 = 151. S (Only 151 frames out of 500 will be successfully received) G 19 Carrier Sensing Multiple Access (CSMA) Section 12.1.2 ⚫ A station senses the channel before it starts transmission ⚫ ⚫ ⚫ ⚫ If busy, either wait or schedule backoff (different options) If idle, start transmission Vulnerable period is reduced to tprop (due to channel capture effect) When collisions occur they involve entire frame transmission times Station A begins transmission at t=0 A Station A captures channel at t = tprop A Dr. Atef Abdrabou 20 Vulnerability Period in CSMA ⚫ ⚫ Vulnerability period is the time duration in which a collision is possible In CSMA protocol, the vulnerability period equals to tprop Dr. Atef Abdrabou 21 IEEE 802.3 Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Section 12.1.3 Duration ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ Duration Each station monitors the medium during frame transmission to see if the transmission was successful If there is a collision, the frame will be sent again At time t1 , station A starts to send its first bit to station D At time t2 , station C starts to send its first bit to station A since the first bit from A has not arrived yet Collision happens at some time after t2 C detects the collision at t3 when the first bit of A arrives to it and stops (aborts) its transmission Dr. Atef Abdrabou 22 Similarly, A stops its transmission at t4, when it receives the first bit from C Ethernet Minimum Frame Size ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ A restriction on Ethernet frame size is required for CSMA/CD to work A transmitting station should detect a collision before the last bit of the frame is sent If the last bit is sent without detecting a collision, the station will not keep a copy of the frame If two communicating stations A & B are at the maximum distance apart, the signal from A takes tprop to reach B If the first bit of a frame sent by A just before reaching B, collided with the first bit of a frame sent by B A will take 2 tprop to know that a collision happens This means the minimum frame transmission time Tfr(min) = 2 tprop Tfr(min) = minimum frame size in bits / transmission rate in bits/sec Dr. Atef Abdrabou 23 Example: Ethernet Minimum Frame Size Calculation A network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time is 25.6 μs, What is the minimum size of the Ethernet frame? Solution The minimum frame transmission time is Tfr(min) = 2 × Tprop = 51.2 μs. This means, in the worst case, a station needs to transmit for a period of 51.2 μs to detect the collision The minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes. This is actually the minimum size of the frame for Standard Ethernet Dr. Atef Abdrabou 24 Medium Access Control Protocols and Local Area Networks Ethernet IEEE 802.3 MAC Frame Section 13.2 802.3 MAC Frame 7 1 Preamble SD Synch ⚫ ⚫ ⚫ ⚫ ⚫ Start frame 6 Destination address 6 Source address 2 Length Information Pad 4 FCS 64 - 1518 bytes Every frame transmission begins “from scratch” Preamble helps receivers synchronize their clocks to transmitter clock 7 bytes of 10101010 generate a square wave Start frame byte changes to 10101011 Receivers look for change in 10 pattern Dr. Atef Abdrabou 26 IEEE 802.3 MAC Frame Section 13.2 802.3 MAC Frame 7 1 Preamble SD Synch ⚫ ⚫ ⚫ Start frame 6 Destination address 6 Source address 2 Length Information Pad 4 FCS 64 - 1518 bytes Length: # bytes in information field ⚫ Max frame 1518 bytes, excluding preamble & SD ⚫ Max information 1500 bytes: 05DC ⚫ The length field is replaced by the upper protocol type in Ethernet II frames (e.g., 0x0800 for the IP protocol) Pad: ensures min frame of 64 bytes FCS: CCITT-32 CRC, covers addresses, length, information, pad fields Dr. Atef Abdrabou ⚫ NIC discards frames with improper lengths or failed CRC 27 IEEE 802.3 Physical Layer Section 13.2 IEEE 802.3 10 Mbps medium alternatives Medium Max. Segment Length Topology (a) 10base5 10base2 10baseT 10baseFX Thick coax Thin coax Twisted pair Optical fiber 500 m 200 m 100 m 2 km Bus Bus Star Point-topoint link transceivers (b) Thick Coax: Stiff, hard to work withDr. Atef Abdrabou Hubs & Switches! T connectors flaky 28 Fast Ethernet Medium Max. Segment Length Topology Section 13.3.2 100baseT4 100baseT 100baseFX Twisted pair category 3 UTP 4 pairs Twisted pair category 5 UTP two pairs Optical fiber multimode Two strands 100 m 100 m 2 km Star Star Star To preserve compatibility with 10 Mbps Ethernet: ⚫ Same frame format, same interfaces, same protocols ⚫ Hub topology only with twisted pair & fiber ⚫ Bus topology & coaxial cable no longer used ⚫ Category 3 twisted pair (ordinary telephone grade) requires 4 pairs ⚫ Category 5 twisted pair requires 2 pairs (most popular) Dr. Atef Abdrabou 29 Gigabit Ethernet Medium Max. Segment Length Topology ⚫ ⚫ Section 13.4.2 1000baseSX 1000baseLX 1000baseCX 1000baseT Optical fiber multimode Two strands Optical fiber single mode Two strands Shielded copper cable Twisted pair category 5 UTP 550 m 5 km 25 m 100 m Star Star Star Star Frame structure preserved but CSMA-CD is not used since Gigabit Ethernet uses only switches. Extensive deployment in backbone of enterprise data networks and in server farms Dr. Atef Abdrabou 30