Transcript Introduction - Aaron Striegel

CSE 30264
Computer Networks
Prof. Aaron Striegel
Department of Computer Science & Engineering
University of Notre Dame
Lecture 6 – January 28, 2010
Today’s Lecture
• Project 1
– Description / Overview
Application
• Physical Layer
Transport
– Shared Access
– Chapter 2.6-2.9
Network
Data
Physical
Spring 2010
CSE 30264
2
Project 1
• TCP Client / Server
–
–
–
–
Pre-built client for testing your server
Remote server for testing your client
Will have debug features to help you out
May use C or C++
• Premise
– Build a single-threaded TCP file client / server
– Client connects to a specific server IP / port requesting
a specific file
– Server responds with the length and binary data
Spring 2010
CSE 30264
3
Project 1
filefetch 129.74.153.157
9000 horns.mp3
C
S
connect
Length of file name
LF File Name
0x0009 horns.mp3
Length of binary data
Working in binary
0x00001001
LBD Binary Data
Binary Data
129.74.153.157, 9000
Spring 2010
CSE 30264
4
Project 1
• Important aspects
– Working with binary values
• Request file name length  16 bit value (0-65535)
– Response file name
• File length  32 bit value
• Will need to monitor speed / status
– Update with information as data comes in
– Will need to record time / data received
– TCP keeps it in order for us
Spring 2010
CSE 30264
5
Project 1
• Sanity checking
– Make sure that you use network byte order
– htons, htonl on the numbers
– Check to make sure that any numbers are believable
• Can write with multiple calls
– Write the size
– Write the file name
– TCP does the work for us figuring out how to split (or
combine) it for us
Spring 2010
CSE 30264
6
Project 1
• Fixed server
– Connect to 129.74.153.157, port 9000, TCP
• Example client
– Test your own server
• Connect to the same machine
– Open up two terminals or ssh sessions
– IP address = 127.0.0.1  localhost
• Anything in the 127.* range works
Spring 2010
CSE 30264
7
Project 1
• Two code directories
– Client
– Server
• Other notes
– Create a makefile
– Tutorial on web for how to create a makefile
• Stop by during office hours
• Two weeks
– Do not save it until the last minute
Spring 2010
CSE 30264
8
Port Sharing – Project 1
• Cannot share same port to listen to
• Pick a random big number
–
–
–
–
10,000 + X
16896 -> Striegel
Phone number, room number, etc.
When in doubt, check ps –A –f on the machine you log
in to
Spring 2010
CSE 30264
9
Shared Access Networks
Outline
Bus (Ethernet)
Token ring (IBM, FDDI, RPR)
Wireless (802.11, WiMAX)
Spring 2010
CS 30264
10
Shared Access Networks
• Challenges
– How do I let multiple devices share
the same communication medium?
• Control / logic
– When is it my turn?
– How long can I talk?
• Physical
–
–
–
–
Spring 2010
Capacitance, resistance, inductance
Signal propagation – latency
Signal vs. noise – SNR
Directionality – half vs. full duplex
CSE 30264
11
Ethernet Overview
• History
–
–
–
–
–
Developed by Xerox PARC in mid-1970s
Roots in Aloha packet-radio network
Standardized by Xerox, DEC, and Intel in 1978
Evolved into the 802.3 standard
Robert Metcalfe – embraced KISS
Metcalfe’s Law
Value of a network is
proportional to the square
of the number of users
Spring 2010
CS 30264
12
CSMA / CD
• CSMA/CD
– Carrier Sense
– Multiple Access
– Collision Detection
• Frame Format
64
48
48
16
Preamble
Dest
addr
Src
addr
Type
HDLC anyone?
Spring 2010
32
Body
CRC
CSMA / CD style networks
Max utilization* ~= 60%
CSE 30264
13
Ethernet (cont)
• Addresses
– Unique
• 48-bit unicast address assigned to each adapter
• Assigned in blocks to vendors
– Example:
• 8:0:e4:b1:2
– Broadcast: all 1s (multicast  first bit is a 1)
64
48
48
16
Preamble
Dest
addr
Src
addr
Type
Spring 2010
32
Body
CS 30264
CRC
Why is dest
address first?
14
Ethernet (cont)
• Variations
– Ethernet – 10 Mb/s
– Fast Ethernet – 100 Mb/s
• Usually what people call Ethernet now
– Gigabit Ethernet – 1000 Mb/s  1 Gb/s
• Gig E
– 10 Gigabit Ethernet
• 10 Gig
• Interconnection
– Bus  connected by hubs (old school)
– Star  connected by switches (everything today)
Spring 2010
CSE 30264
15
Variations
• How do they differ?
– Maximum cable length
• Less means faster
– Star only vs. bus
– Gap between packets
• IFS – Inter-Frame Spacing
• Less means faster
– Minimum / maximum packet size
• 64 / 1514 bytes (1500 byte payload)
• Jumbo frames (8192 bytes)
Spring 2010
CSE 30264
16
Ethernet
Spring 2009
CS 30264
Bridge
17
Transmit Algorithm
• If line is idle (CS)
– Send immediately
– Upper bound message size of 1500 bytes
– Must wait 9.6us between back-to-back frames
• IFS
• If line is busy…
– Wait until idle and transmit immediately
– Called 1-persistent (special case of p-persistent)
MAC – Media Access Control  Layer 2
Spring 2009
CS 30264
18
Algorithm (cont)
• If collision (CD)
– Jam for 32 bits, then stop transmitting frame
– Minimum frame is 64 bytes (header + 46 bytes of data)
– Delay and try again
• 1st time: 0 or 51.2us
• 2nd time: 0, 51.2, 102.4, or 153.6us
• nth time: k x 51.2us, for randomly selected k=0..2n - 1
• Give up after several tries (usually 16)
• Exponential backoff
Spring 2010
CS 30264
19
Collisions
A
B
A
B
A
B
A
B
(a)
(b)
(c)
(d)
Spring 2010
CS 30264
20
Token Ring Overview
• Examples
– IEEE 802.5 (based on earlier IBM Token Ring)
– Fiber Distributed Data Interface (FDDI)
– IEEE 802.17 (Resilient Packet Ring or RPR)
Spring 2009
CS 30264
21
Token Ring (cont)
• Idea
–
–
–
–
Frames flow in one direction: upstream to downstream
Special bit pattern (token) rotates around ring
Must capture token before transmitting
Release token after done transmitting
• Immediate release
• Delayed release
– Remove your frame when it comes back around
– Stations get round-robin service
• Frame Format
8
8
48
48
Start of
frame
Control
Dest
addr
Src
addr
Spring 2010
Body
CS 30264
32
8
24
CRC
End of
frame
Status
22
Timed Token Algorithm
• Token Holding Time (THT)
– Upper limit on how long a station can hold the token
• Token Rotation Time (TRT)
– How long it takes the token to traverse the ring
– TRT <= ActiveNodes x THT + RingLatency
Spring 2009
CS 30264
23
Token Maintenance
• Lost Token
– No token when initializing ring
– Bit error corrupts token pattern
– Node holding token crashes
• Monitoring for a Valid Token
– Should periodically see valid transmission (frame or
token)
– Timer: NumStations * THT + RingLatency
– Set timer and send claim frame if it fires
Spring 2009
CS 30264
24
FDDI
• Runs on fiber
• Consists of dual ring
Spring 2009
CS 30264
25
Resilient Packet Ring (802.17)
•
•
•
•
•
•
Focus on resiliency, bandwidth efficiency, QoS
2 counter-rotating optical fiber rings
Both rings used simultaneously (bandwidth)
Receiver removes RPR frame (bandwidth)
No tokens! Instead: buffer insertion
3 classes supported (QoS):
– class A: low latency, low jitter
– class B: predictable latency and jitter
– class C: best-effort
• Uses wrapping and steering (resiliency)
– wrapping: similar to FDDI
– steering: inform other nodes of failure, can use opposite direction
Spring 2009
CS 30264
26
Which one?
• Unclear
– Ethernet dominates in the LAN
• Local Area Network
– FDDI / SONET / etc.
• Dominate in the MAN
• Metro Area Network
– Why not Ethernet everywhere?
• Broadcast scope
Spring 2010
CSE 30264
27
Wireless
• Unique set of challenges vs. wired
– BER++
– Implicitly a broadcast
• Omni antenna
• Directed antenna
– Heavy environmental effects
• No real “shielding”
– Faraday cage
• Frequency up
– More power
– Inanimate objects bad
Spring 2010
CSE 30264
28
Wireless
• Bluetooth:
– 10m, 2.1Mbps (shared), peripheral devices to computer
• Wi-Fi 802.11:
– 100m, 54Mbps (shared), computer to base stations
• WiMAX 802.16:
– 10km, 70Mbps (shared), link buildings and towers
• 3G Cellular:
– Tens of km, 384+ Kbps (not shared), cell phone to
tower
Spring 2009
CS 30264
29
Modes of Communication
Ad hoc
Managed
Spring 2009
CS 30264
30
Bluetooth (802.15.1)
• 2.45GHz band, range of 10m
• Version 2.0: 2.1Mbps, low power consumption
• Piconet: master-slave
Spring 2009
CS 30264
31
Wi-Fi
•
•
•
•
•
IEEE 802.11: 2.4 GHz band, 1 Mb/s
IEEE 802.11b: 2.4GHz band, 11Mb/s
IEEE 802.11a: 5GHz band, 54Mb/s
IEEE 802.11g: 2.4GHz band, 54Mb/s
IEEE 802.11n: Dual band (2.4, 5), 270 Mb/s
Block Ack
MIMO
Spring 2010
CS 30264
32
Spread Spectrum
• Idea
– Spread signal over wider frequency band than required
– Originally designed to thwart jamming
• Frequency Hopping
– Transmit over random sequence of frequencies
– Sender and receiver share…
• Pseudorandom number generator
• Seed
– 802.11 uses 79 x 1MHz-wide frequency bands
Spring 2009
CS 30264
33
Spread Spectrum (cont)
• Direct Sequence
–
–
–
–
For each bit, send XOR of that bit and n random bits
Random sequence known to both sender and receiver
Called n-bit chipping code
802.11 defines an 11-bit chipping code
1
0
Data stream: 1010
1
0
Random sequence: 0100101101011001
1
0
Spring 2009
XOR of the tw o: 1011101110101001
CS 30264
34
Collisions Avoidance
• Similar to Ethernet
• Problem: hidden and exposed nodes
Spring 2009
CS 30264
35
MACA
•
•
•
•
Multiple Access with Collision Avoidance
Sender transmits RequestToSend (RTS) frame
Receiver replies with ClearToSend (CTS) frame
Neighbors…
– see CTS: keep quiet
– see RTS but not CTS: ok to transmit
• Receiver sends ACK when has frame
– neighbors silent until see ACK
• Collisions
– no collision detection
– known when CTS not received
– exponential backoff
Spring 2009
CS 30264
In general,
bad, bad, bad
36
Supporting Mobility
• Case 1: ad hoc networking
• Case 2: access points (AP)
– Tethered
– Each mobile node associates with an AP
Distribution system
AP-1
AP-3
F
AP-2
A
B
G
H
C
E
D
Spring 2009
CS 30264
37
Mobility (cont)
• Scanning (selecting an AP)
– Node sends Probe frame
– All AP’s w/in reach reply with ProbeResponse frame
– Node selects one AP; sends it AssociateRequest
frame
– AP replies with AssociationResponse frame
– New AP informs old AP via tethered network
• When
– Active: when join or move
– Passive: AP periodically sends Beacon frame
Spring 2009
CS 30264
38
802.11
• Up to 2312 bytes of data
• 32-bit CRC
• 4 addresses, usage depends on mode:
– Addr1 is target, Addr2 is source
– Addr1 is ultimate target, Addr2: immediate sender,
Addr3 is intermediate target, Addr4: original source
Spring 2009
CS 30264
39
WiMAX
•
•
•
•
•
•
•
Worldwide Interoperability for Microwave Access
Standardized by WiMAX Forum, IEEE 802.16
Typical distance: 1-6miles, up to 30miles
“subscriber stations” (e.g., antenna on roof)
Up to 70Mbps
Time Division Duplexing (TDD)
Frequency Division Duplexing (FDD)
Spring 2009
CS 30264
40
Cell Phone Technologies
•
•
•
•
Uses base stations, area served called “cell”
1G: analog
2G, 2.5G (e.g., GSM): digital
GPRS: General Packet Radio Service (typically
30-70Kbps)
• 3G:
– UMTS (Universal Mobile Telecommunications
System)
Spring 2009
CS 30264
41