Transcript PPT - web.iiit.ac.in

Link Layer Devices and
Protocols
Link Layer –Addressing
“link”
• Types of links
– Between nodes in a LAN
– Between nodes of two
networks –router to router
– Wireless links
• Each node needs to be
identified uniquely
• Two types of “Node”
addressing
– IP Layer
– Link Layer
• Other layers use logical or
process level addressing
IP Addressing: Small Overview
• IP address: 32-bit
identifier for host,
router interface
• Interface: connection
between host/router
and physical link
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
– Routers typically have
multiple interfaces
223.1.3.2
223.1.3.1
– Host/Node typically
has one interface
– IP addresses
associated with each 223.1.1.1 = 11011111 00000001 00000001 00000001
interface
1
223
1
1
LAN Addresses Allocation
• MAC address allocation administered by IEEE
• Manufacturer buys portion of MAC address space
(to assure uniqueness) 224
• Analogy:
(a) MAC address: like IT-PAN numbers
(b) IP address: like postal address
• MAC flat address portability
– Can move LAN card from one LAN to another
MAC Addresses and ARP
•
IP Addresses
– Used to move datagram from one network to another –
routers are devices which do this
– Used for global addressing
• MAC (or LAN or physical or Ethernet) address:
– Used to get frame from one interface to another physicallyconnected interface (same network)
– 48 bit MAC address, typically burned in the adapter ROM
• ARP: Address Resolution Protocol
– Maps IP addresses to MAC addresses
– Used to route packets in a LAN as well as across the LAN
Types of LAN Addresses
• Global
00001000
• Local-Individual
00001010
• Multicast
00001011
• Broadcast – all 1’s
LAN Addresses
Each adapter on LAN has unique LAN address
1A-2F-BB-76-09-AD
71-65-F7-2B-08-53
Broadcast address =
FF-FF-FF-FF-FF-FF
(This is logical address)
LAN
(wired or
wireless)
= adapter
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
Interconnection Devices LAN
• Hubs
• Bridges
• Switches
Hubs
• Simple repeaters –physical layer (layer-1)
devices
• Copies bits onto all outgoing interfaces
• No CSMA/CD at hub: network adapters
detect collisions
• No frame buffering
• What is the effect on throughput of
network when using Hubs?
Interconnecting with hubs
• Backbone hub interconnects LAN segments
• Extends max distance between nodes
• But individual segment collision domains become one
large collision domain (why?)
• Can’t interconnect 10BaseT & 100BaseT (why?)
Backbone hub
hub
hub
hub
Bridges
• Bridges are layer-2 devices
• They switch data between different links
• Can connect different types of LAN segments.
E.g., 10BaseT to 100BaseT
• Bridges maintain a bridge table, each entry has
– LAN address of the node
– Bridge interface that leads to that node
– Time when the entry was placed in the table
• Bridge runs CSMA/CD algorithm; thus,
separating collision domains
• Do bridges improve throughput?
Bridge Table
Address
Interface
Time
62-FE-F7-11-89-A3
1
3
9.31
9.40
7C-BA-B2-B4-91-10
Bridge
1
62-FE-F7-11-89-89-A3
2
hub
3
hub
7C-BA-B2-B4-91-10
Bridge Forwarding
• Bridges are store-and-forward devices
• When a bridge receives a frame with destination
MAC address DD-DD-…etc from interface x
– It indexes its table using the MAC address and
locates the interface which leads to DD-DD-.. say y
– If x==y, then frame is from same LAN segment and
need not be forwarded
– If x !=y, then frame is forwarded to that interface
Bridge Learning
• Initially, table is empty
• When a frame arrives and if that frame’s source
address is not in the table, the bridge forwards
the frame onto all its other interfaces
• For each such frame, the bridge stores
– LAN address of the source
– Interface from which the frame arrived
– Time of arrival
• Bridge removes entries if no entries are received
from that source entries after certain timeout
(aging time)
• Why are bridges popular?
Loops in Bridges
 Multiple bridges are useful to build fail-safe
paths
 This may cause loops in the network, resulting
