Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

My big idea: Ancient Brain


CA216      CA249      CA318

CA400      CA651      CA668

Broadcast networks

Recall 1.2.

1.2.1 LANs

LAN - single building, campus, single company

Limited size network.
Worst-case transmission time is bounded and known in advance.
This makes possible certain designs - e.g. setting of tight timeouts.

High speed - up to 10 G bps
Low errors


Ethernet model dominates LANs (though new competition from wireless LANs).
Ethernet is broadcast network.
"Bus" network (all machines attached to one cable):

Search for other images.

Best image here.
Router leads to Internet.

1.5.3 Arbitration mechanism

Only 1 node can transmit at a time. All others have to refrain.
Constant conflicts. Need arbitration mechanism to decide who gets to transmit for next short time interval.
Ethernet algorithm:
Listen first. If someone transmitting, wait.
When transmission over, you transmit (but so will others who have been waiting).
If collision, back off - in fact, jam the ether to alert all nodes.
The other nodes will back off too.
You wait short random time, try again.
If still collision, you double the random wait time, and so on.

Crucial point: If everyone backed off and waited the same amount of time and then tried again, what would happen?

Ch.4 Medium Access Control

Physical / Data Link layer for a broadcast medium such as a LAN.

4.1.1 Static Channel Allocation

Frequency Division Multiplexing - Each user gets a private frequency band. No interference.
If no. of users is small and constant, each with a heavy load (always stuff to send), this works (e.g. between telephone switching offices).

If no. of users is large, constantly varying, or traffic is very bursty, FDM wastes bandwidth.
e.g. on a LAN this doesn't work so well.
Computer traffic is very bursty (peak traffic to mean traffic ratios of 1000:1 are common).
So most channels will be idle most of the time.
Also new users denied a channel because all n channels allocated, even if many idle.

True also with Time Division Multiplexing if time slots static, reserved in advance.
If time slots dynamic, though, we can use more bandwidth.

4.1.2 Dynamic Channel Allocation

Dynamic frequency slots - Used on fiber LANs. See 4.2.5.

Dynamic time slots - ALOHA and Ethernet.

4.2.1 ALOHA

Pure ALOHA: Frames transmitted at arbitrary times.
If any bit of a frame overlaps with any bit of another: collision, both frames are lost and must be re-transmitted.
How can we best avoid collisions?

Slotted ALOHA

Divide time into intervals. Each length of 1 frame.
Nodes have to send at start of a timeslot.
Much reduces collisions and increases throughput.

Aloha led to Ethernet.
Aloha discarded.
Recently, has got new lease of life with Internet on cable TV.

4.3 Ethernet

Ethernet: Check if medium busy before trying to send.
Much reduces collisions and increases throughput.
This is called Carrier Sense. This is possible on cable LAN, but not on wireless LAN.

Ethernet cabling.

"Fast Ethernet" cabling.

"Gigabit Ethernet" cabling.

Note Ethernet not all fiber. Copper wires still used for high-speed Ethernet (but only over short distance).

4.3.3 Ethernet Medium Access / Data Link protocol

Each frame starts with preamble of 8 bytes - each 10101010.
Helps synchronize sender and receiver bit boundaries.
Frame has addresses, since this is not point-to-point.
Data variable size up to max 1500 bytes.
Not allowing frames below a minimum size is found useful in collision detection. So if very little data, the frame is padded up to minimum length.
CRC checksum.
Data Link layer is unreliable, connectionless, datagram service (like PPP and IP).
For reliable, connection-oriented service: acks (an ack frame) and re-transmits in higher level (like TCP).

Ethernet on copper:

Frame formats on (a) old Ethernet, (b) IEEE 802.3.

4.3.4 Binary Exponential Backoff Algorithm

  1. After 1st collision, each node ("station") waits either 0 or 1 slots before trying again. If two pick the same random number, there is a 2nd collision.
  2. After 2nd collision, each waits 0, 1, 2 or 3 slots at random.
  3. If 3rd collision, each waits 0 .. 7 slots.
  4. ...
  5. After n'th collision, each waits random 0 .. 2n-1 slots
After certain max. no. of collisions, we give up. Network failure reported.

This algorithms adapts as the number of stations trying to send grows and shrinks.

  1. If constant: "After any collision, wait random 0 .. 1023"
    Then with 2 stations would almost never get a second collision. But would introduce huge delays.
    On the other hand, if hundreds of stations trying to send, such a rule would make sense, and would not waste time.
    There may be hundreds of stations online, but the number trying to send at any time varies widely.

  2. If constant: "After any collision, wait random 0 or 1"
    Consider if 100 stations trying to send. They will collide again and again until 99 of them pick 1 and one picks 0. This could take years.

Dynamic rule: Low delay when only a few stations collide. Longer delay (can't help that) when lots of stations collide, but collision is resolved.

Privacy on a broadcast LAN

Feeds      w2mind.org      ancientbrain.com

On the Internet since 1987.