The datalink layer in broadcasting networks Flashcards
Basic types of broadcasting networks
- Local area networks (shared wire (e.g. classic Ethernet) or shared wireless (e.g. Wi-Fi))
These have a very short delay. - Satellite networks (Wide area network). These have a very long delay (270 msec)
Channel allocation problem
how to allocate a single broadcast channel among competing
users:
- Static Channel Allocation: Capacity of the channel is split among multiple competing users like FDM or TDM. Do not work well with bursty traffic
- Dynamic Channel Allocation: Gives the channel to a user when they need it. We use multiple access protocols
Assumptions with multiple access protocols
- All hosts can transmit frames on the channel and all can receive from it
- Each frame sent is received by all hosts
- Hosts have to contend for the use of the channel
- If two hosts send more or less simultaneously, the two frames will collide. Both will be damaged (in data terms – electrically, the medium can cope)
What are the assumptions that depend on the system
- hosts may/may not be able to detect collisions when they occur
- Timing of frame transmissions may be assumed continuous or slotted
- A network may have carrier sensing or not have it
Contention protocol - Aloha
- The protocols used on satellite channels are called Aloha
- Developed at the University of Hawaii, using a ground-based radio system
- Two versions (pure ALOHA and Slotted ALOHA)
Pure aloha
- Hosts transmit whenever they want. Colliding frames are destroyed
- If a frame was destroyed, the sender just waits a random amount of time and sends again
- Utilisation is bad under high load (18% utilisation)
Slotted aloha
- Divide the time up into discrete intervals, each interval corresponding to one frame
(slotted time) - Hosts can only transmit at the start of each time slot
- This requires one special station to emit a “pip” at the start of each interval for all others
to synchronise (like a clock). This double the efficiency of Pure Aloha at 37%
What is CSMA protocol
Carrier sense multiple access
1- persistent protocol
- When a host has data to send, it first listens to the channel to see if anyone else is
transmitting - If the channel is busy, the host keeps listening until it becomes idle
- When the host detects an idle channel, it immediately transmits a complete frame
- If the frame is damaged, the host waits a random amount of time and starts all over
again
non persistent protocol
- When a host has data to send, it first listens to the channel to see if anyone else is
transmitting - When the host detects an idle channel, it immediately transmits a complete frame
- When the sending host detects that the channel is busy, it does not continuously sense it
for the purpose of seizing it immediately upon detecting the end of the previous
transmission - Instead, it waits a random period of time and then repeats the algorithm
p Persistent protocol
- When a host becomes ready to send, it senses the channel. If it is idle, it transmits with a
probability p (therefore the probability that it defers transmission until the next slot is q =
1 – p) - If that slot is also idle, it either transmits or defers again, with probabilities p and q
respectively - If a slot is busy, it waits a random amount of time and starts again
Collision detection protocol
- With CSMA/CD, a host aborts its transmission as soon as it detects a collision, it waits a
random period of time, and then tries again - Quickly terminating damaged frames saves time and bandwidth
- This protocol is widely used on LANs including classic Ethernet
- A host can only detect a collision as it happens because
- A host uses highly special electronics that allows it to hear while it is transmitting
- Frame transmission time >= Round trip time
Bit map protocol
- Following a frame transmission period, there is a short contention period which consists
exactly of N small slots for the N hosts on the channel - If a host j has a frame to send, it inserts a 1 into slot j of the contention period. After all N
slots have passed by, each host has complete knowledge of which hosts wish to transmit - At that point, they begin transmitting in numerical order
- Since everyone agrees on who goes next, there will never be any collisions
Limited contention protocols
- Limited Contention Protocols combine the best properties of the contention and collision-
free protocols (uses contention at low loads to provide low delay, but uses a collision-free
technique at high loads to provide good channel efficiency)
Adaptive tree walk protocol
- We divide the hosts up into groups. Only the members of
group j are permitted to compete for slot j. e.g. - In the first contention slot following a successful frame
transmission, slot 0, all hosts are permitted to acquire the
channel - If one of them does so, fine
- If there is collision, then during the next slot, slot 1, only
those hosts falling under node 2 in the tree (first sub-tree)
may compete - If one of them acquires the channel, the next slot is
reserved for those hosts under node 3 (the second sub-
tree), etc
Binary exponential back-off protocol
- After a collision, time is divided up into discrete slots whose length is equal to the worst-
case round-trip propagation time on the LAN cable - After the first collision, each host independently waits either 0 or 1 slot times before
trying again. If two hosts collide and each one picks the same random number (0 or 1),
they will collide again - After the second collision, each one picks either 0, 1, 2 or 3 at random and waits that
number of slot times - If a third collision occurs, then the number of slots to wait is chosen from the interval 0
to 23 – 1 - After 10 collisions, the number is frozen at 210 -1(0-1023) slots
- After 16 collisions, report failure to the computer. Further recovery handled by higher
layers
Wireless has complications compared to wired
- A station may not be able to transmit/receive frames to/from all other stations due to limited
radio range (have different coverage regions) - Wireless system cannot detect a collision while it is occurring. Instead, ACKs are used to
discover collisions and other errors - Carrier sensing is useless because of hidden and exposed terminals problems
Multiple Access with Collision Avoidance Protocol (MACA)
- A wants to send data to B, so it sends a short RTS (Request
To Send) - B is within range of A, hears RTS then sends CTS (Clear To
Send) to allow A to transmit. Upon receipt of the CTS, A
begins transmission - C is within range of A, hears the RTS and keeps quiet long
enough (using RTS info) for the CTS to be transmitted back
to A without conflict - D is not within range of A and so can’t hear RTS, but is
within range of B, hears CTS and keeps quiet during the
upcoming data transmission - E hears both control messages and, like D, must be silent
until the data frame is complete
The ethernet
One shared coaxial cable to which all hosts
attached. Speed is up to 10 Mbps, with
Manchester encoding