当前位置：网站首页>[network planning] Chapter 3 data link layer (3) channel division medium access control

Point to point link ： Two adjacent nodes are connected by a link , There is no third party . application ：PPP agreement , Commonly used in Wide area network .

Broadcast link ： All hosts share communication media . application ： Early bus Ethernet 、 WLAN , Commonly used in LAN . Typical topology ： Bus type 、 Star type （ Logic bus type ）

* Broadcast links, such as interphones, talk to each other , But how to solve it A,B Two interphones talk at the same time ？ This requires media access control

Two 、 Media access control

Media access control The content of is , Take certain measures , So that the communication between two pairs of nodes will not interfere with each other .

* Static channel division refers to the division of channels before starting communication , Dynamic channel allocation refers to dealing with conflicts in the communication process .frequency、time、wave、code.

3、 ... and 、 Channel partition media access control

Channel partition media access control ： Connect each device that uses the media with data from other devices on the same channel Communication is separated , hold Time domain and frequency domain resources Reasonably allocated to devices on the network .

Multiplexing technology ： Multiple signals are combined on a physical channel for transmission , Make multiple computers or terminal devices Sharing information resources , Improve channel utilization . Put a broadcast channel , Logically, it is divided into several non-interference subchannels for communication between two nodes , The actual is Convert broadcast channels into point-to-point channels .

（1） Frequency division multiplexing FDM

After the user is allocated to a certain frequency band , This band is occupied throughout the communication process . All users of frequency division multiplexing occupy different bandwidth at the same time （ Frequency bandwidth ） resources .

advantage ： Make full use of transmission media bandwidth , System More efficient ; Due to the mature technology , The implementation is also relatively Easy to .

（2） Time division multiplexing TDM

Time is divided into a period of time-division multiplexing frame of equal length （TDM frame ）. Every time division multiplexing user in every TDM Occupied in the frame Time slot with fixed serial number , All users occupy the channel in turn .

Frequency division multiplexing is similar to that in the operating system “ parallel ”, Time division multiplexing is similar to “ Concurrent ”.

（3） Improved time division multiplexing —— Statistical time division multiplexing STDM

every last STDM The number of time slots in the frame is less than the number of users connected to the concentrator . Each user can send data to the concentrator at any time Input cache , The concentrator then scans the input cache sequentially , Put the input data from the cache into STDM In the frame , One STDM When the frame is full, it sends out .STDM The frame is not a fixed allocation slot , But when it is dynamically allocated on demand gap .

* It's like residents of four units in a building go downstairs to do nucleic acid , Accounting test location no matter which unit you are , Just make it up 10 personal （STDM The frame is full ） You can form a group . It can happen that multiple residents in a row are all in the same unit .

（4） Wavelength division multiplexing WDM

Wavelength division multiplexing is Optical frequency division multiplexing , Transmit multiple different wavelengths in one optical fiber （ frequency ） Optical signal , Due to the wavelength （ frequency ） Different , Therefore, all optical signals do not interfere with each other , Finally, each wavelength is decomposed by wavelength demultiplexer .

（5） Code division multiplexing CDM

Twist the data sent by two sending ends together on the same transmission channel , Separate these data at the receiving end .

So what's going on C End separation A、B What about the data? ？

Code division multiple access （CDMA） Is a way of code division multiplexing .1 A bit is divided into multiple chips / chip （chip）, Each site is assigned a unique m Bit Chip sequence , send out 1 Send chip sequence when （ Usually put 0 It's written in -1）.

send out 1 When the station sends the chip sequence , send out 0 Time send Chip sequence inversion .

3.5-2 ALOHA agreement

One 、 Dynamically allocate channels

Media access control is an access control applied in broadcasting , Only one sender can send messages at a time .“ Static division channel ” It is to time the channel in advance before the user communicates 、 Space division ;

“ Dynamically allocate channels ” Also known as “ Dynamic media access control / Multipoint access ”, Characteristic is ： The channel is not fixedly assigned to the user during user communication .

“ Dynamically allocate channels ” Medium “ Random access media access control ” in , All users can send messages randomly , When sending information, it takes up all the bandwidth .

Two 、ALOHA agreement

（1）（ pure ）ALOHA agreement

* Norm Abramson When traveling in Hawaii, in order to solve the problem of communication , Created ALOHA agreement ,ALOHA Local greetings for Hawaiians .

