Untitled

Computer Networks (CSC305)

Course Outline

• Overview of Data Communication and Networking
• Physical Layer
• Data Link Layer
  • Logical Link Control (LLC)
  • Medium Access Control (MAC)
• Network Layer
• Transport Layer
• Application Layer

OSI Reference Model

• The Open Systems Interconnection (OSI) model describes how data moves between network applications through a series of layers.
• Media layers consist of Physical, Data Link and Network.
• Host layers consist of Transport, Session, Presentation and Application.

OSI Layers and Functions

• Application Layer:
  • Enables network processes to access applications.
  • Supports user-end APIs, resource sharing, and remote file access.
  • Data type: Data.
• Presentation Layer:
  • Translates data, handles character encoding, encryption/decryption, and data compression.
  • Data type: Data.
• Session Layer:
  • Establishes, maintains, and gracefully shuts down sessions.
  • Data type: Data.
• Transport Layer:
  • Provides reliable end-to-end communication.
  • Handles segmentation, flow control, acknowledgement, and multiplexing.
  • Data type: Segment.
• Network Layer:
  • Determines path, provides logical addressing, routing, and traffic control.
  • Data type: Packet.
• Data Link Layer:
  • Ensures reliable node-to-node transmission of frames.
  • Uses MAC and LLC sublayers
  • Provides physical addressing.
  • Data type: Frames.
• Physical Layer:
  • Transmits/receives binary bit streams over a physical medium.
  • Handles encoding/decoding at bit level.
  • Data type: Bits.

Data Link Layer Responsibilities

• The data link layer is responsible for node-to-node communication.
• Source hosts' data-link layer only encapsulates data.
• Destination hosts' data-link layer only de-capsulates data.
• Intermediate nodes must both encapsulate and de-capsulate data.
• Packet encapsulation comprises adding a header (H2) before the data packet.
• Packet de-capsulation comprises removal of the encapsulation/header (H2) after the data extraction.
• Logical Link Control (LLC) and Media Access Control (MAC) are sub-layers

Data Link Layer | Logical Link Control (LLC)

• Deals with procedures for communication between two adjacent nodes, regardless of whether the link is dedicated or broadcast.

Framing

• Separates messages from source to destination with sender and receiver addresses.

LLC Framing Considerations

• Framing is used by the data-link layer to pack bits into frames, ensuring each frame is distinguishable from another.
• The physical layer provides bit synchronization to ensure the sender and receiver use the same bit durations and timing.
• Framing separates a message from source to destination by adding a sender address and a destination address.
• Framing too large would make flow and error control inefficient with single-bit errors requiring retransmission of whole frame.
• Frames can be of fixed or variable size.
  • Fixed-size framing eliminates the need to define frame boundaries.
  • Variable-size framing requires a way to define the end of one frame and the beginning of the next.
• A frame is composed of four fields:
• Kind indicates whether the frame contains data or control information.
• Seq indicates the sequence number of the frame.
• Ack indicates the acknowledgement of a frame.
• Info is used only in case of data frame and contains a single packet.
• The packet from the network layer is passed to the data link layer for the inclusion in to 'info' field of an outgoing frame.
• When the frame arrives at the destination, the data link layer extracts the packet from the frame and passes the packet to the network layer.

Framing Byte Count

• Involves using a field in the header to specify the number of characters in the frame.
• The receiving data link layer determines how many characters to expect following the header based on the count.
• Character count can be corrupted by a transmission error, so this method is rarely used.

Framing Character or Byte Stuffing

• Gets around resynchronization problems through the start and the end of each frame with special bytes.
• To separate one frame from the next, an 8-bit (1-byte) FLAG is added to the beginning and the end of a frame.
• If the receiver ever loses synchronization, it can just search for the FLAG byte to find the end of the current frame.
• Two consecutive FLAG bytes indicate the end of one frame and start of the next one.
• If the FLAG bytes bit pattern may occur in the text, a special byte (ESC) might be stuffed into the data (byte-stuffing).
• A character or byte-stuffing strategy was added to character-oriented framing A
• To prevent the FLAG byte pattern from being misinterpreted when it occurs within the data, an escape byte (ESC) is inserted before it.
• When the receiver encounters the ESC character, it removes it from the data section and treats the next character as data, not as a delimiting flag.

