Method and Apparatus for Tracing Frames Transmitted Through a Network Path

The present invention relates generally to a method and apparatus for tracing frames transmitted through a path in a communication network.

Typically, a network may connect many nodes, including user terminals, switches, hubs, bridges, routers, etc. In debugging a network, such as local area network called LAN, it is sometimes needed to trace the path of a frame (a packet or a cell) as it travels through the nodes in the network. In a network debugging process, a frame is called trace frame when it is sent from a source node to a destination node for the purpose of tracing the path taken between the source node and the destination node.

It is known that, in debugging a network that contains ATM (asynchronous transfer mode) network nodes and Ethernet network nodes, a cell is transmitted to travel through a source node and a destination node, a dedicated equipment called protocol analyzer is used to keep tracking the cell at each node passed. However, a protocol analyzer is relatively expensive. For example, the current price of a protocol analyzer manufactured by HP is about $100,000.

Furthermore, it is not convenient to use a protocol analyzer to trace a path if a network has many nodes physically far away from each other. By way of example, if a protocol analyzer is used to trace an exemplary path including four nodes in the sequence of: a first node, a second node, a third node, and a fourth node, the protocol analyzer can be first coupled to the second node to copy (or collect) all the cells that are transmitted on a specific VPI/VCI between the first node and the second node. It can then be coupled to the third node to copy (collect) the cells that are transmitted on a specific VPI/VCI between the second node and the third node. It can finally be coupled to the fourth node to copy (collect) the cells that are transmitted on a specific VPI/VCI between the third node and the fourth node. After all cells have been collected, they need to be correlated to determine the path. As illustrated in the process of tracing the exemplary path, to copy (or collect) the cells transmitted between the third and fourth nodes, the protocol analyzer has to be physically moved from one node to another node.

Therefore, there has been a need to provide a method and an apparatus that can trace frames (cells or packets) in a network economically and efficiently. The present invention meets this need.

In first aspect, the invention provides a method for recording path information in a network. The network includes a plurality of network nodes. The method comprises the steps of:

(a) generating a plurality of data sections, each of said data sections being able of storing path information;

(b) sending said data sections from one of said network nodes to another one of said network nodes; and

(c) recording path information between said one network node and said another one network node in one of said data sections.

In second aspect, the invention provides a method recording path information in a network. The network includes a plurality of network nodes being named as N.sub.0, N.sub.1, . . ., N.sub.i, . . ., N.sub.m. The method comprises the steps of:

(a) generating a plurality of data sections being named as F.sub.1, F.sub.2, . . .,F.sub.i, . . ., F.sub.m, said F.sub.i (i=1, 2, . . ., m) being able of storing path information between two adjacent network nodes N.sub.i-1 and N.sub.i (i=1, 2, . . ., m);

(b) sending said data sections from N.sub.0 through said N.sub.i (i=1; 2m); and

(c) recording path information between N.sub.i-1 and N.sub.i (i=1, 2, . . ., m) into F.sub.i (i=1, 2, . . ., m).

In third aspect, the invention provides a method for recording path information in a network. The network includes a plurality of network nodes. The method comprises the steps of:

(a) generating a start and end data sections;

(b) sending said start and end data sections from one of said network nodes to another one of said network nodes;

(c) inserting a data section between said start and end data sections; and

(c) recording path information between said one network node and said another one network node into said data section.

In fourth aspect, the invention provides a method for recording path information in a network. The network includes a plurality of network nodes being named as N.sub.0, N.sub.1, . . ., N.sub.i, . . ., N.sub.m. The method comprises the steps of:

(a) generating a start and end sections;

(b) sending said data sections from N.sub.0 through said N.sub.i (i=1; 2, . . .,m);

(c) between said start and end sections, inserting a plurality of data sections being named as F.sub.1, F.sub.2, . . ., F.sub.i, . . ., F.sub.m, said F.sub.i (i=1, 2, . . . ., m) being able of storing path information between two adjacent network nodes N.sub.i-1 and N.sub.i (i=1, 2, . . ., m); and

(d) recording path information between N.sub.i-1 and N.sub.i (i=1, 2, . . ., m) into F.sub.i (i=1, 2, . . ., m).

The purpose and advantages of the present invention will be apparent to those skilled in the art from the following detailed description in conjunction with the appended drawing, in which:

FIGS. 1A and 1B show two formats of ATM cells;

FIGS. 2A and 2B show two exemplary networks;

FIG. 3 shows some common function blocks within the network nodes of FIGS. 2A and 2B;

