Transcript 5.3 Multiple Access Protocol

Computer Networking
A Top-Down Approach Featuring the Internet
计算机网络-自顶向下方法与Internet特色
Chapter5 The Link Layer and
Local Area Networks
Chapter Goals
understand principles behind data link layer
services:
error detection & correction
sharing a broadcast channel: multiple access
link layer addressing
reliable data transfer, flow control: done!
implementation of various link layer
technologies
Ethernet：broadcast channel
PPP：point to point channel
2
School of Computer Science & Technology
Roadmap
5.1 Link Layer: Introduction and Services
5.2 Error-Detection and -Correction
5.3 Multiple Access Protocols
5.4 Link-Layer Addressing
5.5 Ethernet
5.6 Hubs and Switches
5.7 PPP
5.8 Link Virtualization: ATM and MPLS
3
School of Computer Science & Technology
1. Link Layer Services
5.1 Introduction and
Services
A link-layer protocol is
used to move a
datagram over an
individual link
“link”
Links
communication channels
that connect adjacent nodes
The PDU of a link-layer
protocol is called Frame
4
School of Computer Science & Technology
1. Link Layer Services
5.1 Introduction and
Services
Datagrams may be transferred by different
link protocols over different links:
e.g., Ethernet on first link, frame relay on
intermediate links, 802.11 on the last link
Different link protocol may provide different
services
e.g., may or may not provide rdt (reliable data
transfer) over a link
5
School of Computer Science & Technology
1. Link Layer Services
5.1 Introduction and
Services
Possible Services
Framing
Link Access
Reliable delivery
Flow Control
Error detection and correction
Half/Full duplex
6
School of Computer Science & Technology
1. Link Layer Services
5.1 Introduction and
Services
Framing
encapsulate a datagram into a frame, adding
header and trailer
The structure of a the frame is specified by
the link layer protocol
Link Access
How to share a medium ?
Medium Access Control (MAC) protocol serves to
coordinate the frame transmission of the many
nodes
7
School of Computer Science & Technology
1. Link Layer Services
5.1 Introduction and
Services
Reliable delivery between adjacent nodes
Using ack and retransmission as TCP
we have learned how to do this already
seldom used on low bit error link
Such as fiber, some twisted pair media
wireless links: high error rates
Q: why both link-level and end-end
reliability?
8
School of Computer Science & Technology
1. Link Layer Services
5.1 Introduction and
Services
Flow Control:
pacing adjacent sending and receiving nodes
Error Detection and Correction
errors caused by signal attenuation, noise.
receiver detects presence of errors:
informs sender for retransmission or drops frame
receiver identifies and corrects bit error (s) without
resorting to retransmission
Full-duplex, Half-duplex, Simplex
with half duplex, nodes at both ends of a link can
transmit, but not at same time.
9
School of Computer Science & Technology
2. Adapters Communicating
5.1 Introduction and
Services
datagram
sending
node
rcving
node
link layer protocol
frame
frame
adapter
adapter
link layer protocol implemented in an adapter
aka. Network Interface Card (NIC)
Ethernet card, PCMCIA card, 802.11 card
10
School of Computer Science & Technology
2. Adapters Communicating
5.1 Introduction and
Services
datagram
sending
node
rcving
node
link layer protocol
frame
frame
adapter
adapter
sending side:
encapsulates datagram in a frame
adds error checking bits, rdt, flow control, etc.
receiving side
checking errors, rdt, flow control, etc
extracts datagram from frame and passes it to
receiving node
School of Computer Science & Technology
11
2. Adapters Communicating
5.1 Introduction and
Services
adapter is a semi-autonomous system
It can receive a frame, check errors and discard
the corrupted frames without notifying other
components
It interrupts the parent node only if it wants to pass
datagram up the protocol stack
The parent node fully delegated to the adapter the
task of transmitting the datagram across the link
The adapter is typically housed in the box as the
rest of the node
12
School of Computer Science & Technology
Roadmap
5.1 Link Layer: Introduction and Services
5.2 Error-Detection and -Correction
5.3 Multiple Access Protocols
5.4 Link-Layer Addressing
5.5 Ethernet
5.6 Hubs and Switches
5.7 PPP
5.8 Link Virtualization: ATM and MPLS
14
School of Computer Science & Technology
Error Detection and Correction
5.2 Error Detection and
Correction
EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields
• Error detection not 100% reliable!
• protocol may miss some errors, but rarely
• larger EDC field yields better detection and correction
15
School of Computer Science & Technology
Error-Detection & -Correction Techniques
5.2 Error Detection and
Correction
Parity Checks
Internet Checksumming
Cyclic redundancy Check
16
School of Computer Science & Technology
1. Parity Checks
5.2 Error Detection and
Correction
1.Single Bit Parity: Detect single bit errors
－ Can detect odd number bits error
odd
1
even
17
School of Computer Science & Technology
1. Parity Checks
5.2 Error Detection and
Correction
2. Two Dimensional Bit Parity:
－can detect single bit errors
－can correct single bit errors
0
0
18
School of Computer Science & Technology
1. Parity Checks
5.2 Error Detection and
Correction
0
0
FEC: The ability of the receiver to both
detect and correct errors
School of Computer Science & Technology
19
2. Internet Checksum
5.2 Error Detection and
Correction
Sender
treat segment contents as sequence of 16-bit
integers
checksum: addition (1’s complement sum) of
segment contents
sender puts checksum value into checksum field
Receiver:
the sum of the received data (including the
checksum) = all 1 bits:
NO - error detected
YES - no error detected.
20
School of Computer Science & Technology
2. Checksumming
5.2 Error Detection and
Correction
Checksumming methods require
relatively little overhead, but
provide relatively weak protection
against errors
Why is checksumming used at the
transport layer?
Transport layer is typically implemented in
soft in a host as a part of OS.
21
School of Computer Science & Technology
3. Cyclic Redundancy Check
5.2 Error Detection and
Correction
 The data (D) are viewed as a d-bit binary number
 The Sender chooses r additional bits (R, CRC bits) and
