Networks CS348 Notes

September 13, 2024

Contents

I General Ideas 4
1 Introduction 4
1.1 Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Abstractions, Layering in a network 5

2.1 IP address . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Message Granularity, Delays . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Layering and Design Protocols . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Latency Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Headers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Quality of service 10

II Physical Layer 10
1 Physical Media 10
1.1 Attenuation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Absolute Power in decibel scale . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Frequency vs attenuation . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Attenuation in Wireless signals . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 MIMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Signalling 15
2.1 Manchester coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Differential Manchester Coding . . . . . . . . . . . . . . . . . . . . . . 17

1
3 Phase Modulation in wireless channels 17
3.1 Signals as vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 BPSK encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 QPSK encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

III Data Link Layer 20

1 Introduction 20
1.1 Bit stuffing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Cyclic redundancy check . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3 Coding Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Hamming Distance . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.2 Error Detection: . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3 Error Correction: . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 Galois Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Polynomial Arithmetic 23
2.1 Some Polynomial CRC’s . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 Media Access Control 25

3.1 Interference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Frequency and time . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.2 Issues with Central Coordinator . . . . . . . . . . . . . . . . . . 27
3.2 No central coordinator . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Carrier sense Multiple Access (CSMA) . . . . . . . . . . . . . . 28
3.2.2 Collision Detection . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.3 Random Wait time . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.4 Flowchart to represent CSMA . . . . . . . . . . . . . . . . . . . 29
3.2.5 Limits on frame size . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.6 Format of an ethernet frame . . . . . . . . . . . . . . . . . . . . 31
3.3 MAC in Wifi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.1 Virtual Carrier Sensing . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.2 Modulation in WiFi . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.3 Exposed Terminal problem . . . . . . . . . . . . . . . . . . . . . 33
3.3.4 DIFS and SIFS . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.5 Contention Window . . . . . . . . . . . . . . . . . . . . . . . . 34

4 Ethernet Switching 35
4.1 Automatic MAC address maintanence . . . . . . . . . . . . . . . . . . 36
4.2 Loops in the network . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.1 Spanning tree protocol . . . . . . . . . . . . . . . . . . . . . . . 37

5 Issues with Ethernet Switching 38

2
IV Network layer 38

3
 Lecture 1

Part I

General Ideas
1 Introduction
What is a computer network? A computer network is a group of interconnected devices
that can exchange data and resources with each other. Almost all of today’s devices are
in one way or another connect the biggest computer network alias the Internet. There
are several abstractions and nuances that enable the existence of such a huge structure.
A network consists of several end hosts which are systems that request/receive data
using the network. These end hosts are connected using links which can directly connect
the hosts together or more commonly connect multiple of them to switches/routers
which can simplify the network while still providing connectivity among hosts.

1.1 Topologies
A group of hosts can be connected in multiple ways. The type of graph that is obtained
from considering the hosts as nodes and links as edges is called the ‘topology’ of that
network. Some examples include a bus where all hosts are connected to a common wire.
Others include star topology where hosts are connected to a central host.
Links can also be classified on the basis of how many users can communicate across
them.
• Simplex: Only one user can talk across a link
• Duplex: Both users can communication simultaneously across a network.
• Half Duplex: Both users use the same link to communication but not simulta-
neously.

1.2 Switch
What exactly is a switch? The Switch is a network device that is used to segment the
networks into different subnetworks called subnets. It can help simplify a network by
grouping together lots of hosts into a sub-network. A switch has multiple incoming and

4
 Figure 1: Bus Topology Figure 2: Star Topology

outgoing links. It is capable of routing data from an incoming link to an appropriate

outgoing link.

Figure 3: Example of a switch

2 Abstractions, Layering in a network

There is always the possibility to deal with the network as a single structure at once.
That is to deal with the entire flow of data from the second a request is made by a
‘user’ and all the way till the request is serviced in one go.
However, this is very inconvenient and complicates the network in the sense that any
change made to some part of the network can make or break the entire system. To
combat this the network is clearly split into layers where each layer operates relatively
independently and only exposes parts of it that are necessary for the higher and lower
layers in the network.
To better understand this let us take an example.
The most common request on the Internet is an HTTP request (ie) a request by a
computer for a webpage. Let us see the flow of information when such a request is
made.
1. Application layer: The URL is entered into a browser and then a user request

5
 is made. Then this URL is converted into the IP1 address of the server that holds
the page needed by the user.
2. Transmission layer: Now that we know the IP address from the application
layer, the request for a page is sent to that address using the transmission layer.
This layer sends the request message in manageable pieces to the network to be
sent to the web server.
3. Network layer: Now these ‘manageable pieces’ need to be sent to the destination
(ie) web server. The next router/link to which the message is to be sent is decided
in this layer. These links ‘talk’ to each other in some sense and know where to
send messages to reach the web server.
4. Data Link layer: The data link layer deals with splitting the message bit by
bit and choosing the appropriate media to transfer them using (ie) Optic fiber,
Wireless links etc..
5. Physical layer: Finally the physical layer deals with transmitting the actual bit
signals over whatever media is chosen.
Now once the data is transferred to the physical layer of the web server, it climbs up
in the layers till the application layer of the web server is reached. The response of
the web server is transmitted back similarly. This by no means completely covers the
functionality of each layer but rather gives a flavour of each layer’s functions. It is easy
to see how the abstraction is helpful as now the application layer has no need to worry
about which media is used to transfer the bits and the Physical layer is oblivious to
what message it is transferring.
The abstraction helps to simplify the structure of the network by helping us deal with
one subproblem at a time.

Lecture 2