Framing Bit Stuffing

• The byte-stuffing framing is closely tied to the use of 8-bit characters (only ASCII).
• Each frame begins and ends with a special bit pattern called a flag (01111110).
• Whenever the sender's data link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream, this is called BIT STUFFING.
• When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically de-stuffs the 0 bit.

Framing Physical Layer Coding Violations

• Applicable to networks in which the encoding on the physical medium contains some redundancy.
• Some LANs encode 1 bit of data by using 2 physical bits.
• A 1 bit is represented as a high-low pair
• A 0 bit is represented as a low-high pair.
• Combinations high-high and low-low are unused data combinations.

Flow Control

• Flow Control involves a set of procedures to tell the sender how much data it can transmit before it must wait for an acknowledgement from the receiver.
• Receiving device needs to inform the sending device before limits are to request sending device send fewer frames or stop temportarily.
• Receiving devices have limited speeds of processing data.

Stop-and-Wait protocol

• Sender waits for acknowledgements after every frame it sends.
• Next frame is sent when an acknowledgement is received for the previously sent frame.
• Each frame is checked and acknowledged, and the protocol is simple: this protocol is slow/inefficient
• Maximum utilization of the Stop-and-Wait protocol is defined by the following formula: U = n * tframe / n* (2 * tprop+tframe)
• U = 1 / 1+2a
• where a= (Rd) / (VL)
• "R" is referring to data rate or bits per second
• "d" is referring to distance of link such as KMs or meters
• "V" is referring to Velocity of Propagation which "V" is 3 multiplied 10 to the power of 8 meters per second in air or space which is 0.67 times speed of light in cable
• "L" is referring to Length of the frame in the network
• U = 1/ 1+ 2a , Frame Size > Link Length Propagation Time < Transmission Time
• U = 1/ 1+ 2a , Frame Size < Link Length ,Propagation Time > Transmission Time

Sliding Window Protocol

• Supports transmitting data in both directions (Full Duplex).
• Two separate communication channels can be used, but the bandwidth of the reverse channel would almost be entirely wasted.
• The user will pay for two circuits but will use only the capacity of one.
• Uses the same circuit for data in both directions.
  • Data frames from A to B will inter-mixed with the ACK frames from A to B, where 'kind' field of the header will tell receiver about the type of frame arrived.
• The ACK gets a free ride on the next outgoing data frame, this is called PIGGYBACKING: this is a better use of the available channel bandwidth.
• Introduces an identification scheme based on window size to keep track of which frames are transmitted and received.
• The frames are numbered modulo-n, so that the frames numbered from 0 to n-1.
• When the receiver sends an ACK, it includes the number of the next frame it expects to receive.
• The sender can transmit several frames before needing an ACK by using a single ACK to confirm the receipt of multiple data frames.
• Frames may be acknowledged at any point without waiting for the window but transmitted as long as window not full.
• One Bit Sliding Window protocol is protocol stop and wait with maximum window size of 1, and the sender since the sender transmits a frame and waits for its acknowledgement before sending the next one.

Error Control

• Technology at the physical layer is not always reliable, therefore need to prevent delivering corrupted packets to the network layer.
• Error control refers primarily to methods of Error Detection and Retransmission.
• Reliable delivery of frames needs feedback from the receiver.
• Receivers send special control frames bearing acknowledgements.
  • Acknowledgements can be positive (ACK) or negative (NAK).
• Senders start a timer when transmitting a frame, set to go off after a duration in which to reach the receiver/ be processed/ have the ACK propagate.
• Anytime an error is detected in an exchange, a negative acknowledgement (NAK) is returned and the specified frames are re-transmitted, the process is called AUTOMATIC REPEAT REQUEST (ARQ).

