|
Birth of Ethernet May 22, 1973: Ethernet memo
|
tarix | 17.10.2017 | ölçüsü | 445 b. | | #5477 |
|
May 22, 1973: Ethernet memo - Bob Metcalfe (Xerox Palo Alto Research Center)
- Carrier Sense Multiple Access with Collision Detection and expo backoff
- 3 mbps speed
On the birth of Ethernet [quoting from Ethernet – The definitive guide”]: In late 1972, Metcalfe and his Xerox PARC colleagues developed the first experimental Ethernet system to interconnect the Xerox Alto, a personal workstation with a graphical user interface. The experimental Ethernet was used to link Altos to one another, and to servers and laser printers. The signal clock for the experimental Ethernet interface was derived from the Alto's system clock, which resulted in a data transmission rate on the experimental Ethernet of 2.94 Mbps. Metcalfe's first experimental network was called the Alto Aloha Network. In 1973 Metcalfe changed the name to "Ethernet," to make it clear that the system could support any computer--not just Altos--and to point out that his new network mechanisms had evolved well beyond the Aloha system. He chose to base the name on the word "ether" as a way of describing an essential feature of the system: the physical medium (i.e., a cable) carries bits to all stations, much the same way that the old "luminiferous ether" was once thought to propagate electromagnetic waves through space. Thus, Ethernet was born.
Ethernet Standardization: from DIX to 802.3 1980: DIX Ethernet Standard - DIX = Digital-Intel-Xerox vendor consortium
- Interoperable products from the three founding companies
1982: Xerox relinquish “Ethernet” trademark 1985: IEEE 802.3 - Ethernet becomes an IEEE 802 standard
- Minor modifications vs DIX standard
- Path towards worldwide interoperability
- Speed: 10 mbps
- Medium:
- Thick coaxial, 500 mt max cable (10BASE5)
- Thin coaxial, 185mt max cable (10BASE2)
- Network extension via repeaters (up to a max limit)
A note on Ethernet terminology Speed Signal method - Base, Broad
- Broad = RF modulated on coax
- only one case: 10BROAD36, now obsolete
Medium - Old notation: 2,5 = 200/500 mt (thin/thick coax)
- More recent notation: T, Tx, T4, T2, FX, X, CX, SX, LX
- Depends on which specific twisted pair category & fibre category;
- Different labels (e.g. T, TX, T4, T2) account for different encoding details
Multiple Access shared transmission medium Multiple Access shared transmission medium - thick / thin coaxial cable
Ethernet transceiver (10base-5)
Ethernet transceiver (10Base-2)
Breakthrough idea (1990)
Ethernet RJ45 connector
Pair 3 used for transmission Pair 2 used for reception Pairs 1 & 4 unused - In 10Base-T & 100Base-T(x) Ethernet
- Used in 1000Base-T
Straight & crossover RJ45 meant to connect PC to Hub What About PC to PC or Hub to Hub connection?
Ethernet Frame Preamble: - For bit-level and frame-level synchronization
Destination address: - Who’s this frame for (who is the intended receiver)
- Hardware address (48 bits address of the network interface card)
Source address: - Who’s this frame from (who is the transmitter)
- Hardware address (48 bits address of the network interface card)
Type: - Which type of information is carried by the frame (which upper layer protocol)
Frame Check Sequence - Verifies if the frame has been received properly (not corrupted)
Transmission of bits Idea: - send data + clock in the same signal!
10 mbps Manchester encoding
Preamble (10 mbps) 8 bytes - 7 bytes preamble
- 7 x (10101010) square wave @ 5 MHz
- for clock recovery
- Last byte: SFD (Start Frame Delimiter)
- 1 x (10101011)
- signals the start of the frame
48 bit addresses Typically referred to as - Interface address
- Hardware address
- MAC address
First bit: - 0 = physical address of an interface
- 1 = group address
Second bit: - 0 = globally administered address
- Assigned by the manifacturer
- 1 = locally administered address
- Can be configured through driver
Examples
Multiple Access: Ethernet vs Aloha Aloha: - Transmit without listening
- Regardless of channel activity
- Transmit all the frame
Ethernet vs Aloha: listen before tx
Carrier Sense Multiple Access
Carrier Sense Multiple Access 2. If channel detected busy: defer
Collision Detection
Why collisions occur?
When a frame is “too short”…
Network diameter Essential condition: - a station MUST be able to detect a collision
Shortest possible frame: - 6+6+2+46+4 = 64 bytes = = 512 bits (excl preamble)
Condition on network diameter: - a collision MUST be detected on shortest possible frame
- Bound on maximum RTT
Network diameter in practice Max RTT lower than 51,2 s - 802.3 standard max RTT = 46,38 s
Max link length - Thick coax up to 500 mt
- Fiber link betw. repeaters up to 2 km
- Transceiver cable up to 50 mt
Topological limits - 5-4-3 rule: between any two nodes on the network, there can only be
- a maximum of five segments
- connected through four repeaters
- only three of the five segments may contain user connections.
Repeaters add delay! - Must account for repeater delays
- Min_TX_time > 2 x d/200 + N x Repeater_delay
The need for random backoff Retransmission after collision must occur at different instant of times - Otherwise collision will repeat forever
Deterministic rule? - Hard, for a fully distributed mechanism
Idea: generate a random time after a collision - Different stations will extract (sooner or later) different backoff times
Rationale for backoff “slots”
Backoff slot-time Set to 512 bits guarantees that - A station transmitting at the beginning of the previous backoff slot will be ALWAYS detected;
- A station transmitting for more than 512 bytes will acquire for sure the channel
- No “late collision” possible
- If they occur misconfiguration or hardware failures
Ethernet Backoff rule: extract a DISCRETE value B, and schedule transmission at time B x 51,2 us
Ethernet (truncated) Exponential backoff rules Once a frame collides: - End transmission with Jam signal
- Let N be the retry index
- N=0 for a new frame; N=1 for first rtx; N=2 for second rtx, etc
- Abort transmission after N=16 unsuccessful retries
- Let K=min(10,N)
- Extract a random integer number R in the range:
- 0 ≤ R < 2K
- Example: if K=6, extract R in (0, 31)
- Max range: when K=10 R in (0, 1023)
- Schedule retransmission at time:
- Backoff = R x 51,2 us (10 mbps case)
- Where 51,2 us = tx time of 512 bits @ 10 Mbps
- 100 Mbps Ethernet: slot-time = 5,12 us
- Retransmit at given time only if channel idle (otherwise defer until channel becomes idle for an IFS)
Ethernet Repeaters Physical layer device 3R functions - Re-Shaping
- Restores the proper signal waveform
- Re-Timing
- Restores the proper impulse duration (clock recovery)
- Re-Transmitting
- Retransmits signal on “other” port
- Regardless of who’s the signal intended for
Repeaters & collisions Retransmits collisions, too - Actually, regenerates (extending them to 96 bits) 010101… jam sequences
- And generates collisions when signal is received simultaneously on both ends
Multi-port repeater (hub) Signal regenerated & retransmitted on all repeater ports except the port from which the signal has arrived
Multiport repeaters star topology Coax & transceivers no more necessary! 1990: emergence of 10Base-T technology
Hub-based star topologies: Why collision detection? How collision is detected?
Ethernet bridge Data-link layer device Signal retransmission takes into account destination address
Multiport bridge Switch HUB - broadcasts signal on all links
- Logically behaves as a bus
- Only one tx at a time
SWITCH - Repeats signal on specifically addressed link
- Bridging function
- Many tx-rx pairs at a time
Switches & collisions A sends frame to C; D sends frame to E No collision - Simultaneous transmission occurs
Broadcast domain vs collision domain
Full-duplexing Switched star network: only possible collision is on a same link - When both station and switch simultaneously start transmission
But rx and tx are carried out on different pairs collision is fictitious - detected by the network interface card (activity sensed on Rx pair while NIC is transmitting)
- But it is not a real collision between the signals!
- it would be with a central hub; it is not with central switch
1997: full duplex standard (802.3x) - Simultaneously transmit and receive (2x speed increase)
- In a switched star network collision is no more possible!!
- CSMA/CD no more necessary
- Network diameter no more a concern
- Arbitrary increase of the link speed is now possible!
1998-1999: Gigabit Ethernet 2002 (july): 10 GigaEthernet Ethernet in the metropolitan area (e.g. Fastweb, Telecom IT) Future: 40 Giga-Ethernet, 160 Giga-Ethernet
Buffering
buffering
buffering
buffering
buffering
Buffers Solve output port contention - 1 packet transmitted
- Other stored in waiting line
May have finite capacity - Max number of stored bytes or packets
- Introduce loss!!
- Packet arriving when buffer full gets lost
Introduce latency!! - Latency is NOT deterministic, but statistical
Bridge/Switch operation Store & Forward: - read frame (memorize into onboard buffer)
- Check CRC
- Discard frame if
- CRC fails
- too short (<64 bytes, “runt”)
- too long (>1518 bytes, “giant”)
- Look up destination into forwarding (switching) table
- Forward packet to outgoing port
Cut-through - Just read first few bytes (until destination address)
- Don’t do any check
- Look up forwarding table and select destination
- forward frame while receiving it
Store & forward vs cut-through latency 1518 bytes frame - Assume full 8 bytes preamble received
- S&F @ 10 mbps ≥ 1526*8/10 s = 1222 s
- C-T @ 10 mbps ≥ 14*8/10 s = 11.2 s
- S&F @ 100 mbps ≥ 122 s
- C-T @ 100 mbps ≥ 1.1 s
- Not a real problem at high rate
S&F vs CT: Fragment-free mode Compromise between cut-through and store-and-forward - Reads first 64 bytes
- includes the frame (+LLC) header
- Then starts send packet
- before the entire data field is read and the FCS is checked.
Advantages: - Verify reliability of header information (addresses, frame type, LLC header information)
- Detects & discards runts & collisions
Cut-through possible only if source and destination ports have same bit rate Different rates buffering necessary S&F only Asymmetric switching typical in client/server environments - More bandwidth dedicated to the server port to prevent a bottleneck
Forwarding database Mapping between MAC addresses and ports Static entries: - Configured by sysadmin
- Permanent database
Dinamic entries: - “Learned”
- Expire after ageing process reaches upper value
- E.g. 300 seconds
- configurable
Address Learning /1 Frame arrives at port X - Hence it has come from LAN attached to port X
Address Learning /2 Incoming frame whose SRCaddr not in forwarding DB: - Create new entry
- Ageing-time=0
Address Learning /3
Frame forwarding Very first operation performed by the bridge/switch upon frame reception
Example / 1 start-up Initial state: forwarding DB = empty
Example / 2 STA 1 STA 2 STA 1 transmits frame to STA 2 Flooding occurs (STA2 not registered in DB) Bridge learns STA1=P1
Example / 3 STA 2 STA 1 STA 2 may respond - depends on involved protocol/app rules (e.g. TCP handshake)
transmits frame to STA 1 Destination selected Bridge learns STA2=P3
Example / 4 STA 3 STA 1 STA 3 on LAN 1 transmits to STA 1 Frame arrives to STA1 on LAN 1 - But arrives also to Bridge
Bridge discards frame (STA1 on same port of incoming frame) - This operation is referred to as FILTERING FUNCTION
Bridge learns STA3=P1
Example / 5 STA 1 moves; STA 1 STA 3 STA 1 moves on LAN 2 Then transmits to STA 3 Frame arrives to Bridge on P2, and forwarded to P1 - According to forwarding DB information
Bridge learns that STA 1 moved - Deletes previous entry with P1
- Adds new entry with P2
Example / 6 STA 2 moves; STA 1 STA 2 STA 2 moves on LAN 1 STA 1 transmit frame to STA 2 Frame forwarded on old port P3!! - Bridge will learn only when STA2 will transmit first frame
- OR when ageing time will expire
- and STA2 P3 entry will be removed from forwarding DB
Why a station should move? Fault-tolerant architectures!
WLAN history Original goal: - Deploy “wireless Ethernet”
- First generation proprietary solutions (end ’80, begin ’90):
- WaveLAN (AT&T)
- HomeRF (Proxim)
- Abandoned by major chip makers (e.g. Intel: dismissed HomeRF in april 2001)
IEEE 802.11 Committee formed in 1990 - Charter: specification of MAC and PHY for WLAN
- First standard: june 1997
- Reference standard: september 1999
- Multiple Physical Layers
- Two operative Industrial, Scientific & Medical (ISM) shared unlicensed band
- 2.4 GHz: Legacy; 802.11b/g
- 5 GHz: 802.11a
1999: Wireless Ethernet Compatibility Alliance (WECA) certification - Later on named Wi-Fi
- Boosted 802.11 deployment!!
WLAN data rates Legacy 802.11 - Work started in 1990; standardized in 1997
- 1 mbps & 2 mbps
The 1999 revolution: PHY layer impressive achievements - 802.11a: PHY for 5 GHz
- published in 1999
- Products available since early 2002
- 802.11b: higher rate PHY for 2.4 GHz
- Published in 1999
- Products available since 1999
- Interoperability tested (wifi)
2003: extend 802.11b - 802.11g: OFDM for 2.4 GHz
- Published in june 2003
- Products available, though no extensive interoperability testing yet
- Backward compatibility with 802.11b Wi-Fi
Ongoing standardization effort: 802.11n - Launched in september 2003
- Minimum goal: 108 Mbps (but higher numbers considered)
Why multiple rates? “Adaptive” (?) coding/modulation
Wireless Medium Unreliability
Must rely on explicit ACKs Successful DATA transmission: - ONLY IF an ACK is received
ACK transmission provided by MAC layer - Immediate retransmission
- Don’t get confused with higher layer rtx
DATA-ACK exchange: - Also called two-way handshake
- Or Basic Access Mechanism
Must forget Collision Detection! One single RF circuitry - Either TX or RX…
- Half-duplex
Even if two simultaneous TX+RX: large difference (100+ dB!) in TX/RX signal power - Impossible to receive while transmitting
- On a same channel, of course
Collision detection at sender: meaningless in wireless! - Ethernet = collision detection at sender
- Wireless = large difference in the interference power between sender & receiver!
- Collision OCCURS AT THE RECEIVER
Carrier Sense Multiple Access Station may transmit ONLY IF senses channel IDLE for a DIFS time - DIFS = Distributed Inter Frame Space
Key idea: ACK replied after a SIFS < DIFS - SIFS = Short Inter Frame Space
Other stations will NOT be able to access the channel during the handshake - Provides an atomic DATA-ACK transaction
Grasping wi-fi (802.11b) numbers DIFS = 50 s - Rationale: 1 SIFS + 2 slot-times
- Slot time = 20 s, more later
And when an ACK is “hidden”?
The Duration Field Allows “Virtual Carrier Sensing” - Other than physically sensing the channel, each station keeps a Network Allocation Vector (NAV)
- Continuously updates the NAV according to information read in the duration field of other frames
And when a terminal is “hidden”? The Hidden Terminal Problem - SENDER and STA cannot hear each other
- SENDER transmits to RECEIVER
- STA wants to send a frame
- Not necessarily to RECEIVER…
- STA senses the channel IDLE
- Collision occurs at RECEIVER
Destroys a possibly very long TX!!
The RTS/CTS solution
Why backoff?
Slotted Backoff
Backoff freezing When STA is in backoff stage: - It freezes the backoff counter as long as the channel is sensed BUSY
- It restarts decrementing the backoff as the channel is sensed IDLE for a DIFS period
Why backoff between consecutive tx? A listening station would never find a slot-time after the DIFS (necessary to decrement the backoff counter) Thus, it would remain stuck to the current backoff counter value forever!!
Backoff rules First backoff value: - Extract a uniform random number in range (0,CWmin)
If unsuccessful TX: - Extract a uniform random number in range (0,2×(CWmin+1)-1)
If unsuccessful TX: - Extract a uniform random number in range (0,22×(CWmin+1)-1)
Etc up to 2m×(CWmin+1)-1
Further backoff rules - After a number of attempts, transmission fails and frame is dropped
- Backoff process for new frame restarts from CWmin
- Protects against cannel capture
- unlikely when stations are in visibility, but may occur in the case of hidden stations
Two retry limits suggested: - Short retry limit (4), apply to frames below a given threshold
- Long retry limit (7), apply to frames above given threshold
- (loose) rationale: short frames are most likely generated bu realk time stations
- Of course not true in general; e.g. what about 40 bytes TCP ACKs?
DCF overhead
Example: maximum achievable throughput for 802.11b Data Rate = 11 mbps; ACK rate = 1 mbps Payload = 1500 bytes
DCF overhead (802.11b)
DCF overhead (802.11b)
Performance Anomaly Question 1: - Assume that throughput measured for a single 11 mbps greedy station is approx 6 mbps. What is per-STA throughput when two 11 mbps greedy stations compete?
Answer 1: Question 2: - Assume that throughput measured for a single 2 mbps greedy station is approx 1.7 mbps. What is per-STA throughput when two 2 mbps greedy stations compete?
Answer 2: - Approx 0.85 mbps (easy )
Question 3: - What is per-STA throughput when one 11 mbps greedy station compete with one 2 mbps greedy station?
Answer 3:
Understanding Answers 1&2 (neclect collision – indeed rare – just slightly reduce computed value) Data Rate = 11 mbps; ACK rate = 1 mbps Payload = 1500 bytes
Emerging “problem”: long-term fairness! If you have understood the previous example, you easily realize that 802.11 provides FAIR access to stations in terms of EQUAL NUMBER of transmission opportunities in the long term! But this is INDEPENDENT OF transmission speed!
Computing answer 3
Performance anomaly into action
64>
Dostları ilə paylaş: |
|
|