Token Ring/IEEE 802.5 (CS2302 Computer Networks Unit - II)

                                                        UNIT II

Medium access – CSMA – Ethernet – Token ring – FDDI - Wireless LAN – Bridges and Switches 

Token Ring:

The Token Ring network was originally developed by IBM in the 1970s. It is still IBM's primary local-area network (LAN) technology. The related IEEE 802.5 specification is almost identical to and completely compatible with IBM's Token Ring network. In fact, the IEEE 802.5 specification was modeled after IBM Token Ring, and it continues to shadow IBM's Token Ring development. The term Token Ring generally is used to refer to both IBM's Token Ring network and IEEE 802.5 networks.

 

Token Ring Operation

Token Ring and IEEE 802.5 are two principal examples of token-passing networks (FDDI is the other). Token-passing networks move a small frame, called a token, around the network. Possession of the token grants the right to transmit. If a node receiving the token has no information to send, it passes the token to the next end station. Each station can hold the token for a maximum period of time.

If a station possessing the token does have information to transmit, it seizes the token, alters 1 bit of the token (which turns the token into a start-of-frame sequence), appends the information that it wants to transmit, and sends this information to the next station on the ring. While the information frame is circling the ring, no token is on the network (unless the ring supports early token release), which means that other stations wanting to transmit must wait. Therefore, collisions cannot occur in Token Ring networks. If early token release is supported, a new token can be released when frame transmission is complete.

The information frame circulates the ring until it reaches the intended destination station, which copies the information for further processing. The information frame continues to circle the ring and is finally removed when it reaches the sending station. The sending station can check the returning frame to see whether the frame was seen and subsequently copied by the destination.

Unlike CSMA/CD networks (such as Ethernet), token-passing networks are deterministic, which means that it is possible to calculate the maximum time that will pass before any end station will be capable of transmitting.

Priority System

Token Ring networks use a sophisticated priority system that permits certain user-designated, high-priority stations to use the network more frequently. Token Ring frames have two fields that control priority: the priority field and the reservation field.

Only stations with a priority equal to or higher than the priority value contained in a token can seize that token. After the token is seized and changed to an information frame, only stations with a priority value higher than that of the transmitting station can reserve the token for the next pass around the network. When the next token is generated, it includes the higher priority of the reserving station. Stations that raise a token's priority level must reinstate the previous priority after their transmission is complete. 

Fault-Management Mechanisms

Token Ring networks employ several mechanisms for detecting and compensating for network faults. For example, one station in the Token Ring network is selected to be the active monitor. This station, which potentially can be any station on the network, acts as a centralized source of timing information for other ring stations and performs a variety of ring-maintenance functions. One of these functions is the removal of continuously circulating frames from the ring. When a sending device fails, its frame may continue to circle the ring. This can prevent other stations from transmitting their own frames and essentially can lock up the network. The active monitor can detect such frames, remove them from the ring, and generate a new token.

Frame Format

Token Ring and IEEE 802.5 support two basic frame types: tokens and data/command frames. Tokens are 3 bytes in length and consist of a start delimiter, an access control byte, and an end delimiter. Data/command frames vary in size, depending on the size of the Information field. Data frames carry information for upper-layer protocols, while command frames contain control information and have no data for upper-layer protocols.

Token Frame Fields

The three token frame fields illustrated in Figure 9-3 are summarized in the descriptions that follow: 

Start delimiter - Alerts each station of the arrival of a token (or data/command frame). This field includes signals that distinguish the byte from the rest of the frame by violating the encoding scheme used elsewhere in the frame.

Access-control byte - Contains the Priority field (the most significant 3 bits) and the Reservation field (the least significant 3 bits), as well as a token bit (used to differentiate a token from a data/command frame) and a monitor bit (used by the active monitor to determine whether a frame is circling the ring endlessly).

End delimiter - Signals the end of the token or data/command frame. This field also contains bits to indicate a damaged frame and identify the frame that is the last in a logical sequence.

 

Data/Command Frame Fields

Data/command frames have the same three fields as Token Frames, plus several others. The Data/command frame fields illustrated in Figure 9-3 are described in the following summaries:

