Transcript what’s a computer network: “nuts and bolts” view

1.- LAN basics
 Networking basics
http://www.redes.upv.es/ralir/en/
 The Internet
 TCP/IP
 LANs topologies
 Media Access Control (MAC) techniques
Local Area Networks/School of Engineering in Computer Science/2009-2010
1.- LAN basics
http://www.redes.upv.es/ralir/en/
 Networking basics
Local Area Networks/School of Engineering in Computer Science/2009-2010
Local Area Networks (RALIR) /School of Engineering in Computer Science
3
Goals of computer networks
 to provide ubiquitous access to shared resources (e.g., printers,
databases, file systems...),
 to allow remote users to communicate (e.g., email, IP
telephony),
 to do transactions (banking, e-commerce, stock trading), and…
 … save money: downsizing
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
A “nuts and bolts” view of a network
 Millions of connected computing
devices: hosts, end-systems
 pc’s workstations, servers
 PDA’s phones, toasters
running network apps
 communication links
 fiber, copper, radio, satellite
router
server
 routers: forward packets (chunks) of
data thru network
 protocols: control sending, receiving
of msgs
regional ISP
 TCP, IP, and HTTP, FTP, PPP, …
http://www.redes.upv.es/ralir/en/
mobile
local ISP
company
network
4
workstation
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
A closer look at the network structure
1. The network edge: applications
and hosts
2. The network core:
 routers
 network of networks
3. The access networks and
physical media: communication
links
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
The network edge
 End systems (hosts):
 run application programs at
the “edge of network”
 client/server model
 client host requests, receives
service from server
 e.g., WWW client (browser)/
server; email client/server
 peer-peer model:
 host interaction symmetric
 e.g.: Gnutella, KaZaA
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
7
The network core
 Mesh of interconnected routers
 The fundamental question: how is
data transferred through net?
 Circuit switching: dedicated
circuit per call: telephone net
 Packet switching: data sent
through the network in
discrete “chunks”
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
8
The network core: Circuit switching
 End-end resources reserved
for “call”
 Characterizing parameters: link
bandwidth, switch capacity
 dedicated resources: no
sharing
 circuit-like (guaranteed)
performance
 call setup required
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
9
The network core: Packet switching
 Data traffic divided into packets
 Each packet contains a header (with address)
 Packets travel separately through network
 Packet forwarding based on the header
 Network nodes may store packets temporarily
 Destination reconstructs the message
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
1
0
The network core: Packet switching (routing)
 Goal: move packets among routers from source to destination
 datagram network:
 destination address determines next hop
 routes may change during session
 analogy: driving, asking directions
 virtual circuit network:
 each packet carries tag (virtual circuit ID), tag determines next hop
 fixed path determined at call setup time, remains fixed thru call
 routers maintain per-call state
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
1
1
The access networks and physical media
 How to connect end systems
to edge router?
 Residential access networks
 Institutional access networks
(school, company)
 Wireless access networks
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
Residential access networks: point to point access
 Dialup via modem
 up to 56Kbps direct access to
router (conceptually)
 ISDN: integrated services digital
network: 128Kbps all-digital connect
to router
 ADSL: asymmetric digital subscriber
line
 up to 1 Mbps home-to-router
 up to 8 Mbps router-to-home
 ADSL deployment: happening
 HFC: hybrid fiber coax
 asymmetric: up to 10Mbps
upstream, 1 Mbps downstream
 network of cable and fiber
attaches homes to ISP router
 shared access to router
among home
 issues: congestion,
dimensioning
1
2
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
1
3
Residential access networks: cable modems
Diagram: http://www.cabledatacomnews.com/cmic/diagram.html
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
1
4
Institutional access networks: local area networks
 company/univ local area network
(LAN) connects end system to edge
router
 Ethernet:
 shared or dedicated cable
connects end system and
router
 10 Mbs, 100Mbps, Gigabit
Ethernet
 deployment: institutions, home LANs
happening now
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
Wireless access networks
 Shared wireless access network
connects end system to router
 Wireless LANs:
 radio spectrum replaces wire
 e.g., WiFi, Bluetooth, WiMAX
 Wireless WANs:
 GPRS/EDGE over GSM
 High-Speed Downlink Packet
