Assignment: Framing, checksums and headers
Assignment: Framing, checksums and headers
Consider a communication system where a wireless receiver outputs bits continuously, no matter whether it is receiving frames or just random noise. The link layer communications protocol uses the bit sequence 01111110 as frame start and end markers. Two consecutive frames may be separate by a single marker only. The content of each frame is bitstuffed. With the bitstuffing removed, the frame consists of at least 3 bytes, but potentially more, such that:
The first byte identifies the intended receiver.
The second byte identifies the sender.
This is followed by a variable number of payload bytes.
The last byte is an 8-bit CRC over the frame content, using the generator polynomial 110010101
Your task in this assignment is to decode a bit stream, extract any frames, check for their integrity, and extract the payload of the intact frames. We will index the first bit in the bit stream with 0, the second bit with 1, and so on. The questions you must answer are:
- How many apparent markers are in the given bit stream? Count both frame start and end markers separately, and any bit patterns that look like markers, even if they are noise and not actual transmissions (5 marks).
- A candidate frame is a frame that, after removal of bitstuffing, contains a multiple of 8 bits of data, with a minimum of 24 bits / 3 bytes. How many candidate frames does the bit stream contain? What is the length of each candidate frame? Give the length in bytes, not counting start and end markers, or any bitstuffing. What is the index of the first bit in the candidate frame after the marker? (10 marks).
- Which of the candidate frames are valid frames? (A valid frame is a frame whose CRC checksum is correct) (15 marks).
- What is the payload content of each of the valid frames? (15 marks). (You may assume that it is printable 8-bit ASCII text)
- In your answer document, include a marked-up copy of your bitstream that shows, in different colours: 1. all markers (including any generated by noise)
2. frame content between the start and end markers
3. the bits between the "start" and "end markers" of candidate frames that are not valid frames
You may break this copy over multiple lines. (5 marks).
Note: The bitstream above is likely to be much longer than your browser window is wide. Copy it into a text editor that tells you which column your cursor is in, but ensure that you have turned automatic line breaking off. Also, note that the bit stream starts on a random bit, not necessarily at the beginning of what could be a byte. That is, the first marker may not be a multiple of 8 bits away from the start of the bitstream. As transmissions may occur at any time, the number of bits between transmissions is also generally not a multiple of 8.
Part 2 (50/100 marks)
In this part, you are to decode an Ethernet frame from bit level that contains an IP packet carrying a TCP segment without TCP payload. You may assume that the frame was observed on an Ethernet segment between two network devices that could be either end hosts or routers. For simplicity, we assume that the frame checksum at the end and any padding have already been removed from the end of the frame. However, the Ethernet preamble and frame start marker are still present.
In particular, you will need to answer the following questions:
1. What are the destination and source MAC addresses on the current link, and who are the likely vendors/manufacturers of the interface cards at the destination and source ends? (8 marks) 2. Is the sending TCP host ECN-capable, and has a router indicated congestion? (2 marks)
3. How many further hops can the IP packet travel before it must either be received by the destination host or dropped by the router it has reached? (2 marks)
4. What are the source and destination IP addresses in the IP packet? (4 marks)
5. What are the source and destination ports in the TCP header? (4 marks)
6. One of the two TCP hosts involved is a server for a well-known application layer protocol. What is the name of the protocol? (2 marks)
7. Assuming that the initial sequence number sent by the sender (when the SYN flag was set) was 2141, assuming that this packet is not a retransmission, and assuming that no packets were sent out
of order, how many bytes (octets) of TCP payload has the TCP sender sent since? (4 marks)
8. Assuming that the initial sequence number sent by the receiver (when the SYN flag was set) was 4779, how many bytes (octets) of TCP payload has the TCP sender of this TCP packet successfully
received from the receiver since? (4 marks)
9. At the time that this packet was sent, how many bytes worth of capacity was the sender willing to make available in its receive buffers? (2 marks)
10. The section marked "XXXXXXXXXXXXXXXX" is the 16 bit TCP checksum. Calculate the checksum and express it as a 16-bit value. (18 marks) Note: The frame has no 802.1Q tag and the EtherType field indicates IP.
Points to consider: In which order are the bits in Ethernet header octets transmitted? What about IP and TCP headers? Which fields have known values that you can use to check that your working is correct?
For header information, you may wish to consult the following web sites:
https://en.wikipedia.org/wiki/Ethernet_frame
http://standards-oui.ieee.org/oui/oui.txt
https://en.wikipedia.org/wiki/Internet_Protocol
https://en.wikipedia.org/wiki/IPv4_header_checksum (this is also used for the TCP checksum if you include the TCP pseudo header) https://en.wikipedia.org/wiki/Transmission_Control_Protocol
https://en.wikipedia.org/wiki/List_of_TCP_and_UDP_port_numbers
