Chapter 1 computer networks
Content
Computer Networks
COSC 78, Spring 2005 Tristan Henderson [email protected]
Purpose of this course
• Learn:
• • • • • •
what is a computer network? how do heterogeneous systems communicate? what services can a network provide? how does the Internet work? networked applications and services with a real production computer network (i.e., Dartmouth’s)
• Build: • Play:
Administravia
• Prof: [email protected]
•
255 sudi, but office hrs in 218 sudi (Wed 2-4pm, Fri 3-4pm)
• TA: [email protected] • Textbook: Kurose & Ross 3rd edition • Fill out the survey • Get a Sudikoff UNIX account • Class e-mail list: [email protected] • Schedule: http://www.cs.dartmouth.edu/~cs78
Assessment
• Homeworks (x4, 20%)
• • • • • • • •
Due at the beginning of class on due date Project 1 due April 29 (15%) Project 2 due May 27 (20%) Midterm May 4 (20%) Final June 3 (25%) NO RESCHEDULING OF EXAMS Extra exam/project questions Can use your own BSD/Linux machine, but you’re on your own
• Projects (x2) • Exams (x2)
• Grad students / extra credit: • Work on the Linux machines in 005 Sudikoff
Who am I?
• Research Assistant Professor of Computer Science
•
(i.e., a postdoc)
• M.A. (Cantab), M.Sc Ph.D (London) • Research interests: wireless networks, network •
measurements, networked games, network QoS First-time teacher; please give feedback!
The plan
• Week 1: high-level intro • Weeks 2-7: the basics • Weeks 8-10: extra topics • Things may not go to plan, so
• • •
monitor http://www.cs.dartmouth.edu/~cs78/schedule.html for updates I will follow the order and content of the book for ~75% of the course Slides draw heavily from the book (thanks to Jim Kurose & Keith Ross!)
• Chapter readings or handouts for most lectures
Introduction
• High-level intro to get “feel” and terminology
• • • • • • •
More detail as we progress through the course Use Internet as example What is the Internet? What is a protocol? Network edge, core, access nets, physical media Performance: loss, delay Protocol layers, service models
• Overview:
What is the Internet?
• “nuts and bolts” view • millions of connected • • • •
computing devices: hosts or end systems running network applications communication links • fibre, copper, radio, satellite • transmission rate = bandwidth routers forward packets (i.e., chunks of data) protocols control sending, receiving of messages • e.g., TCP, IP, HTTP, FTP
A quick note about the English
• We spell and pronounce things slightly differently...
routeing= route router =fiber route router fibre routing
Back to the Internet
•
The Internet is a “network of networks” • loosely hierarchical • compare the Internet to a private intrane! Protocols need to be agreed on by standards bodies • IETF, RFCs • IEEE network standards
•
What is the Internet?
• “Service” view • The Internet is a
•
communication in"astructure for enabling distributed applications • web, e-mail, games, p2p Apps are provided with a communication servic# • connection-oriented reliable • connectionless unreliable
What is a protocol?
• • Network protocols: • same idea, but machines instead of humans All communication activity in the Internet is governed by protocols
•
• •
Human protocols: • “Whaťs the time?” • “I have a question” • “I’d like you to meet...” Specific messages are sen! Specific actions are taken when messages are received, or on other events
Protocols define the format, order of messages sent and received among network entities, and the actions taken upon message transmission and receipt
What is a protocol?
Human protocol Network protocol
Network structure
• • •
Network edg# • applications and hosts Network cor# • routers • network of networks Access networks, physical media • communication links
Network edge
•
end systems (hosts) • run applications • e.g., web, blitzmail • sit at “edge of network” client/server model • client host requests, receives service from always-on server • e.g, web browser/server peer to peer model • minimal (or no) use of dedicated servers
•
•
Network edge: connection-oriented service
• Goal: data transfer between end systems • handshaking: setup data transfer ahead of time
• • • • • •
like “Hi”, “Hi” in human protocol sets up state in two communicating hosts The Internet connection-oriented service reliable, in-order byte stream data transfer • to cope with loss, acknowledgements and retransmissions flow control • sender doesn’t overwhelm receiver congestion control • senders slow down sending rate when network is congested
• TCP - Transmission Control Protocol (RFC 793)
Network edge: connectionless service
• Goal: data transfer between end systems • UDP - User Datagram Protocol (RFC 768)
• • • • • •
The Internet connectionless service unreliable data transfer no flow control no congestion control HTTP (web), FTP, telnet, SMTP (e-mail) streaming media, games, VoIP
• TCP applications: • UDP applications:
Network core
• •
A mesh of interconnected routers How is data transferred through the network? • circuit switching: dedicated circuit per call (telephone network) • packet switching: data set through network in discrete “chunks”
Network core: circuit-switching
•
Resources reserved end-to-end for “call” • link bandwidth, switch capacity • dedicated resources: no sharing • circuit-like (i.e., guaranteed) performance • call setup required
Network core: circuit-switching
•
•
Network resources are divided into “pieces” • pieces are allocated to calls • if a call doesn’t use a piece, it is idl# How to divide into pieces? • Frequency division • Time division
Circuit switching: FDM and TDM
Network core: packet-switching
• Each end-end data stream is divided into packets
• • • • • • •
user A, user B’s packets share network resources each packet uses the full link bandwidth resources are used as needed no dedicated allocation, no resource reservation aggregate demand can exceed supply (available resources) congestion: packets queue up and wait for link use store and forward: packets move one hop at a time • (node receives a complete packet before forwarding it)
• What about resource contention?
Packet-switching: statistical multiplexing
• •
Sequence of A & B’s packets does not have a fixed pattern statistical multiplexing Compare to TDM where each host gets same slot in revolving TDM frame
Packet switching is more efficient
• 1 Mb/s link
• • •
Each user: 100 kb/s when “active”; active 10% of time 10 users N = 35, p(> 10 simultaneous active) < 0.004
• Circuit-switching: • Packet-switching:
Packet versus circuit switching
• Is packet-switching always better? • Good for bursty data
• • • •
resource-sharing - link use allocated on demand simpler; no call setup Packet delay, loss Protocols needed for reliable data transfer, congestion control
• What if there is excessive congestion? • How to provide circuit-like behaviour?
• Some applications need guarantees; audio, video • A big research area - look up “Quality of Service” on CiteSeer • Virtual circuits: X.25, frame relay, ATM
Access networks and physical media
•
•
How to connect end systems to an edge router? • Residential access networks • Institutional access networks • Mobile access networks Access networks differ in amounts of available bandwidth (bits per second)
Residential access networks
• Point to point access to ISP • Modem, <=56Kbps • ADSL, <=1Mbps up, <=8Mbps down
• •
FDM: 50kHz-1MHz down, 4-50kHz up, 0-4kHz voice network of cable connects homes to ISP router • homes share access to router
• Cable: HFC, <=30Mbps down <=2Mbps up • Cable and ADSL are always-o)
Institutional access networks
• A company or university local area network (LAN) •
connects end systems to the edge router Ethernet
• •
shared or dedicated links connect end systems and router 10Mbps, 100Mbps, Gigabit Ethernet all common
Wireless access networks
• Shared wireless access network connects end systems to
edge router
• • • • • • •
using “base station” or “access point” 802.11a/b/g: 54/11/54 Mbps 3G UMTS ~384 kbps GSM/GPRS <150kbps (not so much in US) WiMAX/802.16 <48Mbps Bluetooth: <2.1Mbps WUSB: <480Mbps
• Wireless LANs: • Wide-area wireless access networks:
• Wireless PANs:
Physical media
• Bit: propagates between transmitter/receiver pairs • Physical link: what lies between transmitter & receiver
• • • • • • •
guided media: signals propagate in solid media: copper, fibre, coaxial cable unguided media: signals propagate freely: radio, satellite 2 insulated copper wires twisted together to reduce interference UTP (Unshielded Twisted Pair) Cat 3 = telephone, 10BaseT Ethernet Cat 5 = 100BaseT Cat 6 = Gigabit Ethernet
• Twisted pair
Physical media
• Coaxial cable
• • • • • • • •
2 concentric copper connectors bidirectional baseband (single channel) cable, legacy Ethernet broadband - multiple channel cable TV, HFC Glass fibre carrying light pulses; each pulse is one bit Very high speed point-to-point (e.g. 5Gbps) Low error rate repeaters can be spaced far apart Typically used for backbone networks, but changing (Sweden, Digital Dorm)
• Fibre optics
Physical media
• Radio
• • • • • • • •
Signal carried in electromagnetic spectrum No “wire” Bidirectional Environment affects propagation; reflection, obstruction, interference Microwave: <45Mbps LAN (e.g., 802.11): <54Mbps Wide-area: ~100s kbps Satellite: 50Mbps channels (but ~270ms delay)
• Radio link types
Admin
• Fill out survey
• • • • • •
survey is double-sided! today would be good, since Wayne is unlikely to do it at the weekends easiest way is to tell me your name and preferred username if you didn’t receive a test message today, then e-mail me ([email protected]) http://www.cs.dartmouth.edu/~cs78/ Wed 2-4pm, Fri 3-4pm, 218 Sudikoff
• Get a Sudikoff Unix account
• Make sure that you are on the cs78all@cs list • First homework set today, due next week • Office hours start this afternoon
Internet structure
• • •
Network of networks Roughly hierarchical Centre: “tier-1” ISPs (e.g., MCI, Sprint, AT&T, Pipex) • international/national coverage • no formal definition of tier-1 • tier-1 providers peer (interconnect) with a* other tier-1 ISPs, privately and at public NAPs • ISPs connect to other ISPs at POPs (Points of Presence)
A tier-1 ISP: Sprint
Internet structure
• Tier-2 ISPs: smaller (usually regional) ISPs
•
connect to one or more tier-1 ISPs
• Tier-3 ISPs are closest to end-systems (last hop)
Tier-2 ISP pays Tier-2 ISP tier-1 ISP for Tier-2 ISP connectivity to Tier 1 ISP rest of Internet NAP • tier-2 ISP is customer of tier-1 Tier 1 ISP Tier 1 ISP provider
Tier-2 ISP Tier-2 ISP
Tier-2 ISPs also peer privately with each other, interconnect at NAP
Tier-2 ISP
Internet structure
• a packet may pass through many networks
local ISP Tier 3 ISP Tier-2 ISP local ISP local ISP Tier-2 ISP local ISP
Tier 1 ISP
NAP
Tier 1 ISP
Tier-2 ISP local local ISP ISP
Tier 1 ISP
Tier-2 ISP local ISP
Tier-2 ISP local ISP
Network loss and delay
• How do loss and delay occur? • Packets queue in router buffers
• •
packet arrival rate to link exceeds the output capacity packets queue, wait for their turn
Four sources of delay
• 1. processing delay
• •
check bit errors determine output link
Four sources of delay
• 2. queueing delay
• •
time waiting at output link for transmission depends on congestion level of router
Four sources of delay
• 3. transmission delay
• •
store-and-forward: each packet needs to be received before it is forwarded R = link bandwidth (bps), L = packet length (bits) • time to send bits into link = L / R
Four sources of delay
• 4. propagation delay
• • •
d = length of physical link, s = propagation speed in medium (~2x108 m/s) propagation delay = d/s NB: s and R are very different!
Caravan analogy
10-car caravan toll booth 100 km toll booth 100 km
• Cars “propagate” at 100km/hr • Toll booth takes 12 seconds to service a car • car ~ bit; caravan ~ packet • Q: How long until caravan is lined up before 2nd to* booth?
•
•
time to “push” entire caravan through toll booth onto highway = 12*10 = 120 sec time for last car to propagate from 1st to 2nd toll booth = 100km/(100km/hr) = 1 hr
• A: 62 minutes
Caravan analogy
10-car caravan toll booth 100 km toll booth 100 km
• Cars now “propagate” at 1000 km/hr • Toll booth now takes 60 seconds to service a car • Q: Wi* cars arrive at 2nd booth before a* cars serviced a!
1st booth?
•
Yes. 1st car arrives at 2nd booth after 7 minutes, 3 cars still at 1st booth
• 1st bit of a packet can arrive at 2nd router before
packet is fully transmitted at 1st router !
Nodal delay
dnodal = dproc + dqueue + dtrans + dprop
• dproc = processing delay
• • • •
typically a few microseconds or less congestion-dependent L/R, significant for low-speed links ranges from a few ms (LAN, fiber) to hundreds of ms (satellite)
• dqueue = queueing delay • dtrans = transmission delay • dprop = propagation delay
Queueing delay / traffic intensity
• • • • • • •
R = link bandwidth (bps) L = packet length (bits) a = average packet arrival rate traffic intensity = La/R La/R ~ 0: average queueing delay small La/R ~ 1: delays become large La/R ~ 2: more “work” arriving than can be serviced average delay is infinite !
Packet loss
• Queue (buffer) preceding link in buffer has finite • •
capacity When a packet arrives to a full queue, the packet is dropped (lost) Lost packet may be:
• • •
retransmitted by previous node retransmitted by source end system not retransmitted at all
Protocol “layers”
• Networks are complex! • Many pieces
• • •
hosts, routers, links of different media, applications, protocols, hardware, software Is it possible to organise a network structure? Or at least can we organise this course?
• How to organise?
Organising air travel
ticket (purchase) baggage (check) gates (load) runway (takeoff) airplane routing airplane routing ticket (complain) baggage (claim) gates (unload) runway (landing) airplane routing
• A series of steps
Organising air travel by layers
ticket (purchase) baggage (check) gates (load) runway (takeoff) airplane routing departur# airpor! airplane routing intermediate air-traffic control centres ticket (purchase) baggage (check) gates (load) runway (landing) airplane routing arrival airpor! ticke! baggag" gat" takeoff/landing routing
• Layers: each layer implements a servic#
• •
via its own internal-layer actions relying on services provided by the layer below
Why layers?
• When dealing with complex systems: • explicit structure allows identification, relationship of
system pieces
• • •
layered reference model for discussion a change in implementation of a layer’s service is transparent to the rest of the system cross-layer optimisations
• modularisation eases maintenance, updating of system • but some consider layering harmful?
The Internet protocol stack
• application: supports network
applications
• •
FTP, HTTP, SMTP TCP, UDP
application transport network link physical
• transport: host-to-host transfer • network: routing of datagrams
from source to destination
•
IP, routing protocols
• link: data transfer between
neighbouring network elements
•
PPP, Ethernet
• physical: bits “on the wire”
The ISO OSI protocol stack
• presentation: translates
differences in encoding
7. application 6. presentation 5. 4. 3. 2. 1. session transport network data link physical
• •
encryption, endianness ‘conversations’ between apps
• session: manages connections • More than one way to layer a • •
stack Often hear references to “layer 2”, “layer 3” = OSI But Internet stack is more practical for developers
Encapsulation
messag# segmen! datagra"am#
application transport network link physical
link physical
switch
application transport network link physical
network link physical
router
COSC 78, Spring 2005 Tristan Henderson [email protected]
Purpose of this course
• Learn:
• • • • • •
what is a computer network? how do heterogeneous systems communicate? what services can a network provide? how does the Internet work? networked applications and services with a real production computer network (i.e., Dartmouth’s)
• Build: • Play:
Administravia
• Prof: [email protected]
•
255 sudi, but office hrs in 218 sudi (Wed 2-4pm, Fri 3-4pm)
• TA: [email protected] • Textbook: Kurose & Ross 3rd edition • Fill out the survey • Get a Sudikoff UNIX account • Class e-mail list: [email protected] • Schedule: http://www.cs.dartmouth.edu/~cs78
Assessment
• Homeworks (x4, 20%)
• • • • • • • •
Due at the beginning of class on due date Project 1 due April 29 (15%) Project 2 due May 27 (20%) Midterm May 4 (20%) Final June 3 (25%) NO RESCHEDULING OF EXAMS Extra exam/project questions Can use your own BSD/Linux machine, but you’re on your own
• Projects (x2) • Exams (x2)
• Grad students / extra credit: • Work on the Linux machines in 005 Sudikoff
Who am I?
• Research Assistant Professor of Computer Science
•
(i.e., a postdoc)
• M.A. (Cantab), M.Sc Ph.D (London) • Research interests: wireless networks, network •
measurements, networked games, network QoS First-time teacher; please give feedback!
The plan
• Week 1: high-level intro • Weeks 2-7: the basics • Weeks 8-10: extra topics • Things may not go to plan, so
• • •
monitor http://www.cs.dartmouth.edu/~cs78/schedule.html for updates I will follow the order and content of the book for ~75% of the course Slides draw heavily from the book (thanks to Jim Kurose & Keith Ross!)
• Chapter readings or handouts for most lectures
Introduction
• High-level intro to get “feel” and terminology
• • • • • • •
More detail as we progress through the course Use Internet as example What is the Internet? What is a protocol? Network edge, core, access nets, physical media Performance: loss, delay Protocol layers, service models
• Overview:
What is the Internet?
• “nuts and bolts” view • millions of connected • • • •
computing devices: hosts or end systems running network applications communication links • fibre, copper, radio, satellite • transmission rate = bandwidth routers forward packets (i.e., chunks of data) protocols control sending, receiving of messages • e.g., TCP, IP, HTTP, FTP
A quick note about the English
• We spell and pronounce things slightly differently...
routeing= route router =fiber route router fibre routing
Back to the Internet
•
The Internet is a “network of networks” • loosely hierarchical • compare the Internet to a private intrane! Protocols need to be agreed on by standards bodies • IETF, RFCs • IEEE network standards
•
What is the Internet?
• “Service” view • The Internet is a
•
communication in"astructure for enabling distributed applications • web, e-mail, games, p2p Apps are provided with a communication servic# • connection-oriented reliable • connectionless unreliable
What is a protocol?
• • Network protocols: • same idea, but machines instead of humans All communication activity in the Internet is governed by protocols
•
• •
Human protocols: • “Whaťs the time?” • “I have a question” • “I’d like you to meet...” Specific messages are sen! Specific actions are taken when messages are received, or on other events
Protocols define the format, order of messages sent and received among network entities, and the actions taken upon message transmission and receipt
What is a protocol?
Human protocol Network protocol
Network structure
• • •
Network edg# • applications and hosts Network cor# • routers • network of networks Access networks, physical media • communication links
Network edge
•
end systems (hosts) • run applications • e.g., web, blitzmail • sit at “edge of network” client/server model • client host requests, receives service from always-on server • e.g, web browser/server peer to peer model • minimal (or no) use of dedicated servers
•
•
Network edge: connection-oriented service
• Goal: data transfer between end systems • handshaking: setup data transfer ahead of time
• • • • • •
like “Hi”, “Hi” in human protocol sets up state in two communicating hosts The Internet connection-oriented service reliable, in-order byte stream data transfer • to cope with loss, acknowledgements and retransmissions flow control • sender doesn’t overwhelm receiver congestion control • senders slow down sending rate when network is congested
• TCP - Transmission Control Protocol (RFC 793)
Network edge: connectionless service
• Goal: data transfer between end systems • UDP - User Datagram Protocol (RFC 768)
• • • • • •
The Internet connectionless service unreliable data transfer no flow control no congestion control HTTP (web), FTP, telnet, SMTP (e-mail) streaming media, games, VoIP
• TCP applications: • UDP applications:
Network core
• •
A mesh of interconnected routers How is data transferred through the network? • circuit switching: dedicated circuit per call (telephone network) • packet switching: data set through network in discrete “chunks”
Network core: circuit-switching
•
Resources reserved end-to-end for “call” • link bandwidth, switch capacity • dedicated resources: no sharing • circuit-like (i.e., guaranteed) performance • call setup required
Network core: circuit-switching
•
•
Network resources are divided into “pieces” • pieces are allocated to calls • if a call doesn’t use a piece, it is idl# How to divide into pieces? • Frequency division • Time division
Circuit switching: FDM and TDM
Network core: packet-switching
• Each end-end data stream is divided into packets
• • • • • • •
user A, user B’s packets share network resources each packet uses the full link bandwidth resources are used as needed no dedicated allocation, no resource reservation aggregate demand can exceed supply (available resources) congestion: packets queue up and wait for link use store and forward: packets move one hop at a time • (node receives a complete packet before forwarding it)
• What about resource contention?
Packet-switching: statistical multiplexing
• •
Sequence of A & B’s packets does not have a fixed pattern statistical multiplexing Compare to TDM where each host gets same slot in revolving TDM frame
Packet switching is more efficient
• 1 Mb/s link
• • •
Each user: 100 kb/s when “active”; active 10% of time 10 users N = 35, p(> 10 simultaneous active) < 0.004
• Circuit-switching: • Packet-switching:
Packet versus circuit switching
• Is packet-switching always better? • Good for bursty data
• • • •
resource-sharing - link use allocated on demand simpler; no call setup Packet delay, loss Protocols needed for reliable data transfer, congestion control
• What if there is excessive congestion? • How to provide circuit-like behaviour?
• Some applications need guarantees; audio, video • A big research area - look up “Quality of Service” on CiteSeer • Virtual circuits: X.25, frame relay, ATM
Access networks and physical media
•
•
How to connect end systems to an edge router? • Residential access networks • Institutional access networks • Mobile access networks Access networks differ in amounts of available bandwidth (bits per second)
Residential access networks
• Point to point access to ISP • Modem, <=56Kbps • ADSL, <=1Mbps up, <=8Mbps down
• •
FDM: 50kHz-1MHz down, 4-50kHz up, 0-4kHz voice network of cable connects homes to ISP router • homes share access to router
• Cable: HFC, <=30Mbps down <=2Mbps up • Cable and ADSL are always-o)
Institutional access networks
• A company or university local area network (LAN) •
connects end systems to the edge router Ethernet
• •
shared or dedicated links connect end systems and router 10Mbps, 100Mbps, Gigabit Ethernet all common
Wireless access networks
• Shared wireless access network connects end systems to
edge router
• • • • • • •
using “base station” or “access point” 802.11a/b/g: 54/11/54 Mbps 3G UMTS ~384 kbps GSM/GPRS <150kbps (not so much in US) WiMAX/802.16 <48Mbps Bluetooth: <2.1Mbps WUSB: <480Mbps
• Wireless LANs: • Wide-area wireless access networks:
• Wireless PANs:
Physical media
• Bit: propagates between transmitter/receiver pairs • Physical link: what lies between transmitter & receiver
• • • • • • •
guided media: signals propagate in solid media: copper, fibre, coaxial cable unguided media: signals propagate freely: radio, satellite 2 insulated copper wires twisted together to reduce interference UTP (Unshielded Twisted Pair) Cat 3 = telephone, 10BaseT Ethernet Cat 5 = 100BaseT Cat 6 = Gigabit Ethernet
• Twisted pair
Physical media
• Coaxial cable
• • • • • • • •
2 concentric copper connectors bidirectional baseband (single channel) cable, legacy Ethernet broadband - multiple channel cable TV, HFC Glass fibre carrying light pulses; each pulse is one bit Very high speed point-to-point (e.g. 5Gbps) Low error rate repeaters can be spaced far apart Typically used for backbone networks, but changing (Sweden, Digital Dorm)
• Fibre optics
Physical media
• Radio
• • • • • • • •
Signal carried in electromagnetic spectrum No “wire” Bidirectional Environment affects propagation; reflection, obstruction, interference Microwave: <45Mbps LAN (e.g., 802.11): <54Mbps Wide-area: ~100s kbps Satellite: 50Mbps channels (but ~270ms delay)
• Radio link types
Admin
• Fill out survey
• • • • • •
survey is double-sided! today would be good, since Wayne is unlikely to do it at the weekends easiest way is to tell me your name and preferred username if you didn’t receive a test message today, then e-mail me ([email protected]) http://www.cs.dartmouth.edu/~cs78/ Wed 2-4pm, Fri 3-4pm, 218 Sudikoff
• Get a Sudikoff Unix account
• Make sure that you are on the cs78all@cs list • First homework set today, due next week • Office hours start this afternoon
Internet structure
• • •
Network of networks Roughly hierarchical Centre: “tier-1” ISPs (e.g., MCI, Sprint, AT&T, Pipex) • international/national coverage • no formal definition of tier-1 • tier-1 providers peer (interconnect) with a* other tier-1 ISPs, privately and at public NAPs • ISPs connect to other ISPs at POPs (Points of Presence)
A tier-1 ISP: Sprint
Internet structure
• Tier-2 ISPs: smaller (usually regional) ISPs
•
connect to one or more tier-1 ISPs
• Tier-3 ISPs are closest to end-systems (last hop)
Tier-2 ISP pays Tier-2 ISP tier-1 ISP for Tier-2 ISP connectivity to Tier 1 ISP rest of Internet NAP • tier-2 ISP is customer of tier-1 Tier 1 ISP Tier 1 ISP provider
Tier-2 ISP Tier-2 ISP
Tier-2 ISPs also peer privately with each other, interconnect at NAP
Tier-2 ISP
Internet structure
• a packet may pass through many networks
local ISP Tier 3 ISP Tier-2 ISP local ISP local ISP Tier-2 ISP local ISP
Tier 1 ISP
NAP
Tier 1 ISP
Tier-2 ISP local local ISP ISP
Tier 1 ISP
Tier-2 ISP local ISP
Tier-2 ISP local ISP
Network loss and delay
• How do loss and delay occur? • Packets queue in router buffers
• •
packet arrival rate to link exceeds the output capacity packets queue, wait for their turn
Four sources of delay
• 1. processing delay
• •
check bit errors determine output link
Four sources of delay
• 2. queueing delay
• •
time waiting at output link for transmission depends on congestion level of router
Four sources of delay
• 3. transmission delay
• •
store-and-forward: each packet needs to be received before it is forwarded R = link bandwidth (bps), L = packet length (bits) • time to send bits into link = L / R
Four sources of delay
• 4. propagation delay
• • •
d = length of physical link, s = propagation speed in medium (~2x108 m/s) propagation delay = d/s NB: s and R are very different!
Caravan analogy
10-car caravan toll booth 100 km toll booth 100 km
• Cars “propagate” at 100km/hr • Toll booth takes 12 seconds to service a car • car ~ bit; caravan ~ packet • Q: How long until caravan is lined up before 2nd to* booth?
•
•
time to “push” entire caravan through toll booth onto highway = 12*10 = 120 sec time for last car to propagate from 1st to 2nd toll booth = 100km/(100km/hr) = 1 hr
• A: 62 minutes
Caravan analogy
10-car caravan toll booth 100 km toll booth 100 km
• Cars now “propagate” at 1000 km/hr • Toll booth now takes 60 seconds to service a car • Q: Wi* cars arrive at 2nd booth before a* cars serviced a!
1st booth?
•
Yes. 1st car arrives at 2nd booth after 7 minutes, 3 cars still at 1st booth
• 1st bit of a packet can arrive at 2nd router before
packet is fully transmitted at 1st router !
Nodal delay
dnodal = dproc + dqueue + dtrans + dprop
• dproc = processing delay
• • • •
typically a few microseconds or less congestion-dependent L/R, significant for low-speed links ranges from a few ms (LAN, fiber) to hundreds of ms (satellite)
• dqueue = queueing delay • dtrans = transmission delay • dprop = propagation delay
Queueing delay / traffic intensity
• • • • • • •
R = link bandwidth (bps) L = packet length (bits) a = average packet arrival rate traffic intensity = La/R La/R ~ 0: average queueing delay small La/R ~ 1: delays become large La/R ~ 2: more “work” arriving than can be serviced average delay is infinite !
Packet loss
• Queue (buffer) preceding link in buffer has finite • •
capacity When a packet arrives to a full queue, the packet is dropped (lost) Lost packet may be:
• • •
retransmitted by previous node retransmitted by source end system not retransmitted at all
Protocol “layers”
• Networks are complex! • Many pieces
• • •
hosts, routers, links of different media, applications, protocols, hardware, software Is it possible to organise a network structure? Or at least can we organise this course?
• How to organise?
Organising air travel
ticket (purchase) baggage (check) gates (load) runway (takeoff) airplane routing airplane routing ticket (complain) baggage (claim) gates (unload) runway (landing) airplane routing
• A series of steps
Organising air travel by layers
ticket (purchase) baggage (check) gates (load) runway (takeoff) airplane routing departur# airpor! airplane routing intermediate air-traffic control centres ticket (purchase) baggage (check) gates (load) runway (landing) airplane routing arrival airpor! ticke! baggag" gat" takeoff/landing routing
• Layers: each layer implements a servic#
• •
via its own internal-layer actions relying on services provided by the layer below
Why layers?
• When dealing with complex systems: • explicit structure allows identification, relationship of
system pieces
• • •
layered reference model for discussion a change in implementation of a layer’s service is transparent to the rest of the system cross-layer optimisations
• modularisation eases maintenance, updating of system • but some consider layering harmful?
The Internet protocol stack
• application: supports network
applications
• •
FTP, HTTP, SMTP TCP, UDP
application transport network link physical
• transport: host-to-host transfer • network: routing of datagrams
from source to destination
•
IP, routing protocols
• link: data transfer between
neighbouring network elements
•
PPP, Ethernet
• physical: bits “on the wire”
The ISO OSI protocol stack
• presentation: translates
differences in encoding
7. application 6. presentation 5. 4. 3. 2. 1. session transport network data link physical
• •
encryption, endianness ‘conversations’ between apps
• session: manages connections • More than one way to layer a • •
stack Often hear references to “layer 2”, “layer 3” = OSI But Internet stack is more practical for developers
Encapsulation
messag# segmen! datagra"am#
application transport network link physical
link physical
switch
application transport network link physical
network link physical
router
