yes.yarmouky.com fb.com/groups/yes.

yu
William Stallings
Data and Computer
Communications
7th Edition

Chapter 1
Data Communications and
Networks Overview
A Communications Model
• Source
—generates data to be transmitted
• Transmitter
—Converts data into transmittable signals
• Transmission System
—Carries data
• Receiver
—Converts received signal into data
• Destination
—Takes incoming data
Communications Tasks
Transmission system utilization Addressing

Interfacing Routing

Signal generation Recovery

Synchronization Message formatting

Exchange management Security

Error detection and correction Network management

Flow control
Simplified Communications
Model - Diagram
Simplified Data
Communications Model
Networking
• Point to point communication not usually
practical
—Devices are too far apart
—Large set of devices would need impractical number
of connections
• Solution is a communications network
—Wide Area Network (WAN)
—Local Area Network (LAN)
Wide Area Networks
• Large geographical area
• Crossing public rights of way
• Rely in part on common carrier circuits
• Alternative technologies
—Circuit switching
—Packet switching
—Frame relay
—Asynchronous Transfer Mode (ATM)
Circuit Switching
• Dedicated communications path established for
the duration of the conversation
• e.g. telephone network
Packet Switching
• Data sent out of sequence
• Small chunks (packets) of data at a time
• Packets passed from node to node between
source and destination
• Used for terminal to computer and computer to
computer communications
Frame Relay
• Packet switching systems have large overheads
to compensate for errors
• Modern systems are more reliable
• Errors can be caught in end system
• Most overhead for error control is stripped out
Asynchronous Transfer Mode
• ATM
• Evolution of frame relay
• Little overhead for error control
• Fixed packet (called cell) length
• Anything from 10Mbps to Gbps
• Constant data rate using packet switching
technique
Local Area Networks
• Smaller scope
—Building or small campus
• Usually owned by same organization as
attached devices
• Data rates much higher
• Usually broadcast systems
• Now some switched systems and ATM are being
introduced
LAN Configurations
• Switched
—Switched Ethernet
• May be single or multiple switches
—ATM LAN
—Fibre Channel
• Wireless
—Mobility
—Ease of installation
Metropolitan Area Networks
• MAN
• Middle ground between LAN and WAN
• Private or public network
• High speed
• Large area
Networking
Configuration
Further Reading
• Stallings, W. [2003] Data and Computer
Communications (7th edition), Prentice Hall,
Upper Saddle River NJ, chapter 1
• Web site for Stallings book
—http://williamstallings.com/DCC7e.html
William Stallings
Data and Computer
Communications
7th Edition

Chapter 2
Protocols and Architecture
Need For Protocol Architecture
• E.g. File transfer
—Source must activate comms. Path or inform network
of destination
—Source must check destination is prepared to receive
—File transfer application on source must check
destination file management system will accept and
store file for his user
—May need file format translation
• Task broken into subtasks
• Implemented separately in layers in stack
• Functions needed in both systems
• Peer layers communicate
Key Elements of a Protocol
• Syntax
—Data formats
—Signal levels
• Semantics
—Control information
—Error handling
• Timing
—Speed matching
—Sequencing
Protocol Architecture
• Task of communication broken up into modules
• For example file transfer could use three
modules
—File transfer application
—Communication service module
—Network access module
Simplified File Transfer
Architecture
A Three Layer Model
• Network Access Layer
• Transport Layer
• Application Layer
Network Access Layer
• Exchange of data between the computer and
the network
• Sending computer provides address of
destination
• May invoke levels of service
• Dependent on type of network used (LAN,
packet switched etc.)
Transport Layer
• Reliable data exchange
• Independent of network being used
• Independent of application
Application Layer
• Support for different user applications
• e.g. e-mail, file transfer
Protocol Architectures and
Networks
Addressing Requirements
• Two levels of addressing required
• Each computer needs unique network address
• Each application on a (multi-tasking) computer
needs a unique address within the computer
—The service access point or SAP
—The port on TCP/IP stacks
Protocols in Simplified
Architecture
Protocol Data Units (PDU)
• At each layer, protocols are used to
communicate
• Control information is added to user data at
each layer
• Transport layer may fragment user data
• Each fragment has a transport header added
—Destination SAP
—Sequence number
—Error detection code
• This gives a transport protocol data unit
Protocol Data Units
Network PDU
• Adds network header
—network address for destination computer
—Facilities requests
Operation of a Protocol
Architecture
Standardized Protocol
Architectures
• Required for devices to communicate
• Vendors have more marketable products
• Customers can insist on standards based
equipment
• Two standards:
—OSI Reference model
• Never lived up to early promises
—TCP/IP protocol suite
• Most widely used
• Also: IBM Systems Network Architecture (SNA)
OSI
• Open Systems Interconnection
• Developed by the International Organization for
Standardization (ISO)
• Seven layers
• A theoretical system delivered too late!
• TCP/IP is the de facto standard
OSI - The Model
• A layer model
• Each layer performs a subset of the required
communication functions
• Each layer relies on the next lower layer to
perform more primitive functions
• Each layer provides services to the next higher
layer
• Changes in one layer should not require
changes in other layers
OSI Layers
The OSI Environment
OSI as Framework for
Standardization
Layer Specific Standards
Elements of Standardization
• Protocol specification
—Operates between the same layer on two systems
—May involve different operating system
—Protocol specification must be precise
• Format of data units
• Semantics of all fields
• allowable sequence of PCUs
• Service definition
—Functional description of what is provided
• Addressing
—Referenced by SAPs
Service Primitives and
Parameters
• Services between adjacent layers expressed in
terms of primitives and parameters
• Primitives specify function to be performed
• Parameters pass data and control info
Primitive Types
REQUEST A primitive issued by a service user to invoke some
service and to pass the parameters needed to
specify fully the requested service
INDICATION A primitive issued by a service provider either to:
indicate that a procedure has been invoked by the
peer service user on the connection and to provide
the associated parameters, or
notify the service user of a provider-initiated action
RESPONSE A primitive issued by a service user to acknowledge
or complete some procedure previously invoked by
an indication to that user
CONFIRM A primitive issued by a service provider to
acknowledge or complete some procedure
previously invoked by a request by the service user
Timing Sequence for Service
Primitives
OSI Layers (1)
• Physical
—Physical interface between devices
• Mechanical
• Electrical
• Functional
• Procedural
• Data Link
—Means of activating, maintaining and deactivating a
reliable link
—Error detection and control
—Higher layers may assume error free transmission
OSI Layers (2)
• Network
— Transport of information
— Higher layers do not need to know about underlying technology
— Not needed on direct links
• Transport
— Exchange of data between end systems
— Error free
— In sequence
— No losses
— No duplicates
— Quality of service
OSI Layers (3)
• Session
—Control of dialogues between applications
—Dialogue discipline
—Grouping
—Recovery
• Presentation
—Data formats and coding
—Data compression
—Encryption
• Application
—Means for applications to access OSI environment
Use of a Relay
TCP/IP Protocol Architecture
• Developed by the US Defense Advanced
Research Project Agency (DARPA) for its packet
switched network (ARPANET)
• Used by the global Internet
• No official model but a working one.
—Application layer
—Host to host or transport layer
—Internet layer
—Network access layer
—Physical layer
Physical Layer
• Physical interface between data transmission
device (e.g. computer) and transmission
medium or network
• Characteristics of transmission medium
• Signal levels
• Data rates
• etc.
Network Access Layer
• Exchange of data between end system and
network
• Destination address provision
• Invoking services like priority
Internet Layer (IP)
• Systems may be attached to different networks
• Routing functions across multiple networks
• Implemented in end systems and routers
Transport Layer (TCP)
• Reliable delivery of data
• Ordering of delivery
Application Layer
• Support for user applications
• e.g. http, SMPT
OSI v TCP/IP
TCP
• Usual transport layer is Transmission Control Protocol
— Reliable connection
• Connection
— Temporary logical association between entities in different
systems
• TCP PDU
— Called TCP segment
— Includes source and destination port (c.f. SAP)
• Identify respective users (applications)
• Connection refers to pair of ports
• TCP tracks segments between entities on each
connection
UDP
• Alternative to TCP is User Datagram Protocol
• Not guaranteed delivery
• No preservation of sequence
• No protection against duplication
• Minimum overhead
• Adds port addressing to IP
TCP/IP Concepts
Addressing level
• Level in architecture at which entity is named
• Unique address for each end system (computer)
and router
• Network level address
—IP or internet address (TCP/IP)
—Network service access point or NSAP (OSI)
• Process within the system
—Port number (TCP/IP)
—Service access point or SAP (OSI)
Trace of Simple Operation
• Process associated with port 1 in host A sends
message to port 2 in host B
• Process at A hands down message to TCP to
send to port 2
• TCP hands down to IP to send to host B
• IP hands down to network layer (e.g. Ethernet)
to send to router J
• Generates a set of encapsulated PDUs
PDUs in TCP/IP
Example Header Information
• Destination port
• Sequence number
• Checksum
Some Protocols in TCP/IP Suite
Required Reading
• Stallings chapter 2
• Comer,D. Internetworking with TCP/IP volume I
• Comer,D. and Stevens,D. Internetworking with
TCP/IP volume II and volume III, Prentice Hall
• Halsall, F. Data Communications, Computer
Networks and Open Systems, Addison Wesley
• RFCs
William Stallings
Data and Computer
Communications
7th Edition

Chapter 3
Data Transmission
Terminology (1)
• Transmitter
• Receiver
• Medium
—Guided medium
• e.g. twisted pair, optical fiber
—Unguided medium
• e.g. air, water, vacuum
Terminology (2)
• Direct link
—No intermediate devices
• Point-to-point
—Direct link
—Only 2 devices share link
• Multi-point
—More than two devices share the link
Terminology (3)
• Simplex
—One direction
• e.g. Television
• Half duplex
—Either direction, but only one way at a time
• e.g. police radio
• Full duplex
—Both directions at the same time
• e.g. telephone
Frequency, Spectrum and
Bandwidth
• Time domain concepts
—Analog signal
• Various in a smooth way over time
—Digital signal
• Maintains a constant level then changes to another constant
level
—Periodic signal
• Pattern repeated over time
—Aperiodic signal
• Pattern not repeated over time
Analogue & Digital Signals
Periodic
Signals
Sine Wave
• Peak Amplitude (A)
—maximum strength of signal
—volts
• Frequency (f)
—Rate of change of signal
—Hertz (Hz) or cycles per second
—Period = time for one repetition (T)
—T = 1/f
• Phase (φ)
—Relative position in time
Varying Sine Waves
s(t) = A sin(2πft +Φ)
Wavelength
• Distance occupied by one cycle
• Distance between two points of corresponding
phase in two consecutive cycles
• λ
• Assuming signal velocity v
— λ = vT
— λf = v
—c = 3*108 ms-1 (speed of light in free space)
Frequency Domain Concepts
• Signal usually made up of many frequencies
• Components are sine waves
• Can be shown (Fourier analysis) that any signal
is made up of component sine waves
• Can plot frequency domain functions
Addition of
Frequency
Components
(T=1/f)
Frequency
Domain
Representations
Spectrum & Bandwidth
• Spectrum
—range of frequencies contained in signal
• Absolute bandwidth
—width of spectrum
• Effective bandwidth
—Often just bandwidth
—Narrow band of frequencies containing most of the
energy
• DC Component
—Component of zero frequency
Signal with DC Component
Data Rate and Bandwidth
• Any transmission system has a limited band of
frequencies
• This limits the data rate that can be carried
Analog and Digital Data
Transmission
• Data
—Entities that convey meaning
• Signals
—Electric or electromagnetic representations of data
• Transmission
—Communication of data by propagation and
processing of signals
Analog and Digital Data
• Analog
—Continuous values within some interval
—e.g. sound, video
• Digital
—Discrete values
—e.g. text, integers
Acoustic Spectrum (Analog)
Analog and Digital Signals
• Means by which data are propagated
• Analog
—Continuously variable
—Various media
• wire, fiber optic, space
—Speech bandwidth 100Hz to 7kHz
—Telephone bandwidth 300Hz to 3400Hz
—Video bandwidth 4MHz
• Digital
—Use two DC components
Advantages & Disadvantages
of Digital
• Cheaper
• Less susceptible to noise
• Greater attenuation
—Pulses become rounded and smaller
—Leads to loss of information
Attenuation of Digital Signals
Components of Speech
• Frequency range (of hearing) 20Hz-20kHz
—Speech 100Hz-7kHz
• Easily converted into electromagnetic signal for
transmission
• Sound frequencies with varying volume
converted into electromagnetic frequencies with
varying voltage
• Limit frequency range for voice channel
—300-3400Hz
Conversion of Voice Input into
Analog Signal
Video Components
• USA - 483 lines scanned per frame at 30 frames per
second
— 525 lines but 42 lost during vertical retrace
• So 525 lines x 30 scans = 15750 lines per second
— 63.5µs per line
— 11µs for retrace, so 52.5 µs per video line
• Max frequency if line alternates black and white
• Horizontal resolution is about 450 lines giving 225 cycles
of wave in 52.5 µs
• Max frequency of 4.2MHz
Binary Digital Data
• From computer terminals etc.
• Two dc components
• Bandwidth depends on data rate
Conversion of PC Input to
Digital Signal
Data and Signals
• Usually use digital signals for digital data and
analog signals for analog data
• Can use analog signal to carry digital data
—Modem
• Can use digital signal to carry analog data
—Compact Disc audio
Analog Signals Carrying Analog
and Digital Data
Digital Signals Carrying Analog
and Digital Data
Analog Transmission
• Analog signal transmitted without regard to
content
• May be analog or digital data
• Attenuated over distance
• Use amplifiers to boost signal
• Also amplifies noise
Digital Transmission
• Concerned with content
• Integrity endangered by noise, attenuation etc.
• Repeaters used
• Repeater receives signal
• Extracts bit pattern
• Retransmits
• Attenuation is overcome
• Noise is not amplified
Advantages of Digital
Transmission
• Digital technology
— Low cost LSI/VLSI technology
• Data integrity
— Longer distances over lower quality lines
• Capacity utilization
— High bandwidth links economical
— High degree of multiplexing easier with digital techniques
• Security & Privacy
— Encryption
• Integration
— Can treat analog and digital data similarly
Transmission Impairments
• Signal received may differ from signal
transmitted
• Analog - degradation of signal quality
• Digital - bit errors
• Caused by
—Attenuation and attenuation distortion
—Delay distortion
—Noise
Attenuation
• Signal strength falls off with distance
• Depends on medium
• Received signal strength:
—must be enough to be detected
—must be sufficiently higher than noise to be received
without error
• Attenuation is an increasing function of
frequency
Delay Distortion
• Only in guided media
• Propagation velocity varies with frequency
Noise (1)
• Additional signals inserted between transmitter
and receiver
• Thermal
—Due to thermal agitation of electrons
—Uniformly distributed
—White noise
• Intermodulation
—Signals that are the sum and difference of original
frequencies sharing a medium
Noise (2)
• Crosstalk
—A signal from one line is picked up by another
• Impulse
—Irregular pulses or spikes
—e.g. External electromagnetic interference
—Short duration
—High amplitude
Channel Capacity
• Data rate
—In bits per second
—Rate at which data can be communicated
• Bandwidth
—In cycles per second of Hertz
—Constrained by transmitter and medium
Nyquist Bandwidth
• If rate of signal transmission is 2B then signal
with frequencies no greater than B is sufficient
to carry signal rate
• Given bandwidth B, highest signal rate is 2B
• Given binary signal, data rate supported by B Hz
is 2B bps
• Can be increased by using M signal levels
• C= 2B log2M
Shannon Capacity Formula
• Consider data rate,noise and error rate
• Faster data rate shortens each bit so burst of
noise affects more bits
—At given noise level, high data rate means higher
error rate
• Signal to noise ration (in decibels)
• SNRdb=10 log10 (signal/noise)
• Capacity C=B log2(1+SNR)
• This is error free capacity
Required Reading
• Stallings chapter 3
William Stallings
Data and Computer
Communications
7th Edition

Chapter 4
Transmission Media
Overview
• Guided - wire
• Unguided - wireless
• Characteristics and quality determined by
medium and signal
• For guided, the medium is more important
• For unguided, the bandwidth produced by the
antenna is more important
• Key concerns are data rate and distance
Design Factors
• Bandwidth
—Higher bandwidth gives higher data rate
• Transmission impairments
—Attenuation
• Interference
• Number of receivers
—In guided media
—More receivers (multi-point) introduce more
attenuation
Electromagnetic Spectrum
Guided Transmission Media
• Twisted Pair
• Coaxial cable
• Optical fiber
 Transmission Characteristics of
Guided Media

Frequency Typical Typical Repeater

