Tutorial 3 - Autonomous Systems & Routing Tables

Submission process:

  • Submission deadline is November 27, 14:00 CET (before the lecture) .
  • Commit and push your solution as separate notebook files per subtask via git as ./tutorial/tutorial3/tutorial3_2.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 02, 16: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 a separate file per subtask via git as ./tutorial/tutorial3/tutorial3_2.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 02, 16:00 CET eventually.
  • Do NOT duplicate cells or change the type of cells, otherwise you might receive zero points for your submission
  • Please use acn@net.in.tum.de for questions regarding lecture, tutorial, and project of ACN.

Problem 2 Routing Tables (4 credits)

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

In [1]:
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 [2]:
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.
In [ ]:

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 [3]:
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)]
In [ ]:
In [ ]:
In [ ]:

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 [4]:
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))
for i in route_entries:
    print(i)

Send packet towards interface: 2
(IPv4Network('192.0.2.0/30'), 4)
(IPv4Network('10.0.0.4/30'), 0)
(IPv4Network('192.0.2.2/31'), 5)
(IPv4Network('192.0.2.8/29'), 4)
(IPv4Network('10.0.8.0/24'), 1)
(IPv4Network('10.0.9.0/24'), 5)
(IPv4Network('0.0.0.0/0'), 2)
(IPv4Network('10.0.0.8/30'), 0)
(IPv4Network('192.0.2.4/30'), 4)
(IPv4Network('10.0.10.0/24'), 4)
(IPv4Network('10.0.11.0/24'), 1)
In [ ]:

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, Marcel Kempf, Lorenz Lehle, Nikolas Gauder, Patrick Dirks