• Start delimiter - Alerts each station of the arrival of a token (or data/command frame). This field includes signals that distinguish the byte from the rest of the frame by violating the encoding scheme used elsewhere in the frame.
• Access-control byte - Contains the Priority field (the most significant 3 bits) and the Reservation field (the least significant 3 bits), as well as a token bit (used to differentiate a token from a data/command frame) and a monitor bit (used by the active monitor to determine whether a frame is circling the ring endlessly).
• Frame-control bytes - Indicates whether the frame contains data or control information. In control frames, this byte specifies the type of control information.
• Destination and source addresses - Consists of two 6-byte address fields that identify the destination and source station addresses.
• Data - Indicates that the length of field is limited by the ring token holding time, which defines the maximum time a station can hold the token.
• Frame-check sequence (FCS) - Is filed by the source station with a calculated value dependent on the frame contents. The destination station recalculates the value to determine whether the frame was damaged in transit. If so, the frame is discarded.
• End Delimiter - Signals the end of the token or data/command frame. The end delimiter also contains bits to indicate a damaged frame and identify the frame that is the last in a logical sequence.
• Frame Status - Is a 1-byte field terminating a command/data frame. The Frame Status field includes the address-recognized indicator and frame-copied indicator.

 

Carrier Sense Multiple Access (CSMA) --CS2302 Computer Networks Unit - II

                                                        UNIT II

Medium access – CSMA – Ethernet – Token ring – FDDI - Wireless LAN – Bridges and Switches 

Carrier Sense Multiple Access (CSMA)

To minimize the chance of collision and, therefore, increase the performance, the CSMA method was developed. The chance of collision can be reduced if a station senses the medium before trying to use it. Carrier sense multiple access (CSMA) requires that each station first listen to the medium (or check the state of the medium) before sending. In other words, CSMA is based on the principle "sense before transmit" or "listen before talk."

CSMA can reduce the possibility of collision, but it cannot eliminate it. The possibility of collision still exists because of propagation delay; when a station sends a frame, it still takes time (although very short) for the first bit to reach every station and for every station to sense it. In other words, a station may sense the medium and find it idle, only because the first bit sent by another station has not yet been received.

Vulnerable Time

The vulnerable time for CSMA is the propagation time Tp . This is the time needed for a signal to propagate from one end of the medium to the other. When a station sends a frame, and any other station tries to send a frame during this time, a collision will result.

                                                          Vulnerable time in CSMA

Persistence Methods

What should a station do if the channel is busy? What should a station do if the channel is idle?

Three methods have been devised to answer these questions:

1.  I-persistent method
2.  nonpersistent method
3. p-persistent method

I-Persistent : The I-persistent method is simple and straightforward. In this method, after the station finds the line idle, it sends its frame immediately (with probability I). This method has the highest chance of collision because two or more stations may find the line idle and send their frames immediately.

Nonpersistent : In the nonpersistent method, a station that has a frame to send senses the line. If the line is idle, it sends immediately. If the line is not idle, it waits a random amount of time and then senses the line again. The nonpersistent approach reduces the chance of collision because it is unlikely that two or more stations will wait the same amount of time and retry to send simultaneously. However, this method reduces the efficiency of the network because the medium remains idle when there may be stations with frames to send.

p-Persistent: The p-persistent method is used if the channel has time slots with a slot duration equal to or greater than the maximum propagation time. The p-persistent approach combines the advantages of the other two strategies. It reduces the chance of collision and improves efficiency. In this method, after the station finds the line idle it follows these steps:

1. With probability p, the station sends its frame.

2. With probability q = 1 - p, the station waits for the beginning of the next time slot and checks the line again.

                    a. If the line is idle, it goes to step 1.

                    b. If the line is busy, it acts as though a collision has occurred and uses the backoff

                        procedure.

  

                                                     Behavior of three persistence methods

Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

The CSMA method does not specify the procedure following a collision. Carrier sense multiple access with collision detection (CSMA/CD) augments the algorithm to handle the collision.

In this method, a station monitors the medium after it sends a frame to see if the transmission was successful. If so, the station is finished. If, however, there is a collision, the frame is sent again.

To better understand CSMA/CD, let us look at the first bits transmitted by the two stations involved in the collision. Although each station continues to send bits in the frame until it detects the collision, we show what happens as the first bits collide. In Figure, stations A and C are involved in the collision.

 Collision ofthe first bit in CSMAlCD