2.1 IP address
Each connected device has a unique identifier to describe it. This identifier is known
as the IP address of a device.
The IP address has a hierarchical structure. An example of an IP address is ‘72.85.5.25’.
This can be thought of as being similar to a postal address where the country of your
address is the highest level at which location is specified. After this the state, city, area
narrow down your location more and the message travels in an organised way from one
‘level’ to another.
In fact as discussed before each router at the Network layer transmits a message to
1
will be dealt with later, assume it is some id for a computer

6
a particular router which is chosen based on its IP address and the IP address of the
destination. How is this rerouting done?
• Readjusting weights: The weights of each connection can be adjusted to change
the shortest path to the destination
• Longest Prefix Match (Practical): There is a router table present which
gives us the IP corresponding to a router. When a packet has to make the choice
between routers it takes the router connected to the current router with the
longest prefix match when compared to the destination address.

2.2 Message Granularity, Delays

The size of the message which is being sent via the network changes depending on
which layer the transfer happens in. That is a message can be described in various
granularities.
• Application layer: Application dependent, a video/ a webpage etc..
• Transmission layer: TCP splits the message into segments, UDP splits it into
Datagrams
• Network layer: Transfers data as packets
• Data Link layer: Symbols
• Physical layer: Bit by Bit
As we saw in the last Lecture a router has some number of ‘in’ connections and ‘out’
connections which are connected together depending on which ‘out’ connection the
message is supposed to be sent. This ‘routing’ is done by putting each incoming packets
on queues corresponding to the outgoing connection we are supposed to send to.
This rerouting is done so that if the incoming rate to an out connection is greater than
its outgoing rate we have the queue as a buffer.
Why do we just not make the queue very large to prevent these ’drop offs’
• Cost: Memory is not free so we need to be aware of the trade offs of increasing
the queue size
• End-End delay: If the router has a buffer of say size Qmax and an output rate
of c bits/sec. Now if the queue is almost full and we get a new packet put in at
the very end, the packet takes Qmax
c
time to be put on the next connection. This
is called the End-End delay and clearly a large queue increasing the worst case
End-End delay
The total delay for a transmission of a packet through some K routers would be
k=K
X Qkmax
Delay = + Sd + Td
k=1
ck

7
Sd is called the speed of light delay and Td is the transmission delay. In most applica-
tions End-End delay is the significant bottle neck for the whole delay. Infact in some
applications we prefer dropping packets inorder to not have high delays2

2.3 Layering and Design Protocols

Any subproblem is handled by some protocol corresponding to the layer we are at.
We have divided networks into 5 layers. Specifically Application layer, Transmission
Layer, Network Layer, Data Link Layer , Physical Layer. This abstraction enables users
to interact only with the layer they are concerned with in that layer without having to
deal with the network as a whole.
Some advantages of layering networks are:
• Ease of development: Only certain problems need to be dealt with at each
layer
• Debugging: Ease in fixing new problems in each layer independently
• Flexibility of Physical technologies, Applications: As an example what-
sapp as an application only deals with that layer of the network. It doesn’t
interfere/have to deal with the particular intricacies of the physical technology
used by their users to connect to the network.
• Ease of Modification: We need to change only a particular layer to address
problems associated with it. There is no fear of breaking the system due to
modifications made to said layer.
• Choices at each layer: Each layer can use multiple media without breaking
compatability with the system.

Lecture 3
Disadvantages of layering networks:
1. There is some opaqueness about other layers. As an example let’s say a packet
is sent from a source to destination using a sequence of routers. If a packet is
dropped midway, TCP makes an assumption that they were dropped due to a full
queue. Infact there can even be wrong assumptions that a packet was dropped3 .
This mainly arises from the fact that the routers have little to no communication
going with the protocol of a higher layer.
2. There is redundancy at each level of the network. TCP handles retransmission,
but even MAC handles that. Let’s say that a packet transmission attempt in a
wireless link failed. The MAC will make sure that retransmission happens. But
2
Think of voice call where a delay would lead to not being able to communicate anything
3
example for another reason is interference in wireless links

8
 this is also taken care by TCP which is redundant.
3. Transmission is suboptimal. The sender of the message is unable to specify guar-
antees they want in the delivery of said packets. This is referred to as a ‘Best
Effort’ system where the network has no guarantees regarding the quality of ser-
vice

2.4 Latency Metrics

1. One-Way delay: If a packet is sent out at time t0 and it reaches the destination
at t1 , then the one way delay of the packet is t1 − t0 . However measuring one
day delay is difficult since it takes the direct difference in times measured at the
source and destination. This difference may drift apart over time due to both
systems operating at different clock cycles.
2. Round-Trip Time: Once a packet is recieved by the target it sends back an
acknowledgment message. The time taken from sending the messages to recieving
the acknowledgment is its round trip time.
3. Jitter: Jitter measures the variability in the latencies associated with the sending
some k packets. Let jitter be J. It can be written as

ek = |dk+1 − dk |
n
1 X
J= ek
n − 1 k=1

Lecture 4

2.5 Headers
There is some meta data about each packet/module of data generated when a message
is sent from one layer to the below layer. This metadata is added as a header to the
message itself that is shared with the next layer.
When a message goes to another layer below this header is not tampered with at all.
Rather the next header is just layered on like an onion on top of the previous header.

9
 Figure 4: How headers are built and removed

3 Quality of service
There are some metrics to determine the quality of the service provided by the network.
• Latency: Delay from the dispatch of a packet till it reaches destination
• Throughput: Amount of data that can be sent in given time
• Bandwidth: Amount of data that can be sent at the same time in network

Part II

Physical Layer
1 Physical Media
1. Twisted pair cables: It consits of a pair of cables twisted together (to cancel
out magnetic fields created by loops). The larger the number of cables and the
more the twisting the better it is.
There are different categories of cable each having its own data transmission rates.
2. Co-axial Medium: Co-axial cables consist of a series of wires covered by a wire
mesh to deal with magnetic fields. Depending on the thickness of the mesh data
transmission rates vary.
3. Optic Fibre:
• Single Mode: The optical fiber is so thin that only a single ray of light can
cleanly pass through it

