Addressing: routing to another LAN
Download
Report
Transcript Addressing: routing to another LAN
LINK LAYER
د.عـــادل يوسف أبو القاسم
LINK LAYER: INTRODUCTION
global ISP
wired links
wireless links
LANs
في طبقة الربط سنسميهاpackets ال
وهي كبسولة تحتوي الframe
. datagram
Link Layer
Terminology:
سنسمي كل منlink layer عند دراسة ال
سنسميهمrouters و الhost ال
. nodes
nodes قنوات االتصال التي تربط ال
: ً مثالlinks المتجاورة سنسميها
منdatagram هي نقل الlink وظيفة طبقة ال
ً اخرى مجاورة لها فيزيائياnode الىnode
. link خالل
5-2
LINK LAYER: CONTEXT
e.g., Ethernet on first link,
frame relay on
intermediate links, 802.11
on last link
trip from Princeton to Lausanne
limo: Princeton to JFK
plane: JFK to Geneva
train: Geneva to Lausanne
tourist = datagram
transport segment =
communication link
transportation mode = link
layer protocol
travel agent = routing
algorithm
Link Layer
datagram يتم ارسال ال
different link بواسطة
different علىprotocols
: مثال. links
transportation analogy:
5-3
LINK LAYER SERVICES
framing,
link access
)link والوصول الى الframes (التقسيم الى
encapsulate datagram into frame, adding
header, trailer
channel access if shared medium
“MAC” addresses used in frame headers to
identify source, dest
reliable delivery between adjacent
wireless links: high error rates
nodes
افضل اكتشافه على مستوى الend-end بدال من اكتشاف الخطأ في ال
. node-node
5-4
LINK LAYER SERVICES (MORE)
flow
control:
.التحكم في تدفق البيانات من المرسل الى المستقبل
error
detection:
. frames اكتشاف االخطاء في ال
error
correction:
تصحيح االخطاء التي يتم اكتشافها
half-duplex
and full-duplex
with half duplex, nodes at both ends of link can transmit, but not at
same time
Link Layer
5-5
WHERE IS THE LINK LAYER IMPLEMENTED?
in each and every host
link layer implemented in
“adaptor” (aka network
interface card NIC) or on a
chip
Ethernet card, 802.11 card;
Ethernet chipset
implements link, physical
layer
attaches into host’s system
buses
Link Layer
application
transport
network
link
cpu
memory
controller
link
physical
host
bus
(e.g., PCI)
physical
transmission
network adapter
card
5-6
PARITY CHECKING
وفيها يتم اضافة bitللفريم لتحدد هل حدث تعديل للفريم ام ال هذه البت
تجعل عدد الواحدات في الفريم فردي او زوجي
Even two-dimensional bit parity:
detect and correct single bit errors
Odd single bit parity:
detect single bit errors
هنالك طريقة اخرى الكتشاف االخطاء وهي ال checksumوالتي
تطرقنا لها في محاضرات سابقة
5-7
MULTIPLE ACCESS LINKS, PROTOCOLS
: links هنالك نوعين من ال
1.
point-to-point
2.
PPP for dial-up access
point-to-point link between Ethernet switch, host
broadcast (shared wire or medium)
old-fashioned Ethernet
upstream HFC
802.11 wireless LAN
shared wire (e.g.,
cabled Ethernet)
shared RF
(e.g., 802.11 WiFi)
shared RF
(satellite)
Link Layer
humans at a
cocktail party
(shared air, acoustical)
5-8
MULTIPLE ACCESS PROTOCOLS
االشارات تشترك في قناة اتصال واحدة
اذا ارسل اكثر من جهاز بيانات في نفس الوقت فأن ذلك يؤدي
الى حدوث تصادم . collision
multiple access protocol
هي عبارة عن خوارزميات موزعة تحدد كيفية مشاركة ال linkبين ال nodes
المختلفة .
5-9
Link Layer
AN IDEAL MULTIPLE ACCESS PROTOCOL
ال multiple access protocolالمثالي يعمل وفق اآلتي:
given: broadcast channel of rate R bps
الخصائص المطلوبة :
.1عندما تريد nodeواحدة االرسال من خالل القناة فأن ال nodeترسل بمعدل
R bps
.2عندما تريد N nodesاالرسال ,فأن كل nodeترسل بمعدل . R/M
.3يفضل ان يكون ال مركزي حيث ال توجد nodeمعينة مهمتها ادارة عملية
المشاركة.
.4يفضل ان يكون بسيطا ً
5-10
Link Layer
MAC PROTOCOLS: TAXONOMY
: MAC هنالك ثالثة انواع رئيسيىة من برتكوالت ال
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
Link Layer
5-11
CHANNEL PARTITIONING MAC PROTOCOLS: TDMA
TDMA: time division multiple access
الوصول المتعدد باستخدام تقنية تقسيم زمن الوصول
. يصل فيها للقناة في كل دورةslots كل جهاز له فترة معينة
. غير المستخدمة تكون فيها الشبكة عاطلةslots عيبها ان ال
example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6
idle
6-slot
frame
6-slot
frame
1
3
4
1
3
4
Link Layer
5-12
CHANNEL PARTITIONING MAC PROTOCOLS: FDMA
FDMA: frequency division multiple access
FDM cable
frequency bands
الوصول المتعدد بتقسيم التردد
للقناة الى حزم من الترددات المختلفةspectrum يتم فيه تقسيم ال
. كل جهاز يتم تخصيص حزمة تردد معينة له
عيبها ان التردد غير المستخدم يصبح عاطل
example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6
idle
Link Layer
5-13
RANDOM ACCESS PROTOCOLS
عندما يريد جهاز ما ارسال رسالة فانه يقوم بارسال الرسالة
مباشرة عبر الشبكة حيث ال يوجد تنسيق بين االجهزة في
.االرسال
. R ميزتها انها تسمح للجهاز باالرسال بمعدل القناة الكامل
. Collision عيبها انه قد يحدث تصادم
random access MAC protocol specifies:
how to detect collisions
how to recover from collisions (e.g., via delayed
retransmissions)
examples of random access
slotted ALOHA
ALOHA
CSMA, CSMA/CD, CSMA/CA
MAC protocols:
Link Layer
5-14
)CSMA (CARRIER SENSE MULTIPLE ACCESS
الفكرة االساسية هي listen before transmitوهي تحسس
القناة قبل االرسال حيث انه اذا كانت القناة خالية قم باالرسال
بالمعدل الكامل للقناة ,اذا كانت القناة مشغولة أجل االرسال.
5-15
CSMA COLLISIONS
Link Layer
spatial layout of nodes
5-16
رغم عملية تحسس القناة اال
ان التصادم الزال يمكن ان
يحدث
تأخير ال propagation
يعني ان جهاز ما قد ال يسمع
ارسال جهاز آخر.
عند حدوث تصادم فان كل
البيانات التي تم ارسالها تكون
غير سليمة.
)CSMA/CD (COLLISION DETECTION
اكتشاف التصادم
CSMA/CD:
CSMA/CD تعمل بنفس طريقة CSMAلكن يتم اكتشاف التصادم
وعندها نكون قد قللنا نسبة البيانات التالفة.
يتم اكتشاف االخطاء بسهولة في الشبكات السلكية حيث يتم قياس
قوة االشارة ومقارنة االشارات المرسلة والمستقبلة.
difficult in wireless LANs: received signal strength
overwhelmed by local transmission strength
5-17
Link Layer
CSMA/CD (COLLISION DETECTION)
spatial layout of nodes
5-18
Link
Laye
r
ETHERNET CSMA/CD ALGORITHM
1. NIC(Network Interface
4. If NIC detects another
Card) receives datagram
transmission while
from network layer,
transmitting, aborts and
creates frame
sends jam signal
2. If NIC senses channel idle,
starts frame transmission.
If NIC senses channel busy,
waits until channel idle,
then transmits.
3. If NIC transmits entire
frame without detecting
another transmission, NIC
5-19
is done with frame !
“TAKING TURNS” MAC PROTOCOLS
channel partitioning MAC protocols:
share channel efficiently and fairly 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
“taking turns” protocols
look for best of both worlds!
Link Layer
5-20
“TAKING TURNS” MAC PROTOCOLS
polling:
تدعو الmaster node ال
الرسالslave nodes
.بياناتهم حسب الترتيب
data
poll
master
Concerns )(عيوبها:
polling overhead
latency
single point of failure
(master)
data
slaves
Link Layer
5-21
“TAKING TURNS” MAC PROTOCOLS
token passing:
في هذه الطريقة ال توجد
. master node
يتم تمريرها من جهازtoken توجد
.لجهاز بترتيب معين
token التي معها الnode ال
.يمكنها ارسال البيانات
T
(nothing
to send)
T
Concerns عيوبها:
token overhead
latency
single point of failure
(token)
data
Link Layer
5-22
SUMMARY OF MAC PROTOCOLS
channel
partitioning, by time, frequency or code
Time Division, Frequency Division
random
access (dynamic),
ALOHA, S-ALOHA, CSMA, CSMA/CD
carrier sensing: easy in some technologies (wire), hard
in others (wireless)
CSMA/CD used in Ethernet
CSMA/CA used in 802.11
taking
turns
polling from central site, token passing
bluetooth, FDDI, token ring
5-23
MAC ADDRESSES AND ARP
32-bit IP address:
network-layer address for interface
used for layer 3 (network layer) forwarding
MAC (or LAN or physical or Ethernet) address:
function: used ‘locally” to get frame from one interface to another
physically-connected interface (same network, in IP-addressing
sense)
48 bit MAC address (for most LANs) burned in NIC ROM, also
sometimes software settable
e.g.: 1A-2F-BB-76-09-AD
hexadecimal (base 16) notation
(each “number” represents 4 bits)
Link Layer
5-24
MAC ADDRESSES AND ARP
each adapter on LAN has unique MAC address
1A-2F-BB-76-09-AD
LAN
(wired or
wireless)
adapter
71-65-F7-2B-08-53
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
Link Layer
5-25
)MAC ADDRESSES (MORE
أعطاء ال MAC addressيتم بواسطة . IEEE
اصحاب مصانع كروت الشبكة يقوموا بشراء عناوين MACمن . IEEE
يشبه الرقم الوطني MAC address:
يشبه رقم البريد IP address:
MAC flat address ➜ portability
يمكن ان تنتقل من شبكة الى شبكة اخرى بنفس عنوان ال . MAC
IP hierarchical address not portable
ال يمكن لشخص ان ينتقل من شبكة الخرى بنفس عنوان ال . IP
5-26
Link Layer
ARP: ADDRESS RESOLUTION PROTOCOL
Question: how to determine
interface’s MAC address,
knowing its IP address?
137.196.7.78
ARP table: each IP node (host,
router) on LAN has table
1A-2F-BB-76-09-AD
< IP address; MAC address; TTL>
137.196.7.23
137.196.7.14
LAN
71-65-F7-2B-08-53
IP/MAC address mappings
for some LAN nodes:
58-23-D7-FA-20-B0
TTL (Time To Live): time after
which address mapping will
be forgotten (typically 20
min)
0C-C4-11-6F-E3-98
137.196.7.88
Link Layer
5-27
ARP PROTOCOL: SAME LAN
A wants to send datagram to
B
A broadcasts ARP query
packet, containing B's IP
address
dest MAC address = FF-FF-FFFF-FF-FF
all nodes 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-to-MAC
address pair in its ARP
table until information
becomes old (times out)
Link Layer
B’s MAC address not in A’s
ARP table.
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
5-28
ADDRESSING: ROUTING TO ANOTHER LAN
walkthrough: send datagram from A to B via R
focus on addressing – at IP (datagram) and MAC layer (frame)
assume A knows B’s IP address
assume A knows IP address of first hop router, R (how?)
assume A knows R’s MAC address (how?)
B
A
R
111.111.111.111
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer
5-29
ADDRESSING: ROUTING TO ANOTHER LAN
A creates IP datagram with IP source A, destination B
A creates link-layer frame with R's MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
B
A
R
111.111.111.111
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer
5-30
ADDRESSING: ROUTING TO ANOTHER LAN
frame sent from A to R
frame received at R, datagram removed, passed up to IP
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
IP
Eth
Phy
B
A
R
111.111.111.111
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer
5-31
ADDRESSING: ROUTING TO ANOTHER LAN
R forwards datagram with IP source A, destination B
R creates link-layer frame with B's MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
IP
Eth
Phy
B
A
R
111.111.111.111
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer
5-32
ADDRESSING: ROUTING TO ANOTHER LAN
R forwards datagram with IP source A, destination B
R creates link-layer frame with B's MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
IP
Eth
Phy
B
A
R
111.111.111.111
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer
5-33
ADDRESSING: ROUTING TO ANOTHER LAN
R forwards datagram with IP source A, destination B
R creates link-layer frame with B's MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
B
A
R
111.111.111.111
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer
5-34
QUESTIONS
These slides are adapted
from Computer
Networking: A Top Down
Approach
Jim Kurose, Keith Ross
Addison-Wesley
March 2012