Method of transferring packets and router device therefor

The present invention relates to a method of transferring packets and a device therefor. In particular, it relates to a method of transferring packets and a device corresponding to Multi Protocol Label Switching.

Internet Protocol (IP) network is becoming one of the important infrastructure which would replace the telephone network because of its low cost. Accordingly, achievement of high reliability which has been achieved in the conventional telephone network such as recovery in the event of a fault in the network, etc. and guarantee of Quality of Service (QoS) such as reduced delay time and low discarding rate are requested.

As a recovery system of a failure in the network, a high-speed path switching technique using Multi Protocol Label Switching (MPLS) is known. With reference to MPLS, there is a description in RFC 3031 of Internet Engineering Task Force (IETF). Also, with reference to a high-speed path switching technique using MPLS, there is a description in draft-ietf-mpls-rsvp-lsp-fastreroute-00.tx, Internet draft of IETF.

First, an outline of MPLS will be described. MPLS is a packet transfer system in which a router determines the destination of a packet according to a value of a label added to the packet. With reference to FIG. 1 , the outline of the packet transfer using MPLS will be described.

MPLS network 100 of FIG. 1 comprises edge routers ER 1 ( 141 ), ER 2 ( 142 ), ER 3 ( 143 ), ER 4 ( 144 ), which are located at the ports of the network, and core routers CR 1 ( 151 ), CR 2 ( 152 ), CR 3 ( 153 ), which are located in the MPLS network 100 .

Each edge router accommodates a plurality of networks NA ( 161 ), NB ( 162 ), NC ( 163 ) and ND ( 164 ) which are connected with one another via the MPLS network. Each edge router receives a packet from a network that it accommodates, encapsulates the received packet by an MPLS encapsulation header, and transfers it into the MPLS network 100 . In FIG. 1 , among contents of the MPLS encapsulation header, a label alone is shown for the sake of convenience. For example, the edge router ER 1 encapsulates a packet P 1 ( 171 ) received from the network NA by the MPLS encapsulation header containing a label L 11 ( 111 ), and transfers it to the CR 1 . At this point, MPLS encapsulation headers for an output line 181 , the label L 11 , etc. are determined by using information in the header such as a Layer 3 transfer protocol (for example, IP) of the packet P 1 .

The core routers CR 1 , CR 2 determine an output line and a new encapsulation header for outputting by using the MPLS encapsulation header. For example, upon receipt of the packet P 1 , the CR 1 searches a label table held therein using a value of the label L 11 added to the packet P 1 , and determines an output line 1020 - 1 and a label L 12 ( 112 ) for outputting. The CR 1 swaps the label L 11 added to the packet P 1 for the label L 12 for outputting, and transmits the packet to the output line 1020 - 1 . Hereinafter, a label added to a received packet is called an input label and a label newly added by a router when being transferred is called an output label. Likewise, the CR 2 determines an output line 182 and an output label L 13 ( 113 ) of the packet P 1 to which the input label L 12 is added, swaps the input label L 12 for the output label L 13 , and transmits the packet to the output line 182 .

Upon receipt of the packet P 1 to which the label L 13 is added, the edge router ER 3 , using the label L 13 alone, or using the label L 13 and information in the Layer 3 transfer protocol (for example, IP) header of the packet P 1 , determines a place to which the packet P 1 is transmitted (in FIG. 1 , Network NC) and the output line 183 , removes an MPLS encapsulation header, and transmits the packet P 1 to the line 183 . A packet P 2 is also transferred as described above.

As described above, the packet P 1 is transmitted through a path between the routers ER 1 and CR 1 , a path between the routers CR 1 and CR 2 , and a path between the routers CR 2 and ER 3 by using labels L 11 , L 12 and L 13 . Also, a packet P 2 is transmitted through a path between the routers ER 2 and CR 1 , a path between the routers CR 1 and CR 2 , and a path between the routers CR 2 and ER 4 by using labels L 21 , L 22 and L 23 . These paths are called Label Switched Paths (LSP). LSPs are set by a label distribution protocol, or set manually by a network administrator. Label distribution protocols include Label Distribution Protocol (LDP), Constraint-based Routing Label Distribution Protocol (CR-LDP), Extensions to Resource Reservation Protocol for LSP Tunnels (RSVP-TE), etc. Description is made with reference to LDP in RFC 3036 of IETF, with reference to CR-LDP, in draft-ietf-mpls-cr-ldp-04.txt, Internet Draft, and with reference to RSVP-TE, draft-ietf-mpls-rsvp-lsp-tunnel-08.txt, Internet Draft, respectively.

In MPLS, it is possible to explicitly set the LSP. Therefore, it can advantageously provide paths based on the requested communication quality for each traffic and achieve traffic engineering for performance optimization of the network.

Now, with reference to FIGS. 2 and 3 , a high-speed path switching technique using MPLS, which is described in draft-swallow-rsvp-bypass-label-01.txt will be explained.

