Transcript T - Department of Electrical Engineering & Computer Science

COSC 3213: Computer Networks I
Instructor: Dr. Amir Asif
Department of Computer Science
York University
Section M
“Local Area Networks”
Topics:
LAN Standards: IEEE 802.3, IEEE 802.3u, IEEE 802.3z, IEEE 802.5
Garcia: Sections 6.7 – 6.8
Review of Number System
Consider four representations for integers:
1.
Decimal, each digit lies between 0 and 9
2.
Binary, each bit is either 0 or 1
3.
Octal, ecah octal digit lies between 0 and 7
4.
Hexadecimal, each hexadecimal digit lies between 0 and F
Activity 1: Convert the decimal number 1500 into representations (2) – (4).
2
IEEE 802.3 - History
1.
2.
3.
4.
5.
6.
Developed in the 1970s by Xerox
Dec, Intel, and Xerox completed the “DIX” standard for 10Mbps LAN based on coaxial cable.
“DIX” standard is referred to as “DIX Ethernet Standard” or simply “Ethernet”.
IEEE 802.3 LAN standard was developed in 1985, very similar to DIX.
In 1995, the 100Mbps Fast Ethernet standard (IEEE 802.3u) was approved.
In 1998, the 1Gbps Gigabit Ethernet Standard (IEEE 802.3z) was approved.
Trend of faster and long range Ethernet continues …
3
IEEE 802.3 – Protocol (1)
1.
2.
IEEE 802.3 uses the 1-persistent CSMA/CD protocol in the MAC sublayer
 A station with a frame to transmit waits until the channel is free (or silent).
 When the channel goes silent, the frame is transmitted.
 If a collision is not detected for (2 × propagation time), frame is assumed delivered
 In case of a collision, the station aborts the transmission and reattempts after a randomly
scheduled time
Rescheduling Algorithm: is based on a truncated exponential backoff algorithm.
 For n’th transmission, the backoff period is selected by choosing a length at random
between (0, 2k – 1) minislots where k = min(n,10).
 Minislot: defined as a duration that is at least as long as (2 × propagation delay)
 1st Retransmission:
(0,1) minislots
2nd Retransmission:
(0,1,2,3) minislots
3rd Retransmission:
(0,1,2,3,4,5,6,7) minislots
10th and higher retransmissions: (0,1,2, …, 210 – 1) minislots
4
IEEE 802.3 – Protocol (2)
3. A total of 16 retransmission attempts are allowed.
Activity 2: Show that the total propagation delay for a 10Mbps LAN consisting of five segments,
each 2500m long and connected to each other with 4 repeaters, is around 51.2 ms. What is the
minimum length of an Ethernet frame designed for the 10Mbps LAN? (Assume a propagation
speed of 2.5 × 108 m/s)
Answer: 512 bits
4. Activity on the IEEE 802.3 LAN is sum of four components:
2tprop
contention transmission
5.
6.
idle
 Idle: nearly 0 near saturation.
 Contention: multiple of (2tprop)
 Transmission: L / R
 Propagation: tprop
The average number of minislots per contention period is e minislots.
The normalized throughput of IEEE 802.3 is given by:

1
with a  X / t prop
1  (2e  1)a
5
IEEE 802.3 – Protocol (3)
a
Normalized throughput
0.01
0.94
0.1
0.61
0.2
0.44
Transfer delays (multiples of slots) grow very large as load approaches throughput
CSMA-CD
a = 0.1
a = 0.2
30
a = 0.01
25
20
15
10
Load
0.96
0.9
0.84
0.78
0.72
0.66
0.6
0.54
0.48
0.42
0.36
0.3
0.24
0.18
0.12
0
0.06
5
0
8.
Effect of a on performance of IEEE 802.3:
Avg. Transfer Delay
7.
6
IEEE 802.3 – Frame Structure (1)
802.3 MAC Frame
7
Preamble
1
SD
2 or 6
Destination
Address
Preamble:
Starting Delimiter (SD):
Source/Destination Address:
Length:
2 or 6
Source
Address
2
Length
4 (bytes)
Information
Pad
FCS
has 7 bytes of the bit pattern 10101010 …….
Used for synchronization
10101011, indicates start of the frame
6 octets (or 48 bits long) is always used => 246 global addresses
specifies the length of data (information) in bytes (or octets)
Max. frame length = 1518 bytes excluding preamble & SD
Information = 1518 – 18 = 1500 bytes
Length field = (05DC)16 < (0600)16
Min. frame length = 512 bits or 64 bytes
Pad field ensures that the frame is at least 64 bytes long
Length field = ?
7
IEEE 802.3 – Frame Structure (2)
802.3 MAC Frame
7
Preamble
1
SD
2 or 6
Destination
Address
Source/Destination Address:
Types of Addresses:
1
2 or 6
Source
Address
2
Length
4 (bytes)
Information
Pad
FCS
6 octets (or 48 bytes) are always used
47 bits
Single address
0
1
47 bits
Group address
1
1
46 bits
0
Local address
1
46 bits
1
Global address
Unicast addressing based on NIC card
Multicast addressing to identify groups
111 … 1 = broadcast to all stations
Machine addressed is on the local network
Machine addressed is outside the local network
8
IEEE 802.3 – Frame Structure (3)
802.3 MAC Frame
7
Preamble
1
SD
2 or 6
Destination
Address
Source/Destination Address:
Types of Addresses:
1
1
24 bits
22 bits
Vendor
Address
2 or 6
Source
Address
2
Length
4 (bytes)
Information
Pad
FCS
6 octets (or 48 bytes) are always used
First 24 bits are specified by the vendor
CISCO = (00000C)16; 3Comm = (02608C)16
FCS:
Frame Check Sum
Based on CCITT 32-bit CRC code
Structure of DIX Ethernet Frame is same as IEEE 802.3 frame except for the length bytes.
In DIX Ethernet Frame, length field is replaced by type field
Value of type field > (0600)16
9
IEEE 802.3 – Physical Layer (1)