pure ALOHA The idea of agreement ： Do not listen to the channel , Do not send by time slot , Random resend . Send if you want .

* “ It's better to catch up early than skillfully ” agreement , Very casual , It can be seen that this scholar is having a good holiday

$T_{0}$ It refers to the transmission length of a data frame in $T_{0}$ To measure , The time from the beginning of sending a frame to the success of sending .

Each sending station may encounter conflict when sending data frames , So how to detect conflicts ？

—— If there is a conflict , The receiver will detect an error , Then do not confirm or NAK Negative confirmation frame , The sender cannot receive the confirmation within a certain time （ Overtime ）, Just judge that there is a conflict .

How to resolve the conflict ？

—— Wait a random time after timeout before retransmission .

（2） Timeslot ALOHA agreement

Timeslot ALOHA The idea of agreement ： Divide the time into several identical time slices , All users access the network channel synchronously at the beginning of time , In case of conflict , You must wait until the start of the next time slice . Control the randomness of sending whenever you want .

* The time slice division of different sending stations may be different , And there may be an optimization algorithm after the conflict （？） To send the next frame

3、 ... and 、 summary

1. pure ALOHA Protocol is better than time slot ALOHA Lower protocol throughput , Less efficient ;

2. pure ALOHA Send the agreement if you want , Timeslot ALOHA The agreement can only be sent at the beginning of the time segment ;

3.5-3 CSMA agreement

One 、CSMA agreement

Carrier sense multiple access protocol （carrier sense multiple access）

CS（carrier sense）： carrier sense / monitor , Before sending data, each station should check whether there are other computers on the bus sending data .

Test method ：

When several stations send data on the bus at the same time , Signal on bus Voltage swing value Will increase （ Superimpose on each other ）. When the signal voltage swing value detected by a station exceeds a certain threshold , It is considered that at least two stations on the bus are sending data at the same time , Indicates a collision , There was a conflict .

Threshold is a general term , Indicates that this value is the critical point , If a parameter exceeds the threshold value, it will cause a sharp change in a corresponding property .
Threshold effect _ Baidu Encyclopedia English name ：Threshold Effect The so-called threshold effect , That is, when the input signal-to-noise ratio of the envelope detector is reduced to a specific value , A phenomenon that the output signal-to-noise ratio of the detector decreases sharply . The input signal-to-noise ratio that begins to appear threshold effect is called threshold . This threshold effect is caused by the nonlinear demodulation of the envelope detector . In the case of small signal-to-noise ratio , Modulated signals cannot be separated from noise , And useful signals are submerged in noise , At this time, the output signal-to-noise ratio of the detector does not decrease proportionally with the input signal-to-noise ratio , It's a sharp deterioration , That is, there is a threshold effect .https://baike.baidu.com/item/%E9%97%A8%E9%99%90%E6%95%88%E5%BA%94

MA（multiple access）： Multipoint access , It means that many computers are connected to a bus by means of multi-point access .

The idea of agreement ： Before sending frame , Monitoring channels .

（1）1- insist CSMA

Persistence refers to the monitoring channel busy Later persistence .

1- insist CSMA thought ： If a host wants to send a message , Then it listens to the channel first .

When idle, it is transmitted directly , Don't wait for .

Keep listening when you're busy , Transfer until idle .

If there is a conflict （ No positive reply has been received for a period of time ）, Then wait a random long time before listening , Repeat the process .

advantage ： As long as the media is free , The site will send it right away , Avoid the loss of media utilization .

shortcoming ： If two or more sites have data to send , Conflict is inevitable .

（2） Non insistence CSMA

Non persistence refers to the monitoring channel busy Then stop listening .

Non insistence CSMA thought ： If a host wants to send a message , Then it listens to the channel first .

When idle, it is transmitted directly , Don't wait for .

Busy, wait for a random time before listening .

advantage ： Using random retransmission delay time can reduce the possibility of conflict .

shortcoming ： It may be that everyone is in the process of delaying waiting , Make it possible for the media to remain idle , Low media usage .

（3）p- insist CSMA

Applied to slot channels . If p=1, Be similar to 1- insist CSMA, and p=0 when , And non persistence CSMA Different .

p- Persistence refers to the monitoring channel Free To deal with .

