Neurotransmitters and Synapses Quiz

Data Link Layer

• The data link layer transforms the physical layer into a link responsible for node-to-node communication.
• Specific responsibilities include framing, addressing, flow control, error control, and media access control.
• It provides services to the network layer, such as packetizing and media access control.
• It receives services from the physical layer.
• The function is to transfer data from the network layer on the source machine to the network layer on the destination machine.

DLL Design Issues

• Services Provided to the Network Layer: The network layer needs to send packets to its neighbors without needing to worry about the process of getting the packets there intact.
• Framing: Grouping physical layer bits into units known as frames which represent packets or messages.
• Error Control: Sender checksums the frame and transmits checksum with data. The receiver re-computes checksum and compares to the received value to check for any errors.
• Flow Control: Prevents a fast sender from overwhelming the slower receiver.

Data Link Layer Design Issues

• Provides a well-defined service interface to the network layer.
• Deals with transmission errors.
• Regulates the flow of data so that slow receivers are not swamped by fast senders
• Takes packets from the network layer and encapsulates them into frames for transmission to ensure transmission integrity. Each frame has a header, a payload field for the packet, and a trailer.

Services Provided to The Network Layer

• The primary service is transferring data from the network layer on the source machine to the network layer on the destination machine.
• The data link layer can be designed to offer various services.
• Common data link services: -Unacknowledged connectionless service -Acknowledged connectionless service -Acknowledged connection-oriented service

Unacknowledged Connectionless Service

• Source machine sends independent frames to the destination machine without acknowledging.
• No logical connection is established or released.
• If a frame is lost due to noise, no attempt is made to recover in the data link layer.
• Most LANs use this service.
• Appropriate for low error rate scenarios and real-time traffic, where late data is worse than bad data.

Acknowledged Connectionless Service

• Frames are individually acknowledged.
• Sender knows if a frame has arrived correctly.
• If a frame doesn't arrive within a specified time, it is resent.
• Useful for unreliable channels (e.g., wireless systems).
• Optimization rather than a requirement for individual frame acknowledgment. Makes entire packet delivery much faster in reliable channels (e.g., fiber).

Acknowledged Connection-Oriented Service

• Source and destination machines establish a connection before any transfers.
• Every frame sent is numbered.
• The data link layer guarantees that each frame is received exactly once, and in the correct order.
• Transfers go through three phases: connection establishment, data transmission, and connection release.

Placement of Data Link Protocol

• Frame and packet handling by data link layer and routing process in a router.
• Data link protocol handles frames, while a routing process manages packets.

Framing

• DLL translates the physical layer's raw bit stream to discrete units (messages) called frames.
• The receiver must be able to detect frame boundaries, i.e., how to identify the beginning and end of a frame.
• Methods for framing:
  • Character Count -Flag byte with Byte Stuffing
  • Starting and Ending Flag with Bit Stuffing
  • Encoding Violations

Framing - Character Count

• A field in the header specifies the number of characters in the frame.
• Receiver knows where the frame ends.
• Vulnerable to transmission errors (i.e., garbled count).

Framing - Byte Stuffing

• Uses reserved characters (or escape sequences) to signal start and end.
• Ensures proper frame synchronization after an error.
• Problem: Handling cases where the escape sequence itself may appear within the data. The solution is to replace every occurrence of the escape sequence with a special two-character sequence in the frame.

Framing - Bit Stuffing

• Inserts a 0 bit after every five consecutive 1 bits within a frame.
• Receiver detects and removes the extra 0 bits for proper frame synchronisation.
• Detects frames based on recurring patterns of 0s and 1s.

Physical Layer Coding Violations

• Some networks use redundancy, like encoding each bit into two physical bits, for ease of bit boundary detection.

Error Control

• Ensures all frames are correctly delivered to the destination.
• Acknowledgements (ACKs): The receiver sends an acknowledgment message to the sender when it correctly receives a frame.
• Negative Acknowledgements (NACKs): The receiver sends a NACK to notify the sender of an error in the received frame.
• Timers: The sender sets a timer to resend a frame if an acknowledgment is not received within a certain amount of time.

Flow Control

• Sender throttling the transmission rate to match that of the receiver.
• Feedback-based flow control: Receiver sends information to sender about its processing capacity.
• Rate-based flow control: Protocol limits the rate at which the sender transmits data.

Error Correction and Detection

• Error detection and correction is critical for accurate data transmission, storage, and retrieval.
• Redundancy bit addition is needed for detection and correction.
• Types of errors: single bit error, burst error.

Types of Errors

• Single-bit error: One bit in a data unit changes state (e.g., 1 to 0, or 0 to 1)
• Burst error: Two or more bits in a data unit change state without being related in positions.

Error Detection vs. Error Correction

• Error detection codes include enough redundancy bits to detect errors, and usually employ acknowledgements and retransmissions for recovery.
• Error correction codes have enough redundancy to detect and correct errors.

Error Detection

• Error detection means deciding if received data is correct without a copy of the original data.
• It uses the concept of redundancy, adding extra bits to detect errors.
• Methods include VRC (Vertical Redundancy Check), LRC (Longitudinal Redundancy Check), CRC (Cyclic Redundancy Check), and Checksum.

Vertical Redundancy Check (VRC)