Access (HSDPA) a 3G (third
generation) mobile telephony
communications based on
Universal Mobile
Telecommunications System
(UMTS) networks.
router
base
station
mobile
hosts
1
5
http://www.redes.upv.es/ralir/en/
1.- LAN basics
 Networking basics
http://www.redes.upv.es/ralir/en/
 The Internet
Local Area Networks/School of Engineering in Computer Science/2009-2010
Local Area Networks (RALIR) /School of Engineering in Computer Science
Internet structure: network of networks
 Roughly hierarchical
 National/international
backbone providers (NBPs)
 e.g. BBN/GTE, Sprint, AT&T, IBM,
UUNet
 interconnect (peer) with each
other privately, or at public
Network Access Point (NAPs)
 A point of presence (POP) is a
machine that is connected to
the Internet.
 Internet Service Providers
(ISPs) provide dial-up or direct
access to POPs.
 regional ISPs
 connect into NBPs
 local ISP, company
 connect into regional ISPs
1
7
local
ISP
http://www.redes.upv.es/ralir/en/
regional ISP
NBP B
NAP
NAP
NBP A
regional ISP
local
ISP
Local Area Networks (RALIR) /School of Engineering in Computer Science
Network Access Points (NAPs)
Note: Peers in this context are
commercial backbones.
1
8
Source: Boardwatch.com
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
1
9
MCI/WorldCom/UUNET Global Backbone
Source: Boardwatch.com
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
The situation in Europe
See: http://www.redes.upv.es/ralir/en/MforS/GEANT2.WMV
Also: http://video.google.com/googleplayer.swf?docId=-4949195951027294198&hl=en-GB
More about technolgies: http://video.google.com/googleplayer.swf?docId=-4634094763983277329&hl=en-GB
2
0
http://www.redes.upv.es/ralir/en/
1.- LAN basics
 Networking basics
http://www.redes.upv.es/ralir/en/
 TCP/IP
Local Area Networks/School of Engineering in Computer Science/2009-2010
Local Area Networks (RALIR) /School of Engineering in Computer Science
A simple TCP/IP Example
 A user on host argon.tcpip-lab.edu (“Argon”) makes a web
access to URL
http://neon.tcpip-lab.edu/index.html.
 What actually happens in the network?
2
2
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
HTTP Request and HTTP response




