Mechanism to guarantee quality of service to real-time traffic on IP networks

• US 6,418,139 B1
• Filed: 11/25/1998
• Issued: 07/09/2002
• Est. Priority Date: 11/25/1998
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Akhtar, Shahid
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US09/200,262
• Time in Patent Office: 1,322 Days
• Field of Search: 370/356, 370/351, 370/389, 370/392, 370/252, 370/254, 370/255, 370/229, 370/231, 370/235, 370/395.5, 370/464, 370/465, 370/466, 370/467, 370/468, 370/400, 370/401, 370/216, 370/217, 370/221, 370/225, 370/228, 370/395.52
• US Class Current: 370/356
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/1106 Call signalling protocols; H.323 and related
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04M 7/006 Networks other than PSTN/ISDN providing telephone service, e.g. Voice over Internet Protocol (VoIP) , including next generation networks with a packet-switched transport layer H04L65/00 takes precedence; aspects not specific to the type of network H04M3/00; special services in those networks H04M3/42

Abstract

A system for routing of data traffic on a communications network comprising a plurality of gatekeepers interlinked to form a network wherein the plurality of gatekeepers control bandwidth and routing of data packets towards destination terminals. A plurality of routers aggregate real time flow of data packets through said gatekeepers, and terminals which are connected to the network via the gatekeepers, negotiate connection parameters. Real time flow of said data packets is directed from one end point terminal to another utilizing the gatekeepers and the routers.

Claims

1. A system for routing of real time data traffic on a communications network comprising:

a plurality of gatekeepers linked together to form a network wherein said plurality of gatekeepers control bandwidth and routing of data packets towards destination terminals;

a plurality of routers which aggregate real time flow of data packets through said gatekeepers;

terminals which are connected to the network via said gatekeepers and which negotiate connection parameters;

means for compiling external routing information for each of said plurality of routers including shortest paths to each destination terminal;

means for broadcasting said external routing information to other routers within said network to allow said other routers to update their external routing information and determine active neighboring routers, wherein a subsequent transmission from a first router only requires knowledge of a closest neighbor in a destination link; and

control means for directing real time flow of said data packets from one end point terminal to another utilizing said gatekeepers and said routers, wherein real time traffic is allocated to a selected portion of a bandwidth of each link to provide efficient real time traffic transfer along with standard data traffic transfer;

wherein said routers and gatekeepers utilize a process of determining a shortest path between said routers and gatekeepers and further wherein the shortest paths are utilized in establishing the communications network at the logical level of said gatekeepers and at a different network level for said routers, wherein spare capacity for each logical link is allocated to a second shortest path between said routers and said gatekeepers.

2. The system of claim 1, further comprising a plurality of gateways wherein said gateways represent a collection of said terminals and said gateways translate other bearer protocols to the Internet Protocol to enable packet transfer within said network.

3. The system of claim 1, wherein said routers include software switching algorithms programmed with a predetermined percent representing a portion of a link'"'"'s bandwidth reserved for real time traffic and further wherein said routers give a higher priority to said predetermined percent of the bandwidth reserved for real time traffic in routing data to its destination.

4. The system of claim 1, wherein said gatekeepers log routing information in a routing table comprising a first column indicating a first address node and a second column specifying a second address node, and wherein said routing table provides shortest paths of logical links between said first and second address nodes according to the weights on the logical links for real time traffic.

5. The system of claim 4, wherein said routing table further provides spare capacity for each logical link on a second shortest path between said two address nodes.

6. The system of claim 1, wherein each gatekeeper utilizes shortest path algorithm to interconnect with neighboring gatekeepers based on logical links determined from both cost of said gatekeeper to its neighbors and IP addresses directly reachable from said gatekeeper, and further wherein said logical links are utilized to build a network topology to find routes to other gatekeepers, said control means further comprising:

means for allocating a cost associated with each hop of a link connecting two terminals and determining total costs for each possible link between said two terminals; and

means for dynamically evaluating a best route/link based on said cost; and

means, responsive to more than one route/link having an equal cost, for distributing said real time traffic equally among each of said routes.

7. The system of claim 6, wherein a second shortest path with spare capacity is identified and wherein disconnection of said logical link between gatekeepers results in the data packets being directed to said second shortest path.

8. The system of claim 7, further comprising:

means for detecting changes to a router'"'"'s link state that is propagated/broadcasted; and

means, responsive to said detecting, for automatically re-calculating a best route for each router based on said changes.

9. A system for routing of real time data traffic on a communications network comprising:

a plurality of gatekeepers linked together to form a network wherein said plurality of gatekeepers control bandwidth and routing of data packets towards destination terminals;

a plurality of routers which aggregate real time flow of data packets through said gatekeepers, wherein said network formed by said gatekeepers and routers reduces variance and synchronizes packet transmission in the routing of data traffic;

terminals that are connected to the network via said gatekeepers and which negotiate connection parameters;

means for compiling external routing information for each of said plurality of routers including shortest paths to each destination terminal;

means for broadcasting said external routing information to other routers within said network to allow said other routers to update their external routing information and determine active neighboring routers, wherein a subsequent transmission from a first router only requires knowledge of a closest neighbor in a destination link;

