Title of Invention	A METHOD FOR SELECTING INTERNET ROUTING PATHS
Abstract	Network convergence is greatly reduced because new routing paths are only selected when they are substantially better than pre existing, best available paths.

Full Text

Attorney Docket No.: 29250-002020/US Lwent Case Name: 126273/NETRAVALI82-61-3 METHODS AND DEVICES FOR SELECTING INTERNET ROUT] NG PATHS BACKGROUND >F THE INVENTION [OOOl] Devices known as ro iters are responsible for selecting the best path or paths to route information from one location or node within the Internet to another. f or example, when information needs to be sent from a node within on network to a node within a different network, a router using a Borde: Gateway Protocol ("BGP") (hereafter "BGP router") is assigned the tisk of determining the best path or paths. [0002] Because new nodes are constantly being added, deleted, etc. from networks making up the Internet, at any given point in time the best path from one node to another may change very rapidly. Realizing this, existing techniqu es provide BGP routers (sometimes called BGP speaker nodes) with the capability of comparing a pre existing, best available path will a next available path formed when a change occurs to a given network. If the next available path is determined to be better than the pre-existing, best available path, then the next available path will be given the status of "best available path". Thereafter, this new path will be used to route information in place of the pre-existing path (i.e , old, best available path). [0003] When a new path is selected a BGP router is responsible for generating a forwarding tat i e(s) associated with this new path. Once generated, the forwarding able is stored within the BGP router. When a packet arrives at the B( P router it is forwarded on using the stored forwarding table. [0004] A BGP router is constantly comparing its pre-existing, stored best available path to next available paths. If a next available path is even slightly better that. a pre-existing, best available path, then existing techniques requir e a BGP router to replace the pre existing best available path with. the new path. Thus, a given BGP router may be constantly updating its forwarding tables. Attorney Docket No.: 29250-002020/US Lu mt Case Name: 126273/NETRAVALI82-61-3 Complicating matters further, each oh time a new, best available path is determined, it must be transmi tted (referred to as "advertised") to neighboring nodes (e.g., neighboring BGP routers). Upon receiving a new, best available path, the neighboring nodes will also update their forwarding tables. Thereafter, th iese neighboring nodes will advertise to their neighboring nodes and s o on. Thus, any change by one BGP router has a cascading effect upon other BGP routers. [0005] Inherent in this com parison, selection, advertisement and updating process is a time requi rement. That is, relatively speaking, the comparison, selection, adver ising and updating process takes up a significant amount of time. D iring this time it may not be possible to forward a received packet on a next node until the process has been completed. For example, e /en though the comparison, selection and updating and advertising i rocess has been completed at some nodes along a path, this process may not be completed at other nodes. As a result, any attempt to forv ard a packet along the path may be unsuccessful (i.e., the packet wi ll not reach its destination) until each of the nodes along the path have completed their comparison, selection, updating and advertisi ig process. [0006] Other times a phenomena called "looping" occurs which results in a packet being sent back toward a preceding node instead of being forwarded on to a subsequ :nt node. [0007] Only when each node in the network has completed its comparison, selection and up lating (and associated advertising) process can it be assured t tat a packet can successfully be transferred over any given pat h. When each node finishes this process, a network is said to have "converged." This may take, relatively speaking, a substanial amount of time. The faster a network converges, the faster a p acket can be transferred. [0008] It is, therefore, desi arable to provide for methods and devices which reduce the amount of time it takes a network to converge. Attorney Docket No.: 29250-002020/US Lu mt Case Name: 126273/NETRAVALI82-61-3 SUMMARY Q] THE INVENTION [0009] We have recognized hat the time it takes for a network to converge can be significantly re luced by reducing delays associated with computing routing paths. In one embodiment of the present invention, a detected next availal le path will only be selected as a best available path if it is substantiE lly better than the pre-existing, best available path. [0010] Because some deteced, next available paths will not be substantially better than pre-ex sting, best available paths, some of the detected paths will not be se lected. When a path is not selected, there is no need for a BGP ro iter to update its forwarding table. There is also no need to advertise the unselected path to its neighbors. It is believed by the present inve] itors that this may greatly reduce the number of times a BGP router i eeds to update its forwarding tables and reduce cascading, thereby re ducing the time it takes a network to converge. BRIEF DESCRIPTION OF THE DRAWINGS [0011] FIG. 1 depicts nods, such as BGP routers, that are operable to compute Internet rou I ing paths according to embodiments of the present invention. DETAILED DESCRIPTION OF THE INVENTION [0012] Referring now to fig. 1, there is shown a number of routers A, B, C, D, E and F. The ;e routers may be BGP routers. Each of the BGP routers A-F stores fcrwarding tables, where each table is associated with a best available routing path. For example, suppose at some earlier point in time, B( P router B has compared the routes which lead to BGP router D a nd has selected route i as the best available path to BGP router D Thereafter, BGP router B may be operable to store a forwarding table associated with route i in order to route incoming packets to BGP router D. Attorney Docket No.: 29250-002020/US Lu znt Case Name: 126273/NETRAVALI82-61-3 [0013] Suppose further that in the next instant of time a next available path is detected, a one embodiment of the present invention, BGP router B is operable to compare the next available path to the pre-existing, best available path I If this comparison results in a determination tl at the next available path is substantially better (e.g., co it-wise, length-wise, time-wise or otherwise comparatively better) lhan the pre-existing, best available path then the BGP router B is further operable to select the next available path as the new, best available path. However, if the results of the comparison deterr tine that the next available path is not substantially better than th.: pre-existing, best available path i, then the BGP router B is operble to maintain the pre-existing, best available path i as the best available path. [0014] Such comparisons 1 way take the form of comparing the length or cost of a next available path with the length or cost of a pre existing best available path and only selecting the next available path if its length/cost is substantiall shorter/less than that of the pre existing, best available path. Alternatively, one or more known metrics or weights may be assigned to the pre-existing, best available path and the detected next ava idlable path. Upon comparing the metrics or weights, the next avai lable path will be selected only if the metric or weight is substantial y better than the metric or weight associated with the pre-existing, best available path. In yet a further embodiment of the invention, the metric or weight associated with the next available path maybe compa red to a threshold or the like. Only if the metric or weight equals or ex :eeds the threshold (which acts as an indicator that the next available path is substantially better than the pre-existing best available path) is the next available path selected. It should be understood that a metric or weight may be associated with a length, cost, transmission chan nel quality, error rate, etc... It should be understood that these are just some of the metrics and weights which may be used to determine whether the detected next available path is substantially better than pre-existing, best available path. Attorney Docket No.: 29250-002020/US Liu mt Case Name: 126273/NETRAVALI82-61-3 [0015] For example, the ne -1 available path may be associated with a higher cost because it 1 raverses a network operated by an entity which is not affiliated with the entity which operates a given BGP router. In contrast, the cost associated with the pre-existing, best available path may be lowe r than the cost associated with the detected next available path bee muse the pre-existing, best available path traverses a network that is operated by an affiliate of the BGP router. [0016] By requiring that a next available path be substantially better than a pre-existing, best available path, the present invention allows BGP routers to generate new forwarding tables only when the next available path is substantially better than the pre-existing, best available path. Because many t mes the next available path will not be substantially better than the pre-existing, best available path, the present invention effectively reduces the number of times a given BGP router will have to generate new forwarding tables. [0017] In addition, because it is only necessary for a BGP router to advertise or transmit new, b :st available paths to its neighbors, these advertisements or transmis sions need only occur when the next available path is substantially better than the pre-existing, best available path. In the example above, though a next available path i" has been detected, it may not be substantially better than path In a further embodiment of the present invention, BGP router B would not select the next available path i" because it is not substantially better than the pre-existing best availalblle path I As a result, BGP router B would not need to update its fo warding table, nor would it need to advertise a new path to its neighboring nodes. As a result, neighboring routers A, C, E am I F would not have to change their routing paths and associated for yarding tables either. Conversely, if BGP router B determines that i is substantially better than path i, BGP routers A, C, E and F may ] tave to change their pre-existing best available path to next available path i" (assuming they also know of no Attorney Docket No.: 29250-002020/US Lm entCaseName: 126273/NETRAVALI82-61-3 other path that is substantially better than i or u) as well as their forwarding tables. Thereafter, they would also have to advertise this new path to their surrounding BGP routers (not shown in FIG. 1). [0018] To avoid such a cascading effect when a next available path is only slightly better than a pre-existing, best available path, it will not be selected or used to rouate packets. Delays associated with changing forwarding tables and c ascading effects are reduced, thereby reducing the time it takes a network to converge. Fast converging networks make it possible to forward received packets faster than previously thought possible. [0019] Backtracking some\ hat, it was mentioned above that metrics or weights maybe assigr ed to pre-existing and next available paths. It should be understood that these metrics and weights may be assigned, modified or configured (collectively "configured") by a user, network operator or the like (collectively "user") at a BGP router (i.e., they are variable, not fixed). [0020] In yet additional em bodiments of the present invention, the problems associated with so called "looping" are prevented by the present invention. When BG p router B initially selects a next available path as a new, best ava liable path, it determines whether the next available path will result ina packet being transmitted back (i.e., looped back) to BGP router B or any other router along the next available path. If it determines that this may occur, then this path is rejected and not selected as a new best available path. [0021] In addition, the present invention also allows for another comparison to ensure that the next available path f, for example, is in fact the best path of all known paths. For example, though f may be substantially better than i, at the same time the next available path f becomes available, changes may occur to another path, for example, path Jc. To ensure that the n.ext available path, f, is not only substantially better than the pre existing, best available path i, but is also the best path of all known p aths (where it is assumed that path k Attorney Docket No.: 29250-002020/US La ent Case Name: 126273/NETRAVALI82-61-3 is previously known to BGP rou ;.er B), the next available path f will only be selected provided it is ir deed the best path among all known paths, in this case the best path among paths i, i" and k. This proviso holds true for each BGP router shown in FIG. 1. [0022] In a further embodi rnent of the present invention, once BGP router B selects a new best available path (e.g., t") and advertises this new path to its surrounding neighbors, it should be understood that the pre-existing best available path i can no longer be used by BGP router A, etc... Said another way, BGP router A may be further operable to determine whether the pre-existing, best available path t traverses a neighboring node (e.£ ., BGP router B) which has advertised a next available path (e.g., f). I this is the case, then the BGP router A is further operable to select the next available path f (provided, of course, this next available path, has been determined to be the best path along all known paths, i and k.) [0023] In yet a further er ibodiment of the present invention, each BGP router of the present invention may assign a different metric or weight to each best available path. Because of this, when each BGP router carries out its own comparison process, each BGP router may generate a different compari son result. [0024] The discussion above has set forth some of the examples of the present invention. The true scope of the present invention, however, is set forth in the claim . which follow. We claim: 1. A method for selecting Internet routing paths comprising: comparing a next available path for routing a packet to a pre existing path; and selecting either the next available path or the pre-existing path as a best available path based ca whether the next available path is substantially better than the pre- existing path. 2. The method as in claim 1 further comprising selecting the next available path as the best available path when the next available path is substantially better than lie pre-existing path. 3. The method as in claim 1 further comprising selecting the pre-existing path as the best available path when the next available path is not substantially better then the pre-existing path. 4. The method as in claim 1 further comprising: determining whether the pre-existing path traverses a neighboring node which has adve rtised the next available path; and selecting the next availab e path provided the next available path is the best path among all known paths when it is determined that the pre-existing path trav irses a neighboring node that has advertised the next available patl 5. The method as in cla m 1 further comprising advertising a new path only when the next available path is selected as the best available path. 6. The method as in claim 1 wherein the next available path is determined to be substantially better than the pre-existing path by comparing a metric associated with the next available path to a threshold, the metric being selected from a group consisting of at least cost, length, channel quality and error rate. 7. A device for selecting Internet routing paths operable to: compare a next available oath for routing a packet to a pre existing path; and select either the next available path or the pre-existing path as a best available path based on whether the next available path is substantially better than the pre- existing path. 8. The device as in claim 7 further operable to: determine whether the pre existing path traverses a neighboring node which has advertised the next available path; and select the next available path provided the next available path is the best path among all known paths when it is determined that the pre-existing path traverses a neighboring node that has advertised the next available path. 9. The device as in clai m 7 wherein the device comprises a Border Gateway Protocol (BGP) ro uter. 10. The device as in cla im 7 further operable to advertise a new path only when the next available path is selected as the best available path.

Documents:

1384-CHE-2005 AMENDED CLAIMS 13-05-2014.pdf

1384-CHE-2005 AMENDED PAGES OF SPECIFICATION 13-05-2014.pdf

1384-CHE-2005 AMENDED PAGES OF SPECIFICATION 23-10-2013.pdf

1384-CHE-2005 AMENDED CLAIMS 23-10-2013.pdf

1384-CHE-2005 CORRESPONDENCE OTHERS 24-06-2013.pdf

1384-CHE-2005 EXAMINATION REPORT REPLY RECEIVED 13-05-2014.pdf

1384-CHE-2005 EXAMINATION REPORT REPLY RECEIVED 23-10-2013.pdf

1384-CHE-2005 FORM-1 13-05-2014.pdf

1384-CHE-2005 FORM-3 23-10-2013.pdf

1384-CHE-2005 FORM-3 24-06-2013.pdf

1384-CHE-2005 OTHER PATENT DOCUMENT 23-10-2013.pdf

1384-CHE-2005 POWER OF ATTORNEY 23-10-2013.pdf

1384-CHE-2005 CORRESPONDENCE OTHERS 02-07-2013.pdf

1384-che-2005-abstract.pdf

1384-che-2005-assignement.pdf

1384-che-2005-claims.pdf

1384-che-2005-correspondnece-others.pdf

1384-che-2005-description(complete).pdf

1384-che-2005-drawings.pdf

1384-che-2005-form 1.pdf

1384-che-2005-form 26.pdf

1384-che-2005-form 3.pdf

1384-che-2005-form 5.pdf