Description
Overview
In project 2, we will implement a set of programs that mimic an implementation of load balancing
across DNS servers. Spreading the load of incoming DNS queries among replica DNS servers is
one method by which DNS scales to meet the needs of Internet users. In its simplest form, a “load
balancer” simply picks a single DNS server to respond to any given request, spreading requests as
evenly across servers as possible. This has the effect of using several server machines to simulate
one powerful DNS server.
This project will explore a slightly more sophisticated form of balancing load that also takes
into account the need to respond to requests as early as possible. We will explore request duplication, i.e., sending the same request to two servers, and picking the response that arrives first. At
the cost of using more system resources, this allows the overall system to hide the delay caused by
a slow server. In this project, we will model a slow server in the extreme by implementing servers
that do not send any response at all in some cases.
Overall, you will build four programs in this project: a client, a load-balancing server (LS) that
implements load balancing, and two DNS servers TS1 and TS2. We will implement load balancing
across DNS servers as follows. First, the client sends its DNS query to the load-balancing server
LS. LS resolves the query recursively, by querying two other DNS servers TS1 and TS2, and
returning the response or an error to the client. In this project, only TS1 and TS2 store the actual
mappings from domain names to IP addresses. LS does not store any name to IP mappings.
The mappings stored by TS1 and TS2 do not overlap with each other. Only when a TS server
contains a mapping for the queried domain name will it respond to LS; otherwise, that TS sends
nothing back. Hence, at most one TS will respond to any query from LS. It is also possible that
neither TS contains a mapping for the queried domain name.
However, LS does not know in advance which TS, if any, will contain the IP address for a given
domain name. Hence, LS must query both TS1 and TS2. There are three possibilities: (1) TS1
responds; (2) TS2 responds; or (3) neither responds within a fixed timeout. Note that it is never the
case that both TS1 and TS2 respond. In cases (1) and (2) above, LS must relay the response as is
from the server to the client. In case (3), LS returns an error to the client.
Please note that LS implements recursive query resolution for the client. That is, only LS
interacts with the client. The TS servers do not communicate directly with the client. See the
attached pictures showing the interactions among the different programs.
Design of the servers and DNS message formats
In lieu of the actual DNS protocol, this project will use a simple message format for name queries
and responses, which we define below.
Design of the TS servers
There are two TS servers. The primary function of each TS server is to look up a domain name
queried by the LS and return an entry with an IP address, if the lookup succeeds. Each TS maintains
2
just one connection: with the LS. Each TS server maintains a DNS table consisting of three fields:
• Domain name
• IP address
• Resource record type (A only in this project)
For each query received from the LS, each TS server does a lookup of the domain name in its
DNS table, and if there is a match, sends a DNS response with the following string:
DomainName IPaddress A IN
The four fields represent the name, value, type, and class of the response, respectively. If
the queried domain name isn’t found in the local DNS table, the TS server sends nothing back.
A TS server without the domain name in its local DNS table must not send any data to the LS
or the client. TS1 (resp. TS2) will read its DNS table from the input file PROJ2-DNSTS1.txt
(resp. PROJ2-DNSTS2.txt). We will ensure that the two DNS tables have no overlapping domain
names.
DNS lookups are case-insensitive. If there is a hit in the local DNS table, the TS programs
must respond with the version of the string that is in their local DNS table. You will see examples
of this in the samples attached in the project archive.
Design of the LS server
The LS server receives queries from the client and forwards them directly to both TS1 and TS2.
If either one responds, LS will relay the response directly to the client, else it will send an error
message.
Since the DNS tables for TS1 and TS2 have no overlap, at most one of TS1 or TS2 will respond
to any query. It is possible that neither of them responds. If the LS receives a response from one of
the TS servers, it should just forward the response as is to the client. As shown above, this string
will have the format Hostname IPaddress A IN as obtained from the TS that just responded.
If the LS does not receive a response from either TS within a time interval of 5 seconds (it’s also
OK to wait slightly longer), the LS must send the client the message DomainName – TIMED OUT
where the DomainName is the domain name queried by the client.
The LS maintains three connections/sockets: one with the client and one with each TS server.
The most tricky part of implementing the LS is figuring out which TS, if any, has pushed data into
its corresponding socket, and timing out when neither has pushed data. Think carefully about how
you will implement this. Just performing recv() calls on the two TS sockets won’t achieve the
desired result, since recv() by default is a blocking call: if you recv() on the TS1 socket but
TS1 hasn’t pushed any data, your LS program will hang indefinitely waiting for data from TS1.
Client
The client sends queries to the LS. The client also directly prints the output it receives from the LS.
Conceptually, it is the simplest part of this project. The client reads domain names to query from
the input file PROJ2-HNS.txt, one query per line. The client must write all the outputs it receives
from LS into a file, RESOLVED.txt, one line per response. The client must NOT communicate
directly with TS1 or TS2. The client maintains only one connection: with the LS.
3
Some helpful notes
(1) Run your programs by first starting the two TS programs, then the LS program, and finally the
client program.
(2) There are a few methods to turn a blocking recv() call at the LS into a call that will return,
possibly after a timeout. One possibility is to use a non-blocking socket; another is to use the
system call select(). Multi-threading may help, but we have found it unnecessary.
(3) DNS lookups are case-insensitive. The DNS response must contain the version of the domain
name that is in the DNS table.
(4) It is okay to assume that each DNS entry or hostname is smaller than 200 characters.
(5) Please start this project early to allow plenty of time for questions on Piazza should you run
into difficulties.
What you must submit and how we will test it
For your project submission on Canvas, please turn in four programs: ls.py, ts1.py, ts2.py,
and client.py, and a project report entitled report.pdf. The questions for the report are listed
below. We will be running the four programs on the ilab machines with the Python 2 version on
ilab. Please compress the files into a single Zip archive before uploading to Canvas. Only one
team member must submit.
Please do not assume that all programs will run on the same machine or that all connections are
made to the local host. We will test your programs with local and remote socket connections, for
example with client.py, ts1.py, ts2.py, and ls.py each running on a different machine.
You may simplify the initial development/debugging of your programs (and get off the ground) by
testing all programs on one machine first. However, you must eventually ensure that the programs
can work across multiple machines.
The programs must work with the following command lines:
python ts1.py ts1ListenPort
python ts2.py ts2ListenPort
python ls.py lsListenPort ts1Hostname ts1ListenPort ts2Hostname ts2ListenPort
python client.py lsHostname lsListenPort
where
• ts1ListenPort and ts2ListenPort are ports accepting incoming connections at TS1
and TS2 (resp.) from LS;
• lsListenPort is the port accepting incoming connections from the client at LS;
• lsHostname, ts1Hostname, and ts2Hostname are the hostnames of the machines running LS, TS1, and TS2 (resp.).
We will provide the input files PROJ2-HNS.txt, PROJ2-DNSTS1.txt, and PROJ2-DNSTS2.txt.
You must populate RESOLVED.txt from the client.
The entries in the DNS tables (PROJ2-DNSTS1.txt and PROJ2-DNSTS2.txt for TS1 and
TS2 respectively) will be strings with fields separated by spaces. There will be one DNS entry
per line. You can see the format in the samples provided with the project archive. Your server
4
programs TS1 and TS2 should populate their local DNS table by reading the entries from their
corresponding files. Your client program should output the results to a file RESOLVED.txt, with
one line per result. See the samples attached in this folder for questions about formatting. We
will test your code both with these samples and other test cases of our own, and you will be graded
based on the outputs in RESOLVED.txt. Your program should not crash or hang on correct inputs.
Project report
Please answer the following questions for the project report.
1. Team details: Clearly state the names and netids of your team members (there are 2 of you).
2. Collaboration: Who did you collaborate with on this project? What resources and references did you consult? Please also specify on what aspect of the project you collaborated or
consulted.
3. Discuss how you implemented the LS functionality that tracks which TS responded to a
given query or timing out if neither TS responded. Please be clear and specific.
4. Is there any portion of your code that does not work as required in the description above?
Please explain.
5. Did you encounter any difficulties? If so, explain.
6. What did you learn from working on this project? Add any interesting observations not
otherwise covered in the questions above. Be specific and technical in your response.
Contact the course staff on Piazza if you have any questions.
5