control means for directing real time flow of said data packets from one end point terminal to another utilizing said gatekeepers and said routers, wherein real time traffic is allocated to a selected portion of a bandwidth of each link to provide efficient real time traffic transfer along with standard data traffic transfer;

enabling inelastic/real time traffic utilizing a Real-time Transport Protocol (RTP); and

allocating bandwidth to different types of service included in the data packets utilizing weighted fair queuing (WFQ), wherein said plurality of gatekeepers utilize standards of data transfer which permit call-control of real time service on communication networks and allow terminals to negotiate bandwidth and coding requirements for said real time service prior to establishing connection with said gatekeepers and routers.

10. A method of routing of real time data traffic on a communications network comprising the steps of:

linking together a plurality of gatekeepers to form a network wherein said plurality of gatekeepers control bandwidth and routing of data packets towards destination terminals, and wherein further said plurality of gatekeepers utilize standards of data transfer which permit call-control of real time service on communication networks;

aggregating real time flow of data packets through said gatekeepers utilizing a plurality of routers, wherein said routers and gatekeepers utilize a process of determining the shortest path between said routers and gatekeepers;

establishing the communications network at the logical level of said gatekeepers and at a different level network for said routers utilizing the shortest paths;

negotiating connection parameters utilizing terminals which are connected to the network via said gatekeepers;

allowing terminals to negotiate bandwidth and coding requirements prior to establishing connection with said gatekeepers and routers by;

compiling external routing information for each router including shortest paths to each destination node; and

broadcasting said external routing information to other routers within said network to allow said other routers to update their external routing information and determine active neighboring routers, wherein a subsequent transmission from a first router only requires knowledge of a closest neighbor in a destination link; and

controlling real time flow of said data packets from one end point terminal to another utilizing said gatekeepers and said routers, wherein real time traffic is allocated to a selected portion of a bandwidth of each link to provide efficient real time traffic transfer along with standard data traffic transfer.

11. The method of claim 10, wherein said controlling step includes the step of translating other bearer protocols to the Internet Protocol to enable packet transfer within said network utilizing a plurality of gateways representing a collection of said terminals.

12. The method of claim 10, wherein said routers include software switching algorithms programmed with a predetermined percent representing a portion of a link'"'"'s bandwidth reserved for real time traffic and further comprising the step of assigning a higher priority to said predetermined percent of the bandwidth reserved for real time traffic in routing data to its destination.

13. The method of claim 10, further comprising logging routing information in a routing table comprising a first column indicating a first address node and a second column specifying a second address node, wherein said routing table provides the shortest paths of logical links between said first and second address nodes according to the weights on the logical links for real time traffic.

14. The method of claim 13, further comprising the step of providing spare capacity for each logical link on a second shortest path between said two address nodes.

15. The method of claim 10, wherein each gatekeeper utilizes shortest path algorithms to interconnect with neighboring gatekeepers based on logical links determined from both cost of said gatekeeper to its neighbors and IP addresses directly reachable from said gatekeeper, and further wherein said logical links are utilized to build a network topology to find routes to other gatekeepers, said control means further comprising:

allocating a cost associated with each hop of a link connecting two terminals and determining total costs for each possible link between said two terminals; and

dynamically evaluating a best route/link based on said cost; and

responsive to more than one route/link having an equal cost, distributing said real time traffic equally among each of said routes.

16. The method of claim 15, wherein a second shortest path with spare capacity is identified and wherein disconnection of said logical link between gatekeepers results in the data packets being directed to said second shortest path.

17. A method of routing of real time data traffic on a communications network comprising the steps of:

linking together a plurality of gatekeepers to form a network wherein said plurality of gatekeepers control bandwidth and routing of data packets towards destination terminals, and wherein further said plurality of gatekeepers utilize standards of data transfer which permit call-control of real time service on communication networks;

aggregating real time flow of data packets through said gatekeepers utilizing a plurality of routers wherein the network formed by said gatekeepers and routers is utilized to reduce variance and synchronizes packet transmission in the routing of data traffic;

negotiating connection parameters utilizing terminals which are connected to the network via said gatekeepers;

allowing terminals to negotiate bandwidth and coding requirements prior to establishing connection with said gatekeepers and routers by;

compiling external routing information for each router including shortest paths to each destination node; and

broadcasting said external routing information to other routers within said network to allow said other routers to update their external routing information and determine active neighboring routers, wherein a subsequent transmission from a first router only requires knowledge of a closest neighbor in a destination link;

controlling real time flow of said data packets from one end point terminal to another utilizing said gatekeepers and said routers, wherein real time traffic is allocated to a selected portion of a bandwidth of each link to provide efficient real time traffic transfer along with standard data traffic transfer;

enabling inelastic/real time traffic utilizing a Real-time Transport Protocol (RTP); and

allocating bandwidth to different types of service included in the data packets utilizing weighted fair queuing (WFQ), wherein said plurality of gatekeepers utilize standards of data transfer which permit call-control of real time service on communication networks and allow terminals to negotiate bandwidth and coding requirements for said real time service prior to establishing connection with said gatekeepers and routers.