Hop by hop quality of service measurement system

[0001] This application is a continuation of prior U.S. Ser. No. 09/181,952, filed Oct. 28, 1998 now U.S. Pat. No. 6,466,548.

[0002] The present invention relates to a packet switched network used for transmitting audio data, video data or any other delay sensitive data, and more particularly to a hop by hop loopback system that locates quality of service problems in the packet switched network.

[0003] Conversations between two or more people include constant acknowledgements. If the conversation is face to face, the acknowledgement can be either visual or audible. Visual acknowledgements are typically in the form of body motions such as a head nod, hand motion, or facial expression. Audible acknowledgements typically come in the form of words or noises such as “I see”, “ok”, “yes”, “um hum”, etc. Phone conversations also require constant acknowledgements. Since phone conversations are not conducted face to face, these acknowledgements must be given audibly.

[0004] Packet switched networks, such as the Internet, are used for conducting telephone calls. Audio signals from a telephone are converted into voice packets by an originating gateway. The voice packets are then transmitted over the packet switched network to a destination gateway that converts the voice packets back into voice signals that are output to a destination telephone. Delay is a particular problem in packet switched networks that disrupts the interaction and feedback in telephone conversations.

[0005] For example, if the network has a lot of delay, audio feedback can be misinterpreted. A person completing a statement over the phone may wait for an acknowledgement such as “ok”, “yes”, “I see”, “uh hum”, etc. The packet switched network can delay the voice packets containing the acknowledgement. The delayed acknowledgement may be misinterpreted as confusion, apathy, or rudeness. While in fact, an immediate acknowledgement was given by the listener. If audio signals are delayed too long, the speaker may go onto another subject. When the audio packets do arrive, the speaker does not know what part of the conversation the listener was responding to. These network delays result in disjointed and confusing conversations.

[0006] Utilities currently exist that can identify end to end network delay. End to end delay is generally defined as the time it takes a packet to go from an originating telephony gateway endpoint to a destination telephony gateway endpoint. One way to measure end to end delay is to put loopback interfaces into the gateway endpoints. A packet sent from the originating gateway is sent to the destination gateway and then automatically looped back to the originating gateway. The roundtrip delay from the originating gateway to the destination gateway and back to the originating gateway is then calculated.

[0007] A distributed packet switched network includes different subsystems or subnetworks connected together through different network processing nodes such as routers, switches, etc. Any one or more of these subnetworks or processing nodes could be the primary contributor to the end to end delay. End to end delay measurements do not identify where these delays occur in the packet switched network. The subsystems or processing nodes that cause the delay problems, therefore, cannot be located.

[0008] Existing loopback systems also do not test QoS for voice traffic sent over a packet switched network. During any given telephone conversation, the voice packets may be routed through different paths depending on network congestion and other similar considerations. Also, the voice path for incoming voice packets may be different than the voice path for outgoing voice packets. Existing loopback systems, e.g., ping, can only generate one packet about every second. Thus, these loopback systems do not simulate the traffic conditions that are created with an actual audio packet stream. Additionally, ping is based on ICMP, which may receive different treatment by routers than regular traffic.

[0009] Accordingly, a need remains for a system that can identify and locate causes of audio QoS problems in a distributed packet switched network.

[0010] Loopback interfaces are put into routers throughout a packet switched network. When an end to end path in the network is not providing satisfactory Quality of Service (QoS), the delay and jitter characteristics of an audio signal are measured for individual network subsystems between the end to end path. The audio signal is converted into a stream of audio packets and sent hop by hop to the different routers in the network with the loopback interfaces. The QoS for the subsystems are determined by measuring the audio packet stream looped-back from the different routers.

[0011] Subsystems with QoS problems can be identified by comparing the results of adjacent hop by hop loopbacks. If a loopback from a first router has minimal delay and the loopback from a next router has excessive delay, the QoS problem exists in the subsystem between the two routers. The capacity of the network can then be adjusted as necessary according to the measured transmission delay. For example, telephone calls may be rerouted around the problem subsystem through a different network path or additional equipment may be added to the problem subsystem to increase capacity.