FIGS. 4A-4D show five sets of ATM cells for recording path information, in accordance with one embodiment of the present invention;

FIGS. 5A-5D show five sets of ATM cells for recording path information, in accordance with another embodiment of the present invention;

FIGS. 6A-6D show an ATM cell for recording path information, in accordance with still another embodiment of the present invention;

FIG. 7A shows a flowchart illustrating a process of tracing a path for network 202 as shown in FIG. 2A, in accordance with the present invention;

FIG. 7B shows a flowchart illustrating a process of tracing a path for network 204 as shown in FIG. 2B, in accordance with the present invention;

FIG. 8A shows a flowchart illustrating another process of tracing a path for network 202 as shown in FIG. 2A, in accordance with the present invention;

FIG. 8B shows a flowchart illustrating another process of tracing a path for network 204 as shown in FIG. 2B, in accordance with the present invention;

FIG. 9A shows a flowchart illustrating still another process of tracing a path for network 202 as shown in FIG. 2A, in accordance with the present invention; and

FIG. 9B shows a flowchart illustrating still another process of tracing a path for network 204 as shown in FIG. 2B, in accordance with the present invention.

The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the preferred embodiments will be readily apparent to those skilled in the art, and the principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded with the broadest scope consistent with the principles and features disclosed herein.

Referring to FIGS. 1A and 1B, there are shown two formats of ATM cells, namely UNI (user-network interface) format and NNI (network-network interface) format. Each ATM cell is 53 octets long consisting of a 5-octet header and a 48-octet payload.

In the header of UNI ATM cell shown in FIG. 1A, GFC (generic flow control) is a 4-bit field that can provide local function, such as flow control. VPI (virtual path indicator) is an 8-bit field that identifies the virtual path across the interface. VCI (virtual channel indicator) is a 16-bit field that identifies the virtual channel across an interface. PT (payload type) is a 3-bit field that identifies the type of information contained in payload. In PT field, value 110 is reserved for future traffic control and resource management, and 111 is reserved for future functions. CLP is an 1-bit field that the user or network uses to indicate cell's explicit loss priority. HEC is an 8-bit field that detects and/or corrects bit errors occurring in the header.

As shown in FIG. 1B, the header of NNI ATM cell has a format that is almost identical to UNI ATM cell, except for the first octet. Specifically, in UNI ATM cell, bits 5-8 of first octet are used as GFC; whereas in NNI ATM cell, bits 5-8 of first octet are used to extend the length of VPI from 8 bits to 12 bits.

Referring to FIG. 2A, there is shown an exemplary ATM network 202, which includes three network nodes: two ATM nodes (212, 216) and an ATM switch 214.

In network 202, ATM node 212 is connected to ATM switch 214 via virtual path 213 identified by VPI/VCI with values of 20 and 30 respectively. ATM node 216 is connected to ATM switch 214 via virtual path 215 identified by VPI/VCI with values of 40 and 50 respectively.

Referring to FIG. 2B, there is shown an exemplary ATM-Ethernet network 204, which includes four network nodes: an ATM node 222, an ATM switch 224, an ATM switch/gateway 226, and an Ethernet node 228.

In network 204, ATM node 222 is connected to ATM switch 224 via virtual path 223 identified by VPI/VCI with values of 20 and 30 respectively. ATM switch or ATM gateway 226 is connected to ATM switch 224 via virtual path 225 identified by VPI/VCI with values of 40 and 50 respectively. Ethernet node 228 is connected to ATM switch or ATM gateway 226 via virtual path 227 identified by ESI (end system identifier) portion of ATM address 100070B81234 and Ethernet MAC (medium access control) address 100070B85678. The ESI portion of ATM address is also known as MAC address.

In FIGS. 2A and 2B, ATM nodes 212, 216, 222 and 226 are capable of processing ATM data flow in appliance with ATM network protocols. Two ATM switches (214, 224) and ATM switch/gateway 226 are capable of switching ATM data flow in compliance with ATM network protocols. In addition, ATM switch/gateway 226 can process Ethernet data flow in compliance with Ethernet network protocol, so that ATM switch/gateway can be used in Ethernet LAN emulation environment. Ethernet node 228 is capable of processing Ethernet frames in compliance with Ethernet network protocols.

Referring to FIG. 3, there is shown some common function blocks contained in ATM nodes 212, 216 and 222; ATM switches 214 and 224; ATM switch/gateway 226; and Ethernet node 228. 7

