Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / CPS 470/570: Computer Networks Assignment 3, 100 points, two weeks This is NOT a team project
CPS 470/570: Computer Networks
Assignment 3, 100 points, two weeks
This is NOT a team project. Receive an F for this course if dishonesty occurs. Receive 5 bonus points if submit it without errors one day before the deadline
Implement the sequential version of traceroute. Receive 10 bonus points if you implement the parallel version of traceroute.
Several issues you should pay attention to:
Traceroute operates by sending a sequence of probes (i.e., packets) towards a given destination
D. As these probes work their way toward to D, they pass through a series of routers. A preset TTL (time-to-live) value (e.g., TTL=5) is carried in the packet. Every time the packet is forwarded from a router to its adjacent router, the TTL value is decremented by 1. The packet is forwarded in the network until TTL reaches zero.
In your implementation, each probe i has the TTL value set to i, which causes router i along the path to discard the packet and generate/return a “TTL expired” message (see Section 2.4 below). By successively setting TTL from 1 to N, where N is the number of hops in the path, traceroute obtains the IP addresses of each router. Performing reverse DNS lookups on these addresses, traceroute also prints the DNS names of these routers.
Sample execution of your Traceroute:
www.google.com
Tracing route to www.google.com [172.217.4.68] A maximum of 30 hops:
Trace complete.
Columns from left to right refer to: 1) hop number (i.e., TTL value); 2) DNS name of the router at that TTL (empty if a router does not have a DNS name); 3) IP address of the router; 4) one RTT measurement; 5) how many probes were sent with this value of TTL. The reason for having multiple probes is that some of them may be lost and a retransmission may be required.
Traceroute is implemented with ICMP messages (see textbook). The following instructions help you send/receive ICMP packets to destination D.
2
Our task is to implement the methods defined in class RawSocket:
# rawsocket.py import sys, socket, struct, select, time
#import os
# ================ global constants ====================================#
TIMEOUT = 5 # timeout in seconds
MAX_DATA_SIZE = ?? # bytes in data field
ICMP_ECHOREPLY = 0 # Echo reply (per RFC792)
ICMP_ECHO = 8 # Echo request (per RFC792)
ICMP_MAX_RECV = 2048 # Max size of incoming buffer
# =======================================================================# class RawSocket: def __init__(self, remotehost): # constructor. See below
def getIP(self, hostname): # return its IP address. Same as AS#1
def createRawSocket(self): # create a raw socket. Completed. def checksum(self, packet): # parameter packet in bytes. Completed. def sendPing(self, ttl): # ping remotehost, ttl is an int. Completed.
def recvPing(self): # recv msg, return True ie reach destination. See below def close(self): # call sock.close(). Same as AS#1
def trace(self): # See below
…
# constructor: create an object, initialize instance variables
def __init__(self, remotehost):
self.sock = None # raw socket's handler
self.remotehost = remotehost # tracert to the destination
self.ttl = 1 # ttl for this icmp packet self.port = 33435 # port number
self.ip = self.getIP(remotehost) # call socket.gethostbyname() to get IP print("ping to ip = ", self.ip) # print msg for debugging self.myID = 1234 # id for this icmp packet self.seqNumber = 0 # sequence number for this icmp pkt
In order to send and receive ICMP packets, you will need an ICMP socket:
def createRawSocket(self):
try:
self.sock = socket.socket( family = socket.AF_INET, type = socket.SOCK_RAW, # type: raw socket proto = socket.IPPROTO_ICMP # protocol: ICMP
) except socket.error as e:
print("failed. (socket error: '%s')" % e.args[1]) raise # raise the original error return # end oe this eunction
After you create a raw socket, no need to bind port number to the socket. No need to call function connect(). For raw sockets, we will call the functions sendto() in our method sendPing() and call recvfrom() in our method recvPing().
The structure of the ICMP header is shown in Figure 1. The first two fields are used to signal which type of ICMP message is carried in the packet (see textbook for the various values). The ID and Sequence Number fields should be used to match router responses to the transmitted packets (see below).
8 bits 8 bits
Type Code Checksum
ID Sequence number
32 bits
Figure 1. ICMP header (8 bytes).
def sendPing(self, ttl):
""" Create an icmp packet eirst, then use raw socket to sendto this packet """
#Header has 8 bytes: type (8), code (8), checksum (16), id (16), sequence (16) checksum = 0 # initialize checksum to 0
# Create a ICMP header using struct.pack() with a checksum (which is 0):
# In “BBHHH” B means one byte and H means 2 bytes header = struct.pack("!BBHHH", ICMP_ECHO, 0, checksum, self.myID, self.seqNumber) data = bytes(MAX_DATA_SIZE) # bytes oe zeros packet = header + data
checksum = self.checksum(packet) # call eunction to compute checksum
# Now that we have the correct checksum, put that in header. Create a new header
header = struct.pack("!BBHHH", ICMP_ECHO, 0, checksum, self.myID, self.seqNumber)
packet = header + data # Packet ready. We can send it to the Internet … # more code below
def checksum(self, packet): # packet’s type is: bytes. Done already.
""" Return checksum oe a packet (including header and data). Network data is big-endian, hosts are typically little-endian """ evenLength = (int(len(packet) / 2)) * 2 sum = 0
for count in range(0, evenLength, 2): # handle two bytes each time
sum = sum + (packet[count + 1] * 256 + packet[count]) #low byte is at [count]
if evenLength < len(packet): # ie handle last byte ie odd-number oe bytes
sum += packet[-1] # get last byte
sum &= 0xffffffff # Truncate sum to 32 bits (a variance erom ping.c) sum = (sum >> 16) + (sum & 0xffff) # Add high 16 bits to low 16 bits
sum += (sum >> 16) # Add carry erom above (ie any)
sum = ~sum & 0xffff # Invert and truncate to 16 bits 4
return socket.htons(sum) # call htons to convert to network order and then return
Your program will send ICMP echo request packets. It should terminate when you receive an ICMP echo response from the end host rather than an ICMP port unreachable. See textbook for ICMP message types.
Sample code below shows how to transmit a ping message towards a destination.
def sendPing(self, ttl): # Done already
""" Create an icmp packet eirst, then use raw socket to sendto this packet """ #Header has 8 bytes: type (8), code (8), checksum (16), id (16), sequence (16) checksum = 0 # initialize checksum to 0
# Create a ICMP header using struct.pack() with a checksum (which is 0):
# In “BBHHH” B means one byte and H means 2 bytes
header = struct.pack("!BBHHH", ICMP_ECHO, 0, checksum, self.myID, self.seqNumber)
data = bytes(MAX_DATA_SIZE) # bytes oe zeros packet = header + data
checksum = self.checksum(packet) # call eunction to compute checksum
# Now that we have the correct checksum, put that in header. Create a new header header = struct.pack("!BBHHH", ICMP_ECHO, 0, checksum, self.myID, self.seqNumber) packet = header + data # Packet ready. We can send it to the Internet
# coneigure ttl oe this packet
self.ttl = ttl # ttl is passed to this method
self.sock.setsockopt(socket.IPPROTO_IP, socket.IP_TTL, self.ttl) #eor python 3.8.5+ # sele.sock.setsockopt(socket.SOL_IP, socket.IP_TTL, sele.ttl) # eor old python
try: self.sock.sendto(packet, (self.ip, self.port)) # sent to destination (ip, port)
print("bytes sent: ", num) # print msg eor debugging!
except socket.error as e: print("sendto failure (%s)" % (e.args[1])) # print msg eor debugging!
return # end oe sendPing
Once the router discards your packet based on expired TTL, it copies the first 28 bytes (starting with the IP header) of that packet and sends them back to your host using an ICMP “TTL Expired” message. The format of this message is shown in Figure 2, where the first 28 bytes are generated by the router and the remaining 28 bytes are from your original packet.1 Notice in the
1 Some routers return more than 28 bytes of your packet, so be prepared to experience longer return packets. In addition, you
figure, that the entire IP packet is delivered to the socket. Parsing the first IP header, you can obtain the router’s IP address.
|
|
|
|
|
IP header (20 bytes) |
|
|
|
ICMP reply header (8 bytes) |
|
|
|
Original IP header (20 bytes) |
|
|
|
Original ICMP header (8 bytes) |
|
generated |
|
by router |
|
copied |
|
from your |
|
packet |
|
|
Figure 2. “TTL Expired” packet format (standard is 56 bytes).
Since there are no port numbers in ICMP, every received ICMP packet is delivered to all open ICMP sockets! Thus, it is sometimes possible that your socket will receive unrelated ICMP traffic, which you should ignore. To check if this packet was in response to your traceroute probes, set the ID field of all outgoing packets to your process ID and check whether the ID field of the returned original ICMP header matches the ID of your process:
def recvPing(self):
"""Set timeout on receiving reply, call recverom(), interpret header ineo
return True ie reach destination """
# your work: set timer for recvfrom(), as we did in Assignment 1
recvPacket = b'' # empty bytes
recvPacket, addr = self.sock.recvfrom(ICMP_MAX_RECV)
# addr[0] is router’s IP, addr[1] is its port number
print("bytes received: ", len(revcPacket)) # print eor debugging!
# get eirst 20 bytes in recv pkt, IP header that contains router/destination IP ipHeader = recvPacket[:20]
# use struct.unpack() to get each field in ipHeader:
iphVersion, iphTypeOfSvc, iphLength, \ iphID, iphFlags, iphTTL, iphProtocol, \ iphChecksum, iphSrcIP, iphDestIP = struct.unpack("!BBHHHBBHII", ipHeader)
# get next 8 bytes, which are ICMP reply header icmpHeader = recPacket[20:28]
# use struct.unpack() to get each field in icmpHeader: icmpType, icmpCode, icmpChecksum, \
icmpPacketID, icmpSeqNumber = struct.unpack("!BBHHH", icmpHeader)
print("icmpType = ", icmpType) # print to see ICMP type, for bebugging!
# your work: get router’s IP and DNS name.
# Hint: router’s IP address is saved by addr[0]
# look up domain name: name = socket.gethostbyaddr(addr[0])
Finally, we can change ttl in a loop in trace():
|
# rawsocket.py … class RawSocket: def __init__(self, remotehost): def getIP(self, hostname): …
def trace(self): for ttl in range(1, 30, 1): # a maximum of 30 hops to any destination print("ttl", ttl) self.createRawSocket() startTime = time.time() # get startTime, in seconds self.sendPing(ttl) … # your work: call recvPing() and … self.close() # close socket print("RTT (s) = ", time.time() - startTime) # in seconds # ie reach destination, break this eor loop return |
In main(), we can call trace():
|
|
|
from |
|
rawsocket |
|
import |
|
RawSocket |
|
|
|
def |
|
main(): |
|
remotehost = |
|
"www.google.com" |
|
|
|
rs = RawSocket(remotehost) |
|
rs.trace() |
|
# end |
While this homework requires a sequential version of traceroute (send one probe, get one response), your program can send all probes at once (i.e., in parallel) to routers with a single thread. Using a common assumption that the maximum distance to any destination is 30 hops, you should send all 30 probes simultaneously (each with a different TTL) and then wait for responses from the routers. In order to know which router sent which response, use the sequence field in the ICMP header to encode the TTL. In case you hear nothing from a router at a certain TTL x, retransmit the probe for that particular TTL after a timeout (experiment with several values betwe en 0.1 and 3 seconds). If the router at hop x does not respond after 3 attempts, print “<ICMP timeout>” next to hop x:
If the target end-host responds to ICMP ping messages, all packets with a TTL larger than the distance to the host will result in ICMP echo responses. Thus, your code should check for both “TTL expired” and “echo reply” messages coming from the network.
Write about your implementation and analyze the performance of your code. This includes how long it takes to trace certain paths, how many packets (including retransmissions) are usually transmitted by your program, average packet loss observed during traceroute, what timeout is best for an average Internet path, etc.
Please download the anseer file using this link
https://drive.google.com/file/d/1D2Z2Gpc9cFwoaxu4Y3nkxUuNY73IFV4X/view?usp=sharing
