Computer Networks Unit2.pptx Data link layer Design issues, Framing: fixed size framing, variable size framing, flow control, error control, error detection and correction codes, CRC, Checksum: idea, one’s complement internet

Data link layer
Design issues, Framing: fixed size framing, variable size framing, flow control, error control, error detection and correction codes, CRC, Checksum: idea, one’s complement internet checksum, services provided to Network Layer, Elementary Data Link Layer protocols: simplex protocol, Simplex stop and wait, Simplex protocol for Noisy Channel.
Sliding window protocol: One bit, Go back N, Selective repeat-Stop and wait protocol, Data link layer in HDLC, Point to point protocol (PPP)

1. Unit- 2 Data Link Layer

2. Design issues, Framing : fixed size framing, variable size framing, flow control, error control, error detection and correction codes, CRC, Checksum: idea, one’s complement internet checksum, services provided to Network Layer, Elementary Data Link Layer protocols : simplex protocol, Simplex stop and wait, Simplex protocol for Noisy Channel. Sliding window protocol: One bit, Go back N, Selective repeat-Stop and wait protocol, Data link layer in HDLC, Point to point protocol (PPP) Data Link Layer

3. DATA LINK LAYER DESIGN ISSUES The data link layer uses the services of the physical layer to send and receive bits over communication channels. It has a number of functions, including: 1. Providing a well-defined service interface to the network layer. 2. Dealing with transmission errors. 3. Regulating the flow of data so that slow receivers are not swamped by fast senders . Data Link Layer

4. To accomplish these goals, the data link layer takes the packets it gets from the network layer and encapsulates them into frames for transmission. Each frame contains a frame header, a payload field for holding the packet, and a frame trailer , as illustrated in Fig. Frame management forms the heart of what the data link layer does. Data Link Layer

5. The data link layer transforms the physical layer, a raw transmission facility, to a link responsible for node-to-node (hop-to-hop) communication. Specific responsibilities of the data link layer include framing, addressing, flow control, error control, and media access control. Data Link Layer

6. Framing in data link layer separates a message from one source to a destination , or from other messages to other destinations, by adding a sender address and a destination Address. The destination address defines where the packet is to go. The sender address helps the recipient acknowledge the receipt. Two types of Framing: Fixed - Size Framing. Variable – Size Framing Framing

7. Fixed – Size Framing: There is no need for defining the boundaries of the frames. The size itself can be used as delimiter. Example: ATM a wide area network, which uses frames of fixed size called cells. Variable – Size Framing: We need to define the end of the frame and beginning of the next. It is prevalent in local area networks. It has two Approaches Character – Oriented Approach Bit - Oriented Approach Framing

8. Character Oriented Protocol A character stream (a) Without errors (b) With one error

9. In character oriented protocol, the data to be carried The are 8-bit characters from a coding system. Header : which normally carries the source and destination address and other control information. Trailer : which carries error detection or error correction redundant bits, are also the multiples of 8 bits. To separate one frame from the next , an 8-bit flag is added at the beginning and end of a frame. The flag , composed of protocol – dependent special characters, signals the start and end of a frame. Character Oriented Protocol

10. Byte Stuffing and Unstuffing

11. Byte stuffing is the process of adding 1 extra byte whenever there is a flag or escape character in the text. In byte stuffing, a extra byte is added to the data section of the frame when there is a character with the same pattern as the flag. The data section is stuffed with a extra byte. The byte is usually called the escape character (ESC). Whenever the receiver encounters the ESC character it removes it from the data section and treats the next character as data, not a delimiting flag. Byte Stuffing and Unstuffing

12. Byte Stuffing and Unstuffing (a) A frame delimited by flag bytes. (b) Four examples of byte sequences before and after stuffing.

13. Bit stuffing is the process of adding one extra 0 whenever five consecutive 1’s follow a 0 in the data, so that the receiver does not mistake the pattern 01111110 for the flag. The data consists of a sequence of bits. Most protocols use a special 8-bit pattern flag 01111110 as the delimiter to define the beginning and end of the frame. In bit stuffing, if a 0 and five consecutive 1 bits are encountered, an extra 0 is added. The extra bit is eventually removed from the d ata by the receiver. Bit Oriented Protocol

