Data Link Layer

Data Link Layer
Module:3
Data Link Layer - Services
• The data-link layer is located between the physical and the network layers.
• The datalink layer provides services to the network layer; it receives services from
the physical layer
• Framing - each node needs to encapsulate the datagram (packet received from the
network layer) in a frame before sending it to the next node. The node also needs
to decapsulate the datagram from the frame received on the logical channel
• Flow Control - If the rate of produced frames is higher than the rate of consumed
frames, frames at the receiving end need to be buffered while waiting to be
consumed (processed)
• Error Control - The error needs first to be detected. After detection, it needs to be
either corrected at the receiver node or discarded and retransmitted by the
sending node
Error Detection and Correction
• Types of Errors:
• The term single-bit error means that only 1 bit of a given data unit (such as a byte,
character, or packet) is changed from 1 to 0 or from 0 to 1.
• The term burst error means that 2 or more bits in the data unit have changed from 1 to 0
or from 0 to 1.
• The number of bits affected depends on the data rate and duration of noise
Redundancy
• The central concept in detecting or correcting errors is redundancy.
• To be able to detect or correct errors, we need to send some extra bits with our data.
• These redundant bits are added by the sender and removed by the receiver.
• Their presence allows the receiver to detect or correct corrupted bits.
• Coding
• Redundancy is achieved through various coding schemes.
• The sender adds redundant bits through a process that creates a
relationship between the redundant bits and the actual data bits.
• The receiver checks the relationships between the two sets of bits to
detect errors.
• The ratio of redundant bits to data bits and the robustness of the
process are important factors in any coding scheme.
• BLOCK CODING
• In block coding, we divide our message into blocks, each of k bits, called data
words.
• We add r redundant bits to each block to make the length n = k + r. The resulting
n-bit blocks are called code words.
• Error Detection
• How can errors be detected by using block coding?
• If the following two conditions are met, the receiver can detect a change in the
original codeword.
1. The receiver has (or can find) a list of valid codewords.
2. The original codeword has changed to an invalid one.
• Hamming Distance
• Hamming distance between two words (of the same size) is the number of
differences between the corresponding bits.
• We show the Hamming distance between two words x and y as d(x, y).
• Hamming distance between the received codeword and the sent codeword is the
number of bits that are corrupted during transmission.
• For example, if the codeword 00000 is sent and 01101 is received, 3 bits are in
error and the Hamming distance between the two is d(00000, 01101) = 3.
• The Hamming distance can easily be found if we apply the XOR operation (⊕) on
the two words and count the number of 1s in the result.
• Note that the Hamming distance is a value greater than or equal to zero.
Hamming Distance
• Minimum Hamming Distance for Error Detection
• In a set of codewords, the minimum Hamming distance is the smallest
Hamming distance between all possible pairs of codewords.
• The minimum Hamming distance is 2.

• This code guarantees detection of only a single error.
• For example, if the third codeword (101) is sent and one
error occurs, the received codeword does not match any
valid codeword.
• If two errors occur, however, the received codeword may
match a valid codeword and the errors are not detected.
Even parity bit
• In the case of even parity, for a given set of bits, the
number of 1’s are counted.
• If that count is odd, the parity bit value is set to 1,
making the total count of occurrences of 1’s an even
number.
• If the total number of 1’s in a given set of bits is already
even, the parity bit’s value is 0.
Odd Parity bit
• In the case of odd parity, for a given set of bits, the
number of 1’s are counted.
• If that count is even, the parity bit value is set to 1,
making the total count of occurrences of 1’s an odd
number.
• If the total number of 1’s in a given set of bits is already
odd, the parity bit’s value is 0.
Hamming Code
• Hamming codes belongs to family of Block codes.
• Hamming codes can detect one-bit and two-bit errors, or correct
one-bit errors without detection of uncorrected errors.
• By contrast, the simple parity code cannot correct errors, and can
detect only an odd number of bits in error.
Hamming Code - Single-bit error correction
To correct an error, the receiver reverses the value of the altered bit.
To do so, it must know which bit is in error.
Number of redundancy bits needed
• Let data bits = m
• Redundancy bits = r
Total message sent = m+r
The value of r must satisfy the following relation:
2r ≥ m+r+1
General Algorithm of Hamming code
1. Write the bit positions starting from 1 in binary form

