2,A - the DCS lab.
Download
Report
Transcript 2,A - the DCS lab.
Course Syllabus (I)
Lecturer : Gihwan Cho
office : room 607 (voice 3437)
[email protected]
office hour : Wed. 11:00 ~ 14:00 or by appointment
Teaching assistant : Woosuk Cha
office : Distributed Computing System Lab. (room 603)
[email protected]
office hour : Tue: 13:00 ~ 14:00, Wed. 11:00 ~ 14:00
Text Books
Andrew S. Tannenbaum, Computer Networks, 3rd edition,
Prentice Hall, ISBN 0-13-349945-6
D. Comer, Internetworking with TCP/IP, 3rd edition, Prentice
Hall, ISBN 0-13-227836-7
Computer Communications
DCS Lab.
ghcho
2001 Fall
1
Courses Syllabus (II)
Course objectives
understanding of the basic principles of computer networks
understand the Internet and its protocols
then, you are expected to be able to describe in detail the
operations of Internet protocols
Outline
overall introduction of computer network, physical layer,
datalink layer and error, flow control, multiple access
sublayer, network layer and routing algorithms, transport
layer and congestion control, TCP/IP protocols, DNS,
network programming (optional)
Expected works
1 project (network simulations – two persons base)
2 examinations (mid, final), 2 reports (problems in exercise)
Computer Communications
DCS Lab.
ghcho
2001 Fall
2
Courses Syllabus (III)
Lecture information
cs.chonbuk.ac.kr/~ghcho/courses/comnet.html
Policy on missed examinations and project quizzes
possible to have a make-up examination
not possible to have a make-up project quiz
Computer accounts
required to have an account at jiri.chonbuk.ac.kr
if you do not already have it, see TA
Grading
project 20, exam. 70(30, 30), reports 10(5, 5), presents 10
students are not majored in CS will be separately evaluated
from those of majored in CS
Computer Communications
DCS Lab.
ghcho
2001 Fall
3
Lecture Topic 1
Overall Introduction of
Computer Networks
What good is a computer network
Network technologies
Network software
ISO/OSI 7 layer model
TCP/IP model
Network standardization
Computer Communications
DCS Lab.
ghcho
2001 Fall
4
Introduction (I)
Old model was the Mainframe based computer center
current model of computing environment is an interconnected
collection of autonomous computers
We call such a system as Computer Network (CN)
a computer network is a set of nodes that are interconnected to
permit the exchange of information
Computer Communications
DCS Lab.
ghcho
2001 Fall
5
Introduction (I)
An CN is necessary for a Distributed System but is not the same in
a distributed system, in which the existence of multiple
autonomous systems is transparent
What good is a CN
economic and technical Issues: resource sharing; reliability;
cost savings (client/server); scalability; communications (email)
consumer issues: telecommuting; interactive entertainment and
video on demand; socio-political interaction; selling stuff
yucky issues: hate speech; snooping/employee monitoring;
misinformation; ownership & copyright; theft & hacking
Computer Communications
DCS Lab.
ghcho
2001 Fall
6
Network Technology
A network is a carrier of information between 2 or more entities
Generally two types of transmission technology:
broadcast
single channel is shared by all the machines on the
network
messages sent by one node are received by all
use special address field in message to specify target of
comm.(broadcast/multicast)
usually small (geographically) networks
point-to-point
connections between individual pairs of machines
message may pass through many pairs of point-to-point
connections to get from source to destination
often machines may have multiple point-to-point
connections
large (geographically) networks..
Computer Communications
DCS Lab.
ghcho
2001 Fall
7
Classes of Networks : LAN
LAN (Local Area Network)
maximum distance not more than a few kms
ownership by a single organization
transmission speed of at least several Mbps (tens to
hundreds are economical)
often broadcast, shared media based
some widely used standards include:
IEEE 802.3 - Ethernet
IEEE 803.5 - Token ring
FDDI
ATM
an important issue in broadcast LANs is the allocation of the
shared channel (media access control)
control may be static (time division multiplexing) or dynamic
(contention or arbitration)
Computer Communications
DCS Lab.
ghcho
2001 Fall
8
LAN : Two Broadcast Networks
Computer Communications
DCS Lab.
ghcho
2001 Fall
9
Classes of Networks : MAN
MAN (Metropolitan Area Network)
distances between 5 and 50 kms
data rate above 1 Mbps
standards: IEEE 802.6 DQDB, FDDI, and ATM
Computer Communications
DCS Lab.
ghcho
2001 Fall
10
Classes of Networks : WAN
WAN (Wide Area Network)
spans entire states or countries
data rate of 1.544, and 45 Mbps common
higher data rates are available with the wide deployment of
ATM backbone networks
often owned by multiple organizations
usually separate communications functions from application
functions
transmission lines: circuits, channels or trunks
switching elements : Intermediate Systems, Packet
Switching Node, Data Switching Exchange, Router, etc.
Intermediate systems store a complete packet before
forwarding it : store-and-forward; packet switched; point-topoint network
Computer Communications
DCS Lab.
ghcho
2001 Fall
11
WAN : Host and the Subnet
Computer Communications
DCS Lab.
ghcho
2001 Fall
12
WAN : Network Topologies
Computer Communications
DCS Lab.
ghcho
2001 Fall
13
Classes of Networks : Wireless Networks
Wireless Network
wireless comm. has been used from 1901, by G. Marconi,
but its technology did not known, why?
channel multiplexing : AMPS, TDMA, CDMA
two up-coming information technologies invent a new
computing paradigm, so mobile computing
mobile hosts : PDA, palm-top, notebook
mobile packet data : IMT 2000, UMTS, GPRS
permit user to access information anytime, anywhere
one-line mobility vs. off-line mobility
must provide seamless connectivity
actually it would be based a fixed network, possibly Internet,
to be a general information network
why wireless ? - timely news, and way too much of it
- information where people want to be
Computer Communications
DCS Lab.
ghcho
2001 Fall
14
Classes of Networks : Internetworks
Internetworks : an interconnected network of networks
direct links : a full-mesh of point-to-point links => n(n-1)/2 links
indirect links : bus, star, ring, tree …
unlike a single WAN, internetworks often interconnect different,
incompatible networks, so an abbreviated word, Internet
use special types of intermediate systems called Gateways
cf) repeater, bridge, router, gateway
Internet
Computer Communications
DCS Lab.
ghcho
2001 Fall
15
Network Software
Network software is highly structured
This technique has been immensely successful
The key is Layered design
each layer provides a service to the layer above
each layer hides details of how the service is provided to the
layer above
the Nth layer on one machine talks to or interacts with the Nth
layer on another machine
Conventions and rules governing this interaction are specified
by the Layer N Protocol
a protocol is an agreement about how communications are
to proceed, without a protocol, communication can be
difficult or even impossible
e.g. telephone conversation, postal addresses
Computer Communications
DCS Lab.
ghcho
2001 Fall
16
Network Hierarchy : Protocols
Computer Communications
DCS Lab.
ghcho
2001 Fall
17
Network Software : Protocols (Cont.)
Information is not actually transferred directly between peer
layer N entities
peer layer N entities carry on a virtual communication using
the services of the layers below
layer N passes data and control information down to (or
receives data and control from) layer N-1 until the physical
medium is reached
Interfaces exist between each layer, it defines which primitive
functions and services layer N-1 provides to layer N
We want layers to:
perform a well defined, logically related set of functions
minimize the amount of infor. need to pass between layers
keep interfaces “clean” to allow easy and transparent
replacement of layers
Computer Communications
DCS Lab.
ghcho
2001 Fall
18
Network Software : Layering
The set of protocols and layers together make up the Network
Architecture
a network architecture Specification must provide enough
information to allow implementation in hardware/software
implementation specific details are not part of the architecture
and should be irrelevant for inter-operation
with one protocol per layer we have a Protocol Stack
Layering is used in other software, e.g. UNIX OS
For network software the important difference is that we are not
allowed to violate layering (layer 5 cannot directly access layer 1)
For network software it’s important layers don’t peek into headers
of other layers and rely on protocol data of other layers
Computer Communications
DCS Lab.
ghcho
2001 Fall
19
Network Software : Layering (Cont.)
Computer Communications
DCS Lab.
ghcho
2001 Fall
20
The Benefit of Layered Protocols
The network architectures, protocols and protocol stacks are the
fundamentals of computer networks
multilayer communications protocols allow:
ready adaptation of successful protocols to new
technology (prevent obsolescence)
migration of protocols from software implementation
(slow) to hardware (fast) as they evolve
separate data and control information
support differing levels of abstraction (message, packet,
frame) with different sizes
allow segmentation of large messages
peer process abstraction facilitates reduction of difficult
design task (a network architecture) into smaller
manageable tasks (protocol layer architecture)
typically lower layer protocols of “network software” are
implemented in silicon (hardware)
Computer Communications
DCS Lab.
ghcho
2001 Fall
21
Understanding Services and Protocols
The protocol is a set of rules about the format and meaning of
data units exchanged by the peer entities within a layer
The service is a set of primitives (operations) that a layer
provider to the layer above it
The interface tells the processes above it how to access it, that
is, it specifies what parameters are and what results to expect
protocol is used by entity to implement services
protocol and/or it’s implementation can change and as long
as the service (interface) remains unchanged higher layers
are happy and continue to work
like in abstract data types or object orientation we decouple
interface and implementation
Computer Communications
DCS Lab.
ghcho
2001 Fall
22
Network Software : Design Issues
Addressing and Routing
Data transfer : simplex, half duplex, full duplex
Connection management : # of logical channels per connection
Error recovery : error detection, correction, retransmission
Message ordering : full, partial, causal
Flow control / Rate control
Assembly / Disassembly
Multiplexing
TDM (Time Division Multiplexing)
FDM (Frequency Division Multiplexing)
CDM (Code Division Multiplexing)
Computer Communications
DCS Lab.
ghcho
2001 Fall
23
Network Software : QoS
Quality of Service
Computer Communications
DCS Lab.
ghcho
2001 Fall
24
The ISO/OSI Reference Model
Developed by the International Standards Organization (ISO) to
facilitate the intern’l standardization of communications protocols
ISO basic reference model for Open Systems Interconnect
(hence: ISO/OSI), started in the mid-1970’s
the reference model itself is not a network architecture
(doesn’t specify any protocols or services)
ISO also developed network architecture standards
No assumptions are made regarding:
programming language bindings
operating system bindings
applications programming interfaces
Biggest problems
very long time to complete the model and protocol standards
very hard to understand the detailed standards
difficult (expensive) to get the standards documents
Computer Communications
DCS Lab.
ghcho
2001 Fall
25
ISO/OSI 7-Layer Reference Model
Computer Communications
DCS Lab.
ghcho
2001 Fall
26
OSI Layer 1 : Physical Layer
Primary function is transmitting raw bits over a physical
communications channel
Primary design issues include: mechanical, electrical, coding,
physical characteristics
how many pins in the connector
what voltage represents a “1” versus a “0”
etc.
By “raw bits” we mean there is no interpretation of the bits stream of bits in and bits out
Computer Communications
DCS Lab.
ghcho
2001 Fall
27
OSI Layer 2 : Data Link Layer
Primary function is to make Layer 1 into what appears to be a
channel free of undetected errors
Deals with data in chunks (typically 100s-1000s of bytes)
generally called Frames
This layer must create/recognize frame boundaries
remember - physical layer does not care
often requires special bit patterns to signal boundaries
may have to deal with possibility of pattern appearing in data
Among the key issues dealt with are:
error handling (e.g. corrupted frame)
flow control
providing various qualities of service
For Broadcast networks a key issue is controlling access to the
channel:
use a sub-layer called the Media Access Control (MAC)
Computer Communications
DCS Lab.
ghcho
2001 Fall
28
OSI Layer 3 : Network Layer
Primary function is control the operation of the subnet (layers
below)
Among the key issues dealt with are:
how routing packets from source to destination through the
network (or multiple networks) using static or dynamic
routing algorithms
controlling congestion in the subnet
accounting functions (for billing)
translating between protocols across heterogeneous
networks (address, packet size, …)
concerned with addressing
Computer Communications
DCS Lab.
ghcho
2001 Fall
29
OSI Layer 4 : Transport Layer
First end-to-end layer
Uses the network to (most often) provide higher layers with a
connection oriented, reliable, error free channel that delivers
messages (or byte stream) in order
May provide other types of transport services
Generally requires address (or naming)
May also perform flow control
Often performs multiplexing of multiple transport connections
over one or more network connections
Computer Communications
DCS Lab.
ghcho
2001 Fall
30
OSI Layer 5, 6 : Session, Presentation
Session layer
sort of an unwanted layer, this layer is usually very thin and
little more than a pass through for most protocols
manages dialog control (e.g. may manage who’s turn to talk
in a high-level half-duplex protocol)
manages synchronization of transactions which may need to
be able to roll back in case of a crash
Presentation layer
rather than being concerned with moving information the
presentation layer is concerned with the interpretation of
information representation
ensures that the syntax and meaning is the same for each
participant in a communication
provides for standard representation and may provide
capabilities for conversion of data
Computer Communications
DCS Lab.
ghcho
2001 Fall
31
OSI Layer 7 : Application Layer, and
The layer where end-user applications live
All the rest of the layers exist to support these applications
Layering exists so we can move these around to different
machines, and so they can communicate across any platforms Open Systems Interconnect
Review: functions of the OSI layers
layer 1 (physical): transmission of bits
layer 2 (data link): transmission of frames on one given link
layer 3 (network): routing of packets through the network
layer 4 (transport): end-to-end delivery of messages
layer 5 (session): end-to-end conversation, synchronization
layer 6 (presentation): formatting, encryption, and
compression
layer 7 (application): user applications
Computer Communications
DCS Lab.
ghcho
2001 Fall
32
TCP/IP Protocol Suite
Advanced Research Project Agency (ARPA) of DoD sponsored
the development of ARPANET in 1970s.
TCP/IP has been adopted as the ARPANET protocol suite
TCP/IP became popular by the inclusion of this protocol in BSD
Unix system
Transport layer-TCP
provides fully reliable, connection-oriented service
byte-stream transmission
Another transport layer-UDP
provides unreliable, connectionless service
user datagram (message) transmission
Network layer- IP
IP provides datagram service
it is connectionless unreliable service
IP handles routing
Computer Communications
DCS Lab.
ghcho
2001 Fall
33
TCP/IP Suite and OSI 7-Layer Model
Computer Communications
DCS Lab.
ghcho
2001 Fall
34
Comparison of the Two Reference Models
Computer Communications
DCS Lab.
ghcho
2001 Fall
35
A Critique of the OSI Model & Protocols
Bad technology
session, presentation (small) vs. data link, network (big)
IBM SNA (System Network Architecture) 7 layers
complexity of model (services, protocol spec.) : difficult to
implement, inefficient in operation
addressing, flow control, error control are repeated in each layer
inappropriate features in particular layers: eg. virtual terminal
handling -> application layer
ignore the importance of connectionless services & protocols
telecommunications approach ; eg, indication primitive
Bad implementation
huge & slow implementations due to complexity of the model
and protocols => bad impression
good first impl. of TCP/IP in Berkeley UNIX => good impression
Bad politics
Computer Communications
DCS Lab.
ghcho
2001 Fall
36
A Critique of the TCP/IP Model
Bad software engineering
spec. and implementation go hand-in-hand
not distinguish service, interface, and protocol
Not at all general model
Host-to-network layer
not a layer but an interface between the network and data
link layer
Not distinguish the physical and data link layers
Ad hoc protocols
OSI -> model
TCP/IP -> protocol
Computer Communications
DCS Lab.
ghcho
2001 Fall
37
Network Standardization (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
38
Network Standardization (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
39
Network Standardization (III)
Computer Communications
DCS Lab.
ghcho
2001 Fall
40
Lecture Topic 2
Physical Layer
Physical layer functions
Support for framing of information
Analog and digital transmission
Transmission media
Switching techniques
Integrated Services Digital Network (ISDN)
xDSL: x Digital Subscriber Line Technologies
Asynchronous Transfer Mode (ATM) Networks
Computer Communications
DCS Lab.
ghcho
2001 Fall
41
Hardware Building Blocks in
Computer Network
Computer Communications
DCS Lab.
ghcho
2001 Fall
42
Physical/Data Link Layer Interface
Sender
Receiver
NL
HDR
DLL
Frame
ACK
PL
HDR
Transmitted Bits
Computer Communications
DCS Lab.
ghcho
2001 Fall
43
Synchronization and Framing
The simplest way to communicate the bit stream is to use
unipolar modulation:
bits
1 0 1 1 0 0 1
T
received
signal
T2
T1
time
Issues are:
how to keep the correct pace when reading the bits
how to find the start time and the end time
Use some timing mechanism at the receiver so that it reads the
bits every T seconds starting from T1 + T/2
Problem: receiver clock cannot tick exactly every T seconds;
timing may slowly drift, or fall in the wrong
Computer Communications
DCS Lab.
ghcho
2001 Fall
44
Framing with Start-Stop Bits
Solution: specify a short maximum length for the bit sequences
(this is called asynchronous transmission)
START
bit=0
line
idle
STOP
bit=1
N data bits = 0 or 1
T
START bit indicates the beginning of a character
STOP bit concludes the transmission of a character,
equivalent to a return to an idle state
Computer Communications
DCS Lab.
ghcho
2001 Fall
45
Line Coding
Synchronization can be achieved via self-synchronizing codes;
Manchester encoding is a widely used self-synchronizing code
1
0
0
1
1
0
1
Bits
+V
time
-V
Bit 1 is indicated by an upward transition in the middle of the bit time,
Bit 0 is indicated by a downward transition
Computer Communications
DCS Lab.
ghcho
2001 Fall
46
Analog and Digital Transmission
Definition
analog signal : represents information with a continuously
varying electromagnetic wave, e.g. telephone, TV
digital signal : represents information with a sequence of
voltage pulses, e.g. computer
carrier signal : an analog electromagnetic wave that carries
information
modulation : the process of encoding onto a carrier signal
A/D conversion
converts an analog signal into a digital signal,
required 3 steps
• sampling
• quantization
• coding
Computer Communications
DCS Lab.
ghcho
2001 Fall
47
Sending Digital Signal using an
Analog Carrier
AM, FM, PM
Computer Communications
DCS Lab.
ghcho
2001 Fall
48
Sampling
Computer Communications
DCS Lab.
ghcho
2001 Fall
49
Quantization
Computer Communications
DCS Lab.
ghcho
2001 Fall
50
Coding
Computer Communications
DCS Lab.
ghcho
2001 Fall
51
Transmission Media : Twisted Pair Copper
Very common media is twisted pair
usually 2 copper wires (~ 1mm diameter) shielded (STP)
or unshielded (UTP)
twisting reduces tendency to become an antenna
ubiquitous because of the telephone system
can be used for analog or digital transmission
usually require amplifiers (for analog) or repeaters (digital)
every few kilometers
bandwidth related to distance and thickness but Mbps are
possible
Computer Communications
DCS Lab.
ghcho
2001 Fall
52
Transmission Media : Baseband Coaxial
Coaxial cable (Baseband)
“Baseband” => single digital channel
50 Ohm cable usually used for digital transmission
shielding provides high bandwidth and good noise
immunity
1 ~ 2 Gbps on a 1 kilometer cable
now largely replaced by fiber optics on long-haul route
used for cable television and some original 10 base
Ethernet and for 10 base T (Thinwire)
Computer Communications
DCS Lab.
ghcho
2001 Fall
53
Transmission Media : Broadband Coaxial
Coaxial cable (Broadband)
75 Ohm used for analog transmission
can transmit 300 MHz for long distances (100 km)
digital signal requires analog transceivers
divides bandwidth into multiple channels
channels can transmit TV, audio or digital and mix digital and
analog transmissions (6Mhz for a TV channel)
inferior to baseband but lots of cable in place due to historical
development of broadcasting (so analog amplifiers are required)
directional transmission => 2 cables (transmit and receive) in a
tree structure, or
a single cable with two frequency bands : different ways to
allocate frequency bands
- subsplit 5-30 MHz for inbound and 40-300 MHz for outbound
- midsplit 5-116 MHz for inbound and 168-300 MHz for outbound
Computer Communications
DCS Lab.
ghcho
2001 Fall
54
Transmission Media : Fiber Optics (I)
Fiber Optic cable
properties of refraction allow light to be trapped inside a
slender glass strand and propagate for very long
distances with little loss
may use LED(Light Emitting Diode)s (cheaper - usually
with multi-mode) or Lasers (expensive - usually with
single mode)
depending on diameter of fiber and wavelength of light
there may be multiple paths for a given light ray
depending on incident angle of refraction (multi-mode
fiber - usually 62.5 micron core) or there may be just a
single path (single-mode fiber - usually 8 micron core)
multi-mode is cheaper and more common and gives up to
500 Mbps at 2-4 kilometers
Computer Communications
DCS Lab.
ghcho
2001 Fall
55
Transmission Media : Fiber Optics (II)
single-mode is more expensive and gives up to 2 Gbps to
about 30 kilometers
attenuation depends on wavelength of light and there are
3 nice windows (.85, 1.3 and 1.55 micron - most devices
use first or second)
light disperses (signal smears out) especially in multimode since individual rays take paths of different lengths
fiber requires electro-optics for conversion of electrical
signals to/from optical signals
often use Active Repeaters and ring topology or passive
star topology to distribute signals (divides signal power
among the arms)
fiber is immune to thermal noise
Computer Communications
DCS Lab.
ghcho
2001 Fall
56
Modems
Due to attenuation, delay distortion, and noise, it is
undesirable to send wide range frequencies (square waves) baseband signaling (known as DC signaling)
Modulation is used to solve DC signaling problem and uses a
1000-2000 Hz as a carrier signal
Amplitude Modulation, Frequency Modulation, (frequency
shift keying), phase modulation, etc.
Computer Communications
DCS Lab.
ghcho
2001 Fall
57
RS-232 and RS-449
It is a physical protocol to interface computer with modems
specify mechanical, electrical, functional, and procedural
interface
Protective Ground (1)
Transmit (2)
Receive (3)
Computer
or
Terminal
Request to Send (4)
Clear to Send (5)
Modem
Data Set Ready (6)
Common Return (7)
Carrier Detect (8)
Date Terminal Ready (20)
Computer Communications
DCS Lab.
ghcho
2001 Fall
58
Switching Basis (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
59
Switching Basis (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
60
Circuit Switching (I)
Circuit Switching
communications is done via a dedicated path between end
stations
this path is a sequence of links between intermediate
nodes
three phases are required:
Circuit Establishment (Call Setup) : end station A
requests connection to end station B results in
sequence of connection establishments
Data Transfer : information is transmitted in analog or
binary format
Circuit Disconnection : sequence of disconnection of
individual links
Computer Communications
DCS Lab.
ghcho
2001 Fall
61
Circuit Switching (II)
Need circuit setup end-to-end before any data transfer can
take place
disadvantage: setup may introduce appreciable delay
advantage: after set up there is usually low delay and little
variance in delay - effectively a wire
Characteristics good for voice so wide spread because of
voice and the PSTN
Not optimal for many digital applications but can be expected
to continue to be widely used in WANs
As you might suspect a key device is the Switch!
generally digital in modern switches
several different technologies for switching
carrier charges based on distance and call time
Computer Communications
DCS Lab.
ghcho
2001 Fall
62
Switches
NETWORK
INTERFACE
Function of the switch is to provide a
transparent signal path between
attached devices.
Control Unit
Control unit: 1) establishes
connections (usually at request of
connected devices) 2) maintains the
connection (may require continuous
manipulation of switching elements
depending on multiplexing used) and
3) handle disconnection
Digital
FULL
DUPLEX
LINES
Switch
SWITCH
Computer Communications
DCS Lab.
ghcho
2001 Fall
63
Space Division Switches (I)
8 x 8 Crossbar switch
1
2
3
4
5
6
Full Duplex Input
channels
7
8
Example of Space-division
Swtich - signal paths are
phsyically divided
1
Disadvantages: number of
crosspoints grows with N 2
costly for large switches
2
3
4
5
Failure of crosspoint element
eliminates possibility of
connecting associated nodes
6
7
8
Inefficient use of crosspoints
even when all lines are used
Full Duplex Output
channels
Computer Communications
DCS Lab.
ghcho
2001 Fall
64
Space Division Switches (II)
2x5
5x2
1
1
2
2
3
3
4
4
5
5
2x2
Use Multi-stageswitches to
overcome inefficiencies of
simple crossbar
Advantages over singlestage switching matrix
include:
Number of crosspoint
elements reduced improving utilization
2x2
1
1
2
2
3
3
4
4
5
5
5x2
2x5
Three stage Space-division switch
Computer Communications
DCS Lab.
ghcho
Multiple paths to connect
two given end points improves reliability
Disadvantage: Requires
more complex control
May introduce blocking
2001 Fall
65
Packet Switches (I)
Packet Switching
unlike voice traffic, computer interactions usually involve
long periods of idle time - making circuit switching
inefficient
circuit switching requires the two end stations to talk at the
same data rate
a solution to these problems is to break up the
communication into chunks with a relatively small
maximum size - will store temporarily at intermediate
system
now we must add some control information to each packet
so it can be routed through the network
send the packet through sequence to intermediate
systems to get from source to destination
Computer Communications
DCS Lab.
ghcho
2001 Fall
66
Packet Switches (II)
advantages over circuit switching include:
dynamic sharing of circuits rather than dedication of
circuit to single connection increases efficiency of
utilization
eliminates idle time slots by queuing up available
packets
other advantages over circuit switching include:
end stations can operate with connections of different
data rates
circuit switched network will likely block under heavy
load but packet switching we can still stuff packets into
the network but delay increases
we can prioritize packets for lower delay
charge per packet, byte or bit independent of distance
Computer Communications
DCS Lab.
ghcho
2001 Fall
67
Packet Switches Techniques
Datagram
each packet is independent of others
each may take a different path through the network so may
arrive out of order
some may be lost and possibly some may be duplicated
intermediate system make a routing decision on each
packet
call setup time avoided
Virtual Circuit
a call setup process establishes a preplanned route
through the network
all packets follow the same route (hence the name)
intermediate systems make routing decision only on call
setup packets
better support for sequencing and error control
Computer Communications
DCS Lab.
ghcho
2001 Fall
68
Comparison of Switching Techniques
A
x
y
B
Circuit Swtiching
Computer Communications
A
x
y
A
B
ghcho
2001 Fall
y
B
Datagram Pkt Switch
Virtual Circuit Pkt Switch
DCS Lab.
x
69
Narrowband ISDN
Mid 1980’s the telecomm’s decided to invent the replacement
for the analog phone system in anticipation of customer
demand for end-to-end digital service
Since it was to provide integrated voice and non-voice service
they called it Integrated Services Digital Network - ISDN
use on a limited set of standardized facilities
support for both circuit switching and packet switching
based on 64 kbps connections - fundamental building
block of ISDN (hence “narrowband”)
provide intelligent services
layered architecture which can be mapped to OSI
variety of physical configurations
Computer Communications
DCS Lab.
ghcho
2001 Fall
70
Conceptual view of ISDN
Packet
Switched
Network
Telephone
Circuit
Switched
Network
Desktop System
Digital "Pipe"
Customer ISDN Equipement
Other
Network
ISDN Central Office
PBX
Databases
Mac II
Router
Other
Services
Laser printer
IBM Compatible
Computer Communications
DCS Lab.
ghcho
2001 Fall
71
ADSL
It provides up to 7Mbps downstream
up to 500 Kbps downstream traffice
POTS
Downstream Channel
Upstream Channel
3.4
Computer Communications
30
DCS Lab.
138
ghcho
2001 Fall
1104
(KHz)
72
ADSL Technologies
ADSL applications
VOD, home shopping, internet access, remote LAN
access, multimedia access
ADSL speed v.s. distance
18,000 feet
16,000 feet
12,000 feet
9,000 feet
Computer Communications
1.544 Mbps (T1)
2.048 Mbps (E1)
6.312 Mbps (DS2)
8.448 Mbps
DCS Lab.
ghcho
2001 Fall
73
B-ISDN
A single physical network integrates variety of services
The Broadband Integrated Services Digital Network (BISDN)
was defined by CCITT to meet this objective
Problems
Quality of Service (QoS) requirements for services widely
different
- voice : real time (low delay jitter), tolerates occasional
losses
- data : usually no real-time requirements, error-free,
guaranteed delivery
- video : high bandwidth, low delay and jitter
traffic characteristics also widely different
certain applications require synchronization among
multiple traffic streams
Computer Communications
DCS Lab.
ghcho
2001 Fall
74
Services and Protocol Based ATM
and AAL
CO data
applications
(AAL type 3, 5)
CL data
applications
(AAL type 4)
CO AAL
CS sublayer
CL AAL
CS sublayer
CBR
applications
(AAL type 1)
CBR AAL
CS sublayer
VBR
applications
(AAL type 2)
VBR AAL
CS sublayer
Segmentation and Reassembly AAL Sublayer
ATM Layer
Physical Layer (SONET / SDH)
Computer Communications
DCS Lab.
ghcho
2001 Fall
75
ATM Layer
8 bits
Header (5 bytes)
53 bytes
Payload (48 bytes)
cell multipexing and demultiplexing
extracts / attaching headers
Generic Flow Control (GFC)
Virtual Path Identifier (VPI)
Virtual Circuit Identifier (VCI)
Payload Type Identifier (PTI)
Cell Loss Priority (CLP)
Header Error Check (HEC)
(a) ATM cell format
8 7 6 5
4 3 2 1
GFC
VPI
VPI
VCI
8 7 6 5
VPI
VPI
VCI
VCI
4 3 2 1
VCI
VCI
PTI
CLP
VCI
HEC
CLP
HEC
(b) ATM cell header format across UNI
Computer Communications
PTI
DCS Lab.
(c) ATM cell header format across NNI
ghcho
2001 Fall
76
Lecture Topic 3
Data Link Layer
Data Link Layer Functions
Data Link Layer Design Issues
Framing Techniques
Error Detecting and Corrections
Error control and flow control
Media Access Control Sublayer
Carrier Sense Multiple Access Protocols
Standard LAN Protocols
Bridges
Computer Communications
DCS Lab.
ghcho
2001 Fall
77
Data Link Layer
Primary service is transferring data from the network layer on
the source to the network layer on the destination
DL converts the bit pipe provided by the physical layer into a
frame link
DL layer may be designed to offer a variety of services
generalized as:
• unacknowledged connectionless service
• acknowledged connectionless service
• acknowledged connection-oriented service
Most commonly the DL implements reliable and ordered
frame links
Frames received incorrectly are retransmitted, known as
Automatic Repeat Request (ARQ)
Sender is informed of transmission errors by timers and
acknowledgements
Computer Communications
DCS Lab.
ghcho
2001 Fall
78
Data Link Layer Design Issues
Computer Communications
DCS Lab.
ghcho
2001 Fall
79
Data Link Layer Design Issues
Computer Communications
DCS Lab.
ghcho
2001 Fall
80
Data Link Layer Operation
Sender
Receiver
NL
correct and ordered
DLL
CRC
Retransmit
if timeout
PL
Computer Communications
Frame
ACK if
correct
ACK
CRC
DCS Lab.
ghcho
2001 Fall
81
Framing in the DL
Recall DL uses services provided by physical layer (raw bit
stream, not necessarily error free)
Usually DL organizes the bit stream into discrete frames to
perform error detection on frames (perhaps by checksum)
How can we organize this bit stream when we may not have any
guarantees regarding timing
Several methods are commonly used and we can use a
combination of methods
Recall we usually add some protocol control information at each
layer as a header (and maybe a trailer)
Many simple techniques developed for early ASCII character
transmission
character counting
start/end characters
Computer Communications
DCS Lab.
ghcho
2001 Fall
82
Character Counting
Computer Communications
DCS Lab.
ghcho
2001 Fall
83
Start and End Characters
Start and end of a frame is delimited using flags, typically the
bit pattern 01111110
To make sure the flag does not occur in the middle of a packet,
a bit stuffing is used: insert a zero after a five consecutive ones
appear
Bit destuffing is performed at the receiver to recover the original
Example of bit (de)stuffing
01111110 001111110100101011100111111100 01111110
Stuffing
inserted 0
inserted 0
01111110 00111110101001010111001111101100 01111110
Destuffing
deleted 0
deleted 0
01111110 001111110100101011100111111100 01111110
Computer Communications
DCS Lab.
ghcho
2001 Fall
84
Error Control
Noise can introduce transmission errors
Optical communication channels typically have a bit error rate
(BER) on the order of 10e-9
Transmission lines typically have a larger BER: 10e-7 is typical
If a packet is N bits long, then the packet error rate (PER) is given
by PER = 1 - (1 - BER) N
Error Control
(so, retransmission required)
Error Correction
Error Detection
Provide enough redundant data with
each block of data in the frame to
allow receiver to reconstruct the data
in event of error
Just enough redundancy to
allow receiver to detect than an
error has occured
Parity checks
Computer Communications
DCS Lab.
ghcho
2001 Fall
CRC codes
85
Error Detection and Correction (I)
Hamming distance : the number of bit positions in which two
codewords differ
Computer Communications
DCS Lab.
ghcho
2001 Fall
86
Error Detection and Correction (II)
The error detecting and error correcting properties of a code
depend on its Hamming distance
Main idea : choose 2n codewords such that the Hamming
distance of the complete code is maximized!
let A be a complete code, then
to detect “d” error, HD(A) d + 1, and
to correct “d” error, HD(A) 2d + 1
Single bit error correction : in case of each of 2m legal messages
n+1 bits required: so, (n+1) 2m 2n, where n = m + r
(m+r+1) 2r ; given m, this puts a low limit on r
ex) m=4, r=3
Error detection : parity bit, CRC
Error correction : Hamming code
Computer Communications
DCS Lab.
ghcho
2001 Fall
87
Parity Bits (I)
Add a single bit (parity bit) to each character so that the total
number of ones is even (even parity) or odd (odd parity).
If di = i-th data bit,
then, parity bit f = d1 d2 … dn
d1 d2 d3 d4 d5 d6 d7 f
1
0
0
1
1
1
0 0
An example : Parity checks only detect odd number of errors
Received:
Transmitted:
d1
(even parity)
...
d7 f
10110100
1 error
2 errors
3 errors
Computer Communications
DCS Lab.
Status:
10010100
detected
10000100
not detected
10001100
detected
ghcho
2001 Fall
88
Parity Bits (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
89
Cyclic Redundancy Code (CRC)
Powerful method : used in most computer networks
Small amount of hardware required
Consider a message m = 11011001 (where the left-most bit
represents the most significant bit : big endian)
the corresponding polynomial representation of the message
is: M(X) = X7 + X6 + X4 + X3 + 1
• G(x) : degree r (r+1 bits) generator polynomial
• R(x) : CRC polynomial, r bits
• T(x) : text transmitted
Addition, subtraction, multiplication and division of polynomials
are done with modulo two arithmetic
Computer Communications
DCS Lab.
ghcho
2001 Fall
90
CRC Encoding/Decoding Process
Encoding
• step 1: add r zero bits to the low-order end of the frame (this
corresponds to Xr M(X) )
r
• step 2: divide X M(X) by G(X), giving a quotient Q(X) and
remainder R(X) so that
Xr M(X) = Q(X) G(X) R(X), or
Xr M(X) R(X) = Q(X) G(X)
• step 3: transmit
T(X) = Xr M(X) R(X)
Decoding
• receive C(X) = T(X) E(X),
where E(X) is the polynomial representing errors
• step 1: divide C(X) by G(X)
• step 2: if remainder = 0, no error; else, errors detected
Computer Communications
DCS Lab.
ghcho
2001 Fall
91
CRC Generators in Standards
Computer Communications
DCS Lab.
ghcho
2001 Fall
92
CRC Example
Computer Communications
DCS Lab.
ghcho
2001 Fall
93
Hamming Code
Parity bit and CRC catch errors, but can we correct them without
retransmitting information? =: Hamming code
Hamming codes, unlike CRC, contain the information
necessary to locate a single bit error
Procedure
place message bits in their non-power-of-two Hamming
positions
build a table listing the binary representation each of the
message bit positions
calculate the check bit
Hamming code
check bits : b1, b2, b4, b8, b16, ….
data bits : b3, b5, b6, b7, b9, ….
Computer Communications
DCS Lab.
ghcho
2001 Fall
94
Hamming Code Example (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
95
Hamming Code Example (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
96
Hamming Code Example (III)
Computer Communications
DCS Lab.
ghcho
2001 Fall
97
Hamming Code Example (IV)
Now, sent message is 1011011 (for 1011)
how do we check for a single bit error in the sent message?
Computer Communications
DCS Lab.
ghcho
2001 Fall
98
Hamming Code Example (V)
Computer Communications
DCS Lab.
ghcho
2001 Fall
99
Hamming Code Example (VI)
Computer Communications
DCS Lab.
ghcho
2001 Fall
100
Hamming Code Example (VII)
Computer Communications
DCS Lab.
ghcho
2001 Fall
101
Hamming Code Example (VIII)
Computer Communications
DCS Lab.
ghcho
2001 Fall
102
Hamming Code Example (IX)
Computer Communications
DCS Lab.
ghcho
2001 Fall
103
Hamming Code Example (X)
Computer Communications
DCS Lab.
ghcho
2001 Fall
104
Error Control and Flow Control (I)
Error control
feedback mechanisms
• positive acknowledge
cumulate ack.
selective ack.
• negative acknowledge
timer
sequence number
Computer Communications
DCS Lab.
ghcho
2001 Fall
105
Error Control and Flow Control (II)
Flow control
feedback mechanisms
• window-based protocols
A sample frame structure for our protocols
Start
Frame
Delimiter
Frame
Control
Frame
Type
Computer Communications
Seq.
#
DCS Lab.
Data
End
Frame
Delimiter
Ack
ghcho
2001 Fall
106
Unrestricted Simplex Protocol
Transmitter and receiver are always ready, processing time is
negligible and buffer space is not a problem
No error control, no flow control
Seemingly useless and unrealistic but can provide simple model
for communication between software layers of protocol stack
within a host
Computer Communications
DCS Lab.
ghcho
2001 Fall
107
Simplex Stop-and-Wait Protocol
Drop assumption that network layer is already ready to receive
data (that is, receiver has finite buffer, finite processing time
Still assume channel is error free and simplex
Now we need to prevent the sender from flooding the receiver
with frames
Computer Communications
DCS Lab.
ghcho
2001 Fall
108
Simplex Stop-and-Wait Protocol for a
Noisy Channel (I)
Drop assumption that channel is error free
Now frames might be corrupted or even lost completely - but
assume we can detect errors (say via checksum)
Receiver must inform sender of damaged or lost frame and sender
will retransmit, it has to distinguish between multiple copies of the
same frame
Use a Sequence number to distinguish frames
Computer Communications
DCS Lab.
ghcho
2001 Fall
109
Simplex Stop-and-Wait Protocol for a
Noisy Channel (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
110
Simplex Stop-and-Wait Protocol for a
Noisy Channel (III)
ARQ(Automatic Repeat reQuest) or PAR(Positive Acknowledge
Retransmission) protocols
early time or delayed ack. problem
worse-case engineering of the time interval
Computer Communications
DCS Lab.
ghcho
2001 Fall
111
Simplex Stop-and-Wait Protocol for a
Noisy Channel (IV)
Full duplex data transmission considerations
two physical circuits, each one for simplex data traffic
• bandwidth waste (one circuit)
one physical circuit, interleaving data and ack. frames
• the type field in the header of the frames
piggybacking (ack. field in the frame header)
• reduce the # of frame types as small as possible
• advantages
– bandwidth improvement
– processing time improvement
– buffer space improvement
• disadvantages
– heavy dependent of the availability of frames to be
transmitted by the receive
Computer Communications
DCS Lab.
ghcho
2001 Fall
112
Sliding Window Protocols (I)
Stop & wait protocol is not efficient in high speed networks
Need to allow multiple frames in transmit at one time
this requires more error control and flow control
Very robust protocols addressing these issues are known as
Sliding Window Protocols
Key idea is that the sender maintains a Sending Window
set of sequence numbers corresponding to frames it is
permitted to send (unacked frames)
The receiver also maintains a Receiving Window
the set of sequence numbers of frames it is permitted to
receive (may be out of order)
Full duplex, acknowledgement may piggyback on data packet
ABP(Alternating Bit Protocol) is sliding window with window size
= 1 (one bit sliding window)
Computer Communications
DCS Lab.
ghcho
2001 Fall
113
One Bit Sliding Window Protocols (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
114
One Bit Sliding Window Protocols (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
115
Sliding Window Protocols (II)
Two windows can be different sizes, may change size
Sequence numbers represent frames sent for which an ack. has
not been received
sender buffers the frames whose sequence # are still in the
window for possible retransmission
New packets handed down by the NL are given the next highest
sequence # and the upper edge of the window advanced
when an ack. is received from the physical layer the lower
edge of the window is advanced
If the window reaches maximum size N the DL refuses to accept
packets from the NL until an ack. arrives and a buffer is freed
if a frame is received with the sequence # equal to the lower
bound of the window it is processed, the data passed to the
NL, an ack. is generated and the window is rotated by one
Computer Communications
DCS Lab.
ghcho
2001 Fall
116
Sliding Window with Pipelining:
Go-Back-N Protocol
Computer Communications
DCS Lab.
ghcho
2001 Fall
117
Sliding Window with Pipelining:
Go-Back-N Protocol
The sender can have up to W unacknowledged frames
The receiver has 1 window, and acknowledges a correct frame
with an ACK that has the same number as the frame
Computer Communications
DCS Lab.
ghcho
2001 Fall
118
Selective Repeat Protocol (SRP)
Permits more than a single unacknowledged frame to eliminate
“dead time” waiting for ACKs, so cumulative ack.
Now, the receiver has n windows,and may get the frames in the
wrong order from the PL, but it delivers the frames to the NL in order
Computer Communications
DCS Lab.
ghcho
2001 Fall
119
Timer
How to set the timer?
Error control is not confined to the data link layer, but applied to
higher layer protocols
Computer Communications
DCS Lab.
ghcho
2001 Fall
120
Sliding Window : Summary
A simulation project assignment will be posted on the class web
1 (n)
Computer Communications
DCS Lab.
ghcho
2001 Fall
121
Medium Access Control (MAC)
Sublayer (I)
Our previous discussion of DL protocols concerned point-to-point
communications (one sender/one receiver)
For a local computer network a fully interconnected topology is
not economical and would requires adding interfaces to every
system whenever a new computer was added to the network
A more economical approach is the use of a broadcast network
with shared media : multiaccess, or random access channels
Computer Communications
DCS Lab.
ghcho
2001 Fall
122
Medium Access Control (MAC)
Sublayer (II)
Static channel allocation
FDM (Frequency Division Multiplexing)
• only a small and fixed number of users
• problem with fixed engineering, assume n channel
users n blocking even if bandwidth is wasted
users n bandwidth waste inherently
• computer comm. traffic is burst peak/mean = 1000/1
TDM (Time Division Multiplexing)
Dynamic channel allocation
the network has some number N of independent stations
generating frames at a rate (usually assumed to Poisson)
probability a station generates a frame in interval t is given by
t
a single channel is shared by all stations (physical peers)
stations detect a collision if more than one frame transmission
overlaps
Computer Communications
DCS Lab.
ghcho
2001 Fall
123
Pure ALOHA
Goal : let users transmit whenever they have something to send
Procedure
1. transmit whenever you have data to send
2. listen to the broadcast : the sending host can always find
out if its packet was destroyed just by listening to the
downward broadcast one round-trip time later
3. if the packet was destroyed, wait a random amount of time
and send it again
Note that if the first bit of a new packet overlaps with the last bit
of a packet almost finished, both packets are totally destroyed
Due to the collisions and idle periods, pure ALOHA is limited to
approximately 18% throughput in the nest case
Can we improve this
Computer Communications
DCS Lab.
ghcho
2001 Fall
124
Carrier Sense Multiple Access (CSMA)
1-persistent CSMA
when a station has data to send, it first listens to the
channel to see if it is busy (carrier sense)
the station transmits with probability of 1 whenever it finds
the channel idle
the propagation delay has an important effect on the
performance of this protocol
Computer Communications
DCS Lab.
ghcho
2001 Fall
125
Persistent CSMA (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
126
Persistent CSMA (II)
Non-persistent CSMA
the station begins transmitting when the channel is idle
if the channel is busy, the channel waits a random period time
and senses the channel again
Computer Communications
DCS Lab.
ghcho
2001 Fall
127
Persistent CSMA (III)
P-persistent CSMA
this protocol applies to slotted channels
when a station becomes ready to send, it senses the channel
Computer Communications
DCS Lab.
ghcho
2001 Fall
128
CSMA
Computer Communications
DCS Lab.
ghcho
2001 Fall
129
CSMA with Collision Detection
(CSMA/CD)
At the beginning of the contention period, stations can transmit
After a station detects a collision, it aborts the transmission,
waits a random period of time, and then tries again
In the worst case a station cannot seize the channel until it has
transmitted for 2 without hearing a collision, where is the
propagation delay from end to end
Computer Communications
DCS Lab.
ghcho
2001 Fall
130
Ethernet (I)
IEEE 802.3 (Ethernet) uses CSMA/CD protocol
cable length maximum is specified for each media type so
that we can guarantee that collisions will be detected
now most dominant media is twisted pair (10baseT)
minimum frame size is 64 bytes to ensure collision detection
maximum data in frame is 1500 bytes
a simple, easy to implement contention protocol - utilization
decreases as offered load increases - low delay
characteristics => exponential backoff
Computer Communications
DCS Lab.
ghcho
2001 Fall
131
Ethernet (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
132
IEEE 802 LAN standards (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
133
Bridges (I)
LAN has a physical limitations (500 meter Ethernet)
Connect 2 or more LANs with a bridge
Computer Communications
DCS Lab.
ghcho
2001 Fall
134
Bridges (II)
Transparent bridges
do not forward when unnecessary
maintain forwarding table (hash table)
Computer Communications
DCS Lab.
ghcho
2001 Fall
135
Bridges (III)
Spanning tree bridges
extend LANs, sometimes have loops
Computer Communications
DCS Lab.
ghcho
2001 Fall
136
Bridges (IV)
Limitations of bridges
do not scale
• broadcasting does not scale
• spanning tree algorithm does not scale
do not accommodate heterogeneity
• same format for address in network’s frame header
beware of transparency
• bridge congestion
• latency is higher and variable
• frame ordering
Computer Communications
DCS Lab.
ghcho
2001 Fall
137
Lecture Topic 4
Network Layer
Routing algorithms
Congestion control algorithms
InterNetworking issues
IP (Internet Protocol)
Internet routing
IPv6 protocol
Computer Communications
DCS Lab.
ghcho
2001 Fall
138
The Network layer (OSI layer 3)
The Network layer is responsible for communication all the way from
source to destination, that is addressing and routing
three host identifiers
names : what object is (a location independent characteristic
of a network entity)
addresses : where it is (a function of the location of the
destination)
routes : how to get there (something that depends on both the
source and destination)
Routing may include multiple hops through intermediate systems and
include crossing several different networks
It also may be concerned with congestion and optimization of the
subnet
Computer Communications
DCS Lab.
ghcho
2001 Fall
139
Classes of Routing Algorithms
Adaptive Algorithms
collect information dynamically from other routers (IS’s) either
locally or globally
adjust to changes in network topology
adjust to changes in network traffic load
differ in metrics used and frequency of information gathering
Non-Adaptive Algorithms
often called static routing
predetermined routing policies programmed into router (IS)
does not adjust to changes in network topology
does not adjust to changes in network traffic
Computer Communications
DCS Lab.
ghcho
2001 Fall
140
Optimality Principle (I)
An important consideration in routing algorithms irrespective of traffic or
topology:
suppose that router R2 lies on the optimal path from router R1 to
router R3
then the same path contains the optimal router for R2 to R3
otherwise, if there was a different optimal path from R2 to R3 the
optimal path for R1 to R3 would include that path
R2
R1
R3
Computer Communications
DCS Lab.
ghcho
2001 Fall
141
Optimality Principle (II)
B
B
A
D
F
A
C
C
E
D
I
G
J
F
I
G
H
N
M
N
L
O
K
SUBNETWORK
Computer Communications
J
H
L
K
E
M
O
SINK TREE for B
DCS Lab.
ghcho
2001 Fall
142
Static Routing Algorithms : Shortest Path
Shortest path
simple and widely used
have to determine the metric used to define “shortest” - may be
number of hops, or could be queuing delay or some cost
generally “path length” will be a function of a variety of measures cost, bandwidth, traffic, delay, etc. with appropriate weighting of
each component
Dijkstra’s algorithm
each node is labeled with its best path from source
initially all labels are tentative and assigned large values (infinity)
algorithm proceeds to find best paths
node labels are changed to reflect better paths and made
permanent when the shortest path from the source is determined
permanent labels can not change once assigned
Computer Communications
DCS Lab.
ghcho
2001 Fall
143
B
2
A
7
2
E
C
F
2
1
6
3
2
4
H
B (2,A)
2
2
6
D
2
G
A
3
7
E (inf, -)
C (inf,-)
2
F (inf, -)
3
3
D (inf, -)
1
2
2
4
G (6, A)
Computer Communications
DCS Lab.
H (inf, -)
ghcho
2001 Fall
144
B (2,A)
2
A
6
7
E (4,B)
2
C (9, B)
2
F (inf, -)
1
3
D (inf, -)
2
2
4
G (6, A)
H (inf, -)
B (2,A)
2
A
6
3
2
C (9,B)
7
E (4,B)
2 F (6,E)
1
3
2
4
G (5,E)
Computer Communications
DCS Lab.
ghcho
2001 Fall
3
D (inf, -)
2
H (inf, -)
145
B (2,A)
2
2
A
6
7
E (4,B)
2
C (9,B)
F (6,E)
3
D (inf, -)
1
2
2
H (9,G)
4
G (5,E)
B (2,A)
2
A
6
2
7
E (4,B)
2
C (9,B)
F (6,E)
1
3
2
4
G (5,E)
Computer Communications
3
DCS Lab.
ghcho
2001 Fall
3
D (inf, -)
2
H (8,F)
146
Static Routing Algorithms : Flooding
Flooding
send every packet from each input line to every output line
use hop counter and limit to damp the growth of packets
or mark packets to keep from resending a packet already
flooded
or use selective flooding - flood only on output lines making
progress toward the destination
flooding always chooses shortest path because it tries every
path simultaneously!
used as benchmark or in military applications
Computer Communications
DCS Lab.
ghcho
2001 Fall
147
Static Routing Algorithms : Flow Based
Flow based routing
considers traffic instead of just topology
depends on relatively stable traffic and determination of
average delay for each line - so for whole subnet
try to find routes that minimize average delay for the whole
subnet
need to know topology, average traffic and capacity of each
path in advance
the mean delay for each line is:
Computer Communications
DCS Lab.
ghcho
2001 Fall
148
Flow-based Routing (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
149
Flow-based Routing (II)
i
1
Line
AB
2
3
4
5
6
7
BC
(pkts/sec)
1
4
12
CD
AE
EF
FD
BF
EC
8
Ci (kbps) C (pkts/sec) Ti (ms)
Weight
20
25
91
0.171
20
25
77
0.146
6
10
12.5
154
0.073
11
13
20
62.5
50
8
10
8
71
0.134
12.5
20
0.159
10
25
20
20
25
25
222
67
59
0.098
0.122
0.098
mean delay for the whole subnet is 91 msec, thus 1/ = 800 bits
mean delay with weight is 86 msec,
thus the weight = the fraction of the total traffic using that line
Computer Communications
DCS Lab.
ghcho
2001 Fall
150
Dynamic Routing Algorithms : Distance
Vector
Distance vector routing (Bellman-Ford, Ford-Fulkerson)
one of the most commonly used types of algorithms (original
ARPANET, Internet RIP, BGP)
each router maintains a vector giving the best know distance to
a destination and which output line to use
vectors are kept in tables updated by exchanging information
with neighboring routers
table gives preferred outgoing line and estimate of distance for
each destination router
the distance metric might be number of hops, time delay in
milliseconds, total number of packet queued along the path …
a router assumed to know the metric of its neighbors
can suffer from slow propagation of information about routes
that have gone down
Computer Communications
DCS Lab.
ghcho
2001 Fall
151
Distance Vector Routing (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
152
Distance Vector Routing (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
153
Distance Vector Routing (III)
Computer Communications
DCS Lab.
ghcho
2001 Fall
154
Distance Vector Routing (IV)
A
C
B
F
E
New for J
Line
D
G
H
I
J
K
L
Router uses Echo packets
to estimate delays to neighbors
Computer Communications
DCS Lab.
A
B
C
D
E
F
G
H
I
J
K
L
ghcho
A I
H K
0 24 20 21
12 36 31 28
25 18 19 36
40 27 8 24
14 7 30 22
23 20 19 40
18 31 6 31
17 20 0 19
21 0 14 22
9 11 7 10
24 22 22 0
29 33 9 9
JA JI JH JK
8 10 12 6
2001 Fall
155
8 A
20 A
28 I
20 H
17 I
30 I
18 H
12 H
10 I
0 6 K
15 k
new routing
A
E
B
F
C
D
G
H
To
A
I
H
K
A
0
24
20
21
8
A
B
12
36
31
28
20
A
C
25
18
19
36
28
I
D
40
27
8
24
20
H
E
14
7
30
JA = 8
22
17
I
F
23
20
19
40
30
I
18
H
12
H
10
I
G
H
I
J
K
I
L
JA
31 = 8
6
31
AB
17
20 = 12
0
19
JB
21 = JA+AB
0
14 = 20
22
18
J
9
11
7
10
0
-
K
24
22
22
0
6
K
L
29
33
9
9
15
K
JA
JI
JH
JK
delay delay delay delay
is
is
is
is
8
10
12
6
Receive table
from neighbors Distances to
each neighbor
Vectors received from
J’s four neighbors
Computer Communications
DCS Lab.
ghcho
New estimated
dealy from J
Line
2001 Fall
156
New
routing
table
for J
Distance Vector Routing (V) : Count-toinfinity problem
Computer Communications
DCS Lab.
ghcho
2001 Fall
157
Dynamic Routing Algorithms : Link State
Link State Routing
distance vector routing
• queue length as the delay metrics, not considered link
bandwidth
• long convergence time
1) each router must discover neighbors
• sends a HELLO packet on each line
2) measure delay or cost to each neighbor
• send ECHO packet and measure time to get response
3) build an information packet periodically or at specific events
(neighbor router goes down or comes up)
4) send the information packet to all other routers
• use modified flooding
5) compute the shortest path to every other router
• run Dijkstra’s algorithm at the local router
Computer Communications
DCS Lab.
ghcho
2001 Fall
158
Building Link State Package
Sender’s identity
A
B
2
4
C
3
1
A
5
7
8
Age
age
B
4
E
5
List of neighbors
F
A
B
C
D
E
F
Seq.
Seq.
Seq.
Seq.
Seq.
Seq.
Age
Age
Age
Age
Age
Age
B
4
A
4
B
2
C
3
A
5
B
6
E
5
C
2
D
3
F
7
C
1
D
7
F
6
E
1
F
8
E
8
Link state packets for all six routers
The most difficult issue is when to build the link
state information packet and how to distribute it
Computer Communications
Sequence number
D
6
E
Seq.
DCS Lab.
ghcho
<link state packets>
2001 Fall
159
Distributing the Link State Packets
Use flooding to distribute link state packets
Each packet contains a sequence number that is incremented for
each new packet generated by the router
Routers keep track of all pairs (source, seq.) they see
It checks the incoming link state packets
if new, it is forwarded on all lines except the one it came on
if not new, (duplicate), it is discarded
Once a router has a full set of link state packets, the entire subnet
graph can be constructed
Dijkstra’s Algorithm can be run locally to construct the shortest path
for n routers and each with k neighbors
• we need memory proportional to kn
Computer Communications
DCS Lab.
ghcho
2001 Fall
160
Hierarchical Routing
As network size grows, routing tables and CPU time increase
exponentially
Hierarchical routing is used to reduce these size, but increase
number of hops to reach a remote destination
Computer Communications
DCS Lab.
ghcho
2001 Fall
161
Routing in Mobile Networks
Mobile
Host
Wireless
Cell
Home
Agent
Foreign
Host
Computer Communications
DCS Lab.
ghcho
2001 Fall
162
Routing for Mobile Hosts
All users assumed to have home location that never changes (Home
Agent)
foreign agents broadcast information packets
mobile host registers with foreign agent
foreign agent contacts home agent that replies with ack. After
proper authentication, security
once ack is received, the mobile host is registered for its location
mobile hosts de-register once they leave the area
Computer Communications
DCS Lab.
ghcho
2001 Fall
163
Broadcast Routing
Broadcast by repetitive sending the message for each destination
flooding might be an interesting approach to perform
broadcasting
multi-destination routing
• each packet has a list of destinations or a bit map for desired
destinations
• router generates a new copy for each output line to be used
to reach the desired destinations
– partition the destinations among the output lines and
eventually the node will receive only one destination
sink tree or spanning tree
Broadcast incoming packets only on the spanning tree lines
makes excellent use of bandwidth
problem is that each router must have knowledge of some
spanning tree
Computer Communications
DCS Lab.
ghcho
2001 Fall
164
B
B
A
C
D
F
A
D
E
I
G
I
N
L
N
L
O
M
SINK TREE for B
K
O
M
B
SUBNETWORK
(5 hops, 24 packets)
F
L
MG
Computer Communications
C
A
D
K H
J
H
H
K
E
G
F
J
C
G
L
I
J
D N I E
H
F EO
M
O
L
H
Reverse Path Forwarding
(4 hops, 14 packets)
DCS Lab.
ghcho
2001 Fall
165
B
Multicast Routing
A
1
C
B
1,2
2
A
C
D
1
F
2 I
G
J
1
H
1
K
N
L
1 K
1
F
E
1 J
M
B
A
O
2
C
2
SINK TREE for B
Computer Communications
DCS Lab.
2
ghcho
2001 Fall
I
SINK TREE for B
166
Congestion Control (I)
If packet traffic becomes too heavy routers can begin to loose
packets
It an arise because of sudden burst of incoming traffic on
several lines all destined for same output line
Processors in some routers might be slow
Some lines may have lower bandwidth
Congestion tends to generate more congestion as packet
time-outs expire and packets are retransmitted, buffers
become locked waiting for ack’s, etc.
Congestion control is a global issue in the network (vs. flow
control which is a point-to-point issue between a sender and
receiver)
Computer Communications
DCS Lab.
ghcho
2001 Fall
167
Congestion Control (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
168
Congestion Control (III)
Computer Communications
DCS Lab.
ghcho
2001 Fall
169
General Principles of Congestion
Control
We can take closed loop or open loop viewpoint
for open loop control
• decide when to accept new traffic
• decide when to discard packets
• decide which packets to discard
• make decisions independent of current state
for closed loop control
• based on feedback loop concept
• actively monitor network to detect congestion
• pass information to systems where action is needed
• adjust network operation to correct the congestion
Computer Communications
DCS Lab.
ghcho
2001 Fall
170
Open Loop Systems
Layer
Policies
Transport
Retransmission Policy
Out-of-order Caching Policy
Acknowledgement Policy
Flow Control Policy
Timeout Determination
Network
Virtual Circuits vs. Datagram
Packet Queuing and Servicing Policy
Packet Discard Policy
Routing Algorithm
Packet Lifetime Management
Data Link
Retransmission Policy
Out-of-order Caching Policy
Acknowledgement Policy
Flow Control Policy
Computer Communications
DCS Lab.
ghcho
2001 Fall
171
Closed Loop Control
We need metrics to monitor for congestion
percentage of packets discarded due to buffer space
queue lengths
number of retransmissions
packet delay measures
When congestion is detected
may send control packets to traffic sources
• may add to the congestion
May use bits in existing packet headers of control packets
Dynamically query other routers about potential congestion
before it occurs
Problem is to get time scale correct to keep from oscillating
Computer Communications
DCS Lab.
ghcho
2001 Fall
172
DL Policies Impact on Congestion
Retransmission Policy affects how fast a times out waiting for
an Ack and which packets are retransmitted on timeout
short timeout and Go Back N => more load
long timeout and Selective Repeat => less load
Caching Policy affects how receiver deals with packets
received out of order
caching out of order packets lightens network load =>
need for buffer memory at receiver
Ack Policy can affect congestion
piggybacking could result in extra timeouts and
retransmissions
may also save on traffic
Flow Control Policy (e.g. Window size) impacts offered load
large window size => higher load
Computer Communications
DCS Lab.
ghcho
2001 Fall
173
NL Policies Impact on Congestion
Choice of service strategy
virtual circuits may lead to congested links
congestion control algorithms may not work with Datagram service
Packet queuing and service policy affects where congestion may occur
maintain an input Q per line; maintain an output Q per line; or both?
how are the queues serviced?
are there priorities?
Packet discard policy affects how we determine which packets to drop in
the router when there is congestion
age, # of hops, some priority
Routing algorithm choice may evenly distribute or concentrate traffic
possibly leading to congestion
Packet Lifetime concerns how long the packet can bounce around the
net before being discarded
too long => congestion as packets bounce around
too short => senders time-out and retransmit
Computer Communications
DCS Lab.
ghcho
2001 Fall
174
TL Policies Impact on Congestion
Recall TL is first end-to-end layer
Peer transport entities talk across the internetwork
So issues are basically the same as the DL where stations are
logically adjacent (point-to-point)
Primary difference is that it is much more difficult to determine
timeout values across an internetworked environment than
across a LAN
Short timeouts contribute to congestion by generating more
packets while long timeouts impact response time when
packets are lost
Computer Communications
DCS Lab.
ghcho
2001 Fall
175
The Leaky Bucket Algorithm
Outflow is either zero or a constant rate
Packets spilling over the edge of the
bucket are lost
Single-server queue with constant
service time
One packet (drop) output per “clock tick”
Easy to implement in NIC
Particularly easy when packets are all
fixed length (e.g. ATM cells)
For packets of varying size we can
modify to allow fixed number of bytes per
clock tick instead of fixed number of
packets
Enforces fixed maximum output rate
Computer Communications
DCS Lab.
ghcho
2001 Fall
176
The Token Bucket Algorithm
We may want output rate to be able to
speed up when a burst arrives
Instead of packets the bucket holds
Tokens which are generated into the
bucket at a fixed rate
One packet may be transmitted for
each Token in the bucket
If no Token a packet may not be
transmitted until a new Token is
generated
Effectively lets the idle host save
Tokens for a burst up to the limit of
Tokens the bucket can hold
If the bucket is full new Tokens are
discarded (but not packets)
Computer Communications
DCS Lab.
ghcho
2001 Fall
177
Internetworking Issues
Expect that there will continue to be a large variety of protocols at
each layer
Interconnecting heterogeneous networks will introduce many
conflicts
To provide services we want Network layer to accommodate:
different addressing schemes
different maximum packet sizes
different network access mechanisms …
Network layer may have to accommodate:
different timeout values
error recovery
status reporting
routing & congestion control
user access control
Computer Communications
DCS Lab.
ghcho
2001 Fall
178
Internetwork Approaches
Connection oriented with virtual circuits
H1
S
S
S
M
S
H2
S
S
S
H1
H2
G
G
R
R
G
Connectionless with datagrams
Computer Communications
DCS Lab.
ghcho
2001 Fall
179
Connection Oriented Approach
Build virtual circuit pathway through the internetwork between the
source and the destination
Switches maintain information about the virtual circuits
The connection oriented approach is often more appropriate when the
internetwork is homogeneous
Benefits of virtual circuit based internetworking include:
resource allocation at circuit setup
sequencing is guaranteed
low header overhead
no duplicate packets
Drawbacks of internetworking based Virtual Circuit include:
switch resources needed for each circuit
switch failure brings down the whole connection
certain paths may be susceptible to congestion
difficult to incorporate non-VC based network into the internetwork
Computer Communications
DCS Lab.
ghcho
2001 Fall
180
Connectionless Approach
For connectionless we route the packets through the network with
routers performing a role similar to the switches but packets do not
need to all follow the same route
useful for heterogeneous networks
Gateways interconnect networks and are given differing names
depending on the layer
repeaters - physical layer
bridges - DL/MAC layer
routers (Gateways, Multiprotocol Routers) - Network Layer
transport Gateways - Transport Layer
application Gateways (e.g. email gateway) - Application Layer
probably not useful at Presentation or Session layer
Computer Communications
DCS Lab.
ghcho
2001 Fall
181
Gateways
In this case the gateway performs a routing and translation function
between network A and network B
Network A
Network B
HOST
Computer Communications
HOST
DCS Lab.
ghcho
2001 Fall
182
Routing
In this case the gateway performs a routing function between
network A and network B
IP Network A
IP Network B
HOST
Computer Communications
HOST
DCS Lab.
ghcho
2001 Fall
183
Tunneling
In this case the gateway does not translate to the WAN protocol
between network A and network B but wraps the IP packet in a WAN
packet and sends it transparently (tunnels) across the WAN. A & B
seem to have a direct serial link.
Network A
Network B
HOST
HOST
WAN
Computer Communications
DCS Lab.
ghcho
2001 Fall
184
Fragmentation
If our data has to traverse many diverse networks it’s likely that they
will have different maximum data “payload” sizes
This may be determined by OS (device driver) parameters, physical or
data link layer hardware or optimization efforts
Usually the size of PDU payload increases in higher layers (higher
levels of abstraction)
Internetwork has to deal with differences - usually means we have to
fragment larger packets
Easy part - Gateway is allowed to break up a packet into fragments
and send each fragment as a separate piece
Hard part - Gateway has to put pieces back together to reconstruct the
original packet
So the question is - do we need to put them back together again?
As usual there are two competing viewpoints
transparent fragmentation
non-transparent fragmentation
Computer Communications
DCS Lab.
ghcho
2001 Fall
185
Transparent Fragmentation
H1
Fragments recombined at each Gateway and original sized
packet delivered at destination
Requires all packets to leave network via same Gateway so
some performance loss
Gateway needs to know when all fragments have been received
Fragmenting, recombining, fragmenting, recombining… as
packet traverses internet introduces overhead and reduces
performance
R1
G1
R2
G2
G7
Computer Communications
R3
R1
G8
DCS Lab.
ghcho
2001 Fall
186
H1
Non-Transparent Fragmentation
H1
Do not recombine fragments at each intermediate Gateway so each
fragment becomes an independent packet
Allows fragments to take separate paths
Recombination takes place at the destination host
G1
G2
G3
G4
G5
G7
Computer Communications
G6
G8
DCS Lab.
ghcho
2001 Fall
187
H1
The Internet Protocol (IP)
Internet is not a physical network, but it is a method of
internetworking physical networks and a set of conventions for
using networks that allow the computers they reach to Internet
The collection of networks and gateways that use the TCP/IP
protocol suite and that function as a single, cooperative virtual
network
A collection of autonomous systems (in other word ‘domain’)
interconnected by one or more backbones
Loose, collaborative structure with AS’s organized into
Regional Networks interconnected into the larger Internet
Developed from the DARPAnet, NSFnet and grew from the
original TCP/IP protocol suite and was designed for
internetworking from the start
Provides best effort datagram service to transport Layer
Computer Communications
DCS Lab.
ghcho
2001 Fall
188
Internetworking
Computer Communications
DCS Lab.
ghcho
2001 Fall
189
IP (Internet Protocol) (I)
Computer Communications
DCS Lab.
ghcho
2001 Fall
190
IP (Internet Protocol) (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
191
IP (Internet Protocol) (III)
Computer Communications
DCS Lab.
ghcho
2001 Fall
192
IP Addressing
Computer Communications
DCS Lab.
ghcho
2001 Fall
193
IP Addressing - Special Addresses
Computer Communications
DCS Lab.
ghcho
2001 Fall
194
Subnetting
The notion of splitting an internet address into a network and host
portion didn't work well in practice
It required the central authority to handle all requests for address for
networks, of which there were many more than anticipated
A better approach, soon adopted, is to divide the internet address
into three pieces: an institution #, a network #, and a host #
The institution is given a range of addresses
The address bits following the institution # (still officially the network
#) are divided into subnet (or real network) number and host #
This division is specified, for each institution, by a bit mask known
as the subnet mask
Computer Communications
DCS Lab.
ghcho
2001 Fall
195
Internet Control Message Protocol (ICMP)
IP Standards specify that compliant implementations must also
implement ICMP (RFC 792)
ICMP provides a mechanism to provide feedback about problems in
the network
ICMP packets may be sent by routers or hosts and are generated
“at the NL”
ICMP exists at the NL but is a user of NL services - I.e. uses IP
datagram service
ICMP packets are usually generated by a host or router in response
to a previous datagram
ICMP packets have a 64 bit header which includes:
type (8 bits) - type of ICMP packet
code (8 bits) - specifies parameters of the packet
checksum (16 bits) - checksum for entire ICMP packet
parameters (32 bits) - specifies parameters to large for Code
Computer Communications
DCS Lab.
ghcho
2001 Fall
196
Types of ICMP Packets
The header is usually followed by additional information depending
on packet type
When the packet refers to a previous datagram the additional info.
includes the IP header and first 64 bits of the original datagram
Inclusion of first 64 bits of data after the IP header is to allow IP
entity to determine which IP user was associated with the datagram
Types of packets include:
destination unreachable - e.g. router can’t reach dst network
time exceeded - TTL of datagram expires
parameter error - semantic error in IP header
Src Quench - simple flow control
redirect - advise host of better route
echo (reply) - test communications
timestamp (reply) - allow determination of delay
address mask req (reply) - inform host of LAN’s subnet mask
Computer Communications
DCS Lab.
ghcho
2001 Fall
197
ICMP Examples : ping
Use ICMP echo request/reply
Source can calculate round trip time (RTT) of packets
Computer Communications
DCS Lab.
ghcho
2001 Fall
198
ICMP Examples : traceroute
Records the route that packets take
To determine the route, progressively increase TTL
Computer Communications
DCS Lab.
ghcho
2001 Fall
199
Some ICMP Packet formats (I)
Type
Code
Checksum
Type
Unused
Ptr
Code
Checksum
Identifier
Sequence #
Originate timestamp
Dst. unreachable, time exceeded,
src quench
Type
Code
Timestamp
Checksum
Type
Unused
Code
Checksum
Identifier
IP Header + 64 bits original dg
Sequence #
Originate timestamp
Receive timestamp
Parameter error
Transmit timestamp
Timestamp reply
Computer Communications
DCS Lab.
ghcho
2001 Fall
200
Some ICMP Packet formats (II)
Type
Code
Checksum
Type
Gateway IP Address
Identifier
Sequence #
Address mask request
Redirect
Code
Checksum
Identifier
IP Header + 64 bits original dg
Type
Code
Checksum
Type
Sequence #
Code
Checksum
Identifier
Sequence #
IP Header + 64 bits original dg
Address Mask
Echo, Echo Reply
Address mask reply
Computer Communications
DCS Lab.
ghcho
2001 Fall
201
Mapping IP addresses to the DL
Consider an 802.3 LAN running IP
recall DL has it’s own 48-bit addresses used to identify LLC
entities on the LAN
NL superimposes an internetwork on top of the LAN and
provides it’s own 32-bit IP address space
DL knows nothing about IP addresses
How do these two sets of addresses get mapped to each other?
That’s
me!
Who is
1.2.3.4?
A
B
C
D
Ethernet
Computer Communications
DCS Lab.
ghcho
2001 Fall
202
Address Resolution Protocol (ARP) (I)
Another control protocol which resides at the NL is ARP
ARP builds a DL broadcast frame with a packet “what’s the DL
address for IP address w.x.y.z?” and sends it
broadcast frame is received by all hosts and one says “that’s me!”
or another says “I know”
host recognizing the IP address builds a response giving the DL
address to IP address mapping and sends it to the sender
This is a simple and effective protocol which eliminates need for
maintaining static tables
a sender broadcasts the ARP request packet with it’s destination
xffffffffffff address field
But, the broadcasting is too expensive to use repeatedly whenever a
host wants to send a packet. How can it be solved?
when a host receives an ARP reply, it saves the sender’s IP
address and corresponding physical address in its cache for
successive lookups
Computer Communications
DCS Lab.
ghcho
2001 Fall
203
Address Resolution Protocol (ARP) (II)
Is it be possible more refinement?
the sender’s IP-to-physical address binding is included in every
ARP broadcast; receivers update the binding in their cache
ARP is a low-level protocol that hides the underlying network
physical addressing, permitting one to assign an arbitrary IP
address to every machine
ARP is a part of the physical network system, and is not a part of the
internet protocols
Reverse address resolutoin protocol (RARP)
ARP finds out Ethernet address that corresponds to a given IP
RARP finds the IP address of the host using an Ethernet address
associated with the Ethernet card
• when the machine is booted, it broadcasts its 48-bit Ethernet
address and ask for its IP address
• RARP server that is available at each network responds with
the IP address
Computer Communications
DCS Lab.
ghcho
2001 Fall
204
The Internet Routing Architecture
Internet = a core system + a set of autonomous systems
The core system is the glue, as which
is controlled by the INOC(Internet Network Operations Center)
provides reliable and consistent routers for all possible dest.
does not use the default route
has complete infor. about optimal routes to all possible dest.
The autonomous system is an ever-growing component of core
system, as which
is a collection of networks and gateways managed by one
administrative authority
are hierarchically grouped into an autonomous system (nesting)
allows gateways to advertise only the reachability of those
networks within the gateway’s autonomous system
restricts the Internet’s topology to a tree structure in which a core
system forms the root - only one path from the core system
Computer Communications
DCS Lab.
ghcho
2001 Fall
205
Routing Protocols in IP
Core System
Gateway 1
Autonomous
System 1
Gateway 2
Gateway 3
Autonomous
System 2
Autonomous
System 3
Core system : GGP (Gateway-to-Gateway Protocol)
Core and autonomous system(s) : EGP (Exterior Gateway Protocol)
Autonomous system : IGP (Interior Gateway Protocol)
Initial DARPA Internet protocol for GGP was Routing Information
Protocol (RIP) - same Distance Vector routing
As the Internet has grown very large, RIP is being replaced by Open
Shortest Path First (OSPF) - Link State protocol
Widely used IP routing protocol for Exterior gateways is Border
Gateway Protocol (BGP)
Computer Communications
DCS Lab.
ghcho
2001 Fall
206
Table Driven IP Routing
The IP routing algorithm employs an Internet routing table on each
machine (host and router), which contains information about the
possible destinations and how to reach them
It consults the table to decide where to send the datagram
Then what information should be kept in routing tables?
minimal information principle : keep network prefix only
- makes routing efficient and keeps routing table small
information hiding principle : the details of specific hosts confined
to the local environment : next- hop routing
- the routing table in a router only specifies one step along the
path from the router to a destination
Default routing : If no route appears in the table, the routing routines
send the datagram to a default router
it makes their routing decisions efficiently to possible distant
destinations
Computer Communications
DCS Lab.
ghcho
2001 Fall
207
Table Driven IP Routing (An Example)
20.0.0.5
Network
10.0.0.0
Q
30.0.0.6
Network
20.0.0.0
10.0.0.5
R
40.0.0.7
Network
30.0.0.0
20.0.0.6
30.0.0.7
To reach hosts
on network
Route to
this address
20.0.0.0
Deliver Directly
30.0.0.0
Deliver Directly
Computer Communications
10.0.0.0
20.0.0.5
40.0.0.0
30.0.0.7
DCS Lab.
S
ghcho
2001 Fall
208
Network
40.0.0.0
IP Routing Algorithm
Route_IP_Datagram(datagram, routing_table)
Extract destination IP address, ID, from datagram
Compute IP address of destination network, IN
if IN matches any directly connected network address
send datagram to destination over that network;
else if ID appears as a host-specific route
route datagram as specified in the table;
else if IN appears in routing table
route datagram as specified in the table;
else if a default route has been specified
route datagram to the default gateway;
else declare a routing error;
Computer Communications
DCS Lab.
ghcho
2001 Fall
209
Routing Protocols in IP
IP routing is based on the destination network ID alone, what?
all IP traffic for a given network tales the same path regardless to
the delay or throughput of physical network
only the final router can determine if the destination exists or is
operational, the router only can report the delivery to the sender
each router routes traffic independently - someone should find
out if two-way communication is always possible
IP routing selects the next hop to be sent the datagram, what?
where does IP store the next hop address? not IP itself!
IP simply passes the datagram and the next hop address to the
network interface software (so-called network driver)
the driver software responsible for the physical network over
which the datagram must be sent - binds the next hop IP
address to a physical address, forms a frame, and sends it
Computer Communications
DCS Lab.
ghcho
2001 Fall
210
IPv6 Protocol
IPv6 is the formal name of the protocol recommended by the
IETF’ IPng group, its objectives are:
support large global internetwork
support new low-end Internet devices (PDAs, mobile
computers, consumers, devices)
support the networked multimedia services
The Challenges from IPv4
plenty of addresses
reduced administrative overhead
opportunity for better routing
support for address renumbering
improved header processing
reasonable security
support for host mobility
QoS control capability
Computer Communications
DCS Lab.
ghcho
2001 Fall
211
IPv6 Header
Priority to distinguish packets whose sources
can (can not) be flow controlled
Values 8 through 15 used for real-time traffic
0
15
Vers
Prior
31
Flow Level
Payload Length
Next Header
Hop Limit
Source Address (128)
10 X 32 bit
= 40 octets
Destination Address (128)
Next Header
Header Length
Hop-by-hop option (variable)
Next Header
Header Length
Other option headers …
IP payload : TCP header (variable)
Computer Communications
DCS Lab.
ghcho
2001 Fall
212
IPv6 Addresses
Two-level structure of the IPv4 address, what?
Space are 340,282,366,920,938,463,463,374,607,431,768,211,456
(2^^96 times that of IPv4)
An address is represented as x:x:x:x:x:x:x:x (x is 16 bit long)
(ex, fedc:ba45:00d4:4354:f345:ad23:546d:232c)
Compression 0’s (ex, ff01:0:0:0:0:0:0:43 => ff01::43)
Combination between the IPv4 address and IPv6’s one
- IPv4 compatible address => ::IPv4 address (eg. x:x:x:x:x:x:d.d.d.d)
- IPv4 mapped address => ::ffff:IPv4 address
IPv6 addresses are identifiers for interfaces, not nodes
A single interface may be assigned multiple IPv6 addresses of any
type, that is, unicast, anycast, multicast
010
REGISTRY
Computer Communications
PROVIDER
DCS Lab.
SUBSCRIBER
ghcho
2001 Fall
SUBNET INTERFACE
213
Term Report
Who works to evolve Internet technologies?
IETF (Internet Engineering Task Force)
has been concerned with the evolution of the Internet
architecture and the smooth operation of the Internet
9 working areas, about 130 working group for each current
issues
www.ietf.org
Report format
what IETF do?
its responsibilities
then, select 5 working groups whatever you are interesting in
• read the page, and give your word for each WG, as
• aims and duty, time schedule, summary of main documents
(Internet draft, RFC), current working status
• 1 page per WG is recommended
Computer Communications
DCS Lab.
ghcho
2001 Fall
214
Lecture Topic 5
Transport Layer
Transport layer concepts
Protocol layering
Port number
TCP protocol
TCP flow control
TCP congestion control
TCP protocol congestion
UDP protocol
Network programming interfaces
Computer Communications
DCS Lab.
ghcho
2001 Fall
215
Transport Layer (I)
The transport layer must provide higher layers with the illusion of an
end-to-end connection, especially in connectionless networks
Its protocol responsible for providing support for end-to-end
exchange of data between two processes, it may concerned with:
optimizing the use of the network service
providing a requested quality of service to the TL service user
When an application in one host wants to communicate with an
application in another host, it must set up a transport layer
connection to that application
naïve approach
Computer Communications
DCS Lab.
ghcho
2001 Fall
216
Transport Layer (II)
Problems with naïve approach
duplicate connection request or accept connection paskets
solution: introduces sequence numbers and a 3 way handshake
Computer Communications
DCS Lab.
ghcho
2001 Fall
217
Transport Layer (III)
3 way handshake
The transport layer, like the data link layer, must provide a flow-control
and error-controlled link
the DLL is hop-by-hop (node-to-node), while the TL is end-to-end
The same flow and error control protocols used in the data link layer
may be used with the transport layer
one additional concern is packet resequencing
Computer Communications
DCS Lab.
ghcho
2001 Fall
218
Transport Layer (IV)
Sliding window with out of order arrivals
sender side window is unaffected by out of order reception of
packets at the receiver
receiver side window, however, behaves differently when packets
are ale to arrive out of order
Computer Communications
DCS Lab.
ghcho
2001 Fall
219
Protocol Layering in Internet
Software Organization
Conceptual Layers
Protocol 1
Protocol 2
Protocol 3
High Level Layer
IP Module
IP Layer
NI Layer
NI 1
NI 2
NI 3
Sender
Receiver
Others...
Others...
IP Layer
IP Layer
IP Layer
IP Layer
N.I
N.I
N.I
N.I
Net 1
Computer Communications
Net 2
DCS Lab.
ghcho
Net 3
2001 Fall
220
Transport Layer
Responsible for providing support for end-to-end exchange of data
between two processes, TL may be concerned with
optimizing the use of the network service
providing a requested quality of service to the TL service user
Two TL protocols - Transport Control Protocol (TCP) and User
Datagram Protocol (UDP)
TCP is connection oriented
UDP is connectionless (minimal service on top of IP)
TCP provides reliable byte-stream communications between a pair
of TCP user processes across an unreliable network
Functionally equivalent to Class 4 ISO Transport but TCP is stream
oriented
TCP was designed to dynamically adapt to properties of the
internetwork and being robust to many kinds of failures
Computer Communications
DCS Lab.
ghcho
2001 Fall
221
TCP
A TCP entity runs on each host supporting the TCP/IP protocol suite
The entity may be a kernel process which interacts with the IP entity
TCP users exchange streams of data bytes but TCP entity breaks these
up into segments of 64KB or less for transmission
TCP service is obtained by having both the sender and receiver create
end points (sockets)
each socket has a socket number (address) consisting of
IP address of the host
16-bit number local to the host (port)
connections are identified by the socket identifiers at both ends
(socket1, socket2)
Current operating system support multiprogramming
multiple applications would be executed simultaneously; multitask
Computer Communications
DCS Lab.
ghcho
2001 Fall
222
Port Number (I)
A process is the ultimate destination for a message, but IP delivers a
datagram to only the destination host, and
processes are created and destroyed dynamically
process identifier would be changed in times
much reasonable to identify destinations from the functions
Instead of thinking of a process as the ultimate destination, Internet
provides a set of abstract destination points called protocol port, which is
possible for more than one user process at a time to be using either
TCP or UDP
consist of 16-bit integer
When a client process wants to contact a server, the client must have a
way of identifying the server that it wants
assuming that the client knows the server’s IP address, how does
the client identify the particular server process
To solve this problem, a group of well-known ports are defined
the port 1 - 255 (1 - 1023 for BSD UNIX) are reserved
Computer Communications
DCS Lab.
ghcho
2001 Fall
223
Port Number (II)
Now, the hierarchical addressing scheme is:
IP datagram contains the two 32-bit IP addresses
also IP header contains a protocol identifier
UDP or TCP header contains the two 16-bit port # for identifying a
user process (TCP ports are independent of UDP port)
IP address identifies this machine
Protocol “06” is the TCP protocol
06
TCP
203.234.18.72
Network
IP
21
25
FTP
SMTP
Port determines
which application
gets incoming
data
17
UDP
69
7
ECHO
Computer Communications
DCS Lab.
ghcho
TFTP
2001 Fall
224
Some Well Known Ports
Port numbers less than 1024 are reserved for standard services:
# Network services, Internet style
FTP
21
TELNET 23
echo
7/tcp
echo
7/udp
ftp
21/tcp
telnet
23/tcp
smtp
25/tcp
#mail
time
37/udp
#timserver
finger
79/tcp
pop
109/tcp
#postoffice
nntp
119/tcp
# USENET News Transfer Protocol
ntp
123/udp
# network time protocol
snmp
161/udp
# SNMP Network Management
Computer Communications
DCS Lab.
ghcho
2001 Fall
225
TCP Service Model
TCP connection is a byte stream and not a message stream
if a sending process writes 4 512-byte chunks to a TCP stream
it might be delivered as 4 512 byte chunks
two 1024 byte chunks
one 2048 byte chunk
the data can be sent immediately or buffered it in order to collect
a larger amount to send at once
TCP provides a push mechanism to send data immediately without
any delay
user can require TCP to transmit all outstanding data by setting
the PUSH flag
receiver TCP delivers this pushed data immediately
TCP provides an urgent mechanism
TCP allows user to mark data as urgent (CTRL-C)
TCP user at receiving end decides what to do in response
Computer Communications
DCS Lab.
ghcho
2001 Fall
226
TCP Protocol
IP datagrams with TCP specified in protocol field are presented to
the TCP entity to reconstruct data streams
TCP entity uses timers to deal with lost packets, retransmission
and out of order
Use sliding window protocol - receiver ack refers to the next
expected segment
TCP has only one type of TPDU - segment
Minimum header size is 20 octets
segment must fit in maximum IP packet 65535 B
each network has a maximum transfer unit(MTU) and each
segment must fit in that MTU
Computer Communications
DCS Lab.
ghcho
2001 Fall
227
TCP Segment Header
0
8
16
Source Port
24
31
Destination Port
Sequence number
Acknowledgement number
Hlen
Reserved
Flags
Window
Checksum
Urgent Pinter
Option (if any)
Padding
Data
...
After the options, up to 65,535 -20 -20 = 65,495 data bytes may follow
segments without data used for ack and control messages
Computer Communications
DCS Lab.
ghcho
2001 Fall
228
TCP TPDU Header Fields (I)
Source/destination Ports - defines the local end points of the
connection
Sequence Number - Sequence # of first data octet in the
segment except if SYN flag is set, then it’s initial sequence
number N and first data octet is N+1
Ack number refers to the next byte expected
seq and ack are both 32 bits long because every byte in TCP
stream is numbered
TCP Header Length - Number of 32-bit words in the TCP header
Reserved - 6 bits reserved for future use
Computer Communications
DCS Lab.
ghcho
2001 Fall
229
TCP TPDU Header Fields (II)
Flags
URG - Urgent pointer field is used to indicate a byte offset
from the current urgent data
ACK - Acknowledgement field is valid/ignored
PSH - to indicate that data is PUSHED
RST - Reset the connection due to crashes, failures
SYN - is used to establish connections
FIN - release connection No more data sent
Flow control is handled using variable-size sliding window
window size 0 is legal
Checksum - add all 16-bit words in One’s complement and then
take the 1’s complement of the sum
options used to add new capabilities
use large segment to reduce header overhead
increase window size from 16 bits to 30 bits
Computer Communications
DCS Lab.
ghcho
2001 Fall
230
Service Request Primitive Types (I)
Unspecified Passive Open - listen for open from any remote
destination
Fully Specified Passive Open - listen for open from specific
remote destination
Active Open - request connection to specific remote
destination
Active Open with Data - request connection to specific remote
destination and send data with the open request
Send - transfer data across an established connection
Allocate - issue incremental allocation for receive data
Close - close a connection gracefully
Abort - close a connection ungracefully
Status - check on connection status
Computer Communications
DCS Lab.
ghcho
2001 Fall
231
Service Response Primitive Types (II)
Open ID - inform TCP user of connection name assigned to
pending connection requested by Open primitive
Open Failure - report failure of Active Open
Open Success - report completion of Active Open
Deliver - report arrival of data
Closing - report that remote TCP user issued a close and all
data sent by remote user has been delivered
Terminate - reports that the connection has been terminated
Status Response - returns status of current connection
Error - reports serivce request or internal error
Computer Communications
DCS Lab.
ghcho
2001 Fall
232
TCP Connection Setup
Uses 3-way handshake
One side uses Listen and Accept primitives to passively wait for an
open request (usually a server)
Client side issues a Connect (active open) request to establish a
connection (SYN bit on, ACK bit off)
Computer Communications
DCS Lab.
ghcho
2001 Fall
233
TCP Flow Control (I)
TCP uses a modified version of the sliding window
In ack., TCP uses the “window size” field to tell the sender how
many bytes it may transmit
TCP uses bytes, not packets, as sequence numbers
Computer Communications
DCS Lab.
ghcho
2001 Fall
234
TCP Flow Control (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
235
TCP Flow Control Problems (I)
The small packet problem
occurs when the source sends many small packets
The silly window syndrome
occurs when the destination reads a small number of bytes at a
time from its buffer
Consider an interactive application where the source host sends
each keystroke one at a time to the destination host
each keystroke is 1 byte, after adding TCP/IP overhead, a 41
byte packet is generated
when the destination receives the packet, it returns a 40 byte
ack. packet
when the destination removes the byte from its buffer, a 40 byte
window update packet is sent
some applications echo the types character back to the source,
creating another 41-byte packet
The small packet problem seriously degrades throughputs
Computer Communications
DCS Lab.
ghcho
2001 Fall
236
TCP Flow Control Problems (II)
The small packet problem (SPP)
Computer Communications
DCS Lab.
ghcho
2001 Fall
237
How TCP Solves the SPP
Nagle’s algorithm
when data is sent one byte at a time, send only the first byte
buffer all remaining bytes until the first one is acknowledged
after receiving the ack., send all the buffered bytes in one packet
This algorithm reduces the amount of bandwidth required to support
interactive applications
Computer Communications
DCS Lab.
ghcho
2001 Fall
238
TCP Flow Control Problems (III)
The silly window syndrome (SWS)
Consider an application where the source sends in large blocks of
data but the destination reads bytes from its buffer 1 byte at a time
each time the destination reads a byte from its buffer, it returns a
window update to the source
the source sees that it is only free to send 1 more byte so it sends
a single byte
this process repeats itself all the data has been sent, 1 byte at a
time
Clark’s solution
prevent the receiver application from reading only 1 byte from its
TCP buffer
the receiver should only read from the TCP buffer when it has
sufficient application buffer space to handle a large chunk of data
the sender may also help by refusing to send small data packets
Computer Communications
DCS Lab.
ghcho
2001 Fall
239
TCP Flow Control Problems (IV)
The silly window syndrome (SWS)
Computer Communications
DCS Lab.
ghcho
2001 Fall
240
TCP Retransmission
When a packet remains unacknowledged for a period of time, TCP
assumes it is lost and retransmits it
TCP tries to calculate the round trip time (RTT) for a packet and its
acknowledgement
From the RTT, TCP can guess how long it should wait before
timing out
Computer Communications
DCS Lab.
ghcho
2001 Fall
241
RTT Calculation
Computer Communications
DCS Lab.
ghcho
2001 Fall
242
Smoothing the RTT Measurement
First, we must smooth the RTT due to variations in delay within the
network, as
is typically equal to 0.875
The timeout value is then calculated by multiplying the smoothed
RTT by some factor (greater than 1) called , as
Timeout = X SRTT
This coefficient of is included to callow for some variation in the
round trip times
Computer Communications
DCS Lab.
ghcho
2001 Fall
243
Problem with RTT Calculation
Karn’s algorithm
never update RTT measurements based on acknowledgements
from retransmitted packets
Computer Communications
DCS Lab.
ghcho
2001 Fall
244
Another Problem with RTT Calculation
RTT measurements can sometimes fluctuate severely
Smoothed RTT is not a good reflection of RTT in these cases
Solution : use Jacobson/Karels algorithm:
Computer Communications
DCS Lab.
ghcho
2001 Fall
245
TCP Congestion Control (I)
Congestion control is based on the principle that no new packets
can be allowed until the old one is going (law of conservation of
packets)
TCP achieve this by dynamically manipulating the window size
How do we detect congestion?
Detect congestion is difficult
lost packets could be due
noisy transmission line
congested routers or switches
in WANs, frequent timeouts are typically caused by the
existence of congestion
noisy channels (wireless) lead to timeouts
congested routers, or lack of buffer space at receivers lead
to discarding incoming packets
Computer Communications
DCS Lab.
ghcho
2001 Fall
246
TCP Congestion Control (II)
During connection establishment, you setup window size based
on buffer size
Potential congestion causes are due to network capacity and
receiver capacity
TCP maintain two windows
Receiver Window(RW) - determined by buffer size
Congestion Window(CW) - proportion to network capacity
Number of bytes that can be transmitted is the minimum of the
receiver window and the congestion window
Examples
if the RW says the sender can transmit 8K, but the CW is
only 4K, the the sender may only transmit 4K
The TCP congestion control algorithm makes use of :
slow start
congestion avoidance (linear increase thresholds)
Computer Communications
DCS Lab.
ghcho
2001 Fall
247
TCP Congestion Algorithm (Slow Start)
Sender initializes the congestion window to maximum segment size
and the receiver window to maximum buffer space
TCP slow start
congestion window starts small, at 1 segment size
each time a transmitted segment is acknowledged, the
congestion window is increased by one maximum segment size
Congestion window keeps growing exponential until it becomes
equal to receiver window
Packet losses indicate congestion
these are determined by using timers at the sender
When a timeout occurs, the congestion window is reduced to one
maximum segment size and everything starts over
this leads to low throughput
Computer Communications
DCS Lab.
ghcho
2001 Fall
248
Slow Start
Computer Communications
DCS Lab.
ghcho
2001 Fall
249
TCP Linear Increase Threshold (I)
Establish a threshold at which the rate increase is linear instead of
exponential to improve efficiency
Algorithm
start the threshold at 64K
start the congestion window size at 1 segment size
increase the congestion window size exponentially using slow
start until the threshold is reached
once the threshold is passed only increase the congestion
window size by 1 segment size for each congestion window of
data transmitted
if a timeout occurs, reset the congestion window size to 1
segment and set threshold to ½ of MIN (sliding window,
congestion window)
Computer Communications
DCS Lab.
ghcho
2001 Fall
250
TCP Linear Increase Threshold (II)
Computer Communications
DCS Lab.
ghcho
2001 Fall
251
UDP
UDP is an unreliable transport protocol
UDP does not provide:
flow or error control
connection management
guaranteed in-order packet delivery
UDP is almost a “null” transport layer
Why UDP?
no connection needs to be set up
throughput may be higher because UDP packets are
easier to process, especially at the source
the user doesn’t care if the data is transmitted reliably
the user wants to implement his or her own transport
protocol
Computer Communications
DCS Lab.
ghcho
2001 Fall
252
UDP Protocol
Specified in RFC 768
Low overhead since there’s not much for it to do: header is 8 octets
length field specifies length of the entire UDP segment (header
+ data)
checksum applies to segment plus pseudo-header and is same
as with TCP
on error segment is just discarded
Computer Communications
DCS Lab.
ghcho
2001 Fall
253
The Domain Name System (DNS)
Client/Server based protocol
client is any application needing to “look-up” a name
reference to get the corresponding IP #
client uses library of routines called Resolver to formulate,
send & interpret requests
server is a DNS server that maintains a database of
mappings and responds to requests
use UDP to avoid overhead of connection
Operation
client uses resolver routines to formulate a request and
send it to DNS server via UDP
server looks up the name and gets the number (“you know
my name, look up the number!”)
server sends packet back with the information to the
resolver
resolver gives the IP number to the client
clients can procede with it’s business
Computer Communications
DCS Lab.
ghcho
2001 Fall
254
DNS Hierarchical Namespace (I)
From the days when the Internet was much smaller and more
“controlled”
Specified layers of domains in an inverted tree (like a unix file
system)
Below the “root” are the top-level domains
Originally just a few: .com, .mil, .edu., .org, .gov, .net
Like a directory structure each of the domains can be
subdivided into sub-domains
Sub-domains can be subdivided as well (ad nauseam)
Once we settle on a subdomain that we do not further divide
(a leaf on the inverted tree) we add prefixes (hostnames) to
identify the hosts organized within that subdomain
Computer Communications
DCS Lab.
ghcho
2001 Fall
255
DNS Hierarchical Namespace
Recall that the IP space itself can be divided into a hierarchy
some bits designate network number
some bits designate host number
hierarchy of networks containing hosts
Note: despite this apparent similarity the mapping of names to
numbers is completely arbitrary
Hostname alone (e.g. “bozo”)
unqualified
may be duplicated across many domains but not in same
domain
Traverse the tree from the host to the root, with each level
separated by a “.”
fully Qualified Domain Name
uniquely identifies the host
Computer Communications
DCS Lab.
ghcho
2001 Fall
256
DNS Hierarchical Namespace
com
edu
arizona
ece
cs
mit
gov
mil
burger_col
lpl
...
ClownClg
animal
trapeze
bozo.slapstick.ClownClg.edu
Computer Communications
DCS Lab.
ghcho
slapstick
bozo
krusty
2001 Fall
257
DNS Hierarchical Namespace (III)
A name refers to a specific node in the tree and everything
under it
Names may be absolute “bozo.slapstic.ClownClg.edu.”
Names may be relative
interpreted within some context
e.g. in context of UA - aztel.radiology refers to
aztel.radiology.arizona.edu
Components limit to 63 chars and fully qualified name limited
to 255 chars
Computer Communications
DCS Lab.
ghcho
2001 Fall
258
DNS Domain Management (I)
Within each domain the method for allocating subdomains can
differ
Adding new subdomains requires authorization for
organization managing the next level up in the tree
e.g. CCIT Telecom manages Arizona.EDU
adding a new subdomain (usually for a specific campus
unit) requires their authorization
Within that new domain subdomains can be created without
permission of higher level
The namespace allows names to follow organizational
boundaries instead of physical or network boundaries
Therefore, two hosts in the same subdomain (e.g.
radiology.arizona.edu) may reside on different IP subnets
(need to be routed)
Computer Communications
DCS Lab.
ghcho
2001 Fall
259
DNS Domain Management (II)
Conversely, two machines on different subdomains
(zeki.radiology, db.aemrc) can be on the same physical LAN
and may or may not share the same IP subnet
Think about what each of the clauses in the preceeding
sentence imply (you should now know)
We want to have a distributed name service since that’s more
reliable and more responsive
divide the DNS namespace into non-overlapping Zones
each zone contains a portion of the tree (may span levels)
each zone has name servers which maintain authoritative
information for that zone
mostly one Primary for a zone, maybe some Secondary
servers (some may be in another zone)
Computer Communications
DCS Lab.
ghcho
2001 Fall
260
DNS Database (I)
Maintains Resource Records
set of resource records associated with every domain
Nameserver returns resource records
5-tuple stored in binary format (for efficiency & speed)
Domain_name TTL Type Class Value
domain_name
indicates the domain for which this record applies
usually will be many resource records for a typical
domain
TTL (Time-to-live)
Large number indicates data is very stable, small
indicates it is volatile (likely to change in short time)
Computer Communications
DCS Lab.
ghcho
2001 Fall
261
DNS Database (II)
type
indicates the kind of record
some examples are:
– SOA Start of Authority Info about this zone
– A
Host IP Address
32-bit integer (dotted decimal)
– MX
Mail Exchange
domain willing to accept email
– NS
Name Server
Name of server for this domain
– PTR
Alias for IP
Reverse name
– HINFO Host infor
ascii info about host
class
indicates the type of information
always IN for Internet networking
value
the value for the record with semantics depending on the type of
records
may be a number, ascii text or domain name
Computer Communications
DCS Lab.
ghcho
2001 Fall
262
DNS Database
; radiology.db - Zone file for Radiology.Arizona.EDU
; Subnet in Radiology Research Lab, AHSC
@
IN
SOA AHSC.Arizona.EDU.
postmaster.AHSC.Arizona.EDU. (
895020115
; serial prev was 895020116
43200
; refresh - 12 hrs
21600
; retry - 6 hrs
604800
; expire - 1 week
86400 )
; minimum - 1 day
IN
NS AHSC.Arizona.EDU.
IN
NS Arizona.EDU.
Radiology.Arizona.EDU.
IN A
128.196.106.2
IN
MX
10 AHSC.Arizona.EDU.
IN
HINFO "DEC 3400 AXP" "OSF1"
Lola
IN A
128.196.112.2
IN
MX
10 Lola.Radiology.Arizona.EDU.
IN
MX
20 AHSC.Arizona.EDU.
IN
HINFO "DEC 3000/300X" "OSF-1"
Computer Communications
DCS Lab.
ghcho
2001 Fall
263
Nameservers (I)
Usually a Primary server for a Zone and perhaps one or more
Secondaries
Suppose resolver sends request to primary
if request is for name in this domain primary resolves it
and returns the authoritative resource record
authoritative => comes from entity responsible and is
always correct
Computer Communications
DCS Lab.
ghcho
2001 Fall
264
Nameservers (II)
Suppose resolver sends request to primary
if request is for some other domain no information will be
on the primary
primary sends a request to the top level server for the
domain specified in the request
top level server forwards request to appropriate lower level
server
each response satisfies a request (successfully or
unsuccessfully) and the results work their way back to the
original requestor
Servers will usually cache some information in case another
request comes along
This info is non-authoritative since it is held by a server which
does not have authority for the domain
TTL field specifies when to flush these out
If no response comes back before a timer expires client will
usually try other servers (in case of server crash, etc.)
Computer Communications
DCS Lab.
ghcho
2001 Fall
265
Lecture Topic 6
Network Programming
Programming interfaces
An example of client-server programming
Computer Communications
DCS Lab.
ghcho
2001 Fall
266
Network Programming - TCP/IP
Application
Application
OSI 5-7
OSI 4
OSI 3
TCP Entity
ICMP
OSI 1 & 2
Computer Communications
UDP Entity
IP Entity
ARP
DL & Physical NIC
DCS Lab.
ghcho
2001 Fall
267
RARP
Network Programming - API’s
Provides Applications Programming Interface (API)
the interface available to applications programmer
For Unix two common API’s
Berkeley Sockets
Transport Layer Interface (TLI)
For Berkeley sockets
wanted to maintain the flavor of Unix file I/O facilities (file
descriptor, open, create, close, read, write & lseek) socket like a file descriptor
recognize asymmetry of client/server relationship
network I/O requires more parameters than file I/O association = {protocol, local-addr, local-process, foreignaddr, foreign-process}
original socket interface supported Unix domain; TCP/IP;
and XNS
Computer Communications
DCS Lab.
ghcho
2001 Fall
268
Using Sockets - Connection Oriented
Example
Server
socket()
bind()
listen()
socket()
accept()
block
connect()
write()
read()
process
write()
Computer Communications
read()
DCS Lab.
ghcho
2001 Fall
269
Client
Using Sockets - Connectionless
Example
Server
socket()
bind()
socket()
recvfrom()
bind()
block
sendto()
process
sendto()
Computer Communications
recvfrom()
DCS Lab.
ghcho
2001 Fall
270
Client
Socket Address Structure
Generic Socket Address Structure (sys/socket.h)
struct sockaddr {
u_short sa_family;
/* address family: AF_XXX */
char
sa_data[14]; /* protocol-specific address */
}
Internet Address Structure (netinet/in.h)
struct in_addr {
u_long s_addr;
/* 32-bit IP address */
}
struct sockaddr_in {
short
sin_family; /* AF_INET */
u_short
sin_port;
/* 16-bit Port Number */
struct in_addr sin_addr;
/* 32-bit IP Address */
char
sin_zero[8]; /* padding */
}
Computer Communications
DCS Lab.
ghcho
2001 Fall
271
Network Programming System Calls
We have to specify the parameters of an association before we can
communicate
{protocol, local-addr, local-process, foreign-addr, foreign-process}
We use arguments to system calls to specify one or more elements of
the association
Some elements may be returned to our process by as a result of
system calls
Computer Communications
DCS Lab.
ghcho
2001 Fall
272
socket ()
#include <sys/types.h>
#include <sys/socket.h>
int socket (int family, int type, int protocol);
protocol
IPPROTO_IP
IPPROTO_ICMP
IPPROTO_GGP
IPPROTO_TCP
IPPROTO_EGP
IPPROTO_PUP
IPPROTO_UDP
IPPROTO_IDP
IPPROTO_HELLO
IPPROTO_RAW
dummy for IP
control message protocol
gateway^2 (deprecated)
tcp
exterior gateway protocol
pup
user datagram protocol
xns idp
Fuzzball HELLO protocol
raw IP packet
type
SOCK_STREAM
stream socket (TCP)
SOCK_DGRAM
datagram socket (UDP)
SOCK_RAW
raw-protocol interface (IP)
SOCK_RDM
reliably-delivered message
SOCK_SEQPACKET sequenced packet stream
NOTE: Usually use zero (0 = IPPROTO_IP) for protocol field
Computer Communications
DCS Lab.
ghcho
2001 Fall
273
socket ()
family
AF_UNSPEC
AF_UNIX
AF_INET
AF_IMPLINK
AF_PUP
AF_CHAOS
AF_NS
AF_NBS
AF_ECMA
AF_DATAKIT
AF_X25
AF_NETMAN
unspecified
local to host (pipes, portals)
internetwork: UDP, TCP, etc.
arpanet imp addresses
pup protocols: e.g. BSP
mit CHAOS protocols
XEROX NS protocols
nbs protocols
european computer mftrs
datakit protocols
X25 protocols
Phase V network management
Computer Communications
DCS Lab.
ghcho
AF_CCITT
AF_SNA
AF_DECnet
AF_DLI
AF_LAT
AF_HYLINK
AF_BSC
AF_DSS
AF_APPLETALK
CCITT protocols, X.25
IBM SNA
DECnet
Direct data link interface
LAT
NSC Hyperchannel
BISYNC 2780/3780
Dist. system services
Apple talk
AF_OSI
OSI Protocols
2001 Fall
274
socket ()
sockfd = socket(AF_INET, SOCK_STREAM, 0);
Returns a small integer - socket descriptor
The socket call only specifies one element (the protocol) of
the 5-tuple describing an association
Before the socket can be useful we have to specify the
remaining parameters
The calls used depend on the role and type of service
Protocol
local-addr, local-proc
bind()
CO Cli
socket()
socket()
CL Srvr
socket()
bind()
recvfrom()
CL Cli
socket()
bind()
sendto()
CO Srvr
Computer Communications
DCS Lab.
ghcho
foreign-addr, foreign -proc
listen(),accept()
connect()
2001 Fall
275
bind()
int bind (int sockfd, struct sockaddr *myaddr, int addrlen);
Assigns a name to an unnamed socket and fills the local-addr and
local-process parameters of the association
*myaddr points to a protocol specific address structure
addrlen is sizeof(*myaddr)
Three uses for bind()
servers register their “well known” address with the system - must
do before connection requests can be serviced
CO Clients may register a specific address for themselves
CL Clients need this to get a valid “return address”
Returns negative number if any error
Computer Communications
DCS Lab.
ghcho
2001 Fall
276
connect()
int connect(int sockfd, struct sockaddr *srvaddr, int addrlen);
Used by client to req. estab. of a conn. to a remote server
May result in exchange of multiple messages between TL entities to
negotiate service parameters
Client does not have to use bind() first - connect() fills in local-addr, localprocess, foreign-addr, foreign-process
Can be used by connectionless client to store address of destination
(allows use of send() instead of sendto())
Returns negative number if any error
Computer Communications
DCS Lab.
ghcho
2001 Fall
277
listen()
int listen (int sockfd, int backlog);
Used by connection-oriented server to indicate that it is willing to
receive connections
it is executed after socket and bind system calls
Backlog indicates how many processes can be quueed before the
server can execute the accept system call (it is normally set to 5)
Computer Communications
DCS Lab.
ghcho
2001 Fall
278
accept()
int accept (int sockfd, struct sockaddr *peer , int *addrlen);
A fter a connection-oriented server executes the listen system call, an
actual connection request from the client is served by the accept
system call
It takes the first connection request on the queue and creates another
socket with the same properties as sockfd
The peer and addrlen arguments are used to return the address of
the connected peer process (client)
addrlen is normally refers to the actual buffer needed to store the
peer argument (16 bytes)
Computer Communications
DCS Lab.
ghcho
2001 Fall
279
send(), sendto()… recv(), recvfrom()
int send(int sockfd, char *buff, int nbytes, int flags);
int sendto(int sockfd, char *buff, int nbytes, int flags,
struct sockaddr *to, int addrlen);
These system calls are similar to write system calls
the flags argument is either zero
MSG_OOB send or receive out-of-band data
MSG_PEEK peek at incoming message (recv or recvfrom)
MSG_DONTROUTE bypass routing (send or sendto
Returns negative number if any error
int recv(int sockfd, char *buff, int nbytes, int flags);
int recvfrom (int sockfd, char *buff, int nbytes,
int flags, struct sockaddr *to, int addrlen);
Returns negative number if any error
Computer Communications
DCS Lab.
ghcho
2001 Fall
280
close()
int close(int fd);
It uses the same Unix close system call to close a socket
connection
if the socket closed associated with reliable protocol, the system
must assure that any data within the kernel that has to be
transmitted or acknowledged, is sent
Computer Communications
DCS Lab.
ghcho
2001 Fall
281
Byte Operations
Unix provides routines that can manipulate various socket address
structures
bcopy (char *src, char *dest, int nbytes);
bzero(char *dest, int nbytes);
int bcmp *char *ptrl, char *ptr2, int nbytes);
Address conversion routines : these routines convert between the
dotted-decimal format and int_addr structure
unsigned long inet_addr (char *ptr);
char *inet_ntoa(struct in_addr inaddr);
Computer Communications
DCS Lab.
ghcho
2001 Fall
282
A Simple CO Server
#define SERV_UDP_PORT 6543
#define SERV_TCP_PORT 6543
#define SERV_HOST_ADDR “192.43.235.6”
#include “inet.h”
main (int argc, char *argv[]) {
int sockfd, newsockfd, clilen, childpid;
struct sockaddr_in cli_addr, serv_addr;
/* open a TCP Socket (an internet stream socket) */
if ( (sockfd = socket (AF_INET, SOCK_STREAM, 0) < 0 )
error_exit ( “Server can’t open stream socket”);
/* bind our local address so that the client can send to us */
bzero((char*) &serv_addr, sizeof (serv_addr));
serv_addr.sin_family = AF_INET;
serv_addr.sin_addr.s_addr = htonl (INADDR_ANY) ;
serv_addr.sin_port = htons (SERV_TCP_PORT) ;
Computer Communications
DCS Lab.
ghcho
2001 Fall
283
if (bind(sockfd, (struct sockaddr *)
&serv_addr, sizeof (serv_addr )) < 0)
error_exit (“Server can’t bind local address”);
listen(sockfd, 5);
for(;;){
/* wait for a connection from a client process */
clilen = sizeof(cli_addr);
newsockfd = accept(sockfd, (struct sockaddr *)
&cli_addr, &clilen);
if ( newsockfd < 0)
error_exit(“Server error accepting connection”);
if ((childpid = fork()) < 0)
error_exit (“Server error forking child process”);
else if (childpid == 0){ /* 0 => we’re the child */
close (sockfd ); /* close original socket*/
ServerWork (newsockfd );
/* process the request*/
exit (0);
}
close ( newsockfd );
/* parent process */
}
Computer Communications
DCS Lab.
ghcho
2001 Fall
284
A Simple CO Client
#include “inet.h”
main (int argc, char *argv[]) {
int
sockfd;
struct sockaddr_in
serv_addr;
pname = argv[0];
/* Fill in the structure “serv_addr” with the address of
/* the server that we want to connect with */
bzero ( (char*) & serv_addr, sizeof ( serv_addr ));
serv_addr.sin_family = AF_INET;
serv_addr.sin_addr.s_addr =
inet_addr ( serv_host_addr);
serv_addr.sin_port = htons(serv_tcp_port);
Computer Communications
DCS Lab.
ghcho
2001 Fall
285
/* Open a TCP Socket (an internet stream socket)
f ( (sockfd = socket(AF_INET, SOCK_STREAM, 0) < 0)
error_exit(“Client can’t open stream socket”);
/* Connect to Server */
if (connect (sockfd, (struct sockaddr *)
& serv_addr, sizeof (serv_addr)) <0 )
error_exit (“Client can’t connect to server”);
ClientWork (stdin, sockfd);
/* do all the work here
*/
close (sockfd);
exit (0)
}
Computer Communications
DCS Lab.
ghcho
2001 Fall
286