***********************************************************************
*** Ethernet - The Bottom Two Layers : bobtfish
http://napalm.firest0rm.org/ ***********************************************************************

There are lots and lots of articles about TCP/IP, how it works and how
to hack it, however there is very little information (for the poor hacker
who cannot afford text books) about actual ethernet itself, where it came
from and how it works. I hope to go some way to correct that in this
article.

Using the OSI (Open Systems Interconnection) networking reference model
ethernet takes the bottom two layers, the data link layer and the
physical layer. I intend to talk about both of these layers in detail
however first I will give a brief introduction to the ethernet system.

Introduction
------------

Ethernet was invented by Xerox, DEC and Intel. It grew from a system
researched ar Xerox PARC (Where such things as mice and GUIs came from)
where they built a 2.94Mbps system. (Mbps = Million bits per second) This
system was the son of a system called ALOHA constructed to allow radio
communication between the Hawaiian Islands.

[ The great thing was, this was rounded up to 3Mbps for marketing. Some
people objected to a roundoff error greater than the entire bandwidth
of ARPANET at the time... {ajax} ]

Ethernet is sometimes called IEEE 802.3 however this is wrong. IEEE
802.3 is *very* similar to actual ethernet except 802.3 describes a whole
slew of systems running from 1-10Mbps on various media (more than
ethernet) and a field in the packet header is differs between ethernet
and 802.3. Now, you're thinking, there is an 802.3, but what happened to
802.1 and 802.2? Well, 802.1 is an introduction to the 802 standards and
defines a set of primitives and 802.2 describes the upper part of the data
link layer (which we don't give a toss about right now). Additional info
ref #1

Ok, back to ethernet then. Ethernet is a CSMA/CD protocol, which stands
for Carrier Sense Multiple Access with Collision Detection. Don't worry,
I didn't understand it first time either so I'll run through it bit by
bit:

Carrier Sense - The system looks at the cable to see if anything is
transmitting before it does. (So that two machines are not
trying to send data down the same wire at the same time.)

Multiple Access - Multiple machines can access the same communication
channel to send data. Ergo there is only one set of
wires no matter how many machines you have.

Collision Detection - If a station is transmitting and two stations are
waiting then when the first station stops they will
both try to transmit at once, meaning the data will
be garbled. Collision detection means they detect
this and sort it out somehow. (More on this later)

Note that Ethernet does *not* guarantee reliable delivery of the data -
even if it is sent correctly without problems the receiving machine may be
so loaded that it does not have spare buffers to put the data in so it may
be erased.

Types of ethernet - The boring stuff.
-------------------------------------

Since Ethernet refers to the 'ether' ie the medium the signal passes
through we may as well start our discussion on cables.

Name Cable Max segment Nodes/seg Comments
-------------------------------------------------------------------------
10Base5 Thick coax 500m 100 Old - Not used
10Base2 Thin coax 200m 30 Cheap
10BaseT Twisted Pair 100m 1024 Standard
10BaseF Fibre 2000m 1024 Building<>Building
100BaseTX Twisted Pair 100m 1024 Fast
100BaseFX Fibre 2000m 1024 Expensive

I will deal with these in order in the table.

10base5 is the oldest (and obsolete in anywhere but the poorest
universities). It is called thick ethernet because it is yellow and
resembles a garden hose with markings every 2.5 meters. (The 802.3
standard suggests the cable should be yellow but does not require it ;) )
Connections are made using vampire taps in which a pin is forced 1/2 way
into the core which are then connected to a transceiver. This transceiver
invariably connects to the host computer using AUI which if you see it on
a hub or network card look like parallel ports (D shaped connector)

10base2 is known as thin ethernet and in contrast to 10base5 bends
easily. Connections are made using BNC type connectors to form T
junctions in the cable. Thin ethernet is MUCH cheaper and easier to
install than 10base5 but can only run 200 meters and can handle only 30
machines per segment. Both of these systems have a big problem: any bad
connection, wonky BNC connector or cable break will cause the entire
network to fall apart. The only reliable way to find these breaks is to
pull out each cable and T-piece and replace them one by one (which means
quite a long network downtime with 30 machines) or to use an expensive
machine called a 'time domain reflectometer' which injects a specially
shaped pulse into the cable and waits for it to echo back (the echo is
caused by the fault). This allows the fault to be pin-pointed. The phreaks
amongst you will know that a time domain reflectometer can also tell you
if someone is tapping your phone. Well, before it gets to the exchange
that is...

These types of problems prompted the development of 10baseT which uses
a different kind of wiring pattern with every machine going to a central
hub which receives and re-transmits the signals to every other connected
station meaning that a cable break will disable one machine, not the
whole network. A large hub for many stations costs a lot of money but it
means that adding or removing a station can be done without halting the
network.

Another option is 10BaseF which uses fibre optics. This is expensive
due to the cost of fibre and the connectors and terminators but has
excellent noise (and tempest) immunity and is the connection of choice
for low speed links between buildings.