appends them to the D, such that d+r bits is exactly
divisible by G using modulo-2 arithmetic.
 Sender and receiver both know the (r+1)-bit generator (G)
 The receiver divides (d+r)-bit (D,R) by G.
 If non-zero remainder: error detected!
22
School of Computer Science & Technology
3. Cyclic Redundancy Check
5.2 Error Detection and
Correction
 Modulo-2 algorithm
No addition carries
No subtraction borrows
The addition (+) and the subtraction (-) are identical
and both are equivalent to the bitwise exclusive-or
(XOR)
For example:
1011 XOR 0101 = 1110
1011 — 0101 = 1110
1011 ＋ 0101 = 1110
23
School of Computer Science & Technology
3. Cyclic Redundancy Check
5.2 Error Detection and
Correction
How the Sender computes the R?
Want:
equivalently:
D.2r XOR R = nG
D.2r XOR R XOR R = nG XOR R
D.2r = nG XOR R
equivalently:
if we divide D.2r by G, want remainder R
D.2r
R = remainder[
]
G
24
School of Computer Science & Technology
3. Cyclic Redundancy Check
5.2 Error Detection and
Correction
Example:
D=101110 G = 1001
r =3 and T
(D,000)=101110000
T (D,R)=101110011
CRC can detect all burst errors less than r+1 bits.
CRC-32( international standard )
=100000100110000010001110110110111
School of Computer Science & Technology
25
Roadmap
5.1 Link Layer: Introduction and Services
5.2 Error-Detection and -Correction
5.3 Multiple Access Protocols
5.4 Link-Layer Addressing
5.5 Ethernet
5.6 Hubs and Switches
5.7 PPP
5.8 Link Virtualization: ATM and MPLS
26
School of Computer Science & Technology
Introduction
5.3 Multiple Access Protocol
Two types of links:
point-to-point
Only a sender and a receiver sits at each end
PPP for dial-up access
broadcast (shared wire or medium)
Many senders and receivers share the link
traditional Ethernet
WLAN
Upstream of HFC
27
School of Computer Science & Technology
Introduction
5.3 Multiple Access Protocol
single shared broadcast channel
two or more simultaneous transmissions by
nodes will cause interference
Collision-if node receives two or more
signals at the same time
Multiple Access Problem
How to coordinate the access of a
shared broadcast channel?
28
School of Computer Science & Technology
Introduction
5.3 Multiple Access Protocol
multiple access protocol
distributed algorithm that determines how
nodes share the channel, i.e., determine when
and which node can transmit
communication about channel sharing must
use channel itself!
no out-of-band channel for coordination
29
School of Computer Science & Technology
Introduction
5.3 Multiple Access Protocol
The requirements to multiple access
protocol for a broadcast channel of rate
R bps
When one node can transmit, it send at rate R.
When M nodes want to transmit over the channel,
each can send at average rate R/M bps
Fully decentralized:
no special node to coordinate transmissions
no synchronization of clocks, slots
Simple
30
School of Computer Science & Technology
Introduction
5.3 Multiple Access Protocol
Categories of Multiple Access Protocol
Channel Partitioning
divide channel into smaller “pieces” (time slots,
frequency, code)
allocate piece to node for exclusive use
Random Access
channel not divided, allow collisions
“recover” from collisions
Taking turns
Nodes take turns, but nodes with more to send
can take longer turns
School of Computer Science & Technology
31
1. Channel Partitioning Protocols
5.3 Multiple Access Protocol
TDM (Time Division Multiplexing)
Time divided into Frames and further divides each
Frame into N slots, each slot is then assigned to one of
the N nodes
Nodes access to channel in "rounds"
unused slots go idle
FDM (Frequency Division Multiplexing)
CDMA (Code Division Multiplexing Access)
32
School of Computer Science & Technology
1.1 TDMA
5.3 Multiple Access Protocol
TDMA eliminates collisions and is
perfectly fair, but has two drawbacks
each node gets a dedicated transmission rate of
R/N and the average rate is limited to R/N
a node must always wait for its turn
33
School of Computer Science & Technology
1. Channel Partitioning Protocols
5.3 Multiple Access Protocol
TDM (Time Division Multiplexing)
FDM (Frequency Division Multiplexing)
The spectrum is divided into frequency bands
each station assigned fixed frequency band
unused transmission time in each frequency
bands goes idle
CDMA (Code Division Multiplexing Access)
34
School of Computer Science & Technology
1.2 FDMA
can avoids collisions
share the channel fairly
a node is limited to a bandwidth of R/N
a node need not waits for its turn
frequency bands
5.3 Multiple Access Protocol
advantages and drawbacks
35
School of Computer Science & Technology
1. Channel Partitioning Protocols
5.3 Multiple Access Protocol
TDM (Time Division Multiplexing)
FDM (Frequency Division Multiplexing)
CDMA (Code Division Multiplexing Access)
Assign a different code to each node
Each node encodes the data bits using its unique code
Different nodes can transmit simultaneously
Usually used in military systems in early time
Details discussed in wireless networking of Advanced
Computer Networks
36
School of Computer Science & Technology
Introduction
5.3 Multiple Access Protocol
Categories of Multiple Access Protocol
Channel Partitioning
Random Access
channel not divided, allow collisions
“recover” from collisions
Taking turns
37
School of Computer Science & Technology
2. Random Access Protocols
5.3 Multiple Access Protocol
When a node has a packet to send, it transmit
the packet at full channel data rate R bps.
no a priori coordination among nodes
may cause collision
Each node involved in the collision
repeatedly retransmits its packet until the
packet gets through without any collision.
a node waits some time choosed randomly
before retransmission
38
School of Computer Science & Technology
2. Random Access Protocols
5.3 Multiple Access Protocol
random access protocol specifies:
how to detect collisions?
how to recover from collisions?
Examples of random access protocols:
slotted ALOHA
Pure ALOHA
CSMA, CSMA/CD, CSMA/CA
39
School of Computer Science & Technology
2.1 Slotted ALOHA
5.3 Multiple Access Protocol
Assumptions
all frames have same size: L bits
time is divided into equal size slots
time to transmit 1 frame: L/R
nodes start to transmit frames only at beginning of
slots
nodes are synchronized
if there 2 or more nodes transmitting in a slot, all
nodes can detect the collision
40
School of Computer Science & Technology
2.1 Slotted ALOHA
5.3 Multiple Access Protocol
Operation
when node obtains fresh frame, it transmits
in the next slot
If there is not a collision, node can send new
frame in next slot
The sending node can detect the collision before
the end of the slot
If there is a collision ,node retransmits frame
in each subsequent slot with probability p
until success
School of Computer Science & Technology
41
2.1 Slotted ALOHA
5.3 Multiple Access Protocol
Advantages
single active node can continuously transmit at full
rate of channel
highly decentralized: only slots in nodes need to be
in synchronization
simple
42
School of Computer Science & Technology
2.1 Slotted ALOHA
5.3 Multiple Access Protocol
Drawbacks
many wasted slots because of collision
successful slot: The slot which only one node transmit
idle slots because of the probabilistic policy
nodes must detect the collision in less than time to
transmit a packet
clock synchronization used to determine the
start/end of one slot
School of Computer Science & Technology
43
2.1 Slotted ALOHA
5.3 Multiple Access Protocol
Efficiency of slotted ALOHA is the longrun fraction of successful slots when there
are many nodes, each with many frames to
send
Suppose N nodes with many frames to send,
each transmits in each slot with probability p
Prob. that any node has a success = Np(1-p)N-1
lim NP(1  P)
N 1
 1 / e  0.37
