Transcript ppt

15-744: Computer Networking
L-2 Links
Links
•
•
•
•
How to make computers talk across a wire
How to share the wire
How to extend to multiple segments
Assigned reading
• [MB76] ETHERNET: Distributed Packet
Switching for Local Area Networks
• [B+88] Measured Capacity of an Ethernet:
Myths and Reality
© Srinivasan Seshan, 2001
L -2; 1-17-01
2
Outline
• Physical media is analog
• Modulation – signals to bits
• Bit stream vs. packets
• Framing – how to make packets
• Corruption
• Error detection & recovery
• Sharing
• Media access
© Srinivasan Seshan, 2001
L -2; 1-17-01
3
Modulation
• Non-Return to Zero (NRZ)
• Used by Synchronous Optical Network
(SONET)
• 1=high signal, 0=low signal
• Long sequence of same bit cause difficulty
• DC bias hard to detect – low and high detected by
difference from average voltage
• Clock recovery difficult
• SONET XOR’s bit sequence to ensure frequent
transitions
© Srinivasan Seshan, 2001
L -2; 1-17-01
4
Clock Recovery
• When to sample voltage?
• Synchronized sender and receiver clocks
• Need easily detectible event at both ends
• Signal transitions help resync sender and
receiver
• Need frequent transitions to prevent clock skew
© Srinivasan Seshan, 2001
L -2; 1-17-01
5
Modulation
• Non-Return to Zero Inverted (NRZI)
• 1=inversion of current value, 0=same value
• No problem with string of 1’s
• NRZ-like problem with string of 0’s
© Srinivasan Seshan, 2001
L -2; 1-17-01
6
Modulation
• Manchester
•
•
•
•
Used by Ethernet
0=low to high transition, 1=high to low transition
Transition for every bit simplifies clock recovery
Not very efficient
• Doubles the number of transitions
• Circuitry must run twice as fast
© Srinivasan Seshan, 2001
L -2; 1-17-01
7
Modulation
• 4b/5b
• Used by FDDI
• Uses 5bits to encode every 4bits
• Encoding ensures no more than 3 consecutive
0’s
• Uses NRZI to encode resulting sequence
• 16 data values, 3 “special” illegal values, 6
“extra” values, 7 illegal values
© Srinivasan Seshan, 2001
L -2; 1-17-01
8
Outline
• Physical media is analog
• Modulation – signals to bits
• Bit stream vs. packets
• Framing – how to make packets
• Corruption
• Error detection & recovery
• Sharing
• Media access
© Srinivasan Seshan, 2001
L -2; 1-17-01
9
Framing
• Length delimited
• Beginning of frame has length
• Single corrupt length can cause problems
• Must have start of frame character to resynchronize
• Resynchronization can fail if start of frame character
is inside packets as well
© Srinivasan Seshan, 2001
L -2; 1-17-01
10
Framing
• Byte stuffing
• Special start of frame byte (e.g. 0xFF)
• Special escape byte value (e.g. 0xFE)
• Values actually in text are replaced (e.g. 0xFF
by 0xFEFF and 0xFE by 0xFEFE)
• Worst case – can double the size of frame
• Bit stuffing
• Special bit sequence (0x01111110)
• 0 bit stuffed after any 11111 sequence
© Srinivasan Seshan, 2001
L -2; 1-17-01
11
Clock-Based Framing
• Used by SONET
• Fixed size frames (810 bytes)
• Look for start of frame marker that appears
every 810 bytes
• Will eventually sync up
© Srinivasan Seshan, 2001
L -2; 1-17-01
12
Consistent Overhead Byte Stuffing
• Run length encoding applied to byte stuffing
• Encoding
• Add implied 0 to end of frame
• Each 0 is replaced with (number of bytes to
next 0) + 1
• What if no 0 within 255 bytes? – 255 value
indicates 254 bytes followed by no zero
• Worst case – no 0’s in packet – 1/254 overhead
• Possible optimization to encode series of 0’s
© Srinivasan Seshan, 2001
L -2; 1-17-01
13
Outline
• Physical media is analog
• Modulation – signals to bits
• Bit stream vs. packets
• Framing – how to make packets
• Corruption
• Error detection & recovery
• Sharing
• Media access
© Srinivasan Seshan, 2001
L -2; 1-17-01
14
Error Detection - Checksum
• Used by TCP, UDP, IP, etc..
• Ones complement sum of all
words/shorts/bytes in packet
• Simple to implement
• Relatively weak detection
• Easily tricked by typical loss patterns
© Srinivasan Seshan, 2001
L -2; 1-17-01
15
Error Detection – CRC
• Polynomial code
• Treat packet bits a coefficients of n-bit
polynomial
• Choose r+1 bit generator polynomial (well
known – chosen in advance)
• Add r bits to packet such that message is
divisible by generator polynomial
• Better loss detection properties than
checksums
© Srinivasan Seshan, 2001
L -2; 1-17-01
16
Error Recovery
• Two forms of error recovery
• Forward Error Correction (FEC)
• Automatic Repeat Request (ARQ)
• FEC
• Use error correcting codes to repair losses
• ARQ
• Receiver sends acknowledgement (ACK) when
it receives packet
• Sender waits for ACK and timeouts if it does
not arrive within some time period
© Srinivasan Seshan, 2001
L -2; 1-17-01
17
Stop and Wait
© Srinivasan Seshan, 2001
Sender
Time
L -2; 1-17-01
Receiver
Timeout
• Simplest ARQ
protocol
• Send a packet,
stop and wait until
acknowledgement
arrives
18
ACK lost
© Srinivasan Seshan, 2001
Timeout
Timeout
Timeout
Timeout
Timeout
Time
Timeout
Recovering from Error
Packet lost
L -2; 1-17-01
Early timeout
19
Problems with Stop and Wait
• How to recognize a duplicate
• Performance
• Can only send one packet per round trip
© Srinivasan Seshan, 2001
L -2; 1-17-01
20
How to Recognize Resends?
• Use sequence numbers
• both packets and acks
• Sequence # in packet is
finite -- how big should it
be?
• For stop and wait?
• One bit – won’t send seq
#1 until received ACK for
seq #0
© Srinivasan Seshan, 2001
L -2; 1-17-01
21
How to Keep the Pipe Full?
• Send multiple packets without
waiting for first to be acked
• Number of pkts in flight = window
• How large a window is needed
• Round trip delay * bandwidth =
capacity of pipe
• Reliable, unordered delivery
• Several parallel stop & waits
• Send new packet after each ack
• Sender keeps list of unack’ed
packets; resends after timeout
• Receiver same as stop&wait
© Srinivasan Seshan, 2001
L -2; 1-17-01
22
Sliding Window
• Reliable, ordered delivery
• Receiver has to hold onto a packet until all
prior packets have arrived
• Sender must prevent buffer overflow at
receiver
• Circular buffer at sender and receiver
• Packets in transit <= buffer size
• Advance when sender and receiver agree
packets at beginning have been received
© Srinivasan Seshan, 2001
L -2; 1-17-01
23
Sender/Receiver State
Sender
Max ACK received
Receiver
Next expected
Next seqnum
…
…
…
…
Sender window
Sent & Acked
Sent Not Acked
OK to Send
Not Usable
© Srinivasan Seshan, 2001
Max acceptable
Receiver window
Received & Acked
Acceptable Packet
Not Usable
L -2; 1-17-01
24
Window Sliding – Common Case
• On reception of new ACK (i.e. ACK for
something that was not acked earlier
• Increase sequence of max ACK received
• Send next packet
• On reception of new in-order data packet
(next expected)
• Hand packet to application
• Send cumulative ACK – acknowledges
reception of all packets up to sequence number
• Increase sequence of max acceptable packet
© Srinivasan Seshan, 2001
L -2; 1-17-01
25
Loss Recovery
• On reception of out-of-order packet
• Send nothing (wait for source to timeout)
• Cumulative ACK (helps source identify loss)
• Timeout (Go Back N recovery)
• Set timer upon transmission of packet
• Retransmit max ACK received sequence + 1
• Restart from max ACK received sequence + 1
• Performance during loss recovery
• No longer have an entire window in transit
• Can have much more clever loss recovery
• Covered in TCP lectures
© Srinivasan Seshan, 2001
L -2; 1-17-01
26
Sequence Numbers
• How large do sequence numbers need to
be?
• Must be able to detect wrap-around
• Depends on sender/receiver window size
• E.g.
• Max seq = 7, send win=recv win=7
• If pkts 0..6 are sent succesfully and all acks lost
• Receiver expects 7,0..5, sender retransmits old 0..6
• Max sequence must be >= send window +
recv window
© Srinivasan Seshan, 2001
L -2; 1-17-01
27
Outline
• Physical media is analog
• Modulation – signals to bits
• Bit stream vs. packets
• Framing – how to make packets
• Corruption
• Error detection & recovery
• Sharing
• Media access
© Srinivasan Seshan, 2001
L -2; 1-17-01
28
Broadcast Network Arbitration
• Like sharing a single cpu must share a link
• Give everyone a fixed time/freq slot?
• Ok for fixed bandwidth (e.g., voice)
• What if traffic is bursty?
• Centralized arbiter
• Ex: cell phone base station
• Single point of failure
• Distributed arbitration
• Aloha/Ethernet
© Srinivasan Seshan, 2001
L -2; 1-17-01
29
Multiplexing/Media Access/Sharing
• FDMA
• Different freq
• CDMA (covered in wireless lecture)
• Different codes
• Direct sequence
• Frequency hopping
• TDMA
• Different times
• Synchronous TDMA
• CSMA, etc
© Srinivasan Seshan, 2001
L -2; 1-17-01
30
Ethernet
• First practical local area network, built at
Xerox PARC in 70’s
• Carrier sense
• Check to see if active transmission
• Collision detect
• Sender checks for collision; wait and retry
• Adaptive randomized wait to avoid
collisions
© Srinivasan Seshan, 2001
L -2; 1-17-01
31
Ethernet MAC Protocol
Packet?
No
Sense
Carrier
Send
Detect
Collision
Yes
Discard
Packet
attempts < 16
b=CalcBackoff();
wait(b);
attempts++;
attempts == 16
© Srinivasan Seshan, 2001
L -2; 1-17-01
32
Ethernet Backoff Calculation
• If deterministic delay after collision, collision
will occur again in lockstep
• If random delay with fixed mean
• Few senders  needless waiting
• Too many senders  too many collisions
• Exponentially increasing random delay
• Infer senders from # of collisions
• More senders  increase wait time
© Srinivasan Seshan, 2001
L -2; 1-17-01
33
Minimum Packet Size
• What if two people
sent really small
packets
• How do you find
collision?
• None in paper – but
is one in reality
© Srinivasan Seshan, 2001
L -2; 1-17-01
34
Ethernet Collision Detect
• Min packet length > 2x max prop delay
• If A, B are at opposite sides of link, and B starts
one link prop delay after A
• Jam network for 32-48 bits after collision,
then stop sending
• Ensures that everyone notices collision
© Srinivasan Seshan, 2001
L -2; 1-17-01
35
End to End Delay
• 1Km, c in cable = 60% * c in vacuum = 1.8
x 10^8 m/s
• 1000/1.8 x 10^8 ~= 5 x 10^-6 = 5us
• 5us * 3Mbps = 15bits in flight!
• Modern 10Mb Ethernet {
•
•
•
•
2.5km, 10Mbps
~= 12.5us delay
+introduced repeaters (max 5 segments)
worst case – 51.2us round trip time!
© Srinivasan Seshan, 2001
L -2; 1-17-01
36
Minimum Packet Size
• Slot time = 51.2us = 512bits in flight
• After this amount, sender is guaranteed sole access to
link
• 51.2us = slot time for backoff
• What about scaling? 100Mbit, 1Gbit...
• Make network smaller?
• Solution for 100BaseT
• Make min pkt size larger?
• 512bits @ 1Gbps = 512ns
• 512ns * 1.8 * 10^8 = 92meters
• Gigabit ethernet uses collision extension for small pkts
© Srinivasan Seshan, 2001
L -2; 1-17-01
37
Ethernet Packet Format
Preamble
Dst. Addr.
Src. Addr. Type
Data
CRC
• Preamble – 8 byte
• 101010…1011
• Src/Dst Address – 6 bytes
• Globally unique
• Allocated to manufacturers
• Type – 2 bytes
• Data – 46 to 1500 bytes
• CRC – 4 bytes
© Srinivasan Seshan, 2001
L -2; 1-17-01
38
Interaction with Layering
• TYPE field
• Identifies upper layer protocol
• Enables the multiplexing of protocols
• ARP
• Broadcast search for IP address
• Destination responds with appropriate 48-bit
Ethernet address
© Srinivasan Seshan, 2001
L -2; 1-17-01
39
Simple Analysis of Efficiency
• If pkt size/link speed = P/C = slot time = T
•
•
•
•
Minimum packet size
E = 1/(1+W) = 1/ (1 + (1-A)/A) = A
A = (1-(1/Q))^(Q-1)
If Q >>1 the E = A = 1/e = well known Ethernet limit
• Assumptions
•
•
•
•
Single pkt size
Always have pkt to send
Master slot clock, all transmissions start a slot start
Q is estimated well by exponential backoff
© Srinivasan Seshan, 2001
L -2; 1-17-01
40
Ethernet Problems
• Ethernet unstable at high loads
• Peak utilization = 1/e = 37%
• Peak throughput worse with
• More hosts – more collisions needed to identify
single sender
• Smaller packet sizes – more frequent
arbitration
• Longer links – collisions take longer to observe,
more wasted bandwidth
© Srinivasan Seshan, 2001
L -2; 1-17-01
41
Source of Myths
• Assumptions in various analyses
• Static parameters
• Maximum propagation time and slot time
• Maximum packet size
• 1-persistence
• Workload parameters
•
•
•
•
Packet length distribution
Number of hosts
Length of cable and placement of hosts
Load
• Evaluated under unreasonable high load
© Srinivasan Seshan, 2001
L -2; 1-17-01
42
Measurement of Real Ethernet
• Evaluate performance in some typical scenarios
• Scenario 1
• Topology: 4 clusters of 6 hosts – similar to office
configuration
• Fixed pkt size
• Throughput decreases with number of hosts &
increases with pkt size – as expected
• Fairness improves with number of hosts – capture
effects less likely
• Only linear increase in delay with number of hosts unexpected
© Srinivasan Seshan, 2001
L -2; 1-17-01
43
Measurement of Real Ethernet
• Scenario 2
• Topology: 23 hosts on short net
• Load: fixed pkt size
• Improvement in bit rate over scenario 1
• Scenario 3
• Topology: 4 clusters
• Load: bimodal pkt size
• 7/1 ratio of small to large pkts is sufficient to
greatly improve total bit rate
© Srinivasan Seshan, 2001
L -2; 1-17-01
44
How to Improve Performance
•
•
•
•
No long cables
Fewer hosts per cable
Use large packets
Don't mix real-time w/ bulk-data if possible
• Can’t provide good efficiency/throughput and
good latency
© Srinivasan Seshan, 2001
L -2; 1-17-01
45
Ethernet Packet Traces
• Ethernet traffic is “self-similar” (fractal)
• Bursty at every time scale (msecs to months)
• Implication?
• On average, low load
• Occasional peaks
© Srinivasan Seshan, 2001
L -2; 1-17-01
46
Token Rings
• Packets broadcast around ring
• Token “right to send” rotates around ring
• Fair, real-time bandwidth allocation
• Every host holds token for limited time
• Higher latency when only one sender
• Higher bandwidth
• Point to point links electrically simpler than bus
© Srinivasan Seshan, 2001
L -2; 1-17-01
47
Why Did Ethernet Win?
• Failure modes
• Token rings – network unusable
• Ethernet – node detached
• Good performance in common case
• Volume  lower cost  higher volume ….
• Adaptable
• To higher bandwidths (vs. FDDI)
• To switching (vs. ATM)
• Completely distributed, easy to
maintain/administer
• Easy incremental deployment
• Cheap cabling, etc
© Srinivasan Seshan, 2001
L -2; 1-17-01
48
LAN Switching
• Extend reach of a single shared medium
• Connect two or more “segments” by
copying data frames between them
LAN 1
© Srinivasan Seshan, 2001
LAN 2
L -2; 1-17-01
49
Switched Network Advantages
• Higher link bandwidth
• Point to point electrically simpler than bus
• Much greater aggregate bandwidth
• Separate segments can send at once
• Improved fault tolerance
• Redundant paths
• Challenge
• Learning which packets to copy across links
• Avoiding forwarding loops
© Srinivasan Seshan, 2001
L -2; 1-17-01
50
Learning Bridges
• Basic idea: build cache of which nodes are
downstream of which ports
• Monitor source address on all packets
bridge forwards
• Insert reverse path to source into cache
• What to do with unknown sources?
• Flood network
© Srinivasan Seshan, 2001
L -2; 1-17-01
51
Bridges with Loops
S
LAN 1
Packet from S on LAN 1
S D Type Data
Cache at B1
Node Port
S
11
Port 11
Cache at B2
Port 21
B1
B2
Port 12
Port 22
Node Port
S
21
LAN 2
© Srinivasan Seshan, 2001
L -2; 1-17-01
52
Loop Solution: Spanning Tree
• Only want a single spanning tree
• First step agree on a root
• Lowest node ID
• Each bridge announces its current root and
distance to root
• Lowest distance become responsible for
link
• Ties go to lower bridge ID
© Srinivasan Seshan, 2001
L -2; 1-17-01
53
Next Lecture: Layer Functionality
• How to determine split of functionality
• Across protocol layers
• Across network nodes
• Assigned Reading
• [SRC84] End-to-end Arguments in System
Design
• [Cla88] Design Philosophy of the DARPA
Internet Protocols
• [CT90] Architectural Consideration for a New
Generation of Protocols
© Srinivasan Seshan, 2001
L -2; 1-17-01
54