MODULE 2

Datalink Layer
 Nodes and links
• Any device capable of sending or receiving the data unit is called a
node.
• Nodes are connected by links.
• Communication at data link layer is node to node.
 Services of Datalink layer.

• When a packet is travelling in the internet, the data link layer of a

node(host or router) is responsible for delivering the datagram to the
next node.
• For this purpose, datalink layer of sending node encapsulates the
datagram received from network layer in a frame.
• The datalink layer at the receiver needs to decapsulate datagram from
the frame.
A communication with three nodes.
• Framing. The data link layer divides the stream of bits received from
the network layer into manageable data units called frames
• Flow control:
• If the rate at which the data are absorbed by the receiver is less than
the rate at which data are produced in the sender, the data link layer
imposes a flow control mechanism to avoid overwhelming the
receiver.
• The receiver has to buffer while waiting for processing.
• Error control.
• The data link layer adds reliability to the physical layer by adding
mechanisms to detect and retransmit damaged or lost frames.
• It also uses a mechanism to recognize duplicate frames. Error control
is normally achieved through a trailer added to the end of the frame
• Congestion Control.:
• A link may be congested with frames and results in loss of frames.
• Most of the data link layer protocols do not directly use congestion
control to alleviate congestion. Congestion is considered at network
or transport layer.
 Two Categories of Links

• Although two nodes are physically connected by a transmission medium

such as cable or air, we need to remember that the data-link layer controls
how the medium is used.
• A data-link layer that uses the whole capacity of the medium OR we can
also have a data-link layer that uses only part of the capacity of the link.
• In other words, we can have a point-to-point link or a broadcast link.
• In point to point link, the link is dedicated to two devices.
• Eg:Telephone.
• In broadcast,link is shared among the users.
• Eg:mobile communication.
 Sublayers

• To better understand the functionality of and the services provided by

the link layer, the data-link layer is divided into two sublayers:
1)Data link control (DLC)
2) Media access control (MAC).
DLC deals with issues common to both point to point and broadcast
links.
MAC deals with issues specific to broadcast links.
Dividing the data-link layer into two sublayers
 Link layer Addressing
• Source and destination hosts are identified by IP address defined by
network layer.
• A datagram with IP address van not traverse through intermediate
nodes in a network.
• Thus we need another addressing scheme in connectionless
internetwork.
• Hence, Datalink layer uses link address of two nodes. This link address
is also called physical address.
• When a datagram passes from the network layer to the data-link
layer, the datagram will be encapsulated in a frame and two data-link
addresses are added to the frame header. These two addresses are
changed every time the frame moves from one link to another.
IP addresses and link-layer addresses in a small internet
• Here we have three links and two routers.
• We have two hosts: Alice (source) and Bob (destination).
• For each host, we have shown two addresses, the IP addresses (N)
and the link-layer addresses (L).
• We have three frames, one in each link.
• Each frame carries the same datagram with the same source and
destination addresses (N1 and N8), but the link-layer addresses of the
frame change from link to link.
• In link 1, the link-layer addresses are L1 and L2. In link 2, they are L4
and L5. In link 3, they are L7 and L8
. For IP addresses, the source address comes before the destination
address; for link-layer addresses, the destination address comes before
the source.
 Types of Address
• Three types of addresses of link layer.
• 1 Unicast Address:
Each host or each interface of a router is assigned a unicast address.
Unicasting means one to-one communication.
Example :
The unicast link-layer addresses in the most common LAN, Ethernet,
are 48 bits (six bytes) that are presented as 12 hexadecimal digits
separated by colons;
A3:34:45:11:92:F1
• 2) Multicast Address:
Some link-layer protocols define multicast addresses. Multicasting
means one-to many communication.
Example
The multicast link-layer addresses in the most common LAN,Ethernet,
are 48 bits (six bytes) that are presented as 12 hexadecimal digits
separated by colons.
The second digit, needs to be an even number in hexadecimal. The
following shows a multicast address:
A2:34:45:11:92:F1
• 3.Broadcast Address:
• Some link-layer protocols define a broadcast address
• . Broadcasting means one-to-all communication.
• A frame with a destination broadcast address is sent to all entities in
the link. Example The broadcast link-layer addresses in the most
common LAN,Ethernet, are 48 bits, all 1s, that are presented as 12
hexadecimal digits separated by colons.
• The following shows a broadcast address: FF:FF:FF:FF:FF:FF .
 Address Resolution
