CPSC 441: Computer Networks

Fall 2021

Assignment 4: RFID Scanning (40 marks)

Due: Friday, December 3, 2021 (11:59pm)

Learning Objectives

The purpose of this assignment is to learn about Medium Access Control (MAC) protocols, which regulate access to a shared channel. In particular, you will study a slotted-time protocol similar to those used in high-tech RFID scanning systems. While doing so, you will reinforce key concepts regarding multiple-access protocols (e.g., shared channel, multiple nodes, random access, collisions, successes, idle slots, efficiency), and determine how such protocols perform across a wide range of test cases.

Background

In the future, large retail stores like WalMart may use RFID scanning technology at their checkout lanes instead of human clerks or cashiers. In this approach, each item in the store has a small micro-chip attached that uniquely identifies the item using a K-bit identifier. At the checkout, a customer with a basket of N items walks past the RFID scanner, which "instantly" scans the basket of goods, identifies each item, determines a price for each, calculates the total, and initiates the e-payment process with the customer.

Problem Description

In this assignment, you will explore the details of the RFID scanning step, and devise an efficient MAC protocol to make the checkout process simple and fast. You will be told the value of K, which determines the K-bit address space for possible items. You will then be given multiple test cases of customers with baskets of goods. For each customer, you must determine how many items they have, how long it takes the RFID scanner to identify everything in the basket, and how efficient it is in doing so.

MAC Protocol Description

The following MAC protocol is quite different from Ethernet's CSMA/CD or WiFi's CSMA/CA, but is also simpler, since it is a discrete-time (slotted) protocol. While this specific protocol will not be covered in class, the general design principles and performance tradeoffs of channel access protocols will be discussed during the lectures on MAC protocols, and should be helpful to you when undertaking this assignment. However, the assignment is adequately self-contained that you can probably start on it even before we cover MAC protocols in class.

Consider a simple bus-based linear-topology LAN with M nodes (items), where M is a power of 2 (e.g., M = 8). Attached to one end of this network is a special controller that is in charge of coordinating access to the shared channel for the M nodes. Assume that the nodes are numbered from 0 to M-1 in binary (e.g., from '000' to '111' if M = 8), from left to right.

The RFID scanning protocol conceptually arranges these nodes into a complete binary tree configuration. For example, if M = 8, there are 8 (real) leaf nodes at Level 3, there are 4 virtual nodes (each with 2 children) above them at Level 2, there are 2 virtual nodes above these at Level 1, and 1 virtual node at Level 0, which is the root of the binary tree.

Each virtual node in this binary tree represents a particular subset of the real nodes (items) in the network. For example, the root node represents "all nodes in the network", while the leftmost virtual node on Level 1 represents "all nodes with an address of the form 0XX", and the rightmost virtual node on Level 1 represents "all nodes with an address of the form 1XX", where 'X' denotes a wild-card (i.e., Don't Care) condition. Similar reasoning applies recursively for other levels of the tree. For example, the rightmost virtual node on Level 2 represents "all nodes with an address of the form 11X". Note that the virtual binary tree structure is conceptual only; the physical layout of the network is simply a linear bus with M nodes.

The controller regulates channel access on this LAN by polling (querying) certain subsets of the nodes in subsequent steps of the protocol, giving them permission to transmit. These polling steps are referred to as probes in the following description of the protocol. For example, suppose that nodes (items) 1, 5, and 6 are present and ready to transmit. If the controller starts the probing at the root of the tree (Level 0), a collision would occur on the first probe attempt, since three nodes all try to transmit at the same time. Subsequent recursive probes to the two individual nodes on Level 1 would result in a successful transmission for node 1 in the first time slot (since it is the only node in the left subtree whose address starts with '0'), followed by another collision probe for nodes 5 and 6 in the next time slot (since both nodes have an address that starts with '1'). Further recursive probes down the right subtree to Level 2 will resolve the channel access, with a successful transmission by node 5 followed by a successful transmission by node 6. In this example scenario, resolving the three original data frame transmissions required a total of 5 probe slots: 2 collisions, 3 successes, and 0 idle. Continuing the example, if the controller were to start at Level 3 for the given initial scenario, there would be 8 probes required: 3 of these would lead to successful transmissions (nodes 1, 5, and 6), and 5 of these would be idle (wasted) probe slots. In this example, starting the probing at the root level is 60% efficient (i.e., 3 successes out of 5 slots), while starting the probing at the leaf level has an efficiency of 37.5% (i.e., 3 successes out of 8 slots).

Your Task

Your task in this assignment is to write a program that models this recursive slotted-time MAC protocol, and determines its performance on different baskets of items at WalMart. Your program can be written in either C or C++.

Your program should be easily parameterizable for different values of K, either on the command line, via user input, or in the code itself. Your program should be carefully instrumented to keep track of the different events that can happen during the scanning of a specific basket of goods, and to report the total time taken for each scan. Once you have tested your program to ensure that it is working properly, use it to answer the questions indicated below.

Testing

Here are some test cases for K=3. These are each small enough that you should be able to analyze them manually to verify if your program is correct.

And here are the actual test cases for the assignment, with K=10 and M=1024.

Questions

Use your program to answer the following questions:

  1. Which of the customers has the most items? How many items do they have?
  2. When starting at the leaf level of the tree, which basket of goods takes the most time to scan? How many time slots does it require?
  3. When starting at the root level of the tree, which basket of goods takes the most time to scan? How many time slots does it require?
  4. When starting at the root level of the tree, which basket of goods takes the least time to scan? How many time slots are needed?
  5. When starting at the root level of the tree, which basket of goods generates the most collisions during scanning? How many collisions occur?
  6. When starting at the root level of the tree, which basket of goods generates the highest proportion of successful slots (i.e., efficiency) during scanning?

Grading Scheme

The proposed grading scheme for the assignment is as follows:

Optional Bonus 1: (2 marks) Depending on the basket of goods, the RFID scanning protocol might be more efficient if you were to start scanning at an intermediate level of the binary tree, rather than always starting at the root or the leaf level. Modify your program to explore this idea, and try to formulate a heuristic answer (i.e., rule of thumb) for how to choose the best starting level for this protocol for a given basket of goods. Explain your result as best you can.

Optional Bonus 2: (2 marks) From some of the small test cases above, you may get an idea for how to improve the basic RFID scanning protocol. If so, modify your program to evaluate the effectiveness of this idea. Show your new results.

When you are finished, please submit your individual assignment solution via D2L, on or before the stated deadline.

Tips