Abstract:
Loopback interfaces are put into routers in a packet switched network. When an end to end Quality of Service (QoS) path is not performing adequately, the delay and jitter characteristics are measured for individual network subsystems. An audio signal is converted into a stream of audio packets and sent hop by hop to the different routers in the network having the loopback interface. QoS is determined by looping back the stream of audio packets from the different routers. If necessary, the network is reconfigured according to loopback delay in the individual network subsystems. Reconfiguration can comprise routing telephone calls through different paths in the network or adding additional equipment to increase capacity.

Description:
BACKGROUND OF THE INVENTION 
     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. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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. 
     Accordingly, a need remains for a system that can identify and locate causes of audio QoS problems in a distributed packet switched network. 
     SUMMARY OF THE INVENTION 
     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. 
     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. 
     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. 
     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. 
     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. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic diagram of a packet switched network using the hop by hop loopback system according to the invention. 
     FIG. 2 is a schematic diagram of the network in FIG. 1 showing audio loopbacks performed from different processing nodes in the network. 
     FIG. 3 is a block diagram showing how the hop by hop loopback system operates. 
     FIG. 4 is a schematic diagram of the network in FIG. 1 reconfigured according to measurements taken by the hop by hop loopback system in FIG.  2 . 
     FIG. 5 is a detailed block diagram showing how multilevel hop by hop loopback is used in a Voice over IP gateway. 
    
    
     DETAILED DESCRIPTION 
     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 . 
     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. 
     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 1  may exist between the router Ra and a router Rd, a delay d 2  may exist between router Rd and router Re and a delay d 3  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 0 +d 1 +d 2 +d 3 . 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. 
     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. 
     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. 
     Referring to FIG. 2, the network administrator determnines 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. 
     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. 
     The network administrator has a topology of the network  12  that identifies the addresses for the routers, such as Ra, Rb, Rc, 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 Rc. 
     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. 
     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. 
     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 . 
     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. 
     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. 
     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. 
     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 . 
     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 . 
     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. 
     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”: 
     +1408526\*311→loopback:RTP 
     +1408526\*312→loopback:Compressed 
     +1408526\*313→loopback:Uncompressed 
     The dial plan maps for other routers or gateways have the extra entry: 
     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 . 
     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. 
     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 . 
     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 . 
     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 fill 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. 
     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: 
     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 . 
     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 . 
     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 . 
     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. 
     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.