Transcript ppt

CS/ECE 438, CSE 425
Communication Networks
Nikita Borisov
ECE Department, UIUC
Course Information

Instructor



10-12 Tuesdays
or by appointment
Monika Battala, [email protected]
Office hours TBA
http://www.cs.uiuc.edu/class/fa06/cs438
Newsgroup

8/25/06
460 CSL, 244-5385
[email protected]
Webpage


Office Hours:
TA


Prof. Nikita Borisov
class.cs438 on news.cs.uiuc.edu
UIUC - CS/ECE 438, Fall 2006
2
Acknowledgments



8/25/06
Slides are adapted from Prof. Kravets
Some material contributed by Profs.
Luo, Lumetta, Hajek, Vaidya
Some material from Larry Peterson &
James Kurose & Keith Ross
UIUC - CS/ECE 438, Fall 2006
3
Prerequisites

C Programming (CS241)


8/25/06
Pre-req for ECE students is ECE290, but
ECE391/398SSL or C experience highly
recommended
Probability and Statistics (MATH
461,463 or ECE 413)
UIUC - CS/ECE 438, Fall 2006
4
Textbook


Computer Networks: A Top-Down Approach
Featuring the Internet, by Kurose & Ross,
3rd Edition
We will be covering this text out of order





8/25/06
Ch 1
Ch 5 + some of 6
Ch 4
Ch 3
Some of Ch 2
UIUC - CS/ECE 438, Fall 2006
5
Recommended Text


UNIX Network Programming,
Volume 1, by Stevens
There are 3 editions


8/25/06
Second & third edition more up-to-date
First edition (1990) contains more
background on general UNIX
programming
UIUC - CS/ECE 438, Fall 2006
6
Grading Policy

Homework



8/25/06
20%
Oct 12
Programming Projects


7 homework assignments
Mid-term Exam


15%
35%
4 Programming projects
2% off per hour late
Final Exam
30%
UIUC - CS/ECE 438, Fall 2006
7
Homework and Projects

Homeworks:




Projects:


8/25/06
Due Wednesdays at 2:00 in class.
General extension to Thursdays at 2:00pm (hard
deadline).
No questions to TA or on newsgroup after class
on Tuesday.
Project 1: 5%, Projects 2- 4: 10%
Due Fridays at 9:00pm.
UIUC - CS/ECE 438, Fall 2006
8
Academic Honesty




Your work in this class must be your own.
Penalties for excessive collaboration and
cheating are severe
Sharing strategies and small code
fragments (5-10 lines) OK
Sharing homework answers and large
sections of code forbidden


8/25/06
Don’t post these to newsgroup!
If in doubt, ask the professor
UIUC - CS/ECE 438, Fall 2006
9
One Unit Students

Graduate students MAY take an extra unit
project in conjunction with this class

Graduate students





8/25/06
Register for 4 credits
Write a survey paper in a networking research area of
your choice.
Project proposal with list of 10+ academic references
(no URL’s) due September 22
Paper due last day of class
Undergraduates may not take this project course
UIUC - CS/ECE 438, Fall 2006
10
Course Objectives

At the end of the semester, you should be
able to:




8/25/06
Identify the problems that arise in networked
communication
Explain the advantages and disadvantages of
existing solutions to these problems in the
context of different networking regimes
Understand the implications of a given solution
for performance in various networking regimes
Evaluate novel approaches to these problems
UIUC - CS/ECE 438, Fall 2006
11
Programming Objectives

At the end of the semester, you should
be able to



8/25/06
Identify and describe the purpose of each
component of the TCP/IP protocol suite
Develop solid client-server applications
using TCP/IP
Understand the impact of trends in
network hardware on network software
issues
UIUC - CS/ECE 438, Fall 2006
12
Course Contents









