Source: http://www.google.com/patents/US7969890?dq=U.S.+Patent+No.+4,528,643)
Timestamp: 2017-06-24 04:56:28
Document Index: 221470963

Matched Legal Cases: ['application No. 04789215', 'application No. 04789216', 'application No. 04789383', 'Application No. 04789213', 'Application No. 04789215', 'Application No. 04789383', 'application No. 04789213', 'application No. 04789383', 'application No. 04789215']

Patent US7969890 - Methods, systems, and computer program products for load balanced and ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThe subject matter described herein includes methods, systems, and computer program products for load balanced and symmetric SPF path computations for VoIP traffic engineering. One method includes advertising an output interface cost in a first direction over a first network segment between a source...http://www.google.com/patents/US7969890?utm_source=gb-gplus-sharePatent US7969890 - Methods, systems, and computer program products for load balanced and symmetric path computations for VoIP traffic engineeringAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7969890 B2Publication typeGrantApplication numberUS 12/775,442Publication dateJun 28, 2011Filing dateMay 6, 2010Priority dateOct 1, 2003Fee statusPaidAlso published asUS7715403, US20070064613, US20100214927Publication number12775442, 775442, US 7969890 B2, US 7969890B2, US-B2-7969890, US7969890 B2, US7969890B2InventorsEdward Y. Qian, San-Qi Li, David Z. Lu, Rupert Zhu, Yen SheiOriginal AssigneeGenband Us LlcExport CitationBiBTeX, EndNote, RefManPatent Citations (52), Non-Patent Citations (40), Classifications (8), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetMethods, systems, and computer program products for load balanced and symmetric path computations for VoIP traffic engineering
US 7969890 B2Abstract
1. A system for obtaining a symmetric shortest-path-first (SPF) path selection from a source IP device to a destination IP device through a network, the system comprising:
a source IP device comprising:
(a) a cost table for storing output interface costs for reaching the destination IP device from the source IP device, wherein the cost table is configured to store an output interface cost advertised in a first direction over a first network segment between the source IP device and the destination IP device and an output interface cost advertised in a second direction over the first network segment that is different from the output interface cost advertised in the first direction over the network segment;
(b) a router instance embodied in a memory for identifying a plurality of paths between the source IP device and the destination IP device, for calculating a cost of each path, for ranking the paths based on the calculated costs, and for assigning outbound packets of a media session to a lowest cost path; and
(c) wherein calculating a cost for each path includes, for paths that include the first network segment, substituting the output interface cost advertised in the first direction over the first network segment with the output interface cost advertised in the second direction over the first network segment.
2. The system of claim 1 wherein the router instance is configured to use an Open Shortest Path First (OSPF) protocol for calculating the path costs.
3. The system of claim 2 wherein the output interface cost advertised in the first direction is assigned for traffic engineering purposes.
4. The system of claim 1 wherein the source IP device includes at least one router instance and at least one associated network interface.
5. The system of claim 4 wherein the source IP device includes a single router instance that manages traffic flows over a plurality of network interfaces.
6. The system of claim 4 wherein the source IP device includes a single router instance that manages traffic flows over a single network interface.
7. The system of claim 1 wherein the output interface cost advertised in the first direction over the first network segment is at least one order of magnitude greater than the output interface cost advertised in the second direction over the first network segment.
8. The system of claim 1 wherein the output interface cost advertised in the first direction over the first network segment is at least one order of magnitude less than the output interface cost advertised in the second direction over the first network segment.
9. The system of claim 1 wherein the source IP device comprises a media gateway.
10. The system of claim 9 wherein the output interface cost advertised in the first direction over the first network segment comprises a cost for reaching a voice over IP host in the source media gateway and wherein the output interface cost advertised in the second direction over the first network segment comprises a cost for reach a voice over IP host in a destination media gateway. Description
This application is a divisional of U.S. patent application Ser. No. 11/594,568, filed Nov. 8, 2006 (now U.S. Pat. No. 7,715,403), which claims the benefit of U.S. Provisional Patent Application Ser. No. 60/788,800, filed Apr. 3, 2006, and which is a continuation-in-part of U.S. patent application Ser. No. 10/943,513, filed Sep. 17, 2004 (pending), which is a continuation-in-part of U.S. patent application Ser. No. 10/676,233, filed Oct. 1, 2003 (now U.S. Pat. No. 7,424,025), and which claims the benefit of U.S. Provisional Patent Application Ser. No. 60/526,126 filed Dec. 1, 2003 and U.S. Provisional Patent Application Ser. No. 60/551,814 filed Mar. 10, 2004.
As used herein, the term “IP device” refers to any system that has at least one interface to a network, supports conventional network routing protocols, and accepts traffic in conventional formats. An IP device may be a conventional router or it may be an endpoint, such as a media gateway or a server. The term “source IP device” refers to an IP device serving as the origin of traffic to be carried across the network. The term “destination IP device” refers to an IP device serving as the destination or termination point in the network for the traffic. The term “node” refers to any system in the network that is capable of routing traffic and supporting SPF cost assignments and calculations. The term “segment” refers to a physical connection between adjacent network nodes. The term “path” refers to a defined set of segments and nodes that provide a connection across a network between an IP device sourcing traffic and an IP device sinking or terminating traffic. The term “forward cost” refers to a cost advertised by an IP device. The term “reverse cost” refers to a cost advertised to the IP device.
In FIG. 2A, MG1 202 may include two VoIP host functions H1 252 and H2 254, two router instances SPF 1 256 and SPF 2 258 and two network interfaces NI 1 260 and NI 2 262. In addition, media gateway 202 may include a cost table 264 and a path list 266 that are maintained by router instance 256 and 258. VoIP host functions H1 250 and H2 252 may each include a voice over IP transcoder circuit or any similar circuit that serves as a source or termination of application level voice, interactive video, or similar application with requirements on network path delay and routing topologies. Router instances 254 and 256 may each contain resources to implement the subject matter described herein. NI1 260 may terminate a plurality of network segments including segment 220 to network router RT1 206 and segment 222 to network router RT2 208. Similarly, NI 2 260 may terminate a plurality of network segments including segment 224 to network router RT1 206 and segment 226 to network router RT2 208. MG1 202 may be a conventional IP device or a network aware media gateway.
FIG. 2B also illustrates a network segment cost table corresponding to the network of FIG. 2A. The network segment cost table illustrates the costs advertised in various directions over the network segments illustrated in FIG. 2A. The network segment cost table may be distributed and stored as cost tables 264, 266, and 274 at media gateways 202 and 204. Network segment cost information may be exchanged by any suitable means, such as the distribution of link state assignment messages. The data in the network segment cost table CaO be used to establish symmetric paths between a source and a destination node, as will be described in detail below.
In FIG. 3, MG1 302 may two VoIP host modules H1 360 and H2 362 and two SPF routing instances SPF 1 364 and SPF 2 366. Router instance 364 may be associated with a plurality of network interfaces including NI 1A 368 and NI 1B 370. SPF 2 366 may be associated with a plurality of network interfaces including NI 2A 372 and NI 2B 374. Media gateway 302 may also include cost tables 264 and path lists 266 maintained by routing instances 364 and 366. VoIP host functions H1 360 and H2 362 may each include a transcoder circuit or any similar circuit that serves as a source or termination of application level voice, interactive video, or similar application with requirements on network path delay and routing topologies. Router instances 364 and 366 may each contain resources to implement the subject matter described herein. Interface NI 1A 368 may terminate a plurality of network segments including segment 320 to network router RT1 306 and segment 322 to network router RT2 308, while NI 1B 370 may terminate a plurality of network segments including segment 324 to network router RT1 306 and segment 328 to network router RT2 308. Interface NI 2A 372 may terminate a plurality of network segments including segment 328 to network router RT1 306 and segment 330 to network router RT2 308, while NI 2B 374 may terminate a plurality of network segments including segment 332 to network router RT1 306 and segment 334 to network router RT2 308.
In one example, router instance 256 may calculate the aggregate path cost from H1 in MG1 202 to Hd 268 in MG2 204 for each of the network path topologies defined above. Router instance 256 may substitute costs advertised by next hop routers 206 and 208 for reaching host Hd 268 with asymmetric costs for reaching host H1 252 advertised over the same segments. For example, the cost associated with reaching host H1 252 via interface N1 of 1000 may be substituted with the cost of 1 for reaching host Hd 268 via router 206. If this substitution is performed, the following cost calculations may be performed for reaching host Hd 268 from host H1 252 via interface NI 1 260.
Cost (a): 1+1+1+10=13
Cost (b): 1+10+10+10=31
Cost (c): 1+10+1+10=22
Cost (d): 1000+10+10+10=1030
Cost (e): 1000+10+1+10=1021
Cost (f): 1000+10+10+10=1030
a) NI 2 262::RT1 206::RT3 210::RT6 216::NI d 268 b) NI 2 262::RT1 206::RT4 212::RT6 216::NI d 268 c) NI 2 262::RT1 206::RT4 212::RT7 218::NI d 268 d) NI 2 262::RT2 208::RT4 212::RT6 216::NI d 268 e) NI 2 262::RT2 208::RT4 212::RT7 218::NI d 268 f) NI 2 262::RT2 208::RT5 214::RT7 218::NI d 268 The cost models associated with each of these network path definitions may then be defined as follows:
Cost (a): 500+1+1+10=1012
Cost (b): 500+10+10+10=1012
Cost (c): 500+10+1+10=1021
Cost (d): 500+10+10+10=530
Cost (e): 500+10+1+10=521
Cost (f): 500+10+10+10=530
Cost (a): 1000+1+1+10=1012
Cost (b): 1000+10+10+10=1030
Cost (c): 1000+10+1+10=1021
Cost (d): 1+10+10+10=31
Cost (e): 1+10+1+10=22
Cost (f): 1+10+10+10=31
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6049524 *Nov 19, 1998Apr 11, 2000Hitachi, Ltd.Multiplex router device comprising a function for controlling a traffic occurrence at the time of alteration process of a plurality of router calculation unitsUS6061348Dec 22, 1995May 9, 2000Cisco Technology, Inc.Method and apparatus for dynamically allocating bandwidth for a time division multiplexed data busUS6363065Nov 10, 1999Mar 26, 2002Quintum Technologies, Inc.okApparatus for a voice over IP (voIP) telephony gateway and methods for use thereinUS6426944Dec 30, 1998Jul 30, 2002At&T CorpMethod and apparatus for controlling data messages across a fast packet networkUS6633563Mar 2, 1999Oct 14, 2003Nortel Networks LimitedAssigning cell data to one of several processors provided in a data switchUS6674744Sep 22, 1998Jan 6, 2004Lucent Technologies Inc.Point-to-point data transport over the internet utilizing label switching without IP headersUS6714535Nov 8, 1999Mar 30, 2004Broadmedia, Inc.Method and system for unlimited use of telephony services over a data network without incurring long distance calling tollsUS6771673Aug 31, 2000Aug 3, 2004Verizon Communications Inc.Methods and apparatus and data structures for providing access to an edge router of a networkUS6831895 *May 19, 1999Dec 14, 2004Lucent Technologies Inc.Methods and devices for relieving congestion in hop-by-hop routed packet networksUS6831898Aug 16, 2000Dec 14, 2004Cisco Systems, Inc.Multiple packet paths to improve reliability in an IP networkUS6879667Apr 23, 2002Apr 12, 2005General Bandwidth Inc.System and method for interfacing telephony voice signals with a broadband access networkUS6956820Sep 17, 2004Oct 18, 2005Santera Systems, Inc.Methods, systems, and computer program products for voice over IP (VoIP) traffic engineering and path resilience using network-aware media gatewayUS7177943Dec 27, 2001Feb 13, 2007Cisco Technology, Inc.System and method for processing packets in a multi-processor environmentUS7185094Sep 26, 2001Feb 27, 2007Sandcherry, Inc.Media session framework using a control module to direct and manage application and service serversUS7212519Dec 21, 2001May 1, 2007Ericsson Inc.Combining narrowband applications with broadband transportUS7394818Sep 22, 2000Jul 1, 2008Qwest Communications International Inc.Extended multi-line hunt group communicationUS7411963 *Jan 19, 2005Aug 12, 2008Cisco Technology, Inc.Method for dissemination of non-routing information using the IS-IS protocolUS7424025Oct 1, 2003Sep 9, 2008Santera Systems, Inc.Methods and systems for per-session dynamic management of media gateway resourcesUS7460481 *Dec 1, 2004Dec 2, 2008Cisco Technology, Inc.Inter-domain TE-LSP with IGP extensionsUS7522603 *Mar 14, 2006Apr 21, 2009Cisco Technology, Inc.Technique for efficiently routing IP traffic on CE-CE paths across a provider networkUS7570594Oct 10, 2006Aug 4, 2009Santera Systems, LlcMethods, systems, and computer program products for multi-path shortest-path-first computations and distance-based interface selection for VoIP trafficUS7623461 *Feb 9, 2005Nov 24, 2009Cisco Technology, Inc.Trigger for packing path computation requestsUS7715403 *Nov 8, 2006May 11, 2010Genband Inc.Methods, systems, and computer program products for load balanced and symmetric path computations for VoIP traffic engineeringUS7792991 *Dec 17, 2002Sep 7, 2010Cisco Technology, Inc.Method and apparatus for advertising a link cost in a data communications networkUS20010036173Feb 6, 2001Nov 1, 2001Shmulevich Oren TConvergence of telephone signaling, voice and data over a packet-switched networkUS20020006112May 4, 2001Jan 17, 2002Jaber Abed MohdMethod and system for modeling and advertising asymmetric topology of a node in a transport networkUS20020012352Jul 9, 2001Jan 31, 2002Goran HanssonInternet protocol handler for telecommunications platform with processor clusterUS20020016926Apr 26, 2001Feb 7, 2002Nguyen Thomas T.Method and apparatus for integrating tunneling protocols with standard routing protocolsUS20020051464Aug 14, 2001May 2, 2002Sin Tam WeeQuality of transmission across packet-based networksUS20020172221May 18, 2001Nov 21, 2002Telgen CorporationDistributed communication device and architecture for balancing processing of real-time communication applicationsUS20020176374May 20, 2002Nov 28, 2002Dae-Hyun LeeVoice over internet protocol gateway and a method for controllling the sameUS20020191612Jan 28, 2002Dec 19, 2002Placeware, Inc.Method and apparatus for automatically determining an appropriate transmission method in a networkUS20030093555Nov 9, 2001May 15, 2003Harding-Jones William PaulMethod, apparatus and system for routing messages within a packet operating systemUS20030099192Nov 28, 2001May 29, 2003Stacy ScottMethod and system for a switched virtual circuit with virtual terminationUS20030118039Dec 12, 2002Jun 26, 2003Hidetaka NishiGatewayUS20030131263Jan 16, 2003Jul 10, 2003Opeanreach, Inc.Methods and systems for firewalling virtual private networksUS20030142795Dec 6, 2002Jul 31, 2003Gavette Sherman L.Home network telephone answering system and method for sameUS20030193898Apr 15, 2002Oct 16, 2003Wong Vincent Chi ChiuMethod and apparatus for selecting maximally disjoint shortest paths in a networkUS20040047345Aug 25, 2003Mar 11, 2004Ibasis, Inc.System and method for voice over internet protocol (VoIP) and facsimile over internet protocol (FoIP) calling over the internetUS20040066782Sep 22, 2003Apr 8, 2004Nassar Ayman EsamSystem, method and apparatus for sharing and optimizing packet services nodesUS20050068942Sep 30, 2003Mar 31, 2005Chu Thomas P.Method and apparatus for establishment and management of voice-over IP virtual private networks in IP-based communication systemsUS20050073998Sep 17, 2004Apr 7, 2005Santera Systems, Inc.Methods, systems, and computer program products for voice over IP (VoIP) traffic engineering and path resilience using media gateway and associated next-hop routersUS20050111349 *Nov 21, 2003May 26, 2005Vasseur Jean P.Method and apparatus for determining network routing information based on shared risk link group informationUS20060159083 *Jan 19, 2005Jul 20, 2006Ward David DMethod for dissemination of non-routing information using the IS-IS protocolUS20070053300Oct 10, 2006Mar 8, 2007Santera Systems, Inc.Methods, systems, and computer program products for multi-path shortest-path-first computations and distance-based interface selection for VoIP trafficUS20070064613Nov 8, 2006Mar 22, 2007Santera Systems, Inc.Methods, systems, and computer program products for load balanced and symmetric path computations for VoIP traffic engineeringUS20070083528Nov 6, 2006Apr 12, 2007Fortinet, Inc.Switch management system and methodEP1235409A2Feb 26, 2002Aug 28, 2002AlcatelMulti-homing proxy apparatus, and associated method, for digital communication networkGB2363549A Title not availableWO2001043387A2Sep 27, 2000Jun 14, 2001Nortel Networks LimitedVoip switch with a distributed mtp level 2 architectureWO2004002173A1Jun 12, 2003Dec 31, 2003Siemens AktiengesellschaftFail-safe interfacing of a network element with a communication networkWO2004071036A1Feb 2, 2004Aug 19, 2004Telefonaktiebolaget Lm Ericsson (Publ)Shared risk group handling within a media gateway* Cited by examinerNon-Patent CitationsReference1"Gateway Control Protocol: Shared Risk Group Package," ITU-T H.248.22, pp. 1-14 (Jul. 2003).2Communication pursuant to Article 94(3) EPC for European application No. 04789215.3 (Sep. 1, 2010).3Communication pursuant to Article 94(3) EPC for European application No. 04789216.8 (Oct. 28, 2010).4Communication pursuant to Article 94(3) EPC for European application No. 04789383.9 (Nov. 23, 2010).5Dagiuklas et al., "Architecture and Design of an Enhanced H.323 VoIP Gateway," Proceedings of IEEE International Conference on Communications, vol. 2, pp. 1209-1213 (Apr. 28, 2002).6 *Final Official Action for U.S. Appl. No. 10/943,513 (May 5, 2009).7International Search Report and Written Opinion for International Application No. PCT/US04/31918 (Feb. 11, 2005).8International Search Report and Written Opinion for International Application No. PCT/US04/31920 (Mar. 4, 2005).9Interview Summary for U.S. Appl. No. 10/676,233 (Aug. 22, 2007).10 *Interview Summary for U.S. Appl. No. 10/943,513 (Feb. 2, 2010).11 *Interview Summary for U.S. Appl. No. 11/545,788 (Sep. 15, 2008).12Katz et al., "Traffic Engineering (TE) Extensions to OSPF Version 2," IETF RFC 3630, Network Working Group (Sep. 2003).13Moy, "OSPF Version 2," IETF RFC 2328, Network Working Group (Apr. 1998).14 *Non-Final Official Action for U.S. Appl. No. 10/943,513 (Nov. 17, 2009).15Notice of Allowance and Fee(s) Due for U.S. Appl. No. 10/676,233 (May 2, 2008).16Notice of Allowance and Fee(s) Due for U.S. Appl. No. 10/943,275 (Feb. 11, 2005).17Notice of Allowance and Fee(s) Due for U.S. Appl. No. 10/943,513 (Dec. 29, 2010).18Notice of Allowance and Fee(s) Due for U.S. Appl. No. 10/943,513 (May 17, 2010).19 *Notice of Allowance and Fee(s) Due for U.S. Appl. No. 11/545,788 (Nov. 5, 2008).20 *Notice of Allowance and Fee(s) Due for U.S. Appl. No. 11/594,568 (Dec. 22, 2009).21 *Notice of Allowance and Issue Fee(s) Due for U.S. Appl. No. 11/545,788 (Mar. 24, 2009).22Notification of European Publication Number and Information on the Application of Article 67(3) EPC for European Application No. 04789213.8 (May 17, 2006).23Notification of European Publication Number and Information on the Application of Article 67(3) EPC for European Application No. 04789215.3 (May 24, 2006).24Notification of European Publication Number and Information on the Application of Article 67(3) EPC for European Application No. 04789383.9 (May 17, 2006).25Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration for International Application No. PCT/US04/32232 (Jun. 2, 2008).26Official Action for U.S. Appl. No. 10/676,233 (Jun. 11, 2007).27Official Action for U.S. Appl. No. 10/676,233 (Nov. 28, 2007).28Official Action for U.S. Appl. No. 10/943,513 (Aug. 11, 2008).29Official Action for U.S. Appl. No. 10/943,513 (Nov. 26, 2007).30Official Action for U.S. Appl. No. 11/545,788 (Mar. 11, 2008).31Official Action for U.S. Appl. No. 11/545,788 (May 14, 2007).32Official Action for U.S. Appl. No. 11/545,788 (Nov. 14, 2007).33 *Official Action for U.S. Appl. No. 11/594,568 (May 14, 2009).34 *Restriction/Election Requirement for U.S. Appl. No. 11/594,568 (Nov. 26, 2008).35Supplemental European Search Report for European application No. 04789213.8 (Jul. 20, 2010).36Supplemental European Search Report for European application No. 04789383.9 (Jul. 14, 2010).37Supplemental Notice of Allowability for U.S. Appl. No. 10/943,275 (Sep. 9, 2005).38 *Supplementary European Search Report for European application No. 04789215.3 (Dec. 8, 2009).39Venkatachalam et al., "A Highly Flexible, Distributed Multiprocessor Architecture for Network Processing," Computer Networks, vol. 41, No. 5, pp. 563-586 (Apr. 5, 2003).40Yoo et al., "A Media Stream Processing of VoIP Media Gateway," IEEE, vol. 1, pp. 91-94 (Sep. 2003).* Cited by examinerClassifications U.S. Classification370/238, 370/254, 370/389International ClassificationG01R31/08Cooperative ClassificationH04L45/3065, H04L45/12European ClassificationH04L45/3065, H04L45/12Legal EventsDateCodeEventDescriptionDec 2, 2011ASAssignmentOwner name: COMERICA BANK (A TEXAS BANKING ASSOCIATION), AS AGFree format text: AMENDED AND RESTATED INTELLECTUAL PROPERTY SECURITY AGREEMENT;ASSIGNOR:GENBEND US LLC (A DELAWARE LLC);REEL/FRAME:027315/0293Effective date: 20110729Dec 29, 2014FPAYFee paymentYear of fee payment: 4Jul 6, 2016ASAssignmentOwner name: SILICON VALLEY BANK, AS ADMINISTRATIVE AGENT, CALIFree format text: PATENT SECURITY AGREEMENT;ASSIGNOR:GENBAND US LLC;REEL/FRAME:039269/0234Effective date: 20160701Jul 7, 2016ASAssignmentOwner name: GENBAND US LLC, TEXASFree format text: RELEASE AND REASSIGNMENT OF PATENTS;ASSIGNOR:COMERICA BANK, AS AGENT;REEL/FRAME:039280/0467Effective date: 20160701Jan 3, 2017ASAssignmentOwner name: SILICON VALLEY BANK, AS ADMINISTRATIVE AGENT, CALIFree format text: CORRECTIVE ASSIGNMENT TO CORRECT THE REMOVE PATENT NO. 6381239 PREVIOUSLY RECORDED AT REEL: 039269 FRAME: 0234. ASSIGNOR(S) HEREBY CONFIRMS THE PATENT SECURITY AGREEMENT;ASSIGNOR:GENBAND US LLC;REEL/FRAME:041422/0080Effective date: 20160701Owner name: SILICON VALLEY BANK, AS ADMINISTRATIVE AGENT, CALIFree format text: CORRECTIVE ASSIGNMENT TO CORRECT PATENT NO. 6381239 PREVIOUSLY RECORDED AT REEL: 039269 FRAME: 0234. ASSIGNOR(S) HEREBY CONFIRMS THE PATENT SECURITY AGREEMENT;ASSIGNOR:GENBAND US LLC;REEL/FRAME:041422/0080Effective date: 20160701RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services