In this high-speed path switching technique, with respect to a plurality of LSPs set on the same line, only one LSP for switching when the line or next map router has a fault is set. Hereinafter, an LSP for switching in the case of failure is called a backup LSP, and an LSP during a normal operation is called a current LSP. Further, in the high-speed pass switching technique, for the purpose of saving the number of entries of the label table for determining an output label and an output line at the terminal router of the backup LSP, a label stacking technique to add two or more labels is used.

FIGS. 2 and 3 show the MPLS network 100 alone of FIG. 1 , and the networks NA, NB, NC, ND are omitted.

FIG. 2 shows how packets are transferred when the line 1020 - 1 is normal. Further, FIG. 3 shows how packets are transferred in the case when a failure occurs in the line 1020 - 1 (indicated by “X” on the line 1020 - 1 of FIG. 3 ).

In FIG. 2 , an LSP to which the packet P 1 is transferred when the line 1020 - 1 is normal is called LSP 1 , and an LSP to which the packet P 2 is transferred is called LSP 2 . A label used for transfer is the same as the one in FIG. 1 . Labels used in the LSP 1 are the label L 11 ( 111 ) between the routers ER 1 and CR 1 , the label L 12 ( 112 ) between the routers CR 1 and CR 2 , and the label L 13 ( 113 ) between the routers CR 2 and ER 3 . Also, labels used in the LSP 2 are the label L 21 ( 121 ) between the routers ER 2 and CR 1 , the label L 22 ( 122 ) between the routers CR 1 and CR 2 , and the label L 23 ( 123 ) between the routers CR 2 and ER 4 .

In FIG. 3 , a backup LSP 3 for the LSP 1 and the LSP 2 set on the line 1020 - 1 are set on the line 1020 - 2 between the routers CR 1 and CR 3 and on the line 184 between the routers CR 3 and CR 2 . A label used between the routers CR 1 and CR 3 is called L 31 ( 131 ), and a label used between the routers CR 3 and CR 2 is called L 32 ( 132 ).

Referring to FIG. 3 , a method of transferring the packet P 1 when the line 1020 - 1 has a fault will be described. When detecting the fault on the line 1020 - 1 , the core router CR 1 of FIG. 3 changes the number of output labels corresponding to the input label L 11 in the label table from one (L 12 ) to two (L 12 and L 31 ). Further, the core router CR 1 change the output line from the line 1020 - 1 to the line 1020 - 2 . Upon receipt of the packet P 1 , the router CR 1 determines the output labels L 12 , L 31 and the output line 1020 - 2 from the input label L 11 . Then, the input label L 11 is removed from the packet P 1 , and the two output labels are added by using a label stack function. At this point, the label L 31 to be used in a backup LSP is added at a higher position (a position from which data is transferred with priority) of the label L 12 used in the current LSP 1 . Then, the CR 1 transmits the packet P 1 to the line 1020 - 2 . Upon receipt of the packet P 1 , the CR 3 uses only the label L 31 added at the higher position out of the two labels added to the packet P 1 , and determines the output line 184 and the output label L 32 . Among the input labels of the packet P 1 , the CR 3 swaps only the label L 31 added at the higher position for the output label 32 , and transmits it to the line 184 . Upon receipt of the packet P 1 transmitted from the CR 3 , the CR 2 acknowledges itself as a terminal of a backup LSP 3 from a value of the label L 32 added at a higher position among the two labels added to the packet P 1 , and recognizes that the output line and the output label should be determined by using the label L 12 added at a lower position of the label L 32 . Then, the CR 2 determines the output line 182 and the label L 13 for outputting by using the Label L 12 . The CR 2 removes the label L 32 added to the packet P 1 , swaps the label L 12 for the output label L 13 , and transmits it to the line 182 .

A method of transferring the packet P 2 is also the same as that of the packet P 1 except the following points. Of the two output labels added by the CR 1 , the label L 31 added at a higher position is the same as the case of the P 1 , but the other label is the L 22 , which is different. Further, an output label at the CR 2 is the Label 23 , which is also different. As described above, both the packet P 1 transferred in the current LSP 1 and the packet P 2 transferred in the current LSP 2 are transferred likewise in the LSP 3 .

Further, in FIG. 3 , the CR 2 , which is the terminal of a backup LSP, recognizes itself to be a terminal of the backup LSP 3 by using the label L 32 at a higher position and that an output line and an output label should be determined by using the label (L 12 or L 22 ) added at a lower position of the L 32 . On this occasion, in the case of the CR 2 , a label table have to be searched twice according to a certain search method of the label table, which requires longer processing time. In order to avoid this problem, there is a method (Penultimate Hop Popping: hereinafter, called “PHP method”) which removes, in advance, a label added at a higher position by the last router but one before the terminal of the backup LSP. This method will be described referring to FIG. 4 .