• Appends a single bit to the end of the data block to ensure an even number of 1s in the block.
• Also known as parity check.
• Detects odd number of errors in a data block.

Longitudinal Redundancy Check (LRC)

• Adds a block check character (BCC) to the data block (instead of a bit, like VRC)
• Checked longitudinally through the message.
• Detects >10 (burst) errors but less error-capable at detecting single-bit errors.

Two-Dimensional Parity Check

• Checks VRC (vertical parity) on each character to determine whether to accept based on LRC (longitudinal parity).

Cyclic Redundancy Check (CRC)

• Detects errors in data transmission.
• Includes checksum, appended to the transmitted message for the receiver to examine.
• Uses polynomial arithmetic for calculation.
• Easily implemented with hardware (shift registers, XOR for add/sub).

Generator Polynomial

• A polynomial for calculating checksum bits.
• Must fulfill certain requirements involving coefficient terms.

CRC Calculation

• The transmitter generates an n bit sequence ensuring the resulting frame of (k+n) bits is divisible by a predetermined number.

Cyclic Redundancy Check

• Calculates checksum given message and generator polynomials.

Sending CRC Check

• The sender multiplies the message polynomial by a specified power of x
• Divides the result by the generator polynomial
• Keeps the remainder as the checksum
• Forms a new polynomial by combining the message and checksum and transmits it.

Receiving CRC Check

• The receiver receives the frame
• Divides the frame by the generator polynomial.
• If the remainder is zero, the frame is considered valid; otherwise, it is discarded.

Example of CRC

• Shows a practical CRC example given a message polynomial, a generator polynomial and a required checksum length.

Burst Error Correction

• Hamming code cannot correct burst errors directly.
• It is possible to rearrange data and apply Hamming code to single error correction, or use methods to correct for burst errors.

Hamming Code

• Detects/corrects single-bit errors.
• Used to calculate error correcting bits (redundancy bits) for a given message.

Sliding Window Protocols

• Bidirectional protocols, manage sending and receiving frames within a window.
• Protocols include one-bit sliding window, Go-Back-N, and Selective Repeat.

Sliding Window Protocols- Sender & Receiver Windows

• Sender window: set of sequence numbers of frames that can be sent at any time.
• Receiver window: set of sequence numbers of frames that are ready to be accepted at any time.
• They are implemented with upper and lower limits - fixed or variable size.
• Outstanding frames are those that have been sent but not yet acknowledged.

Sliding Window Protocols – Control Variables

• The sender manages 3 variables: the recent frame (S), the first frame (Sp), and the last frame (S1).
• The receiver has one variable (R), the sequence number of the expected next frame in the transmission.

Go Back N Protocol (GBN)

• Improves stop-and-wait protocol efficiency.
• Allows sending multiple frames before waiting for acknowledgment.
• Receiver discards frames out of order.
• Resends all out-of-order frames from the error frame onward after a timer expires for one.

Go Back N ARQ, Sender Window Size

• Sender window must be smaller than 2m.
• Receiving window is usually 1, all ACKs are lost in the case that the transmitter sends more than m frames; therefore the transmitter sends the frames from the erroneous frame and the next frames
• Receiver can accept only frames in correct order (i.e., 0 ,1, 2... and so on, ).

Selective Repeat Protocol

• Resends only the erroneous frames.
• More memory-efficient compared to GBN(Go Back N) sliding windows.
• Uses a negative acknowledgment (NAK) to the sender when an erroneous frame is detected.
• Receiving window size should be larger than 1.

Selective Repeat in Action

• Illustrates a practical example of how Selective Repeat ARQ works given values for frames, sequence numbers, etcetera.

Acknowledgement Timer

• Deals with the issue of reverse traffic being light and no reverse traffic.
• In case there is no reverse traffic before timeout, a separate acknowledgment is sent.
• Crucial for the condition that the acknowledge timeout is less than the data frame timeout.

Checksum

• Error detection scheme used in IP, TCP, and UDP.
• Divides data into segments, sums them using 1's complement arithmetic.
• Complements the sum to get checksum and sends it with data.
• Receiver performs the same operations to check the data's integrity.
• Detects errors involving odd numbers of bits, as well as most errors involving even numbers of bits.

Checksum Example

• Illustrates an example of how checksum works with data segments.
• Shows how sender and receiver calculate checksum and how to verify for correctness.

Checksum Vs CRC

• CRC is more thorough compared to checksum in detecting and reporting errors.
• Checksum is more commonly used and older compared to CRC.
• Checksum is mainly employed for checking single-bit errors (changes in data) while CRC can detect and check double-bit errors.
• CRC can detect more errors than Checksum due to its more complex computation function.
• CRC is mainly used for data evaluation in analog transmissions while Checksum is used for checking data/messages when implementing software.

Error Correction

• Once errors are discovered, they need to be corrected.
• Retransmission (Backward Error Correction): Simplest technique that retransmits a frame until it is successfully acknowledged.
• Forward Error Correction (FEC): The receiving device corrects the errors immediately without asking for retransmission.

Hamming Code

• Calculates Hamming distance from two codewords.
• Minimizes the minimum Hamming distance between any two legal codewords.
• To detect d single bit errors, the minimum Hamming distance needs to be greater than (d+1).