Range Attenuation Delay Spacing
Twisted pair 0 to 3.5 kHz 0.2 dB/km @ 50 µs/km 2 km
(with loading) 1 kHz

Twisted pairs 0 to 1 MHz 0.7 dB/km @ 5 µs/km 2 km

(multi-pair 1 kHz
cables)
Coaxial cable 0 to 500 MHz 7 dB/km @ 10 4 µs/km 1 to 9 km
MHz
Optical fiber 186 to 370 0.2 to 0.5 5 µs/km 40 km
THz dB/km
Twisted Pair
Twisted Pair - Applications
• Most common medium
• Telephone network
—Between house and local exchange (subscriber loop)
• Within buildings
—To private branch exchange (PBX)
• For local area networks (LAN)
—10Mbps or 100Mbps
Twisted Pair - Pros and Cons
• Cheap
• Easy to work with
• Low data rate
• Short range
Twisted Pair - Transmission
Characteristics
• Analog
—Amplifiers every 5km to 6km
• Digital
—Use either analog or digital signals
—repeater every 2km or 3km
• Limited distance
• Limited bandwidth (1MHz)
• Limited data rate (100MHz)
• Susceptible to interference and noise
Near End Crosstalk
• Coupling of signal from one pair to another
• Coupling takes place when transmit signal
entering the link couples back to receiving pair
• i.e. near transmitted signal is picked up by near
receiving pair
Unshielded and Shielded TP
• Unshielded Twisted Pair (UTP)
—Ordinary telephone wire
—Cheapest
—Easiest to install
—Suffers from external EM interference
• Shielded Twisted Pair (STP)
—Metal braid or sheathing that reduces interference
—More expensive
—Harder to handle (thick, heavy)
UTP Categories
• Cat 3
— up to 16MHz
— Voice grade found in most offices
— Twist length of 7.5 cm to 10 cm
• Cat 4
— up to 20 MHz
• Cat 5
— up to 100MHz
— Commonly pre-installed in new office buildings
— Twist length 0.6 cm to 0.85 cm
• Cat 5E (Enhanced) –see tables
• Cat 6
• Cat 7
 Comparison of Shielded and
Unshielded Twisted Pair
Attenuation (dB per 100 m) Near-end Crosstalk (dB)

Frequency Category 3 Category 5 150-ohm Category 3 Category 5 150-ohm

(MHz) UTP UTP STP UTP UTP STP

1 2.6 2.0 1.1 41 62 58

4 5.6 4.1 2.2 32 53 58

16 13.1 8.2 4.4 23 44 50.4

25 — 10.4 6.2 — 41 47.5

100 — 22.0 12.3 — 32 38.5

300 — — 21.4 — — 31.3

 Twisted Pair Categories and
Classes
Category 3 Category 5 Category Category 6 Category 7
Class C Class D 5E Class E Class F

Bandwidth 16 MHz 100 MHz 100 MHz 200 MHz 600 MHz

Cable Type UTP UTP/FTP UTP/FTP UTP/FTP SSTP

Link Cost 0.7 1 1.2 1.5 2.2

(Cat 5 =1)
Coaxial Cable
Coaxial Cable Applications
• Most versatile medium
• Television distribution
—Ariel to TV
—Cable TV
• Long distance telephone transmission
—Can carry 10,000 voice calls simultaneously
—Being replaced by fiber optic
• Short distance computer systems links
• Local area networks
Coaxial Cable - Transmission
Characteristics
• Analog
—Amplifiers every few km
—Closer if higher frequency
—Up to 500MHz
• Digital
—Repeater every 1km
—Closer for higher data rates
Optical Fiber
Optical Fiber - Benefits
• Greater capacity
—Data rates of hundreds of Gbps
• Smaller size & weight
• Lower attenuation
• Electromagnetic isolation
• Greater repeater spacing
—10s of km at least
Optical Fiber - Applications
• Long-haul trunks
• Metropolitan trunks
• Rural exchange trunks
• Subscriber loops
• LANs
Optical Fiber - Transmission
Characteristics
• Act as wave guide for 1014 to 1015 Hz
—Portions of infrared and visible spectrum
• Light Emitting Diode (LED)
—Cheaper
—Wider operating temp range
—Last longer
• Injection Laser Diode (ILD)
—More efficient
—Greater data rate
• Wavelength Division Multiplexing
Optical Fiber Transmission
Modes
Frequency Utilization for Fiber
Applications
Wavelength (in Frequency Band Fiber type Application
vacuum) range range (THz) label
(nm)

820 to 900 366 to 333 Multimode LAN

1280 to 1350 234 to 222 S Single mode Various

1528 to 1561 196 to 192 C Single mode WDM

1561 to 1620 185 to 192 L Single mode WDM

Attenuation in Guided Media
Wireless Transmission
Frequencies
• 2GHz to 40GHz
—Microwave
—Highly directional
—Point to point
—Satellite
• 30MHz to 1GHz
—Omnidirectional
—Broadcast radio
• 3 x 1011 to 2 x 1014
—Infrared
—Local
Antennas
• Electrical conductor (or system of..) used to radiate
electromagnetic energy or collect electromagnetic
energy
• Transmission
— Radio frequency energy from transmitter
— Converted to electromagnetic energy
— By antenna
— Radiated into surrounding environment
• Reception
— Electromagnetic energy impinging on antenna
— Converted to radio frequency electrical energy
— Fed to receiver
• Same antenna often used for both
Radiation Pattern
• Power radiated in all directions
• Not same performance in all directions
• Isotropic antenna is (theoretical) point in space
—Radiates in all directions equally
—Gives spherical radiation pattern
Parabolic Reflective Antenna
• Used for terrestrial and satellite microwave
• Parabola is locus of point equidistant from a line and a
point not on that line
— Fixed point is focus
— Line is directrix
• Revolve parabola about axis to get paraboloid
— Cross section parallel to axis gives parabola
— Cross section perpendicular to axis gives circle
• Source placed at focus will produce waves reflected
from parabola in parallel to axis
— Creates (theoretical) parallel beam of light/sound/radio
• On reception, signal is concentrated at focus, where
detector is placed
Parabolic Reflective Antenna
Antenna Gain
• Measure of directionality of antenna
• Power output in particular direction compared
with that produced by isotropic antenna
• Measured in decibels (dB)
• Results in loss in power in another direction
• Effective area relates to size and shape
—Related to gain
Terrestrial Microwave
• Parabolic dish
• Focused beam
• Line of sight
• Long haul telecommunications
• Higher frequencies give higher data rates
Satellite Microwave
• Satellite is relay station
• Satellite receives on one frequency, amplifies or
repeats signal and transmits on another
frequency
• Requires geo-stationary orbit
—Height of 35,784km
• Television
• Long distance telephone
• Private business networks
Satellite Point to Point Link
Satellite Broadcast Link
Broadcast Radio
• Omnidirectional
• FM radio
• UHF and VHF television
• Line of sight
• Suffers from multipath interference
—Reflections
Infrared
• Modulate noncoherent infrared light
• Line of sight (or reflection)
• Blocked by walls
• e.g. TV remote control, IRD port
Wireless Propagation
• Signal travels along three routes
— Ground wave
• Follows contour of earth
• Up to 2MHz
• AM radio
— Sky wave
• Amateur radio, BBC world service, Voice of America
• Signal reflected from ionosphere layer of upper atmosphere
• (Actually refracted)
— Line of sight
• Above 30Mhz
• May be further than optical line of sight due to refraction
• More later…
Ground Wave Propagation
Sky Wave Propagation
Line of Sight Propagation
Refraction
• Velocity of electromagnetic wave is a function of density
of material
— ~3 x 108 m/s in vacuum, less in anything else
• As wave moves from one medium to another, its speed
changes
— Causes bending of direction of wave at boundary
— Towards more dense medium
• Index of refraction (refractive index) is
— Sin(angle of incidence)/sin(angle of refraction)
— Varies with wavelength
• May cause sudden change of direction at transition
between media
• May cause gradual bending if medium density is varying
— Density of atmosphere decreases with height
— Results in bending towards earth of radio waves
Optical and Radio Horizons
Line of Sight Transmission
• Free space loss
— Signal disperses with distance
— Greater for lower frequencies (longer wavelengths)
• Atmospheric Absorption
— Water vapour and oxygen absorb radio signals
— Water greatest at 22GHz, less below 15GHz
— Oxygen greater at 60GHz, less below 30GHz
— Rain and fog scatter radio waves
• Multipath
— Better to get line of sight if possible
— Signal can be reflected causing multiple copies to be received
— May be no direct signal at all
— May reinforce or cancel direct signal
• Refraction
— May result in partial or total loss of signal at receiver
Free
Space
Loss
Multipath Interference
Required Reading
• Stallings Chapter 4
William Stallings
Data and Computer
Communications
7th Edition

Chapter 5
Signal Encoding Techniques
Encoding Techniques
• Digital data, digital signal
• Analog data, digital signal
• Digital data, analog signal
• Analog data, analog signal
Digital Data, Digital Signal
• Digital signal
—Discrete, discontinuous voltage pulses
—Each pulse is a signal element
—Binary data encoded into signal elements
Terms (1)
• Unipolar
—All signal elements have same sign
• Polar
—One logic state represented by positive voltage the
other by negative voltage
• Data rate
—Rate of data transmission in bits per second
• Duration or length of a bit
—Time taken for transmitter to emit the bit
Terms (2)
• Modulation rate
—Rate at which the signal level changes
—Measured in baud = signal elements per second
• Mark and Space
—Binary 1 and Binary 0 respectively
Interpreting Signals
• Need to know
—Timing of bits - when they start and end
—Signal levels
• Factors affecting successful interpreting of
signals
—Signal to noise ratio
—Data rate
—Bandwidth
Comparison of Encoding
Schemes (1)
• Signal Spectrum
—Lack of high frequencies reduces required bandwidth
—Lack of dc component allows ac coupling via
transformer, providing isolation
—Concentrate power in the middle of the bandwidth
• Clocking
—Synchronizing transmitter and receiver
—External clock
—Sync mechanism based on signal
Comparison of Encoding
Schemes (2)
• Error detection
—Can be built in to signal encoding
• Signal interference and noise immunity
—Some codes are better than others
• Cost and complexity
—Higher signal rate (& thus data rate) lead to higher
costs
—Some codes require signal rate greater than data rate
Encoding Schemes
• Nonreturn to Zero-Level (NRZ-L)
• Nonreturn to Zero Inverted (NRZI)
• Bipolar -AMI
• Pseudoternary
• Manchester
• Differential Manchester
• B8ZS
• HDB3
Nonreturn to Zero-Level (NRZ-L)
• Two different voltages for 0 and 1 bits
• Voltage constant during bit interval
—no transition I.e. no return to zero voltage
• e.g. Absence of voltage for zero, constant
positive voltage for one
• More often, negative voltage for one value and
positive for the other
• This is NRZ-L
Nonreturn to Zero Inverted
• Nonreturn to zero inverted on ones
• Constant voltage pulse for duration of bit
• Data encoded as presence or absence of signal
transition at beginning of bit time
• Transition (low to high or high to low) denotes a
binary 1
• No transition denotes binary 0
• An example of differential encoding
NRZ
Differential Encoding
• Data represented by changes rather than levels
• More reliable detection of transition rather than
level
• In complex transmission layouts it is easy to
lose sense of polarity
NRZ pros and cons
• Pros
—Easy to engineer
—Make good use of bandwidth
• Cons
—dc component
—Lack of synchronization capability
• Used for magnetic recording
• Not often used for signal transmission
Multilevel Binary
• Use more than two levels
• Bipolar-AMI
—zero represented by no line signal
—one represented by positive or negative pulse
—one pulses alternate in polarity
—No loss of sync if a long string of ones (zeros still a
problem)
—No net dc component
—Lower bandwidth
—Easy error detection
Pseudoternary
• One represented by absence of line signal
• Zero represented by alternating positive and
negative
• No advantage or disadvantage over bipolar-AMI
Bipolar-AMI and Pseudoternary
Trade Off for Multilevel Binary
• Not as efficient as NRZ
—Each signal element only represents one bit
—In a 3 level system could represent log23 = 1.58 bits
—Receiver must distinguish between three levels
(+A, -A, 0)
—Requires approx. 3dB more signal power for same
probability of bit error
Biphase
• Manchester
— Transition in middle of each bit period
— Transition serves as clock and data
— Low to high represents one
— High to low represents zero
— Used by IEEE 802.3
• Differential Manchester
— Midbit transition is clocking only
— Transition at start of a bit period represents zero
— No transition at start of a bit period represents one
— Note: this is a differential encoding scheme
— Used by IEEE 802.5
Manchester Encoding
Differential Manchester
Encoding
Biphase Pros and Cons
• Con
—At least one transition per bit time and possibly two
—Maximum modulation rate is twice NRZ
—Requires more bandwidth
• Pros
—Synchronization on mid bit transition (self clocking)
—No dc component
—Error detection
• Absence of expected transition
Modulation Rate
Scrambling
• Use scrambling to replace sequences that would
produce constant voltage
• Filling sequence
— Must produce enough transitions to sync
— Must be recognized by receiver and replace with original
— Same length as original
• No dc component
• No long sequences of zero level line signal
• No reduction in data rate
• Error detection capability
B8ZS
• Bipolar With 8 Zeros Substitution
• Based on bipolar-AMI
• If octet of all zeros and last voltage pulse
preceding was positive encode as 000+-0-+
• If octet of all zeros and last voltage pulse
preceding was negative encode as 000-+0+-
• Causes two violations of AMI code
• Unlikely to occur as a result of noise
• Receiver detects and interprets as octet of all
zeros
HDB3
• High Density Bipolar 3 Zeros
• Based on bipolar-AMI
• String of four zeros replaced with one or two
pulses
B8ZS and HDB3
Digital Data, Analog Signal
• Public telephone system
—300Hz to 3400Hz
—Use modem (modulator-demodulator)
• Amplitude shift keying (ASK)
• Frequency shift keying (FSK)
• Phase shift keying (PK)
Modulation Techniques
Amplitude Shift Keying
• Values represented by different amplitudes of
carrier
• Usually, one amplitude is zero
—i.e. presence and absence of carrier is used
• Susceptible to sudden gain changes
• Inefficient
• Up to 1200bps on voice grade lines
• Used over optical fiber
Binary Frequency Shift Keying
• Most common form is binary FSK (BFSK)
• Two binary values represented by two different
frequencies (near carrier)
• Less susceptible to error than ASK
• Up to 1200bps on voice grade lines
• High frequency radio
• Even higher frequency on LANs using co-ax
Multiple FSK
• More than two frequencies used
• More bandwidth efficient
• More prone to error
• Each signalling element represents more than
one bit
FSK on Voice Grade Line
Phase Shift Keying
• Phase of carrier signal is shifted to represent
data
• Binary PSK
—Two phases represent two binary digits
• Differential PSK
—Phase shifted relative to previous transmission rather
than some reference signal
Differential PSK
Quadrature PSK
• More efficient use by each signal element
representing more than one bit
—e.g. shifts of π/2 (90o)
—Each element represents two bits
—Can use 8 phase angles and have more than one
amplitude
—9600bps modem use 12 angles , four of which have
two amplitudes
• Offset QPSK (orthogonal QPSK)
—Delay in Q stream
QPSK and OQPSK Modulators
Examples of QPSF and OQPSK
Waveforms
Performance of Digital to
Analog Modulation Schemes
• Bandwidth
—ASK and PSK bandwidth directly related to bit rate
—FSK bandwidth related to data rate for lower
frequencies, but to offset of modulated frequency
from carrier at high frequencies
—(See Stallings for math)
• In the presence of noise, bit error rate of PSK
and QPSK are about 3dB superior to ASK and
FSK
Quadrature Amplitude
Modulation
• QAM used on asymmetric digital subscriber line
(ADSL) and some wireless
• Combination of ASK and PSK
• Logical extension of QPSK
• Send two different signals simultaneously on
same carrier frequency
—Use two copies of carrier, one shifted 90°
—Each carrier is ASK modulated
—Two independent signals over same medium
—Demodulate and combine for original binary output
QAM Modulator
QAM Levels
• Two level ASK
—Each of two streams in one of two states
—Four state system
—Essentially QPSK
• Four level ASK
—Combined stream in one of 16 states
• 64 and 256 state systems have been
implemented
• Improved data rate for given bandwidth
—Increased potential error rate
Analog Data, Digital Signal
• Digitization
—Conversion of analog data into digital data
—Digital data can then be transmitted using NRZ-L
—Digital data can then be transmitted using code other
than NRZ-L
—Digital data can then be converted to analog signal
—Analog to digital conversion done using a codec
—Pulse code modulation
—Delta modulation
Digitizing Analog Data
Pulse Code Modulation(PCM) (1)
• If a signal is sampled at regular intervals at a
rate higher than twice the highest signal
frequency, the samples contain all the
information of the original signal
—(Proof - Stallings appendix 4A)
• Voice data limited to below 4000Hz
• Require 8000 sample per second
• Analog samples (Pulse Amplitude Modulation,
PAM)
• Each sample assigned digital value
Pulse Code Modulation(PCM) (2)
• 4 bit system gives 16 levels
• Quantized
—Quantizing error or noise
—Approximations mean it is impossible to recover
original exactly
• 8 bit sample gives 256 levels
• Quality comparable with analog transmission
• 8000 samples per second of 8 bits each gives
64kbps
PCM Example
PCM Block Diagram
Nonlinear Encoding
• Quantization levels not evenly spaced
• Reduces overall signal distortion
• Can also be done by companding
Effect of Non-Linear Coding
Typical Companding Functions
Delta Modulation
• Analog input is approximated by a staircase
function
• Move up or down one level (δ) at each sample
interval
• Binary behavior
—Function moves up or down at each sample interval
Delta Modulation - example
Delta Modulation - Operation
Delta Modulation - Performance
• Good voice reproduction
—PCM - 128 levels (7 bit)
—Voice bandwidth 4khz
—Should be 8000 x 7 = 56kbps for PCM
• Data compression can improve on this
—e.g. Interframe coding techniques for video
Analog Data, Analog Signals
• Why modulate analog signals?
—Higher frequency can give more efficient transmission
—Permits frequency division multiplexing (chapter 8)
• Types of modulation
—Amplitude
—Frequency
—Phase
Analog
Modulation
Required Reading
• Stallings chapter 5
William Stallings
Data and Computer
Communications
7th Edition

