Transcript chapter1

Advanced Data Networks
Chapter #1
Instructor: Syed Ismail Shah, PhD
Department of Computing & Technology
Iqra University
Course Information
Textbook
-“Computer Networks: A Systems Approach”
By L. Peterson, and B. Davie, 4th edition, MKP.
References
-“Data Networks”
By D. Bertsekas, and R. Gallager, 2nd edition
- “Computer Networks”
By A. S. Tanenbaum, 4th edition
- “TCP/IP Protocol Suite”
By Behrouz A. Forouzan
Required Software
OPNET IT Guru (Academic Edition)
2
Class Expectations
•
•
•
•
•
•
Come to lectures on time and participate
Keep up with reading material
Complete assignments, projects, etc on time
Submit clean, organized, and to the point reports
Identify potential project partners early
Familiarize yourself with lab environment (OPNET)
3
Key to Success
• Attendance
– Pay attention to lectures and keep extra notes
– Ask questions
• Effort
– Do homework on your own. It’s ok to ask others but
make your own effort.
• Consistency
– Keep up with reading, homework, and labs
4
Plagiarism Policy
• According to this policy, a student's submitted
work must be the student's own. In this course,
this policy will be applied to all work submitted
for grade including exams, quizzes, homework,
and projects.
• Copying from solution manuals is strictly
forbidden; anyone violating this policy will
receive zero credit for the entire semester.
Repeated violations may result in F grade in the
course.
5
Topics to be covered
•
•
•
•
•
•
•
Network architectures, performance metrics, layering
Direct-link networks
Medium access control
Internetworking, routing
End-to-end protocols, flow control
Congestion control and resource allocation
Applications
6
Networks and Computer Networks
• What is a network?
CATV
network
PSTN network
• How do computer networks differ?
7
Requirements
• Goal is to understand how to build a computer
network from ground up
• First step is to identify set of constraints and
requirements that influence network design
• Before getting started, it is important to
understand the expectations for designing a
network
Requirements
• An application programmer would list the services that
his application needs e.g. error free and on time delivery
of the messages sent by his application
• A network designer would list the properties of a cost
effective design e.g. efficient utilization and allocation of
network resources
• A network provider would list the characteristics of
system that is easy to administer and manage e.g. in
which faults can be easily isolated and where it is easy
to account for usage
Network Elements
• Nodes: Special purpose elements
PC
server
switch
bridge
router
• Links: Connections between nodes
Optical fiber
Coaxial cable
wireless
10
Network design
• The task of connecting nodes via links, so that
nodes can exchange data
• Need to define the network architecture
• Examples
– Directly connected networks
– Circuit-switched networks
– Packet-switched Networks
11
What drives network design?
• Applications
– WWW, email, chat, videoconferencing, e-commerce,
audio/video streaming, VOIP, file sharing
• Who deploys the network
– Enterprise, government, end-user
• Where is the network deployed
– Home, building, campus, state, country, continent,
globe
12
Connectivity
• Network connectivity occurs at different levels
• At the lowest level, a network can consist of two
or more computers directly connected by a
physical medium such as a coaxial cable
• Such a medium is called a link and computers
connected to it are referred to as nodes
• Sometimes node is special purpose device instead
of a computer
13
Directly-Connected Networks
• Point-to-point links: Each node is directly
connected to all others via a link
• Multiple access: All nodes share the same
physical medium
point-to-point
multiple access
14
Directly-Connected Networks
• Multiple access links are often limited in size in
terms of
– The geographical distance they can cover
– The number of nodes they can support
• If networks were limited to situations where all
nodes were directly connected then networks
would either be
– limited in number of nodes they can connect
or
– number of wires coming out of each node would have
been unmanageable
15
Directly-Connected Networks
• Fortunately, connectivity between two nodes
does not necessarily implies a direct physical
connection between them-indirect connectivity
can also be achieved
• This is achieved via
a switched network
• Two types of nodes exist
– End nodes
– Intermediate nodes
16
Switched Networks
• Circuit-Switched
terminal/
host
– A dedicated circuit is
established across a set of links
– Example: Telephone network
• Packet-Switched
– Data is split into blocks called
packets or messages.
– Store-and-forward strategy
– Switches: Store and forward
packets
switch
17
Circuit-Switched Networks
• End-to-end permanent connection
– Dedicated path for communication
– No need for a destination address since a path is
already established
• Once communication is complete, connection is
ended and links are released.
18
Advantages of Circuit Switching
• Guaranteed bandwidth (Quality of Service)
– Predictable bit rate and delay
– Good for delay-sensitive applications
• Reliable communication
– Rare loss of data
– Packets are delivered in order
• Simple data routing
– Forwarding based on time slot or frequency (multiplexing)
– No need to inspect a packet header for address
• Low per-packet overhead
– Forwarding based on time slot or frequency
– No IP (and TCP/UDP) header on each packet
19
Disadvantages of Circuit Switching
• Wasted bandwidth
– Bursty traffic leads to idle connection during silent period
• Blocked connections
– Connection refused when resources are not sufficient
– Unable to offer “okay” service to everybody
• Connection set-up delay
– No communication until the connection is set up
– Unable to avoid extra latency for small data transfers
• Network state
– Network nodes must store information per-connection
– Unable to avoid per-connection storage and state
20
Packet Switched Networks
• Data is divided into packets (messages)
– Each packet contains identification information
(source/destination address seq. number, etc)
• Packets traverse the network individually
– Use the destination address to forward packets
– May use more than one routes, nodes may store
packets temporarily
21
Advantages of Packet Switching
• Less wastage of bandwidth
– Links are not reserved during idle period
• Multiplexing (see next slides)
– Frequency, time, statistical multiplexing
• Service
– More connections of lesser quality
– No blocking of users
• Adaptation
– Can adopt to network congestion and failures
22
Disadvantages of Packet Switching
• No guaranteed bandwidth
– Harder to build applications requiring QoS
• Per packet overhead
– Need a header with source/dest. address, etc.
• Complex end-to-end control
– Packets can be lost, corrupted or delivered out-oforder
• Delay and Congestion
– No congestion control, can lead to arbitrary delays and
packet drops
23
Internetwork
• A collection of interconnected
networks
Internet[work]
• Networks: Different departments,
labs, etc.
• Router: A node that connects
distinct networks
• Host: network endpoints
CS
MS
EE
Internetwork Challenges
• Many differences between
networks
– Address formats
– Performance – bandwidth &
latency
– Packet size
– Error rate
– Routing
• How to translate and interoperate?
– Routers are key to many of
these issues
Internet[work]
ATM
802.3
Frame
relay
1.2.2 Cost Effective Resource Sharing:
Multiplexing
• A pair of nodes indirectly connected hosts can
send messages to each other across a sequence of
links
• Our requirement is to provide multiple pair of
nodes to exchange nodes over these series of
links
• Question: How do all the hosts share the
medium?
• Answer: Multiplexing
26
Multiplexing
Three pairs of senders/receivers
share the same physical link to
communicate
A switch is multiplexing packets
from different senders into one
packet stream (Statistical TDM)
27
Multiplexing Methods
• Time Division Multiplexing
S1
S2
S3
S1
S2
S3
S1
S2
S3
S1
S2
S3
time
• Frequency Division Multiplexing
frequency
f3
S3
f2
S2
f1
S1
time
28
Multiplexing Methods
• Statistical multiplexing
– Division of the communication medium into a number
of channels of variable bandwidth (more precisely
packet sizes)
29
1.2.3 Support for Common Services
• Network applications involve communication of two or
more hosts
• Often, complex functions need to be realized
• Can think of application communication in an abstract
way
logical channel
network cloud
30
Common Services
• Think of network as providing means for set of
application processes that are distributed over
those computers to communicate
• A lot of complicated things happen (instead of
simply sending messages) when two application
programs communicate
• Challenge for a network designer
Hide the complexity of network from the
application without overly constraining the
application programmer
31
Common Services
• Intuition:
– Think of the network as providing logical channels over which
application level processes communicate
– Each channel providing a set of services required by that
application
• Hence we think of a channel as connecting one process
to another over a network
• Challenge is to identify what functionality the channels
should provide to application programs
– Does application require guaranteed message delivery or is it
acceptable if a few messages fail to deliver?
– Is it necessary that messages arrive in sent order or not?
– Does the network ensure no third party eavesdrop?
32
Common Services
• In essence, a network provide a rich collection of
different channels with each application selecting the
best channel that meets its demands
• Designing abstract channels involves
– Understanding communication needs of applications
– Extracting common communication requirements
– Incorporating functionality that meets the requirements
• An interesting fact is that many applications share
common functionalities
• These functionalities need to be integrated on each
application or abstracted in common services
33
Common Services
• A network designer looks for minimum number of
abstract channels that can serve maximum number of
applications but danger is too few channels
• Thus network designers will continue inventing new
channels as long as application programmers are
inventing new applications
34
FTP vs. Video Conferencing
• Both follow the server-client model
• Establish a request/reply channel, and message stream
channel (one can be reliable, other unreliable)
• Use smallest number of channel abstractions
• FTP utilize request/reply channel
• Video-on-demand and videoconferencing use message
stream channel
35
Layering Abstraction
• Layer: A set of functionalities encapsulated in an object
that can be used by other network components
• Example: The network layer implements the end-to-end
packet delivery
• Why layering? Think complexity and common services
• Layers consist of protocols
36
Layering and Protocols
• Two Layers in-between Physical and
Application Layers
– Process-to-process channels
– Host-to-host connectivity: abstracting the fact that
there may be an arbitrary complex topology
between two hosts.
37
Looking into layers a bit closer
• Protocols in each layer have
– Service interface with upper layer/lower layer
– Peer-to-peer interface with host on same layer
38
Hierarchical Layer Structure
• Layering implies the use of a layer hierarchy
39
A simple layering example
• RRP: Request/reply protocol
• MSP: Message streaming protocol
• HHP: Host-to-host protocol
40
Encapsulation
• The process of embedding a header or trailer
41
The OSI Network Architecture
• OSI: Open Systems
Interconnection
• 7 layers X. protocol
specifications for
each layer
• Acts like a reference
model rather than a
real-world protocol
graph
• First three layers are
implemented in all
nodes
42
Layers of the OSI model
• Physical Layer: Transmission/reception of raw bits
• Data Link Layer: Maps bits into frames, dictates sharing of
common medium, corrects/detects errors , re-orders frames
• Network Layer: Routes packets to destination, may perform
fragmentation and re-assembly.
• Transport Layer: Flow (congestion) control, error control,
transparent transport to upper layers
• Session Layer: Establishes connection among hosts, duplex, halfduplex, graceful connection termination, combination of streams
• Presentation Layer: Negotiation of format of data exchanged
between hosts
• Application layer: Application services such as FTP, X.400 (mail),
HTTP
43
The Internet Architecture
FTP
HTTP
TCP
TFTP
Transport
IP
Net 1
Ethernet
DNS
UDP
IP: Internet Protocol: Network or Internet
Net 2
FDDI
TCP: Transmission Control Protocol
FTP: File Transfer Protocol
HTTP: Hypertext Transport Protocol UDP: User Datagram Protocol
TFTP: Trivial File Transfer Protocol FDDI: Fiber Distributed Data Interface
DNS: Domain Name System
44
Comparison of the two architectures
45
Main Driving Goals of IP (In Order)
• Communication should continue despite failures
– Survive equipment failure or physical attack
– Traffic between two hosts continue on another path
• Support multiple types of communication services
– Differing requirements for speed, latency, & reliability
– Bidirectional reliable delivery vs. message service
46
Main Driving Goals of IP (In Order)
• Accommodate a variety of networks
– Both military and commercial facilities
– Minimize assumptions about the underlying network
47
Other Driving Goals, Somewhat Met
• Permit distributed management of resources
– Nodes managed by different institutions
– … though this is still rather challenging
• Cost-effectiveness
– Statistical multiplexing through packet switching
– … though packet headers and retransmissions wasteful
• Ease of attaching new hosts
– Standard implementations of end-host protocols
– … though still need a fair amount of end-host software
• Accountability for use of resources
– Monitoring functions in the nodes
– … though this is still fairly limited and immature
48
1.5 Performance
• Bandwidth
– Amount of data transmitted per unit of time
– Per link, or end-to-end
– Units 1KB = 210 bytes, 1Mbps = 106 bits per sec
• Throughput
– Data that the link or network is able to deliver
– Per link or end-to-end, same units as Bandwidth
49
Latency or delay
• Time for sending data from host A to B
• Per link or end-to-end
– Usually consist of
• Transmission delay
• Propagation delay
• Queuing delay
• Round Trip Time (RTT) : time to send a message
from A to B and back
– Important for flow control mechanisms
50
Delay Calculation
• Propagation Delay: time needed for signal to
travel the medium, Distance / speed of medium
• Transmission Delay: file size/bandwidth
• Queuing Delay: time waiting in router’s buffer
C
d1
A
d2
R
B
51
Example: Problem 1.6 from Book
• Transfer 1,5 MB file, assuming RTT of 80 ms, a packet size of 1KB and an initial “handshake” of 2xRTT
• Bandwidth is 10 Mbps and data packets can be sent
continuously
A
B
RTT = 80 ms
Tt = 1024x8 bits/107 bits/s = 0.8192 ms
Tp = 40 ms
# of packets = 1536 (1.5 x 1024)
request
RTT
reply
confirm
Ack
Tt
D = 2xRTT + 1536xTt + Tp
= 160 + 1258.29 + 40 ms
= 1.458 s
Tp
. . .
t
52
Example: Problem 1.6 from Book
• Transfer 1,5 MB file, assuming RTT of 80 ms, a packet size of 1KB and an initial “handshake” of 2xRTT
• After sending each packet must wait one RTT
A
B
RTT = 80 ms
Tt = 1024x8 bits/107 bits/s = 0.8192 ms
Tp = 40 ms
# of packets = 1536 (1.5 x 1024)
request
RTT
reply
confirm
Ack
Tt
D = 2xRTT + 1535x(Tt +RTT)+ Tt+Tp
= 160 + 124,057 + 0.8192 + 40 ms
= 124.258 s
RTT
. . .
t
53
Example: Problem 1.6 from Book
• Transfer 1,5 MB file, assuming RTT of 80 ms, a packet size of 1KB and an initial “handshake” of 2xRTT
• After sending each packet must wait one RTT
A
B
RTT = 80 ms
Tt = 0 ms
Tp = 40 ms
# of packets = 1536 (1.5 x 1024)
request
RTT
reply
confirm
Ack
D = 2xRTT + 76xRTT + Tp
= 160 + 6080 + 40 ms
= 6.28 s
RTT
. . .
t
54
Example: Problem 1.6 from Book
• Transfer 1,5 MB file, assuming RTT of 80 ms, a packet size of 1KB and an initial “handshake” of 2xRTT
• After sending each packet must wait one RTT
A
B
reply
confirm
Ack
RTT = 80 ms
Tt = 0 ms
Tp = 40 ms
# of packets = 1536 (1.5 x 1024)
# of waits (1+2+…2n = 2n+1 -1)
211 -1 =2047 packets, n = 10
. . .
D = 2xRTT + 10xRTT + Tp
= 160 + 800 + 40 ms
=1s
request
RTT
RTT
t
55
Latency vs. Bandwidth
• Importance depends on application
– 1 byte file, 1ms/1Mbps vs. 100ms/100Mbps
1 ms + 8μs = 1.008ms,
100ms + 0.08μs =100 ms.
– 1GB file, 1ms/1Mbps vs. 100ms/100Mbps
1ms + 10243 x 8 /106 = 2.38h + 1ms,
100ms + 85 s
56
Bandwidth x Delay Product
• The amount of data (bits or bytes) “in the pipe”
• Example: 100Mbps x 10ms = 1 Mbit
• The amount of data sent before first bit arrives
• Usually use RTT as delay: amount of data before
a possible receiver reply arrives
57
High-Speed Networks
Link Type
Bandwidth
Distance
RTT
Delay x BW
Dial-up
56 kbps
10 km
87 μs
5 bits
Wireless LAN
54 Mbps
50 m
0.33 μs
18 bits
Satellite link
45 Mbps
35,000 km
230 ms
10 Mb
Cross-country
fiber
10 Gbps
4,000 km
40 ms
400 Mb
• Infinite bandwidth
– Propagation and RTT delay dominates
– Effective Throughput = Transfer size/Transfer time
– Transfer time = RTT + Transfer size/Bandwidth
– Effective throughput of 1MB file across 1Gbps line (Tx time
=8 ms) and 100ms RTT = 1MB/(108 ms)= 74.1 Mbps.
– Solution: Large packet size????? Disable acknowledgment
??????
58
Computing Application Bandwidth
• FTP can utilize entire BW available
• Video-on-demand may specify upper limit (only
what’s needed)
• Example: res: 352x240 pixels, 24-bit color, 30 fps
– Each frame is (352 x 240 x 24)/8 =247.5 KB
– Total required BW = 352 x 240 x 24 x 30 = 60.8 Mbps
59
Network Jitter
• Variability in the delay between packets
• Video-on-demand application: If jitter is known,
application can decide how much buffering is needed
• Example: jitter is 50 ms per frame and I have 10 s of video
at 30fps.
• If Y frames buffered, video can play uninterrupted for Y x
1/30 s.
• The last frame will arrive 50 x (10 x 30 – Y) ms after video
start, worst case
Y/30 = 50 x (300 – Y)  Y = 180 frames
60
Example: Problem 1.19 from Book
• 1 – Gbps Ethernet with a store and forward switch in the path and a
packet size of 5,000 bits. Tp = 10 μs, switch transmits immediately
after reception
A
Tt = 5 μs
S
B
1st bit: time 0
Last bit: 5μs
Tp
Last bit rec: 15μs
Last bit sent: 20μs
Tp
Last bit rec: 30μs
t
61
Example: Problem 1.19 from Book
• 1 – Gbps Ethernet with a s-a-f switch in the path and a packet size of
5,000 bits. Tp = 10 μs, 3 switches in between A and B
• 4 links equal to 4 Tp delay
• 4 transmissions equal to 4 Tt delay
Total = 4Tp + 4Tt = 60 μs
• Three switches, each transmits after 128 bits are received
Total = 4Tp + Tt + 3x128/(10G) = 40μs + 5μs + 0.384μs = 45.384μs
62