Transcript ppt

CSE401N: COMPUTER NetworkS
LAN address & ARP
Ethernet Basics
1
LAN technologies
Data link layer so far:

services, error detection/correction, multiple
access
Next: LAN technologies
addressing
 Ethernet
 hubs, bridges, switches
 802.11
 PPP
 ATM

2
LAN Addresses and ARP
32-bit IP address:
 network-layer address
 used to get datagram to destination IP network
(recall IP network definition)
LAN (or MAC 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)
burned in the adapter ROM
3
NIC or Network Adaptor
4
LAN Addresses and ARP
Each adapter on LAN has unique LAN address
5
LAN Address (more)
 MAC address allocation administered by IEEE
 manufacturer buys portion of MAC address space (to
assure uniqueness)
 Analogy:
(a) MAC address: like Social Security Number
(b) IP address: like postal address
 MAC flat address => portability

can move LAN card from one LAN to another
 IP hierarchical address NOT portable
 depends on IP network to which node is attached
6
Recall Earlier Routing Discussion
Starting at A, given IP
datagram addressed to E:
A
223.1.1.1
223.1.2.1
 look up net. address of E, find C
 link layer send datagram to C
inside link-layer frame
frame source,
dest address
C’s MAC A’s MAC
addr
addr
223.1.1.2
223.1.1.4 223.1.2.9
C
B
223.1.1.3
datagram source,
dest address
A’s IP
addr
E’s IP
addr
223.1.3.27
223.1.3.1
223.1.2.2
E
223.1.3.2
IP payload
datagram
frame
7
ARP: Address Resolution Protocol
Question: how to determine
MAC address of C
knowing C’s IP address?
 Each IP node (Host,
Router) on LAN has
ARP table
 ARP Table: IP/MAC
address mappings for
some LAN nodes
< IP address; MAC address; TTL>

TTL (Time To Live): time
after which address
mapping will be forgotten
(typically 20 min)
8
ARP protocol
 A knows B's IP address, wants to learn physical
address of B
 A broadcasts ARP query pkt, containing B's IP