p- insist CSMA thought ： If a host wants to send a message , Then it listens to the channel first .

When you are free, use p Probability direct transmission , Don't wait for ; probability 1-p Wait until the next time slot before transmitting .

If busy, continue to listen until the channel is idle, and then continue to listen with p Probability transmission .

In case of conflict, wait until the next time slot starts to listen and repeat the above process .

advantage ： It can reduce conflicts like non persistent algorithms , There's something like 1- Stick to the algorithm to reduce media idle time .

shortcoming ： After a conflict occurs, the sender still insists on sending the data frame , It's a waste .

* How to solve this phenomenon , Once there is a conflict, you can find , Stop sending data ？——CSMA/CD agreement

Two 、 Three CSMA contrast

1- insist CSMA

Non insistence CSMA

p- insist CSMA

Channel free

Send immediately

p The probability will be sent immediately

1-p Probability wait until the next slot

The channel is busy

Keep listening

Give up listening , Wait a random time before listening

Continuous monitoring , Wait until the channel is free p Probability transmission

3.4-5 CSMA/CD agreement

One 、CSMA/CD agreement

* Listen first , When you hear someone talking, you stop talking

Carrier monitoring multipoint access / collision detection CSMA/CD （carrier sense multiple access with collision detection）

CS： Carrier sense / monitor , Every site is in Before sending data as well as When sending data Check whether there are other computers sending data on the bus .

MA： Multipoint access , It means that many computers are connected to a bus by means of multi-point access . Bus network

CD： collision detection （ Collision detection ）,“ Monitor while sending ”, The adapter detects the change of signal voltage on the channel while transmitting data , In order to judge whether other sites are sending data when they are sending data . Half duplex network （ There can only be one sender , A receiver , The situation of two people crossing the single log bridge from the opposite bank of the river ）

Q： Listen first and then send. Why conflict ？

A： Because the electromagnetic wave propagates at a finite rate on the bus , May be in A Send to C At the same time , Has not been transmitted to B In the interval of ,B Also give C send data , This creates conflict .

Two 、 The influence of propagation delay on carrier monitoring

Q： As the sender , How long can I know the data I send ？

A：0 to $2\tau$

3、 ... and 、 How to determine the retransmission time after collision ？

Truncated binary exponential circumvention algorithm

1. Determine the basic backoff （ delay ） The time is the contention period $2\tau$ ;

2. Defining parameters k, Let it equal the number of retransmissions , but k No more than 10, namely k = min[ Number of retransmissions , 10] . When the number of retransmissions does not exceed 10 when ,k Equal to retransmission times ; When the number of retransmissions is greater than 10 when ,k It doesn't grow any more and it's always equal to 10;

3. From a discrete set of integers [0, 1,..., $2^{k}-1$ ] Take a random number r, The backoff time required for retransmission is r Times the basic escape time , namely $2r\tau$ ;

4. When re communicating 16 Time Still unsuccessful , The network is too crowded , I think this frame will never be sent correctly , Discard this frame and report an error to the higher level ;

example ： In the binary fallback algorithm of Ethernet , stay 11 After the first collision , The site will be in 0~（？） Choose a random number between .

Parameters k Is the number of retransmissions , Although it has happened 11 Secondary collision , But the maximum value can only be 10, $2^{10}-1= 1023$

Four 、 Minimum frame length problem

Suppose the sender sends a very short frame , The collision is detected after the frame is sent , There will be no more stop sending , Because the frame is too short, it has been sent .

How to solve this phenomenon ？—— Specify a minimum frame length

Ethernet will be less than 64B Frame of .

5、 ... and 、 summary

3.5-5 CSMA/CA agreement

CSMA/CD It's about collision detection ;

CA It is the avoidance of collision ;

One 、CSMA/CD agreement

Carrier monitoring multipoint access / Collision avoidance CSMA/CA （carrier sense multiple access with collision avoidance）

CA Will wait for a while after sending the message , See if there is a collision , If you don't send the next one

Why? CSMA/CD The agreement is only collision avoidance 、 Use it without collision detection ？

—— Different application scenarios

CA Use with WLAN , That is, in Wireless Networks ;

CD Used when there is a network , In bus Ethernet ;

CD The limitations in WLAN are ：

（1） Can't do 360° Comprehensive collision detection （ Wireless network space is large , It is difficult to realize in hardware ）