Chapter 6
Digital Data Communications
Techniques
Asynchronous and Synchronous
Transmission
• Timing problems require a mechanism to
synchronize the transmitter and receiver
• Two solutions
—Asynchronous
—Synchronous
Asynchronous
• Data transmitted on character at a time
—5 to 8 bits
• Timing only needs maintaining within each
character
• Resynchronize with each character
Asynchronous (diagram)
Asynchronous - Behavior
• In a steady stream, interval between characters
is uniform (length of stop element)
• In idle state, receiver looks for transition 1 to 0
• Then samples next seven intervals (char length)
• Then looks for next 1 to 0 for next char

• Simple
• Cheap
• Overhead of 2 or 3 bits per char (~20%)
• Good for data with large gaps (keyboard)
Synchronous - Bit Level
• Block of data transmitted without start or stop
bits
• Clocks must be synchronized
• Can use separate clock line
—Good over short distances
—Subject to impairments
• Embed clock signal in data
—Manchester encoding
—Carrier frequency (analog)
Synchronous - Block Level
• Need to indicate start and end of block
• Use preamble and postamble
—e.g. series of SYN (hex 16) characters
—e.g. block of 11111111 patterns ending in 11111110

• More efficient (lower overhead) than async

Synchronous (diagram)
Types of Error
• An error occurs when a bit is altered between
transmission and reception
• Single bit errors
— One bit altered
— Adjacent bits not affected
— White noise
• Burst errors
— Length B
— Contiguous sequence of B bits in which first last and any
number of intermediate bits in error
— Impulse noise
— Fading in wireless
— Effect greater at higher data rates
Error Detection Process
Error Detection
• Additional bits added by transmitter for error
detection code
• Parity
—Value of parity bit is such that character has even
(even parity) or odd (odd parity) number of ones
—Even number of bit errors goes undetected
Cyclic Redundancy Check
• For a block of k bits transmitter generates n bit
sequence
• Transmit k+n bits which is exactly divisible by
some number
• Receive divides frame by that number
—If no remainder, assume no error
—For math, see Stallings chapter 6
Error Correction
• Correction of detected errors usually requires
data block to be retransmitted (see chapter 7)
• Not appropriate for wireless applications
—Bit error rate is high
• Lots of retransmissions
—Propagation delay can be long (satellite) compared
with frame transmission time
• Would result in retransmission of frame in error plus many
subsequent frames
• Need to correct errors on basis of bits received
Error Correction Process
Diagram
Error Correction Process
• Each k bit block mapped to an n bit block (n>k)
— Codeword
— Forward error correction (FEC) encoder
• Codeword sent
• Received bit string similar to transmitted but may
contain errors
• Received code word passed to FEC decoder
— If no errors, original data block output
— Some error patterns can be detected and corrected
— Some error patterns can be detected but not corrected
— Some (rare) error patterns are not detected
• Results in incorrect data output from FEC
Working of Error Correction
• Add redundancy to transmitted message
• Can deduce original in face of certain level of
error rate
• E.g. block error correction code
—In general, add (n – k ) bits to end of block
• Gives n bit block (codeword)
• All of original k bits included in codeword
—Some FEC map k bit input onto n bit codeword such
that original k bits do not appear
• Again, for math, see chapter 6
Line Configuration
• Topology
— Physical arrangement of stations on medium
— Point to point
— Multi point
• Computer and terminals, local area network
• Half duplex
— Only one station may transmit at a time
— Requires one data path
• Full duplex
— Simultaneous transmission and reception between two stations
— Requires two data paths (or echo canceling)
Traditional Configurations
Interfacing
• Data processing devices (or data terminal
equipment, DTE) do not (usually) include data
transmission facilities
• Need an interface called data circuit terminating
equipment (DCE)
—e.g. modem, NIC
• DCE transmits bits on medium
• DCE communicates data and control info with
DTE
—Done over interchange circuits
—Clear interface standards required
Data Communications
Interfacing
Characteristics of Interface
• Mechanical
—Connection plugs
• Electrical
—Voltage, timing, encoding
• Functional
—Data, control, timing, grounding
• Procedural
—Sequence of events
V.24/EIA-232-F
• ITU-T v.24
• Only specifies functional and procedural
—References other standards for electrical and
mechanical
• EIA-232-F (USA)
—RS-232
—Mechanical ISO 2110
—Electrical v.28
—Functional v.24
—Procedural v.24
Mechanical Specification
Electrical Specification
• Digital signals
• Values interpreted as data or control, depending
on circuit
• More than -3v is binary 1, more than +3v is
binary 0 (NRZ-L)
• Signal rate < 20kbps
• Distance <15m
• For control, more than-3v is off, +3v is on
Functional Specification
• Circuits grouped in categories
—Data
—Control
—Timing
—Ground
• One circuit in each direction
—Full duplex
• Two secondary data circuits
—Allow halt or flow control in half duplex operation
• (See table in Stallings chapter 6)
Local and Remote Loopback
Procedural Specification
• E.g. Asynchronous private line modem
• When turned on and ready, modem (DCE) asserts DCE
ready
• When DTE ready to send data, it asserts Request to
Send
— Also inhibits receive mode in half duplex
• Modem responds when ready by asserting Clear to send
• DTE sends data
• When data arrives, local modem asserts Receive Line
Signal Detector and delivers data
Dial Up Operation (1)
Dial Up Operation (2)
Dial Up Operation (3)
Null Modem
ISDN Physical Interface Diagram
ISDN Physical Interface
• Connection between terminal equipment (c.f.
DTE) and network terminating equipment (c.f.
DCE)
• ISO 8877
• Cables terminate in matching connectors with 8
contacts
• Transmit/receive carry both data and control
ISDN Electrical Specification
• Balanced transmission
— Carried on two lines, e.g. twisted pair
— Signals as currents down one conductor and up the other
— Differential signaling
— Value depends on direction of voltage
— Tolerates more noise and generates less
— (Unbalanced, e.g. RS-232 uses single signal line and ground)
— Data encoding depends on data rate
— Basic rate 192kbps uses pseudoternary
— Primary rate uses alternative mark inversion (AMI) and B8ZS or
HDB3
Foreground Reading
• Stallings chapter 6
• Web pages from ITU-T on v. specification
• Web pages on ISDN
William Stallings
Data and Computer
Communications
7th Edition

Chapter 7
Data Link Control Protocols
Flow Control
• Ensuring the sending entity does not overwhelm
the receiving entity
—Preventing buffer overflow
• Transmission time
—Time taken to emit all bits into medium
• Propagation time
—Time for a bit to traverse the link
Model of Frame Transmission
Stop and Wait
• Source transmits frame
• Destination receives frame and replies with
acknowledgement
• Source waits for ACK before sending next frame
• Destination can stop flow by not send ACK
• Works well for a few large frames
Fragmentation
• Large block of data may be split into small
frames
—Limited buffer size
—Errors detected sooner (when whole frame received)
—On error, retransmission of smaller frames is needed
—Prevents one station occupying medium for long
periods
• Stop and wait becomes inadequate
Stop and Wait Link Utilization
Sliding Windows Flow Control
• Allow multiple frames to be in transit
• Receiver has buffer W long
• Transmitter can send up to W frames without
ACK
• Each frame is numbered
• ACK includes number of next frame expected
• Sequence number bounded by size of field (k)
—Frames are numbered modulo 2k
Sliding Window Diagram
Example Sliding Window
Sliding Window Enhancements
• Receiver can acknowledge frames without
permitting further transmission (Receive Not
Ready)
• Must send a normal acknowledge to resume
• If duplex, use piggybacking
—If no data to send, use acknowledgement frame
—If data but no acknowledgement to send, send last
acknowledgement number again, or have ACK valid
flag (TCP)
Error Detection
• Additional bits added by transmitter for error
detection code
• Parity
—Value of parity bit is such that character has even
(even parity) or odd (odd parity) number of ones
—Even number of bit errors goes undetected
Cyclic Redundancy Check
• For a block of k bits transmitter generates n bit
sequence
• Transmit k+n bits which is exactly divisible by
some number
• Receive divides frame by that number
—If no remainder, assume no error
—For math, see Stallings chapter 7
Error Control
• Detection and correction of errors
• Lost frames
• Damaged frames
• Automatic repeat request
—Error detection
—Positive acknowledgment
—Retransmission after timeout
—Negative acknowledgement and retransmission
Automatic Repeat Request
(ARQ)
• Stop and wait
• Go back N
• Selective reject (selective retransmission)
Stop and Wait
• Source transmits single frame
• Wait for ACK
• If received frame damaged, discard it
—Transmitter has timeout
—If no ACK within timeout, retransmit
• If ACK damaged,transmitter will not recognize it
—Transmitter will retransmit
—Receive gets two copies of frame
—Use ACK0 and ACK1
Stop and Wait -
Diagram
Stop and Wait - Pros and Cons
• Simple
• Inefficient
Go Back N (1)
• Based on sliding window
• If no error, ACK as usual with next frame
expected
• Use window to control number of outstanding
frames
• If error, reply with rejection
—Discard that frame and all future frames until error
frame received correctly
—Transmitter must go back and retransmit that frame
and all subsequent frames
Go Back N - Damaged Frame
• Receiver detects error in frame i
• Receiver sends rejection-i
• Transmitter gets rejection-i
• Transmitter retransmits frame i and all
subsequent
Go Back N - Lost Frame (1)
• Frame i lost
• Transmitter sends i+1
• Receiver gets frame i+1 out of sequence
• Receiver send reject i
• Transmitter goes back to frame i and
retransmits
Go Back N - Lost Frame (2)
• Frame i lost and no additional frame sent
• Receiver gets nothing and returns neither
acknowledgement nor rejection
• Transmitter times out and sends
acknowledgement frame with P bit set to 1
• Receiver interprets this as command which it
acknowledges with the number of the next
frame it expects (frame i )
• Transmitter then retransmits frame i
Go Back N - Damaged
Acknowledgement
• Receiver gets frame i and send
acknowledgement (i+1) which is lost
• Acknowledgements are cumulative, so next
acknowledgement (i+n) may arrive before
transmitter times out on frame i
• If transmitter times out, it sends
acknowledgement with P bit set as before
• This can be repeated a number of times before
a reset procedure is initiated
Go Back N - Damaged Rejection
• As for lost frame (2)
Go Back N -
Diagram
Selective Reject
• Also called selective retransmission
• Only rejected frames are retransmitted
• Subsequent frames are accepted by the receiver
and buffered
• Minimizes retransmission
• Receiver must maintain large enough buffer
• More complex login in transmitter
Selective Reject -
Diagram
High Level Data Link Control
• HDLC
• ISO 33009, ISO 4335
HDLC Station Types
• Primary station
—Controls operation of link
—Frames issued are called commands
—Maintains separate logical link to each secondary
station
• Secondary station
—Under control of primary station
—Frames issued called responses
• Combined station
—May issue commands and responses
HDLC Link Configurations
• Unbalanced
—One primary and one or more secondary stations
—Supports full duplex and half duplex
• Balanced
—Two combined stations
—Supports full duplex and half duplex
HDLC Transfer Modes (1)
• Normal Response Mode (NRM)
—Unbalanced configuration
—Primary initiates transfer to secondary
—Secondary may only transmit data in response to
command from primary
—Used on multi-drop lines
—Host computer as primary
—Terminals as secondary
HDLC Transfer Modes (2)
• Asynchronous Balanced Mode (ABM)
—Balanced configuration
—Either station may initiate transmission without
receiving permission
—Most widely used
—No polling overhead
HDLC Transfer Modes (3)
• Asynchronous Response Mode (ARM)
—Unbalanced configuration
—Secondary may initiate transmission without
permission form primary
—Primary responsible for line
—rarely used
Frame Structure
• Synchronous transmission
• All transmissions in frames
• Single frame format for all data and control
exchanges
Frame Structure
Flag Fields
• Delimit frame at both ends
• 01111110
• May close one frame and open another
• Receiver hunts for flag sequence to synchronize
• Bit stuffing used to avoid confusion with data containing
01111110
— 0 inserted after every sequence of five 1s
— If receiver detects five 1s it checks next bit
— If 0, it is deleted
— If 1 and seventh bit is 0, accept as flag
— If sixth and seventh bits 1, sender is indicating abort
Bit Stuffing
• Example with
possible errors
Address Field
• Identifies secondary station that sent or will receive
frame
• Usually 8 bits long
• May be extended to multiples of 7 bits
— LSB of each octet indicates that it is the last octet (1) or not (0)
• All ones (11111111) is broadcast
Control Field
• Different for different frame type
—Information - data to be transmitted to user (next
layer up)
• Flow and error control piggybacked on information frames
—Supervisory - ARQ when piggyback not used
—Unnumbered - supplementary link control
• First one or two bits of control filed identify
frame type
• Remaining bits explained later
Control Field Diagram
Poll/Final Bit
• Use depends on context
• Command frame
—P bit
—1 to solicit (poll) response from peer
• Response frame
—F bit
—1 indicates response to soliciting command
Information Field
• Only in information and some unnumbered
frames
• Must contain integral number of octets
• Variable length
Frame Check Sequence Field
• FCS
• Error detection
• 16 bit CRC
• Optional 32 bit CRC
HDLC Operation
• Exchange of information, supervisory and
unnumbered frames
• Three phases
—Initialization
—Data transfer
—Disconnect
Examples of Operation (1)
Examples of Operation (2)
Required Reading
• Stallings chapter 7
• Web sites on HDLC
William Stallings
Data and Computer
Communications
7th Edition