At time t 1, station A has executed its persistence procedure and starts sending the bits of its frame. At time t2, station C has not yet sensed the first bit sent by A. Station C executes its persistence procedure and starts sending the bits in its frame, which propagate both to the left and to the right. The collision occurs sometime after time t2' Station C detects a collision at time t3 when it receives the first bit of A's frame. Station C immediately (or after a short time, but we assume immediately) aborts transmission. Station A detects collision at time t4 when it receives the first bit of C's frame; it also immediately aborts transmission. Looking at the figure, we see that A transmits for the duration t4 - tl; C transmits for the duration t3 - t2' Later we show that, for the protocol to work, the length of any frame divided by the bit rate in this protocol must be more than either of these durations. At time t4, the transmission of A:s frame, though incomplete, is aborted; at time t3, the transmission of B's frame, though incomplete, is aborted.

Minimum Frame Size

For CSMAlCD to work, we need a restriction on the frame size. Before sending the last bit of the frame, the sending station must detect a collision, if any, and abort the transmission. This is so because the station, once the entire frame is sent, does not keep a copy of the frame and does not monitor the line for collision detection. Therefore, the frame transmission time Tfr must be at least two times the maximum propagation time Tp. To understand the reason, let us think about the worst-case scenario. If the two stations involved in a collision are the maximum distance apart, the signal from the first takes time Tp to reach the second, and the effect of the collision takes another time Tp to reach the first. So the requirement is that the first station must still be transmitting after 2Tp .

 

Energy Level

We can say that the level of energy in a channel can have three values: zero, normal, and abnormal. At the zero level, the channel is idle. At the normal level, a station has successfully captured the channel and is sending its frame. At the abnormal level, there is a collision and the level of the energy is twice the normal level. A station that has a frame to send or is sending a frame needs to monitor the energy level to determine if the channel is idle, busy, or in collision mode.

Flow diagramfor the CSMA/CD

Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)

The basic idea behind CSMA/CD is that a station needs to be able to receive while transmitting to detect a collision. When there is no collision, the station receives one signal: its own signal. When there is a collision, the station receives two signals: its own signal and the signal transmitted by a second station. To distinguish between these two cases, the received signals in these two cases must be significantly different. In other words, the signal from the second station needs to add a significant amount of energy to the one created by the first station.

In a wired network, the received signal has almost the same energy as the sent signal because either the length of the cable is short or there are repeaters that amplify the energy between the sender and the receiver. This means that in a collision, the detected energy almost doubles.

However, in a wireless network, much of the sent energy is lost in transmission. The received signal has very little energy. Therefore, a collision may add only 5 to 10 percent additional energy. This is not useful for effective collision detection.

We need to avoid collisions on wireless networks because they cannot be detected. Carrier sense multiple access with collision avoidance (CSMAlCA) was invented for this network. Collisions are avoided through the use of CSMA/CA's three strategies: the interframe space, the contention window, and acknowledgments.

Interframe Space (IFS)

First, collisions are avoided by deferring transmission even if the channel is found idle. When an idle channel is found, the station does not send immediately. It waits for a period of time called the interframe space or IFS. Even though the channel may appear idle when it is sensed, a distant station may have already started transmitting. The distant station's signal has not yet reached this station. The IFS time allows the front of the transmitted signal by the distant station to reach this station. If after the IFS time the channel is still idle, the station can send, but it still needs to wait a time equal to the contention time (described next). The IFS variable can also be used to prioritize stations or frame types. For example, a station that is assigned a shorter IFS has a higher priority.

Contention Window

The contention window is an amount of time divided into slots. A station that is ready to send chooses a random number of slots as its wait time. The number of slots in the window changes according to the binary exponential back-off strategy. This means that it is set to one slot the first time and then doubles each time the station cannot detect an idle channel after the IFS time. This is very similar to the p-persistent method except that a random outcome defines the number of slots taken by the waiting station. One interesting point about the contention window is that the station needs to sense the channel after each time slot. However, if the station finds the channel busy, it does not restart the process; it just stops the timer and restarts it when the channel is sensed as idle. This gives priority to the station with the longest waiting time.

 

                                                             Flow diagramfor the CSMA/CA

CS2302 Computer Networks Unit - I (Link-level flow control)

UNIT I

Network architecture – layers – Physical links – Channel Access on links– Hybrid multiple access techniques – Issues in the data link layer –Framing – Error correction and detection – Link-level flow control


Link-level flow control
 

Reliable Transmission  

• RCC is used to detect errors.
• Some error codes are strong enough to correct errors.
• The overhead is typically too high.
• Corrupt frames must be discarded.
• A link-level protocol that wants to deliver frames reliably must recover from these discarded frames.

Flow control is a technique that a transmitting entity does not conquer a receiving entity with data. Two fundamental mechanisms are acknowledgement and timeouts.