As shown in FIG. 3, memory 312 is able to store programs (which includes instructions and data). Buffer circuitry 316 is able to receive frames/ATM cells via input bus 314, store the frames/ATM cells, and send the frames/ATM cells out via output bus 318. Processor 310 has access to memory 312 and is able to execute the programs to perform desired functions. Process 310 is also able to manipulate the frames/ATM cells received by buffer circuitry 316 and control the operation of buffer circuitry 316.

Before elaborating the present invention in further detail, it is beneficial to describe the gist of one embodiment of the present invention. To debug a network, a source node (called N.sub.s) in the network generates a set of trace cells, including a start trace cell and a plurality of blank message trace cells, and sends the set of trace cells to an adjacent node (called N.sub.1) in the network. After receiving the set of trace cells, N.sub.1 finds the first blank message trace cell, fills it with the path information between N.sub.s and N.sub.1, and sends the set of trace cells to its adjacent node (called N.sub.2) in the network. After receiving the set of trace cells, N.sub.2 finds the second blank message trace cell, fill it with the path information between N.sub.1 and N.sub.2, and sends the set of trace cells to its adjacent node (called N.sub.3) in the network. This process is repeated until the set of trace cells reaches a destination node (called N.sub.n) where the path information between N.sub.n-1 and N.sub.n is filled into n.sup.th blank message trace cell. At the destination node, the path information can be collected from the set of trace cells.

Referring to FIGS. 4A-4D, there are shown four sets of ATM trace cells, in accordance with one embodiment of the present invention.

Referring to FIGS. 5A-5D, there are shown four sets of ATM trace cells, in accordance with another embodiment of the present invention.

Referring to FIGS. 6A-6D, there shown a trace cell for recording path information while it is traveling through network nodes, in accordance with still another embodiment of the present invention.

As discussed above, since in PT field, value 110 and 111 are reserved for future functions, either value in PT field can be used to indicate a trace cell. A specific value in first octet of payload can be used to indicate trace cell type. For example, in first octet, 00000001 can be used to indicate start trace cell; 00000000 a blank message trace cell; 00000010 a filled trace cell; and 00000011 an end trace cell (operational).

Referring to FIG. 7A, there is shown a flowchart illustrating a process of tracing a path for network 202 as shown in FIG. 2A, in accordance with the present invention.

In step 704, as a source node, ATM node 212 generates a set of trace cells (one start trace cell and four blank message trace cells numerated as 412, 414, 416, 418, 420, respectively, as shown in FIG. 4A), and sends this set of trace cells to ATM switch 214. The values of the PT fields in all five trace cells are either 110 or 111, indicating these cells are trace cells. The start trace cell indicates the start position of the trace cells, and each of the message trace cells is able to record path information. The value of the first octet in the payload of the start trace cell is 00000001, indicating a start trace cell; and the value of the first octet in the payloads of all four blank message trace cells is 00000000, indicating a blank message trace cell.

In step 708, ATM switch 214 receives the set of trace cells as shown in FIG. 4A; skips start trace cell by checking the value of the first octet; finds first blank message trace cell (which is trace cell 414) by checking the value of the first octet, fills VPI/VCI value (20,30 in this step) into trace cell 414 as shown in FIG. 4B; and changes value of the first octet in trace cell 414 from 00000000 to 00000010, indicating that trace cell 414 is a filled message trace cell. Then, ATM switch 214 sends the set of trace cells as shown in FIG. 4B to ATM node 216.

In step 710, ATM node 216 receives the set of trace cells as shown in FIG. 4B; skips start trace cell by checking the value of the first octet in the payload; skips message trace cell 414 because the value of the first octet in the payload is 00000010, indicating that it is a filled message trace cell; finds first blank message trace cell (which is trace cell 416) by checking the value of the first octet in the payload, fills VPI/VCI value (40,50 in this step) into trace cell 416; and changes value of the first octet of the payload in trace cell 416 from 00000000 to 00000010, indicating that trace cell 416 is a filed message trace cell.

In step 712, since ATM node 216 is a destination node, the path information is collected from the set of trace cells as shown in FIG. 4C.

Referring to FIG. 7B, there is shown a flowchart illustrating a process of tracing a path for network 204 as shown in FIG. 2B, in accordance with the present invention.

In step 724, as a source node, ATM node 222 generates a set of trace cells (one start trace cell and four blank message trace cells numerated as 412, 414, 416, 418, 420, respectively, as shown in FIG. 4A), and sends this set of trace cells to ATM switch 224. The values of in the fields of the five trace cells are set the same as described in step 704 above.