8/25/06
Overview
UNIX Network Programming
Direct Link Networks
Multiple Access
Packet Switched Networks
Internetworking
Reliable Transport
Congestion Control, QoS & Fair Sharing
Performance Analysis and Queueing Theory
UIUC - CS/ECE 438, Fall 2006
13
Connectivity

Building Block



8/25/06
Links:
Nodes:
coax cable, optical fiber, …
workstations, routers, …
Links:

Point-to-point

Multiple access
UIUC - CS/ECE 438, Fall 2006
…
14
Indirect Connectivity



Switched Networks
Internetworks
Recursive definition of a
network


8/25/06
Two or more nodes
connected by a physical
link
Two or more networks
connected by one or
more nodes
UIUC - CS/ECE 438, Fall 2006
15
Network Problems

What must a network provide?




8/25/06
Connectivity
Cost-effective Resource Sharing
Functionality
Performance
UIUC - CS/ECE 438, Fall 2006
16
Addressing

Addressing


Routing


The process of determining how to forward
messages toward the destination node based on
its address
Types of Addresses



8/25/06
Unique byte-string used to indicate which node
is the target of communication
Unicast:
Broadcast:
Multicast:
node-specific
all nodes on the network
subset of nodes on the network
UIUC - CS/ECE 438, Fall 2006
17
Effects of Indirect Connectivity

Nodes receive data on one link and forward it onto the
next -> switching network

Circuit Switching





Telephone
Stream-based (dedicated circuit)
Links reserved for use by communication channel
Send/receive bit stream at constant rate
Packet Switching
Internet

Message-based (store-and-forward)

Links used dynamically

Admission policies and other traffic
determine bandwidth

8/25/06
UIUC - CS/ECE 438, Fall 2006
18
Cost-Effective Sharing of
Resources

Physical links and switches must be shared
among many users

Common multiplexing strategies


8/25/06
(Synchronous) time-division multiplexing (TDM)
Frequency-division multiplexing (FDM)
UIUC - CS/ECE 438, Fall 2006
19
Circuit Switching: FDM and TDM
Example:
FDM
4 users
frequency
TDM
time
frequency
time
8/25/06
UIUC - CS/ECE 438, Fall 2006
20
Statistical Multiplexing

Statistical Multiplexing (SM)




On-demand time-division multiplexing
Scheduled on a per-packet basis
Packets from different sources are
interleaved
Uses upper bounds to limit transmission

8/25/06
Queue size determines capacity per source
UIUC - CS/ECE 438, Fall 2006
21
Statistical Multiplexing in a
Switch


Packets buffered in switch until forwarded
Selection of next packet depends on policy


How do we make these decisions in a fair manner?
Round Robin? FIFO?
How should the switch handle congestion?
…
8/25/06
UIUC - CS/ECE 438, Fall 2006
22
Functionality

Support For Common Services

Goal


Idea



Common services simplify the role of applications
Hide the complexity of the network without overly
constraining the application designer
Semantics and interface depend on applications


8/25/06
Meaningful communication between hosts on a
network
Request/reply: FTP, HTTP, DNS
Message stream: video-on-demand, video
conferencing
UIUC - CS/ECE 438, Fall 2006
23
Channels

Channel


The abstraction for application-level communication
Idea

Turn host-to-host connectivity into process-to-process
communication
Host
Host
APP
Host
Channe
lChannel
APP
Host
8/25/06
UIUC - CS/ECE 438, Fall 2006
Host
24
Channel Implementation

Question

Where does the functionality belong?

Middle (switches)?


Edges (end hosts)?

8/25/06
Telephone system
Internet
UIUC - CS/ECE 438, Fall 2006
25
Inter-process Communication

Problems typically masked by
communication channel abstractions







Goal

8/25/06
Bit errors (electrical interference)
Packet errors (congestion)
Link/node failures
Message delays
Out-of-order delivery
Eavesdropping
Fill the gap between what applications expect
and what the underlying technology provides
UIUC - CS/ECE 438, Fall 2006
26
Performance
... and to do so while delivering “good” performance.
 Bandwidth/throughput