[0012] Existing network utilities such as trace route can be used to automatically calculate routes in the packet switched network between a source gateway and a destination gateway. Loopback calls are then automatically sent to routers with loopback interfaces. The loopback delays are then calculated for each of the loopback calls to determine the QoS for the different network subsystems.

[0013] Hop by hop loopback is especially useful to Internet Service Providers (ISPs) that buy network services for different backbone carriers. The QoS can be separately measured for both the ISP network and the backbone carrier networks to determine whether the backbone carrier is meeting agreed upon QoS.

[0014] The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings.

[0020] Referring to FIG. 1, a distributed packet switched network 12 having a hop by hop loopback system includes multiple subnetworks 18, 22, 24, 26 and 28 connected together through different network processing nodes Ra, Rb, Rc, Rd and Re. The subnetworks comprise different Local Area Networks (LANs), Wide Area Networks (WANs) and/or Public Switched Telephone Networks (PSTNs). The processing nodes comprise devices such as routers, switches, communication links etc. These different processing nodes are referred to generally below as routers. A telephone 14 is connected to the network 12 through a Voice over IP (VoIP) gateway 16. A telephone 31 is connected to the network 12 through a VoIP gateway 30.

[0021] The VoIP gateways 16 and 30 are capable of converting back and forth between analog voice signals and audio packets. The gateways 16 and 30 also have end to end loopback capability. Some VoIP gateways with loopback capability include the Model Nos. 2600, 3600 and 5300 manufactured by Cisco Systems, Inc., 170 West Tasman Drive, San Jose, Calif. 95134-1706.

[0022] An end to end telephone call between the gateways 16 and 30 may have unacceptable end to end delay “d”. A system administrator does not know where the primary cause of the delay is occurring in network 12. A delay do may exist between telephone 14 and router Ra, a delay d₁ may exist between the router Ra and a router Rd, a delay d₂ may exist between router Rd and router Re and a delay d₃ may exist between router Re and telephone 31. These delays from the subnetworks and processing nodes between the two endpoints 18 and 30 are additive generating the overall end to end delay d=d₀+d₁+d₂+d₃. One of more of these delays may be the primary contributor to the overall delay d. These delays can be caused by a variety of different reasons such as router congestion or a slow network link along the communication path.

[0023] To perform effective voice QoS testing, the invention places the same loopback interface used in VoIP gateways into non-voice routers, such as routers Ra, Rb, Rc and Rd. The loopback interfaces allow hop by hop loopback testing described below. Any type of network router can be installed with the loopback interface. For example, the Model Nos. 7200, 7500, and 4000 all manufactured by Cisco Systems, Inc. are standard routers used in packet switched networks that can be installed with loopback interfaces.

[0024] The loopback interfaces are implemented in software in the routers. The loopback interfaces receive the audio packets and then send the audio packet stream back out uninterpreted to the originating gateway. This provides reliable audio QoS measurements for any individual subsystem inside the network 12. Separate loopback software interfaces can be used for each supported QoS application. For example, a separate loopback interface can be provided for RTP (protocol carrying voice for H.323, SIP and SGCP), FRF. 11 VoFR and SNA.

[0025] Referring to FIG. 2, the network administrator determines if there is a QoS problem by performing an end to end loopback call from gateway 16 to gateway 30. The description below assumes that gateway 16 originates the hop by hop loopbacks. However, the loopbacks can be originated from any gateway in the network.

[0026] Voice packets are sent out from gateway 16 and then looped back by gateway 30 to gateway 16. The gateway 16 measures the delay required for the voice packets to loop through the entire network 12. If the QoS for the end to end loop back is poor (large delay), the hop by hop loopback system is used to isolate the primary source of the delay.

[0027] The network administrator has a topology of the network 12 that identifies the addresses for the routers, such as Ra, Rb, Re, Rd and Re, that each have a loopback interface according to the invention. To isolate the sublink creating the delay, the system administrator initiates a first loopback call 32 to router Ra. The first loopback call 32 may indicate either a large delay or a small acceptable delay between originating gateway 16 and router Ra. If the delay is small, the problem exists either between router Ra and gateway 30 or along an alternate communication path formed by routers Rb and Re.

