Transcript Topic 15 - Electrical and Computer Engineering

Telecommunications Networking II
Topic 15
Local Area Networks
[Ref: “Computer Networks” A.S. Tanenbaum]
Dr. Stewart D. Personick
Drexel University
Copyright 2002, S.D. Personick. All Rights Reserved.
1
Local Area Networks
• LAN Overview
• Link Layer- packet error control and
media access (coordination) protocols
• Network Layer: addressing and routing
protocols
• Higher layer protocols
• Examples of LAN standards: Ethernet, token
ring
Copyright 2002, S.D. Personick. All Rights Reserved.
2
What are we trying to do?
• We are trying to create a local
communications infrastructure which will
allow computing appliances to exchange data
in the form of packet data units (packets)
• We want this local communications
infrastructure to be low in cost, and easy to
implement and maintain
Copyright 2002, S.D. Personick. All Rights Reserved.
3
A typical packet
Payload: 64-to-2048 bytes
Header
Header contains: source address, destination
address, special handling requirements, packet
sequence number, information about packet history,
error control bytes, ...
Copyright 2002, S.D. Personick. All Rights Reserved.
4
What are we trying to do?
(cont’d)
• We would like our local communication
infrastructure to employ “open” interfaces at
appropriate points, so that portions of it can
be provided by different suppliers; and so that
we can accommodate multiple types of
physical layer transmission media: wires,
coaxial cable, fiber, wireless
• We would like our local communication
infrastructure to support a wide range of
applications
Copyright 2002, S.D. Personick. All Rights Reserved.
5
Issues we need to address
• When packet data units (PDU’s) are
transmitted across a physical medium (e.g.,
wire pairs), errors may occur
• We need to coordinate the actions of multiple
computing devices that may wish to send
PDU’s over the same medium
• We need a way to identify the intended
recipient(s) of a PDU
Copyright 2002, S.D. Personick. All Rights Reserved.
6
Issues we need to address
• We need to deal with the possibility that
PDU’s may be inadvertently lost, duplicated,
or delivered out of the order in which they
were sent
• We need to deal with the possibility that some
PDU’s may require expedited delivery
• We need to manage congestion when more
PDU’s are being sent than the network can
accommodate
Copyright 2002, S.D. Personick. All Rights Reserved.
7
“Higher Layer Issues”
• We need a methodology that enables
computing appliances to inform each other of
their desire to communicate (establish a
“session”), and to accept or decline such
communication
• We may need to provide mechanisms for
“secure” communication
• We may need to provide mechanisms which
enable different higher layer protocols to
inter-operate (e.g., converting text to speech)
Copyright 2002, S.D. Personick. All Rights Reserved.
8
The ISO-OSI Protocol Stack
Application Layer (e.g., E-mail or WWW)
Presentation Layer (e.g., Microsoft Word, plain text)
Session Layer (e.g., accepting or denying access)
Transport Layer (e.g., asking for retransmission of lost
packets; re-ordering packets that are out of order)
Network Layer (reading addresses and directing
packets toward their intended destinations)
Link Layer (coordinating access to the physical
medium, and trying to move packets across the
physical medium without making errors)
Physical layer (e.g., wire pairs or fiber or wireless)
Copyright 2002, S.D. Personick. All Rights Reserved.
9
Separation of Concerns
Each layer in the protocol stack should
be able to use the services of the
layer(s) below it, without having to be
concerned with the details of how those
services are implemented.
For example, the transport layer should
not be concerned with, or dependent
upon the details of how the network
layer manages to get the right packets to
the right destinations
Copyright 2002, S.D. Personick. All Rights Reserved.
10
What each layer does
• The engineers who design physical layer (e.g.
wireless) solutions focus on the problems of
moving bits (1’s and 0’s) across their physical
layer... with a specified probability of error, a
specified data rate capability, and specified
delay characteristics. E.g., wireless physical
layer designers worry about the stuff we
discussed in previous topics
Copyright 2002, S.D. Personick. All Rights Reserved.
11
What each layer does (cont’d)
• The engineers who design (and agree on standards
for) link layer protocols are concerned with:
- how to detect errors that occur when PDU’s are
communicated across a physical layer; and how such
detected errors might also be corrected (error
detecting codes, error correcting codes,
retransmission)
-how to coordinate access to the physical layer by
multiple computing appliances which are using the
same physical layer medium at the same time
(“media access control”)
Copyright 2002, S.D. Personick. All Rights Reserved.
12
What each layer does (cont’d)
• Engineers who design (and agree on standards for)
network layer protocols are concerned with:
-how destination addresses (and possibly specific
routing requests) are incorporated into PDU’s
-how routers (network packet switches) coordinate to
establish routes over which packets can be moved
toward their intended destinations
-how requests to reserve network capacity are
specified and accepted (or denied)
Copyright 2002, S.D. Personick. All Rights Reserved.
13
What each layer does (cont’d)
• Engineers who design (and agree on standards for)
transport layer protocols are concerned with
-how to ensure end-to-end PDU transport integrity by:
detecting lost or duplicated packets; requesting
retransmissions of lost packets; re-ordering packets
that are received out-of-order; adjusting the rate at
which packets are sent across the network to
accommodate congestion and other problems;
storing packets for retransmission or initial
transmission, if required.
Copyright 2002, S.D. Personick. All Rights Reserved.
14
The protocol “hour glass”
E-mail, WWW,
Telephony, ...
TCP, UDP
IP
Fewer is better:
Token ring (802.5)
Ethernet (802.3)
HDLC
Wire pairs, Fiber, Coax, Wireless, ...
Copyright 2002, S.D. Personick. All Rights Reserved.
15
HDLC
(see Tanenbaum pp 175-239)
01111110 | Address | Control | Data | Checksum | 01111110
8
8
8
> or = 0
16
Copyright 2002, S.D. Personick. All Rights Reserved.
8
16
HDLC
Each packet data unit (frame) includes a “cyclic redundancy check”
(CDC) sequence that allows for the detection of most single or multiple
bit errors. Frames with detected errors are discarded.
The header of each frame also includes a “frame sequence
number” that is typically between 0-7, but could be between 0 and
(2**n)-1, where n is between 3 and 7
Frames are acknowledged after they are correctly received
The maximum number of outstanding, unacknowledged frames
is: (2**n) -1 (e.g., 7 )
Retransmission is used to replace unacknowledged or rejected frames
Copyright 2002, S.D. Personick. All Rights Reserved.
17
HDLC
2
1
0
Frames (includes
retransmissions)
NR=3*
Acknowledgements
*NR=3 indicates that the next expected
frame sequence number = 3
Copyright 2002, S.D. Personick. All Rights Reserved.
18
Cyclic Redundancy Check
Examples of error detection methods:
Parity bit = sum of the binary digits in the part of the
packet you want to protect ( modulo 2). A single bit
error causes the parity bit not to match the parity
calculated at the receiver
CRC-16 or CRC-32: Divide (modulo 2) the data field
by a binary polynomial with either 2**16 or 2**32 as its
most significant bit. The CRC is the remainder
Copyright 2002, S.D. Personick. All Rights Reserved.
19
Cyclic Redundancy Check
(cont’d)
Example: At the transmitter….
Data sequence to be protected is: (4 byte
example)….
10110111 00001001 11011010 11100110= DS
Polynomial is: CRC- CCITT (16 bit CRC):
10001000000100001= P
Divide DS 00000000 00000000 by P (modulo 2); the
remainder is the CRC
Copyright 2002, S.D. Personick. All Rights Reserved.
20
CRC (binary long division, modulo 2)
10001000000100001 | 101
101101110000100111011010111001100000000000000000
10001000000100001
_______________
01111110001100101
(First remainder + next digit)
00000000000000000
_______________
11111100011001010
(Second remainder + next digit)
10001000000100001
Copyright 2002, S.D. Personick. All Rights Reserved.
21
Cyclic Redundancy Check
(cont’d)
Append CRC (remainder) to data being protected:
[DS CRC]
…….
At the receiver... Divide [DS CRC] by P;
The result should be a zero remainder
Copyright 2002, S.D. Personick. All Rights Reserved.
22
Media Access Protocols
• Sharing a physical link among multiple
(simultaneous) users
• Objectives are: to minimize waiting time to
obtain access to a link; to get a high level of
achievable throughput on the link; and to
provide a “fair” sharing of the link capacity
among users. These objectives are
sometimes at odds with each other
Copyright 2002, S.D. Personick. All Rights Reserved.
23
Aloha* Protocol
Transmit your packet, if it gets
through…fine. If it collides with
another packet, then try again.
Used to share links with long end-toend delay (vs. packet duration)
*Early radio network in the Hawaiian Islands
Copyright 2002, S.D. Personick. All Rights Reserved.
24
Aloha Protocol
(with fixed length packets)
N users; each user sending k packets per second;
fixed packet length = T (seconds). Channel bit rate =
B (bits/sec)
The probability that any transmitter packet does NOT
experience a collision= exp [-2(N-1)kT]; I.e. none of
the other N-1 users transmits a packet within T
seconds (before or after) of the time I start sending
my packet.
Throughput = BT x Nk x exp [-2(N-1)kT]
For N>>1, maximum throughput = B/(2e)
Copyright 2002, S.D. Personick. All Rights Reserved.
25
Carrier Sense Multiple Access
A variation on Aloha, where you listen to see if the
“channel” is being used (e.g., listen for a “carrier”)
before transmitting.
If the end-to-end delays are short compared to the
length of a transmitted packet, this can result in
high utilization of the channel
If the point-to-point (through the medium) delay
between users is large compared to the duration of
a transmitted packet, then this becomes the same
as Aloha
Copyright 2002, S.D. Personick. All Rights Reserved.
26
CSMA/CD [IEEE 802.3 (Ethernet)]
CSMA with collision detection
If a collision is detected, the colliding
transmitters “back off” for a randomly selected
amount of time, in order to try to prevent
another collision when they re-transmit
Copyright 2002, S.D. Personick. All Rights Reserved.
27
Token Passing
[IEEE 802.4 (token bus), 802.5 (token ring)]
Each transmitter has an opportunity (a “turn”)
to send packets... defined as holding the
“token”. After a predefined length of time or
number of transmitted packets, it must pass
the token to another transmitter.
Copyright 2002, S.D. Personick. All Rights Reserved.
28
Command/Response [MIL-STD-1553]
Each “remote terminal (RT)” can transmit
(respond) only when instructed (commanded)
to transmit by a designated “bus controller
(BC)”
Copyright 2002, S.D. Personick. All Rights Reserved.
29
Internetworking Protocol (IP)
Networking Layer
Issues are:
Addressing
Creating routing tables (in routers)
Segmentation and re-assembly of IP
packets
Domain name system
Copyright 2002, S.D. Personick. All Rights Reserved.
30
IP Addressing (IPv4)
0-255, 0-255, 0-255, 0-255
4 bytes of address: e.g., 144.128.32.1
Class A: 1 byte network/ 3 bytes subnet
Class B: 2 bytes network/ 2 bytes subnet
Class C: 3 bytes network/ 1 byte subnet
Copyright 2002, S.D. Personick. All Rights Reserved.
31
xxx.Drexel.edu
Routing
yyy.Drexel.edu
Drexel backbone router
ECE.Drexel.edu
local router
MCS.Drexel.edu
Ethernet hub
Source Host
(computer)
local router
Token ring
Destination Host
(computer)
Copyright 2002, S.D. Personick. All Rights Reserved.
32
Setting Up Routing Tables
• Each router (packet switch) communicates
with its neighbors, using a complex protocol
to determine where it should route packets to
• Routing tables are continuously updated
• When an incoming packet arrives, the router
compares the destination address of the
packet to the listings in its routing table to
determine which output to route the packet to
Copyright 2002, S.D. Personick. All Rights Reserved.
33
Domain Name System (DNS)
• The domain name system complements IP
routing by providing a mechanism for
translating domain “names” into numerical IP
addresses:
ece.drexel.edu => 129.25.60.1
[Drexel class B Address . ECE mail server address]
Drexel’s Domain Name System server:
129.26.60.3
(one of several)
Copyright 2002, S.D. Personick. All Rights Reserved.
34
TCP (Transport Layer)
• Keeps track of incoming packets to detect lost
packets
• Stores transmitted packets for possible
retransmission
• Acknowledges (or NACKS) receipt of packets
• Adjusts window size to accommodate end-toend packet loss and delay conditions
Copyright 2002, S.D. Personick. All Rights Reserved.
35
Ethernet Standards (802.3)
see Tanenbaum pp 276-287
• 802.3 is an IEEE standard for the use of
CSMD/CD on a shared medium (e.g.,
coaxial cable, wire pairs cable, fiber
optic cable, wireless)
• “Ethernet” is the commonly used name
for 802.3 LANs; but it really refers to a
specific product that was developed at
Xerox PARC
Copyright 2002, S.D. Personick. All Rights Reserved.
36
802.3 Layer 1
• 802.3 is specified for various types of cable:
-10Base5: Thick coax, 500m per segment*
-10Base2: Thin coax, 200m per segment*
-10BaseT: Twisted pair, 100m per segment
-10BaseF: Fiber optics, 2000m per segment
-higher speed versions of 802.3
*electronic repeaters, bridges or hubs allow
concatenation of segments
Copyright 2002, S.D. Personick. All Rights Reserved.
37
802.3 Layer 1 (cont’d)
• Manchester bipolar coding is used to avoid
ambiguities between 0 volts and a logical “0”,
and also to produce “d.c. balance”, which is
helpful for designing the transceivers that
interface to 802.3 LANs
Binary “1” => high-low (+.85v, -.85v)
Binary “0” => low-high (-.85v, +.85v)
Copyright 2002, S.D. Personick. All Rights Reserved.
38
802.3 Layer 2
Layer 2 frames consist of:
7 bytes of preamble to allow for transceiver
synchronization (10101010 x 7)
1 byte “start of frame” (10101011)
6 byte (48 bit) destination (global) address
6 byte (48 bit) source (global) address
2 byte “length of frame”
Between 0 and 1500 bytes of data
Up to 46 bytes of “pad” (if needed)
4 byte (32 bit) checksum (CRC)
Copyright 2002, S.D. Personick. All Rights Reserved.
39
802.3 Layer 2 (cont’d)
• When a station detects a collision, it sends
out a 48 bit “noise burst” to warn all other
stations
• As per CSMD-CD definition, stations listen
before they transmit. In the event of a
detected collision, stations “back off” and wait
a random amount of time before sending
again. Frames must be longer than 2T, where
T is the maximum 1-way delay. Minimum
frame duration = 51,200 ns
Copyright 2002, S.D. Personick. All Rights Reserved.
40
Token Ring Standards (802.5)
see Tanenbaum pp 292-299
• Physical layer is formed by point-to-point links
between adjacent stations, connected to form
a closed ring
-Each received bit is buffered, examined,
possibly changed, and re-transmitted by each
station
• The token consists of a 3-byte pattern.
Changing one bit of this pattern converts it to
the first 3 bytes of a normal data frame
Copyright 2002, S.D. Personick. All Rights Reserved.
41
802.5 (continued)
• In “listen mode” each node on the ring inserts
1 bit of buffer delay as part of the total delay
around the ring
• In “transmit mode” a node inserts its frames
into the ring, and removes its inserted bits as
they come back around the ring. When
finished transmitting, a transmitter reinserts
the token on to the ring
Copyright 2002, S.D. Personick. All Rights Reserved.
42
802.5 Physical layer
• 1, 4 or 16 Mbps on shielded twisted pairs
• Differential Manchester bipolar coding: +/3.0-4.5 volts
• “Bypass center” (central hub) can be used to
bypass failed nodes (star-shaped ring)
Copyright 2002, S.D. Personick. All Rights Reserved.
43
802.5 Layer 2
• Token holding time is 10 msec (160,000 bits
@ 16 Mbps)
• The data field of a frame has no byte number
limit (except as limited by the allowed token
holding time)
• Frames are acknowledged by the receiving
station by changing a bit in the “frame status”
byte (after the CRC)
Copyright 2002, S.D. Personick. All Rights Reserved.
44
MIL-STD-1553
ref: http://www.ampol-tech.com/what1553.htm
MIL-STD-1553 is a data bus that interconnects up to 31 terminals
(referred to as Remote Terminals, or RT's), controlled by a single
controller unit (referred to as the Bus Controller, or BC). All of the RT's,
and the BC, are connected using two separate busses. These are
named the Primary Bus (or bus 'A') and the Secondary Bus (bus 'B').
Messages are normally transferred only on the primary bus. If a
message fails to be transferred over one bus, transfer may be retried on
the other bus.
An RT is usually a single box, that has some information to send out,
and needs other information to be sent in. (A sensory unit, for example,
would only need to send data out, while a fuel control unit would need to
transfer data in and out.)
Copyright 2002, S.D. Personick. All Rights Reserved.
45
MIL-STD-1553
An RT can send out up to 30 different messages (numbered 1 through
30), and receive up to 30 other messages (also numbered 1 through 30).
The number of the message in an RT is referred to as a Sub Address.
Each message can hold between 1 and 32 data words, 16 bits per word.
An RT sends or receives data only when instructed
to do so by the BC.
Copyright 2002, S.D. Personick. All Rights Reserved.
46
MIL-STD-1553
The role of the bus controller is typically assigned to one of the more
powerful units on the bus (e.g., the mission computer). The BC is the
only entity that can initiate the transfer of a message over the bus. In a
typical MIL-STD-1553 bus, the BC has a predefined sequence of
messages that it repeats indefinitely. This sequence of messages is
referred to as a bus list. The bus list is planned in such a way that it will
cause each message to be transferred over the bus at a rate that is
appropriate for the information that it carries (e.g., a message that
carries information about wing vibrations is transferred a significantly
larger number of times per second, than a message that carries
information about fuel quantity).
Copyright 2002, S.D. Personick. All Rights Reserved.
47
MIL-STD-1553
There are four basic kinds of messages that the BC can cause to be
transferred over the bus. These include RT to RT, RT to BC, BC to RT
and Mode Commands. In an RT to RT message, the BC instructs one
RT to be prepared to receive a certain number of words into one of its
sub addresses, and then instructs another RT to send that number of
data words from one of its sub addresses. Both RT's are ignorant of
each other. All they concern themselves with are commands from the
BC. In an RT to BC message, the BC instructs an RT to transmit a
certain number of data words from one of its sub addresses, and then
reads the data words that the RT transmits. In a BC to RT message, the
BC instructs an RT to be prepared to receive a certain number of data
words, and then transmits that number of data words to the RT.
Mode Command messages are used for management of the bus.
Copyright 2002, S.D. Personick. All Rights Reserved.
48