CS 422 Class Notes

By Chetak Sirsat

Monday September 8th, 2003

Network Parameters

- Propagation Delay à Time required for a signal to travel across a medium.

- Bandwidth à Maximum times per second a signal can change.

- Throughput à # of bits per second that can be transmitted, the larger the bandwidth the larger the throughput.

Nyquist Theorem

- Relates Network bandwidth and throughput.

· D - throughput (bits/sec)

· B - bandwidth (Hz)

· K - # of values that encode the data in each cycle.

· D = 2*B*log₂*K

- For ex: RS232

K = 2 (+15, -15 are used); D = 2Blog₂(2) = 2B (bit/sec)

- Nyquist theorem does not consider noise, and therefore it only gives a maximum theoretical limit.

Shannon's Theorem

- It considers noise to relate bandwidth and throughput.

· C - Throughput (bits/sec)

· B - Bandwidth (Hz)

· S - Power of the signal

· N - Power of noise

· C = B*log₂*(1 + (S/N)) where S/N is noise ratio

- For ex:

Telephone System, Bandwidth 3000Hz (typical bandwidth used for voice), Signal to Noise Ratio of 1000 (S/N)

Effective Capacity throughput B = 3000Hz

(S/N) = 1000è C = 3000log₂(1 + 1000) = 30, 000 bps

- Result:

With a S/N of 1000 there is little hope to accomplish more than 30 kbps
56 kbps modems accomplish this speed only with larger S/N ratio and compression.
The S/N ratio is given in decibels (dB).

- For ex:

S/N in decibels = 10log₁₀(S/N) = 10*30 = 30 db

Now suppose, S/N in db = 20db; what is S/N?

20 = 10log₁₀(S/N) à 10² = S/N = 100

- Nyquist theorem gives a theoretical limit in the throughput

- Shannon's theorem gives a more practical limit in the throughput

Multiplexing

- Multiplexing means use the same channel to transmit separate source of information

- Multiplexing prevents interference among signals.

- Each destination should receive the corresponding data of the original source.

- Accepts data from multiple data and sends the combined data through shared channel.

- De-multiplexor -Receives combined data and extracts data that corresponds to each destination.

- There are two ways to do multiplexing:

Time Division Multiplexing (TDM)

Only one item at a time in the shared channel
The item is marked to identify source
De-multiplexer uses the mark to deliver to corresponding destination.

Frequency Division Multiplexing (FDM)

Multiple items are sent simultaneously
Each item uses a separate frequency channel

For ex: Cable TV - Each TV channel has a different frequency

Wednesday September 10th, 2003

Multiplexing

- TDM - Time division multiplexing

· The shared channel is used by only one signal at a time

· Transmitter and receiver need to synchronize to know what belongs to each channel

· In some cases, the data packets include a label to identify the original source.

- FDA - Frequency division multiplexing

· Two or more signals can use different carrier frequencies without interference

· When applied to light FDM is called "wave division multiplexing" WDM

· It is also called "color division multiplexing.

Packets, Frames, and Error Correction

- Why do we connect computers to a shared network?

- The alternative is to have a one to one connection to each computer.

- The disadvantage is that you will need n*(n-1)/2 à cost – O (n²)

- The advantage is that throughput is not divided, it is always the same across each pair of computers

- For ex: A à B at 10 Mbps, C à D at 10 Mbps

- With a shared network à cost – O (n)

- The advantage is less expensive

- The disadvantage is the throughput is shared

- For ex: If A, B and C, D exchange data simultaneously, then

- A à B at 5 Mbps, C à D at 5 Mbps

Shared Networks are the only scalable option.

- Problem with shared networks:

It may have a lot of traffic; total throughput is divided across all computers.
Some applications may have large transfers (downloading movies, teleconference and they may affect other applications that are also using the network)
There are applications that cannot wait.
Ex: telephone, voice over IP, teleconferencing.

- A shared network may introduce non-deterministic delays.

- We need to have a fair access to the network

Solution for fairness

The data is divided in small units called packets that are limited in length. (Ethernet - 1500 bytes/per packet)

This makes sure that an application will not use the shared network for a long period of time and will give opportunity to other computers to use network.

This is a form of Time Division Multiplexing.
Separating data in packets is called "packet switching"

Packet Switching Steps

- A wants to send a packet to C

Acquire shared medium
Send one packet
Allow other stations to send packets before sending again.

- The structure of the packet depends on the underlying network. The format of the packet is also called the frame.

Frame Format of RS 232

SOH

DATA

EOT

- RS232 transmission consists of a sequence of characters

- SOH - Star of Header

- EOT - End of Text

- SOH and EOT are special characters used to delimit the message.

- Problem: If the data contains SOH or EOT then the receiver may confuse the start/end of transmission.

- Solution: Use "stuffing"

- Use as alternative representation of SOH and EOT if they appear in the data

- SOH à ESC-X; EOT à ESC-Y; ESC à ESC-Z

- For ex:

Original message-

SOH

EOT

SOH

EOT

Sent Message-

SOH

ESC

EOT

- The receiver translates the sent message back to the original message.

- Stuffed frame may be larger than original

Handling Errors

- Parity bit

- Checksum

- CRC

Friday September 12th, 2003

Handling Errors

- Data sent can be corrupted during transmission

· Bits can be lost

· Bit values can be changed.

- The frame of the packet includes some additional information to detect errors

· This additional information is added by the sender

· Checked by receiver

· If the additional information is wrong discard packet.

- There is always a very small probability of having undetected errors but it works well in practice

Parity Bit

- One additional bit per character tells if the number of bits in the character is even or odd

· Even parity à total # of 1 bits (including parity bit) is an even number

· Odd parity à total # of 1 bits (including parity bit) is an odd number

· With even parity

o 1101001 or 00011011

o If receiver receives 11000001 à there is an error

· The parity check can be implemented in hardware

· Parity check does not handle errors that change two bits ex: 11010001

Checksum

- It is used in sequences of characters

- It treats data as a sequence of integers

- It computes the arithmetic sum of the sequence

100

201

312

- 312 is the checksum value

- The receiver computes the checksum as well and if it differs from the checksum in the packet, the packet is discarded

- Checksum handles multiple bit errors, but there is still the possibility that some errors will remain unchecked

- Example:

- Original Received

- 00100111 00100110 ß error in red

- 10010100 10010101 ß error in red at same position

- ----------- -----------

- 10111011 = 10111011

- ----------- -----------

- The problem is that errors may happen in the position due to bad hardware (TCP/IP protocol uses checksum)

CRC – Cyclic redundancy check

- Better than checksum because detects positional errors

- Mathematical function of data

- More complex to compute, most of the time is done in hardware

- Used in Ethernet packets

- Computing CRC

- Basic operations XOR

A	B	XOR
0	0	0
0	1	1
1	0	1
1	1	0

- Shift Operator

· Before Shift (Left Shift, Add 1 from Right)

· After Shift

- Ex: CRC Hardware

- 16-bit CRC

- Registers are initialized with 0's.

- Bits of message are shifted into the input.

- CRC is found in the registers once all the input sequence has been shifted

- 0000 00000000 00000000 ß 1

- 0000 00000000 00000001 ß 0

- 0000 00000000 00000010 ß 1

- And so on…

- What makes CRC capable of detecting positional errors?

· The feedback operations

- CRC detects errors that tend to happen in the same position

- CRC covers the data only and it is included in the packet