In FIG. 4 , a label adding method and a packet transfer method are almost the same as the methods described in FIG. 3 . However, a label adding method at the router CR 3 immediately before the terminal router CR 2 of the backup LSP 3 is different. Using the label L 31 added at a higher position of the received packets P 1 , P 2 , the CR 3 acknowledges itself to be the router immediately before the terminal of the backup LSP 3 . The labels L 12 , L 22 added at the lower position of the label L 31 are the same labels used between CR 1 and CR 2 for transfer in the current LSPs, LSP 1 , LSP 2 . Accordingly, by using this label, the CR 2 can determine the same output line and the output label as those of the current LSP. Therefore, the CR 3 removes only the label L 31 added at a higher position, and transmits the packet to the output line 184 . The router CR 2 receiving the packet uses one of the added labels L 12 , L 22 , and determines the output line and the output label. With the use of the PHP method described above, it is enough to search the label table in the CR 2 only once, and the processing time becomes equal to the one in the transfer processing using the current LSP.

According to the prior art described above, a common backup LSP is set for a plurality of LSPs set in the same line. Therefore, compared to a method of setting a backup LSP for each of the LSPs, the number of LSPs to be managed by the router in the MPLS network can be reduced. For example, when the number of LSPs set in a line is “N”, the number of LSPs to be managed by the prior art 1 is “(N+1)”. However, when setting backup LSPs one to one with respect to a plurality of LSPs, the number of LSPs to be managed is “2N”.

However, in the above prior art, to guarantee communication quality in the backup LSP is not discussed. Now, the problems with regard to the guarantee of communication quality in the backup LSP will be described below.

For example, in FIG. 2 , it is presumed that a group of packets P 1 (hereinafter, referred to as “Traffic 1 ”) transferred by using the LSP 1 is data that can be transferred by a Best Effort method such as E 1 ectronic mail and World Wide Web data, etc. Further, it is presumed that a group of packets P 2 (hereinafter, referred to as “Traffic 2 ”) transferred by the LSP 2 is data whose delay and delay variation should be reduced to minimum, such as data of a real-time system, Voice Over IP, etc.

In FIG. 2 , each router can determine communication quality to be achieved by the LSP 1 and the LSP 2 according to information of an MPLS encapsulation header including a label, and performs communication quality control such as transferring the LSP 2 prior to the LSP 1 . However, when the line has a fault ( FIG. 3 or FIG. 4 ), Traffic 1 and Traffic 2 transferred by the current LSP 1 and LSP 2 are both transferred by the backup LSP 3 using the same label. In this case, since the router CR 3 on the LSP 3 cannot recognize the communication quality of the current LSP, it cannot transfer the LSP 2 prior to the LSP 1 . Accordingly, the guarantee of the communication quality with respect to Traffic 2 once transferred by the current LSP 2 cannot be achieved on the backup LSP 3 .

Therefore, in order to perform the quality guarantee control (QoS control) of the packet, such a system is required that a router on the backup LSP can recognize the communication quality of the current LSP.

In one aspect, the present invention relates to a method of transferring packets for a packet transfer device accommodating a first output line, which is a current path, and a second output line, which is a backup path, and transferring a packet comprising a header and data containing a label for switching the packet and communication quality information of the packet. In the case when the first line does not have a fault, upon a first packet being received, a label in the header of the first packet is rewritten, and the packet whose label is rewritten is outputted to a first output line. Upon a second packet being received, a label in the header of the second packet is rewritten, and the packet whose label is rewritten is outputted to the first output line. In the case when the first line has a fault, upon the first packet being received, communication quality information in the header of the first packet is copied, and an additional header containing the copied priority information and an additional label is added to the first packet, and the packet to which the additional header is added is outputted to the second output line. When the second packet is received, communication quality information in the header of the second packet is copied, and the additional header containing the copied priority information and the additional label is added to the second packet, and the packet to which the additional header is added is outputted to the second output line. In the manner described above, an additional header is added to the packet to be transmitted to the backup path, and communication quality is defined by the additional header.

In another aspect, the present invention relates to processing of the packet containing the additional header formed as above. What is claimed in the present invention is a method of transferring packets for a packet transfer device which has an associating table for a label added to the inputted packet and a label added to the packet to be outputted, and switches the packet inputted from the input line to the output line corresponding to a label added to the packet. In this packet transfer method, a first header containing a first label and identification information of communication quality of the packet is added before data. Further, when a packet to which a second header (additional header) containing a second label (additional label) and identification information of the communication quality is added is received, priority control of the packet transfer is performed based on the identification information of communication quality in the second header. The second header may be placed before the first header. In this case, an output label is obtained by searching the table based on the second label. The second label is swapped for an output label, which can be outputted to the output line. Also, the second header may be removed from the received packet, and the packet whose second header is removed can be outputted to the output line. Further, the first and second headers are Shim headers described in Request for Comments (RFC) 3032, the identification information of communication quality is a value of an Experimental Use (EXP) field of the first header, and the value of the EXP field of the first header and a value of the EXP field of the second header are made to be equal to each other. The essentials of the present invention are a transmission method of those packets and a device configuration for achieving it.

Other aspects of the present invention will be described in the section of embodiments and with reference to the drawings.

FIG. 1 illustrates how a packet is transferred by MPLS;