Chapter 8
Multiplexing
Multiplexing
Frequency Division Multiplexing
• FDM
• Useful bandwidth of medium exceeds required
bandwidth of channel
• Each signal is modulated to a different carrier
frequency
• Carrier frequencies separated so signals do not
overlap (guard bands)
• e.g. broadcast radio
• Channel allocated even if no data
Frequency Division Multiplexing
Diagram
FDM System
FDM of Three Voiceband Signals
Analog Carrier Systems
• AT&T (USA)
• Hierarchy of FDM schemes
• Group
— 12 voice channels (4kHz each) = 48kHz
— Range 60kHz to 108kHz
• Supergroup
— 60 channel
— FDM of 5 group signals on carriers between 420kHz and 612
kHz
• Mastergroup
— 10 supergroups
Wavelength Division
Multiplexing
• Multiple beams of light at different frequency
• Carried by optical fiber
• A form of FDM
• Each color of light (wavelength) carries separate data
channel
• 1997 Bell Labs
— 100 beams
— Each at 10 Gbps
— Giving 1 terabit per second (Tbps)
• Commercial systems of 160 channels of 10 Gbps now
available
• Lab systems (Alcatel) 256 channels at 39.8 Gbps each
— 10.1 Tbps
— Over 100km
WDM Operation
• Same general architecture as other FDM
• Number of sources generating laser beams at different
frequencies
• Multiplexer consolidates sources for transmission over
single fiber
• Optical amplifiers amplify all wavelengths
— Typically tens of km apart
• Demux separates channels at the destination
• Mostly 1550nm wavelength range
• Was 200MHz per channel
• Now 50GHz
Dense Wavelength Division
Multiplexing
• DWDM
• No official or standard definition
• Implies more channels more closely spaced that
WDM
• 200GHz or less
Synchronous Time Division
Multiplexing
• Data rate of medium exceeds data rate of digital
signal to be transmitted
• Multiple digital signals interleaved in time
• May be at bit level of blocks
• Time slots preassigned to sources and fixed
• Time slots allocated even if no data
• Time slots do not have to be evenly distributed
amongst sources
Time Division Multiplexing
TDM System
TDM Link Control
• No headers and trailers
• Data link control protocols not needed
• Flow control
—Data rate of multiplexed line is fixed
—If one channel receiver can not receive data, the
others must carry on
—The corresponding source must be quenched
—This leaves empty slots
• Error control
—Errors are detected and handled by individual
channel systems
Data Link Control on TDM
Framing
• No flag or SYNC characters bracketing TDM
frames
• Must provide synchronizing mechanism
• Added digit framing
—One control bit added to each TDM frame
• Looks like another channel - “control channel”
—Identifiable bit pattern used on control channel
—e.g. alternating 01010101…unlikely on a data channel
—Can compare incoming bit patterns on each channel
with sync pattern
Pulse Stuffing
• Problem - Synchronizing data sources
• Clocks in different sources drifting
• Data rates from different sources not related by
simple rational number
• Solution - Pulse Stuffing
—Outgoing data rate (excluding framing bits) higher
than sum of incoming rates
—Stuff extra dummy bits or pulses into each incoming
signal until it matches local clock
—Stuffed pulses inserted at fixed locations in frame and
removed at demultiplexer
TDM of Analog and Digital
Sources
Digital Carrier Systems
• Hierarchy of TDM
• USA/Canada/Japan use one system
• ITU-T use a similar (but different) system
• US system based on DS-1 format
• Multiplexes 24 channels
• Each frame has 8 bits per channel plus one
framing bit
• 193 bits per frame
Digital Carrier Systems (2)
• For voice each channel contains one word of
digitized data (PCM, 8000 samples per sec)
—Data rate 8000x193 = 1.544Mbps
—Five out of six frames have 8 bit PCM samples
—Sixth frame is 7 bit PCM word plus signaling bit
—Signaling bits form stream for each channel
containing control and routing info
• Same format for digital data
—23 channels of data
• 7 bits per frame plus indicator bit for data or systems control
—24th channel is sync
Mixed Data
• DS-1 can carry mixed voice and data signals
• 24 channels used
• No sync byte
• Can also interleave DS-1 channels
—Ds-2 is four DS-1 giving 6.312Mbps
DS-1 Transmission Format
SONET/SDH
• Synchronous Optical Network (ANSI)
• Synchronous Digital Hierarchy (ITU-T)
• Compatible
• Signal Hierarchy
—Synchronous Transport Signal level 1 (STS-1) or
Optical Carrier level 1 (OC-1)
—51.84Mbps
—Carry DS-3 or group of lower rate signals (DS1 DS1C
DS2) plus ITU-T rates (e.g. 2.048Mbps)
—Multiple STS-1 combined into STS-N signal
—ITU-T lowest rate is 155.52Mbps (STM-1)
SONET Frame Format
SONET STS-1 Overhead Octets
Statistical TDM
• In Synchronous TDM many slots are wasted
• Statistical TDM allocates time slots dynamically
based on demand
• Multiplexer scans input lines and collects data
until frame full
• Data rate on line lower than aggregate rates of
input lines
Statistical TDM Frame Formats
Performance
• Output data rate less than aggregate input rates
• May cause problems during peak periods
—Buffer inputs
—Keep buffer size to minimum to reduce delay
Buffer Size
and Delay
Cable Modem Outline
• Two channels from cable TV provider dedicated to data
transfer
— One in each direction
• Each channel shared by number of subscribers
— Scheme needed to allocate capacity
— Statistical TDM
Cable Modem Operation
• Downstream
— Cable scheduler delivers data in small packets
— If more than one subscriber active, each gets fraction of
downstream capacity
• May get 500kbps to 1.5Mbps
— Also used to allocate upstream time slots to subscribers
• Upstream
— User requests timeslots on shared upstream channel
• Dedicated slots for this
— Headend scheduler sends back assignment of future tme slots
to subscriber
Cable Modem Scheme
Asymmetrical Digital
Subscriber Line
• ADSL
• Link between subscriber and network
—Local loop
• Uses currently installed twisted pair cable
—Can carry broader spectrum
—1 MHz or more
ADSL Design
• Asymmetric
—Greater capacity downstream than upstream
• Frequency division multiplexing
—Lowest 25kHz for voice
• Plain old telephone service (POTS)
—Use echo cancellation or FDM to give two bands
—Use FDM within bands
• Range 5.5km
ADSL Channel Configuration
Discrete Multitone
• DMT
• Multiple carrier signals at different frequencies
• Some bits on each channel
• 4kHz subchannels
• Send test signal and use subchannels with
better signal to noise ratio
• 256 downstream subchannels at 4kHz (60kbps)
—15.36MHz
—Impairments bring this down to 1.5Mbps to 9Mbps
DTM Bits Per Channel
Allocation
DMT Transmitter
xDSL
• High data rate DSL
• Single line DSL
• Very high data rate DSL
Required Reading
• Stallings chapter 8
• Web sites on
—ADSL
—SONET
William Stallings
Data and Computer
Communications
7th Edition

