Tutorial 3 - Wireshark, IPv6, and Routing Tables

Submission process:

  • Submission deadline is November 28, 14:00 CET (before the lecture) .
  • Commit and push your solution as single notebook file via git as ./tutorial/tutorial3/tutorial3.ipynb. Please take care of the correct subfolder/filename since submission is denied otherwise.
  • During the first lecture after the deadline we will discuss a sample solution in class.
  • Afterwards, you have time until December 5, 14:00 CET (before the lecture) to submit a corrected version of your submission:
    1. Rework your solution according to our discussion in class.
    2. Commit and push the corrected version as single file via git as ./tutorial/tutorial3/tutorial3.ipynb. Please take care of the correct filename since submission is denied otherwise.

Remarks:

  • Grading is done based on both versions of your submission.
  • If the first submission is missing your submission will not be graded.
  • If the second submission contains major flaws after revision not more than half of the credits for this tutorial can be achieved.
  • A sample solution is provided after December 5, 14:00 CET eventually.
  • Please use acn@net.in.tum.de for questions regarding lecture, tutorial, and project of ACN.

Problem 1 Wireshark (5 credits)

We consider the following hexdumps. It is known that these dumps represent Ethernet (IEEE 802.3u) frames including L2 headers but without FCS. In the following, we will dissect the whole frames.

To print the hexdump we use the hexdump Python module, which is not installed by default. Run the following cell to install it.

In [1]:
!pip3 install hexdump

Requirement already satisfied: hexdump in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (3.3)

[notice] A new release of pip is available: 23.3.2 -> 24.3.1
[notice] To update, run: pip install --upgrade pip
In [2]:
import binascii
from hexdump import hexdump

def prtyprnt(dump):
    hexdump(dump)
    
# Here is an example how you can compare fields of a bytearray
# bytearray(b'\x01\x02\x03\x04')[2:4] == bytearray(b'\x03\x04')

dump_ipv4 = bytearray(b'\xfc\xe9\x98\x97\xec\xea\x44\xd9\xe7\x00\x40\x01\x08\x00\x45\x00\x00\x38\x00\x00\x00\x00\xf1\x01\x8c\x2b\x3e\x9a\x59\x2e\xac\x13\xf9\xbd\x0b\x00\xbf\x50\x00\x00\x00\x00\x45\x00\x00\x3c\x15\xb2\x00\x00\x01\x11\xea\x81\xac\x13\xf9\xbd\x81\xbb\x91\xf1\xd4\x0f\x82\xbe\x00\x28\xde\xb8')
dump_ipv6 = bytearray(b'\x33\x33\xff\xd7\x6d\xa0\xe0\x3e\x44\x7a\xa7\x34\x86\xdd\x60\x00\x00\x00\x00\x20\x3a\xff\xfe\x80\x00\x00\x00\x00\x00\x00\x02\x25\x90\xff\xfe\x54\x73\x9a\xff\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\xff\xd7\x6d\xa0\x87\x00\x19\xc9\x00\x00\x00\x00\x20\x01\x4c\xa0\x20\x01\x00\x11\x02\x25\x90\xff\xfe\xd7\x6d\xa0\x01\x01\x90\xe2\xba\x7a\xa7\x34')


                    
print('IPv4 packet:')
prtyprnt(dump_ipv4)
print('\nIPv6 packet:')
prtyprnt(dump_ipv6)