FIG. 2 illustrates a high-speed path switching technique using conventional MPLS;

FIG. 3 illustrates a high-speed path switching technique using conventional MPLS;

FIG. 4 illustrates a high-speed path switching technique using conventional MPLS;

FIG. 5 shows a format of a packet in an MPLS network;

FIG. 6 shows a format of a Shim header, which is an MPLS encapsulation header;

FIG. 7 shows a configuration of an MPLS network to which the router of the present invention is applied;

FIG. 8 shows a configuration of an MPLS network to which the router of the present invention is applied;

FIG. 9 shows a configuration of an MPLS network to which the router of the present invention is applied;

FIG. 10 shows a configuration of the router of the present invention;

FIG. 11 shows a format of a packet in the router 1000 of the present invention;

FIG. 12 shows a configuration of the routing processing section 1300 ;

FIG. 13 shows a configuration of the label table 1320 ;

FIG. 14 shows a configuration of the label table 1320 , whose set value is different from the one in FIG. 13 ;

FIG. 15 shows another configuration of the routing processing section 1300 , which is different from the one in FIG. 12 ;

FIG. 16 shows a configuration of a line status table; and

FIG. 17 shows another configuration of the label table 1320 , which is different from the ones in FIGS. 13 and 14 .

First, with reference to FIGS. 5 and 6 , a data format of an MPLS encapsulated packet and a format of an MPLS encapsulation header will be described. FIG. 5 shows the data format of the MPLS encapsulated packet. The MPLS encapsulated packet comprises a Layer 2 header section 200 , which is a header of a Layer 2 protocol for PPP, Ethernet, etc., an MPLS encapsulation header section 210 , and a data section 220 , which is packet data. The MPLS encapsulation header section 210 is comprised of n Shim headers (n is an integer larger than 1), namely, Shim header 1 to Shim header n ( 210 - 1 to 210 -n). The data section 220 is, for example, data which is encapsulated by a Layer 3 protocol header such as IP, etc.

FIG. 6 shows a format of a Shim header constituting the MPLS encapsulation header section. The format of the Shim header is a common format for Shim header 1 through Shim header n. The format comprises a label field 211 used by a router for determining an output line and an output label, an Experimental Use (EXP) field 212 for indicating communication quality of a packet in an MPLS network, an S bit field (Bottom of Stack field) 213 , which indicates that the label is located at the lowest position when adding two or more Shim headers (hereinafter, “to add a Shim header” is referred to as “to PUSH”), and a Time to Live (TTL) field 214 , which indicates the number of routers that the packet can pass through in the network. The format shown in FIG. 6 is the same format described in FIG. 1 on Page 3 of RFC 3032.

Upon receipt of the MPLS encapsulated packet, the router searches a label table using a value of the label field 211 as a search key, and determines an output line and more than one output label. Further, the router determines communication quality of the packet based on a value of EXP, and performs priority transfer control for guaranteeing the communication quality. Furthermore, the router subtracts a value of the TTL field 214 in an input Shim header by one, and sets the value in the TTL field in an output Shim header.

Now, with reference to FIGS. 7 through 9 , a packet transfer operation in the MPLS network constructed by using the router of the present invention will be described. FIGS. 7 through 9 show a structure of the network using the router to which the present invention is applied. FIG. 7 , FIG. 8 and FIG. 9 each correspond to FIG. 2 , FIG. 3 and FIG. 4 . Namely, FIG. 7 shows the case when a line 1020 - 1 is normal, and FIGS. 8 and 9 show the case when a line 1020 - 2 has a fault. Further, FIG. 9 shows a packet transfer operation when the router CR 3 uses the PHP method. Further, in FIGS. 7 through 9 , as information in Shim headers, values of EXP ( 191 - 193 ) in addition to a value of a label is shown.

In FIGS. 7 through 9 , the LSP 1 is set between the routers ER 1 , CR 1 , CR 2 and ER 3 , and the LSP 2 is set between the routers ER 2 , CR 1 , CR 2 and ER 4 . Further, as a common backup LSP for the LSP 1 and the LSP 2 in the case when the line 1020 - 1 has a fault, an LSP 3 is set between the routers CR 1 , CR 3 and CR 2 . In the LSP 2 , two traffic (packet P 2 ( 172 ) and packet P 3 ( 173 )) requiring two different communication quality guarantee are transferred, and an E 2 ( 192 ) and an E 3 ( 193 ) are set as EXP values. Further, as an EXP value of the LSP 1 , an E 1 ( 191 ), which is different from the E 2 and the E 3 , is set. The priority shown by each EXP value is the E 1 , the E 2 and the E 3 , in this order. For example, the packet P 1 is data of a Voice Over IP, the packet P 2 is data of a real-time system, and the packet P 3 is data of E 1 ectronic mail.