In step 728, ATM switch 224 receives the set of trace cells as shown in FIG. 4A; skips start trace cell by checking the value of the first octet in the payload; finds first blank message trace cell (which is trace cell 414) by checking the value of the first octet in the payload, fills VPI/VCI value (20,30 in this step) into trace cell 414; and changes value of the first octet in the payload of trace cell 414 from 00000000 to 00000010, indicating that trace cell 414 is a filled message trace cell. Then, ATM switch 224 sends the set of trace cells as shown in FIG. 4B to ATM switch/gateway 226.

In step 730, ATM switch/gateway 226 receives the set of trace cells as shown in FIG. 4B; skips start trace cell by checking the value of the first octet in the payload; skips trace cell 414 because the value of the first octet in the payload is 00000010, indicating that it is a filled message trace cell; finds first blank message trace cell (which is trace cell 416) by checking the value of the first octet in the payload, fills VPI/VCI value (40,50 in this step) into trace cell 416; and changes value of the first octet in the payload of trace cell 416 from 00000000 to 00000010, indicating that trace cell 416 is a filled message trace cell. Before sending the set of trace cells to Ethernet node 228, ATM switch/gateway 226 generates an Ethernet frame and embeds the set of trace cells as shown in FIG. 4C into the Ethernet frame.

In step 732, after receiving the Ethernet frame, Ethernet node 228 recovers the trace cells into the format as shown in FIG. 4C, finds the first blank message trace cell (which is trace cell 418), and fills ATM/Ethernet address value (100070B81234, 100070B85678 in this step) into trace cell 418 as shown in FIG. 4D; and changes value of the first octet in the payload of trace cell 418 from 00000000 to 00000010, indicating that trace cell 418 is a filled message trace cell.

In step 734, since Ethernet node 228 is a destination node, the path information is collected from the set of trace cells as shown in FIG. 4D.

Referring to FIG. 8A, there is shown a flowchart illustrating another process of tracing a path for network 202 as shown in FIG. 2A, in accordance with the present invention.

In step 804, as a source node, ATM node 212 generates a set of trace cells (one start trace cell and one end trace cell numerated as 512, 520, respectively, as shown in FIG. 5A), and sends this set of trace cells to ATM switch 214. The values of the PT fields in these two are 110 or 111, indicating these cells are trace cells. The start trace cell and end trace cell indicate the start and ending positions of the set of trace cells. The value of the first octet of the payload in the start trace cell is 00000001, indicating a start trace cell; and the value of the first octet of the payload in the end cell is 00000011, indicating an end trace cell.

In step 808, ATM switch 214 receives the set of trace cells as shown in FIG. 5A; skips the start trace cell and finds the end trace cell, by checking the values of the first octet in the payloads of these two cells; generates a message trace cell (which is trace cell 514 shown in FIG. 5B), and fills VPI/VCI value (20, 30 in this step) into trace cell 514; fills the value of PT field with 110 or 111; fills the value of the first octet of the payload in trace cell 514 with 00000010, indicating that trace cell 514 is a filled message cell; and inserts trace cell 514 before the end trace cell. Then, ATM switch 214 sends the set of trace cells as shown in FIG. 5B to ATM node 216.

In step 810, ATM node 216 receives the set of trace cells as shown in FIG. 5B; finds the end trace cell; generates a message trace cell (which is trace cell 516 shown in FIG. 5C) by, fills VPI/VCI value (40, 50 in this step) into trace cell 516; fills the value of PT filed with 110 or 111, fills value of the first octet in the payload of trace cell 516 with 00000010, indicating that trace cell 516 is a filled message trace cell; and insert trace cell 516 before the end trace cell.

In step 812, since ATM node 216 is a destination node, the path information is collected from the set of trace cells as shown in FIG. 5C.

Referring to FIG. 8B, there is shown a flowchart illustrating another process of tracing a path for network 204 as shown in FIG. 2B, in accordance with the present invention.

In step 824, as a source node, ATM node 222 generates a set of trace cells (one start trace cell and one end trace cell numerated as 512, 520, respectively, as shown in FIG. 5A), and sends this set of trace cells to ATM switch 224. The values of in the fields of trace cells are set the same as in step 804 above.