[ There are sub-standards 10BaseFB, for inter-repeater links, and
10BaseFL, for links to workstations. As far as I can tell, this was
done simply to aggravate people. You may also run into an older
standard called Fiber Optic Inter-Repeater Link, or FOIRL. If so,
good luck to you. {ajax} ]

A quick note about repeaters - 10base5, 10base2 and 10baseT all have
quite small maximum segment lengths so to allow larger networks segments
can be connected with repeaters. These are a physical layer device which
take the signal, amplify it and send it on its way. As far as the
network is concerned there is no difference (other than electronic delay
introduced by the repeater) A network can contain as many segments and
repeaters as required as long as no two machines are > 2.5km apart and no
path between two machines has more than 4 repeaters. (Why these
restrictions are present will be discussed later.)

100baseTX is now quickly becoming the standard for new installations and
is almost the same as 10baseT technically. (coax cables were dropped due
to the overwhelming advantages of a hub-based design) Another good feature
for the network engineer is that the same wires are used for the same
thing meaning you don't need different cables. (However some poor-quality
cables that work at 10Mb/s will not work at 100Mb/s.

A coding scheme called 4B5B is used at 125MHz with 5 clock periods
transmitting 4 bits of data. 100baseFX uses two strands of multimode
fibre, one for each direction and has the same advantages discussed with
10baseF. This is all this paper will say about fast ethernet. Readers are
referred to ref #2 if interested.

Manchester encoding - The interesting stuff
-------------------------------------------

Ethernet does not use straight binary encoding with 0 volts for 0 and 5
volts for 1 as it would lead to ambiguities because stations would not be
able to tell the difference between an idle sender (0 volts) and a zero
bit (0 volts).

What is needed is a system that lets receivers tell the start, middle
and end of each bit with no reference to an external clock. A system
called manchester encoding is used where binary 1 is sent by having the
voltage high during the 1st half of the bit and low during the second. A
binary 0 is sent as a low during the first 1/2 of the bit and a high
during the second. This means every bit has a transition in the middle
making it easier for the receiver to synchronize with the sender. The
disadvantage of Manchester encoding is it requires twice as much
bandwidth as straight binary encoding because the pulses are 1/2 the
width. It is shown below:

Bit stream: 1 0 0 0 0 1 0 1 1 1 1
Binary : --________--__--------
Manchester: -__-_-_-_--__--_-_-_-_

[ Hey bobtfish - did Manchester encoding actually come from Manchester in
the UK, or was it arbitrarily named? {kynik} ]

The high signal in ethernet is +0.85V and the low signal is -0.85V. This
gives a DC value of 0V.

The MAC sublayer protocol - The really interesting bit.
-------------------------------------------------------

Bytes:
7 1 6 6 2 0-1500 0-46 4
|Preamble| |Destination| Source | | Data | Pad | Checksum |
| | | address |address | | | | |


Each frame starts with a preamble of 7 bytes, each containing the bit
pattern 10101010. This, when manchester encoded produces a 10MHz square
wave for 5.6usec to allow the receiver's clock to synchronize to the
transmitter's. Next comes a start of frame byte containing 10101011. The
source and destination addresses come next. The address containing all 1
bits is reserved for broadcast which is delivered to all stations on the
network. The minimum frame length is 64 bytes, from destination address to
checksum and so if the data is less than 46 bytes then the pad field is
used to pad the data to 64 bytes. This stops a station that is
transmitting a short frame from completing before the first bit has
reached the other end of the cable, where it may collide with another
frame. (Remember we can have 2.5km of cable and 4 repeaters in there -
quite a large delay).

If a station detects a collision (by sensing more power on the cable
than it is putting out) then is aborts its transmission and transmits
48bits of noise to warn all the other stations. It then waits a random
amount of time before sensing the cable to try and transmit again. If the
frame was too short then if a collision occurs the sender could conclude
that it was successful as the noise burst does not get back before it has
stopped transmitting.

As network speed increases the minimum frame length must go up or the
maximum cable length must come down. For a 1Gbps LAN the minimum frame
size would be 6400bytes with a 2.5Km maximum distance. This is called the
long fat pipe problem. (Which if you do any studies of high-speed
communication you will come across quite often)

The final field is called the checksum. It is a 32bit hash code of the
data using a cyclic redundancy check. If some of the data is wrong then
the checksum will almost certainly be wrong.

Binary Exponential Backoff (And other things with no amusing acronym)
---------------------------------------------------------------------

We now know how ethernet stops two machines transmitting at the same
time, however how does it arbitrate between them? Well since there is no
designated 'master' machine, (which is why receivers have to synchronize
their clock to the sender - there is no master clock), the two stations
must perform this arbitration between themselves.

After a collision stations divide time up into discrete slots of length
512 bit times, or 51.2usec.

