COM204 Computer Networks Chapter 3 PDF

COM204 Computer Networks Chapter 3 Network Access Layer (Physical and Data link Layers) Prof. Mahmoud Elmesalawy Electronics and Communication Engineering Department Faculty of Engineering Helwan University ...

COM204 Computer Networks Chapter 3 Network Access Layer (Physical and Data link Layers) Prof. Mahmoud Elmesalawy Electronics and Communication Engineering Department Faculty of Engineering Helwan University  Chapter 3: Network Access Layer 3.1 Physical Layer and Network Media 3.1.2 Physical Layer Fundamental Principles 3.1.2 Physical Layer Fundamental Principles 3.1.3 Network Media 3.2 Data link layer functions and Standards 3.2.1 Data Link Layer Functions 3.2.2 Data Link Layer Standards 3.3 Data Link Framing and Addressing 3.3.1 Frame Fields 3.3.2 Frame start and stop indicator flags with Bit Stuffing 3.3.3 LAN and WAN Frames 3.3.4 Layer 2 Data link Address 3.4 Error Control Techniques 3.4.1Types of Errors 3.4.2 Error Detection Techniques 3.4.3 Error Correction Techniques 3.4.4 Error control Techniques 3.5 Error and Flow Control Mechanisms 3.5.1 Stop-and-Wait ARQ 3.5.2 Go-Back N ARQ 3.5.3 Selective Repeat ARQ 3.6 Media Access Control (MAC) 3.1 Physical Layer and Network Media The OSI physical layer provides the means to transport the bits that make up a data link layer frame across the network media. This layer accepts a complete frame from the data link layer and encodes it as a series of signals that are transmitted onto the local media. The encoded bits that comprise a frame are received by either an end device or an intermediate device. 3.1 Physical Layer and Network Media 3.1.1 Physical Layer Standards There are many different international and national organizations, regulatory government organizations, and private companies involved in establishing and maintaining physical layer standards. For instance, the physical layer hardware, media, encoding, and signaling standards are defined and governed by some organizations as shown in the table Standard Networking Standards Organization ISO 8877: Officially adopted the RJ connectors (e.g., RJ-11, RJ-45) ISO ISO 11801: Network cabling standard similar to EIA/TIA 568. TIA-568-C: Telecommunications cabling standards, used by nearly all voice, video and data networks. TIA-569-B: Commercial Building Standards for Telecommunications EIA/TIA Pathways and Spaces TIA-598-C: Fiber optic color coding TIA-942: Telecommunications Infrastructure Standard for Data Centers ANSI 568-C: RJ-45 pinouts. Co-developed with EIA/TIA ITU-T G.992: ADSL 802.3: Ethernet IEEE 802.11: Wireless LAN (WLAN) & Mesh (Wi-Fi certification) 802.15: Bluetooth 3.1 Physical Layer and Network Media 3.1.2 Physical Layer Fundamental Principles Physical Frame Encoding Media Signalling Method Components Technique UTP Manchester Encoding Changes in the voltage of Coaxial Non-Return to Zero (NRZ) Electrical Signal Connectors techniques Copper NICs 4B/5B codes are used Cable Ports with Multi-Level Transition Interfaces Level 3 (MLT-3) signaling 8B/10B PAM5 Single-mode Fiber Pulses of light A pulse equals 1. Multimode Fiber Wavelength multiplexing No pulse is 0. Connectors using different colors Fiber Optic NICs Cable Interfaces Lasers and LEDs Photoreceptors Access Points DSSS (direct-sequence Radio waves NICs spread-spectrum) Wireless Radio OFDM (orthogonal Media Antennas frequency division multiplexing) 3.1 Physical Layer and Network Media 3.1.2 Physical Layer Fundamental Principles The physical layer produces the representation and groupings of bits as voltages, radio frequencies, or light pulses using various standards. As an example, standards for copper media are defined for the: Type of copper cabling used, Bandwidth of the communication, Type of connectors used, Pinout and color codes of connections to the media, Maximum distance of the media. The figure shows different types of interfaces and ports available on a 1941 router. 3.1 Physical Layer and Network Media 3.1.3 Network Media There are three basic forms of network media. The physical layer produces the representation and groupings of bits for each type of media as: Copper Media: The signals are patterns of electrical pulses. Fiber-optic Media: The signals are patterns of light. Wireless Media: The signals are patterns of microwave transmissions. The figure displays signaling examples for copper, fiber-optic, and wireless. 3.1 Physical Layer and Network Media 3.1.3 Network Media 1. Copper Media There are three main types of copper media used in networking: – Unshielded Twisted-Pair (UTP) – Shielded Twisted-Pair (STP) – Coaxial These cables are used to interconnect nodes on a LAN and infrastructure devices such as switches, routers, and wireless access points. Each type of connection and the accompanying devices has cabling requirements stipulated by physical layer standards. UTP cabling is the most common networking media. UTP cabling, terminated with RJ-45 connectors, is used for interconnecting network hosts with intermediate networking devices, such as switches and routers. STP provides better noise protection than UTP cabling. However, compared to UTP cable, STP cable is significantly more expensive and difficult to install. Like UTP cable, STP uses an RJ-45 connector. The coaxial cable design is mainly used in wireless installations and cable Internet installations. 3.1 Physical Layer and Network Media 3.1.3 Network Media 1. Copper Media Unshielded Twisted Shielded Twisted Coaxial Cable Pair (UTP) Cable Pair (STP) Cable 3.1 Physical Layer and Network Media 3.1.3 Network Media 2. Fiber-optic Media Optical fiber cable transmits data over longer distances and at higher bandwidths than any other networking media. Fiber-optic cables are broadly classified into two types: Single-mode fiber (SMF) and Multimode fiber (MMF). 3.1 Physical Layer and Network Media 3.1.3 Network Media 2. Fiber-optic Media An optical fiber connector terminates the end of an optical fiber. A variety of optical fiber connectors are available. The main differences among the types of connectors are dimensions and methods of coupling. Businesses decide on the types of connectors that will be used, based on their equipment. 3.1 Physical Layer and Network Media 3.1.3 Network Media 3. Wireless Media Wireless media carry electromagnetic signals that represent the binary digits of data communications using radio or microwave frequencies. Wireless media provides the greatest mobility options of all media, and the number of wireless- enabled devices continues to increase. Types of Wireless Media 3.2 Data link layer Functions and Standards Data Link Layer provides a service for Network Layer (transfer of data from the network layer of a sender to the network layer of a receiver). Data Link Layer uses the Physical Layer to transmit bits of Data Link Frames over the physical medium. 3.2.1 Data Link Layer Functions are: 1. Framing (Grouping Bits into Frames). 2. Error Control. 3. Flow Control. 4. Addressing 5. Medium Access Control (MAC). Network LLC MAC Physical Fig. 3.1 Functions of Data Link Layer. 3.2 Data link layer functions and Standards (Continued) 3.2.2 Data Link Layer Standards are: Standard Networking Standards organization 802.2: Logical Link Control (LLC) 802.3: Ethernet 802.4: Token bus IEEE 802.5: Token passing 802.11: Wireless LAN (WLAN) & Mesh (Wi-Fi certification) 802.15: Bluetooth 802.16: WiMax G.992: ADSL G.8100 - G.8199: MPLS over Transport aspects ITU-T Q.921: ISDN Q.922: Frame Relay HDLC (High Level Data Link Control) ISO ISO 9314: FDDI Media Access Control (MAC) ANSI X3T9.5 and X3T12: Fiber Distributed Data Interface (FDDI) 3.3 Data Link Framing and Addressing The data link layer prepares a packet for transport across the local media by encapsulating it with a header and a trailer to create a frame. The description of a frame is a key element of each data link layer protocol. Although there are many different data link layer protocols that describe data link layer frames, each frame type has three basic parts: Header, Data and Trailer as shown in figure. All data link layer protocols encapsulate the Layer 3 PDU within the data field of the frame. However, the structure of the frame and the fields contained in the header and trailer vary according to the protocol. Two types of frame are: 1. Fixed-Size Framing: In fixed-size framing, there is no need for defining the boundaries of the frames. 2. Variable-Size Framing: In variable-size framing, we need a way to define the end of the frame and the beginning of the next. 3.3 Data Link Framing and Addressing 3.3.1 Frame Fields As shown in the figure, generic frame field types include: Frame start and stop indicator flags - Used to identify the beginning and end limits of the frame. Addressing - Indicates the source and destination nodes on the media. Type - Identifies the Layer 3 protocol in the data field. Control - Identifies special flow control services such as quality of service (QoS). QoS is used to give forwarding priority to certain types of messages. Data - Contains the frame payload (i.e., packet header, segment header, and the data). Error Detection - These frame fields are used for error detection. A transmitting node creates a logical summary of the contents of the frame, known as the cyclic redundancy check (CRC) value. This value is placed in the Frame Check Sequence (FCS) field 3.3 Data Link Framing and Addressing 3.3.2 Frame start and stop indicator flags with Bit Stuffing Each Frame begins and ends with a special bit pattern 01111110 (Flag Byte). Bit Stuffing - If Data has 5 Consecutive 1S  ADD 0. - Bit stuffing is the process of adding one extra 0 whenever five consecutive 1s follow a 0 in the data, so that the receiver does not mistake the pattern 0111110 for a flag. Flag Byte Data Flag Byte 01111110 0011011101111110101011111010 01111110 Flag Byte Data Flag Byte 01111110 001101110111110101010111110010 01111110 3.3 Data Link Framing and Addressing 3.3.2 Frame start and stop indicator flags with Bit Stuffing 3.3 Data Link Framing and Addressing 3.3.3 LAN and WAN Frames The Layer 2 protocol and consequently the framing used for a particular network topology is determined by the technology used to implement that topology. The technology is, in turn, determined by the size of the network - in terms of the number of hosts and the geographic scope - and the services to be provided over the network. Example of Layer 2 Protocols (Framing) 3.3 Data Link Framing and Addressing 3.3.3 LAN and WAN Frames Point-to-Point Protocol (PPP) Frame 3.3 Data Link Framing and Addressing 3.3.3 LAN and WAN Frames Ethernet Frame 3.3 Data Link Framing and Addressing 3.3.3 LAN and WAN Frames 802.11 Wireless (Wi-Fi) Frame 3.3 Data Link Framing and Addressing 3.4 Layer 2 Data Link Address The data link layer provides addressing that is used in transporting a frame across a shared local media. Device addresses at this layer are referred to as physical addresses. Data link layer addressing is contained within the frame header and specifies the frame destination node on the local network. The frame header may also contain the source address of the frame. Unlike Layer 3 logical addresses, which are hierarchical, physical addresses do not indicate on what network the device is located. Rather, the physical address is unique to the specific device. If the device is moved to another network or subnet, it will still function with the same Layer 2 physical address. The next Figure illustrates the function of the Layer 2 and Layer 3 addresses. As the IP packet travels from host-to-router, router-to-router, and finally router- to-host, at each point along the way, the IP packet is encapsulated in a new data link frame. Each data link frame contains the source data link address of the NIC card sending the frame, and the destination data link address of the NIC card receiving the frame. 3.3 Data Link Framing and Addressing 3.4 Layer 2 Data Link Address 3.5 Error Control Techniques For a system to deal with errors that occur due to disturbances on the physical channel, error control techniques are used. Error control: is both error detection and correction. 3.5.1Types of Errors Networks must be able to transfer data from one device to another with complete accuracy. Data can be corrupted during transmission. For reliable communication, errors must be detected and corrected. Error detection is implemented at the data link layer of the OSI model. Errors can have one of the following forms: 1. Single-bit errors are the least likely type of error in serial data transmission. The term single bit error means that only one bit of a given data unit such as one bit in the character or packet is changed from 1 to 0 or from 0 to 1. 3.5 Error Control Techniques (Continued) 3.5.1Types of Errors 2. Multiple Bit error means that 2 or more bits in the data unit have changed. 3. Burst error is multiple bit error measured from the first corrupted bit to the last corrupted bit, some bits in between may not have been corrupted. 3.5 Error Control Techniques (Continued) 3.5.2 Error Detection Techniques Error detection means to decide whether the received data is correct or not without having a copy of the original message. Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination. Three types of redundancy checks are common in data communication which include: Parity check, Cyclic redundancy check and Checksum. Error Detecting Techniques Add Redundant (Extra) Bits to Deduce that an Error has Occurred. BUT NOT WHICH ERROR. When it is detected that a packet is in error, a retransmission is requested. 3.5 Error Control Techniques (Continued) 3.5.2 Error Detection Techniques Redundancy Check Fig. 3.3(a) The structure of encoder and decoder. 3.5 Error Control Techniques (Continued) 3.5.2 Error Detection Techniques 1. Parity Check In parity check, a parity bit is added to every data unit so that the total number of 1s is even (or odd for odd-parity). Simple even parity check can detect all single-bit errors. It can detect burst errors only if the total number of errors in each data unit is odd. Example: Suppose the sender wants to send the word “world”.In ASCII the five characters are coded as: w o r l d 1110111 1101111 1110010 1101100 1100100 The actual bits sent are: 11101110 11011110 11100100 11011000 11001001 Fig. Even Parity Bit. 3.5 Error Control Techniques (Continued) 3.5.3 Error Detection Techniques 2. Cyclic Redundancy Check (CRC) Most powerful method, Based on binary division A redundant bits called CRC is appended to the end of a data unit. The resulting data becomes exactly divisible by a second predetermined binary bit as shown in Fig. Fig. Process of error detection in Cyclic Redundancy Check. 3.5 Error Control Techniques (Continued) 3.5.3 Error Detection Techniques 2. Cyclic Redundancy Check (CRC) Let D(x) represents the message as a polynomial P(x) represents the divisor as a polynomial F represents the CRC bits quotient n 2 D R remainder Step 1: Q P P Step 2: F=R No remainder Verification: T  2n D  R T 2n D  R 2n D R R R    Q  Q P P P P P P 3.5 Error Control Techniques (Continued) 3.5.3 Error Detection Techniques 2. Cyclic Redundancy Check (CRC) Example: if the message D(x) = x5+ x2 and divisor P(x)= x3+ x2+ 1. Find the following 1. CRC. 2. Transmitted message. 1. Receiver error check. Sender side 3.5 Error Control Techniques (Continued) 3.5.3 Error Detection Techniques 2. Cyclic Redundancy Check (CRC) Transmitted data over the channel will be : 100100001 Original message CRC Receiver side 3.5 Error Control Techniques (Continued) 3.5.3 Error Detection Techniques 2. Cyclic Redundancy Check (CRC) Common polynomials for C(x): CRC C(x) CRC-8 x8+x2+x1+1 CRC-10 x10+x9+x5+x4+x1+1 CRC-12 x12+x11+x3+x2+x1+1 CRC-16 x16+x15+x2+1 CRC-CCITT x16+x12+x5+1 CRC-32 x32+x26+x23+x22+x16+x12+x11+x10+ x8+x7+x5+x4+x2+x+1 3.5 Error Control Techniques (Continued) 3.5.4 Error Correction Techniques Sender Receiver Error correction techniques Data include: FEC and ARQ 0 Frame No Errors Detection/ 1. Forward Error Correction 0 Correction (FEC). In this technique the ACK system adds redundant (extra) Frame is Good bits to Identify which bit is in Error and Correct it as shown in Fig. 3.7. 1 Timer Errors Detection/ FEC Channel codes may be 1 Correction classified into two broad categories: Block Codes and 1 Convolutional codes No Errors Detection/ 1 Correction ACK Frame is Good Fig. 3.7 Forward Error Correction (FEC). 3.5 Error Control Techniques (Continued) 3.5.4 Error Correction Techniques 2. Automatic Repeat Request (ARQ): ARQ technique adds parity or redundant bits to the transmitted data stream that are used by the decoder to detect an error in the received data. When the receiver detects an error, it requests that the data be retransmitted by the receiver. This continues until the message is received correctly. In ARQ, the receiver does not attempt to correct the errors, but rather it sends an alert to the transmitter in order to inform it that an error was detected and that a retransmission is needed. This is known as a negative acknowledgement, and the transmitter retransmits the message upon receipt. If the message is error free, the receiver sends an acknowledgement (ACK) to the transmitter. 3.6 Error and Flow Control Mechanisms One of the most important duties of data link layer. Incoming data must be checked and processed before they can be used. The rate of such processing is often slower than the rate of transmission. For this reason, each receiver has a buffer to store incoming data until they are processed. If buffer begin to fill up, the sender must slow or halt transmission. Flow control refers to a set of procedures used to restrict the amount of data that the sender can send before waiting for acknowledgment. Well-defined rules on when the sender could transmit the next frame Flow control ensures that a transmitting station does not overflow a receiving station with data. Two techniques of flow control in data link layer – Stop-and-Wait flow control – Sliding window flow control Go-Back N ARQ Selective Repeat ARQ 3.6 Error and Flow Control Mechanisms (Continued) Now let us see how the data link layer can combine flow control and error control to achieve the delivery of data from one node to another. Many protocols (mechanisms) are used for error and flow control which contain: 1. Stop-and-Wait Automatic Repeat Request (ARQ) 2. Go-Back N Automatic Repeat Request (ARQ) 3. Selective Repeat Automatic Repeat Request (ARQ) 3.6 Error and Flow Control Mechanisms (Continued) 3.6.1 Stop-and-Wait ARQ It is the simplest flow and error control mechanism. A transmitter sends a frame then stops and waits for an acknowledgment. H : Header Stop after transmitting a frame CRC : Cyclic Redundancy Wait for an Acknowledgement Check (Error Detection) Fig. 3.9(a) Stop-and-Wait ARQ. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.1 Stop-and-Wait ARQ (Stop-and-Wait ARQ Features) The sender sends one frame and waits for feedback from the receiver. When the ACK arrives, the sender sends the next frame. The sending device keeps a copy of the last frame transmitted until it receives an acknowledgement for that frame. For identification purposes, both data frames and acknowledgement (ACK) frames are numbered alternately 0 and 1. The acknowledgement number always defines the number of the next expected frame. If frame 0 is received, ACK 1 is sent; if frame 1 is received, ACK 0 is sent, as shown in Fig. 3.9(b). A damaged or lost frame is treated in the same manner by the receiver. The Sender has a control variable S that holds the recently sent frame (0 or 1). The Receiver has a control variable R that holds the number of the next frame expected (0 or 1), as shown in Fig. 3.10(a). The sender starts a timer when it sends a frame, if an acknowledgement is not received within an allowed time period, the sender assumes that the frame was lost or damaged and resends it. The receiver sends only positive acknowledgement for frames received safely. It is silent about the frames damaged or lost , as shown in Fig. 3.10(b). 3.6 Error and Flow Control Mechanisms (Continued) 3.6.1 Stop-and-Wait ARQ (Cases of Operation) 1. Normal Operation Frame to be received. 0 1 0 0 1 0 Frame to be transmitted 0 1 0 0 1 0 0 1 0 Fig. 3.9(b) Stop-and-Wait ARQ with normal operation. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.1 Stop-and-Wait ARQ (Cases of Operation) 2. Lost or damaged frame Start Timer Start Timer Retransmission Fig. 3.10(a) Stop-and-Wait ARQ with Timers and lost frame. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.1 Stop-and-Wait ARQ (Cases of Operation) 3. Lost Ack frame Fig. 3.10(b) Stop-and-Wait ARQ with Timers and lost ACK. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.1 Stop-and-Wait ARQ (Cases of Operation) 4. Delayed ACK and lost frame In Stop-and-Wait ARQ, numbering frames prevents the retaining of duplicate frames. Fig. 3.10(c) Stop-and-Wait ARQ with Timers and delayed ACK. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.2 Sliding Window-Based ARQ To improve the efficiency, multiple frames should be in transition while waiting for acknowledgment. Two Protocols use this concept which are based on sliding window technique: - Go-Back-N ARQ - Selective Repeat ARQ Definitions: 1. Frame Sequence Number: Frames needed to be numbered to specify the transmitted frame. if m bits used to specify frame, so the sequence numbers start from 0, go to 2m – 1 as shown below: 0 1 2 3 0 1 2 3 0 1 m=2 0 1 2 3 4 5 6 7 0 1 m=3 The frame sequence numbers cannot be allowed to keep on increasing to infinity. WHY? - Headers must be limited in size. - An increase in header size means inefficiency. If m bits are devoted for carrying the sequence numbers, so frame sequence numbers may go from 0 up to 2m – 1. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.2 Sliding Window-Based ARQ (Definitions) 2. Sender sliding window The size of the window in this example is “N=7” as shown below: Frames to be transmitted 3.6 Error and Flow Control Mechanisms (Continued) 3.6.2 Go-Back N ARQ (Normal Operation): Go-Back-N ARQ normal operation is shown in Fig. 3.12(a). Window slides when ACK received Fig. 3.12(a) normal operation in Go-Back-N ARQ. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.2 Go-Back N ARQ (Lost Frame Operation): Go-Back-N ARQ if a frame is lost as in Fig. 3.12(b). Fig. 3.12(b) Lost frame in Go-Back-N ARQ. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.3 Selective Repeat ARQ Disadvantage of Go-Back N - Go Back-N retransmits the erroneous frame and all subsequent frames. - This reduces efficiency especially for High Error Channels. Selective Repeat ARQ - Introduce a receive window to store CORRECT out of sequence frames. - Retransmit individual frames. - TCP uses a form of selective repeat. Sender and Receiver Windows In Selective Repeat ARQ, the size of the sender and receiver window must be at most (2m / 2) or [(2m-1) / 2]. 3.6 Error and Flow Control Mechanisms (Continued) 3.6.3 Selective Repeat ARQ Selective Repeat ARQ if a frame is lost as in Fig. 3.13(a). Fig. 3.13(a) Loss frame in Selective Repeat ARQ. 3.7 Media Access Control (MAC) When more than two nodes send at the same time, the transmitted frames collide. All collide frames are lost and the bandwidth of the broadcast channel will be wasted. We need multiple access protocol to coordinate access to multipoint or broadcast link (Nodes or stations are connected to or use a common link) 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods In random access (contention-based) methods, no station is superior to another station and none is assigned the control over another. No station permits, or does not permit, another station to send. At each instance, a station that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send. This decision depends on the state of the medium (idle or busy). In random access protocols: - Each station has the right to the medium without being controlled by any other station. - Two features gives the method its name: 1. There is no schedule time for a station to transmit: transmission is random among stations. 2. Stations compete with one another to access the medium (Contention method). - Collision: an access conflict occurs when more than one station tries to send, as a result the frame will be either destroyed or modified. Random access tries to answer the following to solve conflict problems: – When can a station access the medium? – What can the station do if the medium is busy? – How is transmission success/failure determined? – What can a station do if there is access conflict? 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 1. Pure ALOHA Aloha, in the Hawaiian language, means hello or goodbye. The earliest random access method developed at the University of Hawaii in the early 1970s. Designed for a radio (wireless) LAN with data rate of 9600 bps. It is a simple method. Each station sends a frame whenever it has a frame to send. Since there is only one channel to share, there is the possibility of collision between frames from different stations. Fig. 3.23 ALOHA network multiple access. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 1. Pure Aloha (Frames Transmission) Vulnerable period is the time in which there is a possibility of collision and in Pure ALOHA equal the 2 𝝬 propagation time (Tp). Fig. 3.24(a) Transmission with frame collision in Pure Aloha. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 1. Pure Aloha (Frames Transmission) Fig. 3.24(b) ALOHA Vulnerable Time. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 1. Pure Aloha (Procedures) Each station sends a frame whenever it has a frame to send. It relies on acknowledgments from the receiver. If the ACK dose not arrive after a time-out period, the station resend the frame. Time-out is equal the max possible round trip time = 2 x Tp. Where Tp (max propagation time) is the time required to send a frame between the most widely separated stations. To minimize collisions, each station waits a random amount of time (back-off time TB) before resending its frame. TB is a random value that depend on K (the number of attempted unsuccessful transmission). The formula of TB is the binary exponential back-off. After a max number of retransmission attempts Kmax, a station must give up and try later to prevent congestion. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 1. Pure Aloha (Procedures) Fig. 3.25 Pure ALOHA Procedures. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 1. Pure Aloha (Procedures) Example 3.3 Calculate possible values of back-off time, TB if the stations on a wireless ALOHA network are a maximum distance, d = 600 km apart. If we assume that signals propagate at the speed of light, c = 3 × 108 m/s. Example 3.3 Solution The propagation time , Tp = (600 × 105 ) / (3 × 108 ) = 2 ms. Now we can find the value of back-off time, TB for different values of K. a. For K = 1, the range is {0, 1}. The station needs to generate a random number with a value of 0 or 1. This means that TB is either 0 ms (0 × 2) or 2 ms (1 × 2), based on the outcome of the random variable. b. For K = 2, the range is {0, 1, 2, 3}. This means that TB can be 0, 2, 4, or 6 ms, Based on the outcome of the random variable. c. For K = 3, the range is {0, 1, 2, 3, 4, 5, 6, 7}. This means that TB can be 0, 2, 4,... , 14 ms, based on the outcome of the random variable. d. We need to mention that if K > 10, it is normally set to 10. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 2. Slotted ALOHA Frames are of the same size. Time is divided into equal size slots which is the time to transmit one frame. Nodes start to transmit frames only at beginning of slots. If two or more nodes transmit in slot, collision occurs. As a consequence, frames either collide completely or don’t collide at all. Vulnerable period equal only one propagation time (Tp). Fig. 3.26 Transmitted frames in Slotted ALOHA. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 4. Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Sense the carrier before transmit : “listen before you talk”. CSMA can reduce the possibility of collision, but it can not eliminate it because of the propagation delay (a station may sense the medium and find it idle, only because the first bit of a frame sent by another station has not been received. A host listens even while it is transmitting “Listen-while-talk” , and if a collision is detected, stops transmitting. Fig. 3.31 Carrier Sense Multiple Access with Collision Detection (CSMA/CD). 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 4. Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Fig. 3.32 CSMA/CD procedure. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 4. Carrier Sense Multiple Access with Collision Detection (CSMA/CD) How the station detects a collision? – Detecting voltage level on the line. – Detecting energy level. Energy in channel can have three values: zero, normal, and abnormal. At zero level, the channel is idle. At the normal level, a station has successfully captured the channel and is sending its frame. At the abnormal level, there is a collision and the level of the energy twice the normal level. Fig. 3.33 Collision detection. 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 4. Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Minimum frame size For CSMA/CD to work correctly we need to restrict the minimum frame size. Before sending the last bit of a frame, the sending station must detect a collision and abort the transmission. This is so because the station, once the entire frame is sent does not keep a copy of the frame and does not monitor the line of collision detection. For the worst case scenario; if the two stations involved in a collision are the max distance apart. Frame transmission time > = 2 x max. propagation time Ttfr > = 2 X Tp (Min. Frame size)/BW = 2 X Tp 3.7 Media Access Control (MAC) - (Continued) 3.7.1 Random (Contention-based) Access Methods 4. Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Example 3.4 A network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal) is 25.6μs, what is the minimum size of the frame? Solution The frame transmission time is Ttfr = 2 × Tp = 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 = 10 Mbps × 51.2 μs = 512 bits or 64 bytes. This is actually the minimum size of the frame for Standard Ethernet.