Part 2 Backward-Learning
In the data-link layer, hubs, bridges, and switches are the main type of devices you are going to encounter. The function of these devices is to eliminate the need for shared access mediums on wired network connections. Before the introduction of these devices, clients had to wait their turn before they could send something on the shared channel. With the introduction of hubs, it was possible for each client to have a dedicated channel to the hub that didnt go down when other computers were offline. Although the hub was a step forward, it still had the disadvantage of blocking the network when a packet was sent by broadcasting it to every client connected to the hub. Bridges and switches solved this problem by keeping track of where clients are located on the switch, in a table. This table stores mappings from MAC address to port number. To learn the location of the clients, bridges and switches use an algorithm called backward learning. This algorithm automatically starts learning about all the clients when they become active on the network.
For more information see section 4.8.2 of the book.
Programming exercise
In this programming exercise, you implement the software that runs on our made-up simplified switch. This switch receives frames on multiple links. Your code needs to forward these frames on the appropriate links. A template will be provided with the correct function signature. A basic test case can be found under the Test tab, but you are highly encouraged to write your own test cases to make sure your implementation is correct.
The core task of the switch is to forward incoming frames on the correct links. Initially, it is unknown how the machines are connected to the different ports. In the backward-learning algorithm, when the location of a machine is unknown, the message is flooded. If a message is sent out on multiple links, these links should appear in ascending order in the output. Your program should also take into account machines connected to the switch via a hub. From the perspective of the switch, this means these machines are connected to the same port.
The bytes that are part of the frame are encoded in hexadecimal notation, which means every two characters correspond to one byte.
The frame has the following format:
aaaabbbbxxxxxxxxxxxxxxxxxxxx
Where aaaa is a hexadecimal representation of the source computer
Where bbbb is a hexadecimal representation of the destination computer
Where xxxxxxxxxxxxxxxxxxxx is a hexadecimal representation of the message
We use a fixed length for the message of 20 hex values, but it shouldnt matter in your implementation.
The output should have the following format: A list of all ports on which the frame is sent out by your switch. If the frame is not sent out on any links, the output should be an empty list.
An example of an output for a broadcast to 4 ports, where the sender is on port 1 would be:
[0, 2, 3]
Assumptions
You may assume that you are always allowed to transmit on a link, even if multiple machines are connected to it
You may assume that there are no collisions
You may assume that frames are forwarded to their destination, even if their checksum
indicates a transmission error.
Part 3 TU-STP
Devices in the data-link layer are normally connected redundantly to make sure that physical failures will not cause a network outage. A good example of this is a switch. When there are two cables connecting two switches, if one fails the other one can still carry the traffic (Although possibly at a reduced rate). However, when there are multiple routes to a destination (Also called loops), a broadcast storm can occur when packets are sent to the entire network. This happens because, with the loop, there is always a path for the traffic to go (that isnt the incoming link). To solve this problem, higher-end switches make use of a protocol called Spanning Tree Protocol (STP). This protocol constructs a view of the network and creates a tree out of the network graph,
without any loops. The extra redundant links are temporarily disabled to accomplish this. When one of the links in the network has failures, the STP protocol can automatically reconfigure the network to use the redundant links.
The regular STP has two main steps:
1. Determine the root switch of the network
2. Calculate the best path (based on e.g. hops, latency, speed or bandwidth) from the current switch to the root switch
For more information see section 4.8.3 of the book.
Programming exercise
In this programming exercise, you are tasked to implement software that will implement our TU- STP protocol. This protocol is a simplified version of the regular STP: the root switch is determined up front and the network is static (i.e. no links are added or removed).
You should implement a Switch class. The constructor receives the MAC of this switch, that of the root and the number of ports the switch has. You should initialize the class variables here, but not send any messages.
Furthermore every switch has a receive function to receive messages.
To create the tree, the root switch of the network will receive a hop packet. This packet should be broadcasted, so other switches can use this to determine their distance to the root as well as the port they should send data to when trying to reach the root.
As the network may be cyclic, a switch may receive the hop packet more than once. Your code needs to be able to determine the ports that should be blocked to create the STP tree. You may also need to unblock links at a later point, if it turns out they should be part of the tree after all.
After the initial hop packet is sent to the root (which is done in Library.init_test()), the tests can send packets to any switch. The switch should send the packet over the correct port to reach the destination of the packet. If a switch does not know where to send a packet, it should send it to the root. The root should drop packets when it does not know where to send them. Sending messages
A library that emulates the network is provided. You should use this to send data over links to other switches. The only function you should use is the following:
This sends a message with the given from over its given . The bytes that are part of the frame are encoded in hexadecimal notation, which means every two characters correspond to one byte.
Frame formatting
The messages sent between the switches should be formatted as follows:
1 byte Flag -> 0 for a normal packet, 1 for the initial hop packet (you can use other flags your own messages)
2 bytes source mac
2 bytes destination mac
Library.send(int senderMac, int senderPort, String frame)
frame
(if hopping packet) 2 bytes hop-count So, a valid frame could look like
(the flag is 01) send to switch with mac hop-count of 2.
Another valid frame would be
comes from AAAA and has to be routed to
The initial hop packet that is sent to the root is the following: 010000FFFF0000 (hop packet with hop count 0). This is received on link -1.
Note: you should not deviate from this frame formatting, otherwise the tests will fail.
Testing
In the library there is a function that returns the entire backlog of messages sent (for testing purposes). The backlog starts from the first regular packet (i.e. the hop packets are not recorded).
The backlog is a list consisting of strings in the format: [Source][SourcePort]-[The frame].
For example: aaaa01-00bbbbccccwould be a packet coming from switch aaaa on port 1, with the frame as specified in the frame format.
senderMac
, which would correspond to a hop packet , coming from the switch with mac BBBB, and a
senderPort
01BBBBAAAA0002
AAAA
00AAAACCCC
, which would correspond to a regular packet that .
CCCC
Visible test
One test network has been provided. It represents the network in this image:
Note that the link between dddd (D) and 1111 (1) is a dead link: both switches have a shorter path to the root.
Useful commands
Java
To process the frame string, you can use the following:
int flag = Integer.parseInt(frame.substring(0, 2), 16);
int source = Integer.parseInt(frame.substring(2, 6), 16);
int dest = Integer.parseInt(frame.substring(6, 10), 16);
(and if applicable)
int hopcount = Integer.parseInt(frame.substring(10, 14), 16);
To create a frame, you can use:
String newframe = String.format(%02x,flag) + String.format(%04x, dest) + String.format(%04x, source) + String.format(%04x, hopcount);
Python
To process the frame string, you can use the following:
flag = int(frame[0:2], 16)
source = int(frame[2:6], 16)
dest = int(frame[6:10], 16)
(and if applicable)
hopcount = int(frame[10:14], 16)
To create a frame, you can use:
newframe = str(format(flag, 02x)) + str(format(dest, 04x)) + str(format(source, 04x)) + str(format(hopcount, 04x))
Reviews
There are no reviews yet.