ＲＩＰ?。幔睿洹。希樱校啤。遥铮酰簦椋睿纭。校颍铮簦铮悖铮欤?/h1>
2009-10-22 08:13:20王暉
商情 2009年21期
王 暉
Abstract:Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) routing protocols are most widely used IGP. The purpose of this paper is to illustrate something as follows:1. Description of RIP,Description of OSPF. 2. Comparison between RIP (DV) and OSPF (LS) routing protocols.3. How reconvergence times can be improved. 4.Explanations of the consequences of least-cost routing in a single-service inter-network.5. How source-routing mechanisms can be used to improve overall network efficiency.
Key words:RIP OSPF reconvergence timesnetwork efficiency
1 Introduction
This paper completes the overview of internet routing by examining how a router in an autonomous system learns about other networks within its autonomous systems and how to improve the overall network efficiency.
2 Description of RIP
2.1 Overview of RIP
RIP(Routing Information Protocols)is one of the most common Distance-Vector Algorithm protocols. RIP is one of the most widely used IGP (Interior Gateway Protocol) and AS (Autonomous System) uses it for information propagation. Distances from destination address to router are measured in RIP through hop counting and this information are contained in update messages.
2.2 Operation of RIP
2.2.1 Initialization
Initialization process is aimed at knowing neighbour network addresses. In the process of initialization, a RIP router broadcasts the General RIP Request messages in its AS. The General RIP Request messages reach the neighbouring RIP routers and a reply to response the requesting router is sent back. Routers use received information and Distance-Vector Algorithm to make up its own routing table.
2.2.2 Update
a. General Update Process
The RIP router is also always ready to listen for neighbouring routers' RIP announcements in order to add or update the routes to its own routing table. A routing update message is broadcasted by a RIP router every 30 seconds, called periodic timer. This kind of request broadcast gets RIP information on each neighbouring interface. received RIP information is compared by Router with the content in its original routing table.
If there are new entries, router will add it into its routing table.
If there is a shorter distance route, router will update existing one.
If equal-distance, router remains what it is.
The algorithm for RIP updating is as following:
Receive: a response RIP message
(1)Add one hop to the hop count for each advertised destintion.
(2)Repeat the following steps for each advertised destination:
If (destination not in the routing table)
Add the advertised information to the table.
Else if (next-hop field is the same)
Remain the routing table.
Else If (advertised hop count smaller than one in the table)
Replace entry in the routing table
(3)Return.
b. Failure Update Process
Something unexpected may lead to failure when getting router information, such as failure in router's interfaces or failure within router caused by power outage or other hardware or software factors.Once this situation emerges, other routers can not be acknowledged immediately. So expiration timer and garbage collection timer are built in RIP update process to deal with this kind of situation.
An expiration timer is aim at controlling the validation of a route. Once a router receives a routing update message, the expiration timer is set to 180 seconds. If there is no routing update message available for 180 seconds, the hop count of that route is set to 16, indicating that destination is unreachable.
Garbage collection timer is for judging whether to delete route information from its routing table. When the route has been set to invalid, it does not disappear immediately. It will broadcast a 16 hop count and set garbage collection timer 120 seconds. When garbage collection timer reaches 0 seconds, the router will delete the corresponding routing information from its table and acknowledge its neighbouring routers.
From above, we know that a failure within the network will be renewal and acknowledge other routers throughout the network after 300 seconds.
3 Description of OSPF
3.1 Overview of OSPF
OSPF (Open Shortest Path First) is a typical Link-state routing protocol for Internet Protocol networks. There are two primary characteristics of OSPF. One is that the specification of protocol is in the public domain and the other is that OSPF is based on SPF algorithm, which is known as the Dijkstra algorithm. Dijkstra's algorithm is used by OSPF to measure the minimum cost in order to determine route.
3.2 Operation of OSPF
3.2.1 Building Adjacency and LSDB of routers
In order to exchanging routing information, Adjacency is a relationship made among neighbouring routers. Hello message is broadcasted by OSPF router and valid LSA from other routers in the AS is sent back in order to create the LSDB.An LSA which contains its own configuration is sent by each router initially. And LSAs are exchanged with its neighbour routers. Through this kind of exchange, flooding of LSAs in the AS, OSPF operates efficiently in the process of LSA information's propagation.
3.2.2 Selection of DR (designated router)/BDR
In multi-access network, a router should be selected as the DR with priority of high value. And the second high priority value router should be selected as BDR.
3.2.3 Foundation of Link State Database
Routers broadcast and receive Hello messages among routers in the AS initially . If one of the routers find that a updated message is available, router will send a request for LSAs (process called Link State Request). And when request message reaches the router , it sends what it needs (process called Link State Update). By this method, router sets up its own Link State Database and applys Dijkstra's algorithm to find a lowest-cost route and then renews its routing table.
In Multi-access network, DR/BDR controls information exchange with other networks and inside the network.
3.2.4 Proper routes selection
When a whole link state database is available to a router, the router will use SPF algorithm to compute and build a routing table based on least-cost principle.
Some alternative links can also be available within the system.
3.2.5 Maintaining routing information
If there are some link states changed, OSPF will inform other routers in AS in the method of flooding. OSPF router receives updated messages then updates its own Link State Database and computes new routing table. The OSPF propagates the updated LSA to other routers.OSPF routing information will automatically update every 30 minutes without changing.
4 Comparison between RIP (DV) and OSPF (LS) routing protocols
RIP is a traditional routing protocol, works well in relatively small network. The rapid development of Internet in current runs out to RIP ability, OSPF improves many aspects which is short for RIP protocol, but it still has some weaknesses.
4.1 Metric
RIP belongs to Distance Vector routing protocol, "hop" is used as its measurement metric. No delay is considered in RIP and routing depends only on the hop number. The router with few hops is selected as the path which can has a long delay and at the same time there is a route with short delay and many hops. RIP can not carry out routing summary at arbitrary bit because of lack of regional information. OSPF is a link state routing protocol and bandwidth and delay are its measurement for routing metric.
4.2 Scale
RIP has a maximum 15 hops. So a RIP routing cannot across the network which is more than 15 hops away.OSPF doesn't has such limitation. OSPF also supports the TOS (Type of Service) routing. Therefore, OSPF has advantages for large-scale network application.
4.3 Support
RIP does not support variable-length subnet mask (VLSM), which makes it less supportive to the current trend of IP addresses shortage and the flexibility of variable-length subnet mask. OSPF supports VLSM.
4.4 Broadcast
RIP broadcasts the routing table regularly, which is a huge waste of bandwidth, especially for large-wide-area network. OSPF routing protocol broadcasts routing updates only when some information is updated by the method of IP multicast to send the information of link state update ,which saves bandwidth.
4.5 Hierarchy
RIP network belongs to flat network.OSPF establishes the hierarchy within the network, so that information can be transmitted within a certain range, which makes full use of link resources.
4.6 Security
RIP doesn't take no any safe measure. OSPF uses licensing mechanism for network security in the process of transmitting information. OSPF supports authentication based on the interface.
4.7 Convergence
RIP has low convergence.OSPF has fast convergence,can transfer routing changes to the whole autonomous system as quickly as possible.As is divided into different regions based on regional concept, and the amount of information is greatly reduced. OSPF applys trigger update mechanism, and RIP uses periodically updates. So OSPF converges much faster than RIP.
Comparison between the two protocols shows that OSPF is more suitable to adapt to the increase Internet network nowadays and becomes the main Internet routing protocol based on the nature routing protocol.
5 How reconvergence times can be improved
When concerning with IGP, low reconvergence time is a critical problem. There are some methods to improve the reconvergence times: Split Horizon; Split Horizon with Poison Reverse; Triggered Updates; Hold Down.
5.1 Split Horizon
Split Horizon is considered as the most basic method to lower convergence time. It lets router remember every route message's source and does not transmit it at the interface where this message is received. Split Horizon prevents the propagation of "fake" messages and brings down the amount of route updates message resulting in bandwidth of network saving.
5.2 Split Horizon with Poison Reverse
Poison reverse brings down count-to-infinity and routing loops greatly in a multi-path inter-network in way of still advertising broadcast with a maximum 16 hop count, designing that the network is out of reach.
Though Split Horizon with Poison Reverse increases the size of route message, yet reduces routing loops,comparing with Split Horizon.
5.3 Triggered Updates
Triggered updates suppot a router to advertise changed message to neighboured router immediately, other than wait update period of 30-second. Changed topology would be quickly known within the internet, bringing down the possibility of Count-to-Infinity problem. Triggered updates lower the convergence time by adding more broadcast traffic as the propagation of triggered updates.
5.4 Hold Down
Hold down timer doesn't accept any route updates information of the same address within the assigned time intervals. It brings down fluctuate of route and improves network stability.
6 Explanations of consequences of least-cost routing in a single-service inter-network
Every router will choose a least-cost path as its best metric from a lot of paths to destination. Router update routing information of best metric in its routing table.In a single-service inter-network,few least-cost routes are available. Every router chooses least-cost route and computes its table with the best metric resulting that many router forwards information packets by the same least-cost path. This path is full of traffic and congestion happens which leads to packets' queue and long waiting time.
7 Conclusions
Source-routing mechanisms used to improve overall network efficiency. Source-routing mechanism is a kind of technology whereby the packet's sender can determine the route to propagate its packet through the network. In source-routing, the source, namely sender, detemines which route the packet propagates with,source-routing is used by manager to compel an alternate route in addition to least-cost path so as to prevent congestion (e.g. consequences of least-cost routing in single-service in inter-network). Source-routing mechanism brings about some advantages, such as used for load balancing, for increased robustness, for rapid recovery in case of routes changing. The overall network efficiency is improved through these advantages.
Bibliography
[1]Douglas E. Comer. Internetworking with TCP/IP, Principles, protocols, and architecture"(fifth edition).
[2]http://en.wikipedia.org/wiki/OSPF.
王 暉
Abstract:Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) routing protocols are most widely used IGP. The purpose of this paper is to illustrate something as follows:1. Description of RIP,Description of OSPF. 2. Comparison between RIP (DV) and OSPF (LS) routing protocols.3. How reconvergence times can be improved. 4.Explanations of the consequences of least-cost routing in a single-service inter-network.5. How source-routing mechanisms can be used to improve overall network efficiency.
Key words:RIP OSPF reconvergence timesnetwork efficiency
1 Introduction
This paper completes the overview of internet routing by examining how a router in an autonomous system learns about other networks within its autonomous systems and how to improve the overall network efficiency.
2 Description of RIP
2.1 Overview of RIP
RIP(Routing Information Protocols)is one of the most common Distance-Vector Algorithm protocols. RIP is one of the most widely used IGP (Interior Gateway Protocol) and AS (Autonomous System) uses it for information propagation. Distances from destination address to router are measured in RIP through hop counting and this information are contained in update messages.
2.2 Operation of RIP
2.2.1 Initialization
Initialization process is aimed at knowing neighbour network addresses. In the process of initialization, a RIP router broadcasts the General RIP Request messages in its AS. The General RIP Request messages reach the neighbouring RIP routers and a reply to response the requesting router is sent back. Routers use received information and Distance-Vector Algorithm to make up its own routing table.
2.2.2 Update
a. General Update Process
The RIP router is also always ready to listen for neighbouring routers' RIP announcements in order to add or update the routes to its own routing table. A routing update message is broadcasted by a RIP router every 30 seconds, called periodic timer. This kind of request broadcast gets RIP information on each neighbouring interface. received RIP information is compared by Router with the content in its original routing table.
If there are new entries, router will add it into its routing table.
If there is a shorter distance route, router will update existing one.
If equal-distance, router remains what it is.
The algorithm for RIP updating is as following:
Receive: a response RIP message
(1)Add one hop to the hop count for each advertised destintion.
(2)Repeat the following steps for each advertised destination:
If (destination not in the routing table)
Add the advertised information to the table.
Else if (next-hop field is the same)
Remain the routing table.
Else If (advertised hop count smaller than one in the table)
Replace entry in the routing table
(3)Return.
b. Failure Update Process
Something unexpected may lead to failure when getting router information, such as failure in router's interfaces or failure within router caused by power outage or other hardware or software factors.Once this situation emerges, other routers can not be acknowledged immediately. So expiration timer and garbage collection timer are built in RIP update process to deal with this kind of situation.
An expiration timer is aim at controlling the validation of a route. Once a router receives a routing update message, the expiration timer is set to 180 seconds. If there is no routing update message available for 180 seconds, the hop count of that route is set to 16, indicating that destination is unreachable.
Garbage collection timer is for judging whether to delete route information from its routing table. When the route has been set to invalid, it does not disappear immediately. It will broadcast a 16 hop count and set garbage collection timer 120 seconds. When garbage collection timer reaches 0 seconds, the router will delete the corresponding routing information from its table and acknowledge its neighbouring routers.
From above, we know that a failure within the network will be renewal and acknowledge other routers throughout the network after 300 seconds.
3 Description of OSPF
3.1 Overview of OSPF
OSPF (Open Shortest Path First) is a typical Link-state routing protocol for Internet Protocol networks. There are two primary characteristics of OSPF. One is that the specification of protocol is in the public domain and the other is that OSPF is based on SPF algorithm, which is known as the Dijkstra algorithm. Dijkstra's algorithm is used by OSPF to measure the minimum cost in order to determine route.
3.2 Operation of OSPF
3.2.1 Building Adjacency and LSDB of routers
In order to exchanging routing information, Adjacency is a relationship made among neighbouring routers. Hello message is broadcasted by OSPF router and valid LSA from other routers in the AS is sent back in order to create the LSDB.An LSA which contains its own configuration is sent by each router initially. And LSAs are exchanged with its neighbour routers. Through this kind of exchange, flooding of LSAs in the AS, OSPF operates efficiently in the process of LSA information's propagation.
3.2.2 Selection of DR (designated router)/BDR
In multi-access network, a router should be selected as the DR with priority of high value. And the second high priority value router should be selected as BDR.
3.2.3 Foundation of Link State Database
Routers broadcast and receive Hello messages among routers in the AS initially . If one of the routers find that a updated message is available, router will send a request for LSAs (process called Link State Request). And when request message reaches the router , it sends what it needs (process called Link State Update). By this method, router sets up its own Link State Database and applys Dijkstra's algorithm to find a lowest-cost route and then renews its routing table.
In Multi-access network, DR/BDR controls information exchange with other networks and inside the network.
3.2.4 Proper routes selection
When a whole link state database is available to a router, the router will use SPF algorithm to compute and build a routing table based on least-cost principle.
Some alternative links can also be available within the system.
3.2.5 Maintaining routing information
If there are some link states changed, OSPF will inform other routers in AS in the method of flooding. OSPF router receives updated messages then updates its own Link State Database and computes new routing table. The OSPF propagates the updated LSA to other routers.OSPF routing information will automatically update every 30 minutes without changing.
4 Comparison between RIP (DV) and OSPF (LS) routing protocols
RIP is a traditional routing protocol, works well in relatively small network. The rapid development of Internet in current runs out to RIP ability, OSPF improves many aspects which is short for RIP protocol, but it still has some weaknesses.
4.1 Metric
RIP belongs to Distance Vector routing protocol, "hop" is used as its measurement metric. No delay is considered in RIP and routing depends only on the hop number. The router with few hops is selected as the path which can has a long delay and at the same time there is a route with short delay and many hops. RIP can not carry out routing summary at arbitrary bit because of lack of regional information. OSPF is a link state routing protocol and bandwidth and delay are its measurement for routing metric.
4.2 Scale
RIP has a maximum 15 hops. So a RIP routing cannot across the network which is more than 15 hops away.OSPF doesn't has such limitation. OSPF also supports the TOS (Type of Service) routing. Therefore, OSPF has advantages for large-scale network application.
4.3 Support
RIP does not support variable-length subnet mask (VLSM), which makes it less supportive to the current trend of IP addresses shortage and the flexibility of variable-length subnet mask. OSPF supports VLSM.
4.4 Broadcast
RIP broadcasts the routing table regularly, which is a huge waste of bandwidth, especially for large-wide-area network. OSPF routing protocol broadcasts routing updates only when some information is updated by the method of IP multicast to send the information of link state update ,which saves bandwidth.
4.5 Hierarchy
RIP network belongs to flat network.OSPF establishes the hierarchy within the network, so that information can be transmitted within a certain range, which makes full use of link resources.
4.6 Security
RIP doesn't take no any safe measure. OSPF uses licensing mechanism for network security in the process of transmitting information. OSPF supports authentication based on the interface.
4.7 Convergence
RIP has low convergence.OSPF has fast convergence,can transfer routing changes to the whole autonomous system as quickly as possible.As is divided into different regions based on regional concept, and the amount of information is greatly reduced. OSPF applys trigger update mechanism, and RIP uses periodically updates. So OSPF converges much faster than RIP.
Comparison between the two protocols shows that OSPF is more suitable to adapt to the increase Internet network nowadays and becomes the main Internet routing protocol based on the nature routing protocol.
5 How reconvergence times can be improved
When concerning with IGP, low reconvergence time is a critical problem. There are some methods to improve the reconvergence times: Split Horizon; Split Horizon with Poison Reverse; Triggered Updates; Hold Down.
5.1 Split Horizon
Split Horizon is considered as the most basic method to lower convergence time. It lets router remember every route message's source and does not transmit it at the interface where this message is received. Split Horizon prevents the propagation of "fake" messages and brings down the amount of route updates message resulting in bandwidth of network saving.
5.2 Split Horizon with Poison Reverse
Poison reverse brings down count-to-infinity and routing loops greatly in a multi-path inter-network in way of still advertising broadcast with a maximum 16 hop count, designing that the network is out of reach.
Though Split Horizon with Poison Reverse increases the size of route message, yet reduces routing loops,comparing with Split Horizon.
5.3 Triggered Updates
Triggered updates suppot a router to advertise changed message to neighboured router immediately, other than wait update period of 30-second. Changed topology would be quickly known within the internet, bringing down the possibility of Count-to-Infinity problem. Triggered updates lower the convergence time by adding more broadcast traffic as the propagation of triggered updates.
5.4 Hold Down
Hold down timer doesn't accept any route updates information of the same address within the assigned time intervals. It brings down fluctuate of route and improves network stability.
6 Explanations of consequences of least-cost routing in a single-service inter-network
Every router will choose a least-cost path as its best metric from a lot of paths to destination. Router update routing information of best metric in its routing table.In a single-service inter-network,few least-cost routes are available. Every router chooses least-cost route and computes its table with the best metric resulting that many router forwards information packets by the same least-cost path. This path is full of traffic and congestion happens which leads to packets' queue and long waiting time.
7 Conclusions
Source-routing mechanisms used to improve overall network efficiency. Source-routing mechanism is a kind of technology whereby the packet's sender can determine the route to propagate its packet through the network. In source-routing, the source, namely sender, detemines which route the packet propagates with,source-routing is used by manager to compel an alternate route in addition to least-cost path so as to prevent congestion (e.g. consequences of least-cost routing in single-service in inter-network). Source-routing mechanism brings about some advantages, such as used for load balancing, for increased robustness, for rapid recovery in case of routes changing. The overall network efficiency is improved through these advantages.
Bibliography
[1]Douglas E. Comer. Internetworking with TCP/IP, Principles, protocols, and architecture"(fifth edition).
[2]http://en.wikipedia.org/wiki/OSPF.
