Chapter 2 Flashcards
Shannon-Hartley Thm.
Upper bound to capacity of a link in terms of bits per second as a function of signal to noise ratio
C = B * log2(1 + S/N)
* S = Signal power
* N = Average noise
* B = Bandwidth of channel
Medium - Characterise
- Copper wire
- Optical / fibre
- Air
Frequency - Characterise
Hz
Wavelength
Distance min and max of wave in metres
Encoding
Binary data on a signal
* Bits travel between adaptors
* Signal travel between signalling components
Problems of Non Return to Zero
- Baseline wander
- Receiver keeps average of signals seen
- uses average to distinguish 0 or 1
- Too many 0s or 1s could lead to inaccuracy
- Clock recovery
- Frequenct transtions are needed for clock recovery
- Sending & decoding done by clock
- Every clock clock cyle a sender transmits a bit and receiver bit
- Sender and receiver has to be insync
Non Return to Zero Inverted
- Sender makes a transition from current signal to encode 1 and stay at 1
- Solves consecutive 1s
Manchester encoding
- Merge clock XOR of NRZ
- for clock: one high and low pair is a cycle
- 0 : low to high
- 1: high to low
Problems with Manchester
Doubles the rate at which signal transitions are made
* The receiver has 1/2 the time to detect each pulse
Baud rate
The rate of change in signal
4B/5B encoding
- Insert extra bits into bit stream to break up long 0s or 1s
- Every 4 bits are encoded in 5 bits
- Each 5B has no more than 1 leading 0
- Each 5B has no more than 2 trailling 0s
- No pair of 5 bit codes have more than 3 consecutive 0s
Idle line 4B/5B
11111
Dead Line 4B/5B
00000
Halt Line
00100
Frames
Blocks of data
Byte Oriented Protocol
View each frame as a collection of bytes rather than bits
Binary Synchronous Communication (BISYNC)
- SYN Character - 8 bits
- SYN Character - 8
- Start of Header (SOH) - 8
- Header
- Start of Text (STX) - 8
- Body
- End of text (ETX) - 8
- Cyclic Redundancy Check (CRC) 16
Point-to-Point Protocol (PPP)
Commonly used over internet links which use sentinel approach
* Special start character: 01111110 : Flag - 8
* Address - 8
* Control - 8
* Protocol for demux: IP/IPX - 16
* Payload
* Checksum - 16
* Flag - 8
Digital Data Communication Message Protocol (DDCMP)
Byte counting approach
If count is corrputed - framing error
* SYN - 8
* SYN - 8
* Class - 8
* Count - 14
* Header - 42
* Body
* CRC - 16
High Level Data Link Control (HDLC)
- Beginning and ending sequences
- 01111110
- Frame:
- Beginning Sequence - 8
- Header - 16
- Body
- CRC - 16
- Ending Sequence - 8
- On sender side
- If 5 1 bits are being sent a 0 is inserted
- On receiver side
- if 5 bits read
- if next bit is a 0 = body
- if next bit is 1 = either end sequence or error and must discard
Two dimensional Parity
- Based on parity
- Adding 1 bit for 7 bits to make it even or odd
- Catches 1, 2, 3 and most 4 bit errors
- Each 7 bits has a parity bit, and there is an additional parity byte at the end
Internet Checksum Algorithm
- Add up all words transmitted & transmit sum
- Sender & receiver do the same calculation then compare
- If different then there is an error
- Data checksummed as a sequence of 16 bit integers
- Add them together using complement arithemetic
- 16 bit number is the checksum
Cyclical Redundancy Check (CRC)
- Reduce the number of bits
- Maximise protection
- Uses bit string that represent polynomials
- M(X) is the message polynomial
- C(X) is the generator polynomial
- If M % C produces a remainder then there is an error
- M comes from the message itself
- C has to be agreed on between sender and receiver
Error handling with CRC
- if M % C does produce a remainder of 0, a bit error could have just gone unnoticed
- For single bit errors: X^k and X^0 must have non zero coefficients
- Double bit: C(X) has a factor of at least 3 terms
- Any odd number of errors : C(x) contains (k+1)
- Any burst error < k bits
Acknowledgement (ACK)
a small control frame that a protocol sends back to its peer saying that it has received an earlier frame
Timeout
If the sender does not receive an ACK after a reasonable amount of time, then it retransmits the original frame. This action of waiting a reasonable amount of time is called a timeout.
Automatic Repeat Request (ARQ)
The general strategy of using acknowledgements and timeouts to implement reliable delivery is sometimes called automatic repeat request
Stop and Wait Protocol
- After transmitting one frame, the sender waits for an ACK before transmitting the next frame.
- If the ACK does not arrive after a certain period of time, the sender times out and retransmits the original frame.
Problems with Stop and Wait
- If the receiver receives the a frame but the ACK does not return in time or simply does not return, a copy of the frame will be sent
- A 1 bit header is required to say whether or not the frame is a copy or not
- Only allows for one outstanding frame which results in a severe misuse of the link capacity
Sliding Window Sender
First, a sender assigns a sequence number, denoted SeqNum, to each frame. The sender maintains three variables:
1. Send window size (SWS), gives the upper bound on the number of outstanding (unacknowledged) frames that the sender can transmit.
2. LAR denotes the sequence number of the last acknowledgement received.
3. LFS denotes the sequence number of the last frame sent.
The sender also maintains the invariant:
LFS - LAR <= SWS
- When an acknowledgement arrives, the sender moves LAR to the right, thereby allowing the sender to transmit another frame.
- Also, the sender associates a timer with each frame it transmits, and it retransmits the frame should the timer expire before an ACK is received.
- Notice that the sender has to be willing to buffer up the SWS frames since it must be prepared to retransmit them until they are acknowledged.
Sliding window Receiver
The receiver maintains the following three variables:
1. RWS, receive window size, which gives the upper bound on the number of out-of-order frames that the receiver is willing to accept.
2. LAF denotes the sequence number of the largest acceptable frame
3. LFR denotes the last frame received.
The receiver also maintains the following invariant:
LAF - LFR <= RWS
- If SeqNum ≤ LFR or SeqNum > LAF, then the frame is outside the receiver’s window and it is discarded.
- If LFR < SeqNum ≤ LAF, then the frame is within the receiver’s window and it is accepted.
Issues with Sliding Window Protocol
- Timeout = Amount of data in transit decreases
- Packet Loss = Pipe is no longer fulle
Solutions to Sliding Window Protocol
Negative ACK
* Sends ACK for packets received in order when out of order frame arrives
Additonal ACK
* Send additonal ACK for frame before the one are looking for = Packet Los
Selective ACK
* ACK Frames Received
* Sender knows packet lost
* Can keep the pipe full
Ethernet
- Uses CSMA/CD tech
- A multiple access network
- “Carrier Sense” means that nodes can distinguish between a busy and an idle link
- “Collision Detect” means that a node listens as it transmits and can therefore detect when a frame it is transmitting has collided