10
 • Multiple Mode: A thicker fiber which is capable of transferring multiple rays
at the same time
Which of those is better? One may think it is multimode since it can transmit
multiple pulses together. However the rays in the multimode gets interferred with
each other if they are placed closer together.
Thus there is a need to delay the throughput in multimode inorder to make sure
the signals received are coherent.
Overall single mode turns out to be better.

Lecture 5
1.1 Attenuation
Attenuation is the loss of power when it is transmitted over a Physical media.

Pin
Attenuation = 10 log( )
Pout
Attenuation has units as dB/decibels.
Some examples on calculating Attenuation:
1.
Pin
=2
Pout

Attenuation = 10 log10 2
= 3dB
2. There are two identical wires which cause an Attenuation of 3dB. The wires are
connected and a signal is passed through the combined wire. Assume P1 is the
power left after the signal passed through one of the wires
Pin P1 Pin
10 log10 + 10 log10 = 10 log10
P1 Pout Pout
Thus total attenuation is the sum of attenuation of both wires.
Another thing to be noted is that power is directly proportional to the square of the
amplitude of a signal. Thus Attenuation can also be expressed as:
(Ain )2
Attenuation =10 log10
(Aout )2
Ain
=20 log10
Aout

11
1.2 Absolute Power in decibel scale
1 mW(milli Watt) is kept as the reference to express absolute power in the decibel scale.
That is power of P Watts can be written as 10 log10 10P−3 .
Absolute power has no significance to describe the quality of a transmission on its own.
What does matter is Recieved power relative to Noise power.

1.3 Frequency vs attenuation

Figure 5: Attenuation vs Length of cable

Clearly, attenuation increases with the frequency of the signal sent through it. This
does not make sense considering the wire to have only resistance. Thus it is clear that
the wire also has some inductance associated to make this behaviour happen.
However, the situation is a bit different for optical fibres.

12
 Figure 6: Attenuation vs Length of optic fibre

Here the attenuation shows non-linear behaviour which suggest some capacitative be-
haviour along with the inductance.
To prevent attenuation from decreasing signal quality, repeaters are used to boost up
the signal. They are placed at calculative distances to maximise their advantage.
Different signals can be sent across the same channel using a different Frequency. But
the speed at which data can be sent decreases as the frequency range of different
messages or Bandwidth increases. This can be calculated using Claude Shanon’s
definition of entropy.

13
1.4 Attenuation in Wireless signals

Figure 7: Attenuation in wireless communication

The power obtained depends on the area it is recieved from and the area it has spread
over. Power obtained (ie) PRx can be written as
P.A
PRx =
4πd2
P
In reality the equation turns out to be proportional to dα
where alpha can vary from 2
to 5.
Why is α > 2? It is due to interference and diffraction. If a big object obstructs a wave
it may bend around the obstacle, so it is non-trivial to note where signals will be weak.
Similarly when waves take longer paths and reflect off surfaces to reach a location they
can interfere destructively to decrease signal power further (Multi-path).
This is why there are random locations with good signals and others very close by with
bad signals.
One point is to note is that due to interference the attenuation in wireless transmission
is much much more than wired transmissions. Thus, some frequency bands are licensed
by different service providers and it is agreed that they will use those frequencies for
transmission.
What about WiFi? Well, there are some bands which are unlicensed and can be used
without any premium. However, here again we have to worry about interference.

14
 Lecture 6
1.4.1 MIMO

Multi Input Multi Output (MIMO) is a larger tower with several antennas to transmit
signals. Why do many different antennas help? Virtue of having several antennas
different signals can be sent on the antennas to strategically make the signals interfere
to only send a beam in a particular direction. Thus it uses multi-path communication
to its advantage.

2 Signalling
Now signals have to formualted and transmitted bit by bit. There are two ways to
formulate signals bit by bit. Assume a ‘1’ is described by +5V and ‘0’ is described by
-5V.
• Non-Return to Zero: To send a signal like ‘101’, +5v and then -5v and then
+5v is sent one after another
• Return to Zero: To send a signal like ‘101’, +5v and then the signal ‘returns’
to 0, then -5v and again returns to zero after some time and then +5v is sent.
What are some of the issues with Non-return to zero?
• The number of bits sent can only be calculated using the time interval of the
signal which is needed for one bit. The issue is that the clocks of the sender and
the reciever need not be in sync.
So the receiver may percieve a different signal.
This problem is rectified by Return to zero since the wave form indicates the
number of bits sent. The tradeoff here is that a higher frequency is needed to
send that waveform which implies higher attenuation.
• Another issue is Baseline wander. When a signal is amplified, non-ideally a DC-
offset is induced in the signal. If the offset is severe enough along with the noise
then a ‘0’ could be mistaken to be a 1.
To deal with this a High-Pass filter is used. A HPF removes all low frequency
signals which includes the DC offset. Infact since only a particular provider’s
signals are to be recieved, a bandpass filter is used to filter out signals not falling
in the desired range.
Apart from this a big issue is that regardless of the method used, lets say that a sequence
of 1s is sent as a signal. Now the average signal sent becomes 1 and as the signal gets

15
amplified an offset is created. Even if this is corrected by removing the offset now the
entire signal is lost.
Thus, to prevent this the average of the signal sent must be zero.
Too many issues phew :/
How to deal with all this?

2.1 Manchester coding

Encode a bit differently depending on the signal. Take an xor of the clock and the bit
to be sent.
• There is a signal transition for every bit period
• The average signal per bit period is 0

Data Clock Encoding