in multiple copies of the same frame being
circulated
CSE
Bridge
ECE
Hub
OBH
DL
Hub
Hub
IT
Bridge
Solution: Spanning Tree Protocol
(by Radia Perlman)
CSE
ECE
DL
IT
OBH
Switches
• Alternatively, Ethernet Switches, are highperformance multi-interface bridges
(functionally)
– Bridges have a max. of 4 interfaces
• Switches have many interfaces (>10)
• Same forwarding techniques as bridges
• Typically operate in full-duplex mode
– Send and receive simultaneously
• For example, switch with 4 100Mbps interfaces
and 20, 10Mbps interfaces to merge LANs
Dedicated Access
• Switches with multiple interfaces in full-duplex mode
provide for dedicated access –unshared link
• This can increase the aggregate bit-rate of the network
A
B
A’
Switch
C
C’
B’
Switches Summary
• Link layer devices
– Stores and forwards Ethernet frames
– Examines frame header and selectively forwards
frame based on MAC dest 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
– Switches do not need to be configured
• Filter data frames
– Create separate collision domains
• Provide dedicated access
Link Layer Implementation
• Link layer is typically implemented in a adapter
also called network interface cards (NIC)
• It has two interfaces
– A bus interface –to communicate data and control
information with its host node
– A link interface –which performs the link layer
operations, including transmit and receive
• An adapter is semi-autonomous
– It can error check received frames and discard them
without informing its host node
– “Semi” because, it shares power and buses with host
node and is ultimately under its control
Design Considerations in NIC
CPU
To network
NIC
I/O Devices
System BUS
Using CPU for Network Processing
• When data is received the NIC can interrupt the CPU to
process the destination address
– The list of addresses to which this host needs to receive packets
is known to the CPU
• The CPU is interrupted whenever a packet is received at
the NIC
– The CPU then copies the packet from the NIC into the memory
• Problems
– Interrupting CPU for handling address resolution can make CPU
not available for other tasks
– Since system BUS is a shared medium, it may be busy
Design Considerations of NIC
• Onboard address Recognition
– Use NIC to resolve destination address
– Multicast Recognition and Filtering
• Onboard Packet Buffering
– Store packets on NIC until BUS becomes free
• Direct Memory Access
– Write packets directly into memory without help of
CPU
• Operation and Data Chaining
– Perform multiple read and write using a chain of
commands without interrupting the CPU
Address Resolution Protocol
• Maintains a table of IP/MAC address
mapping, called ARP table
– ARP table is limited to nodes is limited to
nodes within a LAN
• Each node on the LAN maintains this table
• This table can be dynamically built using
ARP packet broadcasts
Essentially: ARP gives IP address to MAC
address mapping at any given time
ARP: Address Resolution Protocol
Question: how to determine
MAC address of B
knowing B’s IP address?
237.196.7.78
1A-2F-BB-76-09-AD
237.196.7.23
237.196.7.14
• 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>
LAN
71-65-F7-2B-08-53
237.196.7.88
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
–
TTL (Time To Live):
time after which
address mapping will
be forgotten (typically
20 min)
ARP protocol: Same LAN
(network)
• A wants to send datagram
to B, and B’s MAC
address is not in A’s ARP
table.
• A broadcasts ARP query
packet, containing B's IP
address
– Dest MAC address =
FF-FF-FF-FF-FF-FF
– All machines on LAN
receive ARP query
• B receives ARP packet,
replies to A with its (B's)
MAC address
– Frame sent to A’s MAC
address (unicast)
• A caches (saves) IP-toMAC 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
Routing to another LAN
Illustration: send datagram from A to B via R
Assume A know’s B IP address
A
R
Two ARP tables in router R, one for each IP network (LAN)
B
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
R
B
Routing to Another LAN
• A’s adapter sends frame
• R’s adapter receives frame
• R removes IP datagram from Ethernet frame, sees its
destined to B
• R uses ARP to get B’s MAC address
• R creates frame containing A-to-B IP datagram sends to B
Big Picture
Gateway/Router
8Mbps
Web Server
1Gbps
100Mbps
Switch
100Mbps
100Mbps
100Mbps
Mail Server
100Mbps
hub
hub
hub