（2） Hidden station problem , When A and C Can't detect the signal , When the channel is considered idle , Simultaneously to the terminal B Sending data frames , It can lead to conflict .

Two 、CSMA/CA How the protocol works

（1） Before the sender sends data , First, check whether the channel is idle ;

Channel free Send out RTS（request to send）,RTS Including the address of the sender 、 Address of receiving end 、 Information such as the time when the next data will continue to be sent ;

The channel is busy Is waiting for ;

（2） The receiver receives RTS after , Corresponding CTS（clear to send）;

（3） The sender receives CTS after , Start sending data frames （ meanwhile Reservation channel ： The sender tells other sites how long they want to transmit data ）;

（4） After the receiving end receives the data frame , Will use CRC（ Cyclic redundancy check ） To verify that the data is correct , Correct response ACK frame ;

（5） The sender received ACK You can send the next data frame , If not, it will be retransmitted until the specified number of retransmissions （ The binary exponential backoff algorithm is used to determine the random delay time ）;

CA Three methods are used to realize collision avoidance ：

1. Reservation channel （ The sender ）;

2. ACK Confirm frame （ The receiver ）;

3. RTS（ The sender ）/CTS（ The receiver ）（ When detecting the channel, the two ends send these two frames , In order to solve the problem of hidden stations ）;

3、 ... and 、CSMA/CD And CSMA/CA Comparison

The same thing ：

CSMA/CD And CSMA/CA Mechanisms are subordinate to CSMA The idea of , Its core is Listen first . in other words , Both need to be monitored before accessing the channel . When the channel is found to be idle , To access .

Difference ：

1. The transmission medium is different ：CSMA/CD For bus Ethernet （ The cable ）, and CSMA/CA For WLAN （ wireless ）;

2. Carrier detection methods are different ： Due to different transmission media ,CSMA/CD And CSMA/CA The detection methods are also different .

CSMA/CD It is detected by the change of voltage in the cable , When data collides , The voltage in the cable will change with ;

CSMA/CA Use energy detection （ED）、 Carrier detection （CS） And energy carrier hybrid detection are three ways to detect channel idle ;

3. CSMA/CD Detect conflicts ,CSMA/CA To avoid conflict , In case of conflict between them, retransmission with upper limit will be carried out ;

3.5-6 Polling access media access control

One 、 Media access control review

（ Static division channel ） Channel partition media access control （MAC Multiple Access Control） agreement ：

be based on Multiplexing Technology divides resources ;

Heavy network load ： High efficiency of shared channel , And fair ;

The network load is light ： The efficiency of shared channel is low ;

（ Dynamic channel division ） Random access MAC agreement ：

The user will Random Send a message , Exclusive channel bandwidth when sending information .

Heavy network load ： Generate conflict overhead （ The conflict makes the information at the sender invalid ）;

The network load is light ： High efficiency of shared channel , A single node can use all the bandwidth of the channel ;

（ Dynamic channel division ） Polling access MAC agreement / Take turns / Rotational access MAC agreement ：

That is, there is no conflict , It takes up all the bandwidth when sending .

（1） Polling protocol

（2） Token passing protocol

Two 、 Polling protocol

The master node takes turns “ The invitation ” The slave node sends data .

The master node sends short needles to the slave node in order , See whether the dependent node needs to send data to itself .

Existing problems ：

1. Polling overhead （ When there are many subordinate nodes, the master node will ask many times ）;

2. Wait for a delay （ For the following slave node host ）;

3. A single point of failure （ When the primary node goes down, it will all be broken ）;

3、 ... and 、 Token passing protocol

token ： A special format MAC Control frame , Without any information . He controls the use of channels , Ensure that only one node monopolizes the channel at the same time .

Token ring network collision free , Each node can be in a certain time （ Token holding time ） Get the right to send data , You don't hold tokens indefinitely .

Existing problems ：
1. Token overhead （ Lost during token passing , Or after the source site transmits data , Generate a new token ）;

2. Wait for a delay （ The receiving end is in the rear ）;

3. A single point of failure （ Any host will break down , Alternative machines are available ）;

Token passing protocol is applied to token ring network , Logically, it is a ring topology , Physically, it is a star topology .

Token passing networks are often used in Heavy load 、 Large traffic In the network .