Advanced Routing Protocols Gpsr And Egp

As can be evidenced by a simple study of different types of routing protocols, these protocols come in all shapes, sizes and included functionalities. This is mainly due to the idea that each situation, including the hardware being used, functionality of the hardware, and type of collection mechanism, requires a different way to process the incoming data. With certain situations there may also be the need for a conservation of power, which may lead to less ability for computation and communication distance. Therefore, in the following paragraphs, this paper will cover two such protocols used within the networking world, GPSR and EGP. While they are different in terms of their applications, the following paragraphs will give a brief background to the protocol and the industry view on them, thus leading to a discussion of the similarities and differences between them. GPSR. Greedy Perimeter Stateless Routing is a protocol used within dynamic sensor environments to establish connections between nodes which are inherently limited in both computational and power resources. The problem with this is that sensor nodes which use protocols such as Greedy Perimeter Stateless Routing are used in an ad-hoc fashion in which multiple nodes may have to communicate with each other before reaching a wired infrastructure. This creates an additional issue of not having a router or other type of forwarding device between nodes, thus forcing each node to do its own routing and forwarding, based on the protocol which is implemented on it [1]. Combined with the flaws that come with using Distance Vector or Link state routing methods, there was a need to develop new protocols to use in mobile sensor routing and enable a multi hop environment to function efficiently. In a distance vector network, it is common practice to share routing information with neighbors so that routing tables within immediate neighbors will be the same and up to date based on what each of them receives from the other. While this works quite well for wired routing and even single hop wireless networks, in a mobile network the constant movement of nodes and change in the topology leads to shortcomings in the distance vector protocol, mainly being that routing tables expire and become inaccurate within a rather

short amount of time [5]. On the other hand, because link state tries to map the entire network to which it is a part of and then inform all nodes on the network, it too has an issue, but quite the opposite of distance vector. Link state will send out discovery messages at a timed interval to ensure the network topology it has in its database is correct, but will find a change in the network almost every time it does so because of the network’s mobile property. Therefore, there will be a constant flood of topology changes within the network, leading to the exhaustive power consumption of each node, merely to receive, process, and store these changes within its link state database. Obviously, the cases demonstrated will not work for such a dynamic sensor array and thus spawned the development of Greedy Perimeter Stateless Routing (GPSR) [5]. When wireless sensor networks first started being used, a proposition of using caching methods similar to that of caching internet pages for quick use by web browsers, was given and spawned the creation of a number of different protocols to utilize this methodology [1]. This method allowed for sensors to request an update on demand from other sensors to which it plans to send its payload, and expects them to forward the payload onward. This makes it so that nodes are not being flooded with messages, but when requested, provide other nodes with their routing tables and in a timely manner will update their own databases to allow for the forwarding of packets through them. This update will occur if a timer has expired on the next request for the node to forward on a packet. GPSR has mainly been proposed for three types of networks in which its developers thought that it would work best [3][6][5]. The first and most prominent is ad-hoc networks in which there is no established backbone network or any sort wired infrastructure to affix nodes to. This can be any number of situations including disaster recovery or rescuer needs, military operations in areas which may not have any sort of network ability, or conferences in which a backbone network is unavailable or just cannot handle the load of as many computers connecting to it as desired. The only drawback to this is the

preference for the nodes to have the same amount of radio power and be on the same geographical plane, or “planar subgraph” as [3] phrases it. The second proposed use for GPSR is sensor networks in which sensors talk to each other over multihop systems and relay messages to computers for forest fire tracking, weather system prediction or automated tasks. GPSR is especially helpful in these sorts of situations because of the limited amount of communication range and power that these nodes usually have due to their limited size and portability. By using GPSR in this specific situation, it can be useful based on the less need for power, and exertion of power only when the node is needed or being communicated with [6]. The final proposed use for GPSR is rooftop deployment, a common practice within large metropolitan areas to avoid the need for installing wireless access points throughout buildings and city establishments. The antennas used for rooftop deployment enable a city to deploy a metropolitan area wireless network, such as the one used in San Francisco, California, without a need for access points to be installed on a wired infrastructure, thus requiring a larger amount of equipment and a wired network within residential and privately owned establishments [5]. GPSR is used in industry when it comes to mobile sensor systems, such as GPS, but is seen as inherently insecure due to each node being able to hear whatever its neighbors are broadcasting. When used in the real world, GPSR scans for adjacent neighbors which can ensure that packets will reach their destination. This is done by calculating the distance between the source and second node in the neighborhood and relating that distances to that of the neighbor to the destination. When transferring packets between each node, there is the ability for each node to modify the packet due to having to process and forward the packet onto the next node in the sequence which it will follow to get to the destination [5]. There have been a number of alternatives proposed to fix this such as [11] which uses a sort of count mechanism built right into the packet itself and increments itself if the packet is unmodified or decrements otherwise [11].

