Transcript Document

Understanding Networked Applications:
A First Course
Chapter 18
by
David G. Messerschmitt
Objectives
• Major functions of the network
• Impact of network on application
performance
• Collective issues in networking
Understanding Networked Applications
2
A First Course
Impact of network on
applications
• Communication service provided the
application
– What does application have to do for itself?
• Impact on application performance
– Message (packet) latency
– Message (packet) loss
– Message (packet) corruption
Understanding Networked Applications
3
A First Course
Internet protocol architecture
Application
Remote method invocation (RMI)
Datagram (UDP)
Bytestream session (TCP)
Middleware
OS
Internetworking (IP)
Network
Subnetworks
Understanding Networked Applications
4
A First Course
Network topology
Switches
Hosts
Backbone
links
Access links
Understanding Networked Applications
5
A First Course
Properties of a communication
link
Bits waiting to
be sent
Bits in
transit
Bits that have
arrived
00110110
010101110101010
00001011011011
Bitrate = number transmitted per second
(Bitrate is sometimes called “bandwidth”)
Propagation delay = input-output delay experienced by each bit
Understanding Networked Applications
6
A First Course
Sending packets on a link
0101101011010011011010110101010101011010
Packet 1
Packet 2
Packet 3
Bitrate > # packets per sec x average size of a packet
There must be some way (bit patterns) for the
receiver to distinguish packets
Understanding Networked Applications
7
A First Course
Statistical multiplexing
Messages on three
incoming links
Queues
Single
outgoing
link
What are some other examples of
statistical sharing?
Understanding Networked Applications
8
A First Course
Congestion
• Cause: irregular packet arrivals, and
irregular packet length
• Direct effect: sometimes more packets have
to wait in queues for space on output link
– In severe cases, packets discarded
• Indirect effect: waiting time in queues
contributes to packet (and hence message)
latency
Understanding Networked Applications
9
A First Course
Packet structure
• Header
Header
Payload
– Indicate beginning of packet
– Destination address for forwarding
– Other information specified by network
protocols
• Payload
– Unstructured data to be delivered to application
Understanding Networked Applications
10
A First Course
Packet forwarding
Packet switch
Packet


Addr
OutLink
Output link

