Abstract:
A method for selecting a route in a routing protocol includes the steps of: measuring a message reachable time between a plurality of route information managers which manage route information on a network; constructing a reachable time table for managing the message reachable time; checking hop counts of different neighboring route information managers by a receiving route information manager which receives the same route information from the different neighboring route information managers; and selecting an optimum route based on the reachable time table when the neighboring route information managers have the same hop count. Thus, it is possible to reflect network status that varies constantly in selecting an optimum route in a routing protocol, thus maximizing optimum route effects and increasing transmission efficiency of a network.

Description:
CLAIM OF PRIORITY 
   This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C. § 119 from an application for  METHOD FOR SELECTING ROUTE IN ROUTING PROTOCOL  earlier filed in the Korean Intellectual Property Office on Jan. 4, 2005 and there duly assigned Serial No. 2005-0000590. 
   BACKGROUND OF THE INVENTION 
   1. Technical Field 
   The present invention relates to a routing protocol, and more particularly, to a method for selecting an optimum route by reflecting network changes in a routing protocol. 
   2. Related Art 
   A routing protocol is a communication regulation for network routing, and determines a route among devices (e.g., routers) organizing a network. For example, the routers designate an optimum route for packets by referring to a pre-stored routing table when there is a packet transmission request. The routing protocol is a protocol for delivering information (e.g., routing information) for updating the routing table among the routers. 
   Since the Internet has recently expanded extensively, it is difficult to update routing tables of all routers using one routing protocol. Thus, the Internet has been divided into autonomous systems (AS) operated by one management authority, and separate routing protocols are used for inner routing in respective autonomous systems and for outer routing between the autonomous systems, respectively. 
   The protocols most commonly used as an inner routing protocol and an outer routing protocol include a routing information protocol (RIP) and an open shortest path first (OSPF) as inner routing protocols, and a border gateway protocol (BGP) as an outer routing protocol. 
   RIP is a protocol using a distance vector algorithm which dynamically determines a shortest route depending on hop counts of the routers through which the RIP passes. OSPF is a protocol which supports routing through the shortest route by combining inter-node distance information and link status information with the routing information in real time so that users select the shortest route in an Internet network. BGP is a protocol for the exchange of routing information among gateway hosts in the network of the Autonomous System. 
   Recently, as the scale of a network has expanded, routing protocols have been getting more important for increasing transmission efficiency of the network. In other words, how quickly the routing protocol selects an optimum route by reflecting changes on the network has become a key factor. Conventional routing protocols, however, have focused on transmission reliability rather than processing speed. Moreover, the conventional routing protocols have been unable to adapt to changes on the network in selecting the optimum routing path. For example, BGP, as a protocol, has focused on how to reliably transmit routing information to neighboring routers, and thus it is relatively poor when it comes to updating the routing information through a fast route. 
   If one of the ASs (hereinafter, referred to as receiving AS) transmitting routing information using the BGP receives a plurality of the same route information from different neighboring ASs (hereinafter, referred to as transmitting ASs), the receiving AS determines whether the transmitting ASs have the same hop count. That is, the receiving AS determines whether the different neighboring ASs transmitting the same route information have the same hop count. As a result of that determination, if it is determined that the transmitting ASs have the same hop count, the receiving AS establishes an optimum route using the earliest received route information. Otherwise, the receiving AS establishes the optimum route using route information which is received from the AS having a smaller hop count than the receiving AS. 
   On the other hand, if it is determined that the receiving AS has not received the same route information from a plurality of different neighboring ASs, but has received different route information from different neighboring ASs, the receiving AS establishes the route using the received route information. 
   Presuming that AS 1 , AS 2  and AS 3  are connected to network A and transmit routing information using BGP, AS 3  calculates the hop counts of AS 1  and AS 2  when receiving the same route information from AS 1  and AS 2 . This is accomplished so that AS 3  can select an optimum route using the route information of whichever one of AS 1  and AS 2  has the smaller hop count. 
   However, AS 1  and AS 3 , and AS 1  and AS 2 , are interconnected via the same number of routes. AS 3  and AS 1  are interconnected via a first router R 1  and a second router R 2 . AS 3  and AS 2  are interconnected via a third router R 3  and a fourth router R 4 . Therefore, from the viewpoint of AS 3 , AS 1  and AS 2  have the same hop count. 
   In this case, AS 3  establishes an optimum route using whichever one of the route information from AS 1  or the route information from AS 2  is received earlier. For instance, if AS 3  receives the route information from AS 2  after receiving the route information from AS 1 , AS 3  establishes the optimum route using the route information received from AS 1 . However, if the transmission speed of a route from AS 1  to AS 3  (hereinafter, referred to as the first route) is slower than that of a route from AS 2  to AS 3 (hereinafter, referred to as the second route) due to network traffic on the first route, it is an optimal selection for AS 3  to select AS 2  as the next hop. However, AS 3  selects AS 1  as the next hop based on the above-mentioned criteria. In other words, AS 3  selects AS 1  as the next hop because AS 1  transmitted the route information first. 
   As mentioned above, there is a disadvantage in that the conventional routing protocols are unable to properly reflect changes on the network in selecting an optimum routing route. That is, there is a disadvantage in that the conventional routing protocols cause an error in selecting an optimum route because they select the optimum route without reflecting traffic volume on each link on a network. 
   SUMMARY OF THE INVENTION 
   It is an object of the invention to provide a method for selecting a route by reflecting network traffic volume that varies constantly in a routing protocol. 
   It is another object of the invention to provide the capability of selecting an optimum route in a routing protocol. 
   According to an aspect of the present invention, there is provided a method for selecting a route in a routing protocol, comprising the steps of: measuring a message reachable time between a plurality of route information managers which manage route information on a network, and constructing a reachable time table for managing the message reachable time; checking hop counts of different neighboring route information managers at a receiving route information manager which receives the same route information from the different neighboring route information managers; and selecting an optimum route based on the reachable time table when the neighboring route information managers have the same hop count. 
   Preferably, the step of constructing a reachable time table for managing the message reachable time includes the step of measuring a time until a first route information manager receives a response message after transmitting a predetermined message to a second neighboring route information manager so as to construct the reachable time table. 
   Preferably, the reachable time table is constructed by the respective route information managers and contains address information and reachable time of the respective route information managers adjacent to a corresponding route information manager. 
   Preferably, the step of constructing a reachable time table for managing the message reachable time includes the steps of: transmitting, by means of a first route information manager having a reachable time attribute as enabled, a reachable time request message to a second neighboring route information manager; transmitting, by means of the second route information manager, to the first route information manager a reply message in response to the reachable time request message when a reachable time attribute of the second route information manager is enabled; calculating a reachable time until the first route information manager receives a reply message after transmitting the reachable time request message; and updating the reachable time table with the reachable time. 
   Preferably, the step of transmitting, by means of the first route information manager having a reachable time attribute as enabled, a reachable time request message to the second neighboring route information manager includes the step of transmitting a reachable time request message including a time stamp of the first route information manager. 
   Preferably, the step of transmitting, by means of the second route information manager, to the first route information manager a reply message to the reachable time request message includes the step of transmitting a reply message which is the same as the reachable time request message but which has a changed message type. 
   Preferably, each of the reachable time request message and the reply message includes: a type area indicating that a relevant message is a reachable time related message; a sub-type area indicating whether the relevant message is the reachable time request message or the reply message of the reachable time related message; and a time information area storing an initial time for transmitting the reachable time request message. 
   Preferably, the step of transmitting, by means of the first route information manager having a reachable time attribute as enabled, a reachable time request message to a second neighboring route information manager includes the step of periodically transmitting the reachable time request message. 
   Preferably, the step of transmitting, by means of the first route information manager having a reachable time attribute as enabled, a reachable time request message to the second neighboring route information manager includes the step of transmitting the reachable time request message several times, and the step of calculating includes the step of calculating the reachable time as an average value of reachable times of the reply messages generated in response to the respective reachable time request messages. 
   Preferably, the step of transmitting, by means of the first route information manager having a reachable time attribute as enabled, a reachable time request message to a second neighboring route information manager includes the step of transmitting the reachable time request message to the respective neighboring route information managers at predetermined intervals when a plurality of the route information managers are adjacent to the first route information manager. 
   Preferably, the step of updating includes the step of adding the address information and the reachable time of the second route information manager to the reachable time table when there is no reachable time information for the second route information manager in the reachable time table. 
   Preferably, the step of updating includes the step of changing pre-stored reachable information into the calculated reachable time when the reachable time information for the second route information manager already exists in the reachable time table, and the calculated reachable time is greater than the reachable time information stored previously in the reachable time table. 
   Preferably, the step of updating includes the step of changing the previously stored reachable time information when the difference between the previously stored reachable time information and the calculated reachable time exceeds a predetermined threshold. 
   Preferably, the routing protocol is the border gateway protocol (BGP) and the route information manager is an autonomous system. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete appreciation of the invention, and many of the attendant advantages thereof, will be readily apparent as the same becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings, in which like reference symbols indicate the same or similar components, wherein: 
       FIG. 1  is a flowchart of a route selecting method; 
       FIG. 2  shows transmission routes among ASs in a network; 
       FIG. 3  is a flowchart illustrating a method for selecting a route according to an embodiment of the present invention; 
       FIG. 4  illustrates a reachable time table (REACHABLE_TIME table) according to an embodiment of the present invention; 
       FIG. 5  is a flowchart illustrating a management procedure for a reachable time table (REACHABLE_TIME table) according to an embodiment of the present invention; 
       FIG. 6  shows attributes of a typical border gateway protocol (BGP); 
       FIGS. 7A to 7C  illustrate a reachable time attribute (REACHABLE_TIME attribute) according to an embodiment of the present invention; and 
       FIG. 8  illustrates a reachable time message format (REACHABLE_TIME message format) according to an embodiment of the present invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   The present invention will be described with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. In the drawings, whenever the same element reappears in a subsequent drawing, it is denoted by the same reference numeral. Furthermore, in explaining the invention, unnecessary detailed explanation is omitted when its explanation is considered to obscure the subject of the invention. 
     FIG. 1  is a flowchart of a route selecting method. 
   In particular,  FIG. 1  illustrates a method by which an AS transmitting routing information using BGP selects a routing path based on route information received from neighboring ASs. 
   Referring to  FIG. 1 , if one of the ASs (hereinafter, referred to as receiving AS) transmitting the routing information using the BGP receives a plurality of the same route information from different neighboring ASs (hereinafter, referred to as transmitting AS) (S 11 ), the receiving AS determines whether the transmitting ASs have the same hop count (S 13 ). That is, the receiving AS determines whether the different neighboring ASs transmitting the same route information have the same hop count. As a result of that determination, if it is determined that the transmitting ASs have the same hop count, the receiving AS establishes an optimum route using the earliest received route information (S 15 ). Otherwise, the receiving AS establishes the optimum route using route information which is received from the AS having a smaller hop count than the receiving AS (S 17 ). 
   On the other hand, if it is determined in S 11  that the receiving AS does not receive the same route information from a plurality of different neighboring ASs, but receives different route information from different neighboring ASs, the receiving AS establishes the route using the received route information (S 19 ). 
     FIG. 2  illustrates transmission routes among ASs on a network. 
   In the example of  FIG. 2 , presuming that AS 1   200 , AS 2   300  and AS 3   400  are connected to network A  100  and transmit routing information using BGP, AS 3   400  calculates hop counts of AS 1   200  and AS 2   300  when receiving the same routing information from AS 1   200  and AS 2   300 . This is carried out for the purpose of selection, by AS 3   400 , of an optimum route using the route information of whichever one of AS 1   200  and AS 2   300  has the of smaller hop count. 
   However, in the example of  FIG. 2 , AS 1   200  and AS 3   400 , and AS 1   200  and AS 2   300 , are interconnected via the same number of routes. AS 3   400  and AS 1   200  are interconnected via a first router R 1   510  and a second router R 2   520 . AS 3   400  and AS 2   300  are interconnected via a third router R 3   530  and a fourth router R 4   540 . Therefore, from the viewpoint of AS 3   400 , AS 1   200  and AS 2   300  have the same hop count. 
   In this case, AS 3   400  establishes an optimum route using whichever one of the route information from AS 1   200  and the route information from AS 2   300  is received earlier. For instance, if AS 3   400  receives the route information from AS 2   300  after receiving the route information from AS 1   200 , AS 3   400  establishes the optimum route using the route information received from AS 1   200 . However, if the transmission speed of a route from AS 1   200  to AS 3   400  (hereinafter, referred to as the first route) is slower than that of a route from AS 2   300  to AS 3   400  (hereinafter, referred to as the second route) due to network traffic on the first route, it is an optimal selection for AS 3   400  to select AS 2   300  as the next hop. However, AS 3   400  selects AS 1   200  as the next hop based on the above-mentioned criteria. In other words, AS 3   400  selects AS 1   200  as the next hop because AS 1   200  transmitted the route information first. 
     FIG. 3  is a flowchart illustrating a method for selecting a route according to an embodiment of the present invention. In particular,  FIG. 3  illustrates how ASs transmitting routing information using BGP select a routing path based on route information which is received from neighboring ASs. 
   Referring to  FIG. 3 , ASs transmitting routing information the BGP manage a reachable time table for neighboring ASs (S 110 ). For example, an AS manages a table for respective neighboring ASs needed to manage the time (hereinafter, referred to as “reachable time”) until any message (hereinafter, referred to as a “reachable time request message” (‘REACHABLE (REQUEST) message’)) sent to the respective neighboring ASs returns. A method of constructing and managing the reachable time table will be described in detail with reference to  FIGS. 4 and 5 . 
   If one of the ASs managing the reachable time table (hereinafter referred to as “receiving AS”) receives the same route information from different neighboring ASs (hereinafter, referred to as “transmitting ASs”) (S 120 ) as described above, the receiving AS determines whether the transmitting ASs have the same hop count (S 130 ). That is, the receiving AS determines whether different neighboring ASs transmitting the same route information have the same hop count. 
   If it is determined in S 130  that the transmitting ASs have the same hop count, the receiving AS establishes an optimum route based on the reachable time table (S 140 ). For example, the receiving AS checks respective reachable times of the transmitting ASs by referring to the reachable time table, and establishes an optimum route using the route information received from the AS having the shortest reachable time among the transmitting ASs. In other words, the receiving AS establishes the AS having the shortest reachable time as a next hop. If it is determined in S 130  that the transmitting ASs do not have the same hop count, the receiving AS establishes an optimum route using the route information received from the AS having the smaller hop count (S 150 ). That is, the receiving the AS sets AS having the least hop count as the next hop. 
   On the other hand, if it is determined in S 120  that the receiving AS does not receive the same route information from a plurality of different neighboring ASs, but receives different route information from different neighboring ASs, the receiving AS establishes the route using the received route information (S 160 ). 
   In the example of  FIG. 2 , presuming that AS 1   200 , AS 2   300  and AS 3   400  are connected to the network A  100  and transmit routing information using BGP, according to the embodiment of the invention, AS 1   200 , AS 2   300  and AS 3   400  manage the reachable time table for the neighboring ASs. Moreover, when AS 3   400  receives the same route information from AS 1   200  and AS 2   300  which have the same hop count, AS 3   400  designates the AS having the shorter reachable time as the next hop based on the reachable time table. 
   For instance, if AS 3   400  receives the route information from AS 2   300  after receiving the route information from AS 1   200 , and the transmitting speed of the a route from AS 1   200  to AS 3   400  (hereinafter, referred to as the first route) is slower than that of the route from AS 2   300  to AS 3   400  (hereinafter, referred to as the second route) due to network traffic on the first route, AS 3   400  will designate the AS having the shorter reachable time as the next hop based on the reachable time table. In the above example, since the transmitting speed of the route from AS 1   200  to AS 3   400  (i.e., the first route) is slower than that of the route from AS 2   300  to AS 3   400  (i.e., the second route), the AS 2   300  has the shorter reachable time. Therefore, in this case, AS 3   400  will designate AS 2   300  as the next hop. 
     FIG. 4  shows a reachable time table (REACHABLE_TIME table) according to an embodiment of the present invention. Referring to  FIG. 4 , the reachable time table for each AS managing the reachable time of respective neighboring ASs adjacent to the AS includes an area  610  for storing an address family of the neighboring ASs, an area  620  for storing addresses of the neighboring ASs, and an area  630  for storing the reachable time of the ASs. In the example of  FIG. 2 , if AS 1   200  is connected to an IPv4 network and its address and reachable time are ‘16.1.2.2’ and ‘820 ms’, respectively, and if AS 2   300  is connected to an IPv6 network and its address and reachable time are ‘3ffe:0:0:1::2’ and ‘1300 ms’, respectively, the reachable time table stored in the AS 3   400  is as shown in  FIG. 4 . 
   In this case, AS 3   400  will designate AS 1   200 , having the shorter reachable time, as the next hop. 
     FIG. 5  is a flowchart illustrating a management procedure for a reachable time table (REACHABLE_TIME table) according to an embodiment of the present invention. Specifically,  FIG. 5  shows a method of managing a reachable time table through measurement of the reachable time of AS 3   400 , i.e., one of the ASs adjacent to AS 1   200  in a network having the structure shown in  FIG. 2 . 
   Referring to  FIG. 5 , AS 1   200  determines whether its reachable time attribute (REACHABLE_TIME attribute) is available (S 111 ). That is, it is determined whether the reachable time attribute of AS 1   200  is enabled. The process proceeds to the next step only if the reachable time attribute is enabled. For this, it is preferable that AS 1   200  add the reachable time attribute recorded on one of the unused areas in a table defining a typical BGP attribute to indicate whether the attribute is used. This reachable time attribute will be explained in detail with reference to  FIGS. 6 and 7A  to  7 C. 
   If it is determined in S 111  that the reachable time attribute of AS 1   200  is enabled, AS 1   200  generates a reachable time request message (REACHABLE (REQUEST) message) (S 112 ), and transmits it to AS 3   400  (S 113 ) in order to measure the reachable time of AS 3   400 . In S 113 , AS 1   200  transmits the reachable time request message, including a time-stamp value of the AS 1   200 . In other words, AS 1   200  transmits to AS 3   400  a reachable time request message which includes time information about a time when the reachable time request message is transmitted to AS 3   400 . The structure of the reachable time request message generated in S 112  will be explained in detail with reference to  FIG. 8 . 
   Then, AS 3   400  determines whether its reachable time attribute (REACHABLE_TIME attribute) is enabled and available (S 114 ), and then generates a reply message to the reachable time request message (S 115 ) and transmits it to AS 1   200  (S 116 ) only if the reachable time attribute is enabled and available. That is, if the reachable time attribute of AS 3   400  is enabled, AS 3   400  changes only the type of the received reachable time request message to generate a reply message (RECHARGEABLE (REPLY) message), and then transmits the reply message to AS 1   200 . In particular, at this time, AS 3   400  does not add its time stamp value to the reply message. In other words, AS 3   400  transmits the reply message to AS 1   200  without changing the time information contained in the reachable time request message. 
   In response to receiving the reply message, AS 1   200  compares the time information included in the reply message and current time information to calculate a round trip time (S 117 ). For example, AS 1   200  calculates the time that it took to receive a response message after transmitting the reachable time request message to the AS 3   400 . 
   AS 1   200  then updates the pre-stored reachable time table with the calculation result (S 118 ). If there is no pre-stored reachable time information of AS 3   400  in the reachable time table, AS 1   200  additionally registers the IP address and the reachable time of AS 3   400  in the reachable time table. If there is pre-stored reachable time information of AS 3   400  in the reachable time table but the time information has a greater value than that calculated in S 117 , AS 1   200  changes the pre-stored reachable time information to the new value calculated in S 117 . 
   Preferably, in order to measure a fairer reachable time in S 117 , AS 1   200  transmits the reachable time request message several times, receives respective reply messages, and calculates an average value of the respective reachable times to update the reachable time table with the average value. 
   Furthermore, it is preferable that an appropriate threshold (e.g. 500 ms) be used in order to prevent the table from being unnecessarily changed in a next hop due to a minor difference between the reachable times. 
   Although the example of  FIG. 5  shows that AS 1   200  transmits the reachable time request message to AS 3   400  and receives a reply message therefrom, AS 1   200  actually transmits the messages to all neighboring ASs, and receives respective reply messages from the neighboring ASs. AS 1   200  then updates the reachable time table stored in AS 1   200  using the results. 
   Furthermore, it is preferable that the process shown in  FIG. 5  be performed periodically (e.g., every 60 secs.) while the relevant AS is activated. In other words, AS 1   200  updates the reachable time of all neighboring ASs periodically. For instance, AS 1   200  periodically updates the reachable time of all neighboring ASs according to the procedures shown in  FIG. 5 . 
   At this time, in order to prevent overload of the network which may be caused by simultaneous transmission of the messages to all neighboring ASs, it is preferable that AS 1   200  transmit the messages to the respective neighboring ASs at intervals. Also, it is preferable that the message transmission period be changeable by a manager. 
     FIG. 6  shows attributes of typical border gateway protocol (BGP). Referring to  FIG. 6 , in a typical border gateway protocol (BGP), twenty attributes numbered from 1 to 20 are defined, while attributes from 21 to 254 are not defined. Thus, the reachable time attribute according to the embodiment of the present invention is to be defined as any one value of 21 and 252. 
     FIGS. 7A to 7C  illustrate a reachable time attribute (REACHABLE_TIME attribute) according to an embodiment of the present invention. 
     FIG. 7A  illustrates a typical format of a BGP attribute according to one embodiment of the present invention. Referring to  FIG. 7A , the reachable time attribute  700  includes a flag area (Attr. Flags)  710  and a type code area (Attr. Type Code)  720 . A value to indicate whether the reachable time attribute is enabled is stored in the flag area  710  and a reachable time attribute value is stored in the type code area  720 . 
     FIGS. 7B and 7C  show examples of cases where the reachable time attribute is enabled and not enabled, in which the number  21  is defined as the reachable time attribute. 
   Referring to  FIG. 7B , when the reachable time attribute  700   a  is enabled, ‘1’ is stored in the flag area  710   a  and a value (e.g. ‘21’), indicating that a relevant attribute is the reachable time attribute, is stored in the type code area  720   a . Referring to  7 C, when the reachable time attribute  700   b  is not disabled, ‘0’ is stored in the flag area  710   b  and the value, indicating that a relevant attribute is the reachable time attribute (e.g. ‘21’), is stored in the time code area  720   b.    
     FIG. 8  illustrates a reachable time message format (REACHABLE_TIME message format) according to an embodiment of the present invention. In other words,  FIG. 8  shows an example of the structure of a reachable time request message (REACHABLE (REQUEST) message) and a reply message (REACHABLE (REPLY) message). Referring to  FIG. 8 , the format of the reachable time message  800  according to one embodiment of the present invention includes a marker area  810 , a length area  820 , a type area  830 , a sub-type area  840 , and a time stamp area  850 . For instance, the reachable time message may be organized by adding the areas as shown in  FIG. 8  to a BGP message header area. 
   In  FIG. 8 , if the type area  830  is ‘REACHABLE,’ it indicates that a relevant message is a reachable time message. If the type area  830  is ‘REACHABLE’ and the sub-type area  840  is ‘REQUEST’, this indicates that the relevant message is a reachable time request message. If the type area  830  is ‘REACHABLE’ and the sub-type area  840  is ‘REPLY,’ that indicates that the relevant message is a reply message. 
   While the present invention has been described with reference to exemplary embodiments thereof, it should be understood that various changes in form and detail may be made therein without departing from the spirit and scope of the present invention. Although the case of BGP is illustrated by way of example only in the detailed explanation of the invention, the invention is not limited to BGP. In other words, the invention relates to every routing protocol. Therefore, the scope of the invention should be not limited to the embodiments described above, should be defined as set forth in the following claims.