Protocol (ARP)
• The ARP protocol is one of the protocols defined in the network layer
as shown below.
• It belongs to the network layer. It maps an IP address to a logical-link
address.
• The main work of ARP :
• It accepts an IP address from the IP protocol, maps the address to
the corresponding link layer(physical address) address, and passes it
to the data-link layer.

• If a host or a router needs to find the link-layer address of another

host or router in its network, it sends an ARP request packet.
• This packet includes the link-layer and IP addresses of the sender and
the IP address of the receiver.
• Because the sender does not know the link-layer address of the
receiver, the query is broadcast over the link using the link-layer
broadcast address.
•
•
• Every host or router on the network receives and processes the ARP
request packet, but only the intended recipient recognizes its IP
address and sends back an ARP response packet.
• The response packet contains the recipient’s IP and link-layer
addresses.
• The packet is unicast directly to the node that sent the request
packet.

The system on the left (A) has a packet that needs to be delivered to
another system (B) with IP address N2.
System A needs to pass the packet to its data-link layer for the actual
delivery, but it does not know the physical address of the recipient.
It uses the services of ARP by asking the ARP protocol to send a
broadcast ARP request packet to ask for the physical address of a
system with an IP address of N2.
• This packet is received by every system on the physical network, but
only system B will answer it, as shown in Figure b
• System B sends an ARP reply packet that includes its physical address.
Now system A can send all the packets it has for this destination using
the physical address it received.
ARP- Packet Format
• The hardware type field defines the type of the link-layer protocol;
Ethernet is given the type 1.
• The protocol type field defines the network-layer protocol: IPv4
protocol is (0800)16.
• The source hardware and source protocol addresses are variable-
length fields defining the link-layer and network-layer addresses of
the sender.
• The destination hardware address and destination protocol address
fields define the receiver link-layer and network-layer addresses.
• An ARP packet is encapsulated directly into a data-link frame. The
frame needs to have a field to show that the payload belongs to the
ARP and not to the network-layer datagram.
Ex:
• A host with IP address N1 and MAC address L1 has a packet to send
to another host with IP address N2 and physical address L2 (which is
unknown to the first host). The two hosts are on the same network.
shows the ARP request and response messages.
 Data Link
Control(DLC)
• Data link layer is divided into two sublayers.
• The upper sublayer is Data Link Layer.
• The lower sublayer is Multiple Access Control.
• DLC SERVICES
• The data link control (DLC) deals with procedures for communication
between two adjacent nodes.ie: node-to-node communication.
• No matter whether the link is dedicated or broadcast.
• The functions of Data link control are as follows:
• Framing, flow and error control.
1. Framing :
Data transmission in the physical layer means moving bits in the form
of a signal from the source to the destination.
The physical layer provides bit synchronization to ensure that the
sender and receiver use the same bit durations and timing.
The data link layer needs to pack the bits into frame.
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.
 Frames can be of two types: 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.
An example of this type of framing is the ATM WAN, which uses frames
of fixed size called cells.

In variable-size framing, we need a way to define the end of one frame

and the beginning of the next.
Two approaches are used for this.
1) character-oriented framing
2) Bit oriented framing
Character-Oriented Framing
• In character-oriented (or byte-oriented) framing as shown in figure ,
data to be carried are 8- bit characters from a coding system such as
ASCII.
• Here 8 bit data is used. The header, normally carries the source and
destination addresses and other control information, and the trailer,
which carries error detection redundant bits, and multiples of 8 bits.
• To separate one frame from the next, an 8-bit (1-byte) flag is added at
the beginning and the end of a frame.
• The flag, composed of protocol-dependent special characters, signals
the start or end of a frame.
A frame in a character-oriented protocol
• We can also 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 overcome this problem, a byte-stuffing strategy was added to
character oriented.
 Byte stuffing .