• After getting each frame the receiver will send ACK to sender.
• If the sender does not receive ACK up to reasonable amount of time then it retransmit the original frame waiting for reasonable amount of time is called timeout.

The two flow control mechanisms are

•    Stop and wait Flow Control
•    Sliding Window Flow Control

 

Stop and Wait Algorithm  

•  After transmitting one frame, the sender waits for an acknowledgment before transmitting the next frame.
• If the acknowledgment does not arrive after a certain period of time, the sender times out and retransmit the original frame. 

  

Fig: illustrates four different scenarios that result from this basic algorithm. The sending side is represented on the left, the receiving side is depicted on the right, and time flows from top to bottom.

• In Fig (a) ACK is received before the timer expires, (b) and (c) show the situation in which the original frame and the ACK, respectively, are lost, and (d) shows the situation in which the timeout fires too soon..
• Suppose the sender sends a frame and the receiver acknowledges it, but the acknowledgment is either lost or delayed in arriving. This situation is in (c) and (d). In both cases, the sender times out and retransmit the original frame, but the receiver will think that it is the next frame, since it correctly received and acknowledged the first frame. 
• This makes the receiver to receive the duplicate copies. To avoid this two sequence numbers (0 and 1) must be used alternatively.  

                                    Timeline for stop-and-wait with 1-bit sequence number

•      The main drawback of the stop-and-wait algorithm is that it allows the sender have only one outstanding frame on the link at a time. 
•   The sender has only one outstanding frame on the link at a time. 

                     –This may be far below the link’s capacity

•  Consider a 1.5 Mbps link with a 45 ms RTT
• The link has a delay    bandwidth product of 67.5 Kb or approximately 8 KB

• Since the sender can send only one frame per RTT and
• assuming a frame size of 1 KB 
• Maximum Sending rate 
• Bits per frame    Time per frame = 1024    8    0.045 = 182
• Kbps Or about one-eighth of the link’s capacity 
•  To use the link fully, then sender should transmit up to eight frames before having to wait for an acknowledgement 

 

Sliding Window Algorithm

• The sender can transmit several frames before needing an acknowledgement.
• Frames can be sent one right after another meaning that the link can carry several frames at once and it s capacity can be used efficiently. 
•  The receiver acknowledges only some of the frames, using a single ACK to confirm the receipt of multiple data frames 
• Sliding Window refers to imaginary boxes at both the sender and the receiver.  
• Window can hold frames at either end and provides the upper limit on the number of frames that can be transmitted before requiring an acknowledgement.
• Frames are numbered modulo-n which means they are numbered from o to n-1.
• For eg. If n=8 the frames are numbered 0, 1,2,3,4,5,6,7. i.e. the size of the window is n -1.
• When the receiver sends ACK it includes the number of the next frame it expects to receive.
• When the sender sees an ACK with the number 5, it knows that all frames up through number 4 have been received.
• Sender assigns a sequence number denoted as SeqNum to each frame. 
• Assume it can grow infinitely large.
• Sender maintains three variables.
• Sending Window Size (SWS)
• Upper bound on the number of outstanding (unacknowledged) frames that the sender can transmit.
• Last Acknowledgement Received (LAR)
• Sequence number of the last acknowledgement received
• Last Frame Sent (LFS)
• Sequence number of the last frame sent.
  
                                    Timeline for Sliding Window Protocol

• Sender also maintains the following invariant 
• LFS – LAR ≤ SWS

 

                                                                Sliding Window on Sender

• When an acknowledgement arrives
• the sender moves LAR to right, thereby allowing the sender to transmit another frame
• Also the sender associates a timer with each frame it transmits
• It retransmits the frame if the timer expires before the ACK is received 
• Note that the sender has to be willing to buffer up to SWS frames 

 

• Receiver maintains three variables  
• Receiving Window Size (RWS) 
• Upper bound on the number of out-of-order frames that the receiver is willing to accept 
• Largest Acceptable Frame (LAF) 
• Sequence number of the largest acceptable frame 
• Last Frame Received (LFR) 
• Sequence number of the last frame received  
• Receiver also maintains the following invariant 
• LAF – LFR ≤ RWS  

 

 

                                                            Sliding Window on Receiver

 

• When a frame with sequence number SeqNum arrives, what does the receiver do? 
• If SeqNum ≤ LFR or SeqNum > LAF
• Discard it (the frame is outside the receiver window)   
• If LFR < SeqNum ≤ LAF
• Accept it 
• Now the receiver needs to decide whether or not to send an ACK