In step 828, ATM switch 224 receives the set of trace cells as shown in FIG. 5A; finds end trace cell; generates a message trace cell (which is trace cell 514 shown in FIG. 5B), and fills VPI/VCI value (20, 30 in this step) into the payload of trace cell 514; fills value of the first octet in the payload of trace cell 514 with 00000010, indicating that trace cell 514 is a filled message trace cell; and inserts trace cell 514 before the end trace cell. Then, ATM switch 224 send the set of trace cells as shown in FIG. 5B to ATM switch/gateway 226.

In step 830, ATM switch/gateway 226 receives the set of trace cells as shown in FIG. 5B; finds the end trace cell, generates a message trace cell (which is trace cell 516 shown in FIG. 5C), fills VPI/VCI value (40, 50 in this step) into the payload of trace cell 516; fills the value of the first octet in the payload of trace cell 516 with 00000010, indicating that trace cell 516 is a message filled trace cell; and inserts trace cell 516 before the end trace cell. Before sending the set of trace cells to Ethernet node 228, ATM switch/gateway 226 generates an Ethernet frame and embeds the set of trace cells as shown in FIG. 5C into the Ethernet frame.

In step 832, after receiving the Ethernet packet, Ethernet node 228 recovers the trace cells in to the format as shown in FIG. 5C. Then, Ethernet node 228 finds the end trace cell, generates a message trace cell (which is trace cell 518 shown in FIG. 5D), and fills ATM/Ethernet address value (100070B81234, 100070B85678 in this step) into the payload of trace cell 518; fills value of the first octet in the payload of trace cell 518 with 00000010, indicating that trace cell 518 is a filled message trace cell; and insert trace cell 518 before the end cell.

In step 834, since Ethernet node 228 is a destination node, the path information is collected from the set of trace cells as shown in FIG. 5D.

Referring to FIG. 9A, there is shown a flowchart illustrating still another process of tracing path for network 202 as shown in FIG. 2A, in accordance with the present invention.

In step 904, as a source node, ATM node 212 generates a trace cell shown in FIG. 6A, and sends this trace cell to ATM switch 214. The value of the PT field in the trace cell is either 110 or 111, indicating this cell is a trace cell. The value in the payload is all zeros.

In step 908, ATM switch 214 receives the trace cell as shown in FIG. 6A and fills VPI/VCI value (20,30 in this step) into octets 1-4 in the payload. Then, ATM switch 214 sends the trace cell as shown in FIG. 6B to ATM node 216.

In step 910, ATM node 216 receives the trace cell as shown in FIG. 6B, fills VPI/VCI value (40,50 in this step) into octets 5-8 in payload as shown in FIG. 6C.

In step 912, since ATM node 216 is a destination node, the path information is collected from the payload of the trace cell as shown in FIG. 6C.

Referring to FIG. 9B, there is shown a flowchart illustrating still another process of tracing a path for network 204 as shown in FIG. 2B, in accordance with the present invention.

In step 928, as a source node, ATM node 222 generates a trace cell as shown in FIG. 6A and sends this trace cells to ATM switch 224. The values of in the fields of the trace cell are the same as described in step 904 above.

In step 930, ATM switch 224 receives the trace cell as shown in FIG. 6A; fills VPI/VCI value (20,30 in this step) into octets 1-4 in payload, and sends the trace cell as shown in FIG. 6B to ATM switch/gateway 226.

In step 932, ATM switch/gateway 226 receives the trace cell as shown in FIG. 6B; and fills VPI/VCI value (40,50 in this step) into octets 5-8 in the payload. Before sending the trace cell to Ethernet node 228, ATM switch/gateway 226 generates an Ethernet frame and embeds the trace cell as shown in FIG. 6C into the Ethernet frame.

In step 934, after receiving the Ethernet frame, Ethernet node 228 recovers the trace cell in to the format as shown in FIG. 6C. Then, Ethernet node 228 fills ATM/Ethernet address value (100070B81234, 100070B85678 in this step) into octets 9-12 in the payload.

In step 936, since Ethernet node 228 is a destination node, the path information is collected from the trace cell as shown in FIG. 6D.

In the present invention, the software to perform the steps shown in FIGS. 7A, 7B, 8A, 8B, 9A and 9B is stored in memory 312 and executed by processor 310.

While the invention has been illustrated and described in detail in the drawing and foregoing description, it should be understood that the invention may be implemented through alternative embodiments within the spirit of the present invention. By way of one example, the embodiments in FIGS. 7A, 7B, 8A, 8B, 9A and 9B specifically use ATM cells to record path information. However, the principle in the present invention also applies to other formats of frames. Thus, the scope of the invention is not intended to be limited to the illustration and description in this specification, but is to be defined by the appended claims.