15-441: Computer NetworksProject 1: IRC and RoutingLead TA: George Nychis <[email protected]>Assigned: September 5, 2006Checkpoint 1 due: September 12, 2006Checkpoint 2 due: September 26, 2006Final version due: October 12, 20061 IntroductionThe purpose of this project is to give you experience in developing concurrent networkapplications. You will use the Berkeley Sockets API to write an Internet chat server usinga subset of the Internet Relay Chat protocol (IRC)[1] and implement two different routingprotocols so chat messages can be exchanged between a network of chat servers.IRC is a global, distributed, real-time chat system that operates over the Internet. AnIRC network consists of a set of interconnected servers. Once users are connected to an IRCserver, they can converse with other users connected to any server in the IRC network. IRCprovides for group communication, via named channels, as well as personal communicationthrough “private” messages. For more information about IRC, including available clientsoftware and public IRC networks, please see The IRC Prelude[2].If you have not used IRC before, you may want to try it out to get a feel for what it is.For a quick start, log in to an Andrew machine, and run irssi -c irc.freenode.net -n nicknamewhere nickname is the nickname you want to use. Then type /join #networking to join anetworking discussion channel. Other channels you might be interested include #gentoo,#redhat, #perl, and #c++. After you have tried out the text mode IRC client, you maywant to try out graphical clients such as xchat and chatzilla (part of mozilla).In a ddition, you will also implement a shortest path link state routing protocol. In thisprotocol, each node in the network periodically exchanges information with its neighbors sothat everyone in the network knows the best path to take to reach each destination. This issimilar to the protocols used in Internet routers. At the end of this project, you will haveyour own network of chat servers, which could be used to talk with users across the world.12 Logistics• The tar file for this project can be found here:http://www.cs.cmu.edu/∼srini/15- 441/F06/project1/project1.tar.gz• This is a group project. Yo u must find exactly one partner for this assignment. Theonly reason you should not have a partner is if there are an odd number of people inthe class and you are left out (in which case contact us). Talk to your neighbors anduse the bboa rds.• Once you have found a partner, email George at [email protected] your names andandrew logins so we can assign a group number to you. Use “15441 GROUP” as thesubject. Please try to b e sure you know who you will work with for the full duration ofthe project so we can avoid the hassle of people switching later.• This is a larg e project, but not impossible. We recommend adhering to a schedule like:date milestone9/5 project assigned9/9 read and understand the project handout9/12 checkpoint due – version contr ol basics9/17 simple standalone irc server complete9/21 simple standalone irc server tested thoroughly9/26 checkpoint due – standalone IRC server10/1 routing daemon implementation complete10/5 routing daemon tested thoroughly10/7 irc server extensions/forwarding protocol complete10/9 irc server extensions tested thoroughly10/12 last minute rush to get things done and hand-in3 OverviewAn IRC network is composed of a set of nodes interconnected by virtual links in an arbitrarytopology. Each no de runs a process that we will call a routing daemon. Each routing daemonmaintains a list of IRC users available to t he system. Figure 1 shows a sample IRC networkcomposed of 5 nodes. The solid lines represent virtual links between the nodes. Each nodepublishes a set of users (i.e., the nicks of the IRC clients connected to it) to the system. Thedotted lines connect the nodes to their user sets.The usage model is the following: If Bob wants to contact Alice, the IRC server on theleft first must find the r oute or path from it to the node on the right. Then, it must forwardBob’s message to each node alo ng the path (the dashed line in the figure) until it reachesthe IRC server at Alice’s node, which can then send the message to the client Alice.2In essence, each node in the system performs functions similar to the ones performed inthe network layer, namely forwarding and routing. Forwarding is the action performed byeach node to guide a packet toward its destination. Routing refers to the action of buildingthe data structures necessary to reach particular destinations (in terms of the IRC server, adestination is a username/nick).The routing daemon will be a separate program from your IRC server. Its purpose isto maintain the routing state of the network (e.g., build the routing tables or discover theroutes to destinations). When the IRC server wants to send a message to a remote user,it will ask the ro uting daemon how to get there and then send the message itself. In otherwords, the routing daemon does the routing and the IRC server does the forwarding.In your implementation, the routing daemon will communicate with other routing dae-mons (on other nodes) over a UDP socket to exchange routing state. It will talk to the IRCserver that is on the same node as it via a local TCP socket. The IRC server will talk toother IRC servers via the TCP socket tha t it also uses to communicate with clients. It willsimply use special server commands. This high level design is shown in the two large IRCserver nodes in Figure 1.Figure 1: IRC networkIn o rder to find out about the netwo r k topology, each routing daemon will receive a listof neighboring nodes when it starts. In this project, you can assume that the no new nodesor links will ever be added to the topology after starting, but nodes and links can f ail (i.e.,crash or go down) during operation (and may recover after failing).34 Definitions• node – an IRC server and routing daemon pair running together that is part of thelarger network. In the real world, a node would refer to a single computer, but we canrun multiple “virtual” nodes on the same computer since they can each run on differentports. Each node is identified by its nodeID.• nodeID – unique identifier that identifies a node. This is an unsigned 32-bit integerthat is assigned to each node when its IRC server and routing daemon start up.• neighbor – Node 1 is a neighbor of node 2 if there is a virtual link between 1 and2. Each node
View Full Document
Unlocking...