• In byte stuffing (or character stuffing), a special byte is added to the
data section of the frame when there is a character with the same
pattern as the flag. The data section is stuffed with an extra byte as in
figure below.
• This byte is called the escape character (ESC) and has a predefined bit
pattern.
• Whenever the receiver encounters the ESC character, it removes it
from the data section and treats the next character as data, not as a
delimiting flag. .
Byte stuffing and unstuffing
 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.In addition to headers ,we 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, as shown
in below.
 A frame in a bit-oriented protocol

•
• If the flag pattern appears in the data, we need to inform the receiver
that this is not the end of the frame.
• By stuffing 1 single bit(instead of 1 byte) we can prevent the pattern
from looking like a flag. This strategy is called bit stuffing.
• In bit stuffing, if a 0 and five consecutive 1 bits are encountered, an
extra 0 is added as shown in figure below.
• This extra stuffed bit is eventually removed from the data by the
receiver.Bit stuffing is the process of adding one extra 0 whenever five
consecutive 1s follow a 0in the data, so that the receiver does not
mistake the pattern 0111110
Bit stuffing and unstuffing
 Flow and Error Control
• 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.
• Flow control is implemented to prevent traffic
Flow control at the data-link layer
• The data-link layer at the sending node tries to push frames towards
the data-link layer at the receiving node.
• If the receiving node cannot process and deliver the packet to its
network at the same rate that the frames arrive, it becomes over
whelmed (traffic) with frames.
• Flow control in this case can be feedback from the receiving node to
the sending node to stop or slow down pushing frames.
• Buffers: Although flow control can be implemented in several ways,
one of the solutions is normally to use two buffers; one at the sending
data-link layer and the other at the receiving data-link layer.
• A buffer is a set of memory locations that can hold packets at the
sender and receiver.
• Error Control :
• Error control at the data-link layer is very simple and implemented
using one of the following two methods.
• In both methods, a CRC is added to the frame header by the sender
and checked by the receiver.
• In the first method, if the frame is corrupted, it is silently discarded; if
it is not corrupted, the packet is delivered to the network layer. This
method is used mostly in wired LANs such as Ethernet.
• In the second method, if the frame is corrupted, it is silently
discarded; if it is not corrupted, an acknowledgment is sent (for the
purpose of both flow and error control)to the sender.
 DATA-LINK LAYER
PROTOCOLS
• Simple Protocol
• This is a simple protocol with neither flow nor error control.
• Assume that the receiver can immediately handle any frame it
receives. In other words, the receiver can be free of congestion with
incoming frames.
• The data link layer at the sender side mainly gets the data from the
network layer and then makes the frame out of data and sends it.
• On the Receiver site, the data link layer receives the frame from the
physical layer and then extracts the data from the frame, and then
delivers the data to its network layer.
Simplest Protocol.
FSMs ( Description of Simple
protocol)
• The sender should not send a frame until its network layer has a
message to send.
• The receiver site cannot deliver a message to its network layer until a
frame arrives. Requirements are based on two FSMs.
• Each FSM has only one state, the ready state as shown in figure
below.
FSM for simple protocol.
• The sending machine remains in the ready state until a request comes
from the process in the network layer.
• When this event occurs, the sending machine encapsulates the
message in a frame and sends it to the receiving machine.
• The receiving machine remains in the ready state until a frame arrives
from the sending machine.
• When this event occurs, the receiving machine decapsulates the
message out of the frame and delivers it to the process at the
network layer.
Flow Diagram for Simplest Protocol
• In order to send the three frames, there will be an occurrence of
three events at sender A and three events at the receiver B.
• It is important to note that in the above figure the data frames are
shown with the help of boxes.
• The height of the box mainly indicates the transmission time
difference between the first bit and the last bit of the frame.
 Stop-and-Wait Protocol