With reference to FIG. 7 , transfer processing of the packet P 1 when the line 1020 - 1 is normal will be described. Upon receipt of the MPLS encapsulated packet P 1 by the edge router ER 1 , the CR 1 searches a label table by using an input label L 11 and the input EXP value E 1 as search keys, and determines the output line 1020 - 1 , the output label L 12 and communication quality in the device. Further, the input EXP value E 1 is copied, as an output EXP value, to an EXP field in an output Shim header. When showing the output Shim header by using an expression of “(label value, EXP value)”, the output Shim header corresponding to the packet P 1 is (L 12 , E 1 ). Then, the CR 1 removes an input Shim header (L 1 , E 1 ) from the packet P 1 (hereinafter, “to remove a Shim header” is referred to as “to POP”), PUSHes the output Shim header (L 12 , E 1 ), and transmits it from the line 1020 - 1 . When transmitting to the line 1020 - 1 , the CR 1 performs priority transfer control between the packet P 1 and other packets according to communication quality in the device. In this example, since the E 1 has the highest priority, it is preferentially transmitted with respect to other packets. The transfer processing of the packet P 1 in the CR 2 is performed in like manner, and an output Shim header is shown as (L 13 , E 1 ). Upon receipt of the packet P 1 from the CR 2 , the ER 3 removes a Shim header from the packet P 1 according to a value of an input label L 13 , and determines not to PUSH any output label. When the packet P 1 is an IP packet which is transferred by an IP protocol, a routing table of the IP is searched and an output line is determined. Then, the ER 3 POPs the Shim header from the packet P 1 , and transmits it to the output line as the IP packet.

The transfer processing of packets P 2 , P 3 when the line 1020 - 1 is normal is also performed like the transfer processing of the packet P 1 .

Now, with reference to FIG. 8 , transfer processing of the packet P 1 when the line 1020 - 1 has a fault will be described. Upon detecting the fault on the line 1020 - 1 , a line status monitoring section in the CR 1 notifies a control section of it. The control section changes an output label with respect to the input label L 11 in a label table from L 12 to L 12 and L 31 . Further, the control section changes the output line from the line 1020 - 1 , which is used in the current LSP 1 , to the line 1020 - 2 , which is used in the backup LSP 3 . Upon receipt of the packet P 1 , which is MPLS encapsulated by the edge router ER 1 , the CR 1 searches the label table using the input label L 11 and the input EXP value E 1 as search keys, and determines the output line 1020 - 2 , two output labels L 12 , L 31 and communication quality in the device. Further, as an output EXP value, the input EXP value E 1 is copied to EXP fields in two output Shim headers. Therefore, the two output Shim headers corresponding to the packet P 1 are (L 31 , E 1 ) and (L 12 , E 1 ). Then, the CR 1 removes one input Shim label (L 11 , E 1 ) from the packet P 1 , PUSHes two output Shim headers, and transmits them from the line 1020 - 2 . Regarding the order of Shim headers to be PUSHed, if a position from which data is transferred first is called a front, the Shim header (L 31 , E 1 ) is at the front and then comes the Shim header (L 12 , E 1 ). Further, when transmitting to the line 1020 - 2 , the CR 1 performs priority transfer control between the packet and other packets according to communication quality in the device. In the present embodiment, the E 1 has the highest priority. Therefore, the E 1 is the one to be transferred prior to other packets.

Upon receipt of the packet P 1 , whose two Shim headers are PUSHed by the CR 1 , the CR 3 searches the label table using the input label L 31 in the input Shim header, which is PUSHed at the front, and the input EXP value E 1 as search keys, and determines an output line 184 , one output label L 32 , and communication quality in the device. Further, as an output EXP value, the input EXP value E 1 is copied to an EXP field in one of the output Shim headers. Therefore, an output Shim header corresponding to the packet P 1 is (L 32 , E 1 ). Then, the CR 3 removes one Shim header (L 31 , E 1 ) at the front out of the two input Shim headers PUSHed in the packet P 1 , PUSHes one output Shim header (L 32 , E 1 ), and transmits it from the line 184 . Further, when transmitting to the line 184 , according to communication quality in the device, the CR 3 performs priority transfer control over other packets.

Upon receipt of the packet P 1 transmitted from the CR 3 , the CR 2 searches the label table using the input label L 32 in the input Shim header PUSHed at the front and the input EXP value E 1 as search keys. The CR 2 further POPs the input Shim header (L 32 , E 1 ) at the front, and recognizes that it is necessary to search the label table again using another input Shim header (L 12 , E 1 ). Then, the CR 2 searches the label table again using the input label L 12 and the input EXP value E 1 as search keys, and determines an output line 182 , one output label L 13 , and communication quality in the device. Further, as an output EXP value, the CR 2 copies the input EXP value E 1 stored in the second input Shim header to an EXP field in one output Shim header. Therefore, the one output Shim header corresponding to the packet P 1 is (L 13 , E 1 ). Then, the CR 2 removes both the input Shim headers (L 32 , E 1 ), (L 12 , E 1 ) PUSHed in the packet P 1 , PUSHes one output Shim header (L 13 , E 1 ), and transmits it from the line 182 . The packet transfer processing of the ER 3 receiving the packet P 1 from the CR 2 is the same as the case when the line 1020 - 1 is normal.