2. All the bit positions that are a power of 2 are marked as parity bits (1, 2, 4, 8, etc.).
3. All the other bit positions are marked as data bits.
4. Each data bit is included in a unique set of parity bits, as determined its bit position in binary form. a. Parity
bit 1 covers all the bits positions whose binary representation includes a 1 in the least significant position
(1, 3, 5, 7, 9, 11, etc). b. Parity bit 2 covers all the bits positions whose binary representation includes a 1 in
the second position from the least significant bit (2, 3, 6, 7, 10, 11, etc). c. Parity bit 4 covers all the bits
positions whose binary representation includes a 1 in the third position from the least significant bit (4–7,
12–15, 20–23, etc). d. Parity bit 8 covers all the bits positions whose binary representation includes a 1 in
the fourth position from the least significant bit bits (8–15, 24–31, 40–47, etc). e. In general, each parity bit
covers all bits where the bitwise AND of the parity position and the bit position is non-zero.
5. Since we check for even parity set a parity bit to 1 if the total number of ones in the positions it checks is
odd.
6. Set a parity bit to 0 if the total number of ones in the positions it checks is even.
Hamming Code
Hamming Code
Hamming Code
Example of Hamming Code with even parity
Single-bit error
Error
Detection
Problem 2
Illustrate Hamming code for single bit error detection and correction for the following
message: 1011001
Data transferred:
Error detection and correction: Suppose the 6th bit is changed from 0 to 1 during data transmission, then it
gives new parity values in the binary number:
The bits give the binary number 0110 whose decimal representation is 6. Thus, bit 6 contains an error. To
correct the error the 6th bit is changed from 1 to 0.
Checksum
• In checksum error detection scheme, the data is divided into k
segments each of m bits.
• In the sender’s end the segments are added using 1’s complement
arithmetic to get the sum. The sum is complemented to get the
checksum.
• The checksum segment is sent along with the data segments.
• At the receiver’s end, all received segments are added using 1’s
complement arithmetic to get the sum. The sum is complemented.
• If the result is zero, the received data is accepted; otherwise
discarded.
Checksum
Checksum
An example
Cyclic redundancy checking
• Probably the most reliable redundancy checking technique for error
detection is a convolutional coding scheme called cyclic redundancy
checking (CRC).
• With CRC, approximately 99.999% of all transmission errors are
detected
• Unlike checksum scheme, which is based on addition, CRC is based on
binary division.
• In CRC, a sequence of redundant bits, called cyclic redundancy check
bits, are appended to the end of data unit so that the resulting data unit
becomes exactly divisible by a second, predetermined binary number.
• At the destination, the incoming data unit is divided by the same
number. If at this step there is no remainder, the data unit is assumed to
be correct and is therefore accepted.
• A remainder indicates that the data unit has been damaged in transit
and therefore must be rejected.
CRC
CRC
CRC
CRC – An example
CRC - Polynomials
Flow Control - Framing
• The data-link layer, on the other hand, needs to pack bits into frames,
so that each frame is distinguishable from another.
• Our postal system practices a type of framing.
• The simple act of inserting a letter into an envelope separates one
piece of information from another;
• the envelope serves as the delimiter.
• In addition, each envelope defines the sender and receiver addresses,
which is necessary since the postal system is a many to-many carrier
facility.
• Framing in the data-link layer separates a message from one source to a
destination by adding a sender address and a destination address.
• The destination address defines where the packet is to go;
• The sender address helps the recipient acknowledge the receipt.
• Although the whole message could be packed in one frame, that is not
normally done.
• One reason is that a frame can be very large, making flow and error
control very inefficient.
• When a message is carried in one very large frame, even a single-bit
error would require the retransmission of the whole frame.
• Frames can be of fixed or variable size.
• In fixed-size framing, there is no need for defining the boundaries of
the frames; the size itself can be used as a delimiter
• In variable-size framing, we need a way to define the end of one
frame and the beginning of the next.
• Historically, two approaches were used for this purpose: a character-
oriented approach and a bit-oriented approach
Character-Oriented Framing
• In character-oriented (or byte-oriented) framing, data to be carried are 8-bit
characters from a coding system such as ASCII
• Character-oriented framing was popular when only text was exchanged by the data-
link layers.
• The flag could be selected to be any character not used for text communication.
• Now, however, we send other types of information such as graphs, audio, and video;
any character used for the flag could also be part of the information.
• If this happens, the receiver, when it encounters this pattern in the middle of the data,
thinks it has reached the end of the frame.
• To fix this problem, a byte-stuffing strategy was added to character-oriented framing
• Byte stuffing is the process of adding one extra byte whenever there is a flag or
escape character in the text.
Character-Oriented Framing
Bit-Oriented Framing
• In bit-oriented framing, the data section of a frame is a sequence of
bits to be interpreted by the upper layer as text, graphic, audio, video,
and so on.
• However, in addition to headers (and possible trailers), we still need a
delimiter to separate one frame from the other.
• Most protocols use a special 8-bit pattern flag, 01111110, as the
delimiter to define the beginning and the end of the frame
Bit-Oriented Framing
• Bit stuffing is the process of adding one extra 0 whenever five
consecutive 1s follow a 0 in the data, so that the receiver does not
mistake the pattern 01111110 for a flag
Flow Control
• Whenever an entity produces items and another entity consumes
them, there should be a balance between production and
consumption rates.
• If the items are produced faster than they can be consumed, the
consumer can be overwhelmed and may need to discard some items.
• We need to prevent losing the data items at the consumer site.
Sequence Numbers
• Error control requires that the sending transport layer knows which packet
is to be resent and the receiving transport layer knows which packet is a
duplicate, or which packet has arrived out of order.
• This can be done if the packets are numbered.
• When a packet is corrupted or lost, the receiving transport layer can
somehow inform the sending transport layer to resend that packet using
the sequence number.
• The receiving transport layer can also detect duplicate packets if two
received packets have the same sequence number.
• The out-of-order packets can be recognized by observing gaps in the
sequence numbers.
Sequence Numbers
• Packets are numbered sequentially.
• However, because we need to include the sequence number of each
packet in the header, we need to set a limit.
• If the header of the packet allows m bits for the sequence number,
the sequence numbers range from 0 to 2m − 1.
• if m is 4, the only sequence numbers are 0 through 15, inclusive.
However, we can wrap around the sequence. So the sequence
numbers in this case are
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ..
Sliding Window
• The buffer is represented as a set of slices, called the sliding window,
that occupies part of the circle at any time.
• At the sender site, when a packet is sent, the corresponding slice is
marked.
• When all the slices are marked, it means that the buffer is full and no
further messages can be accepted from the application layer.
• When an acknowledgment arrives, the corresponding slice is
unmarked
Sliding Window
• The sequence numbers are in modulo 16 (m = 4) and the size of the
window is 7
Stop-and-Wait Protocol
• Uses both flow and error control
• In this protocol, the sender sends one frame at a time and waits for an acknowledgment
before sending the next one.
• To detect corrupted frames, we need to add a CRC to each data frame.
• When a frame arrives at the receiver site, it is checked.
• If its CRC is incorrect, the frame is corrupted and silently discarded.
• The silence of the receiver is a signal for the sender that a frame was either corrupted or lost.
• Every time the sender sends a frame, it starts a timer.
• If an acknowledgment arrives before the timer expires, the timer is stopped and the sender
sends the next frame (if it has one to send).
• If the timer expires, the sender resends the previous frame, assuming that the frame was
either lost or corrupted.
• This means that the sender needs to keep a copy of the frame until its acknowledgment
arrives.
Stop-and-Wait Protocol
Stop-and-Wait
Protocol
• The first frame is sent and
acknowledged.
• The second frame is sent, but
lost. After time-out, it is resent.
• The third frame is sent and
acknowledged, but the
acknowledgment is lost. The
frame is resent.
Go-Back-N Protocol (GBN)
• To improve the efficiency of transmission (to fill the pipe), multiple packets must be
in transition while the sender is waiting for acknowledgment.
• The key to Go-back-N is that we can send several packets before receiving
acknowledgments, but the receiver can only buffer one packet. We keep a copy of
the sent packets until the acknowledgments arrive
• Note that several data packets and acknowledgments can be in the channel at the
same time.
• Acknowledgment Numbers: An acknowledgment number in this protocol is
cumulative and defines the sequence number of the next packet expected.
• For example, if the acknowledgment number (ackNo) is 7, it means all packets with
sequence number up to 6 have arrived, safe and sound, and the receiver is
expecting the packet with sequence number 7.
• Send Window
• Sliding window of size 7 (m = 3) for the Go-Back-N protocol.
• Receive Window
• The receive window makes sure that the correct data packets are
received and that the correct acknowledgments are sent.
• In Go-Back-N, the size of the receive window is always 1.
• The receiver is always looking for the arrival of a specific packet. Any
packet arriving out of order is discarded and needs to be resent.
• Timers
• Although there can be a timer for each packet that is sent, in our protocol we use only
one.
• The reason is that the timer for the first outstanding packet always expires first.
• We resend all outstanding packets when this timer expires.
• Resending packets
• When the timer expires, the sender resends all outstanding packets. For example,
suppose the sender has already sent packet 6 (Sn = 7), but the only timer expires.
• If Sf = 3, this means that packets 3, 4, 5, and 6 have not been acknowledged; the sender
goes back and resends packets 3, 4, 5, and 6.
• That is why the protocol is called Go-Back-N.
• On a time-out, the machine goes back N locations and resends all packets.
Go-Back-N Protocol (GBN) – Ex 1
• This is an example of a case where the forward channel is reliable, but
the reverse is not.
• No data packets are lost, but some ACKs are delayed and one is lost.
• The example also shows how cumulative acknowledgments can help
if acknowledgments are delayed or lost.
• What happens when a packet is lost?
• Packets 0, 1, 2, and 3 are sent.
• However, packet 1 is lost.
• The receiver receives packets 2 and 3, but they are discarded because they are received
out of order (packet 1 is expected).
• When the receiver receives packets 2 and 3, it sends ACK1 to show that it expects to
receive packet 1.
• However, these ACKs are not useful for the sender because the ackNo is equal to Sf, not
greater than Sf.
• So the sender discards them.
• When the time-out occurs, the sender resends packets 1, 2, and 3, which are
acknowledged.
Go-Back-N Protocol
(GBN) – Ex 2
Selective-Repeat Protocol
• The Go-Back-N protocol simplifies the process at the receiver.
• The receiver keeps track of only one variable, and there is no need to buffer out-of-
order packets; they are simply discarded.
• However, this protocol is inefficient if the underlying network protocol loses a lot of
packets.
• Each time a single packet is lost or corrupted, the sender resends all outstanding
packets, even though some of these packets may have been received safe and
sound but out of order.
• If the network layer is losing many packets because of congestion in the network,
the resending of all of these outstanding packets makes the congestion worse, and
eventually more packets are lost.
• This has an avalanche effect that may result in the total collapse of the network.
• Selective-Repeat (SR) protocol, has been devised, which, as the name
implies, resends only selective packets, those that are actually lost
• Windows
• The Selective-Repeat protocol also uses two windows: a send window
and a receive window.
• However, there are differences between the windows in this protocol
and the ones in Go-Back-N.
• First, the maximum size of the send window is much smaller; it is 2m−1.
• Second, the receive window is the same size as the send window.
• Acknowledgments
• In the Selective-Repeat protocol, an acknowledgment number defines
the sequence number of the error-free packet received
Selective-Repeat
Protocol
Media Access Control (MAC)
• When nodes or stations are connected and use a common link, called
a multipoint or broadcast link, we need a multiple-access protocol to
coordinate access to the link
RANDOM ACCESS
• In random-access or contention methods, no station is superior to another station
and none is assigned control over another.
• At each instance, a station that has data to send uses a procedure defined by the
protocol to make a decision on whether or not to send.
• This decision depends on the state of the medium (idle or busy)
• Two features give this method its name.
• First, there is no scheduled time for a station to transmit.
• Transmission is random among the stations.
• That is why these methods are called random access.
• Second, no rules specify which station should send next.
• Stations compete with one another to access the medium.
ALOHA
• ALOHA, the earliest random access method, was developed at the
University of Hawaii in early 1970.
• It was designed for a radio (wireless) LAN, but it can be used on any
shared medium.
• It is obvious that there are potential collisions in this arrangement.
The medium is shared between the stations.
• When a station sends data, another station may attempt to do so at
the same time.
• The data from the two stations collide and become garbled.
Pure ALOHA
• The original ALOHA protocol is called pure ALOHA.
• This is a simple but elegant protocol.
• The idea is that each station sends a frame whenever it has a frame to
send (multiple access).
• However, since there is only one channel to share, there is the
possibility of collision between frames from different stations.
Pure ALOHA
• We need to mention that even if one bit of a frame coexists on the channel
with one bit from another frame, there is a collision and both will be
destroyed.
• It is obvious that we need to resend the frames that have been destroyed
during transmission.
• The pure ALOHA protocol relies on acknowledgments from the receiver.
• When a station sends a frame, it expects the receiver to send an
acknowledgment.
• If the acknowledgment does not arrive after a time-out period, the station
assumes that the frame (or the acknowledgment) has been destroyed and
resends the frame.
Pure ALOHA
• A collision involves two or more stations.
• If all these stations try to resend their frames after the time-out, the frames
will collide again.
• Pure ALOHA dictates that when the time-out period passes, each station waits
a random amount of time before resending its frame.
• The randomness will help avoid more collisions.
• We call this time the backoff time TB.
• Pure ALOHA has a second method to prevent congesting the channel with
retransmitted frames.
• After a maximum number of retransmission attempts Kmax, a station must
give up and try later.
Pure ALOHA
Pure ALOHA
• Vulnerable time
• Let us find the vulnerable time, the length of time in which there is a
possibility of collision.
• We assume that the stations send fixed-length frames with each
frame taking Tfr seconds to send.
Pure ALOHA vulnerable time = 2* Tfr