Chapter 9
Spread Spectrum
Spread Spectrum
• Analog or digital data
• Analog signal
• Spread data over wide bandwidth
• Makes jamming and interception harder
• Frequency hoping
— Signal broadcast over seemingly random series of frequencies
• Direct Sequence
— Each bit is represented by multiple bits in transmitted signal
— Chipping code
Spread Spectrum Concept
• Input fed into channel encoder
— Produces narrow bandwidth analog signal around central
frequency
• Signal modulated using sequence of digits
— Spreading code/sequence
— Typically generated by pseudonoise/pseudorandom number
generator
• Increases bandwidth significantly
— Spreads spectrum
• Receiver uses same sequence to demodulate signal
• Demodulated signal fed into channel decoder
General Model of Spread
Spectrum System
Gains
• Immunity from various noise and multipath
distortion
—Including jamming
• Can hide/encrypt signals
—Only receiver who knows spreading code can retrieve
signal
• Several users can share same higher bandwidth
with little interference
—Cellular telephones
—Code division multiplexing (CDM)
—Code division multiple access (CDMA)
Pseudorandom Numbers
• Generated by algorithm using initial seed
• Deterministic algorithm
—Not actually random
—If algorithm good, results pass reasonable tests of
randomness
• Need to know algorithm and seed to predict
sequence
Frequency Hopping Spread
Spectrum (FHSS)
• Signal broadcast over seemingly random series
of frequencies
• Receiver hops between frequencies in sync with
transmitter
• Eavesdroppers hear unintelligible blips
• Jamming on one frequency affects only a few
bits
Basic Operation
• Typically 2k carriers frequencies forming 2k
channels
• Channel spacing corresponds with bandwidth of
input
• Each channel used for fixed interval
—300 ms in IEEE 802.11
—Some number of bits transmitted using some
encoding scheme
• May be fractions of bit (see later)
—Sequence dictated by spreading code
Frequency Hopping Example
Frequency Hopping Spread
Spectrum System (Transmitter)
Frequency Hopping Spread
Spectrum System (Receiver)
Slow and Fast FHSS
• Frequency shifted every Tc seconds
• Duration of signal element is Ts seconds
• Slow FHSS has Tc ≥ Ts
• Fast FHSS has Tc < Ts
• Generally fast FHSS gives improved
performance in noise (or jamming)
Slow Frequency Hop Spread
Spectrum Using MFSK (M=4, k=2)
Fast Frequency Hop Spread
Spectrum Using MFSK (M=4, k=2)
FHSS Performance
Considerations
• Typically large number of frequencies used
—Improved resistance to jamming
Direct Sequence Spread
Spectrum (DSSS)
• Each bit represented by multiple bits using spreading
code
• Spreading code spreads signal across wider frequency
band
— In proportion to number of bits used
— 10 bit spreading code spreads signal across 10 times bandwidth
of 1 bit code
• One method:
— Combine input with spreading code using XOR
— Input bit 1 inverts spreading code bit
— Input zero bit doesn’t alter spreading code bit
— Data rate equal to original spreading code
• Performance similar to FHSS
Direct Sequence Spread
Spectrum Example
Direct Sequence Spread
Spectrum Transmitter
Direct Sequence Spread
Spectrum Transmitter
Direct Sequence Spread
Spectrum Using BPSK Example
Approximate
Spectrum of
DSSS Signal
Code Division Multiple Access
(CDMA)
• Multiplexing Technique used with spread spectrum
• Start with data signal rate D
— Called bit data rate
• Break each bit into k chips according to fixed pattern
specific to each user
— User’s code
• New channel has chip data rate kD chips per second
• E.g. k=6, three users (A,B,C) communicating with base
receiver R
• Code for A = <1,-1,-1,1,-1,1>
• Code for B = <1,1,-1,-1,1,1>
• Code for C = <1,1,-1,1,1,-1>
CDMA Example
CDMA Explanation
• Consider A communicating with base
• Base knows A’s code
• Assume communication already synchronized
• A wants to send a 1
— Send chip pattern <1,-1,-1,1,-1,1>
• A’s code
• A wants to send 0
— Send chip[ pattern <-1,1,1,-1,1,-1>
• Complement of A’s code
• Decoder ignores other sources when using A’s code to
decode
— Orthogonal codes
CDMA for DSSS
• n users each using different orthogonal PN
sequence
• Modulate each users data stream
—Using BPSK
• Multiply by spreading code of user
CDMA in a DSSS Environment
Seven Channel CDMA Encoding
and Decoding
Required Reading
• Stallings chapter 9
William Stallings
Data and Computer
Communications
7th Edition

Chapter 10
Circuit Switching and Packet
Switching
Switching Networks
• Long distance transmission is typically done
over a network of switched nodes
• Nodes not concerned with content of data
• End devices are stations
—Computer, terminal, phone, etc.
• A collection of nodes and connections is a
communications network
• Data routed by being switched from node to
node
Nodes
• Nodes may connect to other nodes only, or to
stations and other nodes
• Node to node links usually multiplexed
• Network is usually partially connected
—Some redundant connections are desirable for
reliability
• Two different switching technologies
—Circuit switching
—Packet switching
Simple Switched Network
Circuit Switching
• Dedicated communication path between two
stations
• Three phases
—Establish
—Transfer
—Disconnect
• Must have switching capacity and channel
capacity to establish connection
• Must have intelligence to work out routing
Circuit Switching - Applications
• Inefficient
—Channel capacity dedicated for duration of connection
—If no data, capacity wasted
• Set up (connection) takes time
• Once connected, transfer is transparent
• Developed for voice traffic (phone)
Public Circuit Switched
Network
Telecomms Components
• Subscriber
— Devices attached to network
• Subscriber line
— Local Loop
— Subscriber loop
— Connection to network
— Few km up to few tens of km
• Exchange
— Switching centers
— End office - supports subscribers
• Trunks
— Branches between exchanges
— Multiplexed
Circuit Establishment
Circuit Switch Elements
Circuit Switching Concepts
• Digital Switch
—Provide transparent signal path between devices
• Network Interface
• Control Unit
—Establish connections
• Generally on demand
• Handle and acknowledge requests
• Determine if destination is free
• construct path
—Maintain connection
—Disconnect
Blocking or Non-blocking
• Blocking
—A network is unable to connect stations because all
paths are in use
—A blocking network allows this
—Used on voice systems
• Short duration calls
• Non-blocking
—Permits all stations to connect (in pairs) at once
—Used for some data connections
Space Division Switching
• Developed for analog environment
• Separate physical paths
• Crossbar switch
—Number of crosspoints grows as square of number of
stations
—Loss of crosspoint prevents connection
—Inefficient use of crosspoints
• All stations connected, only a few crosspoints in use
—Non-blocking
Space Division Switch
Multistage Switch
• Reduced number of crosspoints
• More than one path through network
—Increased reliability
• More complex control
• May be blocking
Three Stage Space Division
Switch
Time Division Switching
• Modern digital systems rely on intelligent control
of space and time division elements
• Use digital time division techniques to set up
and maintain virtual circuits
• Partition low speed bit stream into pieces that
share higher speed stream
Control Signaling Functions
• Audible communication with subscriber
• Transmission of dialed number
• Call can not be completed indication
• Call ended indication
• Signal to ring phone
• Billing info
• Equipment and trunk status info
• Diagnostic info
• Control of specialist equipment
Control Signal Sequence
• Both phones on hook
• Subscriber lifts receiver (off hook)
• End office switch signaled
• Switch responds with dial tone
• Caller dials number
• If target not busy, send ringer signal to target
subscriber
• Feedback to caller
— Ringing tone, engaged tone, unobtainable
• Target accepts call by lifting receiver
• Switch terminates ringing signal and ringing tone
• Switch establishes connection
• Connection release when Source subscriber hangs up
Switch to Switch Signaling
• Subscribers connected to different switches
• Originating switch seizes interswitch trunk
• Send off hook signal on trunk, requesting digit
register at target switch (for address)
• Terminating switch sends off hook followed by
on hook (wink) to show register ready
• Originating switch sends address
Location of Signaling
• Subscriber to network
—Depends on subscriber device and switch
• Within network
—Management of subscriber calls and network
—ore complex
In Channel Signaling
• Use same channel for signaling and call
— Requires no additional transmission facilities
• Inband
— Uses same frequencies as voice signal
— Can go anywhere a voice signal can
— Impossible to set up a call on a faulty speech path
• Out of band
— Voice signals do not use full 4kHz bandwidth
— Narrow signal band within 4kHz used for control
— Can be sent whether or not voice signals are present
— Need extra electronics
— Slower signal rate (narrow bandwidth)
Drawbacks of In Channel
Signaling
• Limited transfer rate
• Delay between entering address (dialing) and
connection
• Overcome by use of common channel signaling
Common Channel Signaling
• Control signals carried over paths independent of voice
channel
• One control signal channel can carry signals for a
number of subscriber channels
• Common control channel for these subscriber lines
• Associated Mode
— Common channel closely tracks interswitch trunks
• Disassociated Mode
— Additional nodes (signal transfer points)
— Effectively two separate networks
Common v. In Channel
Signaling
Common
Channel
Signaling
Modes
Signaling System Number 7
• SS7
• Common channel signaling scheme
• ISDN
• Optimized for 64k digital channel network
• Call control, remote control, management and
maintenance
• Reliable means of transfer of info in sequence
• Will operate over analog and below 64k
• Point to point terrestrial and satellite links
SS7
Signaling Network Elements
• Signaling point (SP)
—Any point in the network capable of handling SS7
control message
• Signal transfer point (STP)
—A signaling point capable of routing control messages
• Control plane
—Responsible for establishing and managing
connections
• Information plane
—Once a connection is set up, info is transferred in the
information plane
Transfer
Points
Signaling Network Structures
• STP capacities
—Number of signaling links that can be handled
—Message transfer time
—Throughput capacity
• Network performance
—Number of SPs
—Signaling delays
• Availability and reliability
—Ability of network to provide services in the face of
STP failures
Softswitch Architecture
• General purpose computer running software to make it a smart
phone switch
• Lower costs
• Greater functionality
— Packetizing of digitized voice data
— Allowing voice over IP
• Most complex part of telephone network switch is software
controlling call process
— Call routing
— Call processing logic
— Typically running on proprietary processor
• Separate call processing from hardware function of switch
• Physical switching done by media gateway
• Call processing done by media gateway controller
Traditional Circuit Switching
Softswitch
Packet Switching Principles
• Circuit switching designed for voice
—Resources dedicated to a particular call
—Much of the time a data connection is idle
—Data rate is fixed
• Both ends must operate at the same rate
Basic Operation
• Data transmitted in small packets
—Typically 1000 octets
—Longer messages split into series of packets
—Each packet contains a portion of user data plus
some control info
• Control info
—Routing (addressing) info
• Packets are received, stored briefly (buffered)
and past on to the next node
—Store and forward
Use of Packets
Advantages
• Line efficiency
— Single node to node link can be shared by many packets over
time
— Packets queued and transmitted as fast as possible
• Data rate conversion
— Each station connects to the local node at its own speed
— Nodes buffer data if required to equalize rates
• Packets are accepted even when network is busy
— Delivery may slow down
• Priorities can be used
Switching Technique
• Station breaks long message into packets
• Packets sent one at a time to the network
• Packets handled in two ways
—Datagram
—Virtual circuit
Datagram
• Each packet treated independently
• Packets can take any practical route
• Packets may arrive out of order
• Packets may go missing
• Up to receiver to re-order packets and recover
from missing packets
Datagram
Diagram
Virtual Circuit
• Preplanned route established before any
packets sent
• Call request and call accept packets establish
connection (handshake)
• Each packet contains a virtual circuit identifier
instead of destination address
• No routing decisions required for each packet
• Clear request to drop circuit
• Not a dedicated path
Virtual
Circuit
Diagram
Virtual Circuits v Datagram
• Virtual circuits
—Network can provide sequencing and error control
—Packets are forwarded more quickly
• No routing decisions to make
—Less reliable
• Loss of a node looses all circuits through that node
• Datagram
—No call setup phase
• Better if few packets
—More flexible
• Routing can be used to avoid congested parts of the
network
Packet Size
Circuit v Packet Switching
• Performance
—Propagation delay
—Transmission time
—Node delay
Event Timing
X.25
• 1976
• Interface between host and packet switched
network
• Almost universal on packet switched networks
and packet switching in ISDN
• Defines three layers
—Physical
—Link
—Packet
X.25 - Physical
• Interface between attached station and link to
node
• Data terminal equipment DTE (user equipment)
• Data circuit terminating equipment DCE (node)
• Uses physical layer specification X.21
• Reliable transfer across physical link
• Sequence of frames
X.25 - Link
• Link Access Protocol Balanced (LAPB)
—Subset of HDLC
—see chapter 7
X.25 - Packet
• External virtual circuits
• Logical connections (virtual circuits) between
subscribers
X.25 Use of Virtual Circuits
Virtual Circuit Service
• Logical connection between two stations
—External virtual circuit
• Specific preplanned route through network
—Internal virtual circuit
• Typically one to one relationship between
external and internal virtual circuits
• Can employ X.25 with datagram style network
• External virtual circuits require logical channel
—All data considered part of stream
X.25 Levels
• User data passes to X.25 level 3
• X.25 appends control information
—Header
—Identifies virtual circuit
—Provides sequence numbers for flow and error control
• X.25 packet passed down to LAPB entity
• LAPB appends further control information
User Data and X.25 Protocol
Control Information
Frame Relay
• Designed to be more efficient than X.25
• Developed before ATM
• Larger installed base than ATM
• ATM now of more interest on high speed
networks
Frame Relay Background - X.25
• Call control packets, in band signaling
• Multiplexing of virtual circuits at layer 3
• Layer 2 and 3 include flow and error control
• Considerable overhead
• Not appropriate for modern digital systems with
high reliability
Frame Relay - Differences
• Call control carried in separate logical
connection
• Multiplexing and switching at layer 2
—Eliminates one layer of processing
• No hop by hop error or flow control
• End to end flow and error control (if used) are
done by higher layer
• Single user data frame sent from source to
destination and ACK (from higher layer) sent
back
Advantages and Disadvantages
• Lost link by link error and flow control
—Increased reliability makes this less of a problem
• Streamlined communications process
—Lower delay
—Higher throughput
• ITU-T recommend frame relay above 2Mbps
Protocol Architecture
Control Plane
• Between subscriber and network
• Separate logical channel used
—Similar to common channel signaling for circuit
switching services
• Data link layer
—LAPD (Q.921)
—Reliable data link control
—Error and flow control
—Between user (TE) and network (NT)
—Used for exchange of Q.933 control signal messages
User Plane
• End to end functionality
• Transfer of info between ends
• LAPF (Link Access Procedure for Frame Mode
Bearer Services) Q.922
—Frame delimiting, alignment and transparency
—Frame mux and demux using addressing field
—Ensure frame is integral number of octets (zero bit
insertion/extraction)
—Ensure frame is neither too long nor short
—Detection of transmission errors
—Congestion control functions
User Data Transfer
• One frame type
—User data
—No control frame
• No inband signaling
• No sequence numbers
—No flow nor error control
Required Reading
• Stallings Chapter 10
• ITU-T web site
• Telephone company web sites (not much
technical info - mostly marketing)
• X.25 info from ITU-T web site
• Frame Relay forum
William Stallings
Data and Computer
Communications
7th Edition

Chapter 11
Asynchronous Transfer Mode
Protocol Architecture
• Similarities between ATM and packet switching
—Transfer of data in discrete chunks
—Multiple logical connections over single physical
interface
• In ATM flow on each logical connection is in
fixed sized packets called cells
• Minimal error and flow control
—Reduced overhead
• Data rates (physical layer) 25.6Mbps to
622.08Mbps
Protocol Architecture (diag)
Reference Model Planes
• User plane
—Provides for user information transfer
• Control plane
—Call and connection control
• Management plane
—Plane management
• whole system functions
—Layer management
• Resources and parameters in protocol entities
ATM Logical Connections
• Virtual channel connections (VCC)
• Analogous to virtual circuit in X.25
• Basic unit of switching
• Between two end users
• Full duplex
• Fixed size cells
• Data, user-network exchange (control) and network-
network exchange (network management and routing)
• Virtual path connection (VPC)
— Bundle of VCC with same end points
ATM Connection Relationships
Advantages of Virtual Paths
• Simplified network architecture
• Increased network performance and reliability
• Reduced processing
• Short connection setup time
• Enhanced network services
Call
Establishment
Using VPs
Virtual Channel Connection
Uses
• Between end users
—End to end user data
—Control signals
—VPC provides overall capacity
• VCC organization done by users
• Between end user and network
—Control signaling
• Between network entities
—Network traffic management
—Routing
VP/VC Characteristics
• Quality of service
• Switched and semi-permanent channel
connections
• Call sequence integrity
• Traffic parameter negotiation and usage
monitoring

• VPC only
—Virtual channel identifier restriction within VPC
Control Signaling - VCC
• Done on separate connection
• Semi-permanent VCC
• Meta-signaling channel
— Used as permanent control signal channel
• User to network signaling virtual channel
— For control signaling
— Used to set up VCCs to carry user data
• User to user signaling virtual channel
— Within pre-established VPC
— Used by two end users without network intervention to establish
and release user to user VCC
Control Signaling - VPC
• Semi-permanent
• Customer controlled
• Network controlled
ATM Cells
• Fixed size
• 5 octet header
• 48 octet information field
• Small cells reduce queuing delay for high
priority cells
• Small cells can be switched more efficiently
• Easier to implement switching of small cells in
hardware
ATM Cell Format
Header Format
• Generic flow control
—Only at user to network interface
—Controls flow only at this point
• Virtual path identifier
• Virtual channel identifier
• Payload type
—e.g. user info or network management
• Cell loss priority
• Header error control
Generic Flow Control (GFC)
• Control traffic flow at user to network interface (UNI) to
alleviate short term overload
• Two sets of procedures
— Uncontrolled transmission
— Controlled transmission
• Every connection either subject to flow control or not
• Subject to flow control
— May be one group (A) default
— May be two groups (A and B)
• Flow control is from subscriber to network
— Controlled by network side
Single Group of Connections (1)
• Terminal equipment (TE) initializes two variables
—TRANSMIT flag to 1
—GO_CNTR (credit counter) to 0
• If TRANSMIT=1 cells on uncontrolled connection
may be sent any time
• If TRANSMIT=0 no cells may be sent (on
controlled or uncontrolled connections)
• If HALT received, TRANSMIT set to 0 and
remains until NO_HALT
Single Group of Connections (2)
• If TRANSMIT=1 and no cell to transmit on any
uncontrolled connection:
—If GO_CNTR>0, TE may send cell on controlled
connection
• Cell marked as being on controlled connection
• GO_CNTR decremented
—If GO_CNTR=0, TE may not send on controlled
connection
• TE sets GO_CNTR to GO_VALUE upon receiving
SET signal
—Null signal has no effect
Use of HALT
• To limit effective data rate on ATM
• Should be cyclic
• To reduce data rate by half, HALT issued to be
in effect 50% of time
• Done on regular pattern over lifetime of
connection
Two Queue Model
• Two counters
—GO_CNTR_A, GO_VALUE_A,GO_CNTR_B,
GO_VALUE_B
Header Error Control
• 8 bit error control field
• Calculated on remaining 32 bits of header
• Allows some error correction
HEC Operation at Receiver
Effect of
Error in
Cell Header
Impact of Random Bit Errors on
HEC Performance
Transmission of ATM Cells
• 622.08Mbps
• 155.52Mbps
• 51.84Mbps
• 25.6Mbps
• Cell Based physical layer
• SDH based physical layer
Cell Based Physical Layer
• No framing imposed
• Continuous stream of 53 octet cells
• Cell delineation based on header error control
field
Cell Delineation State Diagram
Impact of Random Bit Errors on
Cell Delineation Performance
Acquisition Time v Bit Error
Rate
SDH Based Physical Layer
• Imposes structure on ATM stream
• e.g. for 155.52Mbps
• Use STM-1 (STS-3) frame
• Can carry ATM and STM payloads
• Specific connections can be circuit switched
using SDH channel
• SDH multiplexing techniques can combine
several ATM streams
STM-1 Payload for SDH-Based
ATM Cell Transmission
ATM Service Categories
• Real time
—Constant bit rate (CBR)
—Real time variable bit rate (rt-VBR)
• Non-real time
—Non-real time variable bit rate (nrt-VBR)
—Available bit rate (ABR)
—Unspecified bit rate (UBR)
—Guaranteed frame rate (GFR)
Real Time Services
• Amount of delay
• Variation of delay (jitter)
CBR
• Fixed data rate continuously available
• Tight upper bound on delay
• Uncompressed audio and video
—Video conferencing
—Interactive audio
—A/V distribution and retrieval
rt-VBR
• Time sensitive application
—Tightly constrained delay and delay variation
• rt-VBR applications transmit at a rate that varies
with time
• e.g. compressed video
—Produces varying sized image frames
—Original (uncompressed) frame rate constant
—So compressed data rate varies
• Can statistically multiplex connections
nrt-VBR
• May be able to characterize expected traffic flow
• Improve QoS in loss and delay
• End system specifies:
—Peak cell rate
—Sustainable or average rate
—Measure of how bursty traffic is
• e.g. Airline reservations, banking transactions
UBR
• May be additional capacity over and above that
used by CBR and VBR traffic
—Not all resources dedicated
—Bursty nature of VBR
• For application that can tolerate some cell loss
or variable delays
—e.g. TCP based traffic
• Cells forwarded on FIFO basis
• Best efforts service
ABR
• Application specifies peak cell rate (PCR) and
minimum cell rate (MCR)
• Resources allocated to give at least MCR
• Spare capacity shared among all ARB sources
• e.g. LAN interconnection
Guaranteed Frame Rate (GFR)
• Designed to support IP backbone subnetworks
• Better service than UBR for frame based traffic
— Including IP and Ethernet
• Optimize handling of frame based traffic passing from
LAN through router to ATM backbone
— Used by enterprise, carrier and ISP networks
— Consolidation and extension of IP over WAN
• ABR difficult to implement between routers over ATM
network
• GFR better alternative for traffic originating on Ethernet
— Network aware of frame/packet boundaries
— When congested, all cells from frame discarded
— Guaranteed minimum capacity
— Additional frames carried of not congested
ATM Adaptation Layer
• Support for information transfer protocol not
based on ATM
• PCM (voice)
—Assemble bits into cells
—Re-assemble into constant flow
• IP
—Map IP packets onto ATM cells
—Fragment IP packets
—Use LAPF over ATM to retain all IP infrastructure
ATM Bit Rate Services
Adaptation Layer Services
• Handle transmission errors
• Segmentation and re-assembly
• Handle lost and misinserted cells
• Flow control and timing
Supported Application types
• Circuit emulation
• VBR voice and video
• General data service
• IP over ATM
• Multiprotocol encapsulation over ATM (MPOA)
—IPX, AppleTalk, DECNET)
• LAN emulation
AAL Protocols
• Convergence sublayer (CS)
—Support for specific applications
—AAL user attaches at SAP
• Segmentation and re-assembly sublayer (SAR)
—Packages and unpacks info received from CS into
cells
• Four types
—Type 1
—Type 2
—Type 3/4
—Type 5
AAL Protocols
Segmentation and Reassembly
PDU
AAL Type 1
• CBR source
• SAR packs and unpacks bits
• Block accompanied by sequence number
AAL Type 2
• VBR
• Analog applications
AAL Type 3/4
• Connectionless or connected
• Message mode or stream mode
AAL Type 5
• Streamlined transport for connection oriented
higher layer protocols
CPCS PDUs
Example AAL 5 Transmission
Required Reading
• Stallings Chapter 11
• ATM Forum Web site
William Stallings
Data and Computer
Communications
7th Edition

Chapter 12
Routing
Routing in Circuit Switched
Network
• Many connections will need paths through more
than one switch
• Need to find a route
—Efficiency
—Resilience
• Public telephone switches are a tree structure
—Static routing uses the same approach all the time
• Dynamic routing allows for changes in routing
depending on traffic
—Uses a peer structure for nodes
Alternate Routing
• Possible routes between end offices predefined
• Originating switch selects appropriate route
• Routes listed in preference order
• Different sets of routes may be used at different
times
Alternate
Routing
Diagram
Routing in Packet Switched
Network
• Complex, crucial aspect of packet switched
networks
• Characteristics required
—Correctness
—Simplicity
—Robustness
—Stability
—Fairness
—Optimality
—Efficiency
Performance Criteria
• Used for selection of route
• Minimum hop
• Least cost
—See Stallings appendix 10A for routing algorithms
Example Packet Switched
Network
Decision Time and Place
• Time
—Packet or virtual circuit basis
• Place
—Distributed
• Made by each node
—Centralized
—Source
Network Information Source
and Update Timing
• Routing decisions usually based on knowledge of
network (not always)
• Distributed routing
— Nodes use local knowledge
— May collect info from adjacent nodes
— May collect info from all nodes on a potential route
• Central routing
— Collect info from all nodes
• Update timing
— When is network info held by nodes updated
— Fixed - never updated
— Adaptive - regular updates
Routing Strategies
• Fixed
• Flooding
• Random
• Adaptive
Fixed Routing
• Single permanent route for each source to
destination pair
• Determine routes using a least cost algorithm
(appendix 10A)
• Route fixed, at least until a change in network
topology
Fixed Routing
Tables
Flooding
• No network info required
• Packet sent by node to every neighbor
• Incoming packets retransmitted on every link except
incoming link
• Eventually a number of copies will arrive at destination
• Each packet is uniquely numbered so duplicates can be
discarded
• Nodes can remember packets already forwarded to keep
network load in bounds
• Can include a hop count in packets
Flooding
Example
Properties of Flooding
• All possible routes are tried
—Very robust
• At least one packet will have taken minimum
hop count route
—Can be used to set up virtual circuit
• All nodes are visited
—Useful to distribute information (e.g. routing)
Random Routing
• Node selects one outgoing path for
retransmission of incoming packet
• Selection can be random or round robin
• Can select outgoing path based on probability
calculation
• No network info needed
• Route is typically not least cost nor minimum
hop
Adaptive Routing
• Used by almost all packet switching networks
• Routing decisions change as conditions on the network
change
— Failure
— Congestion
• Requires info about network
• Decisions more complex
• Tradeoff between quality of network info and overhead
• Reacting too quickly can cause oscillation
• Too slowly to be relevant
Adaptive Routing - Advantages
• Improved performance
• Aid congestion control (See chapter 13)
• Complex system
—May not realize theoretical benefits
Classification
• Based on information sources
—Local (isolated)
• Route to outgoing link with shortest queue
• Can include bias for each destination
• Rarely used - do not make use of easily available info
—Adjacent nodes
—All nodes
Isolated Adaptive Routing
ARPANET Routing Strategies(1)
• First Generation
—1969
—Distributed adaptive
—Estimated delay as performance criterion
—Bellman-Ford algorithm (appendix 10a)
—Node exchanges delay vector with neighbors
—Update routing table based on incoming info
—Doesn't consider line speed, just queue length
—Queue length not a good measurement of delay
—Responds slowly to congestion
ARPANET Routing Strategies(2)
• Second Generation
—1979
—Uses delay as performance criterion
—Delay measured directly
—Uses Dijkstra’s algorithm (appendix 10a)
—Good under light and medium loads
—Under heavy loads, little correlation between
reported delays and those experienced
ARPANET Routing Strategies(3)
• Third Generation
—1987
—Link cost calculations changed
—Measure average delay over last 10 seconds
—Normalize based on current value and previous
results
Least Cost Algorithms
• Basis for routing decisions
— Can minimize hop with each link cost 1
— Can have link value inversely proportional to capacity
• Given network of nodes connected by bi-directional links
• Each link has a cost in each direction
• Define cost of path between two nodes as sum of costs
of links traversed
• For each pair of nodes, find a path with the least cost
• Link costs in different directions may be different
— E.g. length of packet queue
Dijkstra’s Algorithm Definitions
• Find shortest paths from given source node to all other
nodes, by developing paths in order of increasing path
length
• N = set of nodes in the network
• s = source node
• T = set of nodes so far incorporated by the algorithm
• w(i, j) = link cost from node i to node j
— w(i, i) = 0
— w(i, j) = ∞ if the two nodes are not directly connected
— w(i, j) ≥ 0 if the two nodes are directly connected
• L(n) = cost of least-cost path from node s to node n
currently known
— At termination, L(n) is cost of least-cost path from s to n
Dijkstra’s Algorithm Method
• Step 1 [Initialization]
— T = {s} Set of nodes so far incorporated consists of only source node
— L(n) = w(s, n) for n ≠ s
— Initial path costs to neighboring nodes are simply link costs
• Step 2 [Get Next Node]
— Find neighboring node not in T with least-cost path from s
— Incorporate node into T
— Also incorporate the edge that is incident on that node and a node in T
that contributes to the path
• Step 3 [Update Least-Cost Paths]
— L(n) = min[L(n), L(x) + w(x, n)] for all n ∉ T
— If latter term is minimum, path from s to n is path from s to x
concatenated with edge from x to n
• Algorithm terminates when all nodes have been added to T
Dijkstra’s Algorithm Notes
• At termination, value L(x) associated with each
node x is cost (length) of least-cost path from s
to x.
• In addition, T defines least-cost path from s to
each other node
• One iteration of steps 2 and 3 adds one new
node to T
—Defines least cost path from s tothat node
Example of Dijkstra’s Algorithm
 Results of Example
