Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Alternate path routing
Reexamination Certificate
1999-10-12
2003-05-06
Vu, Viet D. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Alternate path routing
C709S235000, C709S242000, C370S238000
Reexamination Certificate
active
06560654
ABSTRACT:
FIELD OF THE INVENTION
The invention generally relates to computer networks and, more particularly, the invention relates to an apparatus and method for managing message traffic in a link state routing network.
BACKGROUND OF THE INVENTION
Multi-protocol label switching (“MPLS”) is a path oriented routing protocol that integrates layer two data link layer (e.g., bandwidth, latency, and utilization) into ISO layer three network layer to simplify and improve packet exchange. More particularly, the data link layer manages packet transportation, while the network layer determines the destination of packets. MPLS achieves these objectives by setting the layer two forwarding tables to meet the layer three requirements.
Layer three networking with MPLS can utilize several families of routing protocols to automatically distribute routing information. One such family of routing protocols, known in the art as “link state routing protocols”, offers a number of advantages. Among those advantages is rapid convergence time when the network changes, and the distribution of complete network information within a given routing domain. Accordingly, MPLS can be implemented across a link state routing network.
Network information (i.e., link information) in a link state network is distributed to active nodes in a given routing domain by a reliable flood of link state advertisements (“LSAs”). LSAs may be broadcasted to active nodes each time a bandwidth allocation changes across a link, or each time a link malfunctions (i.e., a link “goes down”). In addition, LSAs also may be broadcasted once every preselected time interval, such as once every thirty minutes.
There are instances, however, when LSAs unnecessarily reduce network bandwidth. Specifically, the group of network devices receiving a broadcast of an LSA often includes network devices that are not within a given path requiring the data in the LSA, and network devices that do not execute the MPLS protocol. Use of a broadcast therefore can unnecessarily utilize bandwidth by synchronously and/or asynchronously broadcasting LSAs to network devices that do not utilize such advertisements. Stated another way, many devices that do not require use of LSAs nevertheless receive LSAs. Moreover, use of flooding to transport network information can ultimately limit the size of a network, and often does not provide a timely update of topology information.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, an apparatus and method of forwarding a first message from a source to a destination via a link state routing network utilizes point-to-point feedback messages when the quality of a first path from the source to the destination meets some prescribed condition. Accordingly, reliance upon LSAs is reduced. To that end, the first path is initialized within the link state routing network. A feedback message having data relating to a quality of the first path then is received as a point-to-point message that is forwarded to the source. In response to receipt of the feedback message, a second path is initialized from the source to the destination. The first message then is forwarded to the destination via the second path.
It should be noted that although first and second paths are discussed, such paths are not necessarily the first and second paths that are initialized. Prior paths may have been unsuccessfully initialized.
In preferred embodiments, the feedback message includes failure data indicating that the bandwidth along the first path is below a preselected amount. Moreover, the quality of the first path may include data relating to various aspects of the path, such as available bandwidth or quality of service of the first path. The first path may include a plurality of nodes that forward the feedback message to no network devices other than the source, or other network devices that are configured to forward the feedback message toward the source. The source may include a database that is updated in response to receipt of the feedback message. The database thus may be out of synchronization with the other nodes once it is updated. In many embodiments, the first message may comprise s stream of path oriented packets.
In some embodiments, the link state routing network produces broadcast advertisements (i.e., in contrast to the non-broadcast, point-to-point feedback message). Accordingly, when a broadcast advertisement is received by the source, it overwrites the stored data in the local data storage (i.e., from the feedback message, if any) with advertisement data in the broadcast advertisement. As a result of this overwriting process, the source is synchronized with the other nodes in the network. The first path may be initialized in a conventional manner, such as by forwarding label information to a plurality of nodes that are to forward the first message from the source to the destination. The first message preferably is forwarded from the source across data networks that may be either or both connectionless oriented and connection oriented networks. In preferred embodiments, the network implements MPLS.
In accordance with another aspect of the invention, an apparatus and method of forwarding a first message from a source to a destination via a link state routing network similarly uses point-to-point feedback messages. The link state routing network utilizes broadcast advertisements to notify network devices of bandwidth allocation in the link state network. The apparatus and method thus initialize a first path from the destination to the source, and set a minimum bandwidth for the first message to be forwarded through the first path. The source then receives a feedback message having data indicating that the first path has a bandwidth that is below the minimum bandwidth. As noted above, the feedback message is a point-to-point message forwarded toward the source. In response to receipt of the feedback message, a second path from the source to the destination is initialized, and the first message is forwarded to the destination via the second path.
Preferred embodiments of the invention are implemented in hardware, or as a computer program product having a computer usable medium with computer readable program code thereon. The computer readable code may be read and utilized by the computer system in accordance with conventional processes.
REFERENCES:
patent: 5463620 (1995-10-01), Sriram
patent: 5675577 (1997-10-01), Komatsu
patent: 5933422 (1999-08-01), Kusano et al.
patent: 6084858 (2000-07-01), Matthews et al.
patent: 6256309 (2001-07-01), Daley et al.
patent: 6363319 (2002-03-01), Hsu
Rosen et al., “Multiprotocol Label Switching Architecture,” Network Working Group, IETF Internet Draft, pp. 1-62, Aug. 1999.
Unknown, “PNNI Routing Description,” ATM Forum Technical Committee, pp. 15-17, 40-45, 203-206, 240, and 246-247, Mar. 1996.
Spiegel et al., “An Alternate Path Routing Scheme Supporting QOS and Fast Connection Setup in ATM Networks,” Proceedings of the Global Telecommunication Conference (Globecom), IEEE, pp. 1224-1230, 1994.
Ashwood-Smith Peter
Dysart Keith
Fedyk Donald
Miernik Jerzy
Nortel Networks Limited
Steubing McGuinness & Manaras LLP
Vu Viet D.
LandOfFree
Apparatus and method of maintaining timely topology data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method of maintaining timely topology data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method of maintaining timely topology data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3005661