After the first collision, each station waits either 0 or 1 slot times
before trying to transmit again. If they collide again each station picks
0, 1, 2 or 3 at random and waits that number of slot times. If a third
collision occurs then the next time the number of slots to wait is chosen
at random from 0 to (2^3)-1. This random time is increased exponentially
until ten collisions have happened, at this point the randomization is
stopped at a maximum of 1023 slots. After 16 collisions the controller
gives up, goes for a beer and reports failure to transmit.

[ Ethernet beer? Sounds like an IPO! ;) {kynik} ]

This is called binary exponential back off (and has with and without
beer options ;) ) and was chosen to dynamically adapt to the number of
stations trying to send. If the randomization interval was fixed at 1023
the chance of 2 stations colliding a second time would be greatly reduced
but the average delay would be 100s of slots. However if each station
always delayed 0 or 1 slots then if 100 stations were waiting to transmit
then they would collide until 99 picked 0 and 1 picked 1 or vice versa..

By having the random time grow exponentially the system gets the lowest
delay at low load but enables the collision to be resolved when lots of
stations want to transmit.

Switching
---------

As you add more stations to an Ethernet the traffic (naturally) goes up.
Eventually the system will saturate (And with lots of machines waiting to
send efficiency goes down the toilet). There are a number of ways to
resolve this. First one could increase the speed of the LAN. (ie rip out
all the 10BaseT cards and put 100BaseT cards in) however this is not
necessarily practical. Another route to go is to segment groups of
machines that communicate a lot onto different physical networks and use a
bridge or router to connect them. The way we will look at here is a
switch.

A switch is like a hub except that it has inside it a microprocessor and
a very fast internal bus. When a station sends a frame the switch checks
where it is destined for and copies it across its internal bus then
sends it out to the other station. If the internal bus is busy then the
switch buffers the packet in internal ram and then forwards it when the
bus is available. This means that (since the internal bus is many times
faster than the ethernet) you can theoretically get an aggregate bandwidth
of number of stations * speed of network. This is because each port forms
it's own collision domain. This also gives that added advantage that
full-duplex operation can be supported. (ie A station, if its ethernet
card supports it, can be both transmitting and recieving a frame at the
same time)

However, if all stations on the switch are trying to contend to send to
one particular station there can be problems. If one machine is a server
and the rest are clients, all of which are making requests (Using all the
10Mb/s bandwidth on their port) then you have an aggregate of 120Mb/s (on
a 12 port switch) which can never get through. How a switch handles this
situation is manufacturer dependent.

Nowadays a common item is a switch with one or two 100baseT ports and
10 or so 10baseT ports. This goes some way to solve the above problem as
few workstations need more than 10Mb/s however a server can easily use
100Mb/s to serve it's clients.. So with 10 clients at 10Mb/s and a server
at 100Mb/s then each client can get a full (and both ways) 10Mb/s of
throughput. And you can happily boot over the network and run all your X
applications on the remote machine at 10Mb/s. (Ok I wouldn't like to try
remote Quake 3... But hey...)

Another advantage of a switch (to a network administrator) and
disadvantage (to a black-hat) is that any machine connected to the switch
will only see traffic destined for that machine. That is, an ethernet
sniffer will catch no more than local users accounts and passwords.

[ Not entirely true. Most switches have a MAC (ethernet) address table
in internal memory, with possibly multiple MAC addresses associated
with a single port. Some switches will forget MAC addresses after a
period of inactivity. Occasionally, a host will have the MAC address
of another host in its ARP cache, but since the switch no longer knows
what port the destination host is on, it will be forced to broadcast
the packet. Oops. Of course, some switches are even smarter and have
their own MAC address, and can do ARP queries for machines they forget
about. Not a major problem, but don't trust switches to protect you
from sniffing; besides all this, some are just buggy. {ajax} ]

End notes
---------

I hope this article has given you a few clues about how Ethernet
actually works if you didn't know already, and even if you did it might
have told you some interesting history, but maybe not.

Just a couple of (well 4) quick notes:

1) When transmitting IP over ethernet there is a system called arp for
matching IP addresses and physical network addresses. (Look in
/proc/net/arp under linux I believe for the arp of the rest of your
network or ifconfig for that of your ethernet adaptor.)

2) Ethernet hardware addresses are meant to be unique - I know of
multiple instances of people having 2 cards with the same address.

3) Microsoft Office products embed your hardware address in documents.
This is a pretty unique identifier. (And how they got the dude who
wrote Melissa). Get vi now.

4) Microsoft Windows 95 (I believe but I'm not sure - its one of them) is
dumb. If you make an ethernet packet addressed to FFFFFFFFFFFF
(broadcast) but with the station's IP address then it will accept it
as arriving at the station's IP address, not by broadcast. (This would
work for any ethernet address but the hardware in the ethernet card
filters out packets not for the machine or broadcast.)

References
----------
#1 - Stallings, W - Local and Metropolitan Area Networks. 4th Ed.
Macmillan 1993
#2 - Johnson, H. W. - Fast Ethernet-Dawn of a new network, Prentice Hall
1996