• 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 shown in figure below.
• 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.
 FSM for the stop and wait
protocol
Flow Diagram: stop and wait protocol
 Piggybacking
• Piggybacking is a process of attaching acknowledgment with the data
packet to be sent.
• It is used to improve the efficiency of bidirectional protocols.
• Suppose there is two-way communication between two devices A and
B.
• When the data frame is sent by A to B, then device B will not send
the acknowledgment to A until B does not have the next frame to
transmit. And the delayed acknowledgment is sent by the B with the
data frame.
Piggybacking.
Media Access Control
Taxonomy of multiple-access protocols
 RANDOM ACCESS PROTOCOLS
• In random access or contention methods, no station is superior to
another station and none is assigned the control over another.
• No station permits, or does not permit, another station to send
•. Two features give this method its name.
• 1. 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.
• 2. No rules specify which station should send next. Stations compete
with one another to access the medium. That is why these methods
are also called contention methods.
ALOHA Protocol
Frames in pure ALOHA
WORKING OF PURE ALOHA
PROCEDURE FOR PURE ALOHA
 VULNERABLE TIME(Pure
ALOHA)
• Station A sends a frame at time t. Now imagine station B has already
sent a frame between t - Tfr and t. This leads to a collision between
the frames from station A and station B.
• The end of B's frame collides with the beginning of A's frame.
• On the other hand, suppose that station C sends a frame between t
and t + Tfr . Here, there is a collision between frames from station A
and station C. The beginning of C's frame collides with the end of A's
frame.
• we see that the vulnerable time, during which a collision
may occur in pure ALOHA, is 2 times the frame transmission time.
Pure ALOHA vulnerable time = 2 x Tfr
• Throughput
• Let G be average number of frames generated by a system during
one frame transmission time(Tfr)

•. The throughput for pure ALOHA is

S = G × e −2G .
The maximum throughput
Smax = 0.184 when G= (1/2).
Example 1:
• 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.
• Solution
• The frame transmission time is 200/200 kbps or 1 ms.
• a. If the system creates 1000 frames per second, this is 1
frame per millisecond. The load is 1.i.e G=1. In this case
S = G× e−2 G or S = 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.
• b. If the system creates 500 frames per second,[500*10^-3]=1/2. this
is
(1/2) frame per millisecond. The load is (1/2). In this
case S = G × e −2G or S = 0.184 (18.4 percent). This
means that the throughput is 500 × 0.184 = 92 and that
only 92 frames out of 500 will probably survive. Note
that this is the maximum throughput case,
percentagewise.

• c. If the system creates 250 frames per second, this is

• (1/4) frame per millisecond. The load is (1/4). In this case
S = G × e −2G or S = 0.152 (15.2 percent). This means
that the throughput is 250 × 0.152 = 38. Only 38
frames out of 250 will probably survive.
 SLOTTED ALOHA
• Slotted ALOHA was invented to improve the efficiency of pure ALOHA.
• In slotted ALOHA we divide the time into slots of Tfr s and force the
station to send only at the beginning of the time slot.
• Slotted ALOHA vulnerable time = Tfr

The throughput for slotted ALOHA is

S = G × e−G .
The maximum throughput
Smax = 0.368 when G = 1.
• In other words, if a frame is generated during one frame transmission
time, then 36.8 percent of these frames reach their destination
successfully.
• This result can be expected because the vulnerable time is equal to
the frame transmission time.
• Therefore, if a station generates only one frame in this vulnerable
time (and no other station generates a frame during this time), the
frame will reach its destination successfully.
Example2
• A slotted 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.
• Solution
• Framesize=L=200bits
Rate=R=200kbps
Transmission time,T = L/R = 1 * 10 -3 s
• G=NumberofframesperT

• a. If the system creates 1000 frames per second,G=1000*10^-3=1 this