Physical layers defined by the IEEE 802.3 Standard
10Base5
Medium
10Base2
10BaseT
10BaseF
Thick Coaxial
Thin Coaxial
Twisted Pair
Optical Fiber
500m
185m
100m
2km
Topology
Bus
Bus
Star
Point to Point
Data Rate
10Mbps
10Mbps
10Mbps
10Mbps
Segment length
(max)
Miscellaneous
Transceiver
needed to
attach NIC
card to coax
T-shaped BNC
junctions used
Twisted pair
connects NIC
card to hub
responsible for
comm.
10
IEEE 802.3 – Physical Layer (2)

10Base5
transceiver

10Base2
11
IEEE 802.3 – Physical Layer (3)

10 Base T
Single collision domain
High-Speed Backplane or
Interconnection fabric
     




Read more about Fast and Gigabit Ethernet ….
12
IEEE 802.5 - History
Set of protocols at the physical and data link layer (MAC sublayer)
Developed by IBM in 1980s
IEEE 802.5 standard modeled after IBM Token Ring in 1990s
IBM and IEEE specifications differ in minor ways:
 IBM’s Token Ring specifies a star; IEEE 802.5 does not specify a topology but most IEEE
802.5 implementations are based on a star
 IBM’s Token Ring uses twisted-pair wire; IEEE 802.5 does not specify a media type
Speed: 4 Mbps and 16 Mbps
Signalling: Differential Manchester
Size: max 250 stations
13
IEEE 802.5: Token Ring
Token Passing Systems: decenteralized approach with no central controller
 In ring topology, each station is connected in a ring using an interface

Interface operates in two modes
listen mode
input
from
ring
delay
transmit mode
output
to
ring
delay
to device
from device
14
MAC Scheduling Approaches: Token Ring (2)

Interface operates in two modes
listen mode
input
from
ring
delay
transmit mode
output
to
ring
delay
to device
1. Each bit is reproduced on the ring with a delay
2. Delay is a multiple of (one bit duration)
3. Delay allows to check for certain bit patterns
from device
1. Station transmits a message bit by bit on ring
2. Station receives a message bit by bit from ring
3. No forwarding of bits is done
15
MAC Scheduling Approaches: Token Ring (3)

When no station is transmitting, there is a free token floating on the ring
Token Frame Format
Starting delimiter
J K 0 J K 0
Access control
PPP
Ending delimiter

SD
T
M
ED
AC
0
0
J, K non-data symbols (line code)
PPP Priority; T Token bit
M Monitor bit; RRR Reservation
RRR
J K 1 J K 1
I
E
I
E
intermediate-frame bit
error-detection bit
When a free token is received (T = 0), the interface changes the passing token bit (T = 1) and
starts transmitting
16
MAC Scheduling Approaches: Token Ring (4)

When a free token is received (T = 0), the interface changes the passing token bit
(T = 1) and starts transmitting
Data Frame Format
1
1
1
SD


AC
FC
2 or 6
Destination
Address
2 or 6
Source
Address
4
Information
FCS
1
ED
1
FS
Each transmitted bit is removed by the destination station or by the source station
After the transmission is complete, the source station inserts the free token back onto the ring
with (T = 0)
Token Frame Format
Access control
PPP
T
M
SD
RRR
AC
ED
PPP Priority; T Token bit
M Monitor bit; RRR Reservation
17
MAC Scheduling Approaches: Token Ring (5)
Ring Latency: Maximum number of bits in transition around the ring
 If frame size > ring latency, a complete frame cannot be present on the ring at one time
 If frame size < ring latency, complete frame is on transition in the ring.
Ring Latency (t’) in seconds = t + Mb/R
Ring Latency in bits = (t + Mb/R)R
where t is total propagation delay around the ring, M is the number of stations in the ring, b is the
number of bit-delays in an interface.
Approaches to Token Reinsertion:
1. Single token operation (delayed token release): in which the token is released only after a
complete frame is received by the transmitting station. Suitable when frame size is nearly
equal to ring latency.
2. Multiple token operation (early token release): in which token is released after the
transmission of a frame is completed by the transmitting station. Suitable when frame size is
less than ring latency.
18
MAC Scheduling Approaches: Token Ring vs Token Bus
1.
2.
3.
4.
Cost : Ethernet is generally less expensive and easier to install than Token Ring .
Stability : Token Ring is generally more secure and more stable than Ethernet.
Scalability : It is usually more difficult to add more computers on a Token Ring LAN than it is
to an Ethernet LAN. However, as additional computers are added, performance degradation
will be less pronounced on the Token Ring LAN than it will be on the Ethernet LAN.
QoS : Ethernet uses CSMA/CD media access control and Token Ring uses token passing. This
makes Ethernet better suited in a situation where there are a large number of computers
sending fewer, larger data frames. Token Ring is better suited for small to medium size LANs
sending many, smaller data frames.
19