Dijkstra’s Algorithm
Ite T L(2) Path L(3) Path L(4) Path L(5) Path L(6 Path
rat )
ion
1 {1} 2 1–2 5 1-3 1 1–4 ∞ - ∞ -

2 {1,4} 2 1–2 4 1-4-3 1 1–4 2 1-4–5 ∞ -

3 {1, 2, 4} 2 1–2 4 1-4-3 1 1–4 2 1-4–5 ∞ -

4 {1, 2, 4, 2 1–2 3 1-4-5–3 1 1–4 2 1-4–5 4 1-4-5–6

5}

5 {1, 2, 3, 2 1–2 3 1-4-5–3 1 1–4 2 1-4–5 4 1-4-5–6

4, 5}

6 {1, 2, 3, 2 1-2 3 1-4-5-3 1 1-4 2 1-4–5 4 1-4-5-6

4, 5, 6}
Bellman-Ford Algorithm
Definitions
• Find shortest paths from given node subject to
constraint that paths contain at most one link
• Find the shortest paths with a constraint of paths of at
most two links
• And so on
• s = source node
• w(i, j) = link cost from node i to node j
— w(i, i) = 0
— w(i, j) = ∞ if the two nodes are not directly connected
— w(i, j) ≥ 0 if the two nodes are directly connected
• h = maximum number of links in path at current stage
of the algorithm
• Lh(n) = cost of least-cost path from s to n under
constraint of no more than h links
Bellman-Ford Algorithm Method
• Step 1 [Initialization]
— L0(n) = ∞, for all n ≠ s
— Lh(s) = 0, for all h
• Step 2 [Update]
• For each successive h ≥ 0
— For each n ≠ s, compute
— Lh+1(n)=minj[Lh(j)+w(j,n)]
• Connect n with predecessor node j that achieves
minimum
• Eliminate any connection of n with different predecessor
node formed during an earlier iteration
• Path from s to n terminates with link from j to n
Bellman-Ford Algorithm Notes
• For each iteration of step 2 with h=K and for
each destination node n, algorithm compares
paths from s to n of length K=1 with path from
previous iteration
• If previous path shorter it is retained
• Otherwise new path is defined
Example of Bellman-Ford
Algorithm
 Results of Bellman-Ford
Example
h Lh(2) Path Lh(3) Path Lh(4) Path Lh(5) Path Lh(6) Path

0 ∞ - ∞ - ∞ - ∞ - ∞ -

1 2 1-2 5 1-3 1 1-4 ∞ - ∞ -

2 2 1-2 4 1-4-3 1 1-4 2 1-4-5 10 1-3-6

3 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6

4 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6

Comparison
• Results from two algorithms agree
• Information gathered
— Bellman-Ford
• Calculation for node n involves knowledge of link cost to all
neighboring nodes plus total cost to each neighbor from s
• Each node can maintain set of costs and paths for every other node
• Can exchange information with direct neighbors
• Can update costs and paths based on information from neighbors
and knowledge of link costs
— Dijkstra
• Each node needs complete topology
• Must know link costs of all links in network
• Must exchange information with all other nodes
Evaluation
• Dependent on processing time of algorithms
• Dependent on amount of information required
from other nodes
• Implementation specific
• Both converge under static topology and costs
• Converge to same solution
• If link costs change, algorithms will attempt to
catch up
• If link costs depend on traffic, which depends
on routes chosen, then feedback
—May result in instability
Required Reading
• Stalling Chapter 12
• Routing information from Comer D.
Internetworking with TCP/IP Volume 1, Prentice
Hall, Upper Saddle River NJ.
William Stallings
Data and Computer
Communications
7th Edition

Chapter 13
Congestion in Data Networks
What Is Congestion?
• Congestion occurs when the number of packets
being transmitted through the network
approaches the packet handling capacity of the
network
• Congestion control aims to keep number of
packets below level at which performance falls
off dramatically
• Data network is a network of queues
• Generally 80% utilization is critical
• Finite queues mean data may be lost
Queues at a Node
Effects of Congestion
• Packets arriving are stored at input buffers
• Routing decision made
• Packet moves to output buffer
• Packets queued for output transmitted as fast as
possible
— Statistical time division multiplexing
• If packets arrive to fast to be routed, or to be output,
buffers will fill
• Can discard packets
• Can use flow control
— Can propagate congestion through network
Interaction of Queues
Ideal
Network
Utilization
Practical Performance
• Ideal assumes infinite buffers and no overhead
• Buffers are finite
• Overheads occur in exchanging congestion
control messages
Effects of
Congestion -
No Control
Mechanisms for
Congestion Control
Backpressure
• If node becomes congested it can slow down or halt
flow of packets from other nodes
• May mean that other nodes have to apply control on
incoming packet rates
• Propagates back to source
• Can restrict to logical connections generating most
traffic
• Used in connection oriented that allow hop by hop
congestion control (e.g. X.25)
• Not used in ATM nor frame relay
• Only recently developed for IP
Choke Packet
• Control packet
—Generated at congested node
—Sent to source node
—e.g. ICMP source quench
• From router or destination
• Source cuts back until no more source quench message
• Sent for every discarded packet, or anticipated
• Rather crude mechanism
Implicit Congestion Signaling
• Transmission delay may increase with
congestion
• Packet may be discarded
• Source can detect these as implicit indications of
congestion
• Useful on connectionless (datagram) networks
—e.g. IP based
• (TCP includes congestion and flow control - see chapter 17)
• Used in frame relay LAPF
Explicit Congestion Signaling
• Network alerts end systems of increasing
congestion
• End systems take steps to reduce offered load
• Backwards
—Congestion avoidance in opposite direction to packet
required
• Forwards
—Congestion avoidance in same direction as packet
required
Categories of Explicit Signaling
• Binary
—A bit set in a packet indicates congestion
• Credit based
—Indicates how many packets source may send
—Common for end to end flow control
• Rate based
—Supply explicit data rate limit
—e.g. ATM
Traffic Management
• Fairness
• Quality of service
—May want different treatment for different
connections
• Reservations
—e.g. ATM
—Traffic contract between user and network
Congestion Control in Packet
Switched Networks
• Send control packet to some or all source nodes
—Requires additional traffic during congestion
• Rely on routing information
—May react too quickly
• End to end probe packets
—Adds to overhead
• Add congestion info to packets as they cross
nodes
—Either backwards or forwards
Frame Relay
Congestion Control
• Minimize discards
• Maintain agreed QoS
• Minimize probability of one end user monoply
• Simple to implement
— Little overhead on network or user
• Create minimal additional traffic
• Distribute resources fairly
• Limit spread of congestion
• Operate effectively regardless of traffic flow
• Minimum impact on other systems
• Minimize variance in QoS
Techniques
• Discard strategy
• Congestion avoidance
• Explicit signaling
• Congestion recovery
• Implicit signaling mechanism
Traffic Rate Management
• Must discard frames to cope with congestion
—Arbitrarily, no regard for source
—No reward for restraint so end systems transmit as
fast as possible
—Committed information rate (CIR)
• Data in excess of this liable to discard
• Not guaranteed
• Aggregate CIR should not exceed physical data rate
• Committed burst size
• Excess burst size
Operation of CIR
Relationship
Among
Congestion
Parameters
Explicit Signaling
• Network alerts end systems of growing
congestion
• Backward explicit congestion notification
• Forward explicit congestion notification
• Frame handler monitors its queues
• May notify some or all logical connections
• User response
—Reduce rate
ATM Traffic Management
• High speed, small cell size, limited overhead bits
• Still evolving
• Requirements
—Majority of traffic not amenable to flow control
—Feedback slow due to reduced transmission time
compared with propagation delay
—Wide range of application demands
—Different traffic patterns
—Different network services
—High speed switching and transmission increases
volatility
Latency/Speed Effects
• ATM 150Mbps
• ~2.8x10-6 seconds to insert single cell
• Time to traverse network depends on propagation delay,
switching delay
• Assume propagation at two-thirds speed of light
• If source and destination on opposite sides of USA,
propagation time ~ 48x10-3 seconds
• Given implicit congestion control, by the time dropped
cell notification has reached source, 7.2x106 bits have
been transmitted
• So, this is not a good strategy for ATM
Cell Delay Variation
• For ATM voice/video, data is a stream of cells
• Delay across network must be short
• Rate of delivery must be constant
• There will always be some variation in transit
• Delay cell delivery to application so that
constant bit rate can be maintained to
application
Time Re-assembly of CBR Cells
Network Contribution to
Cell Delay Variation
• Packet switched networks
— Queuing delays
— Routing decision time
• Frame relay
— As above but to lesser extent
• ATM
— Less than frame relay
— ATM protocol designed to minimize processing overheads at
switches
— ATM switches have very high throughput
— Only noticeable delay is from congestion
— Must not accept load that causes congestion
Cell Delay Variation
At The UNI
• Application produces data at fixed rate
• Processing at three layers of ATM causes delay
—Interleaving cells from different connections
—Operation and maintenance cell interleaving
—If using synchronous digital hierarchy frames, these
are inserted at physical layer
—Can not predict these delays
Origins of Cell Delay Variation
Traffic and Congestion
Control Framework
• ATM layer traffic and congestion control should
support QoS classes for all foreseeable network
services
• Should not rely on AAL protocols that are
network specific, nor higher level application
specific protocols
• Should minimize network and end to end
system complexity
Timings Considered
• Cell insertion time
• Round trip propagation time
• Connection duration
• Long term

• Determine whether a given new connection can

be accommodated
• Agree performance parameters with subscriber
Traffic Management and
Congestion Control Techniques
• Resource management using virtual paths
• Connection admission control
• Usage parameter control
• Selective cell discard
• Traffic shaping
Resource Management Using
Virtual Paths
• Separate traffic flow according to service
characteristics
• User to user application
• User to network application
• Network to network application

• Concern with:
—Cell loss ratio
—Cell transfer delay
—Cell delay variation
Configuration of
VCCs and VPCs
Allocating VCCs within VPC
• All VCCs within VPC should experience similar
network performance
• Options for allocation:
—Aggregate peak demand
—Statistical multiplexing
Connection Admission Control
• First line of defense
• User specifies traffic characteristics for new
connection (VCC or VPC) by selecting a QoS
• Network accepts connection only if it can meet
the demand
• Traffic contract
—Peak cell rate
—Cell delay variation
—Sustainable cell rate
—Burst tolerance
Usage Parameter Control
• Monitor connection to ensure traffic cinforms to
contract
• Protection of network resources from overload
by one connection
• Done on VCC and VPC
• Peak cell rate and cell delay variation
• Sustainable cell rate and burst tolerance
• Discard cells that do not conform to traffic
contract
• Called traffic policing
Traffic Shaping
• Smooth out traffic flow and reduce cell clumping
• Token bucket
Token Bucket for
Traffic Shaping
GFR Traffic Management
• Guaranteed frame rate is as simple as UBR from
end system viewpoint
• Places modest requirements on ATM network
elements
• End system does no policing or shaping of
traffic
• May transmit at line rate of ATM adaptor
• No guarantee of delivery
—Higher layer (e.g. TCP) must do congestion control
• User can reserve capacity for each VC
—Assures application may transmit at minimum rate
without losses
—If no congestion, higher rates maybe used
Frame Recognition
• GFR recognizes frames as well as cells
• When congested, network discards whole frame
rather than individual cells
• All cells of a frame have same CLP bit setting
• CLP=1 AAL5 frames are lower priority
—Best efforts
• CLP=0 frames minimum guaranteed capacity
GFR Contract Parameters
• Peak cell rate (PCR)
• Minimum cell rate (MCR)
• Maximum burst size (MBS)
• Maximum frame size (MFS)
• Cell delay variation tolerance (CDVT)
Mechanisms for Supporting
Rate Guarantees (1)
• Tagging and policing
— Discriminate between frames that conform to contract and
those that don’t
— Set CLP=1 on all cells in frame if not
• Gives lower priority
— Maybe done by network or source
— Network may discard CLP=1 cells
• Policing
• Buffer management
— Treatment of buffered cells
— Congestion indicated by high buffer occupancy
— Discard tagged cells
• Including ones already in buffer to make room
— To be fair, per VC buffering
— Cell discard based on queue-specific thresholds
Mechanisms for Supporting
Rate Guarantees (2)
• Scheduling
—Give preferential treatment to untagged cells
—Separate queues for each VC
—Make per-VC scheduling decisions
—Enables control of outgoing rate of VCs
—VCs get fair capacity allocation
—Still meet contract
Components of GFR System
Conformance Definition
• UPC
—Monitors each active VC
—Ensure traffic conforms to contract
—Tag or discard nonconforming cells
—Frame conforms if all cells conform
—Cell conforms if:
• Rate of cells within contract
• All cells in frame have same CLP
• Frame satisfies MFS parameter (check for last cell in frame
or cell count < MFS)
QoS Eligibility Test
• Two stage filtering process
—Frame tested for conformance to contract
• If not, may discard
• If not discarded, tag
• Sets upper bound
• Penalize cells above upper bound
• Implementations expected to attempt delivery of tagged
cells
—Determine frames eligible for QoS guarantees
• Under GFR contract for VC
• Lower bound on traffic
• Frames making up traffic flow below threshold are eligible
GFR VC Frame Categories
• Nonconforming frame
—Cells of this frame will be tagged or discarded
• Conforming but ineligible frames
—Cells will receive a best-effort service
• Conforming and eligible frames
—Cells will receive a guarantee of delivery
Required Reading
• Stallings chapter 13
William Stallings
Data and Computer
Communications
7th Edition

