What are collision free protocols? Briefly describe any two collision free protocols.
Answers
1. Collision Free Protocol Hemang Kothari Assistant Professor Computer Engineering Department MEFGI, Rajkot. Email: [email protected]
2. Motivation • Pure ALOHA, slotted ALOHA, CSMA and CSMA/CD are contention based protocols – try. If collide, retry. – No guarantee of performance. – What happens if the network load is high? • Collision free protocols: – pay constant overhead to achieve performance guarantee – Good when network load is high
3. Motivation Reservation Polling Against Corruption
4. Collision Free World • Provides in order access to shared medium so that every station has chance to transfer (fair protocol) • Eliminates collision completely • Three methods for controlled access: – Reservation – Polling – Token Passing
5. Reservation – Bit Map • Stations take turns transmitting a single frame at a full rate ( R ) bps • Each cycle begins with a reservation interval that consists of (N) mini-slots. One mini-slot for each of the N stations
6. Bit Map - Reservation Based • When a station needs to send a data frame, it makes a reservation in its own mini-slot. • By listening to the reservation interval, every station knows which stations will transfer frames, and in which order. • The stations that made reservations can send their data frames after the reservation frame.
7. Polling • Stations take turns accessing the medium • One device is assigned as primary station and the others as secondary stations • All data exchanges are done through the primary • When the primary has a frame to send it sends a select frame that includes the address of the intended secondary • When the primary is ready to receive data it send a Poll frame for each device to ask if it has data to send or not. If yes, data will be transmitted otherwise NAK is sent. • Polling can be done in order (Round-Robin) or based on predetermined order
8. Polling
9. Binary Countdown • Each station sends the address bits in some order (from highest order bit to the lowest order bit). • The bits in each position from different stations are ORed.
10. Example – Binary Countdown
11. Token Ring
12. Limited Contention Protocols • Collision based protocols (ALOHA,CSMA/CD) are good when the network load is low. • Collision free protocols (bit map, binary Countdown) are good when load is high. • How about combining their advantages -- limited contention protocols. – Behave like the ALOHA scheme under light load – Behave like the bitmap scheme under heavy load.
13. Adaptive Tree Walk Protocol • Trick: partition the group of station and limit the contention for each slot. • Under light load, every one can try for each slot like aloha • Under heavy load, only a small group can try for each slot • how do we do it – treat stations as the leaf of a binary tree. – first slot (after successful transmission), all stations (under the root node) can try to get the slot. – if no conflict, fine. – if conflict, only nodes under a subtree get to try for the next one. (depth first search)
14. 0 1 Example: 2 3 4 5 6 A B C* D E* F* G H* Slot 0: C*, E*, F*, H* (all nodes under node 0 can try), conflict slot 1: C* (all nodes under node 1 can try), C sends slot 2: E*, F*, H*(all nodes under node 2 can try), conflict slot 3: E*, F* (all nodes under node 5 can try), conflict slot 4: E* (all nodes under E can try), E sends slot 5: F* (all nodes under F can try), F sends slot 6: H* (all nodes under node 6 can try), H sends.
15. Review - 1 • Sixteen stations, numbered 1 through 16, are contending for the use of a shared channel • By using the adaptive tree walk protocol. If all the stations whose addresses are prime numbers suddenly become ready at once, • how many bit slots are needed to resolve the contention?
A "collision" occurs when there is transmission of data between any two devices where the data is sent between the "sender and receiver".
There is a loss of data or error in the transmitted data when there is a collision in the ends of the either sender or receiver. Collision-free protocols are used to avoid these collisions. Examples are Bitmap and Binary countdown.