14. Bit Oriented Protocol

15. Bit Oriented Protocol Bit stuffing (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in receiver’s memory after destuffing .

16. Flow control refers to the set of procedures used to restrict the amount of data that the sender can send before waiting for acknowledgement. F eedback-based flow control , the receiver sends back information to the sender giving it permission to send more data or at least telling the sender how the receiver is doing R ate-based flow control , the protocol has a built-in mechanism that limits the rate at which senders may transmit data, without using feedback from the receiver. Note: Each receiver has a block of memory called Buffer. Flow Control

17. Error control is both error detection and error correction. It allows the receiver to inform the sender of any frames lost or damaged in transmission and coordinates the retransmission of those frames by the sender. It refers primarily to methods of error detection and retransmission. Any time an error is detected in an exchange, specified frames are retransmitted. This process is called automatic repeat request (ARQ). Error control in the data link layer is based on automatic repeat request, which is the retransmission of the data. Error Control

18. Single Bit Error : It means only one bit of data unit is changed from 1 to 0 or from 0 to 1 Burst Error: It means two or more bits in data unit are changed from 1 to 0 from 0 to 1. In burst error, it is not necessary that only consecutive bits are changed. The length of burst error is measured from first changed bit to last changed bit Types of Errors

19. Error Detection: Redundancy: Exact count Encoding: Error Correction : When the error is discovered, the receiver asks the sender to retransmit the same data. Receiver can use an error correcting codes to detect and correct errors.

20. Four different error-correcting codes: 1. Hamming codes. 2. Binary convolutional codes. 3. Reed-Solomon codes. 4. Low-Density Parity Check codes . All of which add redundancy to transmitted data to detect and correct errors. Error-Correcting Codes

21. • Block Codes: Use a fixed number of data bits (m) and compute a fixed number of check bits (r) to form an (n, m) code, where n = m + r. • Systematic Codes: Transmit the original data bits directly along with check bits. • Linear Codes: Check bits are computed using linear operations, commonly XOR or modulo-2 addition. Error-Correcting Codes

22. The codeword refers to the full n-bit sequence (data + check bits), and the code rate (m/n) indicates the fraction of the codeword that contains actual data. Lower rates (e.g., 1/2) are used in noisy environments, while higher rates (closer to 1) are suitable for cleaner channels. Error-Correcting Codes

23. To handle errors in data transmission, we must first understand what an error is. Given any two codewords that may be transmitted or received—say , 10001001 and 10110001—it is possible to determine how many corresponding bits differ. In this case, 3 bits differ. To determine how many bits differ , just XOR the two codewords and count the number of 1 bits in the result . Error-Correcting Codes

24. For example: The number of bit positions in which two codewords differ is called the Hamming distance (Hamming, 1950). Its significance is that if two codewords are a Hamming distance d apart, it will require d single-bit errors to convert one into the other . Error-Correcting Codes

25. The Hamming distance is crucial because: d single-bit errors are needed to transform one codeword into another that is d units away. The minimum Hamming distance among all valid codewords in a code determines its error-detecting and correcting capability . Error-Correcting Codes

26. Since only a small subset of all possible bit combinations are valid codewords (due to the check bits), the codewords are sparsely distributed . This spacing allows: Detection of up to d errors with a code of Hamming distance d+1 Correction of up to d errors with a code of Hamming distance 2d+1 This ensures that even if some bits are altered during transmission, the original codeword can still be accurately identified. Error-Correcting Codes

27. Hamming codes, introduced by Hamming in 1950, achieve a theoretical lower limit for error correction. In this scheme: Codeword bits are numbered starting from 1 (left to right). Bits at power-of-2 positions (1, 2, 4, 8, etc.) are reserved as check bits. Remaining positions (3, 5, 6, 7, 9, etc.) are filled with data bits. Error-Correcting Codes

28. For example, an (11,7) Hamming code uses 7 data bits and 4 check bits. Each check bit ensures the even parity (or odd, depending on the design) of a specific group of bits—including itself. To determine which check bits are responsible for a given bit: Convert the bit's position number to the sum of powers of 2. The bit is included in parity checks of those positions corresponding to the powers in the sum. Error-Correcting Codes

29. Example: • Bit 11 = 1 + 2 + 8 → Checked by bits 1, 2, and 8. • Bit 29 = 1 + 4 + 8 + 16 → Checked by bits 1, 4, 8, 16. In the example given, the check bits are computed for a message representing the ASCII letter "A", using even parity. Hamming codes have a Hamming distance of 3, enabling them to correct single-bit errors and detect double-bit errors. Error-Correcting Codes

30. The specific numbering of data and check bits is essential for error detection and correction during decoding. When a codeword is received: The receiver recomputes the check results using the received bits. If all check results are zero , the codeword is valid. If not, an error is detected, and the set of check results forms an error syndrome . This syndrome helps locate the position of the error. For example, if the check results are 0101, the error is in bit 5 (since 4 + 1 = 5). Flipping bit 5 corrects the error, and the message (e.g., ASCII ‘A’ ) is retrieved after discarding the check bits. Error-Correcting Codes

31. Error-Correcting Codes Use of a Hamming code to correct burst errors.

32. Error-Correcting Codes

33. 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 Error Detecting codes

34. Also known as Parity Check. In this method, a redundant bit also called parity bit is added to each data unit. This method includes even parity and odd parity. Even parity means the total number of 1s in data is to be even and odd parity means the total number of 1s in data is to be odd .   Vertical Redundancy Check 

35. Example -  If the source wants to transmit data unit 1100111 using even parity to the destination. The source will have to pass through Even Parity Generator. 

36. Parity generator will count number of 1s in data unit and will add parity bit . In the above example, number of 1s in data unit is 5, parity generator appends a parity bit 1 to this data unit making the total number of 1s even i.e 6 which is clear from above figure. Data along with parity bit is then transmitted across the network. In this case, 11001111 will be transmitted.

37. At the destination, This data is passed to parity checker at the destination. The number of 1s in data is counted by parity checker. If the number of 1s count out to be odd, e.g. 5 or 7 then destination will come to know that there is some error in the data. The receiver then rejects such an erroneous data unit.

38. Also known as 2-D parity check. In this method, data which the user want to send is organized into tables of rows and columns. A block of bit is divided into table or matrix of rows and columns. In order to detect an error, a redundant bit is added to the whole block and this block is transmitted to receiver. The receiver uses this redundant row to detect error. After checking the data for errors, receiver accepts the data and discards the redundant row of bits.  Longitudinal Redundancy Check (LRC)

39. Example :  If a block of 32 bits is to be transmitted, it is divided into matrix of four rows and eight columns which as shown in the following figure :

40. Interleaving is a general technique to convert a code that detects (or corrects ) isolated errors into a code that detects (or corrects) burst errors.

41. The cyclic redundancy check, or CRC, is a technique for detecting errors in digital data,. The CRC ( Cyclic Redundancy Check ), also known as a polynomial code Polynomial codes are based upon treating bit strings as representations of polynomials with coefficients of 0 and 1 only. For example, 110001 has 6 bits and thus represents a six-term polynomial with coefficients 1, 1, 0, 0, 0, and 1: 1x5 + 1x4 + 0x3 + 0x2 + 0x1 + 1x0. Cycle Redundancy Check (CRC)

42. Polynomial arithmetic is done modulo 2, according to the rules of algebraic field theory. It does not have carries for addition or borrows for subtraction. Both addition and subtraction are identical to exclusive OR. . 10011011 00110011 11110000 01010101 + 11001010 + 11001101 − 10100110 − 10101111 01010001 11111110 01010110 11111010 Cycle Redundancy Check (CRC)

43. Let r be the degree of G(x). Append r zero bits to the low-order end of the frame, so it now contains m + r bits and corresponds to the polynomial x r M (x). Divide the bit string corresponding to G(x) into the bit string corresponding to x r M (x), using modulo 2 divisions. Subtract the remainder (which is always r or fewer bits) from the bit string corresponding to x r M (x) using modulo 2 subtractions. The result is the check summed frame to be transmitted. Call its polynomial T(x). Algorithm for CRC

44. T he calculation for a frame 1101011111 using the generator G(x) = x4 + x + 1.

45. At sender side calculation of CRC:

46. At receiver side calculation of CRC

47. one’s complement internet checksum It is  a method used to detect errors in data transmission.  It's a simple form of error detection that involves summing the data (often in 16-bit chunks) using one's complement arithmetic and then complementing the result to create a checksum value. This checksum is sent along with the data.  The receiver then performs the same checksum calculation on the received data and checksum. If the result is all zeros, the data is considered error-free.

48. one’s complement internet checksum Detailed explanation: 1. Sender's Side: Data Division:  The data to be transmitted is divided into 16-bit words (or chunks).  One's Complement Sum:  The 16-bit words are added together using one's complement arithmetic. This means that any carry bit generated during the addition is wrapped around and added to the least significant bit.  Checksum Calculation:  The one's complement of the sum is calculated. This is the checksum value.  Transmission:  The checksum is transmitted along with the original data. 

49. one’s complement internet checksum 2 . Receiver's Side: Data Division and Sum:  The received data, including the checksum, is divided into 16-bit words and added together using one's complement arithmetic. One's Complement:  The one's complement of the sum is calculated. Error Detection:  If the result of the one's complement is all zeros, it indicates that the data was likely received without errors. If the result is not all zeros, it suggests that an error occurred during transmission and the data is discarded. 

50. one’s complement internet checksum Example: Let's say we have the following 16-bit words: 0110 1001 1001 0110 and 1100 0011 1100 0011.  1. Sender: Add:  (0110100110010110 + 1100001111000011) = 1001011101011001. Carry:  There's a carry-over bit (1) which is added to the least significant bit: 001011101011001 + 1 = 0010111010110100. Complement:  The one's complement is 1101000101001011. Checksum:  1101000101001011 is the checksum.

51. one’s complement internet checksum 2. Receiver: Add:  (0110100110010110 + 1100001111000011 + 1101000101001011) = 1111111111111111. Carry:  There's a carry (1) which is added: 1111111111111111 + 1 = 0000000000000000 (all zeros). Complement:  The one's complement is 1111111111111111 which is not zero. This indicates no errors have occurred.

52. Services Provided to the Network Layer The function of the data link layer is to provide services to the network layer. The principal service is transferring data from the network layer on the source machine to the network layer on the destination machine . On the source machine is an entity, call it a process, in the network layer that hands some bits to the data link layer for transmission to the destination.

53. Services Provided to the Network Layer The job of the data link layer is to transmit the bits to the destination machine so they can be handed over to the network layer there, as shown in Fig (a). The actual transmission follows the path of Fig (b), but it is easier to think in terms of two data link layer processes communicating using a data link protocol.

54. Services Provided to the Network Layer The data link layer can be designed to offer various services. The actual services that are offered vary from protocol to protocol. Three reasonable possibilities that we will consider in turn are: 1. Unacknowledged connectionless service. 2. Acknowledged connectionless service. 3. Acknowledged connection-oriented service.

55. Services Provided to the Network Layer Unacknowledged connectionless service consists of having the source machine send independent frames to the destination machine without having the destination machine acknowledge them . Ethernet is a good example of a data link layer that provides this class of service. No logical connection is established beforehand or released afterward . If a frame is lost due to noise on the line, no attempt is made to detect the loss or recover from it in the data link layer. This class of service is appropriate when the error rate is very low, so recovery is left to higher layers. It is also appropriate for real-time traffic, such as voice, in which late data are worse than bad data.

56. Services Provided to the Network Layer A cknowledged connectionless service: When this service is offered, there are still no logical connections used, but each frame sent is individually acknowledged. In this way, the sender knows whether a frame has arrived correctly or been lost. If it has not arrived within a specified time interval, it can be sent again. This service is useful over unreliable channels , such as wireless systems. 802.11 ( WiFi ) is a good example of this class of service.

57. Services Provided to the Network Layer Acknowledged connection-oriented service It is the most sophisticated service the data link layer can provide to the network layer. With this service , the source and destination machines establish a connection before any data are transferred . Each frame sent over the connection is numbered, and the data link layer guarantees that each frame sent is indeed received. Furthermore , it guarantees that each frame is received exactly once and that all frames are received in the right order . Connection-oriented service thus provides the network layer processes with the equivalent of a reliable bit stream.

58. Services Provided to the Network Layer Acknowledged connection-oriented service When connection-oriented service is used, transfers go through three distinct phases. In the first phase, the connection is established by having both sides initialize variables and counters needed to keep track of which frames have been received and which ones have not . In the second phase, one or more frames are actually transmitted . In the third and final phase, the connection is released, freeing up the variables, buffers, and other resources used to maintain the connection.

59. Protocols: A network protocol is  a set of established rules that specify how to format, send and receive data There are two types of protocols: Noiseless Channels: Error Free Channels Noisy Channels: Error creating Channels Protocols

60. Simplex Protocol is one that has no flow or error control . it is a unidirectional protocol in which data frames are traveling in only one direction-from the sender to receiver. We assume that the receiver can immediately handle any frame it receives with a processing time that is small enough to be negligible. The data link layer of the receiver immediately removes the header from the frame and hands the data packet to its network layer, which can also accept the packet immediately. In other words, the receiver can never be overwhelmed with incoming frames. Simplex Protocol

61. Design: There is no need for flow control in this scheme. The data link layer at the sender site gets data from its network layer, makes a frame out of the data, and sends it. Sender-site Algorithm for Simplex protoc ol: Simplex Protocol

62. Design: The data link layer at the receiver site receives a frame from its physical layer, extracts data from the frame, and delivers the data to its network layer. Receiver -site Algorithm for Simplex protoc ol: Simplex Protocol

63. It shows an example of communication using this protocol. It is very simple. The sender sends a sequence of frames without even thinking about the receiver. To send three frames, three events occur at the sender site and three events at the receiver site. Note that the data frames are shown by tilted boxes; T he height of the box defines the transmission time difference between the first bit and the last bit in the frame. Example

64. It is data link layer protocol for transmission of frames over noiseless channels. It provides unidirectional data transmission with flow control facilities but without error control facilities. The idea of sto p and wait protocol is straight forward. After transmitting one frame, the sender waits for an acknowledgement before sending the next frame. Stop and Wait Protocol

65. Stop and Wait Protocol

66. Sender site Algorithm

67. Receiver site Algorithm

68. Advantage: Its simplicity. Problems due to lost data Sender waits for ACK for an infinite amount of time. Receiver waits for data an infinite amount of time Problems due to lost ACK. Sender waits for ACK for an infinite amount of time. Problem due to delayed ACK data After timeout on sender side, a delayed ack might be wrongly considered as ACK of some other data packet. Advantage and Problems

69. Sender Side: Send one data frame at a time. Send the next frame only after receiving ACK for the previous frame. Receiver Side: Receive and consume data frame. After consuming the frame, ACK need to be sent (Flow Control) Example

70. Protocols: A network protocol is  a set of established rules that specify how to format, send and receive data so that computer  network endpoints There are two types of protocols: Noiseless Channels: Error Free Channels Noisy Channels: Error creating Channels Protocols

71. Stop-and-Wait Automatic Repeat Request (Stop-and Wait ARQ), adds a simple error control mechanism to the Stop-and-Wait Protocol. To detect and correct corrupted frames, we need to add redundancy bits to our data frame. When the frame arrives at the receiver site, it is checked and if it is corrupted, it is silently discarded. The detection of errors in this protocol is manifested by the silence of the receiver. Lost frames are more difficult to handle than corrupted ones. The solution is to number the frames. Stop and Wait ARQ Protocol

72. When the receiver receives a data frame that is out of order, this means that frames were either lost or duplicated. The lost frames need to be resent in this protocol. If the receiver does not respond when there is an error, how can the sender know which frame to resend? To remedy this problem, the sender keeps a copy of the sent frame. At the same time, it starts a timer. If the timer expires and there is no ACK for the sent frame, the frame is resent, the copy is held, and the timer is restarted. Since the protocol uses the stop-and-wait mechanism, there is only one specific frame that needs an ACK even though several copies of the same frame can be in the network. Stop and Wait ARQ Protocol

73. Sequence Numbers T he protocol specifies that frames need to be numbered. A field is added to the data frame to hold the sequence number of that frame. For example, if we decide that the field is m bits long, the sequence numbers start from 0, go to 2m - 1, and then are repeated. Acknowledgment Numbers The acknowledgment numbers always announce the sequence number of the next frame expected by the receiver. For example, if frame 0 has arrived safe and sound, the receiver sends an ACK frame with acknowledgment 1 (meaning frame 1 is expected next). If frame 1 has arrived safe and sound, the receiver sends an ACK frame with acknowledgment 0 (meaning frame 0 is expected). Stop and Wait ARQ Protocol

74. Stop and Wait ARQ Protocol

75. Sender Side Algorithm

76. Sender Site Algorithm

77. Receiver site Algorithm

78. Example

79. Previous protocols supported only one-way (simplex) data transfer. Real-world communication often requires two-way (full-duplex) data exchange. A basic solution is to run two separate simplex protocols , one in each direction. This method causes the reverse channel to be underutilized , mostly carrying acknowledgements, leading to wasted capacity . Sliding window Protocols

80. Combining data and control frames on a single link improves efficiency over using two physical links. Instead of sending an immediate ACK , the receiver waits for the next data packet from the network layer. The acknowledgement is included in the header of the outgoing data frame. This method, called piggybacking , allows ACKs to "ride along" with data , saving bandwidth and reducing overhead . The next three protocols are bidirectional protocols that belong to a class called sliding window protocols . A One-Bit Sliding Window Protocol A Protocol Using Go-Back-N A Protocol Using Selective Repeat Sliding window Protocols

81. The sender maintains a sending window of sequence numbers for frames it is allowed to transmit. Frames within this window are considered "in-flight" until acknowledged. The receiver maintains a receiving window for frames it is permitted to accept. Sending and receiving windows may differ in size and boundaries. In some protocols, window sizes are fixed , while in others they may dynamically adjust . This mechanism helps achieve efficient and reliable flow control over the communication link. Sliding window Protocols

82. A window size of 1 means the sender can send only one frame at a time . This behaves like the stop-and-wait protocol, where the sender waits for an acknowledgement before sending the next frame . Next_frame_to _ send tells which frame the sender is trying to send . Similarly , frame_expected tells which frame the receiver is expecting. In both cases, 0 and 1 are the only possibilities. A One-Bit Sliding Window Protocol

83. A One-Bit Sliding Window Protocol

84. Only one data link layer initiates communication by sending the first frame. This sender calls the to-physical-layer and start-timer procedures outside the main loop. The sender fetches a packet from its network layer, builds a frame, and transmits it. Upon arrival, the receiver checks for duplicates , as in earlier protocols. If the frame is new and expected , it's delivered to the network layer and the receiver's window advances . A One-Bit Sliding Window Protocol

85. A One-Bit Sliding Window Protocol The acknowledgement field indicates the last correctly received frame ; if it matches the sender’s sequence number, the sender proceeds with the next frame. In case of mismatch, the sender retransmits the same frame until acknowledged correctly. During a timeout or duplicate frame scenario , the receiver rejects unexpected frames but continues sending acknowledgements. Despite repeated timeouts or duplicates, no duplicate packets are delivered , and no packets are skipped. The protocol is resilient to frame loss, duplication, and premature timeouts , ensuring correct, deadlock-free delivery .

86. A One-Bit Sliding Window Protocol A peculiar issue arises if both sender and receiver initiate communication simultaneously . Their first frames may cross in transit , leading to unexpected duplicate frames , even without transmission errors. In normal operation (one side starts first), each frame is unique and correctly accepted . Simultaneous starts or premature timeouts can result in duplicate frame deliveries to the data link layer. These duplicates waste bandwidth , even though the protocol still functions correctly.

87. A One-Bit Sliding Window Protocol

88. N is the sender window size It uses the concept of protocol pipelining ie . the sender can send multiple frames before receiving the acknowledgment for the first frame. There are finite number of frame s and the frames are numbered in a sequential manner . The number of frames that can be sent depends on the window size of the sender. If the acknowledgement of a frame is not received within an agreed upon time period, all frames in the current window are transmitted. Go-back-N ARQ Protocol

89. The size of the sending window determines the sequence number of the outbound frames. N – senders window size. For example, if the sending window size is 4, then the sequence numbers will be 0,1,2,3, 0,1,2,3, and so on. The number of bits in the sequence number is 2 to generate the binary sequence 00, 01,10,11. Go-back-N ARQ Protocol

90. Go-back-N ARQ Protocol

91. Based on sliding window If no error, ACK as usual with next frame expected Use window to control number of outstanding frames If error, reply with rejection Discard that frame and all future frames until error frame received correctly Transmitter must go back and retransmit that frame and all subsequent frames Go-back-N ARQ Protocol

92. Go-back-N ARQ Protocol

93. Go-back-N ARQ Protocol

94. Go-back-N ARQ Protocol

95. Station A needs to send a message consisting of 9 packets to station B using a sliding window (window size 3( and go-back-n error control strategy. All packets are ready and immediately available for transmission. If every 5 th packet that A transmits gets lost (but no ACKs from B ever get lost), then what is the number of packets that A will transmit for sending the message to B? Go-back-N ARQ Protocol

96. Go-back-N ARQ Protocol

97. In Selective repeat ARQ Protocol, Only the erroneous or lost frames are retransmitted , while correct frames are received and buffered. The receiver while keeping track of sequence numbers, buffers the frames in memory and sends NACK for only frame which is missing or damaged. The sender will send/retransmit packet for which NACK is received. Selective Repeat ARQ Protocol

98. Selective Repeat ARQ Protocol

99. Host A wants to send 10 frames to Host B. The hosts agreed to go with SR ARQ. How many numbers of frames are transmitted by Host A if every 6 th frame that is transmitted by host A is either corrupted or lost? Also compare the number of transmissions of SR ARQ with Go-back-4 ARQ. Selective Repeat ARQ Protocol

100. Frames transmitted by Host A No: of frames transmitted in Go Back N protocol is : 17 No: of frames transmitted in Selective repeat protocol is : 11 Selective Repeat ARQ Protocol

101. (3.3.5) A Sliding Window Protocol Using Selective Repeat (a) Initial situation with a window size seven. (b) After seven frames sent and received, but not acknowledged. (c) Initial situation with a window size of four. (d) After four frames sent and received, but not acknowledged.

102. HDLC and PPP

103. The Data Link Layer in the Internet A home personal computer acting as an internet host. Technology like Ethernet cannot provide “high-level” functionality like connection management and parameter negotiation.

104. 104 Point to Point Data Link Control One sender, one receiver, one link: easier than broadcast link: No Media Access Control No need for explicit MAC addressing E.g., dialup link, ISDN line Popular point-to-point and high-level DLC protocols: PPP (point-to-point protocol) HDLC: High level data link control (Data link used to be considered “high layer” in protocol stack). HDLC is also used in multi-point links (one station many receivers) These protocols can often be run over other data link technologies providing best of both worlds E.g., PPPoE , HDLC encapsulation by Ethernet

105. 105 PPP Design Requirements [RFC 1557] Functionality : (similar to link layer services + extra management functions) Packet framing - encapsulation of network-layer datagram in data link frame Multi-protocol - carry network layer data of any network layer protocol (not just IP) at same time ability to demultiplex upwards Bit transparency - must carry any bit pattern in the data field (even if underlying channel can't) Error detection - not correction

106. 106 PPP Design Requirements (cont.) The extra stuff: Connection liveness: detect, signal link failure to network layer Network layer address negotiation: endpoint can learn/configure each other’s network address and other characteristics. Authentication: who are you (or at least whose account do I bill for your dial-in time?) This information is used by traffic management software to control bandwidth to individual subscribers Management features: loopback detection

107. 107 PPP non-requirements No error correction/recovery (modems do one layer FEC, one layer packetization + retransmission “under the covers” anyway; other technologies are pretty reliable) No flow control Out of order delivery OK Error recovery, flow control, data re-ordering all related to higher layers!

108. 108 PPP Data Frame Flag: delimiter (framing) Address: ignored. (historical) Control: ignored. (historical) Protocol: upper layer protocol to which frame delivered (e.g., PPP-LCP, IP, IPCP, etc)

109. 109 PPP Data Frame info: upper layer data being carried check: cyclic redundancy check for error detection

110. Byte Stuffing flag byte pattern in data to send flag byte pattern plus stuffed byte in transmitted data

111. 111 PPP Data Control Protocol Before exchanging network-layer data, data link peers must Configure PPP link (max. frame length, authentication) Learn/configure network layer information for IP: carry IP Control Protocol (IPCP) msgs (protocol field: 8021) to configure/learn IP address

112. 112 Where does PPP get used? Dial-up – PPP over async serial, over modem ADSL – PPP over Ethernet Backbone – Packet over SONET (POS) Why? Framing (dialup, POS) Efficiency (POS) Authentication, address negotiation ( PPPoE )

113. High-Level Data Link Control (HDLC) HDLC was defined by ISO for use on both point-to-point and multipoint data links. It supports full-duplex communication Other similar protocols are Synchronous Data Link Control (SDLC) by IBM Advanced Data Communication Control Procedure (ADCCP) by ANSI Link Access Procedure, Balanced (LAP-B) by CCITT, as part of its X.25 packet-switched network standard

114. HDLC Overview Broadly HDLC features are as follows: Reliable protocol selective repeat or go-back-N Full-duplex communication receive and transmit at the same time Bit-oriented protocol use bits to stuff flags occurring in data Flow control adjust window size based on receiver capability Uses physical layer clocking and synchronization to send and receive frames

115. HDLC Overview Defines three types of stations Primary Secondary Combined Defines three types of data transfer mode Normal Response mode Asynchronous Response mode Asynchronous Balanced mode Three types of frames Unnumbered information Supervisory

116. HDLC The three stations are : Primary station Has the responsibility of controlling the operation of data flow the link. Handles error recovery Frames issued by the primary station are called commands . Secondary station Operates under the control of the primary station. Frames issued by a secondary station are called responses . The primary station maintains a separate logical link with each secondary station. Combined station Acts as both as primary and secondary station. Does not rely on other for sending data

117. HDLC Primary Secondary Secondary Commands Responses Combined Combined commands/Responses Unbalanced Mode Balanced mode

118. HDLC The three modes of data transfer operations are Normal Response Mode (NRM) Mainly used in terminal-mainframe networks. In this case, Secondaries (terminals) can only transmit when specifically instructed by the primary station in response to a polling Unbalanced configuration, good for multi-point links Asynchronous Response Mode (ARM) Same as NRM except that the secondaries can initiate transmissions without direct polling from the primary station Reduces overhead as no frames need to be sent to allow secondary nodes to transmit Transmission proceeds when channel is detected idle , used mostly in point-to-point-links Asynchronous Balanced Mode (ABM) Mainly used in point-to-point links, for communication between combined stations

119. Non-operational Modes Normal Disconnected Mode Asynchronous Disconnected Mode Both the above modes mean that the secondary node is logically disconnected from the primary node Initialization Mode A node negotiates transmission parameters with the other node E.g., flow control information Parameters negotiated in this mode are used during any of the data transfer modes

120. Data Link Control HDLC frame structure (a) Frame Format (b) Control field format

121. HDLC There are three different classes of frames used in HDLC Unnumbered frames , used in link setup and disconnection, and hence do not contain ACK. Information frames , which carry actual information. Such frames can piggyback ACK in case of ABM Supervisory frames , which are used for error and flow control purposes and hence contain send and receive sequence numbers

122. HDLC There are four different supervisory frames SS=00, Receiver Ready (RR), and N(R) ACKs all frames received up to and including the one with sequence number N(R) - 1 SS=10, Receiver Not Ready (RNR), and N(R) has the same meaning as above SS=01, Reject ; all frames with sequence number N(R) or higher are rejected, which in turns ACKs frames with sequence number N(R) -1 or lower. SS=11, Selective Reject ; the receive rejects the frame with sequence number N(R)

123. HDLC The unnumbered frames can be grouped into the following categories: Mode-setting commands and responses Recovery commends and responses Miscellaneous commands and responses