COMPSCI 311 – Computer Network Architecture
Ethernet
Ethernet
• The dominant local are network for over 30 years
• Built in the mid-70s at Xerox PARC
• Standardized as IEEE 802.3
• Originally 10Mbps
• Later 100Mbps, 1Gbps, 10Gbps, 40Gbps, and 100Gbps
• Based on the Aloha radio network protocol
• Very common at datacenters and local networks, competes with Wi-Fi
CSMA/CD
• Carrier Sense
• Nodes can sense whether the medium is “idle” or “busy”
CSMA/CD
• Carrier Sense
• Nodes can sense whether the medium is “idle” or “busy”
• Multiple Access
• Nodes share a single medium, like a bus (originally a coax cable)
• One node transmits, all nodes receive
CSMA/CD
• Carrier Sense
• Nodes can sense whether the medium is “idle” or “busy”
• Multiple Access
• Nodes share a single medium, like a bus (originally a coax cable)
• One node transmits, all nodes receive
• Collision Detection
• Nodes detect when the messages they transmit interfere with a
message transmitted by another node
Ethernet switches
• Today Ethernet is usually deployed as point-to-point
• Ethernet switches multiplexes access to medium
• Close to no collisions, and carrier sense rarely applies
• But concepts still apply to networks with shared mediums, like Wi-Fi
• Old Ethernet hubs created a shared medium, but are no longer in use
Ethernet switches
• Today Ethernet is usually deployed as point-to-point
• Ethernet switches multiplexes access to medium
• Close to no collisions, and carrier sense rarely applies
• But concepts still apply to networks with shared mediums, like Wi-Fi
• Old Ethernet hubs created a shared medium, but are no longer in use
• Here we will focus on a single, shared Ethernet link
Physical properties
• Ethernet was originally designed to work with coax cables up to 500m
• Today’s twisted copper pairs and fibers can go further
Physical properties
• Ethernet was originally designed to work with coax cables up to 500m
• Today’s twisted copper pairs and fibers can go further
Physical properties
• Up to four segments connected by repeaters
• Originally, hosts could be up to 2500m apart
• Terminators at the end of the cable
Physical properties
• Up to four segments connected by repeaters
• Originally, hosts could be up to 2500m apart
• Terminators at the end of the cable to avoid “bounce back” effect
• Long range, but shared medium and lots of collisions
• Originally Manchester encoding, but 4b/5b, 8b/10b, 64b/66b
in later, faster standards
Frame format
• Preamble: Allows the receiver to synchronize with the message
• Alternates zeros and ones
• Addresses: 48-bit source and destination identifiers
• Type: Demultiplexing at higher layer
Frame format
• Preamble: Allows the receiver to synchronize with the message
• Alternates zeros and ones
• Addresses: 48-bit source and destination identifiers
• Type: Demultiplexing at higher layer
• Frames must be at least 64 bytes to allow for collision detection
• Frames must be at most 1500 bytes
Ethernet addresses
• Ethernet addresses are 48 bits long (6 bytes)
• Usually printed in hexadecimal with bytes separated by colons
• 08:00:20:BE:4C:F2
• Each Ethernet address is unique
• Manufactures are allocated 3-byte prefixes (OUI)
• AMD has been allocated 08:00:20
• Manufactures should generate unique addresses for their adaptors
Ethernet addresses
• Ethernet addresses are 48 bits long (6 bytes)
• Usually printed in hexadecimal with bytes separated by colons
• 08:00:20:BE:4C:F2
• Each Ethernet address is unique
• Manufactures are allocated 3-byte prefixes (OUI)
• AMD has been allocated 08:00:20
• Manufactures should generate unique addresses for their adaptors
• Adaptor accepts frames
• To its address
• To the broadcast address (FF:FF:FF:FF:FF:FF)
• To any multicast address its configured to accept
• To any address when configured in promiscuous mode
Transmitter algorithm
• Transmitters sense whether the medium is idle
• Transmitters start transmitting immediately after the medium becomes idle
• Transmitters cannot hold the medium indefinitely
• Wait 9.6us before transmitting again, yield to other transmitters
• Maximum frame size is 1500 bytes
• When a collision happens
• Exponential back-off
• Adaptors wait 51.2k microseconds before retransmitting, where k is chosen randomly
between [0, 2n – 1] and n is the number of consecutive collisions so far
• Adaptors typically retry up to 16 times
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
A B C
Interference
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
A B C
A and C are unaware of the collision at B!
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
Interference
detected at C
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
A must keep
transmitting
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
A must keep
transmitting
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
A must keep B detects the
transmitting collision
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
A must keep
transmitting
Collision detection
• Adaptors detect collisions when they are transmitting
• Collision happens when a concurrent competing transmission occurs
• Transmissions must be long enough for concurrent transmission to
collide with it
A B C
A finally detects
the collision
Minimum frame size
• Transmissions must continue until concurrent competing
transmissions reach sender
• Worst case
• Two nodes at the extremes of the Ethernet cable
• Longest possible cable is 2500m and round-trip delay is 51.2us
• Node C performs carrier sense and starts transmitting right before A’s transmission
reaches it → it will take a whole round-trip delay for C’s transmission to reach A
• On 10Mbps Ethernet, we can transmit 512 bits in 51.2us
Multi-access and Ethernet performance
• Multi-access Ethernets perform badly under heavy load
• A utilization of 30% is already considered heavy load
• Lots of capacity wasted by collisions
• Early Ethernet deployments were conservative
• Few hosts and short cables to minimize collisions
• Flow and congestion control at higher layers help a ton
Gigabit Ethernet
• Now there is 100Gbps Ethernet, and 400Gbps is on the way
• Faster Ethernet standards are backwards compatible
• Can connect a 40Gbps to a 1Gbps adaptor
• Faster speeds require
• Extending the minimum packet size to detect collisions
• Avoiding collisions altogether by using switches
• Better cables
• Shorter cables
Dominance and longevity of Ethernet
• Several properties propelled Ethernet into a dominant position
• Entirely plug and play, in the ’70s
• Zero configuration required
• If cables and adaptors work, communication works
• Easy to attach new hosts and expand
• Cables and switches are cheap
• Backwards compatibility allows incremental deployment