[0028] The system administrator continues hop by hop loopback calls through the network 12 until the primary location of the delay is isolated. For example, a second loopback call 33 is initiated from gateway 16 to router Rd. If substantial delay is detected in the second loopback call 33, the QoS problem exists between router Ra and router Rd. If the QoS problem does not appear in the loopback calls 32 and 33, a loopback 34 may be tried in an alternate network path. If the QoS is good for loopback 34, then the next hop by hop loopback call is made to Rc and a next loopback call possibly made to router Re. The hop by hop loopbacks can be initiated in any sequence depending on the network configuration. The sequence described above is merely one example.

[0029] Internet utilities such as Ping diagnose Internet Protocol (IP) connections. Ping can send a signal to any Internet-connected computer. Ping generates data on the number of packets transmitted and received. The problem with Ping is that only about one data packet is sent every second. QoS audio problems are often caused by network congestion. Because PING does not generate packets at audio communication rates of one audio packet every 20 milliseconds, audio QoS problems may not be detected.

[0030] Test loads generated during hop by hop loopback simulate a voice stream generated during a typical telephone call. The hop by hop loopback system can therefore, measure the actual jitter or absolute delay that an audio packet stream actually experiences in the network 12.

[0031] Referring to FIG. 3, existing Internet utilities such as Pathcar can calculate the different routes through network 12. Block 36 uses utilities like Pathcar to calculate a route table for the network 12. The route table is used in block 38 to identify the topology of the network 12 and to identify the routers that have the loopback feature of the invention. Loopback calls are initiated to the identified routers in block 40. The loopback delays are then calculated in block 42. From the calculated delays, a network administrator is then able to determine the source of the QoS problem.

[0032] The loopback calls can also be automatically initiated and measured by software in the gateway 16. Loopback calls are made incrementally starting from either the closest or furthest loopback interface from the originating gateway 16. The loopback calls are then made automatically hop by hop through the network 12, if necessary, to every router with a loopback interface. The loopback delays are then presented in a list to the system administrator. The loopback calls can also be initiated automatically through the network until a certain delay threshold is exceeded. Then only the loopback path exceeding the delay threshold is identified to the network administrator.

[0033] Once the location and source of the QoS problem are identified, steps are taken by the system administrator to correct the QoS problem. If the problem is congestion at a router location, priority bits can be set in the audio packets to increase priority. Different router queuing techniques can also be selected to more efficiently process the audio packets. In addition, faster interfaces, additional routing resources, or upgraded routing resources can be installed at the source of the congestion.

[0034] Referring to FIG. 4, the hop by hop loopback system can also be used for capacity planning. Two routes are shown from the originating gateway 16 to the destination gateway 30. A first path 40 goes through routers Ra and Rd. The second route 42 goes through routers Rb and Rc. The hop by hop loopback system provides a way to quantitatively determine the delay for these individual paths 44 and 46. A system administrator can perform capacity planning around the two paths. For example, the hop by hop loopback delay for path 44 may be substantially less than path 46. The network can then be configured to route telephone calls through path 44.

[0035] Referring to FIG. 5, VoIP gateways include a Public Switched Telephone Network (PSTN) interface 60 that receives Pulse Code Modulated (PCM) audio signals from a PSTN network 62. A Digital Signal Processor (DSP) subsystem 58 encodes the audio signals from the PSTN interface 60 and decodes audio packets from an IP packet router 56. The IP packet router 56 establishes connections for routing the audio packets to the endpoint 16 in the network 12. The multilevel loopbacks are described below in terms of gateway 30. However, the multilevel loopbacks can be performed in any VoIP gateway in network 12.

[0036] A dialplan mapper (not shown) supports multilevel loopback in the gateway 30 so that users or troubleshooters can invoke loopback from any VoIP capable endpoint. The dialplan mapper is described in detail in copending application entitled: SIGNALING STATE MANAGEMENT SYSTEM FOR PACKET NETWORK GATEWAYS; Ser. No. 09/107,071; filed on Jun. 29, 1998 which is herein incorporated by reference.