The load is 1.
• In this case
S = G× e−G or S = 0.368 (36.8 percent). This means
that the throughput is 1000 × 0.368 = 368 frames.
Only 368 frames out of 1000 will probably survive.
• b. If the system creates 500 frames per second, this is
(1/2) frame per millisecond. The load is (1/2). In this
case S = G × e−G or S = 0.303 (30.3 percent). This
means that the throughput is 500 × 0.303 = 151.
Only 151 frames out of 500 will probably survive.

• c. If the system creates 250 frames per second, this is (1/4)

frame per millisecond. The load is (1/4). In this case
S = G × e −G or S = 0.195 (19.5 percent). This means
that the throughput is 250 × 0.195 = 49. Only 49
frames out of 250 will probably survive.
Carrier Sense Multiple Access
(CSMA)
ex3
• We have a pure ALOHA network with 100 stations. If Tfr = 1μs
• what is the number of frames/s each station can send to achieve the
maximum efficiency.
• Solution :
• Let n to be the number of stations and nfs to be the number of
frames a station can send per sec
G = n × nfs × Tfr = 100 × nfs × 1μs

pureALOGA has max efficiency when G=1/2.

½= 100 × nfs × 1μs; nfs=5000frames/sec
Ex3
• One hundred stations on a pure ALOHA network share a l-Mbps channel. If
frames are 1000 bits long, find the throughput if each station is sending 10
frames per second.

• Tfr = (1000 bits) / 1 Mbps = 1 ms

• Let n to be the number of stations and nfs to be the number of
frames a station can send per sec
G = n × nfs × Tfr = 100 × nfs × Tfr
G = n × nfs × Tfr = 100 × 10 × 1 ms = 1
For pure ALOHA → S = G × e ^−2G ≈13.5%
This means that each station can successfully send only 1.35 frames per second.
Vulnerable time in CSMA
 Persistence methods
• If the station finds the channel busy or idle, it can follow any one of
the persistence methods.
• 1) .1-Persistent Method:
• 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.
1 persistent method.
• 2) Nonpersistent method:
• 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
• p-Persistent Method :
• Thep-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
Carrier Sense Multiple Access with Collision
Detection (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
• Although each station continues to send bits in the frame until it
detects the collision, we show what happens as the first bits collide.
Collision of the first bit in CSMA/CD
• At time t 1, 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 aborts transmission.
• Similarly, Station A detects collision at time t4 when it receives the
first bit of C's frame; it also immediately aborts transmission.
• A transmits for the duration t4 – t1;
• C transmits for the duration t3 - t2 ;
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.
• To understand this, assume ,the two stations involved in a collision are the
maximum distance apart, the signal from the first takes time Tp to reach
the second, and the effect of the collision takes another time Tp to reach
the first
• So the requirement is that the first station must still be transmitting after
2Tp .
Energy Level

• The level of energy in a channel can have three values: zero, normal,
and abnormal.
• At the zero level, the channel is idle. At the normal level, a station has
successfully captured the channel and is sending its frame
• At the abnormal level, there is a collision and the level of the energy
is twice the normal level

Energy level during transmission, idleness, or collision

Throughput:
• The throughput of CSMA/CD is greater than that of pure or slotted
ALOHA
• For 1-persistent method the maximum throughput is around 50
percent when G =1.
• For nonpersistent method, the maximum throughput can go up to 90
percent when G is between 3 and 8
Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)

• The basic idea behind CSMA/CD is that a station needs to be able to

receive while transmitting to detect a collision.
• When there is no collision, the station receives one signal: its own
signal.
• When there is a collision, the station receives two signals: its own
signal and the signal transmitted by a second station.
The signal from the second station needs to add a significant amount
of energy to the one created by the first station.
In a wired network, the received signal has almost double energy
when the collision occurs.
• However, in a wireless network, much of the sent energy is lost in
transmission.
• The received signal has very little energy. Therefore, a collision may
add only 5 to 10 percent additional energy.
• This is not useful for effective collision detection.
• We need to avoid collisions on wireless networks because they cannot
be detected.
• Hence, Carrier sense multiple access with collision avoidance
(CSMA/CA) was invented for wireless network.
• CSMA/CA has three strategies: the interframe space, the contention
window, and acknowledgments