Stop-and-Wait ARQ

• Extends stop-and-wait flow control to included re-transmission of data in case of lost or damaged frames.
• Sending devices keep a copy of the last frame transmitted while waiting for an ACK.
• Data frames and ACK frames are numbered alternately 0 or 1 for identification.
• NAK frames are returned upon receipt of a corrupted frame at the receiver end, they are unnumbered.
• Sending devices are equipped with a timer.
  • If an expected ACK is not received within an allotted time period, the sender assumes that the last data frame was lost in transit and sends it again.

Sliding Window ARQ

• Three features are added to the basic Sliding Window flow control mechanism:
  • The sending device keeps copies of all transmitted frames until they have been acknowledged.
  • Both ACK and NAK frames must be numbered for identification.
• Data frames received error-free do not need to be acknowledged individually, however, every damaged frame must be acknowledged immediately.
  • The sending device is also equipped with a timer to handle lost acknowledgements (ACK/NAK).
• In the cases of a time overrun with no ACK received
  • the sender assumes that the frames were not received and therefore retransmits one or all of the frames depending on the protocol.

Go-Back-N ARQ

• If one frame is lost or damaged, all frames sent since the last frame acknowledged are retransmitted.
• Receiving device stops accepting subsequent frames until damaged frame is resolved.
• NAK# means frame # was damaged or missing and on receiving, sender re-transmits all starting at #.

Selective-Repeat ARQ

• If a frame is corrupted in transit, a NAK is returned and the frame is resent out of sequence.
• One lost, only the specific /lost frame can be retransmitted.
• Receiving device is able to sort frames and insert the retransmitted frame into its proper sequence.
• Sending devices have searching mechanisms to select only frame for retransmission.
• Must keep all previously received frames with the aid of receiver buffer.
• the ACK number will be the FRAME RECEIVED, instead of the next frame expected.
• Sliding window size should be half sender window size.

Error Detection and Correction

• Reliable systems must have a mechanism for DETECTING and CORRECTING ERRORS.
• Electromagnetic signals are subject to unpredictable inference which can change change in the shape of timining of the signal
• Error detection and correction can be implemented at either the data link or transport layer.
• Data can be corrupted during transmission.
• **

Types of Errors

• Single-Bit Error: Only one bit of the unit was corrupted. It happens mostly in parallel transmission due to one noisy wire..
• Burst Error: Two/more bits are corrupted in a frame More likely to happen in serial transmission because a noise will affect a set of bits.

Error Detection

• The central concept to detect errors is REDUNDANCY or extra bits
• Transmit data unit twice: - If there is discrepancy between data when compared, there is an error in transfer - Accurate but very slow. Extra bits are redundant and discarded when transmission is determined to be successful
• Detection Method is Block Coding

Redundancy Checks

• VRC (Vertical Redundancy Check)
  • Mechanism Appends one bit to the smallest unit possible
    • Add 1 bit such that total number of 1s add to even.
• Other name, that the Redundant bit (parity bit) that is added to check even parity or to VRC
• Can detect all single-bit errors.

• Can detect when there is an even number or bits changed
  

• LRC (Longitudinal Redundancy Check) - Organize bits in table format - Create a new row of the same size to compare the parity bits for each column. - Attach the parity bits block (redundant) to the original data and send them to the receiver. - LRC increases the likelihood detecting burst errors.
  • If two bits in a data unit are damaged and two bits in the exact same positions in another are also damaged, the checker will not detect an error

VRC and LRC

• Two dimensional bits in the form of a two-dimensional Parity Code
• Hamming Distance Hamming distance is number of difference between two words.
• To guarantee the detection of up to "s" errors the Minimum Hamming Distance in a Block Code must be "s+1"

CRC (Cyclic Redundancy Check)