[0037] The dialplan mapper to various loopback levels maps a dialstring. The syntax is: loopback:where. “Where” is one of three loopback levels, RTP, Compressed, and Uncompressed in the gateway 30. To understand how this works, assume the following configuration in the dial plan mapper of VoIP gateway 30 called “testme”:

• • [0038] +1408526\*311→loopback:RTP
  • [0039] +1408526\*312→loopback:Compressed
  • [0040] +1408526\*313→loopback:Uncompressed
    The dial plan maps for other routers or gateways have the extra entry:
  • [0041] 7*→dns:testme.cisco.com session=cisco controlled_—load best_—effort
    With this setup, different levels of the gateway 30 can be tested from any telephone in network 12.

[0042] For local loopback it is assumed that the calling line has been assigned a number like +1408526xxxx. Phone 31 is picked up and one of the numbers *311, *312, or *313 is dialed. If the phone 31 is on the other side of a PBX or a PSTN 62, enough digits have to be dialed to get the call completed to the VoIP gateway 30. The dotted lines 50, 52, 54, 64, 66 and 68 show the different loopback paths initiated by the different telephone numbers.

[0043] Uncompressed 64: A Pulse Code Modulated (PCM) voice signal coming into the DSP 58 from the PSTN interface 60 is turned around and sent back out PSTN 62 allowing testing of the transmit -> receive paths in the telephony end point 31.

[0044] Compressed 66: A compressed voice signal coming out of a codec in the DSP subsystem 58 is fed back into a decompressor through a jitter buffer. In addition to testing the telephony endpoint, the encode and decode paths in the DSP 58 are tested without involving data paths or packet handling of the IP packet router 56.

[0045] RTP 68: A session application in the IP packet router 56 sets up an RTP stream to itself. RTP is a “Real-Time Transport Protocol” used for transporting voice information and is described in RTP—Internet Request for Comments 1889. The router 56 allocates a port pair and opens the appropriate User Datagram Protocol (UDP) sockets. The router 56 performs full RTP encapsulation, sends the packets to the loopback IP address, receives the RTP packets, and hands the compressed voice back to the CODEC in DSP subsystem 58. This tests the entire local processing path, both transmit and receive, in the router 56, as well as all the other paths described above.

[0046] A remote loopback is an end to end loopback initiated from telephone 14 to the gateway 30 all the way across the packet switched network 12. To initiate a remote loopback, the phone 14 is picked up and the number 7*311, or 7*312 or 7*313 is dialed. Again, if the telephone 14 is connected to the gateway 16 through a PBX or PSTN, enough digits have to be dialed to get the call completed to the VoIP gateway 16. The dial plan in gateway 16 initiates an IP session to testme.cisco.com, and passes the lower part of the number, say *311, to the gateway 30. When the session application on gateway 30 extracts the number with *31x in it, loopback is invoked as follows:

[0047] RTP 54: RTP packets from the network 12 are decapsulated and immediately reencapsulated in the outbound RTP stream, using the same media clock (i.e., time stamp) as the received packet. The RTP packets are then sent back to the source gateway 16 as if the voice signals had originated on a telephony port on testme gateway 30.

[0048] Compressed 52: RTP packets received from the network 12 are decapsulated and passed to the DSP subsystem 58. Instead of feeding the audio packets into the CODEC for decompression, they are immediately sent back to the IP session application in router 56 as if they had originated locally and been compressed. The voice packets may or may not be dejittered before being sent back to router 56.

[0049] Uncompressed 54: In addition to the above, the voice samples are sent all the way through the CODEC in DSP 58 and then turned around instead of being sent to the telephony endpoint 31.

[0050] QoS problems may occur in the RTP path, the DSPs that compress and decompress the audio signals, or the PSTN path after the audio packets have been uncompressed into the speech as it actually is suppose to sound coming out of the gateway 30. Multilevel hop by hop loopback separately tests each one of these paths so QoS problems can be further located inside each VoIP gateway.

[0051] Having described and illustrated the principles of the invention in a preferred embodiment thereof, it should be apparent that the invention can be modified in arrangement and detail without departing from such principles. I claim all modifications and variation coming within the spirit and scope of the following claims.