CS 422 Class Notes for September 8, 10, 12 - 2003

By Patrick Piemonte

Index:

Monday September 8th, 2003

Wednesday September 10th, 2003

Friday September 12th, 2003

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:

Number 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 = 2B log₂K

Example:

RS232

K = 2 (+15, -15 are used)

D = 2B log₂(2) = 2B

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))

(S/N) - Signal to noise ratio

Example:

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.

If S/N = 0 --> No Signal

The S/N ratio is usually given in decibels (dB).

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

Example:

S/N = 1000

S/N in dB = 10log₁₀(1000)

= 10(3)

= 30dB

S/N = 20 dB

S/N = ?

20 = 10log₁₀(S/N)

20/10 = log₁₀(S/N)

10²=(S/N)

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 - 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.

Multiplexor

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

Demultiplexor

• 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.
• Demultiplexer uses the mark to deliver to corresponding destination.

Frequency Division Multiplexing

• multiple items are sent simultaneously
• each item uses a separate frequency channel.

Channel Use:

Example:

Cable TV - Each TV channel has a different frequency.

Wednesday September 10th, 2003

Multiplexing

TDM

FDM

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.

Disadvantage:

The disadvantage is that you will need n(n-1)/2

cost = O(n²)

Advantage:

Throughput is not divided, it is always the same across each pair of computers.

Example:

A sends to B at 10mbps

C sends to D at 10 mbps

simultaneously.

With a shared network

cost = O(n)

n = # of computers

Advantage:

Less expensive.

Disadvantage:

Throughput is shared at will divided.

If A, B and C, D exchange data simultaneously, then

A sends to B at 5 mbps

C sends to D at 5 mbps

Shared Networks are the only scalable option.

Problems 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 can not wait. Example: telephone, voice over IP, teleconferencing.

A shared network may introduce non-deterministic delays.

• we need to have a fair access access to the network.

Solution for fairness

• The data is divided in small units called packets that are limited in length., Example: 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

1. acquire shared medium
2. send one packet
3. 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.

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

Original Message:

Sent Message:

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 bits (including parity bit) is an even number.

odd parity --> total # of bits (including parity bit) is an odd number.

With Even Parity: (Parity Bit is Underlined)

1001001

00011011

If receiver receives

11000001 <-- received (There is an error)

• The parity check can be implemented in hardware.
• Parity check does not handle errors that change two bits. 11010001

Checksum

• It is used in sequences of characters.
• It treats data as a sequence of integers (Example: 4 bytes --> integer)
• It computes the arithmetic sum of the sequence.

Check field above is 4 bytes. 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

X = Errors

Web Crawling - harvesting internet information.

Google added a protocol on top of TCP that does a more thorough analysis of the terabytes of web crawling information.

• The problem is that erros may happen in the position due to bad hardware.

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 Operator

Shift Operator

Before shift:

After shift:

Example:

CRC Hardware

Input is 0

Input is 1

and so forth...

• What makes CRC capable of detecting positional errors is the feedback operations.
• CRC detects errors that tend to happen in the same position.
• The CRC covers the data only and it is included in the packet.

RS232:

Ethernet:

Ethernet Address is 6 bytes

IP Address is 4 bytes

CRC finds Error. CRC is slower than Checksum.