0 0 0
1 0 1
1 1 0
0 1 1

Table 1: Manchester Encoding

Figure 8: Manchester Encoding

16
 Lecture 7
How to determine the polarity of the signal sent if the voltages are switched. The last
few bits of the preamble can be dedicated to determining the polarity of the signal. Say
they are 111, if 111 is received the polarity would be correct and else polarity needs to
be flipped.
However, bit-errors can make this scheme breakdown quickly.

2.2 Differential Manchester Coding

Another more error-free option is to encode the messages with Differential Manchester
encoding. Rules:
1. 0 bit: The voltage in the first half of the time period is different from the voltage
in the second half of the Previous time period.
2. 1 bit: The voltage in the first half of the time period is same as the voltage in
the second half of the Previous time period.

3 Phase Modulation in wireless channels

Wireless signals can be used to represent bits in several ways. Frequency, amplitude
modulation (ie) encoding the message in values of frequency, amplitude is common.
However, another popular option is to use phase modulation, (ie) the message is put
into the phase of the signal that is sent.
Unrelated side track: Since each company has been allocated a band of frequencies
available to them. This implies that the fourier transform of the signal sent almost
completely lies within the appropriate frequency range.
Assume that f0 is the centre of this band and the ‘Bandwidth’ is 2∆. How do we make
sure the signal’s recieved has a frequency decomposition lying only in the given range?
One option is to use a bandpass filter at the receiver end to obtain only the signals in
some range.
Take a signal like s(t) = A cos(2πf t + ϕ). The signal recieved would be αs(t − δ) + n(t).
α is due to attenuation, δ is the propogation delay, n(t) is white noise4 (after bandpass
filter).
Side track over.
4
White noise is a signal that has energy at all frequencies and cannot be filtered out

17
3.1 Signals as vector spaces
Signals can actually form a vector space. Each signal is a ‘vector’ offset from the axis
corresponding to the phase and having length proportional to amplitude.
The angle between these vectors can be found using their inner product
Z T
< a(t), b(t) >= a(t)b(t)∂t
0

This can be represented as a 2-d diagram where one axis represents the sin component
of the wave and another the cos component. A phase shifted wave can be represented as
a combination of sin, cos wave. The length of the vector in this domain is proportional
to amplitude.
This is called the constellation diagram.

Lecture 8
How to get the constellation diagram for a given signal? We can dot the given signal
with ex and ey (ie) unit normal vectors of this vector space to get each component of
the wave.
Thus given a signal with a phase ϕ its 2d representation can be found to be put on the
constellation diagram.

3.2 BPSK encoding

Now how do we encode bits using the constellation diagram?
One option is to allocate a region in the 2-d vector space for ‘1’ and another for ‘0’
Assume that the +x axis points denote signals for bit as ‘1’ and -x axis points denote
signals for bit as ‘0’.

18
This is called Binary Phase Shift Keying. Note that even with attenuation and white
noise the amount the received signal shifts in a constellation diagram is lesser and thus
unlikely to cause a zero to be interpreted as a 1.

Lecture 9

3.3 QPSK encoding

The issue with BSPK is that a single signal/wave can only transmit one bit of infor-
mation. If we can partition the 2-d plane into say 4 regions and use a similar logic to
now assign a 2-bit encoding to each region, we can double our throughput.
This is called Quadrature Phase Shift Keying. One point to be noted is that while
assigning bits to region it is preferable to assign encoding such that strings which differ
in both bits are diagonally opposite regions so that even if a misinterpretation does
happen its more likely to be a one bit error.
This idea of more regions being able to encode more bits can be expanded more however
the more regions it is split into, the more error prone the encoding becomes due the
regions being more packed.

19
 Figure 9: Diagram to show bit encoding of each region

Lecture 10

Part III

Data Link Layer

1 Introduction
The Data link layer deals with preparing a packet to be sent across the physical medium
and also with error correction in received messages.
Its exact functionalities are:
• Framing: This deals with packaging packets into units called frames by adding
headers with the destination MAC address and also some other information, along
with redundancies to detect errors.
• Error Detection and correction: When a message is sent there are definite
error imposed due to environment. This layer deals with detecting and correcting
such errors by adding some redundancy in these messages.
• Medium Access: Deals with managing the shared medium, prevent collisions
(where two devices transmit simultaneously), and ensuring fair access for all de-
vices on the network.

20
1.1 Bit stuffing
Some networks keep transmitting data in the order of frame, sequence, frame. . .. A
sequence is a filer message sent between two frames. It is the bitstring ‘01111110’.
The receiver knows to ignore sequences. However, now the issue is what if an actual
message to be sent has some substring of the from ‘01111110’. To deal with this when
data is sent every time ‘11111’ (5 1’s) appears in a sequence the next bit is put to be
0. This 0 is removes when the receiver reads a sequence of 5 1’s and at the same time
sequences cannot appear since a sequence of 6 1’s is impossible. This insertion of 0‘s is
called bit stuffing.

1.2 Cyclic redundancy check

Now what if there are bit-flips in the message when it is transmitted?
There is a need to be able to identify and preferable correct some errors. For this
purpose some extra bits are appended to the end of the message. This is called the
Cyclic redundancy check(CRC).
What are some features we would like in CRC?
• Want to be easily able to detect a large variety of errors
• Creation/verification of this CRC must be efficient
• For any n-bit message some k bit CRC should be computable

1.3 Coding Theory

The process of coming with schemes to create such CRC’s is a field called coding theory.
The basic idea is as follows
• Any n-bit bitstring is mapped to an n+k bitstring
• Since there are only 2n valid bit strings in the n+k bitstring domain an error that
results in an invalid string can help us detect an error
• Infact given that both sender, receiver know the coding scheme we should be able
to map the ‘defective’ n+k bitstring back to the original message.

