The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Oct. 12, 2004
Filed:
Feb. 04, 2003
Timothy Gene Kelly, Shawnee, KS (US);
Nina Anne Taft, San Francisco, CA (US);
William Lee Edwards, Carbondale, CO (US);
Richard G. Ogier, Sunnyvale, CA (US);
Bhargav Bellur, Fremeont, CA (US);
Sprint Communications Company, L.P., Overland Park, KS (US);
Abstract
Methods for determining at least two pre-computed paths to a destination in a communications network are provided. The two paths are maximally disjoint. Maximally disjoint paths are paths where the number of links or nodes common to the two paths is minimized. This minimization is given a priority over other path considerations, such as bandwidth or cost metrics. By pre-computing a maximally disjoint pair of paths, the probability that an inoperable link or node is in both paths is minimized. The probability that the inoperable link or node blocks a transfer of data is minimized. Additionally, a pair of maximally disjoint paths is determined even if absolutely disjoint paths are not possible. The communications network may include at least four nodes, and maximally disjoint pairs of paths are pre-computed from each node to each other node. A third path from each node to each other node may also be computed as a function of bandwidth or a cost metric. Therefore, the advantages of the maximally disjoint pair of paths are provided as discussed above and a path associated with a higher bandwidth or lower cost is provided to more likely satisfy the user requirements of a data transfer.