12/18/98
Phonetics (Group 4)
Aric Shafran, Mike Sokoryansky
Directory Service
FINAL REPORT
What we set out to do
Our goal was to implement directory service as part of an Internet telephony system. The directory service is very similar in functionality to yellow pages in a phone book. The yellow pages take a person’s name and return the phone number at which that person can be reached. The directory service takes a person’s name and returns the address at which that person can be found. This address can be a phone number or an IP address.
Our directory service would be used by other parts of the telephony system. For example, the conferencing application might use the directory service to find out what computer (i.e. IP address) a user can be found at any given time. The same application might also use the directory service to keep track of all active conferences (e.g. which users are in the conference, how old is a conference, etc.).
Here’s a list of core features that our directory service was designed to implement.
In addition to these, we hoped to implement the following more-or-less optional features, some of which were requested by other teams implementing the Internet telephony.
Originally, we planned to implement the directory service as an extension of BIND, the existing DNS implementation. About halfway through the semester, though, we realized that we would probably be better off implementing our own directory service from scratch. That would allow us to use Java instead of C (that BIND is written in). Java makes for easy object serialization (writing to/reading from disk and sockets) and simplifies integration of the directory service with other applications (since most applications written by our team were in Java). Also, not being locked into an existing design (such as BIND) allows us to design and implement new features of the directory service in the most flexible way possible.
The directory service is not a stand-alone application but a service provided to other applications. To access directory service, these applications need well-defined interfaces. We decided to encapsulate directory service functionality in a Java class that provided all the functionality of the directory service to clients through its methods. This class (along with many other classes that it uses) is compiled as part of the client application that wants to use the directory service.
The high-level design of the directory service and how it fits into the Internet telephony system is as follows:
Each query and update server has the entire directory service database. All updates are forwarded onto the central update server that informs all query servers of the update. All backups run on the same file system as the primary and read in the latest database file (which is written to after every update) when they get first request for service. The assumption is that if the backup received a service request, the primary must’ve gone down already.
What we did
We implemented the directory service from scratch in Java, as planned. We followed the design outlines in the section above. We were successful in implementing nearly everything we hoped to accomplish. All of the features 1-9 were implemented and the only significant compromises were made in implementing features 4 and 9. Even with these compromises, we feel that our implementation of directory service is quite robust and scalable.
The implementation can be broken down into two stages: implementing single-server directory service and implementing distributed directory service.
The single-server implementation server followed this algorithm:
The directory object provides methods to be used in step 4 which query the directory for information or update the directory. The directory uses hash tables to do quick lookups of users. To allow for crash recovery in the event the server crashes, we do not want to have to reconstruct the directory from scratch. Thus, we use the object serialization interface to periodically write the directory object to disk. When the directory starts up, it first checks if a directory already exists, and if so, it reads the object from disk. Since updates should occur far less frequently than queries, we write the directory to disk every time an update occurs. This means that the disk copy is always completely up to date with the copy in memory, so no information is lost if the server crashes.
The clients to this single-server implementation are Java stubs that we provide to the other groups to use. These stubs implement the interface that we are providing to the other groups. For each function in the interface, the single-server client follows the following procedure:
After we made the directory server distributed, the algorithms for the client and especially the server became more complex. The client now had a choice of servers to connect to. These servers were specified in a configuration file. Step 2 of the client procedure chose a server to connect to at random and tried to connect to it. If it failed, it tried to connect to its backup (if any). If that also failed, the client removed that server and its backup from its list of available directory servers and chose another random server to connect to. It repeats this procedure until it successfully connects to some directory server. Afterwards, the client follows the same steps as before.
The story is more complicated for the server. First of all, there are now two types of servers – query and update. Step 4 becomes very important – if the query server determines that the requested action is an update (such as adding new user or changing which conference a user is in) and that it came from a client (and not the update server), instead of making a call to the directory object, the query server forwards the request to the update server. The update server fulfills all the requests it gets, sends the response back to the query server that forwarded it the update request (so that that query server can return the success/failure back to client), and forwards any update requests to all query servers. The query servers will detect that the update request came from the central update server and update their databases. If, on the other hand, the query server detects in step 4 that the request is a simple query, it fulfills it just as a single-server implementation would.
We now discuss the implementation of the 9 features outlined in the previous section in more detail.
1. The most basic service that a directory service should provide is translating names to addresses. We define an address as a class (called "Address") which can be either a phone number or an IP address. An address could also be a "voice-mail address" – this feature is used by the voice-mail team in our group. The constructor for this class takes a byte-array; based on the size of this array the address is determined to be IP address or phone number. A number of functions such as GetIP( ) are provided to get addresses for a given user (see Interfaces section). These allow the application to specify whether it is looking specifically for an IP address or a phone number or whether it doesn’t care about the address type. These functions can take either usernames (which are also user e-mail addresses in our scheme) or phone number extensions. Extensions are useful to identify phone-only users (since there’s no concept of username associated with phones).
In addition to name-to-address translation, we also provide functions to translate from user extensions to usernames and vice versa. Originally we also planned to implement address-to-username translation (to figure out what user is using a given PC/phone), but it turned out that this functionality was not required by any application and so was not implemented (null-interface for it is still provided).
2. The directory service is necessarily made up of at least two components – the client side (which compiles along with the client application) and the server side (which runs as an independent application usually on a different machine from the client application). This indeed was how we first implemented the directory service. In this implementation, the application that runs the directory client is "under impression" that it is accessing a local directory database even though the actual directory server may run on another machine.
In a distributed server implementation, there are even more interacting components working together to provide the illusion of a single local database. This interaction is illustrated and explained in the previous section. The necessary information about what servers run at which IP addresses and ports is provided by the config file. The config file also tells a server whether it is a query or an update server.
3. We first implemented simple per-user text passwords for functions such as adding and removing a user and roaming logging in and out. We also implemented administrator-level password that allows any action to be performed. Although this implementation provides some security, it is highly susceptible to network snooping. A snoop can intercept a packet containing a plain-text password and will be able to change all settings for that user. Worse yet, the snoop might intercept and learn the admin password.
To remedy this situation, we implemented a DSA security algorithm. In this implementation authenticity of the users is ensured by signatures and there is no need to ever send password from client to server. The algorithm works as follows. When a user is added and his/her password is first specified, the client uses the password to seed the random number generator which, in turn, is used to a create a public/private key pair. The public key is sent to the server instead of the user’s password. The server will use this public key to verify the authenticity of future messages from this user. The important points here are that the same public key can be easily recreated from the password, and that neither the private key nor the password (which are the two sensitive items) are ever transferred over the net. The authenticity of future messages is verified by the client’s using the private key to encrypt a sensitive message and the server’s (both query and update) using the public key to ensure that the message was encrypted by the private key associated with the public key stored on the server. Since, this public key is generated from the user password, we conclude that the private key used to encrypt the message was also generated from the same (correct) password.
4. Reliability and robustness to failure are provided by the optional backup servers. Every query or update server can have a backup which will kick in automatically when the primary goes down. This happens because of the way we establish connections – if we cannot connect to the primary we automatically connect to the backup. When the backup receives its first service request, it assumes that the primary is down (otherwise, we would’ve been able to connect to the primary and would’ve never connected to the backup in the first place), reads in the latest database file (which is always up-to-date since every update gets written to it), and assumes the role of the primary. It is therefore very important that the backup and the primary run on the same file system and share the same database file.
When the primary is restarted, the clients will automatically switch over back to it. At that point the backup should be killed and restarted so it’s once again ready to kick in when the primary goes down. The information about the primaries and backups is contained in the config file.
Some additional degree of robustness is inherent in the fact that query servers are expendable and as long as each client can connect to at least one, all others can fail and the system will still function. However since there is only one update server, it is very important that either its primary or its backup is always up.
5. The roaming users are accounted for in a very simple but effective way. Normally a user sets preferences on which address he/she is most likely to be found at a certain time and day. So, any query asking what IP address (for example) a user is currently found at, finds its answer by examining the user’s preference settings. However, a roaming user can log in from any machine and set the roaming address which will override whatever preferences the user has preset until the user logs out again. The two functions that are relevant here are Login( ) and Logout( ) (see Interfaces section).
6. Our directory service allows the user to greatly customize his/her preferences as to the address the user is at. We allow the user to break down days of the week into two groups (a logical division would be weekdays and weekend). The preferences can be set independently for each group. Further, each day is broken down into 4 time periods and the preferences can be set for each period. The preferences allow the user to specify up to 4 address (each being IP address or phone number) in the order of likelihood of the user being at that address. The relevant functions here are AddUser( ) which defined day and time periods and SetIPPhone which allows to set preferences for each day group and time period.
So, overall, the user can specify up to 32 different address he/she can be found in one week – 2 day groups, each day with 4 time periods, and each time period with up to 4 different addresses. Of course, the user does not have to specify all 32 addresses – they can specify only 1 per time period or even only 1 overall (by using Login( )).
7. Our conferencing and billing groups requested a number of features from our directory service, all of which we implemented. We provide add-, remove-, get- and set-type functions to manage conferences and information about conferences (see Interface section). Each user can be in one conference and each conference keeps track of the people in it. It also keeps track of the active vs. past members of the conference, conference length and quality of service, etc.
8. We managed to make our directory service perfectly configurable – no ports or IP addresses are hard-coded. Instead we rely on three types of config files – one for clients, one for query servers, and one for update server. The client config file lists some (it does not have to list all) query servers’ IP addresses and ports and, optionally, their backups. The query server config file tells the server that it’s a query server and also lists the IP and port of the update server and its backup. The update server config file tells the server that it’s an update server and also lists all (this is important to ensure that all query servers are in the same state) query servers’ IP and ports and their backups.
This ease of configuration came in very handy during testing and integration stages when we had to move a lot from machine to machine.
9. Finally, our last and probably most-difficult objective was to make our directory service as scalable as possible. We succeeded to some degree. Because we can have as many query servers as we want and because each server uses a hash table to quickly locate information, query-type requests (such as GetIP( )) should be executable nearly equally fast for a small database accessed by several users and for a large database accessed by thousands of users. The update-type requests are a much more serious problem. Because our design has only one update server, it is likely that it will get swamped with update requests as the database size grows too large. It also does not help matters that each update will have to forwarded to all query servers since the number of query servers will likely be large for a large directory database.
On the other hand, update-type messages should be a lot less frequent than query-type, so it is reasonable to suppose that our design might still scale well into medium-size directory databases. Certainly, with small directory size (less than 50 users), there is no performance problem with our design. The exact size at which performance starts becoming a problem can be determined empirically by using our directory service in the real world, but such investigation is beyond the scope of our project.
Problems that we encountered
Our problems can be broken down into two categories: technical and coordination. Technical problems were relatively minor. We were able to accomplish nearly everything we planned. The biggest technical obstacle was making a truly scalable distributed directory service. By the time we started implementing distributed directory service, we were running out of time to make it fully scalable. We describe the compromise we made (having one central update server – making it both a potential bottleneck and point of failure, although the latter is alleviated by the backup option) in the previous sections of this report. There were three more obscure compromises we made: each server holds the entire database, each update gets written to disk, and, finally, clients do not remember that a given server is running as a backup and always try to connect to the primary first even though it’s down. We describe these in detail in the following sections.
We decided to make directory database reside fully on each server. In other words, we did not take any advantage of hierarchical naming to distribute the database among many servers. This means that there is an inherent limit on how large our database can be – if it’s too large, it won’t fit into server’s memory. This might seem like a serious problem, but the limit on database size is inherent in our single-update-server design anyway. So, this compromise was the result of previous design choices. In fact, it would’ve made little sense to make the directory database distributed, since the main advantage of this design (allowing for huge directory databases) would be negated by another design choice anyway.
Another compromise we made was to write each update to disk immediately instead of waiting until a significant number of updates accumulates and writing them all out at once. This compromise too does not have much negative impact on performance. Since our database size is limited (once again, by the single-update-server design choice), the number of users is relatively small and so is the number of updates. Furthermore, since our servers are multithreading, one thread can be writing to disk while another answers a query request. Since we use Java object serialization to write to disk, we write the entire database out every time, but again, since the database size is relatively small, this doesn’t have too much of a negative impact. We tested our directory service without ever writing to disk and could not see any noticeable performance improvement.
The last, and most obscure, compromise we had to make, was to not have the clients remember that a given server is running as a backup. This results in slightly slower queries and updates because the client always tries to connect to the primary first even though it’s down; after a short while the client realizes that it cannot connect to the primary, connects successfully to the backup and gets its request services by the backup. Originally we implemented the clients to remember every server’s state to eliminate the problem, but then we realized that it introduces the following bug.
Suppose we have clients A and B accessing update server S. At some point S crashes and S’ (S’s backup) kicks in. On its next request A tries to connect to S, fails, and connects to S’. It uses S’s for some updates causing S’ to write to its database. Then S is restarted. Then B needs service and it tries to connect to S successfully. Now B uses S and A uses S’. If both A and B have update requests, S and S’ will get out of sync causing a major problem. The solution to this problem involves S and S’ making sure that the other one is dead instead of just assuming it because it (whether it be S or S’) gets a service request. Then when B tries to access S, S would try talking to S’, succeed, and realize that they’re both active. Then S can either itself die or tell S’ to die. This type of solution is certainly possible, but we did not think that it was worth implementing, especially since we were running out of time in our distributed implementation.
More significant were coordination problems. As late as three days before the final demo date we were still getting requests to implement new functionality. Despite our group’s and team’s best efforts to utilize Microsoft Visual Source Safe to manage code versions, we ended up having many versions of code floating around in different directories. This, in turn, made it more difficult to integrate everything since different teams were using different versions of our directory service many of which were incompatible with one another (since we extensively use object serialization and it requires that the object written and the object read be identically defined). For most of us, this was by far the most demanding group project we’ve ever had, and we ran into a huge number of large and small problems (mostly unexpected) from scheduling meetings to making sure that the config files are correct.
What we learned
A lot. Some of it was technical. One of us had virtually no prior Java experience and learned while working. We learned a lot about object serialization and security in Java. Aside from Java-related stuff, we learned a fair bit about what’s involved in making a scalable, distributed application. Obviously, we also learned something about directory service functionality, although most of it is fairly common-sense. However this newly-acquired technical knowledge pales in comparison with the experience gained in implementing such a large project. Here’s a short summary of what we learned from this group project:
And most importantly:
What we would do differently next time
We think we handled this project pretty well from the technical point of view. Although at first we planned to modify and extend BIND, we quickly realized the advantages that can be gained by implementing the directory service from scratch in Java. Although we did not investigate heavily what would be involved in extending BIND, it seems likely that it would’ve been significantly more difficult than writing directory service from scratch. This is especially true since almost all other teams in our group use Java and integration of BIND’s C code with Java would’ve made this project that much more difficult. Not switching to Java would’ve probably been the greatest mistake we could have made in this project. Fortunately, we did not make it.
We think that our design did not have any significant problems. If our primary goal had been to make a limitlessly scalable system, then the design wasn’t that great. But the primary goal was to implement functionality; reliability, scalability, and robustness were secondary objectives. In this light, we think our design compromises were well-justified and very reasonable given our limited time.
Where we did make many mistakes is in planning and coordinating our part of the project in relation to the rest of the group. These mistakes led directly to the bullet-list of things we learned in the previous section. We should have, but did not:
And…
Interfaces we provide (in Java)
Note: we do not use anyone’s interfaces.
// in general, the return value of false (for boolean) or -1 (for int) indicates failure
// adds new user to directory
// Email: user's email
// Extension: user's extension -- used to uniquely identify the user with a number for phone-to-PC calls
// Password: password, may be empty
// Week: 7-bit array. Each bit represents one day of the week (0 - Monday, ...). 1's define one
// group of days and 0's another. Example: 0000011 -- Monday- Friday are group 0; Saturday, Sunday are group 1
// Group0Time?: 3 numbers between 1 and 24 used to split each day in group 0 into 4 time periods.
// Ex: Group0Time0 is 9, Group0Time1 is 17, Group0Time2 is 20 means that period 0 is midnight-9am,
// period 1 is 9am-5pm, period 3 is 5pm-8pm, period 4 is 8pm-midnight.
// If the user does not want to specify all 4 time periods, just set unwanted Group0Time? arguments to 24
// Ex: Group0Time? are all 24 means that the whole day is just one period
// Group1Time?: same thing as Group0Time?, but for days in group 1
// returns true if succeeds, false if fails
boolean AddUser(String Email, int Extension, String Password, BitSet Week, byte Group0Time0, byte Group0Time1, byte Group0Time2, byte Group1Time0, byte Group1Time1, byte Group1Time2)
// removes the user from the database and any conferences if password checks out; false for fail
boolean RemoveUser(String Email, String Password)
String GetUserFromExtension(int ext_number)
boolean Login(String Email, String Password, Address add)
boolean Logout(String Email, String Password)
// changes user's password; false for fails
boolean ChangePassword(String Email, String OldPassword, String NewPassword)
// sets the IP/phone# preferences for a day period in one group of the days.
// Example: SetIPPhone(xyz@cornell.edu, "", 0, 0, 128.3.0.1, 128.4.0.1, 506-353-2623, 128.5.0.1)
// means that user xyz@cornell.edu can be reached on 0-group days, first time period
// at 128.3.0.1 (most likely), ... , 128.5.0.1 (least likely)
boolean SetIPPhone(String Email, String Password, byte Group, byte Period, Address Address0, Address Address1, Address Address2, Address Address3)
// gets IP location for the user specified by Email or extension
// (based on preferences);
// Pref is a number 0-3 that indicates which of the IP addresses to return.
// Typically, first called with Pref set to 0, try the returned IP address, if doesn't work,
// call again with Pref set to 1, try that, etc.
// false if fails
boolean GetIP(String Email, byte Pref, Address ReturnIP)
boolean GetIP(int Extension, byte Pref, Address ReturnIP)
// same as GetIP, but gets the phone number
boolean GetPhone(String Email, byte Pref, Address ReturnPhone)
boolean GetPhone(int Extension, byte Pref, Address ReturnPhone)
// same as GetIP, but don't care if the returned address is IP or Phone
boolean GetIPorPhone(String Email, byte Pref, Address ReturnAddress)
boolean GetIPorPhone(int Extension, byte Pref, Address ReturnAddress)
// Not implemented - always fails
String GetUserFromAddress(Address Address)
// On return, ReturnData is a vector of UserInfo objects, each object corresponding to a user
boolean ListAllUsers(Vector ReturnData)
// On return, ReturnData is a vector of ConferenceInfo objects, each object corresponding to a conference
boolean ListAllConferences(Vector ReturnData)
//return value: handle to new conference or -1 for fail
int CreateConference(int qos, boolean pub, String name, String ip)
boolean AddUserToConference(int conf, String Email)
boolean RemoveUserFromConference(String Email)
// deletes all information about that conference
boolean DestroyConference(int conf)
//return value: conference handle for the conf that user "Email" is in or -1 for fail
int GetConference(String Email)
// On return, ReturnUsers is a vector of strings, each string corresponding to a user that's
// currently in the conference
boolean GetCurrentUsersInConference(int conf, Vector ReturnUsers)
// On return, ReturnUsers is a vector of strings, each string corresponding to a user that's
// ever been in the conference
boolean GetAllUsersInConference(int conf, Vector ReturnUsers)
// Return value: -1 Fail, else max number of users ever in the conference
int GetMaxInConference(int conf)
//return value: length of the conference so far in minutes, -1 for fail
long GetConferenceLength(int conf)
//return value: QoS of conference or -1 for fail
int GetConferenceQoS(int conf)
boolean GetConferencePublic(int conf)
String GetConferenceName(int conf)
String GetConferenceIP(int conf)
boolean SetConferencePublic(int conf, boolean pub)
boolean SetConferenceName(int conf, String name)
Advice for staff
We think the staff did a good job in helping us complete this project. One thing they could’ve done that would be useful would be to require some sort of scaled down demo a month or so before the final demo. This would force students to start early which would be very helpful for them (although they might not appreciate that).
References