1 15-441 Computer Networks Project 2: IRC Routing Lead TA: Rui Meireles <[email protected]> Assigned: February 16, 2010 Checkpoint 1 Due: March 1, 2010 Checkpoint 2 Due: March 19, 2010 Final Due: March 25, 2010 (11:59 PM EST) 1 Introduction The purpose of this project is to give you experience in developing concurrent network applications. You will use the BERKELEY SOCKETS API to write an Internet chat server using a subset of the Internet Relay Chat protocol (IRC)1 and implement two different routing protocols so chat messages can be exchanged between a network of chat servers. You will implement a shortest path link state routing protocol. In this protocol, each node in the network periodically exchanges information with its neighbors so that everyone in the network knows the best path to take to reach each destination. This is similar to the protocols used in Internet routers. At the end of this project, you will have your own network of chat servers, which could be used to talk with users across the world. 2 Logistics • The tar file for this project can be found at: http://www.cs.cmu.edu/~srini/15-441/S10/project2/project2.tar.gz • This is a group project. You must find exactly one partner for this assignment. The course bulletin board is an excellent channel for looking for partners. In case there is an odd number of students in class and you are the one left out at the end, the course staff you assign you a simplified project. Please know this is a last resort measure. • As soon as you have found a partner, email the lead TA your names and andrew logins so he can assign you a group number and an SVN repository. Use “15441 GROUP” as the subject line. Please try to be sure you know who you will work with for the full duration of the project so we can avoid the hassle of people switching later. • This is a large project, but not impossible. Here is a recommended set of suggested milestones: √ Date Milestone 2/19 3/01 3/19 3/25 Understand the project handout and learn pertinent knowledge and skills CHKPOINT 1 Due – IRC server extensions/interfaces tested thoroughly CHECKPOINT 2 Due – Routing daemon tested thoroughly Last minute rush to get things done and handin 1 http://www.irchelp.org/irchelp/rfc/2 3 General Overview The routing daemon will be a separate program from your IRC server. Its purpose is to maintain the routing state of the network (e.g., build the routing tables or discover the routes to destinations). When the IRC server wants to send a message to a remote user, it will ask the routing daemon how to get there and then send the message itself. In other words, the routing daemon does the routing and the IRC server does the forwarding.2 Figure 1 – Sample IRC Network In your implementation, the routing daemon will communicate with other routing daemons (on other nodes) over a UDP socket to exchange routing state. It will talk to the IRC server that is on the same node as it via a local TCP socket. The IRC server will talk to other IRC servers via the TCP socket that it also uses to communicate with clients. It will simply use special server commands. This high level design is shown in the two large IRC server nodes in Figure 1. In order to find out about the network topology, each routing daemon will receive a list of neighboring nodes when it starts. In this project, you can assume that no new nodes or links will ever be added to the topology after starting, but nodes and links can fail (i.e., crash or go down) during operation (and may recover after failing). 4 Definitions Before jumping into the gory details, let us define some terminology. • node – An IRC server and routing daemon pair running together that is part of the larger network. In the real world, a node would refer to a single computer, but we can run multiple “virtual” nodes on the same computer since they can each run on different ports. Each node is identified by 2 In actual routers, and even overlay networks like peer-to-peer file sharing networks, the notion of the separate routing daemon is atypical. Normally, the forwarding program should keep the forwarding table, not query the route daemon for each route lookup.3 its nodeID. • nodeID – A unique identifier that identifies a node. This is an unsigned 32-bit integer that 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 and 2. Each node obtains a list of its neighbors’ nodeIDs and their routing and forwarding ports at startup. • destination – An IRC username or nick as a null terminated character string. As per the IRC RFC, destinations will be at most 9 characters long and may not contain spaces. • IRC port – The TCP port on the IRC server that talks to clients and other IRC servers. • forwarding port – Same as IRC port. • routing port – The UDP port on the routing daemon used to exchange routing information with other routing daemons. • local port – The TCP port on the routing daemon that is used to exchange information between it and the local IRC server. For example, when the IRC server wants to find out the route to remote user, it queries the routing daemon on this port. The socket open for listening will be on the routing daemon. The IRC server will connect to it. • OSPF – The shortest path link state algorithm that inspires the (much simpler) algorithm you will implement · routing table – The data structure used to store the “next hops” that packet should take used in OSPF. 5 Link-State Routing Protocol 5.1 Basic Operation You will implement a link-state routing protocol similar to OSPF, which is described in the textbook in chapter 4, and in more detail in the OSPF RFC3. Note, however, that your protocol is greatly simplified compared to the actual OSPF spec. As described in the references, OSPF works by having each router maintain an identical database describing the network’s topology. From this database, a routing table is calculated by constructing a shortest-path tree. Each routing update contains the node’s list of neighbors, users, and channel. Upon receiving a routing update,
View Full Document
Unlocking...