Pure ALOHA
• Throughput
• Let us call G the average number of frames generated by the system during one frame
transmission time.
• Then it can be proven that the average number of successfully transmitted frames for
pure ALOHA is S = G × e−2G
• The maximum throughput Smax is 0.184, for G = 1/2
• A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What
is the throughput if the system (all stations together) produces
a. 1000 frames per second?
b. 500 frames per second?
c. 250 frames per second?
Pure ALOHA
• The frame transmission time is 200/200 kbps or 1 ms.
• a. If the system creates 1000 frames per second, or 1 frame per
millisecond, then G = 1.
• In this case S = G × e−2G = 0.135 (13.5 percent).
• This means that the throughput is 1000 × 0.135 = 135 frames.
• Only 135 frames out of 1000 will probably survive.
Pure ALOHA
• b. If the system creates 500 frames per second, or 1/2 frames per
millisecond, then G = 1/2.
• This means that the throughput is 500 × 0.184 = 92 and that only 92
frames out of 500 will probably survive.
• C. If the system creates 250 frames per second, or 1/4 frames per
millisecond, then G = 1/4.
• This means that the throughput is 250 × 0.152 = 38.
• Only 38 frames out of 250 will probably survive.
Slotted ALOHA
• Pure ALOHA has a vulnerable time of 2 × Tfr.
• This is so because there is no rule that defines when the station can
send.
• A station may send soon after another station has started or just
before another station has finished.
• Slotted ALOHA was invented to improve the efficiency of pure ALOHA.
• In slotted ALOHA we divide the time into slots of Tfr seconds and force
the station to send only at the beginning of the time slot.
Slotted ALOHA
Slotted ALOHA
• Because a station is allowed to send only at the beginning of the
synchronized time slot, if a station misses this moment, it must wait
until the beginning of the next time slot.
• This means that the station which started at the beginning of this slot
has already finished sending its frame.
• Of course, there is still the possibility of collision if two stations try to
send at the beginning of the same time slot.
• However, the vulnerable time is now reduced to one-half, equal to Tfr.
Slotted ALOHA
Slotted ALOHA
• Throughput
• It can be proven that the average number of successful transmissions
for slotted ALOHA is S = G × e−G.
• The maximum throughput Smax is 0.368, when G = 1.
Slotted ALOHA
CSMA
• To minimize the chance of collision and, therefore, increase the performance, the
CSMA method was developed.
• The chance of collision can be reduced if a station senses the medium before
trying to use it.
• Carrier sense multiple access (CSMA) requires that each station first listen to the
medium (or check the state of the medium) before sending.
• In other words, CSMA is based on the principle “sense before transmit” or “listen
before talk.”
• CSMA can reduce the possibility of collision, but it cannot eliminate it.
• The possibility of collision still exists because of propagation delay; when a station
sends a frame, it still takes time (although very short) for the first bit to reach every
station and for every station to sense it.
CSMA
• At time t1, station B senses the
medium and finds it idle, so it sends
a frame.
• At time t2 (t2 > t1), station C senses
the medium and finds it idle
because, at this time, the first bits
from station B have not reached
station C.
• Station C also sends a frame.
• The two signals collide and both
frames are destroyed.
CSMA
• Vulnerable Time
• The vulnerable time for CSMA is the
propagation time Tp.
• This is the time needed for a signal to
propagate from one end of the medium to
the other.
• When a station sends a frame and any other
station tries to send a frame during this time,
a collision will result.
• But if the first bit of the frame reaches the
end of the medium, every station will already
have heard the bit and will refrain from
sending.
CSMA
• Persistence Methods
CSMA
• 1-Persistent
• The 1-persistent method is simple and straightforward. In this
method, after the station finds the line idle, it sends its frame
immediately (with probability 1).
• This method has the highest chance of collision because two or more
stations may find the line idle and send their frames immediately.
CSMA
• Nonpersistent
• In the nonpersistent method, a station that has a frame to send
senses the line.
• If the line is idle, it sends immediately.
• If the line is not idle, it waits a random amount of time and then
senses the line again.
• The nonpersistent approach reduces the chance of collision
because it is unlikely that two or more stations will wait the same
amount of time and retry to send simultaneously.
• However, this method reduces the efficiency of the network
because the medium remains idle when there may be stations
with frames to send.
CSMA
• p-persistent
• The p-persistent method is used if the channel has time slots with a slot duration equal to
or greater than the maximum propagation time.
• The p-persistent approach combines the advantages of the other two strategies.
• It reduces the chance of collision and improves efficiency.
• In this method, after the station finds the line idle it follows these steps:
1. With probability p, the station sends its frame.
2. With probability q = 1 − p, the station waits for the beginning of the next time slot
and checks the line again.
a. If the line is idle, it goes to step 1.
b. If the line is busy, it acts as though a collision has occurred and uses the
backoff procedure.
CSMA/CD
• The CSMA method does not specify the procedure following a
collision.
• Carrier sense multiple access with collision detection (CSMA/CD)
augments the algorithm to handle the collision.
• In this method, a station monitors the medium after it sends a frame
to see if the transmission was successful.
• If so, the station is finished.
• If, however, there is a collision, the frame is sent again.
CSMA/CD
CSMA/CD
• At time t1, station A has executed its persistence procedure and starts sending the bits of
its frame.
• At time t2, station C has not yet sensed the first bit sent by A.
• Station C executes its persistence procedure and starts sending the bits in its frame, which
propagate both to the left and to the right.
• The collision occurs sometime after time t2. Station C detects a collision at time t3 when it
receives the first bit of A’s frame.
• Station C immediately (or after a short time, but we assume immediately) aborts
transmission.
• Station A detects collision at time t4 when it receives the first bit of C’s frame; it also
immediately aborts transmission.
• Looking at the figure, we see that A transmits for the duration t4 − t1; C transmits for the
duration t3 − t2.
CSMA/CD
• Minimum Frame Size
• For CSMA/CD to work, we need a restriction on the frame size.
• Before sending the last bit of the frame, the sending station must detect a
collision, if any, and abort the transmission.
• This is so because the station, once the entire frame is sent, does not keep
a copy of the frame and does not monitor the line for collision detection.
• Therefore, the frame transmission time Tfr must be at least two times the
maximum propagation time Tp.
• Or frame transmission time should be at least equal to Round-Trip Time
(RTT)
CSMA/CD
• A network using CSMA/CD has a bandwidth of 10 Mbps. If the
maximum propagation time is 25.6 μs, what is the minimum size of
the frame?
• The minimum frame transmission time is Tfr = 2 × Tp = 51.2 μs.
• This means, in the worst case, a station needs to transmit for a period
of 51.2 μs to detect the collision.
• The minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64
bytes
CSMA/CD
• Throughput
• The throughput of CSMA/CD is greater than that of pure or slotted
ALOHA.
• The maximum throughput occurs at a different value of G and is
based on the persistence method and the value of p in the p-
persistent approach.
• For the 1-persistent method, the maximum throughput is around 50
percent when G = 1.
• For the nonpersistent method, the maximum throughput can go up to
90 percent when G is between 3 and 8.
Ethernet (IEEE 802.3 Standard)
• The Ethernet is the most successful local area networking technology of the last 20 years.
• Developed in the mid-1970s by researchers at the Xerox Palo Alto Research Center (PARC), the Ethernet is a
working example of CSMA/CD local area network technology.
• As indicated by the CSMA name, the Ethernet is a multiple-access network, meaning that a set of nodes send
and receive frames over a shared link.
• You can, therefore, think of an Ethernet as being like a bus that has multiple stations plugged into it.
• The "carrier sense" in CSMA/CD means that all the nodes can distinguish between an idle and a busy link, and
"collision detect" means that a node listens as it transmits and can therefore detect when a frame it is
transmitting has interfered (collided) with a frame transmitted by another node.
• IEEE 802.3 defines a much wider collection of physical media over which Ethernet can operate, and it has
been extended to include a 100-Mbps version called Fast Ethernet, and a 1,000-Mbps version called Gigabit
Ethernet.
• Physical Properties
• An Ethernet segment is implemented on a coaxial cable of up to 500 m.
• This cable is similar to the type used for cable TV, except that it typically has an
impedance of 50 ohms instead of cable TV's 75 ohms.
• Hosts connect to an Ethernet segment by tapping into it; taps must be at least
2.5 m apart.
• A transceiver—a small device directly attached to the tap detects when the
line is idle and drives the signal when the host is transmitting. It also receives
incoming signals.
• The transceiver is, in turn, connected to an Ethernet adaptor, which is plugged
into the host.
• Multiple Ethernet segments can be joined together by repeaters.
• Ethernet has a total reach of only 2,500 m and an Ethernet is
limited to supporting a maximum of 1,024 hosts
• Any signal placed on the Ethernet by a host is broadcast over the
entire network, that is, the signal is propagated in both directions,
and repeaters forward the signal on all outgoing segments.
• Terminators attached to the end of each segment absorb the
signal and keep it from bouncing back and interfering with
trailing signals.
• The Ethernet uses the Manchester encoding scheme
• In addition to the system of segments and repeaters just described, alternative technologies have been
introduced over the years.
• Today, a Category 5 twisted pair wiring is predominantly used and it is usually limited to under 100 m in
length.
• Because the cable is so thin, you do not tap into a 10BaseT (Twisted pair) cable and so the common
configuration is to have several point-to-point segments coming out of a multiway repeater, sometimes
called a hub
• Access Protocol
• Frame Format
• The 64-bit preamble allows the receiver to synchronize with the signal; It is a sequence of alternating 0s and 1s.
• Both the source and destination hosts are identified with a 48-bit address.
• The packet type field serves as the demultiplexing key, that is, it identifies to which of possibly many higher-level protocols
this frame should be delivered.
• Each frame contains up to 1,500 bytes of data.
• Minimally, a frame must contain at least 46 bytes of data, even if this means the host has to pad the Frame before
transmitting it.
• The reason for this minimum frame size is that the frame must be long enough to detect a collision;
• Finally, each frame includes a 32-bit CRC.
• From the host's perspective, an Ethernet frame has a 14-byte header: two 6-byte addresses and a 2-byte type field.
• Access Protocol
• Addresses
•Each host on an Ethernet—in fact, every Ethernet host in the world—has a unique Ethernet address.
•Technically, the address belongs to the adaptor, not the host; it is usually burned into ROM.
•Ethernet addresses are typically printed in a form humans can read as a sequence of six numbers separated by
colons.
•Each number corresponds to 1 byte of the 6-byte address and is given by a pair of hexadecimal digits, one
for each of the 4-bit nibbles in the byte; leading 0s are dropped.
•For example, 8:0:2b:e4:b1:2 is the human-readable representation of Ethernet address
• 00001000 00000000 00101011 11100100 10110001 00000010
• Access Protocol
• Addresses
• To ensure that every adaptor gets a unique address, each manufacturer of Ethernet devices is allocated a different prefix
that must be prepended to the address on every adaptor they build.
• For example, Advanced Micro Devices has been assigned the 24-bit prefix x080020 (or 8:0:20).
• A given manufacturer then makes sure the address suffixes it produces are unique.
• Each frame transmitted on an Ethernet is received by every adaptor connected to that Ethernet.
• Each adaptor recognizes those frames addressed to its address and passes only those frames on to the host.
• In addition to these unicast addresses, an Ethernet address consisting of all 1s is treated as a broadcast address; all
adaptors pass frames addressed to the broadcast address up to the host.
• Similarly, an address that has the first bit set to 1 but is not the broadcast address is called a multicast address.
• A given host can program its adaptor to accept some set of multicast addresses.
• Multicast addresses are used to send messages to some subset of the hosts on an Ethernet (e.g., all file servers).
• Transmitter Algorithm
•When the adaptor has a frame to send and the line is idle, it transmits the frame immediately; there is no
negotiation with the other adaptors.
•The upper bound of 1,500 bytes in the message means that the adaptor can occupy the line for only a fixed
length of time.
• When an adaptor has a frame to send and the line is busy, it waits for the line to go idle and then transmits
immediately
• The Ethernet is said to be a 1-persistent protocol because an adaptor with a frame to send transmits with
probability 1 whenever a busy line goes idle.
• Because there is no centralized control it is possible for two (or more) adaptors to begin transmitting at the
same time, either because both found the line to be idle or because both had been waiting for a busy line to
become idle.
• When this happens, the two (or more) frames are said to collide on the network.
• Transmitter Algorithm
• Each sender, because the Ethernet supports collision detection, is able to determine that a collision is in
progress.
• At the moment an adaptor detects that its frame is colliding with another, it first makes sure to transmit a
32-bit jamming sequence and then stops the transmission.
• Thus, a transmitter will minimally send 96 bits in the case of a collision: 64-bit preamble plus 32-bit
jamming sequence.
• Once an adaptor has detected a collision and stopped its transmission, it waits a certain amount of time
and tries again.
• Each time it tries to transmit but fails, the adaptor doubles the amount of time it waits before trying again.
• This strategy of doubling the delay interval between each retransmission attempt is a general technique
known as exponential backoff
• Adaptors typically retry up to 16 times, although the backoff algorithm caps n in the above formula at 10.
Wi-Fi (IEEE 802.11)
• Like its Ethernet and token ring siblings, 802.11 is designed for use in a limited geographical area (homes,
office buildings, campuses), and its primary challenge is to mediate access to a shared communication medium
—in this case, signals propagating through space.
• The original 802.11 standard defined two radio-based physical layers standards, and b oth provide up to 2
Mbps.
• Then physical layer standard 802.11b was added. Using a variant of direct sequence, 802.1 lb provides up to
11 Mbps.
• These three standards run in the license-exempt 2.4 GHz frequency band of the electromagnetic spectrum.
• Then came 802.11 a, which delivers up to 54 Mbps using a variant of FDM called orthogonal frequency division
multiplexing (OFDM).
• 802.11a runs in the license-exempt 5-GHz band.
• On one hand, this band is less used, so there is less interference. On the other hand, there is more absorption of
the signal and it is limited to almost line of sight.
• The most recent standard is 802.11g, which is backward compatible with 802.1 lb (and returns to the 2.4-
GHz band). 802.11g uses OFDM and delivers up to 54 Mbps.
Wi-Fi (IEEE 802.11)
• Collision Avoidance
• The additional complication for wireless is that, while a node on an Ethernet receives every other node's
transmissions, a node on an 802.11 network may be too far from certain other nodes to receive their
transmissions (and vice versa).
Wi-Fi (IEEE 802.11)
• Collision Avoidance
• 802.11 addresses these two problems with an algorithm called multiple access with collision avoidance
(MACA).
• The idea is for the sender and receiver to exchange control frames with each other before the sender actually
transmits any data. This exchange informs all nearby nodes that a transmission is about to begin.
• Specifically, the sender transmits a Request to Send (RTS) frame to the receiver; the RTS frame
includes a field that indicates how long the sender wants to hold the medium (i.e., it specifies the length of
the data frame to be transmitted).
• The receiver then replies with a Clear to Send (CTS) frame; this frame echoes this length field back to the
sender.
• Any node that sees the CTS frame knows that it is close to the receiver, and therefore cannot transmit for
the period of time it takes to send a frame of the specified length.
• Any node that sees the RTS frame but not the CTS frame is not close enough to the receiver to interfere
with it, and so is free to transmit.
Wi-Fi (IEEE 802.11)
Bluetooth (IEEE 802.15.1 Standard)
•Bluetooth fills the niche of very short-range communication between mobile phones, PDAs, notebook
computers, and other personal or peripheral devices.
•For example, Blue-tooth can be used to connect a mobile phone to a headset, or a notebook computer to a
printer.
•Roughly speaking, Bluetooth is a more convenient alternative to connecting two devices with a wire.
•In such applications, it is not necessary to provide much range or bandwidth.
•This is fortunate for some of the target battery-powered devices, since it is important that they not consume
much power.
•Bluetooth operates in the license-exempt band at 2.45 GHz.
•It has a range of only about 10 m.
•For this reason, and because the communicating devices typically belong to one individual or group,
•Bluetooth is sometimes categorized as a personal area network (PAN).
•Version 2.0 provides speeds up to 2.1 Mbps.
•Power consumption is low.

Data Link Layer

Uploaded by

Copyright:

Available Formats

Data Link Layer

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Link Layer

Uploaded by

Copyright:

Available Formats

Data Link Layer

• The minimum Hamming distance is 2.

1. Write the bit positions starting from 1 in binary form

Pure ALOHA vulnerable time = 2* Tfr

• Finally, each frame includes a 32-bit CRC.

You might also like