Chapter 14
Cellular Wireless Networks
Principles of Cellular Networks
• Underlying technology for mobile phones,
personal communication systems, wireless
networking etc.
• Developed for mobile radio telephone
—Replace high power transmitter/receiver systems
• Typical support for 25 channels over 80km
—Use lower power, shorter range, more transmitters
Cellular Network Organization
• Multiple low power transmitters
—100w or less
• Area divided into cells
—Each with own antenna
—Each with own range of frequencies
—Served by base station
• Transmitter, receiver, control unit
—Adjacent cells on different frequencies to avoid
crosstalk
Shape of Cells
• Square
— Width d cell has four neighbors at distance d and four at
distance 2 d
— Better if all adjacent antennas equidistant
• Simplifies choosing and switching to new antenna
• Hexagon
— Provides equidistant antennas
— Radius defined as radius of circum-circle
• Distance from center to vertex equals length of side
— Distance between centers of cells radius R is 3R
— Not always precise hexagons
• Topographical limitations
• Local signal propagation conditions
• Location of antennas
Cellular Geometries
Frequency Reuse
• Power of base transceiver controlled
— Allow communications within cell on given frequency
— Limit escaping power to adjacent cells
— Allow re-use of frequencies in nearby cells
— Use same frequency for multiple conversations
— 10 – 50 frequencies per cell
• E.g.
— N cells all using same number of frequencies
— K total number of frequencies used in systems
— Each cell has K/N frequencies
— Advanced Mobile Phone Service (AMPS) K=395, N=7 giving 57
frequencies per cell on average
Characterizing Frequency
Reuse
• D = minimum distance between centers of cells that use the same
band of frequencies (called cochannels)
• R = radius of a cell
• d = distance between centers of adjacent cells (d = R)
• N = number of cells in repetitious pattern
— Reuse factor
— Each cell in pattern uses unique band of frequencies
• Hexagonal cell pattern, following values of N possible
— N = I2 + J2 + (I x J), I, J = 0, 1, 2, 3, …
• Possible values of N are 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, …
• D/R= 3N
• D/d = N
Frequency
Reuse
Patterns
Increasing Capacity (1)
• Add new channels
—Not all channels used to start with
• Frequency borrowing
—Taken from adjacent cells by congested cells
—Or assign frequencies dynamically
• Cell splitting
—Non-uniform distribution of topography and traffic
—Smaller cells in high use areas
• Original cells 6.5 – 13 km
• 1.5 km limit in general
• More frequent handoff
• More base stations
Cell Splitting
Increasing Capacity (2)
• Cell Sectoring
—Cell divided into wedge shaped sectors
—3 – 6 sectors per cell
—Each with own channel set
• Subsets of cell’s channels
—Directional antennas
• Microcells
—Move antennas from tops of hills and large buildings
to tops of small buildings and sides of large buildings
• Even lamp posts
—Form microcells
—Reduced power
—Good for city streets, along roads and inside large
buildings
Frequency Reuse Example
Operation of Cellular Systems
• Base station (BS) at center of each cell
— Antenna, controller, transceivers
• Controller handles call process
— Number of mobile units may in use at a time
• BS connected to mobile telecommunications switching
office (MTSO)
— One MTSO serves multiple BS
— MTSO to BS link by wire or wireless
• MTSO:
— Connects calls between mobile units and from mobile to fixed
telecommunications network
— Assigns voice channel
— Performs handoffs
— Monitors calls (billing)
• Fully automated
Overview of Cellular System
Channels
• Control channels
—Setting up and maintaining calls
—Establish relationship between mobile unit and
nearest BS
• Traffic channels
—Carry voice and data
Typical Call in
Single MTSO Area (1)
• Mobile unit initialization
— Scan and select strongest set up control channel
— Automatically selected BS antenna of cell
• Usually but not always nearest (propagation anomalies)
— Handshake to identify user and register location
— Scan repeated to allow for movement
• Change of cell
— Mobile unit monitors for pages (see below)
• Mobile originated call
— Check set up channel is free
• Monitor forward channel (from BS) and wait for idle
— Send number on pre-selected channel
• Paging
— MTSO attempts to connect to mobile unit
— Paging message sent to BSs depending on called mobile number
— Paging signal transmitted on set up channel
Typical Call in
Single MTSO Area (2)
• Call accepted
— Mobile unit recognizes number on set up channel
— Responds to BS which sends response to MTSO
— MTSO sets up circuit between calling and called BSs
— MTSO selects available traffic channel within cells and notifies
BSs
— BSs notify mobile unit of channel
• Ongoing call
— Voice/data exchanged through respective BSs and MTSO
• Handoff
— Mobile unit moves out of range of cell into range of another cell
— Traffic channel changes to one assigned to new BS
• Without interruption of service to user
Call Stages
Other Functions
• Call blocking
— During mobile-initiated call stage, if all traffic channels busy, mobile
tries again
— After number of fails, busy tone returned
• Call termination
— User hangs up
— MTSO informed
— Traffic channels at two BSs released
• Call drop
— BS cannot maintain required signal strength
— Traffic channel dropped and MTSO informed
• Calls to/from fixed and remote mobile subscriber
— MTSO connects to PSTN
— MTSO can connect mobile user and fixed subscriber via PSTN
— MTSO can connect to remote MTSO via PSTN or via dedicated lines
— Can connect mobile user in its area and remote mobile user
Mobile Radio
Propagation Effects
• Signal strength
— Strength of signal between BS and mobile unit strong enough to
maintain signal quality at the receiver
— Not strong enough to create too much cochannel interference
— Noise varies
• Automobile ignition noise greater in city than in suburbs
• Other signal sources vary
• Signal strength varies as function of distance from BS
• Signal strength varies dynamically as mobile unit moves
• Fading
— Even if signal strength in effective range, signal propagation
effects may disrupt the signal
Design Factors
• Propagation effects
— Dynamic
— Hard to predict
• Maximum transmit power level at BS and mobile units
• Typical height of mobile unit antenna
• Available height of the BS antenna
• These factors determine size of individual cell
• Model based on empirical data
• Apply model to given environment to develop guidelines
for cell size
• E.g. model by Okumura et al refined by Hata
— Detailed analysis of Tokyo area
— Produced path loss information for an urban environment
— Hata's model is an empirical formulation
• Takes into account variety of environments and conditions
Fading
• Time variation of received signal
• Caused by changes in transmission path(s)
• E.g. atmospheric conditions (rain)
• Movement of (mobile unit) antenna
Multipath Propagation
• Reflection
— Surface large relative to wavelength of signal
— May have phase shift from original
— May cancel out original or increase it
• Diffraction
— Edge of impenetrable body that is large relative to wavelength
— May receive signal even if no line of sight (LOS) to transmitter
• Scattering
— Obstacle size on order of wavelength
• Lamp posts etc.
• If LOS, diffracted and scattered signals not significant
— Reflected signals may be
• If no LOS, diffraction and scattering are primary means
of reception
Reflection, Diffraction,
Scattering
Effects of Multipath
Propagation
• Signals may cancel out due to phase differences
• Intersymbol Interference (ISI)
—Sending narrow pulse at given frequency between
fixed antenna and mobile unit
—Channel may deliver multiple copies at different times
—Delayed pulses act as noise making recovery of bit
information difficult
—Timing changes as mobile unit moves
• Harder to design signal processing to filter out multipath
effects
Two Pulses in Time-Variant
Multipath
Types of Fading
• Fast fading
— Rapid changes in strength over distances about half wavelength
• 900MHz wavelength is 0.33m
• 20-30dB
• Slow fading
— Slower changes due to user passing different height buildings,
gaps in buildings etc.
— Over longer distances than fast fading
• Flat fading
— Nonselective
— Affects all frequencies in same proportion
• Selective fading
— Different frequency components affected differently
Error Compensation
Mechanisms (1)
• Forward error correction
— Applicable in digital transmission applications
— Typically, ratio of total bits sent to data bits between 2 and 3
— Big overhead
• Capacity one-half or one-third
• Reflects difficulty or mobile wireless environment
• Adaptive equalization
— Applied to transmissions that carry analog or digital information
— Used to combat intersymbol interference
— Gathering the dispersed symbol energy back together into its
original time interval
— Techniques include so-called lumped analog circuits and
sophisticated digital signal processing algorithms
Error Compensation
Mechanisms (2)
• Diversity
— Based on fact that individual channels experience independent
fading events
— Provide multiple logical channels between transmitter and
receiver
— Send part of signal over each channel
— Doesn’t eliminate errors
— Reduce error rate
— Equalization, forward error correction then cope with reduced
error rate
— May involve physical transmission path
• Space diversity
• Multiple nearby antennas receive message or collocated multiple
directional antennas
— More commonly, diversity refers to frequency or time diversity
Frequency Diversity
• Signal is spread out over a larger frequency
bandwidth or carried on multiple frequency
carriers
• E.g. spread spectrum (see chapter 9)
First Generation Analog
• Original cellular telephone networks
• Analog traffic channels
• Early 1980s in North America
• Advanced Mobile Phone Service (AMPS)
—AT&T
• Also common in South America, Australia, and
China
Spectral Allocation In North
America
• Two 25-MHz bands are allocated to AMPS
— One from BS to mobile unit (869–894 MHz)
— Other from mobile to base station (824–849 MHz)
• Bands is split in two to encourage competition
— In each market two operators can be accommodated
• Operator is allocated only 12.5 MHz in each direction
• Channels spaced 30 kHz apart
— Total of 416 channels per operator
• Twenty-one channels allocated for control
• 395 to carry calls
• Control channels are 10 kbps data channels
• Conversation channels carry analog using frequency modulation
• Control information also sent on conversation channels in bursts as
data
• Number of channels inadequate for most major markets
• For AMPS, frequency reuse is exploited
Operation
• AMPS-capable phone has numeric assignment module
(NAM) in read-only memory
— NAM contains number of phone
• Assigned by service provider
— Serial number of phone
• Assigned by the manufacturer
— When phone turned on, transmits serial number and phone
number to MTSO (Figure 14.5)
— MTSO has database of mobile units reported stolen
• Uses serial number to lock out stolen units
— MTSO uses phone number for billing
— If phone is used in remote city, service is still billed to user's
local service provider
Call Sequence
1. Subscriber initiates call by keying in number and
presses send
2. MTSO validates telephone number and checks user
authorized to place call
• Some service providers require a PIN to counter theft
3. MTSO issues message to user's phone indicating traffic
channels to use
4. MTSO sends ringing signal to called party
• All operations, 2 through 4, occur within 10 s of initiating call
5. When called party answers, MTSO establishes circuit
and initiates billing information
6. When one party hangs up MTSO releases circuit, frees
radio channels, and completes billing information
AMPS Control Channels
• 21 full-duplex 30-kHz control channels
—Transmit digital data using FSK
—Data are transmitted in frames
• Control information can be transmitted over
voice channel during conversation
—Mobile unit or the base station inserts burst of data
• Turn off voice FM transmission for about 100 ms
• Replacing it with an FSK-encoded message
—Used to exchange urgent messages
• Change power level
• Handoff
Second Generation CDMA
• Higher quality signals
• Higher data rates
• Support of digital services
• Greater capacity
• Digital traffic channels
— Support digital data
— Voice traffic digitized
— User traffic (data or digitized voice) converted to analog signal for
transmission
• Encryption
— Simple to encrypt digital traffic
• Error detection and correction
— (See chapter 6)
— Very clear voice reception
• Channel access
— Channel dynamically shared by users via Time division multiple access
(TDMA) or code division multiple access (CDMA)
Code Division Multiple Access
• Each cell allocated frequency bandwidth
—Split in two
• Half for reverse, half for forward
• Direct-sequence spread spectrum (DSSS) (see chapter 9)
Code Division Multiple Access
Advantages
• Frequency diversity
— Frequency-dependent transmission impairments (noise bursts, selective
fading) have less effect
• Multipath resistance
— DSSS overcomes multipath fading by frequency diversity
— Also, chipping codes used only exhibit low cross correlation and low
autocorrelation
— Version of signal delayed more than one chip interval does not interfere
with the dominant signal as much
• Privacy
— From spread spectrum (see chapter 9)
• Graceful degradation
— With FDMA or TDMA, fixed number of users can access system
simultaneously
— With CDMA, as more users access the system simultaneously, noise
level and hence error rate increases
— Gradually system degrades
Code Division Multiple Access
• Self-jamming
— Unless all mobile users are perfectly synchronized, arriving
transmissions from multiple users will not be perfectly aligned
on chip boundaries
— Spreading sequences of different users not orthogonal
— Some cross correlation
— Distinct from either TDMA or FDMA
• In which, for reasonable time or frequency guardbands,
respectively, received signals are orthogonal or nearly so
• Near-far problem
— Signals closer to receiver are received with less attenuation than
signals farther away
— Given lack of complete orthogonality, transmissions from more
remote mobile units may be more difficult to recover
RAKE Receiver
• If multiple versions of signal arrive more than one chip interval
apart, receiver can recover signal by correlating chip sequence with
dominant incoming signal
— Remaining signals treated as noise
• Better performance if receiver attempts to recover signals from
multiple paths and combine them, with suitable delays
• Original binary signal is spread by XOR operation with chipping
code
• Spread sequence modulated for transmission over wireless channel
• Multipath effects generate multiple copies of signal
— Each with a different amount of time delay (τ1, τ2, etc.)
— Each with a different attenuation factors (a1, a2, etc.)
— Receiver demodulates combined signal
— Demodulated chip stream fed into multiple correlators, each delayed by
different amount
— Signals combined using weighting factors estimated from the channel
Principle of RAKE Receiver
IS-95
• Second generation CDMA scheme
• Primarily deployed in North America
• Transmission structures different on forward
and reverse links
IS-95 Channel Structure
IS-95 Forward Link (1)
• Up to 64 logical CDMA channels each occupying
the same 1228-kHz bandwidth
• Four types of channels:
—Pilot (channel 0)
• Continuous signal on a single channel
• Allows mobile unit to acquire timing information
• Provides phase reference for demodulation process
• Provides signal strength comparison for handoff
determination
• Consists of all zeros
—Synchronization (channel 32)
• 1200-bps channel used by mobile station to obtain
identification information about the cellular system
• System time, long code state, protocol revision, etc.
IS-95 Forward Link (2)
—Paging (channels 1 to 7)
• Contain messages for one or more mobile stations
—Traffic (channels 8 to 31 and 33 to 63)
• 55 traffic channels
• Original specification supported data rates of up to 9600 bps
• Revision added rates up to 14,400 bps
—All channels use same bandwidth
• Chipping code distinguishes among channels
• Chipping codes are the 64 orthogonal 64-bit codes derived
from 64 × 64 Walsh matrix
Forward Link Processing
• Voice traffic encoded at 8550 bps
• Additional bits added for error detection
— Rate now 9600 bps
• Full capacity not used when user not speaking
• Quiet period data rate as low as 1200 bps
• 2400 bps rate used to transmit transients in background noise
• 4800 bps rate to mix digitized speech and signaling data
• Data transmitted in 20 ms blocks
• Forward error correction
— Convolutional encoder with rate ½
— Doubling effective data rate to 19.2 kbps
— For lower data rates encoder output bits (called code symbols)
replicated to yield 19.2-kbps
• Data interleaved in blocks to reduce effects of errors by spreading
them
Scrambling
• After interleaver, data scrambled
• Privacy mask
• Prevent sending of repetitive patterns
— Reduces probability of users sending at peak power at same
time
• Scrambling done by long code
— Pseudorandom number generated from 42-bit-long shift register
— Shift register initialized with user's electronic serial number
— Output of long code generator is at a rate of 1.2288 Mbps
• 64 times 19.2 kbps
• One bit in 64 selected (by the decimator function)
• Resulting stream XORed with output of block interleaver
Power Control
• Next step inserts power control information in
traffic channel
—To control the power output of antenna
—Robs traffic channel of bits at rate of 800 bps by
stealing code bits
—800-bps channel carries information directing mobile
unit to change output level
—Power control stream multiplexed into 19.2 kbps
• Replace some code bits, using long code generator to
encode bits
DSSS
• Spreads 19.2 kbps to 1.2288 Mbps
• Using one row of Walsh matrix
—Assigned to mobile station during call setup
—If 0 presented to XOR, 64 bits of assigned row sent
—If 1 presented, bitwise XOR of row sent
• Final bit rate 1.2288 Mbps
• Bit stream modulated onto carrier using QPSK
—Data split into I and Q (in-phase and quadrature)
channels
—Data in each channel XORed with unique short code
• Pseudorandom numbers from 15-bit-long shift register
Forward
Link
Transmission
Reverse Link
• Up to 94 logical CDMA channels
—Each occupying same 1228-kHz bandwidth
—Supports up to 32 access channels and 62 traffic
channels
• Traffic channels mobile unique
—Each station has unique long code mask based on
serial number
• 42-bit number, 242 – 1 different masks
• Access channel used by mobile to initiate call, respond to
paging channel message, and for location update
Reverse Link Processing
and Spreading
• First steps same as forward channel
— Convolutional encoder rate 1/3
— Tripling effective data rate to max. 28.8 kbps
— Data block interleaved
• Spreading using Walsh matrix
— Use and purpose different from forward channel
— Data from block interleaver grouped in units of 6 bits
— Each 6-bit unit serves as index to select row of matrix (26 = 64)
— Row is substituted for input
— Data rate expanded by factor of 64/6 to 307.2 kbps
— Done to improve reception at BS
— Because possible codings orthogonal, block coding enhances decision-
making algorithm at receiver
— Also computationally efficient
— Walsh modulation form of block error-correcting code
— (n, k) = (64, 6) and dmin = 32
— In fact, all distances 32
Data Burst Randomizer
• Reduce interference from other mobile stations
• Using long code mask to smooth data out over
20 ms frame
DSSS
• Long code unique to mobile XORed with output
of randomizer
• 1.2288-Mbps final data stream
• Modulated using orthogonal QPSK modulation
scheme
• Differs from forward channel in use of delay
element in modulator to produce orthogonality
—Forward channel, spreading codes orthogonal
• Coming from Walsh matrix
—Reverse channel orthogonality of spreading codes not
guaranteed
Reverse
Link
Transmission
Third Generation Systems
• Objective to provide fairly high-speed wireless
communications to support multimedia, data, and video
in addition to voice
• ITU’s International Mobile Telecommunications for the
year 2000 (IMT-2000) initiative defined ITU’s view of
third-generation capabilities as:
— Voice quality comparable to PSTN
— 144 kbps available to users in vehicles over large areas
— 384 kbps available to pedestrians over small areas
— Support for 2.048 Mbps for office use
— Symmetrical and asymmetrical data rates
— Support for packet-switched and circuit-switched services
— Adaptive interface to Internet
— More efficient use of available spectrum
— Support for variety of mobile equipment
— Flexibility to allow introduction of new services and technologies
Driving Forces
• Trend toward universal personal telecommunications
— Ability of person to identify himself and use any communication system
in globally, in terms of single account
• Universal communications access
— Using one’s terminal in a wide variety of environments to connect to
information services
— e.g. portable terminal that will work in office, street, and planes equally
well
• GSM cellular telephony with subscriber identity module, is step
towards goals
• Personal communications services (PCSs) and personal
communication networks (PCNs) also form objectives for third-
generation wireless
• Technology is digital using time division multiple access or code-
division multiple access
• PCS handsets low power, small and light
Alternative Interfaces (1)
• IMT-2000 specification covers set of radio interfaces for
optimized performance in different radio environments
• Five alternatives to enable smooth evolution from
existing systems
• Alternatives reflect evolution from second generation
• Two specifications grow out of work at European
Telecommunications Standards Institute (ETSI)
— Develop a UMTS (universal mobile telecommunications system)
as Europe's 3G wireless standard
— Includes two standards
• Wideband CDMA, or W-CDMA
– Fully exploits CDMA technology
– Provides high data rates with efficient use of bandwidth
• IMT-TC, or TD-CDMA
– Combination of W-CDMA and TDMA technology
– Intended to provide upgrade path for TDMA-based GSM systems
Alternative Interfaces (2)
• CDMA2000
—North American origin
—Similar to, but incompatible with, W-CDMA
• In part because standards use different chip rates
• Also, cdma2000 uses multicarrier, not used with W-CDMA
• IMT-SC designed for TDMA-only networks
• IMT-FC can be used by both TDMA and FDMA
carriers
—To provide some 3G services
—Outgrowth of Digital European Cordless
Telecommunications (DECT) standard
IMT-2000 Terrestrial Radio
Interfaces
CDMA Design Considerations –
Bandwidth and Chip Rate
• Dominant technology for 3G systems is CDMA
— Three different CDMA schemes have been adopted
— Share some common design issues
• Bandwidth
— Limit channel usage to 5 MHz
— Higher bandwidth improves the receiver's ability to resolve
multipath
— But available spectrum is limited by competing needs
— 5 MHz reasonable upper limit on what can be allocated for 3G
— 5 MHz is enoughfordata rates of 144 and 384 kHz
• Chip rate
— Given bandwidth, chip rate depends on desired data rate, need
for error control, and bandwidth limitations
— Chip rate of 3 Mcps or more reasonable
CDMA Design Considerations –
Multirate
• Provision of multiple fixed-data-rate logical channels to a given user
• Different data rates provided on different logical channels
• Traffic on each logical channel can be switched independently
through wireless fixed networks to different destinations
• Flexibly support multiple simultaneous applications from user
• Efficiently use available capacity by only providing the capacity
required for each service
• Achieved with TDMA scheme within single CDMA channel
— Different number of slots per frame assigned for different data rates
— Subchannels at a given data rate protected by error correction and
interleaving techniques
• Alternative: use multiple CDMA codes
— Separate coding and interleaving
— Map them to separate CDMA channels
Time and Code Multiplexing
Required Reading
• Stallings chapter 14
• Web search on 3G mobile phones
William Stallings
Data and Computer
Communications
7th Edition