1.3.1 Hamming Distance

Hamming distance between two bitstrings(same length) is the number of bit flips needed
to transform one to the other. The minimum Hamming distance of a code is the
minimum hamming distance between all valid bitstring in the n+k bitstring domain
explained before.

21
1.3.2 Error Detection:

If the minimum Hamming distance is N(for a coding scheme), then any message with
less than N − 1 bit errors(but atleast 1) can never be a valid bitstring. If that was the
case min hamming distance for the code is less than N, which cannot be true.

1.3.3 Error Correction:

If the minimum Hamming distance is 2N + 1 (for a coding scheme), then any message
with less than N − 1 bit errors(but atleast 1) can be mapped to the corresponding
corrected bitstring accurately.
This bitstring will be the valid bitstring closest to the one with errors. If that was
not the case min hamming distance for the code is less than 2N+1, since the bitstring
closest to the one with errors and the corrected bitstring will have a hamming distance
less than 2N+1.

Lecture 11

1.4 Galois Theory

A Galois field, named after the mathematician Évariste Galois, is a finite field that
contains a set number of elements and supports operations of addition, subtraction,
multiplication, and division (excluding division by zero).
We define a galois field where addition is replaced by xor.
The claim is that for any given data bit string, the remainder obtained when the
data(appended with k zeros) is divided5 by a special k+1 bit generator gives us a CRC.
Example:
Data is ‘110110’, generator is ‘1101’. Note that here there is no carry in the addition,
just bit by bit addition.
5
Not exactly but similar operation

22
 Figure 10: Example for CRC generation

So the algorithm is similar to long division and just uses additions one after another
instead of subtraction.
This algorithm can in fact be simulated by a simple logic circuit.
How can this CRC be used for error correction at the receiver side?
• If the received message on divison with the generator does not give 000 as a
remainder then there is an error
• Take the data part of the message and append 000 to it and perform division with
the generator. If the remainder obtained from this does not match with the CRC
there was an error in the transmission

Lecture 12

2 Polynomial Arithmetic
As done before in Galois fields, division is still defined using Addition (xor), multipli-
cation (normal).
But encoding is now being done as the coeffiicent of Polynomials. For example, some-
thing like ‘110110’ is encoded as x5 + x4 + x2 + x. In this context what does it mean
for A(x) to be divisble by D(x), basically

A(x) = B(x)D(x)

23
Let’s try to understand how to use this now,
Say P (x) is the message to be sent (clear from before Polynomial is equivalent to
bitstrings), lets say some bits get flipped in the Polynomial. The bits that get flipped
corresponds to a polynomial E(x).
So the total received message can be denoted as P (x) + E(x). Now if the generator is
known across both devices which have the message and it also divides P (x), then error
detection can be done by checking if P (x) + E(x) is divisible by C(x).
For this method to work, E(x) cannot be divisible by C(x). But is this the case?
• Single Error Bit: E(x) = xi for some i, Suppose C(x) = xk + 1 then C(x)
cannot divide E(x),
To see why think of a divisor for this operation, say D(x)

C(x)D(x) = xi (1)
(xn + · · · + 1)(xm + · · · + xq ) = xi (2)

The above is not possible.

• Two Bit Errors: E(x) = xj + xi , (j > i) E(x) = xi (xj−i + 1)
Suppose C(x) is of the form xk + · · · + 1
Now again the problem reduces to if C(x) can divide P (x)+E(x), which basically
is asking if it can divide E(x).
Order of a Polynomial: The smallest ‘r’ such that C(x) divides xr + 1 is called
its order.
Methods are known to find C(x) such that their orders are very high. Example:
k = 16, C(x) = x16 + · · · + 1, then we can find c(x) s.t it will not divide any xp + 1,
if p < 216 − 1.
• Odd number of Errors:
1. If C(x) = (1 + x)(...)(...), this can catch all odd number of errors.
2. If C(x) has even number of terms, it can also capture all odd number of
errors.
Why is this true?
1. Assume that a Polynomial E(x) has an odd number of terms, E(1) is ‘1’,
since addition is xor. Similary C(1) is 0. Since the term 1 + 1 becomes 0.
Thus C(x)*D(x) = E(x) can never be true since the equation fails for x = 1.
2. Similar argument applies to argue that C(1) is 0 when it has even number
of terms.
• Burst of Errors: Many times, due to interference we have a consecutive sequence
of bits which get flipped.
Thus
E(x) = xi+l−1 + xi+l−2 + · · · + xi
, which can also be written as (xi )(xl−1 + xl−2 + · · · + 1)

24
 If our carry is of form C(x) = xk + xk−1 + xk−2 + · · · + 1. It can detect all burst
errors of length less than l, since it cannot divide the error term. If you are not
convinced think of a dividend D(x) then E(x) = C(x)D(x), which is not possible.

2.1 Some Polynomial CRC’s

CRC-32: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Lecture 13

3 Media Access Control

Media Access Control protocol takes care of managing shared resources over a network.
It helps a device access the medium of communication (a wire, wireless tower) in-order
to start transmitting data. The protocol manages which device has control over the
shared media so that multiple people don’t use the network at once and thus start to
interfere with one another.
Also, there is a need for each need for each message to be addressed to the destination
so that the message can reach the receiver accurately, which is also taken care of by the
MAC.
One way to do this is to give a particular frequency bandwidth to each device as
an identifier. However, this method cannot easily accommodate the addition of new
devices. Further it hampers the Bandwidth of the network as more devices split up the
available bandwidth. To enable this functionality, the MAC protocol requires that each
‘Network Interface Card (NIC)’ has a unique MAC address. This is taken care by the
manufacturer and hard coded into the card.
MAC address come out of the size of 48 bits, so for the reasonable future we have
enough address to get a MAC address for all cards.