Data transmitted per unit time
Example: 10 Mbps
Link bandwidth vs. end-to-end bandwidth
Notation


8/25/06
KB = 210 bytes
Mbps = 106 bits per second
UIUC - CS/ECE 438, Fall 2006
27
Performance

Latency/delay




Time from A to B
Example: 30 msec (milliseconds)
Many applications depend on round-trip time (RTT)
Components




8/25/06
Transmission time
Propagation delay over links
Queueing delays
Software processing overheads
UIUC - CS/ECE 438, Fall 2006
28
Performance Notes

Speed of Light




Comments




No queueing delays in a direct link
Bandwidth is not relevant if size = 1bit
Software overhead can dominate when distance is small
Key Point


8/25/06
3.0 x 108 meters/second in a vacuum
2.3 x 108 meters/second in a cable
2.0 x 108 meters/second in a fiber
Latency dominates small transmissions
Bandwidth dominates large
UIUC - CS/ECE 438, Fall 2006
29
Delay x Bandwidth Product




channel = pipe
delay = length
bandwidth = area of a cross section
bandwidth x delay product = volume
Delay
Bandwidth
8/25/06
UIUC - CS/ECE 438, Fall 2006
30
Delay x Bandwidth Product

Example: Transcontinental Channel



BW = 45 Mbps
delay = 50ms
bandwidth x delay product
= (45 x 106 bits/sec) x (50 x 10–3 sec)
= 2.25 x 106 bits

Bandwidth x delay product


8/25/06
How many bits the sender must transmit before
the first bit arrives at the receiver if the sender
keeps the pipe full
Takes another one-way latency to receive a
response from the receiver
UIUC - CS/ECE 438, Fall 2006
31
Bandwidth vs. Latency
Relative importance


1-byte: Latency bound


25MB: Bandwidth bound

25MB
8/25/06
1ms vs 100ms latency dominates 1Mbps vs 100Mbps BW
1Mbps vs 100Mbps BW dominates 1ms vs 100ms latency
100 Mbps
1Mbps
1 Mbps
1Mbps
100ms
1ms
1b
UIUC - CS/ECE 438, Fall 2006
32
Bandwidth vs. Latency

Infinite bandwidth

RTT dominates



Its all relative

8/25/06
Throughput = TransferSize / TransferTime
TransferTime = RTT + 1/Bandwidth x
TransferSize
1-MB file to 1-Gbps link looks like a 1-KB
packet to 1-Mbps link
UIUC - CS/ECE 438, Fall 2006
33
Network Architecture

Challenge



Hardware and expectations are moving
targets.
How do network designers cope with
complexity?



8/25/06
Fill the gap between hardware capabilities and
application expectations, and to do so while
delivering “good” performance.
Layering
Protocols
Standards
UIUC - CS/ECE 438, Fall 2006
34
Abstraction through Layering

Abstract system into layers:

Decompose the problem of building a network into manageable
components


Each layer provides some functionality
Modular design provides flexibility


Modify layer independently
Allows alternative abstractions
Application programs
Message stream channel
Request/reply channel
Host-to-host connectivity
Hardware
8/25/06
UIUC - CS/ECE 438, Fall 2006
35
Protocols

Definition


A protocol is an abstract object that makes up
the layers of a network system
A protocol provides a communication service
that higher-layer objects use to exchange
messages

Service interface:


Peer interface:

8/25/06
To objects on the same computer that want to use its
communication services
To its counterpart on a different machine. peers
communicate using the services of lower-level protocols
UIUC - CS/ECE 438, Fall 2006
36
Interfaces
Host 1
Higherlevel
protocol
(TCP)
Lower-level
Protocol
(IP)
8/25/06
Host 2
Service interface
Peer-to-peer
interface
UIUC - CS/ECE 438, Fall 2006
Higherlevel
protocol
(TCP)
Lower-level
Protocol
(IP)
37
Terminology