Timing in CSMA/CA
• Interframe Space (IFS)
• First, collisions are avoided by deferring transmission even if the channel
is found idle.
• When an idle channel is found, the station does not send immediately. It
waits for a period of time called the interframe space or IFS.
• Even though the channel may appear idle when it is sensed, a distant
station may have already started transmitting.
• This is because the distant station's signal has not yet reached this
station.
• The IFS time allows the front of the transmitted signal by the distant
station to reach this station.
• If after the IFS time the channel is still idle, the station can send, but it
still needs to wait a time equal to the contention time .
• Contention Window
• The contention window is an amount of time divided into slots.
• A station that is ready to send chooses a random number of slots as
its wait time.
• The number of slots in the window changes according to the binary
exponential back-off strategy.
• This means that it is set to one slot the first time and then doubles
each time the station cannot detect an idle channel after the IFS time.
• This is very similar to the p-persistent method
• Acknowledgment
• With all these precautions, there still may be a collision resulting in
destroyed data.
• The positive acknowledgment and the time-out timer can help
guarantee that the receiver has received the frame.
 CONTROLLED
ACCESS
• Reservation :
• In controlled access, the stations consult one another to find which station has the
right to send.
• A station cannot send unless it has been authorized by other stations.
• Time is divided into intervals. In each interval, a reservation frame precedes the
data frames sent in that interval
• If there are N stations in the system, there are exactly N reservation minislots in the
reservation frame.
• Each minislot belongs to a station.
• When a station needs to send a data frame, it makes a reservation in its own
minislot
• The stations that have made reservations can send their data frames after the
reservation frame.
Reservation access method
• a situation with five stations and a five-minislot reservation frame.
• In the first interval, only stations 1, 3, and 4 have made reservations.
In the second interval, only station 1 has made a reservation.
• Polling
• Polling works with topologies in which one device is designated as a
primary station and the other devices are secondary stations.
• The primary device controls the link; the secondary devices follow its
instructions.
• It is up to the primary device to determine which device is allowed to
use the channel at a given time.
• If the primary wants to receive data, it asks the secondaries if they
have anything to send; this is called poll function.
• If the primary wants to send data, it tells the secondary to get ready
to receive; this is called select function.
Poll function
• Select function
• The select function is used whenever the primary device has
something to send.
• So the primary must alert the secondary to the upcoming
transmission and wait for an acknowledgment of the secondary's
ready status.
• Token Passing
• In the token-passing method, the stations in a network are organized in a logical
ring.
• In other words, for each station, there is a predecessor and a successor.
• The predecessor is the station which is logically before the station in the ring;
the successor is the station which is after the station in the ring.
• The current station is the one that is accessing the channel now.
• The right to this access has been passed from the predecessor to the current
station.
• The right will be passed to the successor when the current station has no
• more data to send.
• In this method, a special packet called a token circulates through the ring. The
possession of the token gives the station the right to access the channel and
send its data.
 CHANNELIZATION PROTOCOLS
• Channelization is a multiple-access method in which the available
bandwidth of a link is shared in time, frequency, or through code,
between different stations.
• There are three channelization protocols: FDMA, TDMA, and CDMA.

• Frequency-Division Multiple Access (FDMA)