Chapter 15
Local Area Network Overview
LAN Applications (1)
• Personal computer LANs
—Low cost
—Limited data rate
• Back end networks
—Interconnecting large systems (mainframes and large
storage devices)
• High data rate
• High speed interface
• Distributed access
• Limited distance
• Limited number of devices
LAN Applications (2)
• Storage Area Networks
— Separate network handling storage needs
— Detaches storage tasks from specific servers
— Shared storage facility across high-speed network
— Hard disks, tape libraries, CD arrays
— Improved client-server storage access
— Direct storage to storage communication for backup
• High speed office networks
— Desktop image processing
— High capacity local storage
• Backbone LANs
— Interconnect low speed local LANs
— Reliability
— Capacity
— Cost
Storage Area Networks
LAN Architecture
• Topologies
• Transmission medium
• Layout
• Medium access control
Topologies
• Tree
• Bus
—Special case of tree
• One trunk, no branches
• Ring
• Star
LAN Topologies
Bus and Tree
• Multipoint medium
• Transmission propagates throughout medium
• Heard by all stations
— Need to identify target station
• Each station has unique address
• Full duplex connection between station and tap
— Allows for transmission and reception
• Need to regulate transmission
— To avoid collisions
— To avoid hogging
• Data in small blocks - frames
• Terminator absorbs frames at end of medium
Frame
Transmission
on Bus LAN
Ring Topology
• Repeaters joined by point to point links in closed
loop
—Receive data on one link and retransmit on another
—Links unidirectional
—Stations attach to repeaters
• Data in frames
—Circulate past all stations
—Destination recognizes address and copies frame
—Frame circulates back to source where it is removed
• Media access control determines when station
can insert frame
Frame
Transmission
Ring LAN
Star Topology
• Each station connected directly to central node
—Usually via two point to point links
• Central node can broadcast
—Physical star, logical bus
—Only one station can transmit at a time
• Central node can act as frame switch
Choice of Topology
• Reliability
• Expandability
• Performance
• Needs considering in context of:
—Medium
—Wiring layout
—Access control
Bus LAN
Transmission Media (1)
• Twisted pair
—Early LANs used voice grade cable
—Didn’t scale for fast LANs
—Not used in bus LANs now
• Baseband coaxial cable
—Uses digital signalling
—Original Ethernet
Bus LAN
Transmission Media (2)
• Broadband coaxial cable
— As in cable TV systems
— Analog signals at radio frequencies
— Expensive, hard to install and maintain
— No longer used in LANs
• Optical fiber
— Expensive taps
— Better alternatives available
— Not used in bus LANs
• All hard to work with compared with star topology twisted pair
• Coaxial baseband still used but not often in new
installations
Ring and Star Usage
• Ring
—Very high speed links over long distances
—Single link or repeater failure disables network
• Star
—Uses natural layout of wiring in building
—Best for short distances
—High data rates for small number of devices
Choice of Medium
• Constrained by LAN topology
• Capacity
• Reliability
• Types of data supported
• Environmental scope
Media Available (1)
• Voice grade unshielded twisted pair (UTP)
—Cat 3
—Cheap
—Well understood
—Use existing telephone wiring in office building
—Low data rates
• Shielded twisted pair and baseband coaxial
—More expensive than UTP but higher data rates
• Broadband cable
—Still more expensive and higher data rate
Media Available (2)
• High performance UTP
— Cat 5 and above
— High data rate for small number of devices
— Switched star topology for large installations
• Optical fiber
— Electromagnetic isolation
— High capacity
— Small size
— High cost of components
— High skill needed to install and maintain
• Prices are coming down as demand and product range increases
Protocol Architecture
• Lower layers of OSI model
• IEEE 802 reference model
• Physical
• Logical link control (LLC)
• Media access control (MAC)
IEEE 802 v OSI
802 Layers -
Physical
• Encoding/decoding
• Preamble generation/removal
• Bit transmission/reception
• Transmission medium and topology
802 Layers -
Logical Link Control
• Interface to higher levels
• Flow and error control
Logical Link Control
• Transmission of link level PDUs between two
stations
• Must support multiaccess, shared medium
• Relieved of some link access details by MAC
layer
• Addressing involves specifying source and
destination LLC users
—Referred to as service access points (SAP)
—Typically higher level protocol
LLC Services
• Based on HDLC
• Unacknowledged connectionless service
• Connection mode service
• Acknowledged connectionless service
LLC Protocol
• Modeled after HDLC
• Asynchronous balanced mode to support
connection mode LLC service (type 2 operation)
• Unnumbered information PDUs to support
Acknowledged connectionless service (type 1)
• Multiplexing using LSAPs
Media Access Control
• Assembly of data into frame with address and
error detection fields
• Disassembly of frame
—Address recognition
—Error detection
• Govern access to transmission medium
—Not found in traditional layer 2 data link control
• For the same LLC, several MAC options may be
available
LAN Protocols in Context
Media Access Control
• Where
— Central
• Greater control
• Simple access logic at station
• Avoids problems of co-ordination
• Single point of failure
• Potential bottleneck
— Distributed
• How
— Synchronous
• Specific capacity dedicated to connection
— Asynchronous
• In response to demand
Asynchronous Systems
• Round robin
— Good if many stations have data to transmit over extended
period
• Reservation
— Good for stream traffic
• Contention
— Good for bursty traffic
— All stations contend for time
— Distributed
— Simple to implement
— Efficient under moderate load
— Tend to collapse under heavy load
MAC Frame Format
• MAC layer receives data from LLC layer
• MAC control
• Destination MAC address
• Source MAC address
• LLS
• CRC
• MAC layer detects errors and discards frames
• LLC optionally retransmits unsuccessful frames
Generic MAC Frame Format
Bridges
• Ability to expand beyond single LAN
• Provide interconnection to other LANs/WANs
• Use Bridge or router
• Bridge is simpler
—Connects similar LANs
—Identical protocols for physical and link layers
—Minimal processing
• Router more general purpose
—Interconnect various LANs and WANs
—see later
Why Bridge?
• Reliability
• Performance
• Security
• Geography
Functions of a Bridge
• Read all frames transmitted on one LAN and
accept those address to any station on the other
LAN
• Using MAC protocol for second LAN, retransmit
each frame
• Do the same the other way round
Bridge Operation
Bridge Design Aspects
• No modification to content or format of frame
• No encapsulation
• Exact bitwise copy of frame
• Minimal buffering to meet peak demand
• Contains routing and address intelligence
— Must be able to tell which frames to pass
— May be more than one bridge to cross
• May connect more than two LANs
• Bridging is transparent to stations
— Appears to all stations on multiple LANs as if they are on one
single LAN
Bridge Protocol Architecture
• IEEE 802.1D
• MAC level
— Station address is at this level
• Bridge does not need LLC layer
— It is relaying MAC frames
• Can pass frame over external comms system
— e.g. WAN link
— Capture frame
— Encapsulate it
— Forward it across link
— Remove encapsulation and forward over LAN link
Connection of Two LANs
Fixed Routing
• Complex large LANs need alternative routes
—Load balancing
—Fault tolerance
• Bridge must decide whether to forward frame
• Bridge must decide which LAN to forward frame
on
• Routing selected for each source-destination
pair of LANs
—Done in configuration
—Usually least hop route
—Only changed when topology changes
Bridges and
LANs with
Alternative
Routes
Spanning Tree
• Bridge automatically develops routing table
• Automatically update in response to changes
• Frame forwarding
• Address learning
• Loop resolution
Frame forwarding
• Maintain forwarding database for each port
—List station addresses reached through each port
• For a frame arriving on port X:
—Search forwarding database to see if MAC address is
listed for any port except X
—If address not found, forward to all ports except X
—If address listed for port Y, check port Y for blocking
or forwarding state
• Blocking prevents port from receiving or transmitting
—If not blocked, transmit frame through port Y
Address Learning
• Can preload forwarding database
• Can be learned
• When frame arrives at port X, it has come form
the LAN attached to port X
• Use the source address to update forwarding
database for port X to include that address
• Timer on each entry in database
• Each time frame arrives, source address
checked against forwarding database
Spanning Tree Algorithm
• Address learning works for tree layout
—i.e. no closed loops
• For any connected graph there is a spanning
tree that maintains connectivity but contains no
closed loops
• Each bridge assigned unique identifier
• Exchange between bridges to establish spanning
tree
Loop of Bridges
Layer 2 and Layer 3 Switches
• Now many types of devices for interconnecting
LANs
• Beyond bridges and routers
• Layer 2 switches
• Layer 3 switches
Hubs
• Active central element of star layout
• Each station connected to hub by two lines
— Transmit and receive
• Hub acts as a repeater
• When single station transmits, hub repeats signal on outgoing line
to each station
• Line consists of two unshielded twisted pairs
• Limited to about 100 m
— High data rate and poor transmission qualities of UTP
• Optical fiber may be used
— Max about 500 m
• Physically star, logically bus
• Transmission from any station received by all other stations
• If two stations transmit at the same time, collision
Hub Layouts
• Multiple levels of hubs cascaded
• Each hub may have a mixture of stations and other hubs
attached to from below
• Fits well with building wiring practices
— Wiring closet on each floor
— Hub can be placed in each one
— Each hub services stations on its floor
Two Level Star Topology
Buses and Hubs
• Bus configuration
—All stations share capacity of bus (e.g. 10Mbps)
—Only one station transmitting at a time
• Hub uses star wiring to attach stations to hub
—Transmission from any station received by hub and
retransmitted on all outgoing lines
—Only one station can transmit at a time
—Total capacity of LAN is 10 Mbps
• Improve performance with layer 2 switch
Shared Medium Bus and Hub
Shared Medium Hub and
Layer 2 Switch
Layer 2 Switches
• Central hub acts as switch
• Incoming frame from particular station switched
to appropriate output line
• Unused lines can switch other traffic
• More than one station transmitting at a time
• Multiplying capacity of LAN
Layer 2 Switch Benefits
• No change to attached devices to convert bus LAN or
hub LAN to switched LAN
• For Ethernet LAN, each device uses Ethernet MAC
protocol
• Device has dedicated capacity equal to original LAN
— Assuming switch has sufficient capacity to keep up with all
devices
— For example if switch can sustain throughput of 20 Mbps, each
device appears to have dedicated capacity for either input or
output of 10 Mbps
• Layer 2 switch scales easily
— Additional devices attached to switch by increasing capacity of
layer 2
Types of Layer 2 Switch
• Store-and-forward switch
— Accepts frame on input line
— Buffers it briefly,
— Then routes it to appropriate output line
— Delay between sender and receiver
— Boosts integrity of network
• Cut-through switch
— Takes advantage of destination address appearing at beginning
of frame
— Switch begins repeating frame onto output line as soon as it
recognizes destination address
— Highest possible throughput
— Risk of propagating bad frames
• Switch unable to check CRC prior to retransmission
Layer 2 Switch v Bridge
• Layer 2 switch can be viewed as full-duplex hub
• Can incorporate logic to function as multiport bridge
• Bridge frame handling done in software
• Switch performs address recognition and frame
forwarding in hardware
• Bridge only analyzes and forwards one frame at a time
• Switch has multiple parallel data paths
— Can handle multiple frames at a time
• Bridge uses store-and-forward operation
• Switch can have cut-through operation
• Bridge suffered commercially
— New installations typically include layer 2 switches with bridge
functionality rather than bridges
Problems with Layer 2
Switches (1)
• As number of devices in building grows, layer 2 switches
reveal some inadequacies
• Broadcast overload
• Lack of multiple links
• Set of devices and LANs connected by layer 2 switches
have flat address space
— Allusers share common MAC broadcast address
— If any device issues broadcast frame, that frame is delivered to
all devices attached to network connected by layer 2 switches
and/or bridges
— In large network, broadcast frames can create big overhead
— Malfunctioning device can create broadcast storm
• Numerous broadcast frames clog network
Problems with Layer 2
Switches (2)
• Current standards for bridge protocols dictate no closed
loops
— Only one path between any two devices
— Impossible in standards-based implementation to provide
multiple paths through multiple switches between devices
• Limits both performance and reliability.
• Solution: break up network into subnetworks connected
by routers
• MAC broadcast frame limited to devices and switches
contained in single subnetwork
• IP-based routers employ sophisticated routing
algorithms
— Allow use of multiple paths between subnetworks going through
different routers
Problems with Routers
• Routers do all IP-level processing in software
—High-speed LANs and high-performance layer 2
switches pump millions of packets per second
—Software-based router only able to handle well under
a million packets per second
• Solution: layer 3 switches
—Implementpacket-forwarding logic of router in
hardware
• Two categories
—Packet by packet
—Flow based
Packet by Packet or
Flow Based
• Operates insame way as traditional router
• Order of magnitude increase in performance
compared to software-based router
• Flow-based switch tries to enhance performance
by identifying flows of IP packets
—Same source and destination
—Done by observing ongoing traffic or using a special
flow label in packet header (IPv6)
—Once flow is identified, predefined route can be
established
Typical Large LAN Organization
• Thousands to tens of thousands of devices
• Desktop systems links 10 Mbps to 100 Mbps
— Into layer 2 switch
• Wireless LAN connectivity available for mobile users
• Layer 3 switches at local network's core
— Form local backbone
— Interconnected at 1 Gbps
— Connect to layer 2 switches at 100 Mbps to 1 Gbps
• Servers connect directly to layer 2 or layer 3 switches at
1 Gbps
• Lower-cost software-based router provides WAN
connection
• Circles in diagram identify separate LAN subnetworks
• MAC broadcast frame limited to own subnetwork
Typical
Large
LAN
Organization
Diagram
Required Reading
• Stallings chapter 15
• Loads of info on the Web