/////////////////////////////////////////////////////////////////////////////// // Title: Programming Assignment 2: Routing Protocol // Files: p2/server/server.c // p1/server/Makefile // Semester: Fall 2007 // Author: Cymen Vig (cymen@cs.wisc.edu) // John Goebel (jgoebel@wisc.edu) // Partner: cymen goebel /////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define DEBUG 0 #define INFINITY 16 #define MAX_UDP 65507 // Max size of UDP packet #define MAX_LENGTH 255 #define USAGE -100 #define BAD_ID -9999 // structure to hold neighbor records (linked-list) typedef struct { int id; char ip[16]; int port; time_t ttl; // time(&ttl) int sockfd; struct sockaddr_in sockaddr; struct Neighbor *next; } Neighbor; // structure to hold route records (linked-list) typedef struct { int nextHop; int dest; int cost; char ip[16]; struct Route *next; } Route; // structure to hold running server variables (me) typedef struct Server { int id; char ip[16]; int port; int interval; // how often to send updates Neighbor *neighbor; Route *route; char *tfile; unsigned char packet[MAX_UDP]; int packetLength; } Server; Server server; int packetCount; void getOpts(int argc, char *argv[]); // get cmd line options void update_handler(int signum); // send scheduled updates void endProgram(int val); // exit w/ usage int loadData(char *file); // load data, initialize void stripNL(char *string); // strip new line int packUpdate(); // data struct -> update pkt int unpackUpdate(int from, unsigned char *inPacket, int pSize); // unpack and check routes void idToIp(int id, char *ip); // neighbor id to IP int ipToId(char *ip); // neighbor IP to id void addNeighbor(Neighbor *new); // add neigbhor to LL void addRoute(Route *new); // add route to LL int neighborPresent(int id); // check if id is a neighbor int routePresent(int id); // check if route to id present int delNeighbor(int id); // delete neighbor from LL void printRoutes(); // display routes void printNeighbors(); // display neighbors int commandInput(char *buf); // parse console input & respond int connectRouter(Neighbor *router); // connect to router (UDP) int updateRoute(int nextHop, int dest, int cost); // update route cost int getDestCost(int dest); // get destination cost int sendUpdate(int sockfd, struct sockaddr_in sockaddr); // send update pkt to all neighbors // main method int main(int argc, char *argv[]) { if (argc != 9) endProgram(USAGE); getOpts(argc, argv); loadData(server.tfile); int quit = 0; int result; char buf[256]; char *token; packetCount = 0; unsigned char inPacket[MAX_UDP]; int inPacketSize; int inResult; int fromId; // set update interval (update_handler() method) struct itimerval itime; itime.it_interval.tv_sec = server.interval; itime.it_interval.tv_usec = 0; itime.it_value.tv_sec = server.interval; itime.it_value.tv_usec = 0; fd_set socket_set; int sockfd, clilen; struct sockaddr_in serv_addr, cli_addr; clilen = sizeof(cli_addr); // setup server listening socket sockfd = socket(AF_INET, SOCK_DGRAM, 0); if (sockfd < 0 && DEBUG) printf("ERROR with sockfd\n"); bzero((char *) &serv_addr, sizeof(serv_addr)); serv_addr.sin_family = AF_INET; serv_addr.sin_addr.s_addr = INADDR_ANY; serv_addr.sin_port = htons(server.port); if (bind(sockfd, (struct sockaddr *) &serv_addr, sizeof(serv_addr)) < 0) if (DEBUG) printf("ERROR on binding\n"); // connect to neighbor routers Neighbor *n = server.neighbor; while (n) { if (DEBUG) printf("connecting to router %d...\n", n->id); n->sockfd = connectRouter(n); n = (Neighbor *) (n->next); } // initialize update handler method (send scheduled updates) struct sigaction action, oldaction; action.sa_handler = update_handler; action.sa_flags = SA_RESTART; sigemptyset(&action.sa_mask); result = sigaction(SIGALRM, &action, NULL); if (DEBUG && result != 0) printf("sigaction result: %d\n", result); result = setitimer(ITIMER_REAL, &itime, NULL); if (DEBUG && result != 0) printf("setitimer result: %d\n", result); // main loop while (!quit) { FD_ZERO(&socket_set); FD_SET(0, &socket_set); // add fd of standard input/output FD_SET(sockfd, &socket_set); // add fd of UDP port listening on result = select(FD_SETSIZE, &socket_set, (fd_set *) 0, (fd_set *) 0, NULL); if (result < 0) { if (errno != EINTR) { printf("%m\n", errno); } } else { // check for console input if (FD_ISSET(0, &socket_set)) { fgets(buf, sizeof(buf), stdin); quit = commandInput(buf); result--; } // check for socket input (incoming packet updates) if (FD_ISSET(sockfd, &socket_set)) { while(result) { // receive UDP packet inPacketSize = recvfrom( sockfd, &inPacket, sizeof(inPacket), 0, (struct sockaddr *) &cli_addr, &clilen ); // look up ID of sender fromId = ipToId(inet_ntoa(cli_addr.sin_addr)); // process packet if from valid neighbor if (fromId != BAD_ID) { unpackUpdate(fromId, inPacket, inPacketSize); // update TTL to now... n = server.neighbor; while (n) { if (n->id == fromId) { time(&n->ttl); break; } n = (Neighbor *) (n->next); } } result--; packetCount++; } } } } // quitting/crashing // - free neighbor memory n = server.neighbor; Neighbor *nNext; while (n) { close(n->sockfd); nNext = (Neighbor *) (n->next); free(n); n = nNext; } // - free route memory Route *r = server.route; Route *rNext; while (r) { rNext = (Route *) (r->next); free(r); r = rNext; } } // 40 SUCCESS // Report successful executon of update, step, packets, display or disable command. void success(char *command) { printf("40 %s SUCCESS\n", command); } // 40 // Report error cncountered during executon of command. void errorEncountered(char *command, char *errorMsg) { printf("40 %s %s\n", command, errorMsg); printf("Useage:\n"); printf(" update \n"); printf(" step\n"); printf(" packets\n"); printf(" display\n"); printf(" disable \n"); printf(" crash\n"); } // pack route table into update packet int packUpdate() { int vectorCount = 0; Route *r = server.route; while (r) { vectorCount++; r = (Route *) r->next; } if (vectorCount == 0) return 0; /* calculate size of packet in bytes for malloc * header: * 2 - number of update fields * 2 - padding (0x0) * for each vector: * 4 - ip address of dest server * 2 - server id of dest server * 2 - cost to dest server * Total: * 4 + vectorCount * (8) */ int size = 4 + vectorCount*8; server.packetLength = size; bzero(server.packet, MAX_UDP); // pack field count int offset = 0; unsigned short fieldCount = htons(vectorCount); memcpy(server.packet+offset, (char *) &fieldCount, sizeof(fieldCount)); offset += sizeof(fieldCount); // intentional skip (2 bytes) (already set to zero w/ bzero() above) offset += sizeof(fieldCount); r = server.route; while (r) { // pack destionation router ip (aka "server ip") struct sockaddr_in ip; inet_aton(r->ip, &ip.sin_addr); memcpy(server.packet+offset, (char *) &ip.sin_addr, sizeof(ip.sin_addr)); offset += sizeof(ip.sin_addr); // pack server id unsigned short id = htons(r->dest); memcpy(server.packet+offset, (char *) &id, sizeof(id)); offset += sizeof(id); // pack cost to server unsigned short cost = htons(r->cost); memcpy(server.packet+offset, (char *) &cost, sizeof(cost)); offset += sizeof(cost); r = (Route *) r->next; } // thought for error checking -- should we verify path to dest. server is valid? return size; } // unpack route update and check if any routes available at lower cost int unpackUpdate(int from, unsigned char *inPacket, int pSize) { int vectorCount = (pSize-4)/8; int offset = 0; int neighborCost; // unpack field count unsigned short n_fieldCount; memcpy((char *) &n_fieldCount, inPacket+offset, sizeof(n_fieldCount)); unsigned short fieldCount = ntohs(n_fieldCount); offset += sizeof(fieldCount); if (fieldCount != vectorCount) { if (DEBUG) { printf("fieldCount: %d\n", fieldCount); printf("vectorCount: %d\n", vectorCount); } return 0; } // intentional skip (2 bytes) offset += sizeof(fieldCount); int i; Route nr; int costToNeighbor = getDestCost(from); for (i = 0; i < fieldCount; i++) { // unpack destionation router ip (aka "server ip") struct sockaddr_in ip; memcpy((char *) &ip.sin_addr, inPacket+offset, sizeof(ip.sin_addr)); strcpy(nr.ip, inet_ntoa(ip.sin_addr)); offset += sizeof(ip.sin_addr); // unpack server id unsigned short n_id; memcpy((char *) &n_id, inPacket+offset, sizeof(n_id)); nr.dest = ntohs(n_id); offset += sizeof(n_id); // unpack cost to server unsigned short n_cost; memcpy((char *) &n_cost, inPacket+offset, sizeof(n_cost)); nr.cost = ntohs(n_cost); offset += sizeof(n_cost); nr.nextHop = from; if (DEBUG) { printf("unpack: (ip, dest, cost) = (%s, %d, %d) (from: %d)\n", nr.ip, nr.dest, nr.cost, nr.nextHop); printf("nr.dest -> getDestCost(%d) = %d\n", nr.dest, getDestCost(nr.dest)); printf("from -> getDestCost(%d) = %d\n", from, getDestCost(from)); } // our cost to route providing routing information neighborCost = getDestCost(from); // check if current path goes through INFINITY neighbor (bad) Route *r = server.route; while (r) { if (r->dest == nr.dest) { if (getDestCost(r->nextHop) == INFINITY) { updateRoute(nr.nextHop, nr.dest, neighborCost + nr.cost); } } r = (Route *) (r->next); } // check if neighbor to dest cost has increased r = server.route; while (r) { if (r->nextHop == from && r->dest == nr.dest) { updateRoute(nr.nextHop, nr.dest, neighborCost + nr.cost); } r = (Route *) (r->next); } // check if route is lower cost if (getDestCost(nr.dest) > (neighborCost + nr.cost)) { // cost is lower -- go with lower cost route updateRoute(nr.nextHop, nr.dest, neighborCost + nr.cost); } } if (DEBUG) printf("\n"); return 1; } // resolve neighbor id to ip void idToIp(int id, char *ip) { Neighbor *n = server.neighbor; while (n) { if (n->id == id) { memcpy(ip, n->ip, sizeof(n->ip)); return; } n = (Neighbor *) n->next; } ip = NULL; } // resolve neighbor ip to id int ipToId(char *ip) { Neighbor *n = server.neighbor; while (n) { if (strcmp(n->ip, ip) == 0) return n->id; n = (Neighbor *) n->next; } return BAD_ID; } // handle terminal input while running int commandInput(char *lineIn){ int servID1, servID2, linkCost, numArgs; int lineLen = 80; char command[lineLen]; char tmp[4]; strcpy(command, ""); servID1 = -1; servID2 = -1; tmp[0] = '\0'; linkCost = -1; numArgs = sscanf(lineIn, "%s %d %d %s", &command, &servID1, &servID2, &tmp); if (DEBUG) { printf("numArgs = %d\n", numArgs); printf("You typed: %s\n", lineIn); printf("%s - %d - %d - %d\n", command, servID1, servID2, linkCost); } if ( strcmp(command, "update") == 0 ) { if (numArgs != 4) { errorEncountered(command, "Invalid # of arguments!"); } else { if (strcmp(tmp, "inf") == 0) linkCost = INFINITY; else linkCost = atoi(tmp); if(update(servID1, servID2, linkCost)) success(command); } } else if( strcmp(command, "step") == 0 ) { printf("step entered!\n"); if (numArgs != 1) errorEncountered(command, "No arguments required!"); else { update_handler(14); success(command); } } else if( strcmp(command, "packets") == 0 ) { if (numArgs != 1) errorEncountered(command, "No arguments required!"); else { printf("%d\n", packetCount); packetCount = 0; success(command); } } else if( strcmp(command, "display") == 0 ) { printRoutes(); if (numArgs != 1) errorEncountered(command, "No arguments required!"); else {success(command);} } else if( strcmp(command, "disable") == 0 ) { printf("disable entered!\n"); if (numArgs != 2) errorEncountered(command, "Invalid # of arguments!"); else { if (disableNeighbor(servID1)) { success(command); } else { errorEncountered(command, "Invalid server id or problem resetting route."); } } } else if( strcmp(command, "crash") == 0 ) { if (numArgs != 1) { errorEncountered(command, "No arguments required!"); } return 1; } else { errorEncountered(command, "Invalid command!\n"); } return 0; } // disable neighbor (close connection, remove from neighbors, // adjust route to neighbor and through neighbor). int disableNeighbor(int id) { int result = 0; Neighbor *n = server.neighbor; while (n) { if (n->id == id) { close(n->sockfd); result = 1; break; } n = (Neighbor *) (n->next); } if (result) { delNeighbor(n->id); // 2 - set cost to INF in routing table AND // 3 - nextHop = -1 (invalid route) result = updateRoute(-1, n->id, INFINITY); } return result; } // called at interval specified on command line void update_handler(int signum) { if (DEBUG) printf("signum == %d\n", signum); int result; packUpdate(); Neighbor *n = server.neighbor; time_t now; time(&now); while (n) { if (n->ttl + 2*server.interval < now) { if (DEBUG) printf("disabling neighbor %d after >2 intervals\n", n->id); disableNeighbor(n->id); } else { result = sendUpdate(n->sockfd, n->sockaddr); } n = (Neighbor *) (n->next); } } // parse command line options void getOpts (int argc, char *argv[]) { // parse program options with getopt int c; opterr = 0; while ((c = getopt (argc, argv, "p:t:i:d:")) != -1) switch (c) { case 'p': // port server.port = atoi(optarg); break; case 't': // topology filename server.tfile = optarg; break; case 'i': // update interval server.interval = atoi(optarg); break; case 'd': // server id server.id = atoi(optarg); break; case '?': // error on anything else case ':': default: endProgram(USAGE); } } // exit program w/ usage details void endProgram(int val) { if (val == USAGE) { printf("server -p -t -i "); printf(" -d \n"); } exit(val); } // load data from files and create tables int loadData(char *file) { FILE *fd; char tmp[MAX_LENGTH]; char *sep = " "; char *token = NULL; int neighborCount, routeCount, i; fd = fopen(file, "r"); if (fd == 0) { printf("error opening file: %s\n", file); // memory leak exit(-1); } fgets(tmp, MAX_LENGTH, fd); neighborCount = atoi(tmp); fgets(tmp, MAX_LENGTH, fd); routeCount = atoi(tmp); Neighbor *n; for(i = 0; i < neighborCount; i++) { n = (Neighbor *) malloc(sizeof(Neighbor)); fgets(tmp, MAX_LENGTH, fd); n->id = atoi(strtok(tmp, sep)); token = strtok(NULL, sep); strcpy(n->ip, token); n->port = atoi(strtok(NULL, sep)); addNeighbor(n); } if (DEBUG) printNeighbors(); Route *r; for(i = 0; i < routeCount; i++) { r = (Route *) malloc(sizeof(Route)); fgets(tmp, MAX_LENGTH, fd); sscanf(tmp, "%d %d %d", &r->nextHop, &r->dest, &r->cost); // validate routing record for us (1st field matches our id) if (r->nextHop != server.id) { free(r); continue; } r->nextHop = r->dest; // add destination ip to route record idToIp(r->dest, r->ip); addRoute(r); } if (DEBUG) printRoutes(); // loop through servers -- if not in routes, add to routes w/ cost inf n = server.neighbor; while (n) { if (!destPresent(n->id)) { Route *r = (Route *) malloc(sizeof(Route)); if (n->id == server.id) r->nextHop = server.id; else r->nextHop = -1; // we have no next hop to this router r->dest = n->id; if (n->id == server.id) r->cost = 0; else r->cost = INFINITY; addRoute(r); } n = (Neighbor *) (n->next); } if (DEBUG) printRoutes(); // loop through routes -- if cost INFINITY remove invalid neighbor n = server.neighbor; while (n) { if (destRouteInf(n->id)) delNeighbor(n->id); if (n->id == server.id) { // preserve our own ip strcpy(server.ip, n->ip); delNeighbor(n->id); } n = (Neighbor *) (n->next); } if (DEBUG) printNeighbors(); // special case - add our ip to our route record r = server.route; while (r) { if (r->nextHop = server.id) { strcpy(r->ip, server.ip); break; } r = (Route *) (r->next); } // set initial ttl values on neighbors n = server.neighbor; while (n) { time(&n->ttl); n = (Neighbor *) (n->next); } } // strip new line from end of char * void stripNL (char *string) { int len = strlen(string); if (len > 0 && string[len-1] == '\n') string[len-1] = '\0'; } // add neighbor to LL void addNeighbor(Neighbor *new) { // add new neighbor to front of list new->next = (Neighbor *) (server.neighbor); server.neighbor = new; } // add route to LL void addRoute(Route *new) { // add new route to front of list new->next = (Route *) (server.route); server.route = new; } // remove neighbor from LL int delNeighbor(int id) { if (DEBUG) printf("delNeighbor for id = %d\n", id); Neighbor *n, *nprior; int result = 0; n = server.neighbor; nprior = NULL; while (n) { if (n->id == id) { // is it head of list? if (n == server.neighbor) { server.neighbor = (Neighbor *) (n->next); free(n); result = 1; } else { nprior->next = n->next; free(n); result = 1; } } nprior = n; n = (Neighbor *) (n->next); } return result; } // check if route to NEIGHBOR is present int routePresent(int id) { Route *r = server.route; while(r) { if (r->nextHop == id) return 1; r = (Route *) (r->next); } return 0; } // check if destation present int destPresent(int id) { Route *r = server.route; while(r) { if (r->dest == id) return 1; r = (Route *) (r->next); } return 0; } // set destination route to INFINITY int destRouteInf(int id) { Route *r = server.route; while (r) { if (r->dest == id && r->cost == INFINITY) return 1; r = (Route *) (r->next); } return 0; } // check if neighbor is present int neighborPresent(int id) { Neighbor *n = server.neighbor; while(n) { if (n->id == id) return 1; n = (Neighbor *) (n->next); } return 0; } // display routes void printRoutes() { Route *r = server.route; if (DEBUG) printf("Routing table for router %d:\n", server.id); while (r) { // special cases: // 1. self as nextHop // 2. cost == INFINITY //printf("%d %d %d %s\n", r->dest, r->nextHop, r->cost, r->ip); printf("%d %d %d\n", r->dest, r->nextHop, r->cost); r = (Route *) (r->next); } } // display neighbors void printNeighbors() { Neighbor *n = server.neighbor; if (DEBUG) printf("Neighbors for router %d:\n", server.id); while (n) { printf("\t%d %s\n", n->id, n->ip); n = (Neighbor *) (n->next); } } // update cost to destination (just cost, not nextHop) int setRouteCost(int id, int dest, int cost) { Route *r = server.route; int result = 0; while(r) { if (r->nextHop == id && r->dest == dest) { r->cost = cost; result = 1; } r = (Route *) (r->next); } return result; } // get destination cost int getDestCost(int dest) { Route *r = server.route; while (r) { if (r->dest == dest) return r->cost; r = (Route *) (r->next); } return INFINITY; } // update route (nextHop) & cost int updateRoute(int nextHop, int dest, int cost) { Route *r = server.route; int result = 0; while (r) { if (r->dest == dest) { r->nextHop = nextHop; r->cost = cost; result = 1; } r = (Route *) (r->next); } return result; } // update link cost (triggered by console input) int update(int id, int dest, int cost) { if (id != server.id) { errorEncountered("update", "Cannot change link cost for other routers."); return -1; } if (!neighborPresent(dest)) { errorEncountered("update", "Destination not a neighbor."); return -1; } if (cost <= 0) { errorEncountered("update", "Cost must be a positive value."); return -1; } if (cost > INFINITY) cost = INFINITY; if (setRouteCost(dest, dest, cost) == 1) { return 1; } else { errorEncountered("update", "Unknown error setting route cost."); return 0; } } // connect to neighbor router via UDP int connectRouter(Neighbor *router) { int sfd = socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP); if (sfd < 0) { if (DEBUG) printf("ERROR with sockfd\n"); } bzero((char *) &router->sockaddr, sizeof(router->sockaddr)); router->sockaddr.sin_family = AF_INET; router->sockaddr.sin_port = htons(router->port); if (inet_aton(router->ip, &router->sockaddr.sin_addr) == 0) { printf("Error: could not connect to router %s on port %d.\n", router->ip, router->port); } return sfd; } // send update packet via sockfd to destination in serv_addr int sendUpdate(int sockfd, struct sockaddr_in serv_addr) { //printf("sendUpdate: server.packetLength = %d\n", server.packetLength); return sendto( sockfd, server.packet, server.packetLength, 0, (struct sockaddr *) &serv_addr, sizeof(serv_addr) ); }