• In frequency-division multiple access (FDMA), the available
bandwidth is divided into frequency bands.
• Each station is allocated a band to send its data.
• In other words, each band is reserved for a specific station, and it
belongs to the station all the time.
• Each station also uses a bandpass filter to confine the transmitter
frequencies.
• To prevent station interferences, the allocated bands are separated
from one another by small guard bands
• FDMA, is an access method in the data link layer.
• The data link layer in each station tells its physical layer to make a
bandpass signal from the data passed to it. The signal must be created
in the allocated band.
• The signals created at each station are automatically bandpass-
filtered. They are mixed when they are sent to the common channel.
Frequency-division multiple access
(FDMA)
Time-Division Multiple Access
(TDMA)
• In time-division multiple access (TDMA), the stations share the
bandwidth of the channel in time.
• Each station is allocated a time slot during which it can send data.
• Each station transmits its data in is assigned time slot.
• The main problem with TDMA lies in achieving synchronization
between the different stations
• Each station needs to know the beginning of its slot and the location
of its slot.
Time-division multiple access (TDMA)
• This may be difficult because of propagation delays introduced in the
system if the stations are spread over a large area.
• To compensate for the delays, we can insert guard times.
• Synchronization is normally accomplished by having some
synchronization bits (known as preamble bits) at the beginning of
each slot.
• The data link layer in each station tells its physical layer to use the
allocated time slot.
• There is no physical multiplexer at the physical layer.
Code-Division Multiple Access
(CDMA)
• In CDMA, one channel carries all transmissions simultaneously.
• CDMA differs from FDMA because only one channel occupies the entire bandwidth
of the link.
• It differs from TDMA because all stations can send data simultaneously; there is no
timesharing.
• Analogy
• CDMA simply means communication with different codes.
• For example, in a large room with many people, two people can talk in English if
• nobody else understands English.
• Another two people can talk in Chinese if they are the only ones who understand
Chinese, and so on.
• In other words, the common channel, the space of the room in this case, can easily
allow communication between several couples, but in different languages (codes).
• Idea
• Let us assume we have four stations 1, 2, 3, and 4 connected to the
same channel.
• The data from station 1 are d 1, from station 2 are d2, and so on.
• The code assigned to the first station is c1, to the second is c2, and so
on.
• We assume that the assigned codes have two properties.
• 1. If we multiply each code by another, we get 0.
• 2. If we multiply each code by itself, we get 4 (the number of
stations).
• Station 1 multiplies (a special kind of multiplication) its data by its
code to get d 1 . C1.
Station 2 multiplies its data by its code to get d2 . C2, And so on.
The data that go on the channel are the sum of all these terms, as
shown in the box.
• Any station that wants to receive data from one of the other three
multiplies the data on the channel by the code of the sender.
• For example, suppose stations 1 and 2 are talking to each other.
Station 2 wants to hear what station 1 is saying. It multiplies the data
on the channel by c1 the code of station 1.
• Because (c1 . c1) is 4, but (c2 . c1), (c3 . c1), and (c4 . c1) are all 0s,
station 2 divides the result by 4 to get the data from station 1.
• data =(d1 . C1 + d2 . C2 +d3 . C3 + d4 . c4) . C1
• =d 1 • C1. C1 + d2. C2 . C1 + d3 . C3 . C1 + d4 . C4 C1 =4 X d1
• Simple idea of communication with code
• Chips
• CDMA is based on coding theory. Each station is assigned a code,
which is a sequence of numbers called chips.

Chip sequences
• They are called orthogonal sequences and have the following
properties:
• 1. Each sequence is made of N elements, where N is the number of
stations.
• 2. If we multiply a sequence by a number, every element in the
sequence is multiplied by that element. This is called multiplication of
a sequence by a scalar.
• For example,
• 2. [+1 +1-1-1]=[+2+2-2-2]
• 3. If we multiply two equal sequences, element by element, and add the
results, we get N, where N is the number of elements in the each
sequence.
• This is called the inner product of two equal sequences.
• For example,
• [+1 +1-1 -1]· [+1 +1 -1 -1] = 1 + 1 + 1 + 1 = 4
• 4. If we multiply two different sequences, element by element, and add
the results, we get 0. This is called inner product of two different
sequences. For example,
• [+1 +1 -1 -1] • [+1 +1 +1 +1] = 1 + 1 - 1 - 1 = 0
• 5. Adding two sequences means adding the corresponding elements. The
result is another sequence. For example,
• [+1+1-1-1]+[+1+1+1+1]=[+2+2+ 0+0]
Sharing channel in CDMA
• Data Representation
• We follow these rules for encoding:
• If a station needs to send a 0 bit, it encodes it as -1;
• if it needs to send a 1 bit, it encodes it as +1.
• When a station is idle, it sends no signal, which is interpreted as a O.