The transfer processing of the packets P 2 , P 3 when the line 1020 - 1 has a fault is the same as the transfer processing of the packet P 1 .

Now, with reference to FIG. 9 , the case when the router CR 3 uses the PHP method will be described. The packet transfer method of FIG. 9 is the same as the method described in FIG. 8 except that a method of adding Shim headers at the router CR 3 immediately before the terminal router CR 2 of the backup LSP 3 , and a label table search at the CR 2 . Now, transfer processing of the packet P 1 by the CR 3 and the CR 2 will be described.

When adopting the PHP method, upon receipt of the packet P 1 whose two Shim headers are PUSHed by the CR 1 , the CR 3 searches the label table using the input label L 31 in the input Shim header PUSHed at the front and the input EXP value E 1 as search keys. Consequently, the output line 184 and communication quality in the device are determined as in the case of FIG. 8 . However, a significant value is not determined as an output label, and only the POPing of the front input Shim header is determined. Then, out of the two input Shim headers PUSHed in the packet P 1 , the CR 3 removes one front Shim header (L 31 , E 1 ) alone, and transmits it to the line 184 . Further, when transmitting to the line 184 , according to communication quality in the device, the CR 3 performs priority transfer control over other packets. As described above, the Shim header processed by the CR 3 is to only POP the front Shim header of the received packet P 1 , and is different from the case of FIG. 8 .

When adopting the PHP method, upon receipt of the packet P 1 transmitted from the CR 3 , the CR 2 searches the label table using the input label L 12 in the input Shim header, which is PUSHed alone, and the input EXP value E 1 as search keys, and determines the output line 182 , one output label L 13 and communication quality in the device. Further, as an output EXP value, the CR 2 copies the input EXP value E 1 stored in the input Shim header to an EXP field in one output Shim header. Therefore, one output Shim header corresponding to the packet P 1 is (L 13 , E 1 ). Then, the CR 2 removes one input Shim header (L 12 , E 1 ) PUSHed in the packet P 1 , PUSHes one output Shim header (L 13 , E 1 ), and transmits them from the line 182 . As described above, unlike in FIG. 8 , it is not necessary for the CR 2 to search the label table twice, and it can determine an output line and an output Shim header by only one search.

So far, the packet transfer operation in the MPLS network constructed by using the router of the present invention has been described. With the use of the router of the present invention, even when the line has a fault and a packet is transferred by a backup LSP, it is possible for the router in the backup LSP to determine communication quality by using an EXP value, which is used in determination of communication quality in the current LSP. Therefore, even in the backup LSP, the same communication quality as the one in the current LSP can be guaranteed. For example, the packet P 1 , which is data of the Voice Over IP, is most preferentially transferred whether by the current LSP or by the backup LSP, and its communication quality is guaranteed even when the line has a fault.

Now, with reference to FIGS. 10 through 14 , an embodiment of the router of the present invention will be described. FIG. 10 shows a configuration of the router of the present invention. The router 1000 comprises N input lines 1010 -i (i=1 to N), a packet reception processing section 1100 -i which performs reception processing of packets, a packet transfer processing section 1200 , a routing processing section 1300 determining the output lines of packets, a switch 1400 switching packets, a packet transmission processing section 1500 -j performing priority transfer control for every output line, a line status monitoring section 1600 -j monitoring a line status, N output lines 1020 -j where packets are outputted, a control section 1700 performing the overall control of a router and routing processing. The control section 1700 performs setting of each table in the routing processing section and processing of the notice of faults from each line status monitoring section.

FIG. 11 shows an embodiment of a packet format in the router 1000 . The format of a packet in the router 1000 is made by adding an inner header section 230 to the format of the packet in the MPLS network. This inner header section 230 comprises an input line number 231 , which is an identifier of the line to which the packet is inputted, an output line number 232 , which is an identifier of the line to which the packet is outputted, and in-device QoS information 233 indicating communication quality of the packet in the device. In FIG. 11 , a Layer 2 header section 200 is removed from the format of the packet in the MPLS network. However, the Layer 2 header section may be added.

When a packet is inputted from the input line 1010 -i of the router 1000 , the packet reception section 1100 -i adds the inner header section 230 , and writes a line number i of the input line 1010 -i to which the packet is inputted into an input line number 231 , and transmits the packet to the packet transfer processing section 1200 . At this point, the output line number 232 and the in-device QoS information 233 are insignificant values.

Upon receipt of the packet, the packet transfer processing section 1200 accumulates all of the MPLS encapsulation header section 210 , data section 220 , and the inner header section 230 , extracts the MPLS encapsulation header information 210 and the inner header information 230 , and sends them to a routing processing section 1300 .

Using the MPLS encapsulation header information 210 and the inner header information 230 , the routing processing section 1300 performs the label table search, determines an output line (for example, the line 1020 -j), an output Shim header, the number of POPs, the number of PUSHes, and in-device QoS information indicating communication quality of the packet in the device, and notifies the packet transfer processing section 1200 of such information. Further, a configuration and an operation of the routing processing section 1300 will be described later in detail.