address
 all machines on LAN receive ARP query
 B receives ARP packet, replies to A with its (B's)
physical layer address
 A caches (saves) IP-to-physical address pairs until
information becomes old (times out)
 soft state: information that times out (goes
away) unless refreshed
9
10
11
Address Resolution Protocol (ARP)
1. With TCP/IP networking, a data packet must contain both a
2.
3.
4.
5.
6.
7.
8.
destination MAC address and a destination IP address.
Some devices will keep tables that contain MAC addresses and
IP addresses of other devices that are connected to the same
LAN.
These are called Address Resolution Protocol (ARP) tables.
ARP tables are stored in RAM memory, where the cached
information is maintained automatically on each of the devices.
Each device on a network maintains its own ARP table. >arp -a
When a network device wants to send data across the network,
it uses information provided by the ARP table.
When a source determines the IP address for a destination, it
then consults the ARP table in order to locate the MAC address
for the destination.
If the source locates an entry in its table, destination IP
address to destination MAC address, it will associate the IP
address to the MAC address and then uses it to encapsulate the
data.
12
Address Resolution Protocol (ARP)
1. The computer that requires an IP and
MAC address pair broadcasts an ARP
request.
2. All the other devices on the local area
network analyze this request, and if one
of the local devices matches the IP
address of the request, it sends back an
ARP reply that contains its IP-MAC pair.
3. Another method to send data to the
address of a device that is on another
network segment is to set up a default
gateway.
4. If the receiving host is not on the same
segment, the source host sends the data
using the actual IP address of the
destination and the MAC address of the
router.
13
ARP conversation
HEY - Everyone please listen!
Will 128.213.1.5 please send me
his/her Ethernet address?
not me
Hi Green! I’m 128.213.1.5, and
my Ethernet address is
87:A2:15:35:02:C3
14
RARP conversation
HEY - Everyone please listen!
My Ethernet address is
22:BC:66:17:01:75.
Does anyone know my IP address ?
not me
Hi Green! Your IP address is
128.213.1.17.
15
Getting a datagram from source to
dest.
routing table in A
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
IP datagram:
misc source dest
fields IP addr IP addr
data
A
 datagram remains
unchanged, as it travels
source to destination
 addr fields of interest
here
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
16
Getting a datagram from source to
dest.
misc
data
fields 223.1.1.1 223.1.1.3
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
Starting at A, given IP
datagram addressed to B:
 look up net. address of B
 find B is on same net. as A
A
223.1.1.1
223.1.2.1
 link layer will send datagram
directly to B inside link-layer
frame
 B and A are directly
connected
223.1.1.4
223.1.1.4
1
2
2
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
17
Getting a datagram from source to
dest.
misc
data
fields 223.1.1.1 223.1.2.3
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
Starting at A, dest. E:
 look up network address of E
 E on different network
A, E not directly attached
routing table: next hop
router to E is 223.1.1.4
link layer sends datagram to
router 223.1.1.4 inside linklayer frame
datagram arrives at 223.1.1.4
continued…..
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1





223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
18
Getting a datagram from source to
dest.
misc
data
fields 223.1.1.1 223.1.2.3
Arriving at 223.1.4,
destined for 223.1.2.2
 look up network address of E
 E on same network as router’s
interface 223.1.2.9
 router, E directly attached
 link layer sends datagram to
223.1.2.2 inside link-layer
frame via interface 223.1.2.9
 datagram arrives at
223.1.2.2!!! (hooray!)
Dest.
next
network router Nhops interface
223.1.1
223.1.2
223.1.3
A
-
1
1
1
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
19
Routing to another LAN
walkthrough: routing from A to B via R
A
R
B
 In routing table at source Host, find router
111.111.111.110
 In ARP table at source, find MAC address E6-E900-17-BB-4B, etc
20
A
R
B
 A creates IP packet with source A, destination B
 A uses ARP to get R’s physical layer address for 111.111.111.110
 A creates Ethernet frame with R's physical address as dest,





Ethernet frame contains A-to-B IP datagram
A’s data link layer sends Ethernet frame
R’s data link layer receives Ethernet frame
R removes IP datagram from Ethernet frame, sees its destined
to B
R uses ARP to get B’s physical layer address
R creates frame containing A-to-B IP datagram sends to B
21
Ethernet (IEEE 802.3)
“dominant” LAN technology:
 first widely deployed LAN technology
 simpler, cheaper than token ring, FDDI, and
ATM

Lesson learned: KISS (Keep It Simple, Stupid)
 kept up with speed race: 10, 100, 1000 Mbps
Metcalfe’s Ethernet
sketch
22
Ethernet(2)
 First widely used LAN Technology
 Simpler than token ring, FDDI, or ATM
 Comply with new Technology and Speed
Can run over coaxial cable,or twisted pair, or
fiber optics or radio link
 10Mbps, 100Mbps, 1Gbps, 10Gbps.

 Ethernet Hardware(Hub/Bridge/Switch)
is widely available and cheap
23
Ethernet and the OSI Model
24
Ethernet and the OSI Model
25
Repeaters: Layer1 Device
26
Ethernet and the OSI Model
27
Naming(MAC Address)
28
802.3 Frame Structures
29
Ethernet Frame Structures
30
Ethernet Frame Structures
31
Ethernet Frame Structure
Sending adapter encapsulates IP datagram
(or other network layer protocol packet) in
Ethernet frame
8
6
6
2
46-1500 (including padding)
4
Preamble:
 7 bytes with pattern 10101010 followed by
one byte with pattern 10101011
 used to synchronize receiver, sender clock
rates
32
Ethernet Frame Structure(2)
 Addresses: 6 bytes each
 if adapter receives frame with matching destination
address, or with broadcast address (e.g. ARP request), it
passes data in frame to network layer
 otherwise, adapter discards frame
 Type (2 bytes): indicates the higher layer
protocol, mostly IP but others may be supported
(such as Novell IPX and AppleTalk)
 Data (46-1500 bytes): MTU is 1500 bytes, MIN
frame size = 46 + 18 = 64 bytes = 512 bits
 CRC (4 bytes): checked at receiver, if error is
detected, the frame is simply dropped
33
Unreliable, connectionless service
 Connectionless: No handshaking between sending and
receiving adapter.
 Unreliable: receiving adapter doesn’t send ACKs or
NAKs to 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
34
Ethernet: From Bit to Electrical Signal
 Use Manchester encoding
 One voltage change per bit
For a “1”, a voltage from 1 to 0
 For a “0”, a voltage from 0 to 1

 Example
35
MAC Rules & Collision Detection/Backoff
36
MAC Rules and Collision Detection/Backoff
37
Ethernet Timing
 Slot time:

amount of time required to travel between
the furthest points of the collision domain,
collide with another transmission at the
last possible instant, and then have the
collision fragments return to the sending
station and be detected.
38
Interframe Spacing and Backoff
39
The Basic MAC Mechanisms of Ethernet
CSMA/CD + Exponential backoff
get a packet from upper layer;
K := 0; n :=0; // K: random wait time; n: no. of collisions
repeat:
wait for K * 512 bit-time;
while (network busy) wait;
wait for 96 bit-time after detecting no signal;
transmit and detect collision;
if detect collision
stop and transmit a 48-bit jam;
n ++;
m:= min(n, 10), where n is the number of collisions
choose K randomly from {0, 1, 2, …, 2m-1}.
if n < 16 goto repeat
else giveup
Question: Why exponential backoff?
40
Ethernet: uses CSMA/CD
A: sense channel, if idle
then {
transmit and monitor the channel;
If detect another transmission
then {
abort and send jam signal;
update # collisions;
delay as required by exponential backoff algorithm;
goto A
}
else {done with the frame; set collisions to zero}
}
else {wait until ongoing transmission is over and goto A}
41
Ethernet’s CSMA/CD (more)
Jam Signal: make sure all other transmitters are aware of
collision
Bit time: 0.1 microsec for 10 Mbps Ethernet; for K=1023,
wait time is about 50 msec
Exponential Backoff:
 Goal: adapt retransmission attempts to estimated
current load
 heavy load: random wait will be longer
 first collision: choose K from {0,1}; delay is K x 512 bit
transmission times
 after second collision: choose K from {0,1,2,3}…
 after ten or more collisions, choose K from
{0,1,2,3,4,…,1023}
42
Why 64 bytes min frame length?
 10Base5 Ethernet: 10Mbps, max segment 500m, max 4
repeaters, max network diameter 2500m

Repeater: physical layer device that amplifies and retransmits
bits it hears on one interface to its other interfaces, used to
connect multiple segments
 Round trip time (worst case collision detection time) about
50 microsec


All frames must take more than 50 microsec to send so that
transmission is still taking place when the noise burst gets back
to sender
With 10Mbps bandwidth, 1 bit time = 0.1 microsec
 minimum frame size at least 500 bits, choose 512 bits to add
some margin of safety
 As network speed goes up, the minimum frame length must
go up or the maximum cable length must come down

E.g. for a 2500m 1Gbps LAN, minimum frame size should be
6400 bytes
43
CSMA/CD efficiency
 Tprop = max prop. time between 2 nodes in LAN
 ttrans = time to transmit max-size frame
efficiency 
1
1  5t prop / ttrans
 Efficiency goes to 1 as tprop goes to 0
 Efficiency goes to 1 as ttrans goes to infinity
 Much better than ALOHA, but still decentralized,
simple, and cheap
44
Parameters for 10Mbps Ethernet
45