diff options
| -rw-r--r-- | assignment5.tex | 108 | ||||
| -rwxr-xr-x | assignment5/traceroute.py | 140 |
2 files changed, 248 insertions, 0 deletions
diff --git a/assignment5.tex b/assignment5.tex new file mode 100644 index 0000000..8289bea --- /dev/null +++ b/assignment5.tex @@ -0,0 +1,108 @@ +\documentclass[a4paper,9pt]{article} + +\author{Camil Staps\\\small{s4498062}} +\title{Networking\\\large{Assignment 5}} +\date{April 27, 2016} + +\usepackage{polyglossia} +\setmainlanguage{english} +\usepackage{geometry} +\usepackage{enumitem} +\setenumerate{label=\alph*)} +\usepackage{amsmath} +\usepackage{minted} + +\begin{document} + +\maketitle + +\section{Packet forwarding} +\begin{enumerate} + \item + \begin{tabular}{l | l} + Dest. addr. & Interface \\\hline + H1 & 1 \\ + H2 & 2 \\ + H3 & 3 \\ + \end{tabular} + + \item No: in a datagram network, the forwarding table entries are tuples of + destination address prefixes and link interfaces. There is no way to + distinguish packets coming from host H1 from packets coming from host H2. + + \item + \begin{tabular}{l | l | l | l} + \multicolumn{2}{c|}{Incoming} & \multicolumn{2}{c}{Outgoing} \\\hline + Interface & VC\# & Interface & VC\# \\\hline + 1 & 13 & 3 & 23 \\ + 2 & 37 & 4 & 47 \\ + \end{tabular} + + \item + \begin{enumerate}[label=\Alph*.] + \setcounter{enumii}{1} + \item + \begin{tabular}{l | l | l | l} + \multicolumn{2}{c|}{Incoming} & \multicolumn{2}{c}{Outgoing} \\\hline + Interface & VC\# & Interface & VC\# \\\hline + 1 & 23 & 2 & 33 \\ + \end{tabular} + + \item + \begin{tabular}{l | l | l | l} + \multicolumn{2}{c|}{Incoming} & \multicolumn{2}{c}{Outgoing} \\\hline + Interface & VC\# & Interface & VC\# \\\hline + 1 & 47 & 2 & 57 \\ + \end{tabular} + + \item + \begin{tabular}{l | l | l | l} + \multicolumn{2}{c|}{Incoming} & \multicolumn{2}{c}{Outgoing} \\\hline + Interface & VC\# & Interface & VC\# \\\hline + 1 & 33 & 3 & 43 \\ + 2 & 57 & 3 & 67 \\ + \end{tabular} + \end{enumerate} +\end{enumerate} + +\section{Switching} +\begin{enumerate}[label=\arabic*.] + \item Only one packet can be handled at the same time, so we may have to wait + for $n-1$ packets. That gives a delay of $(n-1)\cdot D$. + \item Every packet goes to a different output port, so we will never go over + the bus bandwidth (which is at least 1). Therefore, there is no queuing + delay in this case. + \item Every packet goes to a different output port and therefore uses a + different vertical bar in the interconnection network. Queuing can only + occur when two packets need the same vertical line, but as explained this + cannot happen. Therefore, there is no queuing delay in this case either. +\end{enumerate} + +\section{Subnets} +223.1.17.128/26 can support up to 64 addresses (so also 60).\\ +223.1.17.0/25 can support up to 128 addresses (so also 90).\\ +223.1.17.192/26 can support up to 64 addresses (so also 12). + +The subnets do not conflict; their binary prefixes in the last byte are +\texttt{10}, \texttt{0} and \texttt{11} respectively. + +\section{ICMP Traceroute} +\texttt{do\_one\_ping} and the underlying functions have been adapted to return +a tuple \texttt{(address, icmp\_type)} (or \texttt{(None, None)} in case of a +timeout). + +The function \texttt{ping} has been replaced by \texttt{traceroute}. This uses +a counter \texttt{i} to increase the TTL of the echo requests we send. For each +TTL we call \texttt{do\_one\_ping} which gives us either \texttt{(None, None)} +if no server responded, or \texttt{(address, icmp\_type)}, where +\texttt{icmp\_type} is either \texttt{ICMP\_ECHO\_REPLY} or +\texttt{ICMP\_TIME\_EXCEEDED}. We can use this to stop (in case of a reply) or +continue (in case of a TTL excess). + +The logic may be found in \texttt{traceroute}: + +\inputminted[linenos,xleftmargin=1cm,firstline=102,lastline=118]{python}% + {assignment5/traceroute.py} + +\end{document} + diff --git a/assignment5/traceroute.py b/assignment5/traceroute.py new file mode 100755 index 0000000..68f2d36 --- /dev/null +++ b/assignment5/traceroute.py @@ -0,0 +1,140 @@ +#!/usr/bin/env python +"""Python implementation of the Unix traceroute program""" +import argparse +import os +import socket +import struct +import sys +import time + +ICMP_ECHO_REQUEST = 8 +ICMP_ECHO_REPLY = 0 +ICMP_TIME_EXCEEDED = 11 + + +def checksum(str_): + """The ICMP checksum as defined in RFC 792""" + str_ = bytearray(str_) + csum = 0 + count_to = (len(str_) // 2) * 2 + + for count in range(0, count_to, 2): + this_val = str_[count+1] * 256 + str_[count] + csum = csum + this_val + csum = csum & 0xffffffff + + if count_to < len(str_): + csum = csum + str_[-1] + csum = csum & 0xffffffff + + csum = (csum >> 16) + (csum & 0xffff) + csum = csum + (csum >> 16) + answer = ~csum + answer = answer & 0xffff + answer = answer >> 8 | (answer << 8 & 0xff00) + return answer + + +def receive_one_ping(my_socket, rec_id, timeout): + """Attempt to receive a ping. + + Arguments: + my_socket -- a Python socket to receive from + rec_id -- only receive packets with this identifier (in case of echo reply) + timeout -- timeout in seconds + + Return value: + A tuple (responding server, icmp message type) + """ + start_time = time.time() + + while (start_time + timeout - time.time()) > 0: + try: + rec_packet, _ = my_socket.recvfrom(1024) + except socket.timeout: + break # timed out + + # Fetch the ICMPHeader fromt the IP + icmp_header = rec_packet[20:28] + source_ip = '%d.%d.%d.%d' % struct.unpack("BBBB", rec_packet[12:16]) + + icmp_type, _, _, packet_id, _ = struct.unpack("bbHHh", icmp_header) + + if icmp_type == ICMP_TIME_EXCEEDED or \ + icmp_type == ICMP_ECHO_REPLY and packet_id == rec_id: + return (source_ip, icmp_type) + + return None, None + +def send_one_ping(my_socket, dest_addr, snd_id, ttl=30): + """Send an ICMP echo message""" + # Make a dummy packet with a 0 checksum + header = struct.pack("bbHHh", ICMP_ECHO_REQUEST, 0, 0, snd_id, 1) + data = struct.pack("d", time.time()) + + # Calculate the checksum on the data and the dummy header. + my_checksum = socket.htons(checksum(header + data)) + if sys.platform == 'darwin': + my_checksum = my_checksum & 0xffff + + header = struct.pack("bbHHh", ICMP_ECHO_REQUEST, 0, my_checksum, snd_id, 1) + packet = header + data + + my_socket.setsockopt(socket.SOL_IP, socket.IP_TTL, ttl) + my_socket.sendto(packet, (dest_addr, 1)) + + +def do_one_ping(dest_addr, timeout, ttl=30): + """Send one echo and receive either an echo reply or a time exceeded msg""" + icmp = socket.getprotobyname("icmp") + + my_socket = socket.socket(socket.AF_INET, socket.SOCK_RAW, icmp) + my_socket.settimeout(timeout) + + my_id = os.getpid() & 0xffff + send_one_ping(my_socket, dest_addr, my_id, ttl) + response = receive_one_ping(my_socket, my_id, timeout) + + my_socket.close() + return response + + +def traceroute(host, timeout=1.0, hops=10): + """Python version of the Unix traceroute program""" + dest = socket.gethostbyname(host) + print 'traceroute to %s (%s), %d hops max' % (host, dest, hops) + + i = 0 + while i < hops: + i += 1 + address, icmp_type = do_one_ping(dest, timeout, ttl=i) + if address == None: + print '%2d *' % i + else: + name, _, _ = socket.gethostbyaddr(address) + print '%2d %s (%s)' % (i, name, address) + + if icmp_type == ICMP_ECHO_REPLY: + break + + +def main(): + """Wrapper for traceroute to get host from the command line""" + parser = argparse.ArgumentParser(description='Traceroute') + parser.add_argument( + 'host', metavar='HOST', type=str, nargs=1, + help='The host to traceroute to') + parser.add_argument( + '--timeout', type=float, default=1.0, + help='Number of seconds to wait for response to a probe (default 1.0)') + parser.add_argument( + '--hops', type=int, default=10, + help='Maximum number of hops (default 10)') + + args = parser.parse_args() + traceroute(args.host[0], timeout=args.timeout, hops=args.hops) + + +if __name__ == '__main__': + main() + |