Parity Bit
v
Even
parity – The bit 7 is chosen such that the number of 1’s is even.
Example:
v
Odd
parity – The bit 7 is chosen such that the number of 1’s is odd.
Example:
v
Check
sum
v
CRC
Local Area Networks
v
Network
technologies are classified in:
Ø
Local Area Networks (LAN) --------------- à
room/building
Ø
Metropolitan
Area Networks (MAN) ---------- à city
Ø
Wide
Area Networks (WAN) ----------------- à group of cities
LAN
Ø
Many
technologies
Example:
ethernet, appletalk, token ring,
pronet, x25
Ø
high
throughput
Ø
relative
low cost
Ø
limited
short distance
Ø
often
rely on shared media
Ø
LAN
principle: A computer is more likely to communicate with computers nearby than
with computers that are distant. This is also called the locality principle.
Topology of a Network (page 77)
v
specifies
the general “shape” of the network
v
primarily
refers to interconnections between computers
v
hides
the actual hardware devices
Star Topology
Ø
central
component of the network is the hub
Ø
there
is a separate connection for each computer in the hub
Ring Topology
Ø
no
Central facility
Ø
connections
go from one computer to the other
Ø
computers
take turns to send messages to each other using a passing token
Bus Topology
shared cable
Ø
shared
medium connects the computers
Ø
example
of bus network: Ethernet
Ø
Most
popular: LAN
Ø
IEEE
standard 802.3
Ø
There
are 3 generations of internet:
o 10 Mbps (ethernet),
100 Mbps (fast ethernet), 1 Gbps
(gigabit Ethernet
Ø
it
uses the same format regardless of speed as well as MTU (maximum transfer
unit)/(max data size) of 1500 bytes
Ø
ethernet
uses a shared medium
Ø
computers
take turns to transmit because only one station transmits at a time
Ø
media
access control (MAC) policy ensures fairness
Ø
Messages
sent by a computer are received by all other computers, including it.
Ø
Signal
propagates across entire cable
Ø
All
stations receive the transmission
Ø
The
Ethernet interface will filter the packets and will pass to the OS only the
messages that are going to that computer
Ø
Destination
address is 6 bytes
Ø
Each
interface has a different Ethernet address given by the manufacturer
Ø
A
technique called CSMA/CD is used to control the access to the shared bus
CSMA/CD
v
Carrier
Sense Multiple Access/Collection Detection.
v
Multiple
access (MA)
Ø
Multiple
computers share the same media.
Ø
All
of them use the same access algorithm.
v
Carrier
sense (CS)
Ø
A
computer transmits until the medium is idle.
v
Collision
detection (CD)
Ø
Simultaneous transmissions are
possible and they will interfere with each other (collision).
Ø
The
interface will listen to the medium during transmission.
Ø
If
the received signal is different than the signal sent then there is a
collision.
Ø
If this is the case the transmitter
stops the transmission (back off) and tries again later.
v
Back
off after collision
Ø
Wait
for random time t1, such that 0 ≤ t1 ≤ d
Ø
Use
CSMA and try again
v
If a
2nd collision occurs wait a random time t2, such that 0 ≤ t2
≤ 2d
v
Double
range after each successive collision
v
This is
called “exponential backoff”
Ethernet
v
CSMA/CD – Carrier Sense Multiple Access/
Collision Detection
Ø
Exponential
backoff. Wait
random time 0 ≤ t1 ≤ d
Ø
If
second collision occurs, wait 0 ≤ t2 ≤ 2d
Wireless Networks (page 82)
v
Limited
range. Not all the stations receive all
of the transmissions.
v
The
power of the network of the transmitters is limited to allow more networks
without interference with each other.
There is a limited number of
channels
v
If
the max transmission range is “d”, then station 2 can’t receive packets from 1
and 2
v
However,
station 1 and 3 do not receive packets from each other.
v
We
cannot use collision detection only because:
Ø
In
Ethernet we assume that all stations receive the transmitted packets
Ø
In a
wireless network, there is no guaranteeing that all the stations will receive
the packets sent. Example: if one sends
a packet, 3 will not receive it
Ø
If we
had collision detection and 1 sends a packet to 2 while 3 sends a packet to 2
at the same time, 1 will not be able to detect a collision since 3 is more than
“d” from 1, and 3 will not be able to detect a collision since 1 is also more
then “d” from 3
v
Instead of using collision
detection, wireless networks use “collision avoidance” (CA)
CSMA/CA (Wireless
Nets)
v
Carrier Sense Multiple
Access/Collision Avoidance
v
Both sides send a small
message before data transmission
v
The small message
informs all the stations in the range that the channel will be used.
Ø
1. sends a message: “1
is about to send a packet to 2.” à 2 receives message.
Ø
2. sends a message: “2 is about to receive a packet from 1.”
1 and 3 receive message
Ø
3. Message is sent from
1 to 2
This protocol does not prevent collisions 100% of the time but it limits
the amount of collisions.
Identifying a
destination
v
All stations on a
shared media receive all of the transmissions
v
Each station has an
assigned unique number called “the station address”
v
Each packet contains
the source and the destination
v
Ethernet :
Ø
Address is 48 bits long
(6 bytes)
Ø
Address is assigned by
the manufacturer
Ø
Network interface card
is also called NIC
Ø
All stations receive packets and the stations will discard the packets
addresses to another station.
Ø
Interface hardware (not
software), checks the address. If the
address matches the NIC, the packet is passed to the OS by interrupting the CPU.
Ø
This prevents CPU overhead
due to excessive traffic
v The same packet
goes to all of the computers in the network.
Ø If a packet is
sent from B to A, all of the computers will receive the packets (A, B, C,
D). However, the network interface will
filter the packets that are not destined to that computer.
Ø That packet will
then be discarded by the interface.
v In this case
only in A, will the packet cause an interrupt in the OS, but the same packet
does not cause an interrupt in C, B, and D.
v The filtering is
done by the hardware.
v There is a
special mode in the Ethernet interface called “Promiscuous Mode” where all
packets regardless of their destination are passed to the OS.
v This mode is
used by network analyzers and packet sniffer
programs.
v The program
needs to have root privileges to be able to set interface in promiscuous mode.
v Snoop programs
may use a lot of CPU because there is an interrupt for every packet that goes
through the network.
Types of Addresses
v Single
destination (called Unicast in most cases).
v All stations in
the network (broadcast). It is not used very often because it causes a lot of
CPU overhead in the computers in the network.
v A subset of
stations (Multicast). The stations in
the subset add a common address to the list of multicast addresses in the
Ethernet interface.
Broadcast in the Ethernet
v All 1’s in the
destination address specifies broadcast
v The sender
places the broadcast address in packet.
It transmits a copy of the packet and keeps a copy of the packet to
itself
v All stations
receive a copy
v A receiver
always accepts a packet that contains a destination,
Ø The station’s unicast address, or
Ø The broadcast
address, or
Ø A multicast
address that exists in the station’s network interface.
Format of Ethernet Packet – 1526 bytes
v The minimum
packet size is necessary to be able to detect collisions in an internet network
that uses a long wire
v The Ethernet
header is fixed for all types of Ethernet
v Ethernet frame
type contains the type of data sent:
0x0800 à Data is an IP packet
0x8137, 8138 à Data is an IPX
packet (Novell)
0x806 à ARP
Evolution of the Ethernet
v
Original
Ethernet:
Ø
Used
a heavy coaxial cable
Ø
Formal
name: 10 base 5
Ø
Also called thicknet
v
Second
generation:
Ø
Thin
Ethernet
Ø
Formal
Name: 10 base 2