The packet transfer processing section 1200 writes a line number j of the output line 1020 -j into the output line number 232 in the inner header, and writes the in-device QoS information into the in-device QoS information 233 in the inner header. Further, using the output Shim header, the number of POPs and the number of PUSHes, the packet transfer processing section 1200 rewrites the Shim header in the MPLS encapsulation header section 210 . The data length of the MPLS encapsulation header section 210 when inputting and the data length of the MPLS encapsulation header section when outputting may differ according to the number of POPs and the number of PUSHes. In such a case, according to the number of POPs and the number of PUSHes, the data length of the MPLS encapsulation header section is readjusted. Then, the packet transfer processing section 1200 transmits the inner packet to a switch 1400 .

According to the output line number 232 , the switch 1400 switches the packet, and transmits it to a packet transmission processing section 1500 -j for each output line. According to the in-device QoS information 233 , the packet transmission processing section 1500 -j performs transmission control corresponding to the priority of packets, deletes the inner header section 230 , and transmits the packet to the output line 1020 -j.

Thus, one embodiment of the router of the present invention has been described.

Now, with reference to FIGS. 12 through 14 , an embodiment of the routing processing section 1300 will be described. FIG. 12 shows a configuration of the routing processing section 1300 . The routing processing section 1300 comprises a header information accumulating section 1310 , a label table 1320 , a label table search processing section 1330 searching the label table 1320 , an inner header information extracting section 1340 , a TTL subtraction section 1350 , and an output Shim header generating section 1360 .

The header information accumulating section 1310 accumulates the MPLS encapsulation header section 210 and the inner header section 230 received from the packet transfer processing section 1200 . The inner header information extracting section extracts an EXP value and a TTL value in the input Shim header accumulated in the header information accumulating section, outputs the EXP value ( 1371 ) to the output Shim header generating section 1360 , and outputs the TTL value ( 1372 ) to the TTL subtraction section 1350 . The TTL subtraction section subtracts the TTL value in the input Shim header by 1, and outputs a calculation result ( 1373 ) to the output Shim header generating section 1360 .

FIG. 13 shows a configuration of the label table 1320 . Each entry of the label table 1320 comprises a label 1321 and an EXP 1322 , which are search keys, and a search result 1323 corresponding to them. The search result 1323 comprises the number of POPs 1324 of the input Shim header, the number of PUSHes 1325 of the output Shim header, 0 or more output labels 1326 for the number of PUSHes, an output line number 1327 , and in-device QoS information 1328 . FIG. 13 shows table setting values when the router 1000 is applied to the CR 1 in FIG. 7 . In this case, the number of POP(s) corresponding to input labels L 11 , L 21 is 1 and the number of PUSH(es) is 1. As for output labels, each one of L 12 and L 22 is respectively set in a label 1 field ( 1326 - 1 ), and the output line is “1”. Further, in order to set in-device QoS information corresponding to an input EXP value, two EXP values E 2 , E 3 are prepared as entries corresponding to the input label L 21 .

FIG. 14 shows table setting values when the router 1000 is applied to the CR 1 of FIG. 8 or FIG. 9 . In this case, the number of POP(s) corresponding to the labels L 11 , L 21 is 1 and the number of PUSHes is 2. Output labels are set at label 1 and label 2 , and the output line is “2”.

Now, an operation of the routing processing section 1300 will be described. Among information accumulated in the header information accumulating section 1310 , the label table search processing section 1330 uses information necessary for the label table search as a search key, and searches the label table 1320 . The result of the search determines the number of POPs 1324 of the input Shim header corresponding to the search key, the number of PUSHes 1325 of the output Shim header, the output labels 1326 for the number of PUSHes, the output line number 1327 , and in-device QoS information 1328 . Among them, the number of POPs, the number of PUSHes, the output line number, and the in-device QoS information are outputted to the packet transfer processing section 1200 as they are ( 1374 in FIG. 12 ). Further, the number of POPs, the number of PUSHes, and the output label are outputted to the output Shim header generating section 1360 ( 1375 in FIG. 12 ). While the label table is being searched, among the information accumulated in the header information accumulating section 1310 , the inner header information extracting section 1340 extracts an EXP value in the input Shim header and a TTL value. The EXP value is outputted to the output Shim header generating section and the TTL value is outputted to the TTL subtraction processing section 1350 ( 1377 in FIG. 12 ). The TTL subtraction processing section subtracts 1 from the TTL value, and transfers the calculation result to the output Shim header generating section 1360 ( 1373 in FIG. 12 ).

Upon receipt of the number of POPs, the number of PUSHes and the output label ( 1375 in FIG. 12 ) from the label table search processing section 1330 , an EXP value from the inner header information extracting section, and a subtraction result of the TTL value from the TTL subtraction processing section, the output Shim header generating section performs the output Shim header generating processing. At this point, as a label value, the label value received from the label table search processing section is used. As EXP values of a plurality of output Shim headers, the EXP values in the input Shim header received from the inner header information extracting section 1340 are used. Also, as a TTL value, the value made by subtraction in the TTL subtraction processing section 1350 is used. The output Shim header generating section generates output Shim headers for the number of PUSHes and transmits them to the packet transfer processing section 1200 .