Routing table
Understanding Networked Applications
11
A First Course
Two basic functions in packet
switching
• Packet forwarding
– Transmitting each packet on the appropriate
output link
– Based on routing table
• Routing
– Updating the routing table
– Objective: each packet gets closer to destination
via less congested links
Understanding Networked Applications
12
A First Course
Routing
• Full route not written down
• Each packet switch has >1 output link
• Routing table :
Final Destination Next hop
141.211.203.32
X
207.75.186.1
Y
• Reducing table size
– use wildcards: 141.211.* next hop is X
Understanding Networked Applications
13
A First Course
Routing function
• Switches (routers) talk to each other
– “I’m now accepting traffic for 141.211.*”
• Called “advertising a route”
– “Is anyone accepting traffic for 141.211.*?”
• Update entries in own routing table
• Sophistication is in deciding whether to
accept traffic
Understanding Networked Applications
14
A First Course
Routing Dangers
• Long routes
• Circular routes
– HopLimit limits damage
– Decrement HopLimit at each router
– Discard packet if HopLimit=0
• Hijacking routes
– Advertise a route, but don’t deliver
• Route flapping
– Frequent updates to routing table
Understanding Networked Applications
15
A First Course
Packet delivery not guaranteed
• Intermediate switch not responding
– Temporary malfunction
– Queues full (congestion)
• Bad routing
– Too long or circular
• Corruption of packet, especially header
• Network does not inform sender
– Network may not know!
Understanding Networked Applications
16
A First Course
Why packets?
• Fairness: short message doesn’t have to wait
for long message
– Allows messages to be sent concurrently
– Reduces statistical waiting time
• Store and forward delay reduced
• Data garbling may necessitate resending
only a packet, not a whole message
Understanding Networked Applications
17
A First Course
IP Addresses
• Every host gets a distinct address
– Can be dynamically assigned
• IPv4 (current standard)
–
–
–
–
Recall three ways of
locating something:
Each address 32 bits
Divide into 8 bit segments
Example: 141.211.203.32
4 billion addresses
• Address
• Name
• Reference
• IPv6 (future standard)
– Each address 128 bits
– ~1500 addresses per square foot
Understanding Networked Applications
18
A First Course
Domain Name Service
• IP addresses are inconvenient for people
– 32 bits hard to remember
– 128 bits very hard to remember
• Domain names
– e.g. www.sims.berkeley.edu
• Domain Name Service (DNS)
– get an IP address from a domain name
Understanding Networked Applications
19
A First Course
Hierarchy in location
• Addresses hierarchical in topology
– Maximize “wild cards” and distribute address
administration
• Names hierarchical in administration
– Single administered organizations often
distributed topologically (e.g. ibm.com)
• DNS decouples these two issues
Understanding Networked Applications
20
A First Course
Forms of broadcast
Simulcast
Multicast
Multicast requires more
sophisticated addressing and
routing within the network
Understanding Networked Applications
21
A First Course
Flow control
Queue
Producer
Consumer
Stream
of messages
Flow control
Normally the producer determines what information
is sent, but consumer has to have a way to slow
down producer
Understanding Networked Applications
22
A First Course
Network congestion
• Fluctuations of traffic can result in
overloads in given network links
– Failure of statistical multiplexing
• Analogous to processing congestion of a
server, except resent packets can make the
problem worse
• Congestion must be limited in some fashion
Understanding Networked Applications
23
A First Course
Carried
traffic
Congestion instability
Network “capacity”
Increasing portion of
network traffic is resent
packets
Offered
traffic
Social
optimum
Understanding Networked Applications
24
A First Course
Questions to address
• What social objectives should a congestion
control method achieve?
• What technical approaches are available to
achieve those objectives?
• What is the cost of those approaches?
• Ultimately, what will the customer pay for
congestion control, and how does that relate
to the value received?
Understanding Networked Applications
25
A First Course
Congestion control methods
• Over-provisioning of facilities (mitigation, not control)
• Network initiated
– Network  source flow control, or
– Source notification and policies, policing, or pricing incentives, or
– Admission control for sessions
• Sources initiated
– Source detects congestion (necessary resent packets is one
method), and
– Voluntary or mandatory policies
Examples of each?
Understanding Networked Applications
26
A First Course
Understanding Networked Applications:
A First Course
Quality of service (QoS)
by
David G. Messerschmitt
QoS attributes of a packet
• Packet latency
– Time until packet delivered at destination
– Transmission time, propagation time, queuing delay,
processing time
• Packet loss
• Packet corruption
– Payload only
– Normally network will not deliver corrupt packet
Understanding Networked Applications
28
A First Course
Transport services
• “Raw” packet service is not what is needed by
most applications
• Transport services “condition” packet service by
adding layers
–
–
–
–
–
Reliable delivery
Message service
Session
Time stamps
etc
Understanding Networked Applications
29
A First Course
Packet latency affects transport
service QoS
Stream of
packets
Audio
coder
Audio
decoder
Packet
latency
End-to-end
delay
Understanding Networked Applications
30
A First Course
Reliable delivery
• Add acknowledgement for each packet
• Lost packet can be detected by missing
ACK
• Lost packet can be retransmitted
• Tradeoff:
– Reliable delivery for greater latency
– Latency-sensitive applications must abandon
reliable delivery (e.g. remote conferencing)
Understanding Networked Applications
31
A First Course
QoS Guarantees
• Source and network enter “session
contract”:
– Source promises not to exceed specified traffic
parameters for that session
• Rate and burstiness
– Network promises to limit impairments such as
latency, loss, and corruption
Understanding Networked Applications
32
A First Course
Achieving QoS
• TCP/IP offers only best-effort
– Every connection gets “best-effort” service
• Achieving maximum latency guarantees
– Reserve resources
– Or attach priorities to packets
• Contract may allow network to delay or discard low-priority
packets when necessary
– Application may guarantee traffic “shape”
• e.g., steady flow rather than bursts
Understanding Networked Applications
33
A First Course
Pricing and Accounting
• What’s the incentive for using low quality
service?
– Why should user accept greater latency if less is
an option?
– Why should application try to minimize
bandwidth, or shape its traffic?
– Answer is good citizenship, or pricing
incentives
Understanding Networked Applications
34
A First Course
Pricing Today
• Commercial services: usually flat rate plus
connect time (but no per-bit charges)
– e.g., CompuServe, Prodigy, America On-Line
• Internet: flat rate, unlimited usage
– Resellers can charge for connect time
– Many people have unlimited use through a
university or company
Understanding Networked Applications
35
A First Course
Pricing options
Price component
Fixed
Usage
QoS
Congestion
Cost recovery
Capital/operational costs of access
network
Shared costs of backbone network
Cost of reduced statistical
multiplexing advantage
Impact on other users, cost of
upgrading facilities
Understanding Networked Applications
36
A First Course
Congestion Pricing Rationale
• The fixed cost of building the network is high
• The marginal cost of accepting new session is
nearly zero (assuming not congested)
• Economic efficiency: use whenever marginal
benefit > 0
– But capacity is fixed (in the short run)
– Person A’s use may reduce B’s quality of service
Understanding Networked Applications
37
A First Course
Congestion Pricing
• If network is underutilized, charge nothing
• If network is congested
– Charge person A the amount of B’s lost value
– A will drop out unless his value of use is greater than
B’s lost value
• Theorem: this raises enough money to expand the
network by the socially optimal amount
• Monitoring and billing overhead
Understanding Networked Applications
38
A First Course
Big advantage of pricing
• Congestion pricing uses incentives rather than
forced control or policies to affect user/application
behavior
– Market mechanism like other goods and services
• User/application can determine freely and
independently whether use of network during
periods of congestion is warranted
• Major objection is cost of monitoring and billing
Understanding Networked Applications
39
A First Course