As the Internet becomes the ubiquitous infrastructure for various applications, demands on the reliability, availability and security of routing protocols in the Internet are becoming more stringent. Unfortunately, failures are still common in the daily operation of a network. Service disruption for even a short time can seriously affect the quality of real-time applications, such as VoIP and video on demand applications. Moreover, critical business and government applications require routing protocols to be robust against malicious attacks, such as denial of Service attacks. This dissertation proposes three techniques to address some reliability and security concerns in intra-domain (distance vector) routing protocols and inter-domain (path vector) routing protocols. The first technique addresses the problem of service disruption that arises from sudden link failures in distance vector routing protocols. We consider two types of link failures: single link failures and shared risk link group failures. For single link failures, we propose an IP fast reroute mechanism to reroute packets around the failed links. This fast reroute mechanism is the first that does not require complete knowledge of the network topology and does not require changing of the original routing protocol. This mechanism proactively computes a set of relay nodes that can be used to tunnel the rerouted packets immediately after the detection of a link or node failure. The mechanism includes an algorithm for a node to automatically identify itself as a candidate relay node for a reroute link and notify the source node of the reroute link of its candidacy. The source node can then decide the validity of a candidate relay node. The mechanism also includes an algorithm to suppress redundant notification messages. We then extend our IP fast reroute mechanism for single link failures to accommodate shared risk link group failures. We achieve this goal by introducing one more bit information. Through simulations, I show that the proposed mechanisms succeed in rerouting around failed links about 100% of the time, with the length of the reroute path being comparable to the length of the re-converged shortest path. The second technique addresses the problem that arises from allowing any node to route data packets to any other node in the network (and consequently allow any adversary node to launch DoS attacks against other nodes in the network). To solve this problem, we propose a blocking option to allow a node u to block a specified set of nodes and prevent each of them from sending or forwarding packets to node u. The blocking option intends to discard violating packets near the adversary nodes that generated them rather than near their ultimate destinations. We then discuss unintentionally blocked nodes, called blind nodes and extend the routing protocols to allow each node to communicate with its blind nodes via some special nodes called joint nodes. Finally, I show, through extensive simulation, that the average number of blind nodes is close to zero when the average number of blocked nodes is small. The third technique addresses the problem that arises when a set of malicious ASes in the Internet collude to hijack an IP prefix from its legitimate owner in BGP. (Note that none of previous proposals for protecting BGP against IP prefix hijacking is effective when malicious ASes can collude.) To solve this problem, we propose an extension of BGP in which each listed AS in an advertised route supplies a certified full list of all its peers. Then I present an optimization where each AS in an advertised route supplies only a balanced peer list, that is much smaller than its full peer list. Using real Internet topology data, I demonstrate that the average, and largest, balanced peer list is 92% smaller than the corresponding full peer list. Furthermore, in order to handle the dynamics of the Internet topology, we propose algorithms on how to issue certificates to reflect the latest changes of the Internet topology graph. Although the results in this dissertation are presented in the context of distance vector and path vector routing protocols, many of these results can be extended to link state routing protocols as well. / text