Veri İletişimi Veri
İletişimi
Data Communications
Suat ÖZDEMİR
Suat
ÖZDEMİR
Gazi Üniversitesi Bilgisayar Mühendisliği Bölümü
12. Çoklu Erişim
Çoklu Erişim
Çoklu Erişim
• İletişimde bulunan uç noktalar arasında her ş
ç
zaman atanmış bir kanal bulunmayabilir
– Cep telefonu • Data link katmanı 2 alt katmandan oluşur
– Atanmış kanal varsa alttaki katman kullanılmaz
– IEEE LAN Logical Link Layer (LLC) ve Medium Access Layer (MAC)
http://ceng.gazi.edu.tr/~ozdemir/
Çoklu Erişim
Çoklu Erişim
• Çoklu ortam erişim protokolleri 3 ana g y y
kategoriye ayrılır http://ceng.gazi.edu.tr/~ozdemir/
Rastgele Erişim
Rastgele Erişim
• R
Rastgele erişim yada yarışma metotlarında bütün t l
ii
d
t tl
d bütü
düğümler eşittir. Hiçbir düğüm bir diğerini kontrol etmez yada öncelik
• Hiçbir düğüm bir diğerini kontrol etmez yada öncelik sağlamaz
• İletim ortamının boş yada dolu olmasına göre her şy
g
düğüm karar verir
• İki nedenden dolayı rastgele adı verilmiştir
– Gönderme işlemi için her hangi bir zamanlama d
l
h h
b
l
mekanizması yoktur
– Hangi düğümün göndereceğini belirleyen kural yoktur, Hangi düğümün göndereceğini belirleyen kural yoktur,
düğümler iletim ortamı için yarışırlar
• Yarışma tabanlı metot da denilir
http://ceng.gazi.edu.tr/~ozdemir/
Rastgele Erişim
Rastgele Erişim
• Hi
Hiçbir düğüm diğerine karşı üstün değildir
bi düğü diğ i k
ü tü d ğildi
• Birden çok düğüm aynı anda iletim ortamını kullanırsa erişim çatışması
çatışması” yani çakışma olur ve frame
yani çakışma olur ve frame ler tekrar tekrar
“erişim
gönderilmek zorundadır
• Erişim çatışmalarını (çakışmaları) engellemek ya da ş ç ş
(ç ş
) g
y
oluştuğu zaman çözmek için aşağıdaki sorular cevaplamalıdır
– Düğüm
Düğüm ortama ne zaman erişebilir
ortama ne zaman erişebilir
– Ortam meşgulse ne yapılabilir
– Düğüm iletimin başarılı yada başarısız olduğunu nasıl ğ
ş
y
ş
ğ
anlayabilir
– Erişim çatışması varsa düğüm ne yapar
http://ceng.gazi.edu.tr/~ozdemir/
ALOHA
• R
Rastgele erişim metotları ALOHA adlı protokolden t l
ii
t tl ALOHA dl
t k ld
türetilmişlerdir
• ALOHA çoklu erişim sağlayan basit bir protokoldür
ALOHA çoklu erişim sağlayan basit bir protokoldür
• ALOHA daha sonra iletişimden önce iletim ortamının dinlenmesi işlemi ile geliştirilmiştir
ortamının dinlenmesi işlemi ile geliştirilmiştir
• Buna “carrier sense multiple access” adı verilir
• Daha sonra “carrier sense multiple access with D h
“
i
lti l
ith
collision detection (CSMA/CD)” ve “carrier sense multiple access with collision avoidance
multiple access with collision avoidance (CSMA/CA)” protokolleri ortaya çıkmıştır
http://ceng.gazi.edu.tr/~ozdemir/
ALOHA
• En eski rastgele ortam erişimi protokolü olan y
ALOHA 1970 lerde University of Hawaii’de geliştirilmiştir. • Kablosuz LAN için geliştirilmiştir
Kablosuz LAN için geliştirilmiştir
• Tüm paylaşımlı ortamlarda kullanılabilir
• Paylaşımlı ortamlarda birden fazla düğüm iletişim yaparken çakışma olma olasılığı her
iletişim yaparken çakışma olma olasılığı her zaman vardır
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• Orjinal ALOHA protokolü Orjinal ALOHA protokolü “Pure
Pure ALOHA
ALOHA” olarak bilinir
olarak bilinir
• Bir düğüm frame i olduğu zaman gönderir
• Paylaşımlı kanal olduğu için çakışma olabilir Paylaşımlı kanal olduğu için çakışma olabilir
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• ŞŞekilde iletim ortamını kullanmak için “yarışan” 4 kild il i
k ll
ki i “
”
düğüm vardır.
• Her düğüm 2 frame gönderir, iletim ortamında 8 frame vardır • Çakışmalar olur ve sadece 2 frame hedefe ulaşabilir: Frame 1.1 ve Frame 3.2 • Kanal üzerinde aynı anda farklı frame lerden birer ç ş
bit bile olsa çakışma vardır ve frame ler bozulur
• Bozulan framelerin tekrar gönderilmesi gerekir http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• P
Pure ALOHA alıcıdan gönderilen ACK ları kullanır
ALOHA l d
ö d il ACK l k ll
• Bir frame gönderildiğinde alıcıdan ACK beklenir
• Belli bir zaman aralığında alıcıdan ACK gelmezse, gönderici Belli bir zaman aralığında alıcıdan ACK gelmezse gönderici
frame in ya da ACK nın çakıştığını kabul eder ve frame i yeniden gönderir
• Eğer tüm düğümler frame lerini aynı anda tekrar gönderirse Eğ ü düğü l f
l i i
d
k
ö d i
yeniden çakışma olur
• Pure ALOHA her düğümün yeniden gönderim yapmadan Pure ALOHA her düğümün yeniden gönderim yapmadan
önce “rastgele” bir zaman dilimi beklemesini gerektirir • Rastgelelik tekrar çakışma olma olasılığını azaltır
• Bu zaman dilimi “Back‐off time (TB)” olarak adlandırılır
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• Pure ALOHA’nın kanalda tıkanıklığı önlemek ç
için ikinci bir metodu vardır
• Belli sayıdaki (Kmax) frame tekrar gönderiminden sonra düğüm gönderme
gönderiminden sonra düğüm gönderme işlemini bırakmalı ve sonra tekrar denemelidir
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• TB formülü yg
y
uygulamaya göre değişir • En çok En çok
kullanılan binary exponential back‐off http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA Örnek
Pure ALOHA ‐
• K
Kablosuz
bl
bi ALOHA ağında
bir
ğ d düğümler
düğü l birbirlerinden
bi bi l i d 600 km
k
mesafe uzaklıktadır. Sinyal hızı 3 × 108 m/s olduğuna göre
maximum propagation time
Tp = (600 × 105 ) / (3 × 108 ) = 2 ms.
olur. Değişik K değerleri için TB yi hesaplayalım
• K=1.
K 1 Düğüm
Düğü {0,1}
{0 1} aralığında
l ğ d rastgele
l bir
bi sayı üretir.
ü i Bu
B
durumda TB ya 0 ms (0 × 2) yada 2 ms (1×2) olur.
• K
K=2.
2. Aralık {0,1,2,3} dır. Üretilen rastgele sayıya göre TB 0, 2,
4, yada 6 ms olabilir.
• K=3. Aralık {0,1,2,3,4,5,6,7} dır. Üretilen rastgele sayıya göre
TB 0,
0 2,
2 4,6,.....14
46
14 ms olabilir.
l bili
• K > 10 ise genelde değeri K=10 olarak alınır
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• Çakışmanın olabileceği “vulnerable time” (hassas zaman) tanımlanabilir tanımlanabilir
• Her düğüm sabit uzunlukta frame ler gönderir • Her frame in gönderme süres Tfr dir
• Şekilde A düğümü için vulnerable time gösterilmiştir
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• A
A düğümü t zamanında bir frame gönderir düğü ü
d bi f
ö d i
• B düğümüde t‐Tfr zaman aralığında bir frame göndermiş olsun l
• A ve B nin frameleri arasında bir çakışma olacaktır
• C düğümde t+T
d ğ d
lğ d b f
d
fr zaman aralığında bir frame göndersin
• A ve C nin frameleri arasında da bir çakışma olacaktır
• Bu durumda pure ALOHA da vulnerable time frame iletim zamanın iki katıdır
Pure ALOHA vulnerable time = 2 x Tfr http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA Örnek
Pure ALOHA ‐
• Bir pure ALOHA ağı 200 kbps’lik bir kanala g
y Ç
Çakışma ş
200‐bit’lik frame’ler gönderiyor.
olmaması için gerekli olan zaman nedir?
• Ortalama frame (transmission time) iletim frame (transmission time) iletim
zamanı Tfr=200 bits/200 kbps=1 ms.
• Vulnerable time = 2 x 1 ms =2 ms.
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA
Pure ALOHA
• Throughput
h
h
analizi
li i
• G bir frame iletim zamanı içinde sistem ç
tarafından üretilen ortalama frame sayısı • Pure ALOHA da ortalama başarılı iletim sayısı S Pure ALOHA da ortalama başarılı iletim sayısı S
= G x e‐2G dir
• G=1/2 için maximum throughput
G 1/2 için maximum throughput Smax =0.184. 0 184
• 2 frame iletim zamanı içinde 1 frame üretilirse, bu framelerden %18.4’ü başarılı olarak hedefe ulaşır.
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA Örnek
Pure ALOHA ‐
• Bir pure ALOHA ağı 200 kbps’lik bir kanala
y
Aşağıdaki
ş ğ
200‐bit’lik frame’ler ggönderiyor.
sistem (bütün düğümler tarafından üretilen)
frame üretim değerleri için throughput nedir.
nedir
a) 1000 frames per second
b) 500 frames
f
per second
d
c) 250 frames per second
http://ceng.gazi.edu.tr/~ozdemir/
Pure ALOHA ‐ Örnek
• Frame transmission time=200/200 kbps=1 ms.
a) 1000 frames per second=1 frame per millisecond.
• G=1 ve S=G×e−2G = 0.135 (%13.5).
• Throughput = 1000×0.135=135 frames. 1000 frame den
sadece 135 tanesi hedefe ulaşır
b) 500 frames per second = 1/2 frame per millisecond.
millisecond
• G=1/2 ve S=G×e−2G = 0.184 (%18.4).
• Throughput = 500×0.184
500×0 184 = 92 frame.
frame 500 frame den
sadece 92 tanesi hedefe ulaşır
c) 250 frames per second = 1/4 frame per millisecond.
• G=1/4 ve S=G×e−2G = 0.152 (%15.2).
• Throughput
g p = 250×0.152 = 32 frame. 250 frame den
sadece 32 tanesi hedefe ulaşır
http://ceng.gazi.edu.tr/~ozdemir/
Slotted ALOHA
Slotted ALOHA
• P
Pure ALOHA nın
ALOHA
vulnerable time’ı 2 x T
l
bl ti ’ 2 Tfr . • Düğümün ne zaman göndereceğini belirleyen bir kural olmamasındandır
• Bir frame gönderildikten az önce yada az sonra başka bir frame gönderilmiş olabilir
g
ş
• Slotted ALOHA pure ALOHA’nın verimliliğini artırmak için ortaya çıkmıştır.
• Slotted ALOHA zamanı Tfr slotlarına bölünür ve düğümler bir slot un başında frame göndermeye zorlanır. zorlanır
• Şekil slotted ALOHAdaki frame çakışmalarını gösterir
http://ceng.gazi.edu.tr/~ozdemir/
Slotted ALOHA
http://ceng.gazi.edu.tr/~ozdemir/
Slotted ALOHA
• Bir düğüm sadece slot başında frame
g
gönderebilir
• Bu anı kaçırırsa bir sonraki slot ı beklemek zorundadır zorundadır
• İki düğüm aynı slot ın başında göndermeye başlarsa çakışma olur
• Ancak vulnerable time yarıya düşer (T
Ancak vulnerable time yarıya düşer (Tfr)
http://ceng.gazi.edu.tr/~ozdemir/
Slotted ALOHA
http://ceng.gazi.edu.tr/~ozdemir/
Slotted ALOHA
• Throughput
h
h
analizi
li i
• G bir frame iletim zamanı içinde sistem ç
tarafından üretilen ortalama frame sayısı • Slotted ALOHA da ortalama başarılı iletim ALOHA da ortalama başarılı iletim
sayısı S = G x e‐G dir
• G=1 için maximum throughput
G 1 için maximum throughput Smax =0.368. 0 368
• 1 frame iletim zamanı içinde 1 frame üretilirse, bu framelerden %36.8’i başarılı olarak hedefe ulaşır.
http://ceng.gazi.edu.tr/~ozdemir/
Slotted ALOHA ‐Örnek
ALOHA Örnek
• Bir slotted ALOHA ağı 200 kbps’lik bir kanala
y
Aşağıdaki
ş ğ
200‐bit’lik frame’ler ggönderiyor.
sistem (bütün düğümler tarafından üretilen)
frame üretim değerleri için throughput nedir.
nedir
a) 1000 frames per second
b) 500 frames
f
per second
d
c) 250 frames per second
http://ceng.gazi.edu.tr/~ozdemir/
Slotted ALOHA ‐Örnek
ALOHA Örnek
• Frame
F
t
transmission
i i time=200/200
ti
200/200 kbps=1
kb 1 ms.
a) 1000 frames per second=1 frame per millisecond.
• G=1
G 1 ve SS=G×e
G×e−G = 0.368 (%36.8).
• Throughput = 1000×0.368=368 frames. 1000 frame den sadece
368 tanesi hedefe ulaşır
b) 500 frames per second = 1/2 frame per millisecond.
millisecond
• G=1/2 ve S=G×e−G = 0.303 (%30.3).
• Throughput
g p = 500×0.303 = 151 frame. 500 frame den sadece
151 tanesi hedefe ulaşır
c) 250 frames per second = 1/4 frame per millisecond.
• G=1/4 ve S=G×e−GG = 0.195
0 195 (%19.5).
(%19 5)
• Throughput = 250×0.195 = 49 frame. 250 frame den sadece 49
tanesi hedefe ulaşır
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
• Ç
Çakışma olasılığını azaltmak ve performansı k
l lğ
l
k
f
artırmak için CSMA protokolü geliştirilmiştir. • Her düğüm kullanmadan önce iletim ortamını dinlerse çakışma olasılığı düşer
• CSMA de "sense before transmit" yada "listen before talk“ prensibine dayanır
• CSMA çakışma olasılığını düşürür ancak y
önleyemez
• Şekilde CSMA in time‐space modeli verilmiştir.
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
• Ç
Çakışma ihtimali propagation
ş
p p g
delayy nedeniyle hala vardır
y
– Bir düğüm frame gönderdiği zaman, ilk bitin diğer tüm düğümlere ulaşması için geçen zaman (çok kısa) – Diğer düğümler ancak o zaman iletim ortamının dolu olduğunu Diğer düğümler ancak o zaman iletim ortamının dolu olduğunu
anlar • Bir başka düğüm bu kısa aralıkta frame göndermeye b l bili
başlayabilir
• t1 anında B düğümü iletim ortamını boş bulur ve g
göndermeye başlar
y
ş
• t2 (t2> t1) anında C düğümü iletim ortamını boş bulur çünkü B düğümünün gönderdiği frame’in ilk biti C’ye henüz ulaşmamıştır
• C düğümü de göndermeye başlar • İki sinyal çakışır ve frame
İki sinyal çakışır ve frame’ler
ler bozulur
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
• CSMA için vulnerable
ç
time p
propagation time T
p g
ye eşittir. Bu ş
py
aralıkta bir başka düğümde frame gönderirse çakışma olur
• Şekilde worst case senaryo verilmiştir. A düğümü t1 anında D düğümüne frame gönderir
D düğümüne frame
• Gri alan vulnerable time’i gösterir http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
• Persistence Methods / ısrar metotları
• Ortamı meşgul yada boş bulan bir düğümün Ortamı meşgul yada boş bulan bir düğümün
yapması gerekenler için 3 metot geliştirilmiştir.
– 1‐persistent
1
i t t metot
t t
– nonpersistent metot
– p‐persistent metot
• Şekilde
Şekilde kanal dolu olduğunda 3 metodunda kanal dolu olduğunda 3 metodunda
nasıl çalıştığı gösterilmiştir
http://ceng.gazi.edu.tr/~ozdemir/
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
• 1‐Persistent oldukça basit bir metottur • Bir düğüm iletim ortamını boş bulur bulmaz Bir düğüm iletim ortamını boş bulur bulmaz
“1” olasılıkla frame gönderir
• Çakışma olma olasılığı oldukça yüksektir
Ç k
l
l l ğ ld k
ük k i
• İki düğüm aynı kanalı boş bulup frame
ğ
y
ş
p
gönderebilir
• Ethernet protokolü bu metodu kullanır
Eth
t
t k lü b
t d k ll
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
• Nonpersistent
i
metotta iletim ortamı boşsa il i
b
düğüm frame i hemen gönderir
• Eğer iletim ortamı doluysa rastgele bir zaman dilimi bekler ve iletim ortamını dinler • Nonpersistent yaklaşım çakışma olasılığını azaltılır • İki düğümün eşit zaman dilimi kadar bekleyip aynı İki düğümün eşit zaman dilimi kadar bekleyip aynı
anda gönderme olasılığı azdır • Ancak verimlilik boş geçen bekleme Ancak verimlilik boş geçen bekleme
zamanlarından dolayı düşüktür
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
• p‐Persistent metot kanal maximum propagation time
P it t
t tk
l
i
ti ti
a eşit it
yada büyük zaman dilimlerine (slot) ayrılmışsa kullanılabilir
• p‐persistent yaklaşım iki yaklaşımın avantajlarını birleştirir
pp
y
ş
y
ş
j
ş
• Çakışma olasılığını düşürür ve verimi artırır • İletim ortamı boş bulunduğunda şu işlemler yapılır • 1. p olasılıkla düğüm frame i gönderir
• 2. q = 1 – p olasılıkla düğüm bir sonraki slot ın başlangıç zamanını bekler ve iletim ortamını tekrar dinler
zamanını bekler ve iletim ortamını tekrar dinler
– a. Eğer iletim ortamı boş ise 1. basamağa gidilir
– b. Eğer iletim ortamı dolu ise, çakışma olduğunu varsayar ve backoff yapar
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA)
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access with Collision Detection (CSMA/CD)
• CSMA çakışma olma durumundan sonrası için p
bir prosedür tanımlamaz
• CSMA/CD çakışma sonrasını düşünür
– Frame
F
b
başarısız olmuşsa tekrar gönderilir
l
t k
ö d ili
• Çakışan ilk bitin durumuna göre hareket edilir
• Çakışma anlaşıldığı anda gönderim durdurulur
– Şekilde C t
Şekilde C t3 anında A t
anında A t4 anında göndermeyi bırakır
anında göndermeyi bırakır
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CD
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CD
• Frame boyutu için bir üst sınıra ihtiyaç vardır • Son bit gönderilene kadar çakışma tespit Son bit gönderilene kadar çakışma tespit
edilmelidir – Aksi takdirde frame
Ak i t kdi d f
d
de çakışma olduğu tespit k
ld ğ t it
edilemez • Frame iletim zamanı Tfr maximum propagation
zamanı Tp nin en az 2 katı olmalıdır
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CD
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CD ‐ Örnek
• CSMA/CD kullanan bir ağın 10 Mbps
/ k ll
bi ğ
b
bantgenişliği var. Eğer maximum propagation time 25.6 μs ise en küçük frame boyutu nedir?
• Frame transmission time Tfr = 2 × Tp = 51.2 μs. μ
Worst case’de, bir düğüm çakışmayı detect
ç
μ transmit etmelidir. edebilmek için 51.2 μs
Frame in en küçük boyutu 10 Mbps × 51.2 μs = 512 bits yada 64 byte
512 bits yada
64 byte olur. (The minimum size olur. (The minimum size
of the frame for Standard Ethernet.)
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CD
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CD
• Çakışma enerji seviyesindeki değişim ile ş
anlaşılır
http://ceng.gazi.edu.tr/~ozdemir/
Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)
• CSMA/CD nin ana fikri bir istasyonun g
gönderim yaparken aynı zamanda y p
y
dinleyebilmesidir • Kablosuz ortamda sinyal seviyesi ile Kablosuz ortamda sinyal seviyesi ile
çakışmanın tespiti zordur – Enerji gönderim sırasında kaybolur
• Çakışmanın engellenmesi gerekir Çakışmanın engellenmesi gerekir
• CSMA/CA bu amaç için geliştirilmiştir
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CA
• Interframe space (IFS), yarışma penceresi ve (IFS) yarışma penceresi ve
ACK
• Kanal boş bile olsa IFS kadar beklenir
lb bl l
k d b kl
• IFS sonunda kanal boş ise yine contention
ş
y
window kadar beklenir
• IFS öncelik planlaması için kullanılabilir.
IFS ö lik l l
i i k ll l bili
http://ceng.gazi.edu.tr/~ozdemir/
CSMA/CA
http://ceng.gazi.edu.tr/~ozdemir/
Download

masa tenisi final müsabakaları