Code: Select all
<!--
Load in the styling so any notes taken like this can be
viewed nicely in web browsers later.
-->
<link href="notexml.css" rel="stylesheet" type="text/css" />
<header>
<topic>The Data Link Layer</topic>
<class>Computer Networks</class>
<author>Andrew Brown</author>
</header>
<list title="Responsibilities">Responsibilities
<list title="Error Control">Error Control
<item>Parity checks</item>
<description>
A parity bit usually occupies one bit per byte (usually the LSB). The
sender counts up the number of ones in the binary string and adds
either a one or zero to make the number of ones even. For example,
if a binary string has five ones, the parity bit will be a one to make the
total number of ones six – even. If there are four ones in the binary
string, the parity bit will be a zero in order to keep the number of ones
even.
</description>
<note>
People like parity checks a lot because they can easily be added to
systems on the hardware level.
</note>
<item>Block sum check</item>
<description>
Another idea based off parity checks, except this one is aimed at larger
amounts of data. In addition to having a parity check on each byte, it
also has a horizontal parity bit to check columns (where normal parity
checks would be checking rows) when the data is aligned in a grid
format.
</description>
<note>
It was created as a better version of parity checks, but still had errors.
For this reason, it didn't last that long.
</note>
<item>CRC</item>
<description>
A CRC is calculated with exclusive or (XOR) and is usually used with
longer amounts of data, including a lot of packets.
</description>
<example>
</example>
<math>
</math>
<note>
CRC-16 catches all (100% of) single bit and odd-numbered bit errors in
16-bit and shorter binary strings, 99.997% of 17-bit strings, and 99.998%
of 18-bit or longer binary strings.
</note>
<item>Checksums</item>
<description>
Complex calculations that create a unique string for each unique piece
of data. They have great error detection, but have a heavier “cost" to
calculating them compared to other methods, such as parity checks. In
addition, they are usually larger than other methods, such as a single
parity bit. MD5 is an example of a checksum.
</description>
<item>Hamming Code</item>
<description>
Not only does the hamming code detect errors, but it tries to fix them,
which is unusual. It can only detect and correct single-bit errors.
</description>
<description>
If you have the data 01101110 to send, you number the bytes in binary
from the right to the left and reserve the bytes with locations that are
powers of two (1, 10, 100, 1000, etc). In this example, we will have
four check bits (1, 10, 100, and 1000) that will bring the total size
of data to send to 12 bits (original 8 + hamming 4). Now, the data is
written out to fill all the spaces except the check bits. To calculate the
check bits, you look at one check bit (for example, 100) and then count
the number of ones in the other bits with the check bit—in this case,
the third bit (due to a 1 in the third position of 100)—and perform the
same calculations as a parity bit: if there are an even number of ones in
the checked bits already, then the check bit is cleared and holds a zero.
If there are an odd amount of ones in the other bits being checked
(which, for check bit 100, is 101, 110, 111, and 110) then the check bit is
set and holds a one. This process is repeated for every check bit.
</description>
<description>
When the receiver receives the message, it looks at each check bit and
calculates the validity of it in the same way it was determined in the first
place: by looking at the other bits where the check bit is set (see above)
and counting the number of ones. If there are an even amount of ones,
the data is correct for that check bit. This process is repeated for all of
the check bits. If there is an error, the location of the error will be held
in the binary values of the concatenated check bits. For example, 0110.
</description>
<example>
Computer A wants to send the data 01101110. After it adds the check
bits, it transfers the data to Computer B, who receives the
data 011001011001. What bit was corrupted?
</example>
<answer>
The sixth bit, 0110, was corrupted on the way to the receiver. It left the
sender as a one, and arrived as a zero.
</answer>
</list>
<list title="Flow Control">Flow Control
<item>Stop-and-Wait ARQ</item>
<description>
<definition>ARQ – Automatic Repeat Request</definition>
<definition>Negative Acknowledgement – short circuits retransmit
times, so computers resend much faster.</definition>
Computer A wants to ask Computer B out on a date, so he first sends a
“Hello" message to Computer B. He waits until he gets an
acknowledgement back from Computer B before A sends the rest of his
message. If he doesn't receive an acknowledgement back, he waits a bit
and then says “Hello" again.
</description>
<description>
To calculatethe maximum time it would take to receive an acknowledgement
back from the server, you simply calculate the total time you are
transmitting (d = rt) and multiply by two.
</description>
<example>
Computer A is connected to Computer B with a 100km cat5 cable. What is
the maximum time Computer A would wait assuming that Computer B got the
correct message and sent back an acknowledgement?
</example>
<answer>
<math>
d = rt
100km = 200000000m/s * t
100000m = 200000000m/s * t
t = 0.0005s one way
2t = 0.0001s round trip
</math>
</answer>
<note>
To make stop & wait more efficient, you increase the packet size that is
transmitted. However, larger packet sizes have an increased chance to
corrupt, so there's a limit to how much it should be increased. Corrupted
packets have to be retransmitted.
</note>
<note>
Another method of making it more efficient would be to send more data during
the wait time -- which makes it look like a sliding window.
</note>
<item>Sliding Windows</item>
<description>
In a sliding window, the sender and receiver create buffers on both ends with
packet size n, labeled sequentially (0, 1, 2, 3, 4, etc) and relative to the
packet labels (0, 1, 2, 3, 4, etc). The sender starts at packet 0 and sends
it. While it's waiting for a response, it goes ahead and sends more packets
(for example, 1, 2, and 3), however it cannot send more packets than are inside
its "window" (buffer). When the sender receives each message, it marks it off
and moves its window down so it can accept new messages. (With a window size
of 3, it can only accept the 0, 1, and 2 packets. However, once it gets packet
0, it moves the window down and can now accept the 1, 2, and 3 packets.) When
the receiver has received a packet it was looking for (i.e. one inside the
window) it sends an acknowledgement back to the sender. When the sender receives
the acknowledgement, it also moves its window downwards (assuming the first
packet he sent -- packet 0 in this case -- has gotten a response back). If
the sender still hasn't received a response in a certain amount of time, it will
retransmit the packet in the window that it needs to get an acknowledgement for
so it can move its window down to transmit more packets.
</description>
<note>
Windows should have twice as many sequence numbers for the packets and window
frames than the total window size so no two packets have the same sequence number.
</note>
<list title="Sliding window forms">Sliding windows come in two forms:
<item>Selective repeat - only retransmits the packets that aren't acknowledged.</item>
<item>Go-back in - retransmits the packet that was damaged, plus all packets that
were sent afterwards.</item>
</list>
</list>
<list title="Framing">Framing
<list title="Framing Techniques">Framing Techniques
<item>Byte stuffing (character stuffing)</item>
<description>
<definition>
BSC - Binary Synchronous Communication (IBM, 1964)
</definition>
BSC marks the beginning of a frame with the string "DLS STX." So, a simple
piece of data about to be transmitted might look like:
<example>
DLE STX Party at my house tonight DLE ETX
</example>
But what happens when you try to transmit the string DLE STX in your actual
message? That's where you use byte stuffing. The sender decides to change
all strings of "DLE" to "DLE DLE" and the receiver knows to change all strings
of "DLE DLE" to "DLE." That way, someone sending the message
<example>
MAN, WEEDLE IS MY FAVORITE
</example>
actually looks like
<example>
MAN, WEEDLE DLE IS MY FAVORITE
</example>
but will revert back to its original form when the receiver receives the message.
</description>
<note>
This is for the most part obsolete now.
</note>
<item>Bit stuffing</item>
<description>
Bit stuffing is byte stuffing on a lower level. Instead of stuffing in
extra characters when a certain pattern is found, bit stuffing inserts
extra binary digits.
<definition>
HDLC - High Level Data-link Control
</definition>
<definition>
PPP - Point to Point Protocol (a type of HDLC)
</definition>
PPP uses start and end delimiters for each of its messages in the form of the
binary string 01111110. The data is in the middle. If you have the string
<example>
0111111000101111101111111010010110101011010101101111110
</example>
to send, the sender looks at the string for five consecutive ones in the data.
If it finds any, it appends a zero after the fifth one to prevent the packet
ending prematurely from an end delimiter being found in the data.
The above string would be sent as
<example>
011111100010111110011111011010010110101011010101101111110
</example>
<note>
Two extra zeros were added.
</note>
The receiver looks for strings of five ones and then a zero in the data, and
if it finds any, removes the zero to convert it back to five consecutive ones.
</description>
<item>Physical layer coding violations</item>
<description>
When a device has the ability to send more signals than have meanings, they can
use the "extra" signals (code violations) to mark the beginning and end of frames.
</description>
<example>
Token ring uses this by sending values without changing voltage (this is illegal
because Token rings use differential Manchester encoding).
</example>
<item>Bit count / Byte count</item>
<description>
This method has a field in the packet frame to tell the sender how long the
data field (or another field(s)) is. Ethernet is an example of this.
</description>
</list>
<item>Frame length field</item>
<item>Flag characters with character stuffing</item>
<item>Flag bit patterns with bit stuffing</item>
<item>Physical layer coding violations</item>
</list>
<list title="Access Control">Access Control
<item>Token passing</item>
</list>
</list>
<list title="IEEE Committees">IEEE Committees (802.x)
<item>802.1</item>
<description>
Head committee to oversee the other committees.
</description>
<item>802.2</item>
<description>
Worked on the standards that were common to all Local Area Networks.
<definition>
LLC - Logical Link Control
</definition>
</description>
<item>802.3</item>
<description>
Ethernet
</description>
<description>
<list title="10Base5">10 Base 5
<item>Thick Ethernet (RG8 Coax)</item>
<item>Yellow, marked every 2.5m for taps</item>
<item>10 stands for 10 Mbps</item>
<item>Base stands for baseband signalling</item>
<item>5 stands for 500 meter segments</item>
<item>100 nodes/segment</item>
<item>5 segments, up to 4 repeaters</item>
</list>
<list title="10Base2">10 Base 2
<item>Thin Ethernet ("cheapernet")</item>
<item>200m segments, 30 nodes/segment</item>
<item>RG58</item>
<item>BNC connectors</item>
<item>10 Mbps</item>
<item>Baseband signalling</item>
</list>
<list title="10BaseF">10 Base F
<item>Fiber optics</item>
<item>Max segment length: 2000m</item>
<item>Up to 1024 nodes</item>
<item>No increase in speed; just used to cover long distances</item>
</list>
<fact>
When a collision occurs on an Ethernet network, it does a Binary Exponential
Back-off Algorithm.
</fact>
<subject>
Binary Exponential Back-off Algorithm
<description>
When a collision is detected, the computers first continue transmitting
a "jam packet" to make sure everyone on the network hears the collision.
Afterwards, all parties in the collision stop transmitting for a random
amount of frame slots (either 0 or 1).
</description>
<definition>
The slot time in a network is the time taken to transmit a minimum-size frame.
</definition>
<description>
After waiting for its own amount of slot times, both parties listen for
traffic on the network, and if they find silence, they try to transmit again.
</description>
<note>
There's a 50% chance that both computers will choose the same random
number.
</note>
<description>
If a second collision is detected, the same steps are followed except that
the set of numbers that both computers choose from increases by a power
of two. For the second collision, the computers choose a number between
zero to three (4 numbers), and on the third collision they choose from
zero to seven (8 numbers).
</description>
</subject>
<fact>
In 1992, Ethernet was revamped to make it faster. It was backwards-compatible.
</fact>
<fact>
In 1995, IEEE finished the 802.3u standard.
</fact>
<subject>
802.3u
<list title="802.3u Statistics">
<item>100 Mbps</item>
<item>There was no coax standard because coax was on its way out.</item>
<item>Two twisted pair standards were created:</item>
<list title="100 Base TX">100 Base TX
<item>Cat5</item>
<item>Uses 2 twisted pairs (so you can have a phone line in addition to
Internet running through the cord.</item>
<item>4 BSB at 125 mHz encoding</item>
<item>Full duplex</item>
<item>100 Mbps</item>
</list>
<list title="100 Base T4">100 Base T4
<item>100m segments</item>
<item>25 mHz signal</item>
<item>Used all 4 pairs in the wire</item>
<item>1 pair was always to the hub</item>
<item>1 pair was always from the hub</item>
<item>and the middle two pairs could switch directions of flow</item>
<item>Because they used all 4 pairs, someone had to sacrifice a phone line</item>
<item>100Mbps one way, 33.3333Mbps the other way</item>
<item>Half-duplex</item>
</list>
<item>And a fiber standard was created:</item>
<list title="100 Base FX">100 Base FX
<item>2 strands of fiber</item>
<item>Full duplex 100Mbps</item>
<item>2Km range</item>
<item>Used to connect from building to building</item>
</list>
<list title="Two kinds of hubs">Used two kids of hubs
<item>Traditional shared hub</item>
<description>
Had a bus topology; half duplex
</description>
<item>Switched hub</item>
<description>
Eliminated all collisions; full duplex; no sniffing; standard today
</description>
</list>
</list>
</subject>
</description>
<item>802.4</item>
<description>
Token bus
</description>
<note>For the most part, this is obsolete.</note>
<item>802.5</item>
<description>
Token ring
</description>
<list>
<item>Shielded twisted pair</item>
<item>1, 4, or 16Mbps</item>
<item>Differential manchester encoding</item>
<item>2 modes of operation: listen mode and transmit mode</item>
</list>
<definition>
Mau - basically a switch for token rings, it would connect all
stations together and fix breaks automatically.
</definition>
<list title="Monitor station">
<item>Sees that the token is not lost somewhere on the ring</item>
<item>It does this by listening to the ring and timing it as it comes
around each time.</item>
<item>If the token is deemed lost, the monitor station will issue a
new one.</item>
<item>It also cleans out any messed up or corrupted frames in the
token, which is referred to as "draining the ring."</item>
<item>Watches for orphans (stations leaving after they've transmitted a
message on the token but before they removed it)</item>
<item>It does this by turning on a "monitor bit" in the frame when
the token comes by. If it already is turned on, it knows that it's
been around already and that it should be removed.</item>
<item>Inserts an artificial delay so the token will fit in the ring
if you don't have enough physical wire (or don't want to keep a thousand
feet of token cable in your room :P) - in other words, it "buffers the token."</item>
</list>
<list title="Beaconing">Beaconing
<item>Computers listen to their neighbors and alert the network on
any screwups.</item>
<item>Useful in identifying where a problem is</item>
</list>
<list title="Hierarchy">Hierarchy
<item>The standby monitor takes over if the monitor dies</item>
<item>Monitors periodically broadcast "I'm still here!"</item>
<item>In the event that the monitor is replaced, a new standby
monitor is elected</item>
</list>
<list title="Advantages">Advantages
<item>Eliminates all collisions</item>
<item>Faster than ethernet (16Mbps vs 10Mbps)</item>
<item>Built-in acknowledgement system</item>
<item>Priorities</item>
</list>
<list>WANs that use Token Rings
<subject>FDDI
<list>
<item>Fiber optics</item>
<item>100 Mbps</item>
<item>200km segments</item>
<item>Up to 1000 stations</item>
</list>
<list>Differences in using fiber
<item>Can't use differential manchester, so you have
to limit the frame length (to 4500 bytes here) so clocks
don't drift out of sync.</item>
<item>The sender reissues the token when he finishes transmitting
as opposed to when he strips off his message because the token
travels so fast</item>
<item>Priorities are handled differently. They time the token
coming around each time so they can predict the next time it'll
come along. If it's ahead of schedule, any station can send
anything. If it's behind schedule, only priority messages can be
sent. Late = busy network</item>
</list>
</subject>
<subject>SONET
<fact>Usually used to connect phone companies to phone companies (backbone)</fact>
<fact>Fiber optics</fact>
<list title="Types">Types
<item>OC1 - 51.84 Mbps</item>
<item>OC3 - 155 Mbps</item>
<item>OC192 - 9953.28 Mbps</item>
</list>
</subject>
</list>
<item>802.11</item>
<description>
Wireless Ethernet ("wifi")
</description>
<note>
Where 802.11b/g/n comes from
</note>
<definition>
Basic Service Set (BSS) - one standard wireless network
</definition>
<definition>
Extended Service Set (ESS) - two or more BSS networks connected together
</definition>
<subject>Frequency hopping spread spectrum (FHSS)
<fact>Originally used by the military</fact>
<fact>Keeps switching channels to prevent people from listening in</fact>
<fact>2.4-2.48 GHz range (unregulated, split into 79 1Mhz channels)</fact>
<fact>2 or 4 frequency shift keying</fact>
<fact>1m baud</fact>
<fact>1 or 2 Mbps</fact>
<fact>Made for voice communication (phones)</fact>
</subject>
<subject>Direct sequence spread spectrum
<fact>2.4-2.48 Ghz range</fact>
<fact>Each bit is replaced with a sequence of bits called the "chip code"</fact>
<fact>Uses entire band</fact>
<fact>Uses phase shift keying</fact>
<fact>1 or 2 Mbps</fact>
<fact>Not really used anymore</fact>
<fact>Uses a contention protocol to access channel</fact>
<subject>Contention protocol
<fact>Uses carrier-sense multiple-access with collision avoidance</fact>
<fact>Collision detection with wireless can't be done, so collision
avoidance is used instead.</fact>
<list title="Steps">Steps
<item>1. Listen first (until the line isn't being used)</item>
<item>2. Wait an interframe gap (IFG) amount of time</item>
<item>3. Wait an additional random amount of time</item>
<item>4. Transmit message and set timer</item>
<item>5. Listen for an acknowledgement</item>
<item>If one comes before the timer goes off - success!</item>
<item>Otherwise, the computer waits an exponential backoff time
and then goes back to step 4.</item>
</list>
</subject>
</subject>
<subject>802.11a
<definition>OFDM - orthogonal frequency division multiplexing</definition>
<fact>5.6 Ghz, 52 subchannels (48 for data, 4 for management)</fact>
<fact>PSK or QAM</fact>
<fact>18 or 54 Mbps</fact>
</subject>
<subject>802.11b
<definition>
HR-DSSS - High rate direct sequence spread spectrum
</definition>
<fact>2.4 GHz</fact>
<fact>54 Mbps</fact>
</subject>
<item>802.15</item>
<description>
Bluetooth
</description>
<fact>From Denmark (Ericsson)</fact>
<fact>Named after a former king who liked blueberries -- Harold Bluetooth.</fact>
<fact>Original idea was to make cell phones work as cell phones away from home
and as wireless landlines when at home</fact>
<definition>
Piconet - a network with up to 8 stations per network
</definition>
<fact>Uses piconets with 1 master and 7 slaves</fact>
<fact>Slaves cannot speak to each other</fact>
<fact>Slaves are provided a bare-minimum wage and a place to stay</fact>
<fact>Bluetooth can have up to 16 stations, but only 8 can be powered on and in
the same piconet at once</fact>
<definition>
Scatternet - a network of multiple piconets
</definition>
<fact>On a scatternet, a master on one network is a slave on another, forming a tree
through the network</fact>
<fact>Bluetooth tries to connect automatically to other BT devices when in range</fact>
<fact>2.4 GHz, 79 channels, 1MHz each</fact>
<fact>Uses FHSS - frequency hopping spread spectrum</fact>
<fact>Hops 1600 times/second</fact>
<fact>Uses time division multiple access with 625ms timeslots and 1 message per timeslot</fact>
<fact>1Mbps</fact>
<list>Two types of communication links
<item>SCO - Synchronous Connection-Oriented Link</item>
<description>
Used when avoiding delaying in delivery is more important
than accuracy
</description>
<item>ACL - Asynchronous Connectionless Link</item>
<description>
Used when data integrity is more important than delays
</description>
<note>Bad or corrupted frames are retransmitted in ACL, but not in SCO.</note>
</list>
<fact>Requires 259 microseconds just to hop between channels, which leaves
366 microseconds (from the total timeslot) for the data frame</fact>
<fact>You can either use 1, 3, or 5 timeslots, but you only have to jump once
per data packet, so it's more efficient to use 5 timeslots</fact>
</list>
<subject>Ethernet
<fact>
Originally developed as a way for the University of Hawaii (located on
several islands) to communicate between buildings, and was named ALOHA.
It was a wireless network.
</fact>
<definition>
CSMA/CD - Carrier Sense Multiple Access with Collision Detection
</definition>
<fact>
Uses CSMA/CD to be able to "listen in" on the messages as they are sending
them in order to determine if a collision occurred.
</fact>
<fact>
Bob Metcalfe, Ph. D (Harvard/MIT) from Xerox PARC looked at the ALOHA
network developed in Hawaii and build the first "Ethernet" network on
May 22, 1973. He looked at how the network worked (see below) and linked
together 100 workstations on a 100km coax cable in a bus topology.
</fact>
<note>
Metcalfe named it Ethernet, which is short for "Luminiferous ether network."
</note>
</subject>
<subject>Gigabit
<list title="Gigabit">
<item>Cat5 or Cat6</item>
<item>25m segments</item>
<item>Full duplex</item>
<item>Bad for great distances (use fiber)</item>
</list>
</subject>
<subject>Token
<list title="Criticisms">Addressed two criticsms of Ethernet:
<item>A non-deterministic protocol made it impossible to predict how
long it would take for an Ethernet packet to transmit (which made it
impossible to use Ethernet in factories and construction lines).</item>
<item>No priority mechanism</item>
</list>
<fact>Eliminates all collisions in a network (with correct usage) and can
allow a theoretical 100% utilization of the network.</fact>
<list>Originally driven by two companies
<item>Token Bus - GM (for their assembly lines)</item>
<item>Token Ring - IBM (for monopoly's sake)</item>
</list>
</subject>
<subject>Bridges
<definition>
Repeaters - on the physical layer, retransmits data
</definition>
<definition>
Bridges - data link layer, ties two networks together
</definition>
<definition>
Routers - network later, not as seamless as bridges
</definition>
<list title="Reasons people bridge networks">Reasons people bridge networks
<item>Cover a larger physical distance</item>
<item>Traffic control</item>
</list>
</subject>