3.1 Interference
What about interference? If it can be ensured that only one device uses the network at
one time, then interference is taken care of. However in some networks based on WiFi,
ethernet allow collisions and have methods to deal with them. We will look into those
further.
Possible methods:

25
 • Frequency-Based: Will different frequencies help? How to allocate different
frequencies to devices? This method however still has the Bandwidth issue men-
tioned earlier. Frequency Division Multiple Access(FDMA)
• Time-Based: A leader device can be assigned such that it sends a special mes-
sage to send to a device to indicate that it is their turn to send a message. The
issue is that if A doesn’t use a time slot then that time is wasted. This is referred
to as Time Division Multiple Access(TDMA)
• Token-Based: There is a ‘token’ message the owner of which is allowed to
transfer messages. A token release message is sent if a particular device passes
the token to the next device. The token release message(TRM) has a identifier
for the device which is going to receive the token.
A common form of implementing the token system is to connect devices in a
ring topology and have the token sent from one device to the next in a step by
step fashion. In this system fairness is maintained since each system gets an
opportunity to transmit its message within one cycle.
The second one is a better option in some ways since it completely negates interference.
A smart leader can also assign more time slots to a device if it sends a message with
many packets.

Lecture 14
3.1.1 Frequency and time

There is a possibility to combine both frequency and time based methods to prevent
interference. Note that this is also a leader based system and we call the leader the
‘base station’.
Say a particular frequency band is assigned to a company6 . This band can be split up
into further smaller bands called sub-channels. Now these sub-channels can be further
divided into time chunks to entirely split up the frequency * time domain into a grid.
How to decide who uses which block in the grid? The base station sends a scheduling
message before transmission to denote which frequency and time slot is used for which
message.
Any user first synchronises with the base station for purposes like syncing up this clock.
So they also receive this scheduling message once they connect with the base station.
This method of avoiding interference is called Orthogonal Frequency Division Mul-
tiple Access What is the point of all this hassle over simple time sharing? Well clearly
more information can be pumped through the system compared to when there is only
6
This is called a frame

26
one user per time slot.
Down-link: When user receives data from the base station
Up-link: User sends data to the base station

3.1.2 Issues with Central Coordinator

• Single point of failure
• May not be possible in certain situations (when the bandwidth is unlicensed)

3.2 No central coordinator

What are the wants from such a system?
• Plug and play: need to be able to connect and disconnect any device from the
network
• No central coordinator exists
How to prevent interference without a coordinator?
The idea is that if only one node transmits most of the time, then we rarely have
collisions. Why is a collision so bad? When multiple nodes transfer messages at the
same time, they all interfere and become meaningless and cannot be split up.
Main idea → If there is a collision detected then stop transmitting. How to detect
collisions? Since the combined signal will have a much higher energy, a collision can be
detected by this increase in energy.

27
 Lecture 15
3.2.1 Carrier sense Multiple Access (CSMA)

This is the MAC policy used in ethernet to prevent interference. Again as discussed
before the sudden increase in energy when a collision occurs can be used for collisions
detection. In carrier sensing the device probes the medium/link to see if some other
device is using the medium to transmit a message and waits for the channel to get free
before transmission.
This is referred to as carrier sensing. There are two approaches the protocol can take
to deal with collisions
• Collision Detection: A message is sent till a collision is detected, after a collision
is detected transmission is stopped and the message is resent.
• Collision Avoidance: A message is sent such that collisions are avoided com-
pletely.

3.2.2 Collision Detection

There are still some issues with collision detection. So far, we rely on the fact that if C
is sending a message and it detects a collision then it can stop transmitting. But what
if the collisions starts occuring (spatially) farther away from the source of the message.
Look at the figure given below, though not clear try to imagine a case where C sent
a message(yellow) and it does not detect the white message when sending. A collision
happens later on(between C,D) which both A,C will not detect.
To deal with this case we use a Jamming Signal. So when one device detects a
collision like in this case D, apart from stopping its own transmissions it also sends a
jamming signal which informs all devices to stop transmitting and to wait.
Thus the devices contributing to the collision get the message to stop and retransmit
their message.

28
3.2.3 Random Wait time

There is another issue with the current form of CD7 . If A, B both send messages
which collide and both of them retransmit after a fixed interval after collision, then
it is possible that A starts sending before B’s message is seen and vice versa and the
collision just occurs again.
To prevent this we allocate a random time to wait to each node after a CD. This random
time can be split up as R.∆ where R is a random number from a uniform distribution
chosen by the node(always integer).
Let us assume that R chosen by A, B differ by one. Now the time A waits after B
started its transmission is just ∆. All we want to make sure is that A can see B’s
message before it is ready to transmit so that carrier sensing(don’t forget this guy still
exists :)) can make sure it waits till B is done to start transmitting.
It can be shown that if ∆ is more than the round trip time and Ra > Rb then b starts
transmitting(and A senses it) before A starts respecting. This makes sense since it takes
a trip for the jamming signal to reach all devices and one more trip for the message
from B to reach A. Thus ∆ can be put as a constant slightly greater than the highest
possible value of RTT(round trip time) in a network.

3.2.4 Flowchart to represent CSMA

The flowchart below represents the algorithm that is to be run at every node inorder
to implement CSMA-CD.
7
collision detection

29
Some new things have been mentioned in the diagram. Let us see what those mean.
Exponential Back-off: The space of possible R values for the random wait time is
intially kept to be small. However, as the number of misses increases this range is
doubled inorder to increase the probability that the difference between waiting times in
two nodes is larger. This is called Exponential backoff. It helps to sacrifice by having
delay in transmission incase retransmission efforts are continuosly failing.
Also the reason to wait for 9.6µs is to give some time for the receivers to process the
frames from the senders.

