chapter4-themediumaccesscontrolsublayer-230102143330-82dd047e.ppt

MACLAYER DATA LINK LAYER COMPUTER NETWORKS

1. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
The Medium Access Control
Sublayer
Chapter 4

2. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Static Channel Allocation
•Multiplexing schemes : divide the resources
•Service delay T of a channel with capacity C bps, average
frame arrival rate of λ frames/sec, average frame length of
1/μ bits:
•Service delay of the same channel splat to N segments:

3. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Assumptions for Dynamic Channel Allocation
1.Independent traffic
2.Single channel
3.Observable Collisions
4.Continuous or slotted time
5.Carrier sense or no carrier sense

4. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Multiple Access Protocols
•ALOHA
•Carrier Sense Multiple Access
•Collision-free protocols
•Limited-contention protocols
•Wireless LAN protocols

5. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
ALOHA (1)
In pure ALOHA, frames are transmitted
at completely arbitrary times
Collision
Collision
Time
User
A
B
C
D
E

6. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
ALOHA (2)
Vulnerable period for the shaded frame = 2t
Average packets to be transmitted per 2 frame interval = 2G
Probability of sending k frames during a frame time =
probability of zero frames =
Channel throughput =

7. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
ALOHA (3)
The probability of a transmission requiring exactly k attempts:
The expected number of transmissions:

8. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Persistent and Nonpersistent CSMA
Comparison of the channel utilization versus load for various
random access protocols.

9. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
CSMA with Collision Detection
When collision is detected, nodes stop sending their frames.
 station must wait 2T to know if it has seized the channel or not.
 for a 1 km cable T= 5 μsec
CSMA/CD can be in one of three states: contention, transmission, or idle.

10. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Collision-Free Protocols (Bitmap protocol)
a)low-numbered stations must wait on average 1.5N slots and
high-numbered stations must wait 0.5N slots.
b) the mean for all stations is N slots.
c)Channel efficiency = d /(d + N) if each frame contains d bits.

11. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Collision-Free Protocols (Token Ring)
IEEE802.5, 802.17
The efficiency is same as bitmap protocol.
Station
Direction of
transmission
Token

12. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Binary Countdown
A dash indicates silence.
The channel efficiency = d /(d + log2 N).
If the first bits of a frame are the station’s address, efficiency = 100%

13. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Limited-Contention Protocols
Use Contention at low load to provide low delay, and collision-
free technique at high load to provide good channel efficiency.
The probability that some station successfully acquires the
channel during a given slot =
the best value of p is 1/k.

14. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Limited-Contention Protocols
a.divide the stations into (not necessarily disjoint) groups.
b.Only the members of group 0 are permitted to compete for
slot 0; and so on.
c.At one extreme, each group has but one member, it
resembles collision free protocols like binary countdown.
d.The limiting case is a single group containing all stations,
which resembles CSMA protocols.
e.The protocol should assign many stations per slot when the
load is low and few (or even just one) station per slot when
the load is high.

15. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
The Adaptive Tree Walk Protocol
The tree for eight stations.
the average number of ready stations per time slot = q
level i has a fraction 2^−i of the stations below it.
the expected number of ready stations below level i= (2^−i)q
at level i = log2 q in the tree should the search begin.

16. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Wireless LAN Protocols
(hidden & exposed terminals)

17. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Wireless LAN Protocols (MACA)
(a)A sending an RTS (30 bytes) to B.
(b) B responding with a CTS to A.

18. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Ethernet (IEEE 802.3)
a)Classic Ethernet
–Shared medium
–2.5 km max + 4 repeaters
b)switched Ethernet
–Fast Ethernet : 100 Mbps
–Gigabit Ethernet
–10 Gigabit Ethernet
Thick Ethernet : 500 m, 100 users
Thin Ethernet: 185 m, 30 users

19. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Classic Ethernet Physical Layer

20. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Classic Ethernet MAC sublayer
•Preamble: 10101010  10 MHz square wave 6.4 μsec
•Start of frame: 10101011
•D_addr: 0… : unicast, 1… : multicast, 11…1 : broadcast
•S_addr: globally unique for each NIC. First 3 bytes are for
manufacturers assigned by IEEE, the last 3 byte is assigned
by manufacturer to each produced NIC.

21. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
MAC Sublayer Protocol (2)
oCollision detection can take as long as 2 so a minimum
frame length is required.
oFor a 2500 m cable: RTT = 50 μsec
oFor 10 Mbps BW = min frame size = 500 bit or 64 bytes.

22. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
CSMA/CD with
Binary Exponential Backoff
a)After i’th consecutive collision, the sender nodes wait a random number of
time slots between 0 and 2^i − 1.
b)Each Time slot = 51.2 μsec = 512 bit times
c)after 10 collisions, the interval is frozen at maximum 1023 slots.
d)After 16 collisions, the controller reports failure back

23. Ethernet Performance
probability A that some station acquires the channel:
maximized when p = 1/k, with A → 1/e as k →∞
The probability that the contention interval has exactly j slots:
mean number of slots per contention:
slot duration = 2τ, the mean contention interval, w = 2τ/A.
w is at most 2τe
∼∼
5.4τ.
mean frame takes P sec 
The longer the cable, the longer the contention interval

24. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Efficiency of Ethernet at 10 Mbps with 512-bit slot times

25. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Switched Ethernet (1)
(a) Hub. (b) Switch.

26. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Switched Ethernet (2)
An Ethernet switch.
Switch
Twisted pair
Switch ports
Hub

27. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Fast Ethernet
100B-T4: uses 4 twisted pairs with 25 MHz BW. 1 to the
switch, 1 from the switch and other 2 are interchangeable.
Using 3 voltage levels for symbols. Manchester encoding.
100B-TX: 4B/5B encoding. 125 MHz BW results 100 Mbps.
2 pairs of cable required.
100B-FX: only works with switches because the maximum
cable length should be less than 250 m for CD to work.

28. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Gigabit Ethernet
a)Two ways to enhance cable length to 200 m when using hubs:
–Hardware carrier extension to 512 bytes.
–frame bursting
b)8B/10B encoding is used to maintain synchronization.
c)In UTP cables all 4 pairs are used in simultaneous full-duplex mode!
With 5 voltage levels
d)Pause frames are defined to cease the communication speed.

29. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
10 Gigabit Ethernet
Fiber cables use 64B/66B coding is used.
CX cables use 8B/10B coding and 3.125 Gsymbol/sec on
each pair.
T cabling requires 16 voltage levels. LDPC (Low Density
Parity Check) is used.
40Gbps and 100Gbps Ethernet standards are in the way.

30. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Ethernet benefits
a)Reliable: by introducing switches
b)Cheap: twisted pairs and NICs
c)Easy to maintain: no software requirement. Easy
configuration.
d)Well integration with IP: both are connection less.
e)Flexible: evolve by time in speed requirements with minimum
reconfiguration and changes.

31. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Wireless Lans
•802.11 architecture and protocol stack
•802.11 physical layer
•802.11 MAC sublayer protocol
•802.11 frame structure
•Services

32. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
802.11 Architecture and Protocol Stack (1)
802.11 architecture – infrastructure mode
Access
Point
Client
To Network

33. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
802.11 Architecture and Protocol Stack (2)
802.11 architecture – ad-hoc mode-

34. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
802.11 Protocol Stack
1-2 Mbps 11 Mbps 54 Mbps600 Mbps

35. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
802.11b PHY Layer
a)1 Mbps : 11 chip barker code to spread the signal with BPSK
to send 1 bit per 11 chip. The chip rate is 11 Mchips/sec.
b)2 Mbps : QPSK (Quadrature Phase Shift Keying) to send 2
bits per 11 chip.
c)5.5 Mbps: CCK (Complementary Code Keying) with 4 bits per
8 chips.
d)11 Mbps: CCK with 8 bits per 8 chips.

36. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
802.11a, g, n PHY Layer
a)Works in 5GHz band.
b)Uses OFDM (Orthogonal frequency-division multiplexing) with 52
subcarriers 48 for data and 4 for sync.
c)Each symbol lasts 4μs and sends 1, 2, 4, or 6 bits.
d)Supports 8 data rates from 6 up to 54Mbps.
e)Communication range is 1/7 802.11b because of freq. band.
f)802.11 g uses OFDM in 2.4GHz band.
g)Supports same rates of 802.11a with same range of 802.11b
h)802.11n doubles the channel width from 20 to 40MHz.
i)Uses multiple antennas and MIMO techniques to increase BW.

37. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
The 802.11 MAC Sublayer Protocol
Sending a frame with CSMA/CA.
The initial back off gets exponentially bigger if no ack is received.

38. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Collision Avoidance mechanism
The use of virtual channel sensing using CSMA/CA.
NAV (Network Allocation Vector)
RTS/CTS: request to send/ clear to send

39. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
CSMA/CA
a)RTS/CTS mechanism is seldom used, because it slows down
the communication.
b)The random back-off mechanism as well as virtual carrier
sensing (by overhearing the NAV field) are the main
mechanisms to avoid collision.
c)Fragmentation is also used to keep the frame error rates
small.
d)Fragments are sent in bursts when channel is acquired and
each fragment should be acknowledged before the next one
is sent.

40. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Power management
a)Nodes go to sleep mode and inform AP of it.
b)AP buffers traffic for sleeping nodes.
c)AP sends periodic beacons to announce which node has a
buffered frame.
d)Nodes should wake up at beacon intervals (typically
100msec) to see if they have frames.
e)If so they tell the AP to send them the frames.

41. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Interframe timing for QoS purposes
a)SIFS (Short InterFrame Spacing)
b)DIFS (Distributed Coordination Function InterFrame Spacing)
c)AIFS (Arbitration InterFrame Space)
d)EIFS (Extended InterFrame Spacing)

42. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
802.11 Frame Structure
Format of the 802.11 data frame

43. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Data Link Layer Switching
•Uses of bridges
•Learning bridges
•Spanning tree bridges
•Repeaters, hubs, bridges, switches,
routers, and gateways
•Virtual LANs

44. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Using bridges to connect LANs

45. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
backward learning
a)hash tables are initially empty.
b)Bridges use a flooding algorithm.
c)Gradually By looking at the source addresses, they can tell which
machines are accessible on which ports.
d)it makes an entry in its hash table for each station.
e)the arrival time of the last frame is noted in the entry.
f)It purges all entries more than a few minutes old.
1. If the port for the destination address is the same as the source port, discard
the frame.
2. If the port for the destination address and the source port are different,
forward the frame on to the destination port.
3. If the destination port is unknown, use flooding and send the frame on all
ports except the source port.
Forwarding Rules

46. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Protocol processing at a bridge

47. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Loop creation in case of using redundant
links between bridges

48. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Spanning Tree Bridging
a)B1 is elected to be the root because of its lowest ID.

49. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Poem by Radia Perlman (1985)
Algorithm for Spanning Tree
I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree which must be sure to span.
So packets can reach every LAN.
First the Root must be selected
By ID it is elected.
Least cost paths from Root are traced
In the tree these paths are placed.
A mesh is made by folks like me
Then bridges find a spanning tree.

50. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Repeaters, Hubs, Bridges, Switches,
Routers, and Gateways
(a) Which device is in which layer.
(b) Frames, packets, and headers.

51. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Virtual LANs (1)
A building with centralized wiring using hubs and a switch.

52. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Virtual LANs (2)
Two VLANs, gray and white, on a bridged LAN.
Frames from gray LAN nodes are only forwarded to gray LAN ports.

53. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
The IEEE 802.1Q Standard (1)
The standard adds VLAN field in the MAC header.
Bridged LAN that is only partly VLAN-aware. The shaded
frames are originally VLAN aware. The empty ones are not.

54. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
The IEEE 802.1Q Standard (2)
The 802.3 (legacy) and 802.1Q Ethernet frame formats.

55. Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Home work assignment
Student Assigned problems (problems between 26-35 should be ommited)
1 37 40 6 27 1 35 9 41 9 4
2 7 42 10 16 20 27 32 39 28 17
3 14 35 9 40 34 12 7 1 13 1
4 32 15 7 5 17 8 39 2 41 30
5 26 9 21 24 2 13 28 9 20 20
6 31 4 1 30 22 28 33 15 4 38
7 11 28 10 28 4 41 31 6 23 37
8 36 12 37 24 35 40 31 26 29 24
9 5 26 4 8 15 29 41 4 19 28
10 28 36 42 30 27 4 35 33 20 38
11 28 32 27 22 38 35 24 2 6 1
12 33 31 22 16 32 0 3 30 16 35
13 36 9 14 32 30 15 14 17 20 24
14 41 30 31 1 7 5 42 22 34 2
15 7 24 21 38 9 9 37 0 11 6
16 32 5 0 28 16 23 3 4 10 18
17 22 38 35 19 8 40 23 26 9 20
18 1 17 23 7 25 18 40 15 18 15
19 39 28 6 4 25 5 12 22 17 19
20 23 30 2 25 4 26 10 37 11 18
21 38 37 21 20 30 21 10 9 20 27
22 29 13 25 16 17 10 13 8 22 11
23 1 1 15 4 40 40 32 32 34 37
24 28 24 30 12 15 41 12 41 41 36
25 10 32 9 32 31 18 43 35 38 34