Birth of Ethernet May 22, 1973: Ethernet memo

Birth of Ethernet

• 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

• 10, 100, 1000, 10G

• 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

Signal transmission & reception on twisted pair

• 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
• Unicast address
• 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

Ethernet vs Aloha: collision handling

Carrier Sense Multiple Access

• 1. Listen before talking

Carrier Sense Multiple Access

• 2. If channel detected busy: defer

Collision Detection

• 3. Listen while talking

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

• As minimum frame size
• As maximum RTT

• 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

• Transmission medium = twisted pair point-to-point link
• Hub distributes signal across all stations

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
• More bw!

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

Further issues with C-T

• Cut-through possible only if source and destination ports have same bit rate

• Symmetric switching.

• Different rates  buffering necessary  S&F only

• Asymmetric switching 

• 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

• Ports: module/port-#

• 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

• Before learning

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
• 1 and 2 Mbps operation
• 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
• Carrier Sense failure
• 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

• Truncated exponential backoff

• 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:

• Approx 3 mbps (easy )

• 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