IPv4 packet:
00000000: FC E9 98 97 EC EA 44 D9  E7 00 40 01 08 00 45 00  ......D...@...E.
00000010: 00 38 00 00 00 00 F1 01  8C 2B 3E 9A 59 2E AC 13  .8.......+>.Y...
00000020: F9 BD 0B 00 BF 50 00 00  00 00 45 00 00 3C 15 B2  .....P....E..<..
00000030: 00 00 01 11 EA 81 AC 13  F9 BD 81 BB 91 F1 D4 0F  ................
00000040: 82 BE 00 28 DE B8                                 ...(..

IPv6 packet:
00000000: 33 33 FF D7 6D A0 E0 3E  44 7A A7 34 86 DD 60 00  33..m..>Dz.4..`.
00000010: 00 00 00 20 3A FF FE 80  00 00 00 00 00 00 02 25  ... :..........%
00000020: 90 FF FE 54 73 9A FF 02  00 00 00 00 00 00 00 00  ...Ts...........
00000030: 00 01 FF D7 6D A0 87 00  19 C9 00 00 00 00 20 01  ....m......... .
00000040: 4C A0 20 01 00 11 02 25  90 FF FE D7 6D A0 01 01  L. ....%....m...
00000050: 90 E2 BA 7A A7 34                                 ...z.4

a) [0.5 credits] Briefly explain which purpose the FCS serves and how it is computed.

The frame check sequence (FCS) is appended at the end of each frame. Its purpose is to detect bit errors that occur during transfer. For Ethernet the FCS is computed using cyclic redundancy check (CRC). Depending on the CRC polynomial different kinds of errors can be detected. However, burst errors longer than the checksum can never be detected reliably as the error may be a multiple of the CRC polynomial. Note that CRC is normally not used for error correction although very special types of errors are indeed recoverable using CRC. Error correcting codes such has Hamming codes, Reed Solomon Codes, etc. are used by line codes on the physical layer.

b) [0.1 credits] Write the body of the given function extend_hexdump(). The function gets a hexdump without the FCS as an input and should return the extended hexdump with the FCS at the correct position and with the correct length. extend_hexdump() may not modify the original hexdump. You do not need to calculate the correct FCS but can set all bits of the FCS to '1'.

In [3]:
def extend_hexdump(dump):
    # begin insert code
    return dump + bytearray(b'\xFF\xFF\xFF\xFF')
    # end insert code
    return dump
    
prtyprnt(extend_hexdump(dump_ipv4))

00000000: FC E9 98 97 EC EA 44 D9  E7 00 40 01 08 00 45 00  ......D...@...E.
00000010: 00 38 00 00 00 00 F1 01  8C 2B 3E 9A 59 2E AC 13  .8.......+>.Y...
00000020: F9 BD 0B 00 BF 50 00 00  00 00 45 00 00 3C 15 B2  .....P....E..<..
00000030: 00 00 01 11 EA 81 AC 13  F9 BD 81 BB 91 F1 D4 0F  ................
00000040: 82 BE 00 28 DE B8 FF FF  FF FF                    ...(......

c) [0.2 credits] Write two functions which return the source and destination MAC of a given Ethernet frame.

  • getSrcMAC() shall return a bytearray containing the source MAC address
  • getDstMAC() shall return a bytearray containing the destination MAC address
All functions get an Ethernet hexdump as input with the FCS excluded. The functions should work not only on the given hexdumps but on an arbitrary packet hexdump.

In [4]:
def getSrcMAC(dump):
    # begin insert code
    
    # src is the second address in the ethernet frame
    return dump[6:12]
    
    # end insert code
    return dump

prtyprnt(getSrcMAC(dump_ipv6))

00000000: E0 3E 44 7A A7 34                                 .>Dz.4
In [5]:
def getDstMAC(dump):
    # begin insert code
    
    # dst is the first address in the ethernet frame
    return dump[0:6]
    
    # end insert code
    return dump

prtyprnt(getDstMAC(dump_ipv6))

00000000: 33 33 FF D7 6D A0                                 33..m.

d) [0.5 credits] Try to identify the hardware vendors, based on MAC addresses given in the IPv6 hexdump.

  • Dst MAC: 33:33:ff $\longrightarrow$ IPv6 Multicast -- No associated company
  • Src MAC: E0:3E:44 $\longrightarrow$ Broadcom

Taken from http://standards-oui.ieee.org/oui.txt

e) [0.6 credits]

Without knowing that the given hexdump is an Ethernet frame, we would not be able to decode it as we had no clue what the data fields represent. Knowing that it is Ethernet enables us to parse the first header.

  • Write a function that is able to check for a given hexdump whether the frame contains an IPv4 packet as its payload or not.
  • Write a function that is able to check for a given hexdump whether the frame contains an IPv6 packet as its payload or not.
  • Write a function that returns the type of the layer 3 payload. It should return 4/6 for IPv4/IPv6 and None otherwise.

Note: You can assume Ethernet frames without VLANs, i.e., no IEEE 802.3q.

In [6]:
def isIPv4(dump):
    # begin insert code
    
    # Ethertype has fixed position => cut out respective bytes
    ethertype = dump[12:14]
    
    # length check (nice to have but not strictly required for this problem)
    if len(ethertype) == 0:
        print('frame too short')
        return False
    
    # check ethertype value
    # 0x0800 => IPv4
    # A list of standardized Ethertypes is maintained by IANA 
    # (Internet Assigned Numbers Authority)
    # https://www.iana.org/assignments/ieee-802-numbers/ieee-802-numbers.xhtml
    if ethertype == bytearray(b'\x08\x00'):
        return True
    
    # This piece of code only handles Layer 2 not Layer 3.
    # You may additionally check the IP version field but it is not required 
    # for this exercise. Checking only the Layer 3 version field would not
    # suffice as we do not know the header of the Layer 3 protocol without
    # checking Layer 2 first.
    
    # end insert code
    return False

print('Does dump_ipv4 contain a valid IPv4 packet?', isIPv4(dump_ipv4))

Does dump_ipv4 contain a valid IPv4 packet? True
In [7]:
def isIPv6(dump):
    # begin insert code
    
    # Ethertype has fixed position => cut out respective bytes
    ethertype = dump[12:14]
    
    # length check (nice to have but not strictly required for this problem)
    if len(ethertype) == 0:
        print('frame too short')
        return False
    
    # check ethertype value
    # 0x86DD => IPv4
    # A list of standardized Ethertypes is maintained by IANA 
    # (Internet Assigned Numbers Authority)
    # https://www.iana.org/assignments/ieee-802-numbers/ieee-802-numbers.xhtml
    if ethertype == bytearray(b'\x86\xDD'):
        return True
    
    # This piece of code only handles Layer 2 not Layer 3.
    # You may additionally check the IP version field but it is not required 
    # for this exercise. Checking only the Layer 3 version field would not
    # suffice as we do not know the header of the Layer 3 protocol without
    # checking Layer 2 first.
    
    # end insert code
    return False

print('Does dump_ipv6 contain a valid IPv6 packet?', isIPv6(dump_ipv6))

Does dump_ipv6 contain a valid IPv6 packet? True
In [8]:
def getL3Type(dump):
    # begin insert code
        
    # check if IPv4
    if isIPv4(dump):
        return 4
    
    # check if IPv6
    if isIPv6(dump):
        return 6
    
    # return None otherwise
    return None
    
    # end insert code
    return None

print('dump_ipv4 contains IP version {}'.format(getL3Type(dump_ipv4)))
print('dump_ipv6 contains IP version {}'.format(getL3Type(dump_ipv6)))

dump_ipv4 contains IP version 4
dump_ipv6 contains IP version 6

f) [0.5 credits] How can the beginning of the payload be determined for Ethernet frames?

For traditional Ethernet there is a fixed header length (Dst MAC address 6 Byte, Src MAC address 6 Byte, Ethertype 2 Byte). Since the header has a fixed length, there is no need to indicate the beginning of the payload itself.

Later in the lecture we present VLAN (IEEE 802.1Q). For frames following that standard the header length varies. If no VLAN tag is present, the traditional header is used. In case of VLAN tagged frames, the location of the original Ethertype contains a 0x8100, followed by the Tag Control Information (TCI, 16 bit). After that the Ethertype of the payload is defined and after that the payload begins. The header size for frames of this kind is 4 Bytes longer.

According to IEEE 802.1ad (also known as QinQ) it is possible to define two VLANs. There the TCI of the first VLAN is followed by 0x8100 and a second TCI, before the Ethertype of the payload starts. After that the payload begins. The header size for frames of this kind is 4 Bytes longer than IEEE 802.1Q tagged frames.

g) [0.6 credits] How can the beginning of the payload be determined for IP packets? What is the difference between IPv4 and IPv6?

IPv4 has a variable header length and IPv6 can have extension headers after a fixed size header, so the begin of the payload is not fixed.

  • IPv4: header length is defined in the IP header length (IHL) field, these 4 Bit determine the length of the IP header in 32 bit words [RFC 791]
  • IPv6: next header field, defines the following header which can either be the payload, e.g., TCP or an extension header. The extension headers itself have a next header field and a length forming a chain of extension headers. The payload starts after this chain of extension headers. [RFC 8200]

h) [0.6 credits] Write three functions:

  • cutL2PDU() shall return a bytearray containing the Layer 2 PDU
  • cutL2SDU() shall return a bytearray containing the Layer 2 SDU
  • cutIPPDU() shall return a bytearray containing the Layer 3 PDU.
    cutIPPDU() should only cut out valid IPv4 or IPv6 packets. In case no IPv4 or IPv6 packet is found an empty bytearray should be returned.

All functions get an Ethernet hexdump as input with the FCS excluded. The functions should work not only on the given hexdump but on an arbitrary packet hexdump. For this exercise you can assume correct packets, i.e. your functions do not need to validate the given data.

In [9]:
def cutL2PDU(dump):
    # begin insert code
    
    # Validation of packet data was omitted intentionally.
    
    # The protocol data unit (PDU) contains the header and the payload.
    # No changes required for the given input data.
    
    # end insert code
    return dump

prtyprnt(cutL2PDU(dump_ipv4))

00000000: FC E9 98 97 EC EA 44 D9  E7 00 40 01 08 00 45 00  ......D...@...E.
00000010: 00 38 00 00 00 00 F1 01  8C 2B 3E 9A 59 2E AC 13  .8.......+>.Y...
00000020: F9 BD 0B 00 BF 50 00 00  00 00 45 00 00 3C 15 B2  .....P....E..<..
00000030: 00 00 01 11 EA 81 AC 13  F9 BD 81 BB 91 F1 D4 0F  ................
00000040: 82 BE 00 28 DE B8                                 ...(..
In [10]:
def cutL2SDU(dump):
    # begin insert code

    # Validation of packet data was omitted intentionally.
    
    # The service data unit (SDU) contains only the payload data
    # This requires the header to be removed from the layer 2 frame
    
    return dump[14:len(dump)]

    # end insert code
    return dump

prtyprnt(cutL2SDU(dump_ipv4))

00000000: 45 00 00 38 00 00 00 00  F1 01 8C 2B 3E 9A 59 2E  E..8.......+>.Y.
00000010: AC 13 F9 BD 0B 00 BF 50  00 00 00 00 45 00 00 3C  .......P....E..<
00000020: 15 B2 00 00 01 11 EA 81  AC 13 F9 BD 81 BB 91 F1  ................
00000030: D4 0F 82 BE 00 28 DE B8                           .....(..
In [11]:
def cutIPPDU(dump):
    # begin insert code
    
    # L2 SDU == L3 PDU

    # check if there is IPv4 
    if isIPv4(dump) or isIPv6(dump):
        return cutL2SDU(dump)
    else:
        return bytearray()
    
    # end insert code
    return dump

prtyprnt(cutIPPDU(dump_ipv4))

00000000: 45 00 00 38 00 00 00 00  F1 01 8C 2B 3E 9A 59 2E  E..8.......+>.Y.
00000010: AC 13 F9 BD 0B 00 BF 50  00 00 00 00 45 00 00 3C  .......P....E..<
00000020: 15 B2 00 00 01 11 EA 81  AC 13 F9 BD 81 BB 91 F1  ................
00000030: D4 0F 82 BE 00 28 DE B8                           .....(..

i) [0.2 credits] Write a function which helps to identify the type of payload an IPv4 or IPv6 packet is carrying. You can assume that the identifyPayploadIP() gets an Ethernet hexdump as input with the FCS excluded. It should return a bytearray containing the L4 payload identifier or an empty bytearray if neither an IPv4 nor an IPv6 payload was found.

Hint: you can assume that there are no Extension Headers within the IPv6 packets.

In [12]:
def identifyPayloadIP(dump):
    # begin insert code
    
    ip_pdu = cutIPPDU(dump)
    if getL3Type(dump) == 4:
        # Protocol field contains protocol of payload
        return ip_pdu[9:10] 
    elif getL3Type(dump) == 6:
        # Next Header field contains protocol of payload in this case
        return ip_pdu[6:7]
    else:
        # Return an empty byterarry otherwise
        return bytearray() 
    
    # end insert code
    return dump

prtyprnt(identifyPayloadIP(dump_ipv4))
prtyprnt(identifyPayloadIP(dump_ipv6))

00000000: 01                                                .
00000000: 3A                                                :

j) [0.2 credits] Based on your answer of i), what are the protocols contained in the two given hexdumps.

Protocol numbers are also maintained by the IANA. The IPv4 header contains a protocol field. Its value 0x01 identifies the L3-SDU as ICMPv4. The IPv6 header contains a next header field. Its value 0x3a identifies the L3-SDU as ICMPv6.

k) [0.5 credits] Explain the payload (header fields and the content type) of the IPv4 packet identified in j).

Knowing that the L3 SDU is ICMPv4, we can identify the content using the ICMPv4 type and code header fields yielding Time Exceeded / TTL expired in transit. For those ICMP messages the following 4 B are unused and thus set to zero. The payload consists in the IPv4 header of the original message that timed out plus the first 8 B of the following header.

We can thus parse this IPv4 header and find that the payload must be UDP as the protocol field is 0x11. The last 8 B are thus a UDP header containing in particular source and destination port numbers.

l) [0.5 credits] Explain the payload (header fields and the content type) of the IPv6 packet identified in j) and how this relates to the answer in d).

The IPv6 dump contains the ICMPv6 NDP neighbor solicitation message for 2001:4ca0:2001:11:225:90ff:fed7:6da0. As the Source does not know the destinations MAC address it sends it to the IPv6 multicast address.

Problem 2 IPv6 (3.5 credits)

IPv6 is the successor if IPv4. Instead of 32 bits, 128 bits are used for each address. This offers enough space for many different address types. However, the text representation of the addresses becomes more complex as well.

a) [1 credits] Write a function convert_ipv6.

The function receives a bytearray containing a valid IPv6 address and should return the shortest possible string representation of the address. Make sure the following requirements are fulfilled.

  • remove leading zeros for each byte-pair (do not remove trailing ones)
  • the longest serie of consecutive 0s can be merged with ::
  • your function implementation should be able to correctly handle any given IPv6 address

Remark: For this problem you are not allowed to use any modules like ipaddress.

In [13]:
def convert_ipv6(address):
    # begin insert code
    
    out = []
    zero_len = 0
    zero_start = None
    max_zero_len = 0
    max_zero_start = None

    for i, b in enumerate(address[::2]):
        part = '{:02x}{:02x}'.format(address[i*2], address[i*2+1])
        part = part.lstrip('0') or '0'
        
        if part == '0':
            if zero_start is None:
                zero_start = i
                zero_len = 0
            zero_len += 1
    
        if part != '0' or i == 7:
            if zero_len > max_zero_len:
                max_zero_len = zero_len
                max_zero_start = zero_start
            zero_start = None
        out.append(part)

    if max_zero_start is not None:
        return '::'.join([
            ':'.join(out[:max_zero_start]),
            ':'.join(out[max_zero_start+max_zero_len:])
        ])
    
    return ':'.join(out)
    # end insert code
    return str(address)



ipv6 = bytearray(b'\xff\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\xff\xd7\x6d\xa0')
# should convert to ff02::1:ffd7:6da0
convert_ipv6(ipv6)
Out[13]:
'ff02::1:ffd7:6da0'

Stateless Address Auto Configuration (SLAAC) is a protocol to automatically set up Link-Local addresses. RFC 4291 describes in Section 2.5.6 how Link-Local addresses are computed using the device's MAC address.

b) [0.5 credits] Write a function generate_link_local.

The functions receives a bytearray containing a MAC address and should return a bytearray with the corresponding Link-Local address.

Remark: For this problem you are not allowed to use any modules like ipaddress.

In [14]:
def generate_link_local(mac):
    # begin insert code
    
    addr = bytearray(16)      # create an empty bytearray of size 16
    addr[:2] = b'\xfe\x80'    # set Link-Local prefix
    addr[8] = mac[0] ^ 0x02   # flip 7th bit of the first octet of the mac address
    addr[9:] = mac[1:3]       # set remaining 2 octets from the mac address
    addr[11:] = b'\xff\xfe'   # insert 0xfffe
    addr[13:] = mac[3:]       # set last 3 bytes of the mac address
    return addr

    # end insert code
    return bytearray(16)


mac = bytearray(b'\x01\x02\x03\x04\x05\x06')
convert_ipv6(generate_link_local(mac ))
Out[14]:
'fe80::302:3ff:fe04:506'

IPv6 Multicast Address spaces are defined in RFC 4291 in Section 2.7. For Neigbor Discovery the Solicited-Node Address is used.

c) [0.5 credits] Write two functions:

  • compute_solicited_node_multicast, which gets as input a bytearray containing an IPv6 address and returns a bytearray containing the Solicited-Node Multicast address of the IPv6 address.
  • compute_multicast_mac, which gets as input a bytearray containing an IPv6 address and returns a bytearray containing the multicast MAC address as specified in RFC 2464 in Section 7.

In [15]:
def compute_solicited_node_multicast(ipv6):
    # begin insert code
    
    # From RFC4291: FF02:0:0:0:0:1:FFXX:XXXX
    # With XX:XXXX being the last 3 bytes of the IPv6 address
    
    addr = bytearray(16)
    addr[:2] = b'\xff\x02'
    addr[11:12] = b'\x01'
    addr[12:] = b'\xff'
    addr[13:] = bytearray(ipv6[-3:])
    return addr

    # end insert code
    return ipv6


def compute_multicast_mac(ipv6):
    # begin insert code
    
    solicited = compute_solicited_node_multicast(ipv6)
    addr = bytearray(6)
    addr[0:2] = b'\x33\x33'
    addr[2:] = solicited[-4:]
    return addr

    # end insert code
    return bytearray(6)


ipv6 = bytearray(b'\x20\x01\x4c\xa0\x20\x01\x00\x40\xe1\x14\x90\xfe\x38\x62\x55\x4f')
print(convert_ipv6(compute_solicited_node_multicast(ipv6)))

mac = compute_multicast_mac(ipv6)
print('{:02x}:{:02x}:{:02x}:{:02x}:{:02x}:{:02x}'.format(*mac))

ff02::1:ff62:554f
33:33:ff:62:55:4f

In the next subproblem you will analyze how IPv6 addresses are distributed. First you will download a file from the ACN website which contains two datasets with different IPv6 addresses.

Run the following cell to download the file and print some sample values from each dataset.

In [16]:
# Download IPv6 address lists from ACN website
!wget -nc https://acn.net.in.tum.de/exercise/ipv6_dataset.npz -O /tmp/ipv6_dataset.npz
# Load file into Python
import numpy as np
data = np.load('/tmp/ipv6_dataset.npz')

# Print sample data
print('Dataset 1:')
print('\n'.join(map(convert_ipv6, data['dataset1'][:3])))
    
print('\nDataset 2:')
print('\n'.join(map(convert_ipv6, data['dataset2'][:3])))


7[Files: 0  Bytes: 0  [0 B/s] Re]8
7[https://acn.net.in.tum.de/exer]87Saving '/tmp/ipv6_dataset.npz'
87/tmp/ipv6_dataset.np 100% [=============================>]    3.05M    --.-KB/s87HTTP response 200  [https://acn.net.in.tum.de/exercise/ipv6_dataset.npz]
87/tmp/ipv6_dataset.np 100% [=============================>]    3.05M    --.-KB/s87[Files: 1  Bytes: 3.05M [15.65M]8
Dataset 1:
8961:9391:9596:a6c8:bebf:4624:befc:d2e1
b08d:a07b:88a2:5cce:e06a:ca30:84a3:ae78
6fe6:f3d0:bd90:f2b3:8cf2:e222:2a59:d4b6

Dataset 2:
19b0:3e8d:50a7:9ac4:20::1
efe4:a1b1:8bba:ca58::1
8241:fa7b:6b37:5a0d::200:0:1

d) [0.5 credits] Write a function count_ones.

The function receives a bytearray containing an IPv6 address and should return the number of bits set to 1 in the last 64 bits of the IPv6 address.

In [17]:
def count_ones(ipv6):
    # begin insert code
    
    ipv6 = ''.join(map(lambda i: "{0:08b}".format(i), ipv6[8:])) # convert address to bitstring
    return ipv6.count('1')

    # end insert code
    return 0

Once you finished the previous subproblem you can run the following cell which plots the distributions of bits set to one for each dataset.

In [18]:
%matplotlib inline
import matplotlib.pyplot as plt

def plot_histogram(dataset1, dataset2):
    
    fig, axis = plt.subplots(1, 2, figsize=(15, 4))
    axis[0].hist(list(map(count_ones, dataset1)), bins=64, range=(0,64), density=True)
    axis[1].hist(list(map(count_ones, dataset2)), bins=64, range=(0,64), density=True)
    axis[0].set(xlabel='# of 1', ylabel='Density', title='Dataset 1')
    axis[1].set(xlabel='# of 1', ylabel='Density', title='Dataset 2')
    fig.show()
    
plot_histogram(data['dataset1'], data['dataset2'])

/tmp/ipykernel_35625/3498065665.py:11: UserWarning: FigureCanvasAgg is non-interactive, and thus cannot be shown
  fig.show()
No description has been provided for this image

e) [1 credits] Explain how the addresses in the two datasets differ. Give a reason for the differences and what kind of addresses are most likely contained in each dataset.

The number of ones of the addresses in dataset1 approximates a normal distribution with a mean of 32. This means that each individual bit is set to 1 with a probability of 0.5. The reason for this is that the addresses were generated automatically using the IPv6 privacy extension.

The addresses in dataset2 follow a different distribution. There only a few bits are set to 1, which results from these addresses being assigned manually (e.g. by network admins) and tend to a more human readable form.

Problem 3 Routing Tables (4 credits)

For this exercise consider the following entries for a routing table.

In [19]:
import ipaddress

route_entries = [
           # the following entries specify a destination network and an egress interface id
           (ipaddress.IPv4Network('192.0.2.0/30'), 4),
           (ipaddress.IPv4Network('10.0.0.4/30'), 0),
           (ipaddress.IPv4Network('192.0.2.2/31'), 5),
           (ipaddress.IPv4Network('192.0.2.8/29'), 4),
           (ipaddress.IPv4Network('10.0.8.0/24'), 1),
           (ipaddress.IPv4Network('10.0.9.0/24'), 5),
           (ipaddress.IPv4Network('0.0.0.0/0'), 2),
           (ipaddress.IPv4Network('10.0.0.8/30'), 0),
           (ipaddress.IPv4Network('192.0.2.4/30'), 4),
           (ipaddress.IPv4Network('10.0.10.0/24'), 4),
           (ipaddress.IPv4Network('10.0.11.0/24'), 1) 

]

a) [0.25 credits] What is the route entry pointing to egress interface 2?

This is a way of describing the default route for the given route entries.

b) [0.5 credits] Create a function which calculates the minimum number of bits necessary for encoding the egress interfaces. The function gets a list of interfaces, e.g., route_entries.

In [20]:
import math

def bits_interfaces(entries):
    # begin insert code
    
    # This exercise uses the number of different interfaces,
    # i.e. length of the set of interface names
    # rather than the maximum value of any interface.
    # 
    # In case non-integer names for interfaces are chosen the
    # routing table might become unnecessarily big, so renaming
    # the interfaces (e.g. 'eth0' -> 0) saves memory, increases
    # cache utilization and saves memory.
    #
    # Due to a common misinterpretation of the problem description
    # also the max() of the given interface ids was accepted.    
    
    egressset = set()
    for entry in entries:
        egressset.add(entry[1])
    print("Set of available interfaces: ", egressset)
    return math.ceil(math.log2(len(egressset)))

    # end insert code  
    return 0

print(str(bits_interfaces(route_entries)) + " bits are required for encoding the given interfaces.")

Set of available interfaces:  {0, 1, 2, 4, 5}
3 bits are required for encoding the given interfaces.

c) [1.5 credits] Simplify the given routing table by aggregating the route entries if possible. Write a brief comment for every aggregation you are performing. Adhere to the format shown in route_entries.

Note: Keep in mind that for LPM more specific entries have precedence over less specific entries even if the input data is not sorted!

In [21]:
compressed_entries = [
    # begin insert code  
   
    # Sort the entries according to LPM
    
    # When LPM works correctly always the route with the longest matching prefix is chosen
    # even when the entries are not sorted.
    
    # networks can be aggregated as they have same network address
    # there are no gaps between networks
    # can be aggregated as they point to the same interface:
    #   (ipaddress.IPv4Network('192.0.2.0/30'), 4),
    #   (ipaddress.IPv4Network('192.0.2.4/30'), 4),
    #   (ipaddress.IPv4Network('192.0.2.8/29'), 4),
    (ipaddress.IPv4Network('192.0.2.0/28'), 4),
   
    # cannot be aggregated with the other addresses 
    # as the entry points to a different interface
    (ipaddress.IPv4Network('192.0.2.2/31'), 5),

    # cannot be aggregated due to incompatible network address:
    # '10.0.0.4/30' is part of 10.0.0.0/29
    # '10.0.0.8/30' is part of 10.0.0.8/29
    #
    # both entries could theoretically be combined into 10.0.0.0/28
    # however in this case wrong routes are introduced,
    # i.e. 10.0.0.2 originally takes the default route
    # if 10.0.0.0/28 would be in place the take this route
    (ipaddress.IPv4Network('10.0.0.4/30'), 0),
    (ipaddress.IPv4Network('10.0.0.8/30'), 0),
   
    # entries to egress interface 1 have same prefix and can be aggregated
    # entries to egress interfaces 4 & 5 must remain due to different egress interface
    #
    # In this special case '10.0.8.0/24' and '10.0.11.0/24' can be aggregated into
    # '10.0.8.0/22' despite there are gaps in between the original subnets
    # because there are more specific routes in place which make correct routing possible
    #   (ipaddress.IPv4Network('10.0.8.0/24'), 1),
    (ipaddress.IPv4Network('10.0.9.0/24'), 5),
    (ipaddress.IPv4Network('10.0.10.0/24'), 4),
    #   (ipaddress.IPv4Network('10.0.11.0/24'), 1), 
    (ipaddress.IPv4Network('10.0.8.0/22'), 1), 

    (ipaddress.IPv4Network('0.0.0.0/0'), 2)
    # end insert code
]
    
print(compressed_entries)

[(IPv4Network('192.0.2.0/28'), 4), (IPv4Network('192.0.2.2/31'), 5), (IPv4Network('10.0.0.4/30'), 0), (IPv4Network('10.0.0.8/30'), 0), (IPv4Network('10.0.9.0/24'), 5), (IPv4Network('10.0.10.0/24'), 4), (IPv4Network('10.0.8.0/22'), 1), (IPv4Network('0.0.0.0/0'), 2)]

d) [0.5 credits] Consider the LPM introduced in the lecture as naive LPM. For this approach to work the routing table entries must be sorted according to their prefix length. Why must the input be sorted according to the prefix length? Give an example what could happen if the input would not be sorted this way.

The entries must be sorted so that the most specific entries are matched before any other entry. By putting the longest prefixes first, a hit for the most specific entry is guaranteed, as less specific matching entries are sorted towards the end of the list.

An intuitive example for a wrong match would be to put the default route at the beginning of the route entries. Every possible entry matches against the default route, so every packet would be routed towards the default gateway with possibly more specific entries ignored.

e) [0.5 credits] Implement the naive LPM as presented in the lecture. Your lookup() function gets a (possibly unsorted) list of routing table entries and an IP address as input. It must return the egress interface id of the most specific route for the given IP address.

In [22]:
def lookup(entries, lookup_addr):
    # begin insert code
    
    # sort entries
    sentries = sorted(entries, key=lambda x: x[0].prefixlen, reverse=True)
    
    # perform lookup (short solution)
    for network, egressID in sentries:
        if lookup_addr in network:
            return egressID

    # should never be reached (if there is a default route)
    return -1
    
    # end insert code
    return 0


addr = ipaddress.ip_address('1.0.8.4')

print("Send packet towards interface:", lookup(route_entries, addr))

Send packet towards interface: 2

Routing tables are a crucial part of router performance. For routing tables, the number of memory accesses or comparisons necessary for a lookup are an important metric. In case of a routing table a comparison is performed between the network address of the route to look up with the routes given in the routing table. The following subproblems analyze the complexity of your implementation.

You may ignore the complexity of the sorting operation for this example. Use the non-compressed routing table entries for your analysis.

f) [0.5 credits] Give the number of comparisons between the entry list and the address for your LPM implementation. Give the numbers in the best case scenario and the worst case scenario including an example IP address.

  • Only a single comparison is necessary if matching against the first entry in the list which is (ipaddress.IPv4Network('192.0.2.2/31'), 5). Sample address: 192.0.2.2
  • The address must be compared to every entry in the list if only the last entry matches. In our case this is the default route. Sample address: 172.16.0.1

g) [0.25 credits] Give the worst case analysis for the comparison of your LPM in the Big O notation depending on the number of routing table entries $n$.

For every entry one comparison has to be performed in the worst case: $\mathcal{O}(n)$.

Advanced Computer Networking by Prof. Dr.-Ing. Georg Carle

Teaching assistants: Christian Dietze, Sebastian Gallenmüller, Max Helm, Benedikt Jaeger, Marcel Kempf, Jihye Kim, Patrick Sattler