Thus, one embodiment of the routing processing section 1300 has been described.

Now, with reference to FIGS. 10 , 13 and 14 , an example of the operation of the router 1000 when the line has a fault will be described. A line status monitoring section 1600 of each line in FIG. 10 constantly monitors the status of the output line. When the line has a fault, the line status monitoring section 1600 notifies a control section 1700 of the occurrence of the fault. Upon receipt of the notice of the fault, the control section 1700 performs a changing operation of the label table 1320 in the routing processing section 1300 .

For example, the case when the router 1000 is applied to the CR 1 of FIGS. 7 through 9 will be described. The setting of the label table 1320 when the line 1020 - 1 is normal is shown in FIG. 13 . Further, FIG. 14 shows settings of the label table 1320 when the line 1020 - 1 has a fault. Upon detecting that the line 1020 - 1 has a fault, the line status monitoring section 1600 - 1 monitoring the status of the line 1020 - 1 notifies the control section 1700 of the occurrence of the fault. The control section 1700 recognizes that the line 1020 - 1 has the fault, and changes the label table entry, which is using the line 1020 - 1 as a search result, according to the set value of FIGS. 13 to 14 . As for the packet to be processed after the change of the label table, transfer processing is performed according to the set value of FIG. 14 .

So far, the operation of the router 1000 when the line has a fault has been described. In the above paragraphs, a method of changing the label table after reception of the notice of the fault by the control section 1700 has been described.

As another embodiment, with reference to FIGS. 15 through 17 , a high-speed table switching method will be described. FIG. 15 shows a configuration of the routing processing section 1300 to which the present method is applied. In addition to the E 1 ements shown in FIG. 12 , the routing processing section 1300 of FIG. 15 comprises a current/backup determination section 1380 and a line status table 1390 . The line status table 1390 is a table to hold bits indicating whether the line status is normal or faulty with respect to all lines possessed by the router 1000 . FIG. 16 shows a configuration of the line status table 1390 . Shown in FIG. 16 are a line number 1391 and the line status 1392 . The line status is set as “0” when normal and “1” when faulty. FIG. 17 shows a configuration of a label table to which the present method is applied. The label table of FIG. 17 has both the current search result 1323 - 1 and the backup search result 1323 - 2 with respect to a pair of a label and an EXP, which is a search key. The contents of each search result is the same as those shown in FIGS. 13 and 14 .

Now, an operation of the routing processing section 1300 to which the high-speed table switching method is applied will be described. First, among information accumulated in the header information accumulating section 1310 , the label table search processing section 1330 uses information necessary for the label table search as a search key and searches the label table 1320 . As a result of the search, the current search result 1323 - 1 and the backup search result 1323 - 2 corresponding to the search key are obtained. The label table search processing section 1330 outputs these two pairs of search results to the current/backup determination section 1380 . Out of the two pairs of received search results, the current/backup determination section 1380 searches the line status table 1390 using a current output line number and a backup output line number as search keys, and reads out the status of the current output line and the backup output line. As a result, when the current output line is normal, the current search result 1323 - 1 is selected, and necessary information is outputted to the packet transfer processing section 1200 and the output shim header generating section 1360 . The necessary information is the same as the one described in FIG. 12 . When the current output line has a fault and the backup output line is normal, the backup search result 1323 - 2 is selected, and necessary information is outputted to the packet transfer processing section 1200 and the output Shim header generating section 1360 . When both the current output line and the backup output line have faults, an instruction to discard the packet is given to the packet transfer processing section 1200 . Further, copying of the EXP and the TTL subtraction processing are the same as those described in FIG. 12 .

So far, an operation of the routing processing section 1300 to which the high-speed table switching method is applied has been described. As described above, both the current search result and the backup search result are prepared in advance in the label table entry. Further, by having the line status table, when the line has a fault, the control section can switch the table only by rewriting the status of the line number where the line table has a fault. Therefore, time required for changing the table can be reduced.

As has been described above, the router 1000 can copy an EXP value in the input Shim header to EXP values in the output Shim headers for the number of PUSHes. Therefore, by applying the router to a switching point (the CR 1 of FIGS. 7 through 9 ) of the current LSP and the backup LSP, the router in the backup LSP can also guarantee the same communication quality as that of the current LSP.

By applying the router of the present invention to the switching point of the current LSP and the backup LSP, the router in the backup LSP can also guarantee the same communication quality as that of the current LSP. Therefore, even when the line has a fault, the same communication quality as in the normal state can be guaranteed.

The invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The present embodiment is therefore to be considered in all respects as illustrative and not restrictive, the scope of the invention being indicated by the appended claims rather than by the foregoing description and all changes which come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein.