Data Communication - 2 | Computer Networks - Computer Science Engineering (CSE) PDF Download

6. ENCODING

Problem with NRZ

• Baseline wander
  • The receiver keeps an average of the signals it has seen so far
  • Uses the average to distinguish between low and high signal
  • When a signal is significantly low than the average, it is 0, else it is 1
  • Too many consecutive 0’s and 1’s cause this average to change, making it difficult to detect

 Problem with NRZ

• Clock recovery
  • Frequent transition from high to low or vice versa are necessary to enable clock recovery
  • Both the sending and decoding process is driven by a clock
  • Every clock cycle, the sender transmits a bit and the receiver recovers a bit
  • The sender and receiver have to be precisely synchronized

 NRZI

• Non Return to Zero Inverted
• Sender makes a transition from the current signal to encode 1 and stay at the current signal to encode 0
• Solves for consecutive 1’s

Manchester encoding

•  Merging the clock with signal by transmitting Ex-OR of the NRZ encoded data and the clock
• Clock is an internal signal that alternates from low to high, a low/high pair is considered as one clock cycle
• In Manchester encoding
  • 0: low→ high transition
  • high→ low transition

Problem with Manchester encoding

• Doubles the rate at which the signal transitions are made on the link
  • Which means the receiver has half of the time to detect each pulse of the signal
• The rate at which the signal changes is called the link’s baud rate
• In Manchester the bit rate is half the baud rate

4B/5B encoding

• Insert extra bits into bit stream so as to break up the long sequence of 0’s and 1’s
• Every 4-bits of actual data are encoded in a 5- bit code that is transmitted to the receiver
• 5-bit codes are selected in such a way that each one has no more than one leading
• 0(zero) and no more than two trailing 0’s.
• No pair of 5-bit codes results in more than three consecutive 0’s

7. FRAMING

• We are focusing on packet-switched networks, which means that blocks of data (called frames at this level), not bit streams, are exchanged between nodes.
•  It is the network adaptor that enables the nodes to exchange frames.
• When node A wishes to transmit a frame to node B, it tells its adaptor to transmit a frame from the node’s memory. This results in a sequence of bits being sent over the link.
• The adaptor on node B then collects together the sequence of bits arriving on the link and deposits the corresponding frame in B’s memory.
• Recognizing exactly what set of bits constitute a frame—that is, determining where the frame begins and ends—is the central challenge faced by the adaptor
• Byte-oriented Protocols
  • To view each frame as a collection of bytes (characters) rather than bits
  • BISYNC (Binary Synchronous Communication) Protocol
    • Developed by IBM (late 1960)
  •  DDCMP (Digital Data Communication Protocol)

Used in DECNet

•  BISYNC – sentinel approach
  •  Frames transmitted beginning with leftmost field
  • Beginning of a frame is denoted by sending a special SYN (synchronize) character
  • Data portion of the frame is contained between special sentinel character STX (start of text) and ETX (end of text)
    • SOH : Start of Header
    • DLE : Data Link Escape

PPP Frame Format

Recent PPP which is commonly run over Internet links uses sentinel approach

• Special start of text character denoted as Flag
  •  0 1 1 1 1 1 1 0
•  Address, control : default numbers 
• Protocol for demux : IP / IPX
• Payload : negotiated (1500 bytes) 
• Checksum : for error detection

 Byte-counting approach

•  DDCMP
• count : how many bytes are contained in the frame body
• If count is corrupte
  • Framing error

• Bit-oriented Protocol
  •  HDLC : High Level Data Link Control
    • Beginning and Ending Sequences

0 1 1 1 1 1 1 0

HDLC Protocol

On the sending side, any time five consecutive 1’s have been transmitted from the body of the message (i.e. excluding when the sender is trying to send the distinguished 01111110 sequence). The sender inserts 0 before transmitting the next bit

HDLC Protocol

On the receiving side

 5 consecutive 1’s

 Next bit 0 : Stuffed, so discard it

 1 : Either End of the frame marker

 Or Error has been introduced in the bitstream Look at the next bit

If 0 ( 01111110 ) ^→ End of the frame marker

If 1 ( 01111111 ) ^→ Error, discard the whole frame

The receiver needs to wait for next 01111110 before it can start receiving again

 8. ERROR DETECTION

•  Bit errors are introduced into frames
  • Because of electrical interference and thermal noises
• Detecting Error
• Correction Error
• Two approaches when the recipient detects an error
  •  Notify the sender that the message was corrupted, so the sender can send again.
    •  If the error is rare, then the retransmitted message will  be error-free
  • Using some error correct detection and correction algorithm, the receiver reconstructs the message
• Common technique for detecting transmission error
  • CRC (Cyclic Redundancy Check)
    • Used in HDLC, DDCMP, CSMA/CD, Token Ring
  • Other approaches
    •  Two Dimensional Parity (BISYNC)
    •  Checksum (IP)
• Basic Idea of Error Detection
  • To add redundant information to a frame that can be used to determine if errors have been introduced
  • Imagine (Extreme Case)
    • Transmitting two complete copies of data
      • Identical ^→ No error
      • Differ ^→ Error
      • Poor Scheme ???
        • n bit message, n bit redundant information
        • Error can go undetected
    • In general, we can provide strong error detection technique
      • k redundant bits, n bits message, k << n
      • In Ethernet, a frame carrying up to 12,000 bits of data requires only 32-bit CRC
•  Extra bits are redundant
  • They add no new information to the message
  • Derived from the original message using some algorithm
  • Both the sender and receiver know the algorithm
  • Sender Receiver Receiver computes r using m If they match, no error

  9. TRANSMISSION

• CRC is used to detect errors.
• Some error codes are strong enough to correct errors.
• The overhead is typically too high.
• Corrupt frames must be discarded.

A link-level protocol that wants to deliver frames reliably must recover from these discarded frames.

• This is accomplished using a combination of two fundamental mechanisms
  • Acknowledgements and Timeouts
• An acknowledgement (ACK for short) is a small control frame that a protocol sends back to its peer saying that it has received the earlier frame.
  • A control frame is a frame with header only (no data).
  • The receipt of an acknowledgement indicates to the sender of the original frame that its frame was successfully delivered.
• If the sender does not receive an acknowledgment after a reasonable amount of time, then it retransmits the original frame.
• The action of waiting a reasonable amount of time is called a timeout.

The general strategy of using acknowledgements and timeouts to implement reliable delivery is sometimes called Automatic Repeat reQuest (ARQ).

Stop and Wait Protocol. Idea of stop-and-wait protocol is straightforward. After transmitting one frame, the sender waits for an acknowledgement before transmitting the next frame. If the acknowledgement does not arrive after a certain period of time, the sender times out and retransmits the original frame

If the acknowledgment is lost or delayed in arriving

• The sender times out and retransmits the original frame, but the receiver will think that it is the next frame since it has correctly received and acknowledged the first frame
• As a result, duplicate copies of frames will be delivered

 How to solve this

• Use 1 bit sequence number (0 or 1)
•  When the sender retransmits frame 0, the receiver can determine that it is seeing a second copy of frame 0 rather than the first copy of frame 1 and therefore can ignore it (the receiver still acknowledges it, in case the first acknowledgement was lost)

The sender has only one outstanding frame on the link at a time

• This may be far below the link’s capacity
• Consider a 1.5 Mbps link with a 45 ms RTT. The link has a delay bandwidth product of 67.5 Kb or approximately 8 KB. Since the sender can send only one frame per RTT and assuming a frame size of 1 KB Maximum Sending rate Bits per frame Time per frame = 1024 8 0.045 = 182 Kbps Or about one-eighth of the link’s capacity

To use the link fully, then sender should transmit up to eight frames before having to wait for an acknowledgement Sliding Window Protocol Sender assigns a sequence number denoted as SeqNum to each frame.

Assume it can grow infinitely large Sender maintains three variables Sending Window Size (SWS) Upper bound on the number of outstanding (unacknowledged) frames that the sender can transmit Last Acknowledgement Received (LAR)

Sequence number of the last acknowledgement received Last Frame Sent (LFS). Sequence number of the last frame sent .When an acknowledgement arrives the sender moves LAR to right, thereby allowing the sender to transmit another frame. Also the sender associates a timer with each frame it transmits. It retransmits the frame if the timer expires before the ACK is received.

Note that the sender has to be willing to buffer up to SWS frames

Receiver maintains three variables. Receiving Window Size (RWS).Upper bound on the number of out-of-order frames that the receiver is willing to accept. Largest Acceptable Frame (LAF).Sequence number of the largest acceptable frame. Last Frame Received (LFR) . Sequence number of the last frame received. Receiver also maintains the following invariant

LAF – LFR ≤ RWS

If SeqNum ≤ LFR or SeqNum > LAF

Discard it (the frame is outside the receiver window). If LFR < SeqNum ≤ LAF. Accept it. Now the receiver needs to decide whether or not to send an ACK. Let SeqNumToAck. Denote the largest sequence number not yet acknowledged, such that all frames with sequence number less than or equal to SeqNumToAck have been received.  The receiver acknowledges the receipt of SeqNumToAck even if high-numbered packets have been receivedThis acknowledgement is said to be cumulative.  The receiver then sets

 LFR = SeqNumToAck and adjusts

 LAF = LFR + RWS

For example, suppose LFR = 5 and RWS = 4

(i.e. the last ACK that the receiver sent was for seq. no. 5)

LAF = 9

If frames 7 and 8 arrive, they will be buffered because they are within the receiver window. But no ACK will be sent since frame 6 is yet to arrive Frames 7 and 8 are out of order. Frame 6 arrives (it is late because it was lost first time and had to be retransmitted). Now Receiver Acknowledges Frame 8 and bumps LFR to 8 and LAF to 12