Industry views on the protocol in general are that it is generally scalable and usable within a relatively small network of around 50 nodes. Once this threshold is passed, issues arise based on link state databases growing too large for the sensor to handle and transmit without a degradation of power and time it takes to transmit the message. There is also the view that GPSR allows for robust deliverance of packets, but this is sometimes affected by sensors interfacing with different powered radios. GPSR is also a major research topic and is being researched into how it might be able to improve relatively small geographical area sensor routing. The authors of [10] discuss using a similar protocol to GPSR and combining it with what they call “Greedy Other Adaptive Face Routing (GOAFR)”. When routing is done between the source and destination nodes with GPSR, there is the downfall that the path taken may not be necessarily be the best in terms of metrics like link speed or latency. With GOAFR, there is the ability to create an expected route in which the number of hops is predicted, and a better path may be taken if there is a geographically shorter route, compared to the number within the path taken consisting of hops. Because GPSR allows for the use of GPS within the nodes which it connects, it seems that it will increase in popularity as more sensors are added to cars and in metropolitan areas to interface between nodes [6][3]. EGP. When the Department of Defense’s DARPANET was originally implemented, they ran into a number of problems with the expansion of the network as more facilities and institutions were given the ability and permission to participate in it. While the Gateway to Gateway protocol (GGP) provided a means for the routers from each facility to communicate (in the form of multiple autonomous systems communicating with each other), routing protocols began to evolve and thus allowed for different software and hardware to be installed in each individual autonomous system. No longer was it acceptable to use a hop-count based metric to determine the route from AS to AS, mainly because of the sheer size of the ever expanding DARPANET network [8]. This also created a number of problems including the lack

of an ability to do fault isolation because of the different protocols and software being used, as well as this software not being able to be adapted to expansion because of it having to communicate with multiple other pieces of software. With this lack of ability for DARPANET to expand, researchers also found that the need to advertise which protocol a router is using to all other routers on the network is unneeded and could possibly facilitate attacks on the source network. Both of these issues were thought about and began to be remedied in RFC 827 which stated these problems and was the first to propose that the internet would expand into a large number of autonomous systems which needed a common protocol to allow communication between a large number of autonomous systems [15]. Exterior Gateway protocol was originally designed and implemented in the early 1980’s with the first Request for Comments regarding the protocol being published in October of 1982. It was one of the original TCP/IP protocols used in the ARPANET and DARPANET military networks [7] but was obsoleted with the creation and widespread acceptance and use of Border Gateway Protocol. Before modern internet was implemented, EGP allowed for transport of datagrams between manual systems and autonomous systems without interruption of service to the user. This was mainly done between core routers and non-core routers which were the main backbone to the early internet as used within ARPANET and DARPANET. Information was able to be exchanged between the core routers and noncore routers which encompassed individual autonomous systems [7], while still providing net reachability information between the autonomous systems through which it traversed.[9] With this traversal through multiple types of networks, the number of networks and autonomous systems “are to be transparent to the end-user [7].” In other words, when a datagram is being transmitted between multiple networks to reach a final destination, the user should see little lag or latency, and see the traversal across all of the multiple networks that the datagram traverses across as a single pathway through a flat internet. This is to prevent the need for multiple protocols, but rather to inspire the creation of a single protocol