Lecture 16
3.2.5 Limits on frame size

Minimum Frame size:

Why must there be a minimum frame size? Assume A is sending a signal and then B
detects it is a collision. To make sure even A detects that there is a collision we must
make sure that even if B’s message starts just as A’s message ends, it still makes sure
to collide with A. For this to be true A must be long enough that it takes atleast RTT
units of time to transmit it. To see why refer the diagram.

30
Assuming that ∆ = 51.2µs as before and that rate of transmission is 10 MBps, we get
that the frame must be 64 Bytes long.
Minimum frame = RTT * Bitrate
Maximum Frame size:
The issue with having arbitrarily big frames is that the probability of bit errors occuring
grows with the size of the frame. Apart from this very big frames take significant
amounts of time to send and thus lead to one device monopolising the network for long
durations

3.2.6 Format of an ethernet frame

Figure 11: Structure of an ethernet frame

3.3 MAC in Wifi

What is the primary difference in the network in a wirless setting?

31
First let us define something called an access point. It can be thought of as a device
which bridges a wireless connection network to a wired network. It connects to multiple
devices wirelessely and is itself connected to a wired network.
Let us consider two devices A, B and an access point AP. Even if both A, B are in
range of the AP they need not be in each other’s range. Thus a message sent from A
to AP need to necessarily reach B and vice versa.
So will carrier sensing still work in this case? Well due to the fact that unlike a wired
network some devices are basically invisible to others probing what you receieved to
detect collisions is insufficient. This is referred to as the Hidden terminal problem.
This is due to the extremely large attenuation in wireless networks compared to wired
ones.
Apart from this there is the fact that due to attenuation even closeby towers do not see
a huge increase in energy when a collision occurs.
How do we then decide if a transmission was successful? We use an acknowledgment
message from the receiver. Unless this (ACK) acknowledgment message was received,
we retransmit.

3.3.1 Virtual Carrier Sensing

The Network Allocation Vector(NAV) tells us how long a channel is occupied by a

sender. Apart from the message, preceding it we send a Request To Send (RTS) and
receive a Clear To Send(CTS) message from the receiver. Even if the other nodes, B in

32
this case cannot hear the RTS they have to hear the CTS since it is from the receiver
which must be within range. Thus it knows to remain silent during that duration.
• What if A sends RTS but can’t hear CTS. A assumes a collision and retransmits
the RTS.
• What if the ACK was not received by A? The data alone is retransmitted.
This system seems quite robust since now the problem of retransmission is divided into
several levels. Receiving the CTS ensures that the connection is established after which
the device can completely focus on transmitting the data.
Note that this system is optional and can be switched off if needed.

Lecture 17
3.3.2 Modulation in WiFi

Why would someone disable RTS, CTS is a question that comes up now. The RTS, CTS
blocks are much smaller than message and greatly reduce the possibility of collisions.
The issue is that RTS, CTS cannot afford to have bit errors and thus are send at much
lower modulation rates than the actual data which can deal with biterrors. BPSK is
usually the modulation used for RTS, CTS whereas QPSK is used for the acknowledg-
ment and the actual data frame. Thus at times especially when collisons occur rarely
the tradeoff of having virtual carrier sensing is not worth it and is switched off.

3.3.3 Exposed Terminal problem

Consider devices A, B, C and D arranged as shown below.

33
Clearly in this case B→ A communication and C→D communication can happen freely
without interference. This is since A,C and B,D are not withing hearing ranges of each
other.
However, with carrier sensing with/without RTS-CTS B transmits which is sensed by
C and thus it is silent.
But the WiFI protocol does not bother with this case and is okay with making this
tradeoff.

3.3.4 DIFS and SIFS

If we observe the packet diagrams for example in section 3.3.1, we can notice that
there is a small gap between the RTS and CTS packets. Similarly between Data and
acknowledgment.
This is referred to as SIFS (Short Inter Frame Spacing). Why is this gap necessary?
First of all the receiver receives some finite time to process each packet so a gap between
these packets is needed. Further in many NIC (Network interface Cards) the receiving
and transmission circuits are different and some finite time is required to swap from
one to another.
Now what an issue comes up. What if a device carrier senses the SIFS, assumes network
is free and starts transmitting? To prevent this and few other issues we also set a gap
between two series of transmissions for a single data packet. This is called the DIFS
(or) Distributed Inter Frame Spacing.
Another point to note here is that in the wifi protocol time is divided into discrete
intervals called slots.
We also make sure that while carrier sensing the device will make sure that the channel
is free for atleast DIFS time before starting a transmission. What does this do? First
off all we will never start transmitting during an SIFS time period since we have to
wait the channel to be free for atleast DIFS amount of time (DIFS > SIFS).

3.3.5 Contention Window

Now obviously if all devices only wait for constant amount of time and then subsequently
start at the same time, we are asking for collisions.
Thus we want to make each device wait for a random amount of time. The difference
between the waiting time of two devices must be large enough that the later device
must be able to hear the transmission of the one who transmitted first so that it can
carrier sense and wait for that transmission to get over.
The Contention window(CW) is the space of possible waiting time periods from which

