Transcript Chapter 1 - Introduction

Computer Networks and Internets, 5e
By Douglas E. Comer
Lecture PowerPoints
By Lami Kaya, [email protected]
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
1
Chapter 14
The IEEE MAC Sub-Layer
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
2
Topics Covered
•
•
•
•
•
•
14.1
14.2
14.3
14.4
14.5
14.6
Introduction
A Taxonomy of Mechanisms for Multi-Access
Static and Dynamic Channel Allocation
Channelization Protocols
Controlled Access Protocols
Random Access Protocols
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
3
14.1 Introduction
• This chapter
– continues the discussion by examining the IEEE's MAC sublayer
– explains multi-access protocols
– considers both static and dynamic channel allocation
• Later chapters in this part
– discuss specific networking technologies that use the access
mechanisms explained here
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
4
14.2 A Taxonomy of Mechanisms for
Multi-Access
• How do multiple, independent computers coordinate access
to a shared medium?
• There are three broad approaches:
– they can use a modified form of a multiplexing technique
– they can engage in a distributed algorithm for controlled access
– or they can use a random access strategy
• Figure 14.1 illustrates the taxonomy
– including specific forms of each approach
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
5
14.2 Çoklu-Erişim Mekanizmalarının
Karşılaştırılması
• Birbirinden bağımsız bilgisayarlar paylaşılan ortama nasıl
kordineli bir şekilde erişim sağlayacaktır?
• Üç tane geniş yaklaşım mevcuttur:
– Bunlar multiplexing tekniklerinin modifiye edilmiş formunu kullanır
– Dağınık algoritmalar kontollü şekilde erişim ile meşgul oluyorlar
– Bunlar rastgele erişim stratejisini kullanabilirler
• Şekil 14.1 bu karşılaştırmayı şekillendirilir
– Her yaklaşım için özel form içeriyor
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
6
Fig. 14.1
Çoklu-Erişim
Mekanizmalarının
Karşılaştırılması
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
7
14.3 Static and Dynamic Channel
Allocation
•
Channelization refers to a mapping between a given
communication and a channel in the underlying system
– There should be a mapping between entities and a channel is
referred to as 1-to-1 and static
– Static channel allocation works well for situations where the set of
communicating entities is known in advance and does not change
• In many networks, however, the set of entities using the
network varies over time
• As an example, consider cellular telephones in a city
– users move, and they can turn a cell phone on and off at any time
– thus, the set of cell phones that are operating in the range of a given
cell tower varies constantly
– A dynamic channel allocation scheme is needed; a mapping can be
established when a new station appears, and the mapping can be
removed when the station disappears
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
8
14.3 Static ve Dinamik Kanal tahsisat
• Kanal tahsisatı verilen iletişimin ve temelde (alt sistem) bulunan sistemin
kanallarıyla eşleşmesidir
– Varlıklar arasında eşleşme olmalıdır ve kanal 1-e-1 ve statik olarak
adlandırılır
– Statik kanal tahsisatı iletişim birimlerinin iyi bilinmesi ile ve değişmeden bir
yapıda olanları ile iyi çalışır
• Fakat çoğu ağda, ağın içerindeki birimlerin çoğu zaman içerisinde
farklılıklar göstermektedir
• Mesela, şehirde kullanılan hücresel telefonları ele alalım
– Kullanıcılar hareket eder, ve telefonlarını istedikeri zaman açar yada
kapatırlar
– Böylece, verilen aralıklarda çalışan hücresel telefonlar , hücresel kuleye göre
sabit birşekilde değişir
– Bunun için dinamik kanal tahsisat şeması gerekir, eşleşme yeni bir istasyon
belirdiğinde yapılır, ve istasyon kaybolduğunda eşleşme kaldırılır
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
9
14.4 Channelization Protocols
• Channelization protocols extend the multiplexing techniques
covered in Chapter 11
• Figure 14.2 (below) lists the main channelization techniques
• These schemes have been discussed in Chapter 11 in detail
– 14.4.1 FDMA
– 14.4.2 TDMA
– 14.4.3 CDMA
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
10
14.4 Kanal Açma Protokolleri
• Kanal Açma Protokolleri Bolüm 11’de anlatılan multiplexing
tekniklerinin genişletilmiş halidir
• Şekil 14.2 (Aşağıdaki) Kanal Açma tekniklerinin asıl listeleri
verilmiştir
• Bu şemalar Bölüm 11’den tartışılmıştır
– 14.4.1 FDMA
– 14.4.2 TDMA
– 14.4.3 CDMA
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
11
14.5 Controlled Access Protocols
• Controlled access protocols provide a distributed version of
statistical multiplexing
– Figure 14.3 (below) lists the three principal forms:
• These will be discussed in the following sub-sections
– 14.5.1 Polling
– 14.5.2 Reservation
– 14.5.3 Token Passing
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
12
14.5 Kontollü Erişim Protokolleri
• Kontrollü erişim protokolleri istatiksel multiplexing’in dağınık
versiyonunu sağlarlar
– Şekil 14.3 (aşağıdaki) en önemli üç prensiperini listelemektedir:
• Bunlarda aşağıdaki alt bölümde inceleneceklerdir
– 14.5.1 Polling (oylama)
– 14.5.2 Reservation (rezervasyon)
– 14.5.3 Token Passing (jeton geçişi)
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
13
14.5 Controlled Access Protocols
14.5.1 Polling
•
Polling uses a centralized controller
– which cycles through stations on the network and gives each an
opportunity to transmit a packet
• Algorithm 14.1 gives the steps a controller follows
• The selection step is significant because it means a
controller can choose which station to poll at a given time
• There are two general polling policies:
– Round robin order
• Round-robin means each station has an equal opportunity to transmit packets
– Priority order
• Priority order means some stations will have more opportunity to send
• For example, priority order might be used to assign an IP telephone higher
priority than a personal computer
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
14
14.5 Controlled Access Protocols
14.5.1 Polling
•
Polling merkezi düzenleyici kullanır
– Her döngüde bütün birimlere paket gönderme olanağı sağlar
• Algoritma 14.1 denetleyici adımların sırasını verir
• Seçim adımı önemlidir çünkü kontroller’a hangi birimin hangi
zaman aralığında paket göndereceğine karar verir
• İki Genel polling mekanizması mevcuttur:
– Round robin sırası
• Round-robin her birimin paket göndermek için eşit gönderim şansına sahiptir
– Priority order
• Öncelik sırası İstasyonların gönderimdeki önceliğini belirtir
• Mesela, IP telefonlarının öncelik sırası kişesel bilgisayarınkinden daha
yüksektir
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
15
14.5 Controlled Access Protocols
14.5.1 Polling (oylama)
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
16
14.5 Controlled Access Protocols
14.5.2 Reservation (rezervasyon )
• Genelde uydu iletişiminde kullanılır
• İki adımlık bir işlem gerektirir, her işlem paket iletimlerinin
detaylı bir şekilde planlamasını gerektirir
• Tipik olarak, rezervasyon sistemleri merkezi kontrolcüye
sahiptir ve buda aşağıdaki algoritmayı içerir
•
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
17
14.5 Controlled Access Protocols
14.5.2 Reservation
• In the first step
– each potential sender specifies whether they have a packet to send
during the next round, and the controller transmits a list of the
stations that will be transmitting
• In the second step
– stations use the list to know when they should transmit
• Variations exist
– where a controller uses an alternate channel to gather reservations
for the next round
• while the current round of transmissions proceeds over the main channel
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
18
14.5 Controlled Access Protocols
14.5.2 Reservation (rezervasyon )
• İlk adım
– Potansiyel göndericiler bir sonraki adımda veri gönderip
göndermeyeceklerini hesaplarlar, ve kontolcü gönderecek
birimlerin/istasyonların listesini gönderir
• İkinci adım
– Gönderilen listeyi alan birimler ne zaman göndereceklerini bilirler
• Değişiklikler mevcuttur
– Kontrolcü rezervasyonları almak için alternatif kanallar kullanır (her
adımda)
• Hali hazırdaki adımdaki iletimler asıl kanallar üzerinden alınır
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
19
14.5 Controlled Access Protocols
14.5.3 Token Passing
• It is most often associated with ring topologies
• Although older LANs used token passing ring technology
– popularity has decreased, and few token passing networks remain
• Imagine a set of computers connected in a ring
– and imagine that at any instant, exactly one of the computers has
received a special control message called a token
• When no station has any packets to send
– the token circulates among all stations continuously
• For a ring topology, the order of circulation is defined
– if messages are sent clockwise, the next station mentioned in the
algorithm refers to the next physical station in a clockwise order
• When token passing is applied to other topologies (bus)
– each station is assigned a position in a logical sequence
– and the token is passed according to the assigned sequence
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
20
14.5 Controlled Access Protocols
14.5.3 Token Passing (jeton geçişi)
• Genelde halka topolojisi ile birleştirilmiştir
• Eski LAN’larda token passing (jeton geçişi) halka teknolojisinde
kullanılıyor
– Popülerliği düşmüştür, ve az token passing ağları kalmıştır
• Bazı bilgisayarların halkaya bağlandığını hayal edin
– Ve tam olarak bir bilgisayar özel kontrol mesajı olan jeton (token)’a sahiptir
• Herhangi bir birimin gönderecek verisi olmadığı zaman
– Jeton bütün birimleri sürekli dolaşır
• Halka topolojisi için, dolaşma sırası tanımlanmıştır
– Eğer mesajlar saat yönüne doğru gönderilmişse, algoritmada bir sonraki
birim olarak adlandırılan diğer fiziksel birim, saat yönünü temsil eder
• Jeten geçişi diğer topolojilere uygulandığı zaman (bus)
– Her birim için mantıksa sıra (logical sequence) kararlaştırılır
– Ve jeton kararlaştırılan sıraya göre yerdeğiştirir
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
21
14.5 Controlled Access Protocols
14.5.3 Token Passing (jeton geçişi)
Kontollü ulaşımda her bilgisayar aşağıdaki algoritmayı kullanır
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
22
14.6 Random Access Protocols
• Some LANs do not employ a controlled access mechanism
– Instead, a set of computers attached to a shared medium attempt to
access the medium without coordination
• The term random is used because access only occurs when
a given station has a packet to send
– and randomization is employed to prevent all computers on a LAN
from attempting to use the medium at the same time
– the descriptions of specific methods below will clarify the use of
randomization
• Figure 14.4 lists the three random access methods that are
discussed
– 14.6.1 ALOHA
– 14.6.2 CSMA/CD
– 14.6.3 CSMA/CA
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
23
14.6 Random Access Protocols
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
24
14.6 Random Access Protocols
14.6.1 ALOHA
• An early network in Hawaii, known as ALOHAnet, pioneered
the concept of random access
– the network is no longer used, but the ideas have been extended
• The network consisted of a single powerful transmitter in a
central geographic location
– It is surrounded by a set of stations/computer
– Stations had a transmitter capable of reaching the central transmitter
• but not powerful enough to reach all the other stations
• ALOHAnet used two (2) carrier frequencies for broadcasting:
– one for outbound by the central transmitter to all stations
– and another for inbound by stations to the central transmitter
• Figure 14.5 illustration of outbound and inbound frequencies
in ALOHAnet
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
25
14.6 Random Access Protocols
14.6.1 ALOHA
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
26
14.6 Random Access Protocols
14.6.1 ALOHA
• The ALOHA protocol is straightforward:
– when a station has a packet to send
• it transmits the packet on the inbound frequency
– the central transmitter repeats the transmission on the outbound
frequency (which all stations can receive)
• To insure that transmission is successful
– a sending station listens to the outbound channel
• if a copy of its packet arrives, the sending station moves to the next packet
• if no copy arrives, the sending station waits a short time and tries again
• Why might a packet fail to arrive? Interference
– if two stations simultaneously transmit
• the signals will interfere and the two transmissions will be garbled
• called a collision, and say that the two transmitted packets collide
• The protocol handles a collision
– by requiring a sender to retransmit each lost packet
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
27
14.6 Random Access Protocols
14.6.2 CSMA/CD
• Researchers at Xerox PARC created a random access
protocol (1973)
– In 1978, a standard (also called the DIX standard) was created
• by Digital Equipment Corporation, Intel, and Xerox
– It is widely known as Ethernet
• It uses cable as a shared medium
– instead of broadcasting radio frequency transmissions through the
atmosphere
• Ethernet uses three (3) mechanisms to handle collisions:
– Carrier sense
– Collision detection
– Binary exponential backoff
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
28
14.6 Random Access Protocols
14.6.2 CSMA/CD
• Ethernet requires each station to monitor the cable to detect
whether another transmission is already in progress
– this process is known as carrier sense
– it prevents the most obvious collision problems
– and substantially improves network utilization
• A collision can occur if two stations wait for a transmission
to stop, find the cable idle, and both start transmitting
– A small part of the problem is that even at the speed of light, some
time is required for a signal to travel down the cable
– Thus, a station at one end of the cable cannot know instantly when a
station at the other end begins to transmit
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
29
14.6 Random Access Protocols
14.6.2 CSMA/CD
• To handle collisions
– each station monitors the cable during transmission
• If the signal on the cable differs from the signal that the
station is sending
– it means that a collision has occurred
– the technique is known as collision detection
– when a collision is detected, the sending station aborts transmission
• Many details complicate Ethernet transmission
– For example, following a collision, transmission does not abort until
enough bits have been sent to guarantee that the collided signals
reach all stations
– Furthermore, following a transmission, stations must wait for an
interpacket gap (9.6 sec for a 10 Mbps Ethernet) to insure that all
stations sense an idle network and have a chance to transmit
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
30
14.6 Random Access Protocols
14.6.2 CSMA/CD
• Binary Exponential Backoff
– After a collision occurs
• a computer must wait for the cable to become idle again before transmitting
a frame
– Randomization is used to avoid having multiple stations transmit
simultaneously as soon as the cable is idle
– The standard specifies a maximum delay, d, and requires each
station to choose a random delay less than d after a collision occurs
• When two stations each choose a random value
– the station that chooses the smallest delay will proceed to send a
packet and the network will return to normal operation
• In the case where two or more computers happen to choose
nearly the same amount of delay
– they will both begin to transmit at nearly the same time
– producing a second collision
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
31
14.6 Random Access Protocols
14.6.2 CSMA/CD
• To avoid a sequence of collisions
– Ethernet requires each computer to double the range from which a
delay is chosen after each collision
• a computer chooses a random delay between 0 - d after one collision
• a random delay between 0 - 2d after a second collision
• a random delay between 0 - 4d after a third, and so on
– After a few collisions, the range from which a random value is
chosen becomes large
• Thus, some computer will choose a random delay shorter than the others,
and will transmit without a collision
• Doubling the range of the random delay after each collision
is known as binary exponential backoff
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
32
14.6 Random Access Protocols
14.6.2 CSMA/CD
• By using exponential backoff
– an Ethernet can recover quickly after a collision
– because each computer agrees to wait longer times between
attempts when the cable becomes busy
• Even in the unlikely event that two or more computers
choose delays that are approximately equal
– exponential backoff guarantees that contention for the cable will be
reduced after a few collisions
• The combination of techniques described above is known by
the name Carrier Sense Multi-Access with Collision
Detection (CSMA/CD)
• Algorithm 14.4 summarizes CSMA/CD
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
33
14.6 Random Access Protocols
14.6.3 CSMA/CD
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
34
14.6 Random Access Protocols
14.6.3 CSMA/CA
• CSMA/CD does not work as well in wireless LANs
– because a transmitter used in a wireless LAN has a limited range
• A receiver that is more δ than away from the transmitter
– will not receive a signal, and will not be able to detect a carrier
• Consider three computers with wireless LAN hardware
positioned as Figure 14.6 (below) illustrates
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
35
14.6 Random Access Protocols
14.6.3 CSMA/CA
• In Figure 14.6, computer1 can communicate with
computer2, but cannot receive the signal from computer3
– Thus, if computer3 is transmitting a packet to computer2,
computer1's carrier sense mechanism will not detect the
transmission
– Similarly, if computer1 and computer3 simultaneously transmit, only
computer2 will detect a collision
• The problem is sometimes called the hidden station problem
– because some stations are not visible to others
• Wireless LANs use a modified access protocol
– known as CSMA with Collision Avoidance (CSMA/CA)
• The CSMA/CA triggers a brief transmission from the
intended receiver before transmitting a packet
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
36
14.6 Random Access Protocols
14.6.3 CSMA/CA
• The idea is that if both the sender and receiver transmit a
message
– all computers within range of either will know a packet transmission
is beginning
• Figure 14.7 (below) illustrates the sequence
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
37
14.6 Random Access Protocols
14.6.3 CSMA/CA
• In Figure 14.7
– computer3 sends a short message to announce that it is ready to
transmit a packet to computer2
– and computer2 responds by sending a short message announcing
that it is ready to receive the packet
– all computers in range of computer3 receive the initial announcement
– and all computers in the range of computer2 receive the response
– as a result, even though it cannot receive the signal or sense a
carrier, computer1 knows that a packet transmission is taking place
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
38
14.6 Random Access Protocols
14.6.3 CSMA/CA
• Collisions of control messages can occur when using
CSMA/CA, but they can be handled easily
• For example, if computer1 and computer3 each attempt to
transmit a packet to computer2 at exactly the same time
– their control messages will collide
– When a collision occurs, the sending stations apply random backoff
before resending the control messages.
• Because control messages are much shorter than a packet,
the probability of a second collision is low
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
39