that had similar characteristics and could be implemented on a large scale basis between autonomous systems. Overall, EGP was used by the ARPANET and DARPANET defense networks in the early days of routing and network connectivity between autonomous systems. With the implementation and widespread standardization of BGP, EGP has been obsoleted and is currently unused within industry. This is because of the additional features that BGP added to EGP. The main problem with EGP is that it assumes that the network it is implemented on, in this case the internet, is structured in a tree type topology. Therefore, it tried to recreate the routing table and metrics to each network within its routing database by mapping the network in a tree form (See appendix a for examples.] It is obvious that the internet is by no means a tree type structure, and this was the driving factor for obsolescing EGP and implementing BGP. BGP has the ability to map the internet in whatever topology actually existed, rather than the assumed one. At the moment, BGP still uses EGP in some forms to discover networks external from the network that it is currently being run on. [14][13] As can be seen in the preceding paper, GPSR and EGP, while different, both provide an essential service to different types of networks with different needs. While EGP is being phased out, but still being used in the basic idea of BGP, GPSR is being experimented with and improved upon on a daily basis. EGP was mainly used within wired networks which were expected to only expand a certain amount, but added the ability to GGP to allow for a single protocol to be run on routers across the network. On the other hand, GPSR allows for routing to be done on the sensor itself and can be deployed in a vast environment where wireless communication and ad hoc networks are needed due to a lack of infrastructure. In the end, when comparing the two protocols discussed here, it comes down to a grandfather of routing protocols which was developed at a time when there was a significant need for expansion and the ability for multiple autonomous systems to communicate with each other, compared to a much younger generation of protocols that is currently used for wireless networks in multiple situations

where wires are unavailable and a need for on board routing exists. As stated at the beginning of the paper, routing protocols come in many shapes and sizes, and the uses of them, as seen here, justify the differences and immense number of protocols that exist. Appendix A.

Figure 1: An example of the assumed network structure as seen by EGP [16]

Figure 2: A network with the ability to be processed by BGP. Note that there is not a definite tree like structure here.[16] References

[1] Broch, Josh, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. "A performance comparison of multi-hop wireless ad hoc network routing protocols." International Conference on Mobile Computing and Networking (1998): 85-97. [2] "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks from Harvard University White Papers at ZDNet.co.uk." White Papers White Papers at ZDNet.co.uk. 17 Sept. 2000. Harvard University. 12 May 2009 . [3] "Greedy Perimeter Stateless Routing (GPSR)." UCL-CS Information. 16 Mar. 2004. 12 May 2009 . [4] "Greedy Perimeter Stateless Routing." Wiki.uni.lu. 18 Feb. 2005. University of Luxembourg. 12 May 2009 . [5] Karp, Brad, and H. T. Kung. "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks." Harvard School of Engineering and Applied Sciences - Research - Computer Science. 2000. Harvard University. 12 May 2009 .

[6] Karp, Brad. "Challenges in Geographic Routing: Sparse Networks, Obstacles, and Traffic Provisioning." UCL-CS Information. 21 May 2001. Berkeley, CA. 12 May 2009 . [7] Kozierok, Charles M. "The TCP/IP Guide - TCP/IP Exterior Gateway Protocol (EGP)." Welcome to The TCP/IP Guide! 20 Sept. 2005. The TCP/IP Guide. 12 May 2009 . [8] Kozierok, Charles M. "The TCP/IP Guide - TCP/IP Gateway-to-Gateway Protocol (GGP)." Welcome to The TCP/IP Guide! 20 Sept. 2005. The TCP/IP Guide. 12 May 2009 . [9] Mills, D. L. "RFC 904 - Exterior Gateway Protocol formal specification." IETF Tools. Apr. 1984. 12 May 2009 . [10] Moaveninejad, Kousha, Wen-Zhan Song, and Xiang-Yang Li. Washington State University Vancouver - Vancouver, WA. Illinois Institute of Technology. 12 May 2009 . [11] Pirzada, Asad Amir. "Trusted Greedy Perimeter Stateless Routing." IEEE Xplore. 2007. The University of Western Australia. 12 May 2009 . [12] Rekhter, J. "RFC 1092 (rfc1092) - EGP and policy based routing in the new NSFNET backbo." Internet RFC/FYI/STD/BCP Archives. Feb. 1989. T.J. Watson Research Center, IBM Corp. 12 May 2009 . [13] Rekhter, Y., and P. Gross. "RFC 1772 - Application of the Border Gateway Protocol in the Internet." IETF Tools. Mar. 1995. T.J. Watson Research Center, IBM Corp. 12 May 2009 . [14] Rekhter, Y., and T. Li. "RFC 1771 (rfc1771) - A Border Gateway Protocol 4 (BGP-4)." Internet RFC/FYI/STD/BCP Archives. Mar. 1995. T.J. Watson Research Center, IBM Corp. 12 May 2009 . [15] Rosen, Eric C. "RFC 827 - Exterior Gateway Protocol (EGP)." IETF Tools. Oct. 1982. Bolt Beranek and Newman Inc. 12 May 2009 . [16] Vakharia, Digant, and Sandip Patel. "Egp /bgp." Personal Home Pages (at UEL). 12 May 2009 .