Web browser runs an HTTP client program
Web server runs an HTTP server program
HTTP client sends an HTTP request to HTTP server
HTTP server responds with HTTP response
Argon
HTTP client
Neon
HTTP request
HTTP response
2
3
http://www.redes.upv.es/ralir/en/
HTTP server
Local Area Networks (RALIR) /School of Engineering in Computer Science
HTTP Request
GET /index.html HTTP/1.1
Accept: image/gif, */*
Accept-Language: en-us
Accept-Encoding: gzip, deflate
User-Agent: Mozilla/4.0
Host: neon.tcpip-lab.edu
Connection: Keep-Alive
2
4
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
HTTP Response
HTTP/1.1 200 OK
Date: Sat, 25 May 2002 21:10:32 GMT
Server: Apache/1.3.19 (Unix)
Last-Modified: Sat, 25 May 2002 20:51:33 GMT
ETag: "56497-51-3ceff955"
Accept-Ranges: bytes
Content-Length: 81
Keep-Alive: timeout=15, max=100
Connection: Keep-Alive
Content-Type: text/html
<HTML>
<BODY>
<H1>Internet Lab</H1>
Click <a href="http://www.tcpiplab.net/index.html">here</a> for the Internet Lab webpage.
</BODY>
</HTML>
2
5
• How does the HTTP request get from Argon to Neon ?
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
2
6
From HTTP to TCP
 To send a request, the HTTP client program establishes an TCP
connection to the HTTP server at Neon.
 The HTTP server at Neon has a TCP server running
Argon
Neon
HTTP client
HTTP request / HTTP response
HTTP server
TCP client
TCP connection
TCP server
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
2
7
Resolving hostnames and port numbers
 Since TCP does not work with hostnames and also does not
know how to find the HTTP server program at Neon, two things
must happen:
1. The name “neon.tcpip-lab.edu” must be translated into a 32-bit IP
address.
2. The HTTP server at Neon must be identified by a 16-bit port
number.
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
2
8
Translating a hostname into an IP address
 The translation of the hostname neon.tcpip-lab.edu into an IP
address is done via a database lookup
neon.tcpip-lab.edu
HTTP client
argon.tcpip-lab.edu
128.143.71.21
DNS Server
128.143.136.15
 The distributed database used is called the Domain Name
System (DNS)
 All machines on the Internet have an IP address:
argon.tcpip-lab.edu
128.143.137.144
neon.tcpip-lab.edu
128.143.71.21
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
2
9
Finding the port number
 Note: Most services on the Internet are reachable via wellknown ports. E.g. All HTTP servers on the Internet can be
reached at port number “80”.
 So: Argon simply knows the port number of the HTTP server at
a remote machine.
 On most Unix systems, the well-known ports are listed in a file
with name /etc/services. The well-known port numbers of some
of the most popular services are:
ftp 21
telnet
smtp
http://www.redes.upv.es/ralir/en/
finger
23
25
79
http
nntp
80
119
Local Area Networks (RALIR) /School of Engineering in Computer Science
Requesting a TCP Connection
 The HTTP client at argon.tcpip-lab.edu requests the TCP client to
establish a connection to port 80 of the machine with address
128.141.71.21
argon.tcpip-lab.edu
HTTP client
Establish a TCP connection
to port 80 of 128.143.71.21
TCP client
3
0
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
3
1
Invoking the IP Protocol
 The TCP client at Argon sends a
request to establish a connection
to port 80 at Neon
 This is done by asking its local IP
module to send an IP datagram
to 128.143.71.21
 (The data portion of the IP
datagram contains the request to
open a connection)
http://www.redes.upv.es/ralir/en/
argon.tcpip-lab.edu
TCP client
Send an IP datagram to
128.143.71.21
IP
Local Area Networks (RALIR) /School of Engineering in Computer Science
Sending the IP datagram to an IP router
 Argon (128.143.137.144) can deliver the IP datagram directly to
Neon (128.143.71.21), only if it is on the same IP network
(sometimes called “subnet”).
 But Argon and Neon are not on the same IP network
(Q: How does Argon know this?)
 So, Argon sends the IP datagram to its default gateway
 The default gateway is an IP router
 The default gateway for Argon is Router137.tcpip-lab.edu
(128.143.137.1).
3
2
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
The route from Argon to Neon
 Note that the gateway has a different name for each of its interfaces.
3
3
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
3
4
Finding the MAC address of the gateway
 To send an IP datagram to Router137, Argon puts the IP
datagram in an Ethernet frame, and transmits the frame.
 However, Ethernet uses different addresses, so-called Media
Access Control (MAC) addresses (also called: physical address,
hardware address)
 Therefore, Argon must first translate the IP address
128.143.137.1 into a MAC address.
 The translation of addressed is performed via the Address
Resolution Protocol (ARP)
http://www.redes.upv.es/ralir/en/
3
5
Local Area Networks (RALIR) /School of Engineering in Computer Science
Address resolution with ARP
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
Invoking the device driver
 The IP module at Argon, tells its Ethernet device driver to send
an Ethernet frame to address 00:e0:f9:23:a8:20
argon.tcpip-lab.edu
IP module
Send an Ethernet frame
to 00:e0:f9:23:a8:20
Ethernet
3
6
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
3
7
Sending an Ethernet frame
 The Ethernet device driver of Argon sends the Ethernet frame to
the Ethernet network interface card (NIC)
 The NIC sends the frame onto the wire
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
3
8
Forwarding the IP datagram
 The IP router receives the Ethernet frame at interface
128.143.137.1, recovers the IP datagram and determines that
the IP datagram should be forwarded to the interface with name
128.143.71.1
 The IP router determines that it can deliver the IP datagram
directly
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
3
9
Another lookup of a MAC address
 The router needs to find the MAC address of Neon.
 Again, ARP is invoked, to translate the IP address of Neon
(128.143.71.21) into the MAC address of neon
(00:20:af:03:98:28).
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
Invoking the device driver at the router
 The IP protocol at Router71, tells its Ethernet device driver to
send an Ethernet frame to address 00:20:af:03:98:28
router71.tcpip-lab.edu
IP module
Send a frame to
00:20:af:03:98:28
Ethernet
4
0
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
4
1
Sending another Ethernet frame
 The Ethernet device driver of Router71 sends the Ethernet frame
to the Ethernet adapter, which transmits the frame onto the
wire.
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
Data has arrived at Neon
 Neon receives the Ethernet frame
 The payload of the Ethernet frame is an IP
datagram which is passed to the IP
protocol.
 The payload of the IP datagram is a TCP
segment, which is passed to the TCP
server
Neon.cerf.edu
HTTP server
 Note: Since the TCP segment is a connection
request (SYN), the TCP protocol does not pass
data to the HTTP program for this packet.
Instead, the TCP protocol at neon will respond
with a SYN segment to Argon.
TCP server
IP module
Ethernet
4
2
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
4
3
Wrapping-up the example
 So far, Neon has only obtained a single packet
 Much more work is required to establish an actual TCP
connection and the transfer of the HTTP Request
 The example was simplified in several ways:
 No transmission errors
 The route between Argon and Neon is short
(only one IP router)
 Argon knew how to contact the DNS server (without routing or
address resolution)
 ….
http://www.redes.upv.es/ralir/en/
1.- LAN basics
http://www.redes.upv.es/ralir/en/
 LANs topologies
Local Area Networks/School of Engineering in Computer Science/2009-2010
Local Area Networks (RALIR) /School of Engineering in Computer Science
4
5
LAN basics
 A local area network is a communication network that interconnects a
variety of data devices within a small geographic area and broadcasts
data at high data transfer rates with very low error rates.
 They are typically private
 Since the local area network first appeared in the 1970s, its use has
become widespread in commercial and academic environments.
 Functions of a LAN: a few examples
 File server - A large storage disk drive that acts as a central storage repository.
 Print server - Provides the authorization to access a particular printer, accept and
queue print jobs, and provides a user access to the print queue to perform
administrative duties.
 Interconnection - A LAN can provide an interconnection to other LANs and to wide
area networks
 Manufacturing support - LANs can support manufacturing and industrial environments.
 Distributed processing - LANs can support network operating systems which perform
the operations of distributed processing.
 …
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
4
6
LAN Selection Criteria
 Cost
 For most of us, cost is an overriding constraint, and you must choose the
best solution within your budget. Usually, cost is the most inflexible
constraint under which you must operate, and in the final analysis the LAN
must be a cost-effective solution to your problem.
 Number of Workstations
 Each LAN is physically capable of supporting some maximum number of
workstations. If you exceed that maximum number, you must make some
provision for extending the maximum number.
 Number of Concurrent Users / type of use
 As the number of concurrent users goes up, so does the LAN workload. As
the LAN workload increases, you have two basic choices: You can allow
system responsiveness to decrease, or you can increase the work potential
of the system.
 Many concurrent users may increase the LAN workload.
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
LAN Selection Criteria (cont.)
 Distance and Medium
 Attaining high speed over long distances can be very expensive. Thus, each
LAN has a maximum distance it can cover.
 Speed
 It is important to you select a LAN capable of meeting your performance
goals. Available LAN speeds are 10, 100, and 1,000 Mbps, and the trend is
for increasing speeds.
 Device connectivity
 Some organizations need to attach special devices to the LAN, for example,
a plotter or scanner. LAN interfaces for such devices may not be available
on some LANs or on some LAN file servers.
 Connectivity to Other Networks
 A variety of connection capabilities exist, but a given LAN may not support
all of them.
 Adherence to Established Standards
 There are several standards for LAN implementation. Some LANs conform
to these standards whereas others do not.
4
7
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
4
8
Simple LAN Topologies
 Physical topology: Physical layout of a network
 Bus topology consists of a single cable—called a bus—
connecting all nodes on a network without intervening
connectivity devices
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
4
9
Simple LAN Topologies
 Ring topology
 Each node is connected to the two nearest nodes so the entire network
forms a circle
 Active topology
 Each workstation transmits data
 Each workstation functions as a repeater
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
0
Simple LAN Topologies
 Star topology
 Every node on the network is connected through a central device
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
1
Hybrid LAN Topologies
 Hybrid topology
 Complex combination of the simple physical topologies
 Star-wired ring
 Star-wired topologies use physical layout of a star in conjunction with token
ring-passing data transmission method
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
2
Hybrid LAN Topologies
 Star-wired bus
 In a star-wired bus topology, groups of workstations are star-connected to
hubs and then networked via a single bus
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
3
Hybrid LAN Topologies
 Daisy-Chained
 Daisy chain is linked series of devices
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
4
Hybrid LAN Topologies
 Hierarchical
 Uses layers to separate devices by their priority or function
http://www.redes.upv.es/ralir/en/
5
5
Local Area Networks (RALIR) /School of Engineering in Computer Science
The UPV extended LAN
http://www.redes.upv.es/ralir/en/
1.- LAN basics
http://www.redes.upv.es/ralir/en/
 Media Access Control (MAC) techniques
Local Area Networks/School of Engineering in Computer Science/2009-2010
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
7
Media Access Control (MAC)
 single shared communication channel
 two or more simultaneous transmissions by nodes: interference
 only one node can send successfully at a time
 Media Access Control:
 distributed algorithm that determines how stations share channel, i.e.,
determine when a station can transmit
 communication about channel sharing must use channel itself!
 Takes also care of:
 Assembly of data into frame with address and error detection fields
 Disassembly of frame
 Address recognition
 Error detection
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
8
Media Access Control (MAC)
 For the same LLC, several MAC options may be available
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
5
9
MAC Protocols: a taxonomy
 Three broad classes:
 Channel Partitioning
 divide channel into smaller “pieces” (time slots, frequency)
 allocate piece to node for exclusive use
 Random Access
 allow collisions
 “recover” from collisions
 “Taking turns”
 tightly coordinate shared access to avoid collisions
 Goal: efficient, fair, simple, decentralized
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
Channel Partitioning MAC protocols
TDMA
TDMA: time division multiple access
 access to channel in "rounds"
 each station gets fixed length slot (length = pkt trans time) in
each round
 unused slots go idle
 example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle
 inefficient with low duty cycle users and at light load.
6
0
http://www.redes.upv.es/ralir/en/
FDMA: frequency division multiple access
 channel spectrum divided into frequency bands
 each station assigned fixed frequency band
 unused transmission time in frequency bands go idle
 example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6
idle
frequency bands
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
1
Channel Partitioning MAC protocols
FDMA
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
2
Random Access MAC protocols
 When node has packet to send
 transmit at full channel data rate R.
 no a priori coordination among nodes
 two or more transmitting nodes -> “collision”,
 random access MAC protocol specifies:
 how to detect collisions
 how to recover from collisions (e.g., via delayed retransmissions)
 Examples of random access MAC protocols:
 pure ALOHA
 slotted ALOHA
 CSMA and CSMA/CD
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
3
Random Access MAC protocols
Pure (unslotted) ALOHA
 unslotted Aloha: simpler, no synchronization
 pkt needs transmission:
 send without awaiting for beginning of slot
 collision probability increases:
 pkt sent at t0 collide with other pkts sent in [t0 -1, t0 +1]
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
Random Access MAC protocols
Slotted Aloha
 time is divided into equal size slots (= pkt trans. time)
 node with new arriving pkt: transmit at beginning of next slot
 if collision: retransmit pkt in future slots with probability p, until
successful.
Success (S), Collision (C), Empty (E) slots
6
4
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
5
Random Access MAC protocols
CSMA: Carrier Sense Multiple Access
CSMA: listen before transmit:
 If channel sensed idle: transmit entire pkt
 If channel sensed busy, defer transmission
 Persistent CSMA: retry immediately with probability p when channel
becomes idle (may cause instability)
 Non-persistent CSMA: retry after random interval
 human analogy: don’t interrupt others!
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
6
Random Access MAC protocols
CSMA collisions
spatial layout of nodes along ethernet
collisions can occur:
propagation delay means
two nodes may not hear
each other’s transmission
collision:
entire packet transmission
time wasted
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
7
“Taking Turns” MAC protocols
 “taking turns” protocols look for best of both worlds,
because:
 Channel partitioning MAC protocols:
 share channel efficiently at high load
 inefficient at low load: delay in channel access, 1/N bandwidth allocated
even if only 1 active node!
 Random access MAC protocols
 efficient at low load: single node can fully utilize channel
 high load: collision overhead
http://www.redes.upv.es/ralir/en/
Local Area Networks (RALIR) /School of Engineering in Computer Science
6
8
“Taking Turns” MAC protocols
Polling:
 master node “invites” slave nodes to
transmit in turn
 Request to Send, Clear to Send
msgs
 concerns:
 polling overhead
 latency
 single point of failure (master)
http://www.redes.upv.es/ralir/en/
Token passing:
 control token passed from one node
to next sequentially.
 token message
 concerns:
 token overhead
 latency
 single point of failure (token)