N 
44
School of Computer Science & Technology
2.1 Slotted ALOHA
5.3 Multiple Access Protocol
N 1
E ( p)  Np(1  p)
E ' ( p)  N (1  p) N 1  Np( N  1)(1  p) N 2
 N (1  p) N 2 ((1  p)  p( N  1))
1
E ' ( p )  0  p* 
N
1
1
1
E ( p*)  N (1  ) N 1  (1  ) N 1
N
N
N
1
lim (1  )  1
N 
N
1
1
lim (1  ) N 
N 
N
e
1
lim E ( p*) 
N 
e
1 N
)
N

1
1
N
(1 
45
School of Computer Science & Technology
2.2 Pure (un-Slotted) ALOHA
5.3 Multiple Access Protocol
unslotted ALOHA－no synchronization
when frame first arrives, transmit immediately
collision probability increases:
frame sent at t0 collides with other frames sent in [t0-L/r,t0+L/R]
46
School of Computer Science & Technology
2.2 Pure (un-Slotted) ALOHA
5.3 Multiple Access Protocol
P(success by given node) =
P(node transmits) .P(no other node transmits in [t0-L/R,t0] . P(no other
node transmits in [t0,t0+Ｌ/Ｒ] = p . (1-p)N-1 . (1-p)N-1= p . (1-p)2(N-1)
E ( p)  Np(1  p) 2( N 1)
E ' ( p)  N (1  p) 2( N 2 )  Np2( N  1)(1  p) 2( N 3)
 N (1  p) 2( N 3) ((1  p)  p2( N  1))
1
E ' ( p )  0  p* 
2N  1
N
1 2 ( N 1)
E ( p*) 
(1 
)
2N  1
2N  1
1 1 1
lim E ( p*)   
N 
2 e 2e
47
School of Computer Science & Technology
2.3 CSMA
5.3 Multiple Access Protocol
CSMA: Carrier Sense Multiple Access
listen before transmitting
If channel sensed idle, then transmits entire frame
immediately
If channel sensed busy, then waits a random
amount of time and then senses the channel
48
School of Computer Science & Technology
2.3 CSMA
5.3 Multiple Access Protocol
If all nodes perform carrier sensing, do
collisions occur all the same?
collisions can still occur:
spatial layout of nodes
propagation delay means two nodes
may not hear each other’s transmission
note: the role of distance &
propagation delay in determining
collision probability
collision: entire packet
transmission time wasted
49
School of Computer Science & Technology
2.4 CSMA/CD (collision detection)
5.3 Multiple Access Protocol
CSMA/CD: carrier sensing and
deferral as in CSMA
collisions detected within short time
colliding transmissions aborted,
reducing channel wastage
50
School of Computer Science & Technology
2.4 CSMA/CD (collision detection)
5.3 Multiple Access Protocol
collision detection:
easy in wired LANs
measure signal strengths, compare transmitted,
received signals
but difficult in wireless LANs
receiver shut off while transmitting for saving
energy
51
School of Computer Science & Technology
2.4 CSMA/CD (collision detection)
5.3 Multiple Access Protocol
52
School of Computer Science & Technology
Introduction
5.3 Multiple Access Protocol
Categories of Multiple Access Protocol
Channel Partitioning
Random Access
Taking turns
Nodes take turns, but nodes with more to send
can take longer turns
53
School of Computer Science & Technology
3. Taking-Turns Protocols
5.3 Multiple Access Protocol
Polling:
master node “invites” slave nodes to transmit in turn
concerns:
polling overhead and polling latency
single point of failure (master)
Token passing:
 control token passed from one node to next sequentially.
 concerns:
token overhead and latency
single point of failure (token)
54
School of Computer Science & Technology
4. Summary
5.3 Multiple Access Protocol
What do you do with a shared media?
Channel Partitioning, by time, frequency or
code
Random partitioning (dynamic),
ALOHA, S-ALOHA, CSMA, CSMA/CD
CSMA/CD used in Ethernet
CSMA/CA used in 802.11 WLAN (Wireless LAN)
carrier sensing: easy in some technologies (wire),
hard in others (wireless)
Taking Turns
polling from a central site, or token passing
55
School of Computer Science & Technology
LAN technologies
Categories of Networks
LAN-Local Area Network
WAN-Wide Area Network
MAN-Metropolitan Area Network
 Data Link layer so far:
services, error detection/correction, multiple access
 Next: LAN technologies
addressing
Ethernet
hubs, switches
PPP
56
School of Computer Science & Technology
Roadmap
5.1 Link Layer: Introduction and Services
5.2 Error-Detection and -Correction
5.3 Multiple Access Protocols
5.4 Link-Layer Addressing
5.5 Ethernet
5.6 Hubs and Switches
5.7 PPP
5.8 Link Virtualization: ATM and MPLS
57
School of Computer Science & Technology
1. MAC Addresses
5.4 Link-Layer Addressing
32-bit IP address:
network-layer address
used to get datagram to destination IP subnet
MAC (or LAN or physical or Ethernet)
address:
used to get datagram from one interface to another
physically-connected interface (same network)
48 bit MAC address (for most LANs) is burned in the
ROM of NIC
for example, 1A-2F-BB-76-09-AD
58
School of Computer Science & Technology
1. MAC Addresses
5.4 Link-Layer Addressing
59
School of Computer Science & Technology
1. MAC Addresses (more)
5.4 Link-Layer Addressing
MAC flat address ➜ portability
can move LAN card from one LAN to
another
Like an ID card
IP hierarchical address NOT portable
depends on IP subnet to which node is
attached
Like a postal address
62
School of Computer Science & Technology
2. ARP: Address Resolution Protocol
5.4 Link-Layer Addressing
Question: how to determine MAC address
of B if a node knows B’s IP address?
237.196.7.78
1A-2F-BB-76-09-AD
237.196.7.23
237.196.7.14
LAN
71-65-F7-2B-08-53
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
237.196.7.88
63
School of Computer Science & Technology
2. ARP: Address Resolution Protocol
5.4 Link-Layer Addressing
Each IP node on LAN has an ARP table
ARP Table: IP/MAC address mappings
for some nodes sited on the same LAN
< IP address; MAC address; TTL>
TTL typically 20 min
64
School of Computer Science & Technology
2. ARP: Address Resolution Protocol
5.4 Link-Layer Addressing
A wants to send datagram to B, and B’s MAC
address not in A’s ARP table.
A broadcasts ARP request packet is sent which
containing B's IP address
ARP Packet:={src_ip, src_mac, des_ip,des_mac}
ARP packet is encapsulated in a frame whose dest MAC
address = FF-FF-FF-FF-FF-FF
all machines on LAN receive the ARP query
request
B receives ARP frame, replies to A with its (B's)
MAC address
frame sent to A’s MAC address (unicast)
why?
School of Computer Science & Technology
65
2. ARP: Address Resolution Protocol
5.4 Link-Layer Addressing
ARP Packet
66
School of Computer Science & Technology
2. ARP: Address Resolution Protocol
5.4 Link-Layer Addressing
A caches (saves) IP-to-MAC address pair in its
ARP table until information becomes old (times
out)
soft state: information that times out (goes away) unless
refreshed
ARP is “plug-and-play”:
nodes create their ARP tables without
intervention from net administrator
67
School of Computer Science & Technology
2. Routing to another LAN
walkthrough: send datagram from A to B via R assume
A knows B’s IP address
A
R
B
Two ARP tables in router R, one for each IP network
(LAN)
68
School of Computer Science & Technology
2. Routing to another LAN
 A creates datagram with source A, destination B
 A uses ARP to get R’s MAC address for 111.111.111.110
 A creates link-layer frame with R's MAC address as dest,
frame contains A-to-B IP datagram
 A’s adapter sends frame
 R’s adapter receives frame
 R removes IP datagram from Ethernet frame, sees it’s
destined to B
 R uses ARP to get B’s MAC address
 R creates frame containing A-to-B IP datagram sends to B
69
School of Computer Science & Technology
3. Dynamic Host Configuration Protocol
5.4 Link-Layer Addressing
DHCP is a Client/Server protocol
The client is typically a newly arriving host
wanting to obtain network configuration
information
each subnet will have a DHCP server at
least.
runs over UDP
plug and play
70
School of Computer Science & Technology
3. Dynamic Host Configuration Protocol
5.4 Link-Layer Addressing
Operation
server discovery msg.
Dest. IP:255.255.255.255, Source IP:0.0.0.0
Dest. MAC:FF-FF-FF-FF-FF-FF
server offer msg.
DHCP offer msg. including IP address, Subnet Mask,
Address lease time, DNS Server, Default
Gateway/Router, etc.
DHCP request msg.
choose one from multiple offers, may be come from
different DHCP servers
DHCP ACK msg.
server ack.
71
School of Computer Science & Technology
3. Dynamic Host Configuration Protocol
5.4 Link-Layer Addressing
UDP Port Number
72
School of Computer Science & Technology
Roadmap
5.1 Link Layer: Introduction and Services
5.2 Error-Detection and -Correction
5.3 Multiple Access Protocols
5.4 Link-Layer Addressing
5.5 Ethernet
5.6 Hubs and Switches
5.7 PPP
5.8 Link Virtualization: ATM and MPLS
73
School of Computer Science & Technology
Introduction
5.5 Ethernet
“dominant” wired LAN technology:
 cheap $20 for 100Mbs!
 first widely used LAN technology
 Simpler, cheaper than token LANs and ATM
 Kept up with speed race: 10 Mbps – 10 Gbps
Metcalfe’s Ethernet
sketch
74
School of Computer Science & Technology
Introduction
5.5 Ethernet
Bus topology popular through mid 90s
Now star topology prevails
Connection choices: hub or switch (more later)
hub or
switch
75
School of Computer Science & Technology
1. Ethernet Frame Structure
5.5 Ethernet
Sending adapter encapsulates IP datagram (or
other network layer protocol packet) in Ethernet
frame
Preamble(8 bytes):
7 bytes with pattern 10101010 followed by one byte with
pattern 10101011
 used to synchronize receiver, sender clock rates
76
School of Computer Science & Technology
1. Ethernet Frame Structure
5.5 Ethernet
Addresses: 6 bytes
matching destination MAC address, or with broadcast
address (eg ARP packet), to net-layer protocol
otherwise, adapter discards frame
Type:
indicates the higher layer protocol (mostly IP but Novell
IPX and AppleTalk)
CRC:
checked at receiver, if error is detected, the frame is
simply dropped
77
School of Computer Science & Technology
1.1 Manchester Encoding
5.5 Ethernet
78
School of Computer Science & Technology
1.2 Unreliable and connectionless service
5.5 Ethernet
Connectionless
no handshaking between sending and receiving
adapter.
Unreliable
receiving adapter doesn’t send ACKs/NAKs to the
sending adapter
stream of datagrams passed to network layer can
have gaps
gaps will be filled if app is using TCP
otherwise, app will see the gaps
79
School of Computer Science & Technology
2. Ethernet uses CSMA/CD (P460)
5.5 Ethernet
No slots
adapter doesn’t transmit if it senses that
some other adapter is transmitting, that is,
carrier sense
transmitting adapter aborts when it senses
that another adapter is transmitting, that is,
collision detection
Before attempting a retransmission, adapter
waits a random time, that is, random access
80
School of Computer Science & Technology
2. Ethernet‘s CSMA/CD (P461)
5.5 Ethernet
1. Adapter receives datagram from net layer & creates frame
2. If an adapter senses channel idle, it starts to transmit frame. If
it senses channel busy, waits until channel idle and then
transmits.(96-bit times)
3. If adapter transmits entire frame without detecting another
transmission, the adapter is done with frame !
4. If adapter detects another transmission while transmitting,
aborts and sends jam signal(48-bit stream)
5. After aborting, adapter enters exponential backoff: after the
mth collision, adapter chooses a K at random from
{0,1,2,…,2m-1}. Adapter waits K·512 bit times and returns to
Step 2
School of Computer Science & Technology
81
2. Ethernet‘s CSMA/CD (P461-462)
5.5 Ethernet
Exponential Backoff:
Goal:
adapt retransmission attempts to estimated current
load
heavy load: random wait will be longer
first collision: choose K from {0,1};
after second collision: choose K from {0,1,2,3}…
after tenth or more collisions, choose K from
{0,1,2,3,4,…,1023}
delay is K*512 bit-time
82
School of Computer Science & Technology
2. Ethernet‘s CSMA/CD
5.5 Ethernet
Bit time:
1 microsec for 10 Mbps Ethernet
for K=1023, wait time is about 50 msec
Jam Signal:
make sure all other transmitters are aware of
collision; 48 bits
83
School of Computer Science & Technology
CSMA/CD Example
5.5 Ethernet
Ethernet网络中的只有两个节点A和B活动，相
距225bit-time。假设A和B同时发送Frame造成
冲突，并且A和B选择不同的K值退后重传。两
节点重传的Frame会不会再一次造成冲突？
 t=0时，A和B同时开始发送Frame
 t=225bit-time时两者均检测到冲突
 A和B在t=225+48＝273bit-time结束传输jam信号
 假设KA=0, KB=1
 何时A开始重传？
何时A重传信号到达B?
 何时B计划开始重传？
B计划的重传会不会延后进行？
84
School of Computer Science & Technology
CSMA/CD Example (contd…)
5.5 Ethernet
时间t (bit-time)
0
225
225＋48＝273
273+225 = 498
498+ 96 = 594
273+512 = 785
785+ 96 = 881
594+225 = 819
881>819
事
件
A和B均开始发送Frame
A和B均检测到冲突
A和B结束传输Jam信号
B的最后一位Jam信道到达A
A检测到信道空闲
B计划重新侦测信道是否空闲
B计划开始重传Frame
A重传Frame的第一位到达B
B将自己的重传计划推后进行
85
School of Computer Science & Technology
Roadmap
5.1 Link Layer: Introduction and Services
5.2 Error-Detection and -Correction
5.3 Multiple Access Protocols
5.4 Link-Layer Addressing
5.5 Ethernet
5.6 Hubs and Switches
5.7 PPP
5.8 Link Virtualization: ATM and MPLS
87
School of Computer Science & Technology
1. Hubs (P465)
5.6 Interconnections
Hubs are essentially physical-layer repeaters:
bits coming from one link go out all other links
at the same rate
no frame buffering
no CSMA/CD at hub: adapters detect collisions
may provide net management functionality
twisted pair
hub
88
School of Computer Science & Technology
1. Hubs (P465)
5.6 Interconnections
 Backbone hub interconnects LAN segments
 Extends max distance between nodes
 But individual segment collision domains become one large
collision domain
 Can’t interconnect 10BaseT & 100BaseT
backbone hub
hub
hub
hub
89
School of Computer Science & Technology
2. Switch (P467)
5.6 Interconnections
Link layer device
stores and forwards Ethernet frames
examines frame header and selectively
forwards frame based on dest MAC address
when frame is to be forwarded on segment,
uses CSMA/CD to access segment
transparent
hosts are unaware of presence of switches
plug-and-play, self-learning
90
School of Computer Science & Technology
2.1 Forwarding / Filtering (P468)
5.6 Interconnections
A switch has a switch table
(MAC Address, Interface, Time Stamp)
stale entries in table dropped (TTL can be
60 min)
switch learns which hosts can be
reached through which interfaces
when frame received, switch “learns”
location of sender: incoming LAN segment
records sender/location pair in switch table
92
School of Computer Science & Technology
Switch example (P469)
Suppose C sends a frame to D
1
3
2
B
C
hub
hub
hub
A
address interface
switch
I
D
E
F
G
A
B
E
G
C
1
1
2
3
1
H
Switch receives frame from C
notes in switch table that C is on interface 1
because D is not in table, switch forwards frame into
interfaces 2 and 3 (broadcasting)
frame received by D
93
School of Computer Science & Technology
Switch example (P469)
Suppose D replies back with frame to C.
1
switch
3
2
B
C
hub
hub
hub
A
address interface
I
D
E
F
G
A
B
E
G
C
1
1
2
3
1
H
Switch receives frame from D
notes in switch table that D is on interface 2
because C is in table, switch forwards frame only to
interface 1
frame received by C
94
School of Computer Science & Technology
2.2 Self-Learning (P471)
5.6 Interconnections
Switch Table is built automatically,
dynamically, autonomously — without
any intervention from a network
administrator or from a configuration
protocol.
95
School of Computer Science & Technology
2.2 Self-Learning (P471)
5.6 Interconnections
 switch table is initially empty
 if frame’s dest address is not in the Switch table,
switch forwarded the frame to all other interfaces,
otherwise, the frame is forwarded to the interface
 for each incoming frame, switch stores in its table
 MAC address in frame’s source address field
 interface that the frame comes from
 arrival time
 switch deletes an address in the table if no frames
are received with that address as the source address
after a period of time
96
School of Computer Science & Technology
2.3 Switch: traffic isolation
5.6 Interconnections
switch installation breaks subnet into LAN segments
switch can filter packets:
same-LAN-segment frames not usually forwarded onto
other LAN segments
segments become separate collision domains
switch
collision
domain
hub
collision domain
hub
hub
collision domain
97
School of Computer Science & Technology
2.4 Switches: dedicated access
5.6 Interconnections
Switch with many interfaces
Hosts have direct connection
C’
to switch
No collisions; full duplex
A
B
switch
Switching: A-to-A’ and B-toB’ simultaneously, no
collisions
C
B’
A’
98
School of Computer Science & Technology
More on Switches (P473)
5.6 Interconnections
cut-through switching:
frame forwarded from input to output port
without first collecting entire frame
slight reduction in latency
combinations of shared/dedicated,
10/100/1000 Mbps interfaces
99
School of Computer Science & Technology
Institutional network
to external
network
mail server
web server
router
switch
IP subnet
hub
hub
hub
100
School of Computer Science & Technology
Switches vs. Routers (P475)
5.6 Interconnections
 both store-and-forward devices
routers: network layer devices
switches: link layer devices
 routers maintain routing tables, implement routing
algorithms
 switches maintain switching tables, implement filtering,
self-learning algorithms
switch
101
School of Computer Science & Technology
Summary comparison (P476)
hubs
routers
switches
traffic
isolation
no
yes
yes
plug & play
yes
no
yes
optimal
routing
cut
through
no
yes
no
yes
no
yes
102
School of Computer Science & Technology
Roadmap
5.1 Link Layer: Introduction and Services
5.2 Error-Detection and -Correction
5.3 Multiple Access Protocols
5.4 Link-Layer Addressing
5.5 Ethernet
5.6 Hubs and Switches
5.7 PPP
5.8 Link Virtualization: ATM and MPLS
103
School of Computer Science & Technology
Homeworks
Chapter 5
P.495
Problem: 1,4,11,12
114
School of Computer Science & Technology