34
we randomly draw a sample. It is initalised to a range of (0, 15) slots intially and is
double at every failed attempt. Why is it increased? An increased CW means the
probability of the waiting times differing for two devices by a large amount is larger.
Thus we have a lesser possibility for a collision. However the CW is upper capped to
1023 slots.
Another thing to note. Let us say A, B both are ready to transmit and drew a random
waiting time from the contention window say 2, 4. Now A sends first and B waits for
A to finish. Is it fair for B to again draw a random waiting time the next time the
medium is free? No, since B already waited for sometime. So B just continues with the
new waiting time set to the remaining waiting time, 2 in this case.
This is implemented as follows, a variable is set to the random sample value and every
idle time slot it is decremented by 1. If it reaches 0 a message is transmitted and post
transmission a new sample is drawn for the waiting time.
Fairness however is a slight issue here. Let us say that a device C has had 2 failed
collisions, as mentioned before its Contention window doubles. However if a device G
now tries to transmit it is very likely to have a smaller waiting time and transmit first.
Empirically, he DIFS of the protocol is set to be SIFS + 2 ∗ slot duration.
Coding rate: Just a random term. A coding rate of pq implies that for every q bits
sent, p of those are data bits and q - p are bookkeeping/extra bits.

Lecture 18
So far communication between two machines can only happen if they are directly con-
nected by a link. One huge problem with this is that when a machine sends a frame all
the other machines in the network/subnetwork hears that message.
A much smarter solution is to have several subnetworks that are connected by ‘smart
links’ which can connect appropriate subnetworks together so that a minimal number of
machines are a part of the communication path at any given time. From our discussion
on collisions it is easy to see that more machines will result in more collisions and thus
be a bigger headache.

4 Ethernet Switching
As mentioned before we have a smart link for connecting these ‘subnetworks’. These
smart links are called network switches. How do these work with the ethernet system?
Consider the scenario in the diagram,
How do we know which device is connected to which port? Remeber that we also need

35
flexibility atleast to the point where we can remove a device from one port and connect
it to another.
What if we maintain a table which is maintained manually by an admin? This requires
a manual update at every addition/port change for a device. Leaving up this much to a
human being is basically asking for mishaps to happen. Anything from a missed entry
to a wrong entry can mess up the entire system.

4.1 Automatic MAC address maintanence

The table mentioned above should preferably be maintained automatically. One possi-
bility is to add an entry in the table everytime a message is sent from a device.
Let us say A sends a message to B, then we can store A‘s MAC address corresponding
to the port which recieved the message and we can have an expiry time for this entry.
Once this expiry time has elapsed this entry is invalidated.
Note that the table is populated when a device is a sender, and the table is used when
the device is a receiver.

Destination MAC Port expiry

A 1 12
C 1 10
B 0 14
D 0 9
E 1 13

Table 2: Example of MAC address table

36
4.2 Loops in the network
What if A tries to send a message to B and B does not exist on the network? The
message is forwarded from every port connected to A and then the message just keeps
getting forwarded and loops around in the network.
These loops are undesirable and these messages unnecessarily occupy the network. One
possible idea to prevent this is called time to live. Every packet has a portion allocated
to track how many times it was forwarded. If this number exceeds some fixed amount,
then the packet is dropped.

4.2.1 Spanning tree protocol

STEPS:
1. Elect the Root Switch. This can also be controlled by the admin by configuring
IP addresses appropriately
2. The root ports are detected (port in a switch closest to the root)
3. Disable some of the ports for forwarding Data Frames

Lecture 19
Now how to we communicate to bridges regarding who the root bridge is? Every
bridge is assigned an ID which is made of two components. The first 2 Bytes is called
the configuration ID and can be changed in a network. But the later 6 Bytes is the
smallest MAC address across all devices connected on all ports of that bridge.
The configurable part helps us to force to make a particular bridge as a route. The
Bridge with the smallest bridge ID becomes the root.
Every bridge broadcasts a message of the form (Y, d, X, P ortId).
• Y - Who the device thinks they root is
• d - Distance from assumed root
• X - Device who sent the message
Intially all the bridges assume they are the root and thus send a message of the form
(Si , 0, Si ) where Si is the bridge id (the configurable part of the ID). Eventually as
bridges hear these messages they update their assumption, distances and eventually all
of them know the true bridge and their distances from it.
Once this information is known, we also know the distances of each port from the root.
If there is a unique closest port, then we choose that port. Else we choose the port that
is connected to the bridge with the smallest id(tiebreaker rule).
For each subnetwork we find the designated port, (ie) the port which connects it to the

37
bridge closest to the root. If multiple ports have the same distance, ties are broken on
basis of the sizes of the MAC address.
Any port which is not the root port of a bridge (or) the designated port of a subnetwork
is disabled. Thus every subnetwork is connected to a port and all ports have a root
port connecting it to the spanning tree.

Lecture 20
Not yet completely done

5 Issues with Ethernet Switching

• MAC addresses are given to a hardware at the time of manufacturing. Thus the
addresses of all the devices in a network is spread all over the place. There is
no common addressing scheme that addresses the devices close by with similar
addresses
• If all the devices are directly connected with ethernet switching, when a root/link
fails then the entire spanning algorithm has to be run again. This may happen
often in larger networks since there are more nodes which can possibly fail
• Paths for data flow is not optimal since every packet travels up the tree to reach
the root and then down the tree to reach the destination
• Broadcasts in the network happen often, but a broadcast or particular message
transfers from one end of the network to another is very expensive
These issues make the current system not so scaleable.

Part IV

Network layer
In this layer there is an universal addressing scheme. The addressing is called the IP
address scheme. We may have seen numbers like ‘62.5.7.20’ to denote IP addresses.
These are 32 bit addresses written in human readable form. Each byte is seperated by
a ‘.’.
How are these addresses assigned? A subnetwork is assigned an address like ‘10.22.*.*’.
Every machine in the subnetwork must have its prefix match with the networks address.
The ‘*’ can be replaced by anything.
Why is this good? Now the address has an hierarchy built into it. The first few bits

38
denote at a very big granularity the location of the device. As the message gets closer
to the device more bits are looked at to figure out where this device is.
Obviously hardware addresses cannot have IP configured since the device’s location
would affect this address. Thus this address needs to be figured out manually or with
the help of some protocols.

39