• More powerful than LRC/VRC, but based on division instead addition
• A sequence or "redundant bits" is added to the end of a data unit - Divisible by second, predetermined number
• *if there's no remainder after the binary division process indicates that data is sent in contact and accepted by the receiver. A remainder indicates that the data has been damaged in transit and rejected To better guarantee a working CRC system, a Polynomial should have some of the following properties:
• Should not be divisible at all. Guarantees that a bus system of the link with degree of polynomial can be collected.
• Should have a divisible at 1 or 2.
• Guarantees that all the bust system errors and odd bits
• The data is is sent using modulo system with specific amount degree of the message

Checksum

• Error detecting technique can be applied to a data message.

Implementing Checksum

• Sub-divides the data unit into equal "n" bit long segments.
• Total Sum then complemented, and then appended to checksum field that gets extended for the data.
• New checksum field ZERO determines there is no Error on send/receive end.
• Uses two accumulators (R+L) with the first one simply adding a data and the second adds a weight for the measurement.
• Fletcher Checksum/Adler Checksum.

Error Correction

• Can be handled in two ways:
  • Receiving end request's sender to retransmit an entire unit of data when and error is discovered. -Receiver can use an error-correcting system that could help automatically correct data's, therefore some errors, are sophisticated.
• Most errors limited to one, two or three-bit errors
• VRC can detect a single bit in the received frame, and will try to isolate the invalid bit.
• For code to work, and to correct single -bit in a message, ECC has to determine which is 7-bit that needs to change.
• Use additional (enough) bits for all eight stage: all positions, from 1 to 7
• To code with redundancy, must use a 3 bit redundancy code. If an error occurs with too many redundancy bits, it might me necessary for Additional bits, for complete data.

Hamming Code

• Can be used in data, while coding
• Requires 4 or more bits, to the to send a message unit or message
• Redundant bits are located in position 1 to 8

Protocol

• High-Level Data Link Control (HDLC)
• Point-to-Point Protocol (PPP)

High-Level Data Link Control Protocol

• HDLC is a bit-oriented data link protocol, supporting half/full duplex communication over point-to-point/multipoint links
• Primary station controls the links: sends commands to secondary, and receives
• Secondary station responds to primary station:
• Combined station both send and receive commands
• Unbalanced configuration: one device primary, others secondary.
• Balanced configuration: both are combined type.
• Symmetrical: physical station has two of devices and the link controls can the set across the same
• Modes of Communication - (NRM) Normal Response, primary/secondary setup where secondary can the send information once a primary allows: must have permission for the primary - All stations are equal only combined point-to-point connections - Asynchronous balanced mode (ABM) - only combined stations. - asynchronous response mode (ARM) - transmit w/o permission from primary, when channel is idle

HDLC Frame Structure:

1. FLAGS: both start/end and pattern
2. ADDRESS: points at one terminal.
3. CONTROL: sends back all numbers, for frame-sequence; etc.
4. DATA: info unit
5. FCS: Error check

ADDRESS:

• Address of message will be send to a specific secondary receiver terminal If any receiver will have the correct address
  • the last bit is always 1
    • so the receiver can determine how many bytes
• MAC Ethernet: the last 6 bytes of each address will occur in MAC

CONTROL: (3 types)

1. I-frames: transfer data using 4 bits
2. S-Frames: with only control infor
3. U-Frames: for Management

SUPERVISORY frames

• Is the result of a single bit:
  • either is POLL
  • or is final

Types of Supervisory frames

• Used to recognize other frames and all to stop or start sending
  • 0: Acknowledgement frame, used to the next Frame
  • 1: The negative Acknowledgement or REJECT which indicates at ransmission -3 : negative Ac -reject, its code is "11": used for retran
  • 2: used with "Receiving/Not ready" mode which used for other sendings codes.

High-Level Data Link Control Protocol

• BUSY CONDITION sharing what send with Frame/sequence

Timeout and Recovery

If an 'it' is still on that transmission and is lost after sometime, reinitiates this time, if it's already expired