Term “protocol” is overloaded


8/25/06
specification of peer-to-peer interface
module that implements this interface
UIUC - CS/ECE 438, Fall 2006
38
Layering Concepts

Encapsulation




Multiplexing and Demultiplexing

8/25/06
Higher layer protocols create messages and
send them via the lower layer protocols
These messages are treated as data by the
lower-level protocol
Higher-layer protocol adds its own control
information in the form of headers or trailers
Use protocol keys in the header to determine
correct upper-layer protocol
UIUC - CS/ECE 438, Fall 2006
39
Encapsulation
Application
program
Application
program
DATA
DATA
Request/
Reply
RRP HDR
Request/
Reply
DATA
RRP HDR
Host-to-Host
Host-to-Host
HHP HDR RRP HDR
8/25/06
DATA
UIUC - CS/ECE 438, Fall 2006
DATA
40
OSI Architecture

Open Systems Interconnect (OSI)
Architecture




8/25/06
International Standards Organization
(ISO)
International Telecommunications Union
(ITU, formerly CCITT)
“X dot” series: X.25, X.400, X.500
Primarily a reference model
UIUC - CS/ECE 438, Fall 2006
41
OSI Protocol Stack
Application

Application:
Presentation

Presentation: Format of exchanged data

Session:
Name space for connection mgmt

Transport:
Process-to-process channel
Network

Network:
Host-to-host packet delivery
Data Link

Data Link:
Framing of data bits

Physical:
Transmission of raw bits
Session
Transport
Physical
8/25/06
Application specific protocols
UIUC - CS/ECE 438, Fall 2006
42
OSI Protocol Stack
Host
UserLevel
Application
Application
Presentation
Presentation
Session
Session
Transport
Router
Transport
Host
Network
Network
Network
OS
Data Link
Data Link
Data Link
Physical
Physical
Physical
Kernel
8/25/06
UIUC - CS/ECE 438, Fall 2006
43
Internet Architecture

Internet Architecture (TCP/IP)


Developed with ARPANET and NSFNET
Internet Engineering Task Force (IETF)




Popular with release of Berkeley Software
Distribution (BSD) Unix; i.e., frees software
Standard suggestions debated publicly through
“requests for comments” (RFC’s)

8/25/06
Culture:
implement, then standardize
OSI culture: standardize, then implement
We reject kings, presidents, and voting. We believe in
rough consensus and running code. – David Clark
UIUC - CS/ECE 438, Fall 2006
44
Internet Architecture –
Hourglass Design
FTP
HTTP
DNS
TCP
VoIP
UDP
IP
Ethernet
8/25/06
FDDI
ATM
UIUC - CS/ECE 438, Fall 2006
Modem
45
Internet Architecture

Features:


No strict layering
Hourglass shape – IP is the focal point
Application
TCP
UDP
IP
Network
8/25/06
UIUC - CS/ECE 438, Fall 2006
46
Protocol Acronyms










8/25/06
(T)FTP HTTP DNS SMTP –
NTP TCP UDP IP FDDI ATM -
(Trivial) File Transfer Protocol
HyperText Transport Protocol
Domain Name Service
Simple Mail Transfer Protocol
Network Time Protocol
Transmission Control Protocol
User Datagram Protocol
Internet Protocol
Fiber Distributed Data Interface
Asynchronous Transfer Mode
UIUC - CS/ECE 438, Fall 2006
47
Summary

Goal


Steps



8/25/06
Understanding of computer network
functionality, with experience building and using
computer networks
Identify what concepts we expect from a network
Define a layered architecture
Implement network protocols and application
programs
UIUC - CS/ECE 438, Fall 2006
48
Assignments

Homework 1


Project 1


8/25/06
Due Wednesday September 6 at
2:00pm.
Due Friday September 8 at 9:00pm.
Both will be on website by end of
day today.
UIUC - CS/ECE 438, Fall 2006
49