•
• Encoding and Decoding
• We assume that stations 1 and 2 are sending a 0 bit and channel 4 is
sending a 1 bit. Station 3 is silent.
• The data at the sender site are translated to -1, -1, 0, and +1.
• Each station multiplies the corresponding number by its chip (its
orthogonal sequence), which is unique for each station.
• The result is a new sequence which is sent to the channel.
• The sequence on the channel is the sum of all four sequences as
defined before
• Now imagine station 3, which we said is silent, is listening to station 2.
Station 3 multiplies the total data on the channel by the code for
station 2, which is [+1 -1 +1-1], to get
• [-1-1-3 +1]· [+1-1 +1-1] =-4/4 =-1 ...... bit 1
• Sequence Generation
• To generate chip sequences, we use a Walsh table, which is a two-
dimensional table with an equal number of rows and columns,
• General rule and examples of creating Walsh tables
Example 1

• Find the chips for a network with

• a. Two stations b. Four stations
Solution
We can use the rows of W2 and W4 in
a. For a two-station network, we have
[+1 +1] and [+1 −1].

b. For a four-station network we have

[+1 +1 +1 +1], [+1 −1 +1 −1],
[+1 +1 −1 −1], and [+1 −1 −1 +1].
• What is the number of sequences if we have 90 stations in our
network?
• Solution
• The number of sequences needs to be 2m. We need to choose m = 7
and N = 27 or 128. We can
• then use 90 of the sequences as the chips.
ex2
• A network with one primary and four secondary stations uses polling.
The size of a data frame is 1000 bytes. The size of the poll, ACK, NACK
frames are 32 bytes. Each station has 5 frames to send how many
total bytes are exchanged if each station can send only one frame in
response to a poll.
• Polling and data transfer:
• Frame 1 for all four stations: 4 * [ poll + frame + ACK]
• Frame 2 for all four stations: 4 * [ poll + frame + ACK]
• Frame 3 for all four stations: 4 * [ poll + frame + ACK]
• Frame 4 for all four stations: 4 * [ poll + frame + ACK]
• Frame 5 for all four stations: 4 * [ poll + frame + ACK]
•
• Polling and sending NAKs
•
• Station 1: [poll+ NAK]
• Station 2: [poll+ NAK]
• Station 3: [poll+ NAK]
• Station 4: [poll+ NAK]
•
• Total activity:
• 24 polls + 20 frames + 20 ACK s+ 4 NAKs = 21536 bytes.
•
ex4
• Get the sequences (chips) for 6 stations.
• (6 is not power of 2 but 23=8 so we calculate W8 but consider only
the first 6 rows as our stations)

•
 W8 = +1 +1 +1 +1 +1 +1 +1 +1 S1
+1 -1 +1 -1 +1 -1 +1 -1 S2
+1 +1 -1 -1 +1 +1 -1 -1 S3
+1 -1 -1 +1 +1 -1 -1 +1 S4
+1 +1 +1 +1 -1 -1 -1 -1 S5
+1 -1 +1 -1 -1 +1 -1 +1 S6
+1 +1 -1 -1 -1 -1 +1 +1
+1 -1 -1 +1 -1 +1 +1 -1
1) W1=[1]
W2 = 1 1
•-1
W4 = +1 +1 +1 +1
+1 -1 +1 -1
+1 +1 -1 -1
+1 -1 -1 +1
1. If a TDMA network has eight stations, the medium bandwidth has
_________bands
2. If a CDMA network has eight stations, the medium bandwidth has
_______ bands.
3. A Walsh table for 16 stations has a chip sequence of _________
chips.
4. In the reservation access method, if there are 10 stations on a
network, then there are _________ reservation mini slots in the
reservation frame.