Method and apparatus for composing virtual links in a label switched network

• US 20030137978A1
• Filed: 01/18/2002
• Published: 07/24/2003
• Est. Priority Date: 01/18/2002
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Kanetake, Tatsuo
• Granted Patent: US 7,212,526 B2
• Time in Patent Office: Days
• US Class Current: 370/386
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A method for managing virtual links within a multiple protocol label switched network is provided. According to one aspect of the method, a virtual link which is made up of a set of links between two devices within the multiple protocol label switched network is regarded as a single entity by a control component of a label switching router. Each packet to be transported on the virtual link is labeled based on its assigned forwarding equivalence class. A specific label is bound to a corresponding forwarding equivalence class. The specific label are used on packets belonging to the same forwarding equivalence class and such packets can then be forwarded onto any one of the links within the virtual link. Furthermore, according to another exemplary aspect of the method, each forwarding equivalence class can be mapped to one of the links within an outgoing virtual link without changing the output label. This mapping is performed using a selected hash function. The selected hash function is used to map the labels to integers to get a distribution on a smaller set of links in the virtual link. In addition, according to a further exemplary aspect of the method, packets with different labels are apportioned among links within the virtual link. Packets with the same label (hence the same forwarding equivalence class) are forwarded onto the same link within the virtual link. In order to load balance the various links within the virtual link, different selected hash functions can be used at selected times to apportion the packets depending on the load conditions. Finally, according to yet another exemplary aspect of the method, respective hash functions used at the sending and receiving label switching routers are synchronized. By synchronizing the hash functions, the number of entries in the load forwarding tables are reduced thereby reducing search time and memory storage requirements.

Claims

1. A system for managing multiple links in a label switched network, comprising:

a plurality of virtual links including a plurality of input virtual links and a plurality of output virtual links, each input or output virtual link having a plurality of individual links;

a plurality of ingress nodes, each ingress node configured to receive packets and label the packets with associated labels;

a plurality of label switching nodes, each label switching node configured to receive the labeled packets having respective associated labels via one or more input virtual links and forward the received labeled packets based on their respective associated labels via one or more output virtual links, each label switching node further including a control component configured to maintain label information relating to the associated labels and a forwarding component configured to perform forwarding of the received labeled packets based on the label information;

a plurality of egress nodes, each egress node configured to receive the labeled packets forwarded from one of the plurality of label switching nodes;

wherein one or more label switching nodes are identified as belonging to a label switched path and virtual links are used to interconnect the identified label switching nodes as belonging to the label switched path; and

wherein the plurality of individual links within each of the virtual links used to interconnect the identified label switching nodes are collectively regarded as a single entity by the control component with respect to the label switched path.

2. The system of claim 1 wherein details with respect to which ones of the individual links within an output virtual link are to be used to forward the received packets are concealed from the control component.

3. The system of claim 1 wherein at least one of the labeled packets is capable of being forwarded to any one of the plurality of individual links within an output virtual link without changing its associated label that is established in an initial signaling process.

4. The system of claim 1 wherein the associated label is composed of any one of the following entities or combination thereof including a single sequence of bits of fixed length, time slot position in a TDM frame and wavelength of optical carrier.

5. The system of claim 1 wherein each associated label belongs to one of a plurality of classes;

and

wherein the associated labels are used by a label switching node to forward packets belonging to a corresponding class onto one of the plurality of individual links of an output virtual link.

6. The system of claim 5 wherein the label switched network is a multiple protocol label switched network and the corresponding class is a forwarding equivalence class.

7. The system of claim 5 wherein a first hash function is used to operate on an associated label of a packet to be forwarded via an output virtual link to obtain a hash value, the hash value representing one of the plurality of individual links within the output virtual link that is to be used to forward the packet.

8. The system of claim 7 wherein by using the first hash function to operate on the associated label of the packet, the packet is capable of being forwarded to one of the plurality of individual links within the output virtual link without changing its associated label.

9. The system of claim 5 wherein one of a plurality of hash functions is used to operate on respective associated labels of packets to be forwarded via an output virtual link to obtain corresponding hash values;

wherein the respective associated labels correspond to one or more classes; and

wherein the corresponding hash values represent one or more of the plurality of individual links within the output virtual link that are to be used to respectively forward the packets.

10. The system of claim 9 wherein by using one of the plurality of hash functions to operate on the respective labels, the packets associated with the respective associated labels are apportioned among the plurality of individual links within the output virtual link.

11. The system of claim 9 wherein which one of the plurality of hash functions is used to operate on the respective associated labels depends on one or more load balancing conditions.

12. The system of claim 7 further comprising:

a plurality of label forwarding tables, each label forwarding table having a plurality of entries, each entry including an input virtual port number, an input label, an output label and an output virtual port number; and

wherein the input virtual port number represents identification information relating to an input virtual link through which an input packet is received, the input label represents label information relating to the input packet, the output label represents label information relating to an output packet and the output virtual port number represents identification information relating to an output virtual link through which the output packet is to be forwarded.

13. The system of claim 12 wherein each label forwarding table is associated with one of the plurality of individual links within an input virtual link.

14. The system of claim 12 wherein a first label switching node forwards a packet to a second label switching node via an individual link within a virtual link coupling the first label switching node and the second label switching node;

wherein the first label switching node uses the first hash function to operate on the associated label of the forwarded packet to obtain its corresponding hash value, the corresponding hash value representing the individual link within the virtual link;

wherein for a label forwarding table associated with the individual link within the virtual link at the second label switching node, an entry is tagged if a hash value of the input label for that entry is equal to an input practical port number which corresponds to the individual link within the virtual link;

wherein the second label switching node uses a second hash function to obtain the hash value of the input label for that entry;

wherein the first hash function and the second hash function are synchronized.

15. The system of claim 14 wherein the label forwarding table associated with the individual link within the virtual link at the second label switching node is modified to include only tagged entries.

16. The system of claim 14 wherein when a packet is received via the individual link within the virtual link at the second label switching node, only the tagged entries within the label forwarding table associated with the individual link within the virtual link at the second label switching node are searched for an entry corresponding to the received packet.

17. A system for setting label switched paths in a label switched network, comprising:

a plurality of links; and

a plurality of nodes interconnected to each other via the plurality of links;

wherein a label switched path is identified for transmitting packets through the label switched network and is made up of one or more links interconnecting one or more nodes;

wherein the one or more links within the label switched path include one or more virtual links; and

wherein each of the one or more virtual links is made up of one or more physical links.

18. The system of claim 17 wherein each node in the label switched path is configured to receive packets having respective labels via one or more links connected thereto and forward the received packets based on their respective labels via one or more links connected thereto;

wherein each node in the label switched path includes a control component configured to maintain label information relating to the labels and a forwarding component configured to perform forwarding of the received packets based on the label information; and

wherein for a node in the label switched path, if the link to be used to forward a received packet is a virtual link, the received packet is capable of being forwarded to any one of the one or more physical links within the virtual link without changing its label that is established in an initial signaling process.

19. The system of claim 17 wherein the label associated with a packet is composed of any one of the following entities or combination thereof including a single sequence of bits of fixed length, time slot position in a TDM frame and wavelength of optical carrier.

20. The system of claim 18 wherein the node in the label switched path further includes control logic configured to select one of one or more hash functions to be used to operate on respective labels of received packets to be forwarded via the virtual link to obtain corresponding hash values;

and

wherein the corresponding hash values represent one or more of physical links within the virtual link that are to be used to forward the received packets.

21. The system of claim 18 wherein the node in the label switched path further comprises:

a plurality of label forwarding tables, each label forwarding table having a plurality of entries, each entry including an input virtual port number, an input label, an output label and an output virtual port number; and

wherein the input virtual port number represents identification information relating to a virtual link used to receive the packets, the input label represents label information relating to a received packet, the output label represents label information relating to the received packet to be forwarded and the output virtual port number represents identification information relating to a virtual link used to forward the received packet.22.A label switching router for use in a multiple protocol label switched network, comprising;

a plurality of virtual links including a plurality of input virtual links and a plurality of output virtual links, each input or output virtual link having a plurality of individual links;

a control component configured to maintain label information relating to labels carried by packets received via one or more of the input virtual links;

a forwarding component configured to perform forwarding of the received packets based on the label information via one or more of the plurality of output virtual links; and

at least one label forwarding table for storing the label information, the at least one label forwarding table having a plurality of entries, each entry having an input virtual port number, an input label, an output label and an output virtual port number;

wherein the label switching router is identified as part of a label switched path for routing packets; and

wherein with respect to the label switched path, the control component is capable of treating either the plurality of individual links within each input virtual link or the plurality of individual links within each output virtual link or both as a single entity.

23. The label switching router of claim 22 wherein the control component is not concerned with details with respect to which ones of the individual links within the output virtual link are to be used to forward the received packets.

24. The label switching router of claim 22 wherein at least one of the packets is capable of being forwarded to any one of the plurality of individual links within an output virtual link without changing its associated label that is established in an initial signaling process.

25. The label switching router of claim 22 wherein a received packet has an associated input label, the associated input label corresponding to a forwarding equivalence class and an associated output label;

wherein the label switching router uses the associated input label and an input virtual port number associated with the received packet as keys to look up in the at least one label forwarding table the associated output label and an output virtual port number corresponding to an output virtual link through which the received packet is to be forwarded; and

wherein a first hash function is used to operate on the associated output label to obtain a hash value, the hash value representing an output practical port number corresponding to one of the plurality of individual links within the output virtual link through which the received packet is to be forwarded.

26. The label switching router of claim 25 wherein a second hash function is alternately used to operate on the associated output label to obtain a second hash value, the second hash value representing a second one of the plurality of individual links within the output virtual link through which the received packet is to be forwarded;

and

wherein by alternately using the first and second hash functions, different ones of the plurality of individual links within the output virtual link through which the received packet is to be forwarded are capable of being selected without changing the associated output label.

27. The label switching router of claim 26 wherein by alternately using the first and second hash functions, load balancing for the plurality of individual links within the output virtual link through which the received packet is to be forwarded is achieved.

28. The label switching router of claim 25 wherein for each entry in the at least one label forwarding table, if a hash value of the input label associated with that entry is equal to a predetermined input practical port number, that entry is tagged;

wherein the hash value of the input label associated with that entry is obtained by using a second hash function; and

wherein the first and second hash functions are synchronized.

29. The label switching router of claim 28 wherein all the tagged entries are copied and stored into an additional label forwarding table;

and

wherein the additional label forwarding table is associated with the predetermined input practical port number corresponding to an individual link within an input virtual link.

30. The label switching router of claim 28 wherein when a packet is received via an individual link within an input virtual link having the predetermined input practical port number, only tagged entries are searched with respect to the received packet.

31. A method for managing virtual links in a label switched network, comprising:

grouping a plurality of individual links into a plurality of virtual links, each virtual link having one or more individual links, and the plurality of virtual links including a plurality of input virtual links and a plurality of output virtual links;

maintaining a plurality of ingress routers, wherein each ingress router is configured to receive packets and label the packets with associated labels;

maintaining a plurality of label switching routers within the label switched network, wherein each label switching router is configured to receive the labeled packets having respective labels from one of the plurality of ingress routers via one or more input virtual links and forward the received labeled packets via one or more output virtual links, each label switching router further includes a control component configured to maintain label information relating to the labels and a forwarding component configured to perform forwarding of the received labeled packets based on the label information;

maintaining a plurality of egress routers, wherein each egress router is configured to receive the labeled packets forwarded by one of the plurality of label switching routers;

establishing a label switched path having one or more label switching routers for routing the labeled packets, wherein one or more virtual links are used to interconnect the label switching routers along the label switched path and the label switching routers along the label switched path communicate with one another via their respective control components to exchange label information to establish the label switched path; and

treating the one or more individual links within each of the one or more virtual links being used to interconnect the label switching routers along the label switched path collectively as a single entity with respect to the label switched path, wherein the exchanged label information does not include details relating to which ones of the individual links within a virtual link are to be used to forward packets.

32. The method of claim 31 further comprising:

maintaining a label forwarding table at each label switching router;

wherein the label forwarding table includes a plurality of entries, each entry including an input virtual port number, an input label, an output label and an output virtual port number.

33. The method of claim 32 wherein a plurality of labels uniquely correspond to a plurality of classes.

34. The method of claim 33 wherein the label switched network is a multiple protocol label switched network and the plurality of class is a plurality of forwarding equivalence classes.

35. The method of claim 33 further comprising:

for a packet received via an input virtual link;

using an input virtual port number corresponding to the input virtual link and the label of the received packet to look up an output label and an output virtual port number for the received packet in the label forwarding table, the output virtual port number corresponding to an output virtual link through which the received packet is to be forwarded; and

using a first hash function to operate on the output label for the received packet to obtain a hash value, the hash value representing an output practical port number corresponding to an individual link within the output virtual link through which the received packet is to be forwarded.

36. The method of claim 35 wherein by using the first hash function to operate on the output label for the received packet, the received packet is capable of being forwarded to one of the individual links within the output virtual link through which the received packet is to be forwarded without changing the output label.

37. The method of claim 35 further comprising:

for the packet received via the input virtual link;

selecting one of a plurality of hash functions to operate on the output label for the received packet to obtain a hash value, the hash value representing an output practical port number corresponding to an individual link within the output virtual link through which the received packet is to be forwarded;

wherein by having the plurality of hash functions, load balancing among the individual links within the output virtual link through which the received packet is to be forwarded is achieved.

38. The method of claim 35 further comprising:

for each entry in the label forwarding table, tagging that entry if a hash value of the input label associated with that entry is equal to a predetermined input practical port number;

wherein the hash value of the input label associated with that entry is obtained by using a second hash function; and

wherein the first and second hash functions are synchronized.

39. The method of claim 38 further comprising:

copying all the tagged entries in the label forwarding table into an additional label forwarding table; and

associating the additional label forwarding table with the predetermined input practical port number corresponding to an individual link within an input virtual link.

40. The method of claim 38 further comprising:

when a packet is received via an individual link within an input virtual link having the predetermined input practical port number, searching only the tagged entries with respect to the received packet.