计算机网络课业代做 计算机网络作业代做

Assignment 4 (100 points)

 

1 Written questions   计算机网络课业代做

1.1 Different router architectures (10 points)

Consider a router with N input ports and N output ports. Answer the following questions.

1. How many enqueues and dequeues does the memory of a shared-memory router need to support on every tick? (2 points)
2. How many enqueues and dequeues does each memory of an output-queued router need to support on every tick? How many such memories are required? (3 points)
3. How many enqueues and dequeues does each memory of an input-queued router need to support on every tick? How many such memories are required? (3 points)
4. What is the advantage of a shared-memory router relative to aninput/output-queued router? What is the disadvantage? (2 points)

1.2 The ALOHA protocol (10 points)

Assume there are N users who cannot hear each other communicating with a centralized coordinator in the ALOHA protocol.

1. Derive the optimal value of the transmission probability for each user in the ALOHA protocol. (5 points)
2. What it the overall utilization of the shared medium when each user uses the optimal transmission probability? Show your work. (5 points)

1.3 Differences between ALOHA, WiFi, and Ethernet (20 points)   计算机网络课业代做

1. Explain the difference in operating conditions between ALOHA and WiFi. (5 points)
2. How does this manifest itself as differences in the design of the ALOHA and WiFi MAC protocols? (5 points)
3. Explain the difference between the physical layer of WiFi and Ethernet. (5 points)
4. How does this manifest itself as differences in the design of the WiFi and Ethernet MAC protocols? (5 points)

1.4 Other questions on MAC protocols (30 points)

1. What is carrier sense? (5 points)
2. What is one possibile implementation of the carrier sense capability? (5 points)
3. Give an example of the hidden terminal problem. (5 points)
4. Explain how WiFi solves the hidden terminal problem. (5 points)
5. Explain the TDMA and FDMA MAC protocols. (5 points)
6. Where would you use TDMA/FDMA-style MAC protocols? (2 points)
7. How are they different from the MAC protocols used in WiFi, ALOHA, or Ethernet? (3 points)

 

2 Coding questions (30 points)   计算机网络课业代做

Use the starter code (hash_tables.py) to implement the three different schemes for exact matching we discussed in class: standard hashing (5 points), 2choice hashing (10 points), and 2left hashing (15 points).

2.1 Code walkthrough

hash_tables.py is the only Python file you’ll need to work with for this assignment. It takes two arguments.

The first one is the occupancy of the hash table (i.e., what fraction of the hash table is populated with entries).

The second one is the name of the hashing scheme (“2choice”, “2left”, or “standard”). For instance, to run hash_tables.py with the standard hashing scheme with an occupancy of 30%, you would run the following command:

Anirudhs-Air:sims anirudh$ python3 hash_tables.py 0.3 standard
Fraction of trials in which slot size did not exceed capacity 0.671

The output of running this command tells you how often the hash table did not overflow. To understand how this is calculated, let’s walk through hash_tables.py.

 

 

The constants at the top of hash_tables.py are:

1. The occupancy of the hash table as a fraction between 0 and 1. This is fed in by the user.
2. The number of slots in the hash table. For all three hashing schemes, we structure the hash table as an array with a certain number of slots, where each slot can hold up to a certain number of elements.
3. The capacity of each slot. This reflects hardware realities of how many elements can be held in each slot. We have set this to 5 because it is in the same ballpark as the number of elements in each slot for real hardware implementations.
4. The number of trials. For each trial, we check if the hash table overflowed: did the hash table run out of space because a particular slot that an element hashed into was already full? Note that we say that the hash table overflowed if even a single slot’s capacity has been exceeded—even though the hash table might still have space in other slots. This is why the fraction of trials in which the hash table did not overflow reaches 0 long before the occupancy of the hash table reaches 1.
5. The number of elements in the hash table. This is computed by multiplying the occupancy fraction with the product of the number of slots and the capacity of each slot (i.e., the maximum occupancy of the entire hash table).

After the constants have been initialized (either to default or user-supplied values), the main for loop in hash_tables.py runs (for seed in range(TOTAL_TRIALS):). This for loop runs a number of independent trials, each initialized with a different random seed to ensure the randomness in each trial is independent of other trials.

In each trial, we run through the total number of elements in the hash table in another for loop (for i in range(NUM_ELEMENTS):). For each element, we compute the slot it hashes into depending on the hashing scheme, which is another user-supplied input.

You need to implement three hashing schemes.   计算机网络课业代做

1. standard: We compute a single slot number for each new element regardless of the current occupancy of each slot.
2. 2choice: We compute 2 slot numbers using two independent hash functions, and then pick the slot number that has lower occupancy, breaking ties randomly.
3. 2left: We conceptually divide the hash table into two subtables with equal number of slots in each subtable. We compute a slot number in each subtable using two independent hash functions. Of these 2 slots in 2 subtables, we pick the slot that has lower occupancy, but always break ties in favor of one of the two subtables.

To compute a random slot number, you do not need to use an actual hash function for this assignment. Instead, you can use the Python function call (random.randint(U, L)) to generate a random slot number between U and L (both U and L included). You can test the occupancy at a particular slot number using the occupancy array in hash_tables.py. For each algorithm, make sure that the slot number you pick is written into the variable (slot_number) in hash_tables.py because this is the index variable we use to update the occupancy array.

2.2 Testing your code   计算机网络课业代做

The easiest way to test your code is to remember that for a given occupancy, the fracton of trials in which the hash table does not overflow is going to be highest for 2left, followed by 2choice, followed by standard. For instance, when I run my solutions for all three algorithms with an occupancy of 0.6, here’s what I see.

Anirudhs-Air:sims anirudh$ python3 hash_tables.py 0.6 2left
Fraction of trials in which slot size did not exceed capacity 0.999
Anirudhs-Air:sims anirudh$ python3 hash_tables.py 0.6 2choice
Fraction of trials in which slot size did not exceed capacity 0.994
Anirudhs-Air:sims anirudh$ python3 hash_tables.py 0.6 standard
Fraction of trials in which slot size did not exceed capacity 0.0

Also, when the occupancy of the hash table goes up, the performance of all three schemes must degrade: the fraction of trials in which the hash table does not overflow should go down. When I run the three algorithms with an occupancy of 0.7, here’s what I see.

Anirudhs-Air:sims anirudh$ python3 hash_tables.py 0.7 2left
Fraction of trials in which slot size did not exceed capacity 0.95
Anirudhs-Air:sims anirudh$ python3 hash_tables.py 0.7 2choice
Fraction of trials in which slot size did not exceed capacity 0.844
Anirudhs-Air:sims anirudh$ python3 hash_tables.py 0.7 standard
Fraction of trials in which slot size did not exceed capacity 0.0

 

 

更多代写：cs澳大利亚网课代考价格  sat考试作弊  英国金融数学网课代上   澳洲论文essay代写  北美assignment代写  计算机网络编程代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写