Inter-domain routing technique using MPLS

• US 7,570,638 B2
• Filed: 11/28/2005
• Issued: 08/04/2009
• Est. Priority Date: 05/18/2005
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shimizu, Takao, Kitade, Michio, Iitsuka, Kazuhiro, Matsukawa, Norikazu, Takahashi, Naoyuki
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): Kamara; Mohamed
• Application Number:
  US11/287,338
• Publication Number:
  US 20060262786A1
• Time in Patent Office: 1,345 Days
• Field of Search: 370/349, 370/447, 370/235, 370/351, 370/395.2, 709/238, 709/223, 455/12.1
• US Class Current: 370/389
• 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/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

This invention is to enable inter-domain routing using MPLS. When communication is carried out passing through plural domains, respective management servers managing respective domains cooperate to carry out path constitution and optimum routing. At the path constitution, the respective management servers connect links within the respective controlling domain to constitute paths to reach a target address. When the paths are constituted, label data is notified to nodes associated with the constituted paths, and is used at the routing. At the routing, the management server controlling the source domain obtains the dynamic transmission bandwidths from the respective management servers, and identifies the routing policy from a port number of a request to be routed or the like to identify the optimum path. When the optimum path is determined, it is possible to carry out the routing using the label data held in the respective nodes.

Claims

1. An information processing method executed by a management server that manages paths between arbitrary nodes in a specific domain, comprising:

detecting an event in which a path is constituted between a source address associated with said specific domain and a destination address associated with a second domain different from said specific domain;

constituting a plurality of paths between a first node associated with said source address and a second node associated with said second domain and included in said specific domain;

identifying, as registered paths, a number of paths based on bandwidth information of said plurality of paths;

storing said source address, said destination address and data concerning said registered path for each said registered path into a path data storage;

transmitting, to a management server in a third domain connected to said second node, a constitution request including said source address and said destination address, and including, for each said registered path, data concerning bandwidth of said registered path and data concerning said second node;

receiving constitution information including said source address and said destination address, and including, for each said registered path, data concerning a connection link between said second node and a connection node on the third domain side from said management server in said third domain;

storing said data concerning said connection link into said path data storage, in association with a combination of said source address, said destination address, and said data concerning said registered path; and

carrying out setting for routing to nodes associated with said registered path in said specific domain by using data stored in said path data storage.

2. The information processing method as set forth in claim 1, further comprising:

receiving a second constitution request including a source address and a destination address, which are associated with a domain different from said specific domain, and including, for each candidate path, data concerning bandwidth of said candidate path and data concerning a last relay node in a fourth domain from a management server of said fourth domain;

constituting a plurality of paths between said last relay node and a third node associated with a fifth domain, which is associated with said destination address included in said second constitution request, in said specific domain;

identifying, as second registered paths in said specific domain, a second number of paths whose total bandwidth in which said bandwidth of said candidate path is taken into account is ranked within the top among said plurality of paths;

storing said source address and said destination address, which are included in said second constitution request, and data concerning said second registered path in said specific domain into said path data storage;

transmitting a third constitution request including said source address and said destination address, which are included in the received second constitution request, and including, for each said identified second registered path, data concerning said total bandwidth of said second registered path and data concerning said third node, to a management server of a sixth domain connected with said third node;

receiving, from said management server of said sixth domain, second constitution information including said source address and said destination address, which are included in the received second constitution request, and including, for each said second registered path in the transmitted third constitution request, data concerning a connection link between said third node and a connection node of the sixth domain side;

storing said data concerning said connection link, which is included in the received second constitution information, into said path data storage in association with a combination of said source address and said destination address, which are included in said second constitution information, and said second registered path;

carrying out setting for routing to said nodes within said specific domain, which are associated with said second registered path, by using data stored in said path data storage; and

transmitting, to said management server in said fourth domain, third constitution information including said source address and said destination address, which are included in said second constitution information, and including, for each said second registered path, data concerning a connection link between said last relay node in said fourth domain and a connection node in said specific domain.

3. The information processing method as set forth in claim 1, further comprising:

receiving a fourth constitution request including a destination address associated with said specific domain and a source address associated with a eighth domain other than said specific domain, and including, for each candidate path, data concerning bandwidth of said candidate path and data of a last relay node in a seventh domain, from a management server in said seventh domain;

constituting a plurality of paths between said last relay node and a node associated with said destination address, which is included in said fourth constitution request, in said specific domain;

identifying, as third registered paths in said specific domain, a third number of paths whose total bandwidth in which said bandwidth of said candidate path is taken into account is ranked within the top among said plurality of paths;

storing said source address and said destination address, which are included in said fourth constitution request, and data concerning said third registered path in said specific domain into said path data storage;

carrying out setting for routing to said nodes within said specific domain, which are associated with said third registered path, by using data stored in said path data storage; and

transmitting, to said management server in said seventh domain, fourth constitution information including said source address and said destination address, which are included in said fourth constitution request, and including, for each said third registered path, data concerning a connection link between said last relay node in said seventh domain and a connection node in said specific domain.

4. The information processing method as set forth in claim 1, wherein a label unique in each domain is assigned to a head link included in a path,

a link of a portion connected with another domain is identified by identification information of a domain to which said link belongs and a label in said domain, and

said data concerning said registered path includes labels of links included in said registered path.

5. The information processing method as set forth in claim 1, wherein a label unique in a plurality of domains is assigned to a head link included in a path, and said data concerning said registered path includes labels of links included in said registered path.

6. The information processing method as set forth in claim 1, wherein a label in a belonging domain is assigned to each link included in a path,

a link of a portion connected with another domain is identified by identification information of a domain to which said link belongs and a label in said domain,

an identical label is assigned to a shared link shared by a plurality of paths,

said path data storage stores labels of respective links included in said specific domain and in said registered path in association with data to identify a link branch direction in a reverse direction of said registered path, for said shared link included in said respective links, which are included in said specific domain and in said registered path, and

said carrying out includes registering, as routing data, data to identify, from a specific label, a next link in said registered path including a link corresponding said specific label, and data including, for said shared link in said registered path, data to identify a branch direction at a reverse direction routing in said specific domain, which is other than a domain associated with a source address of said registered path, and data to identify whole of said registered path.

7. The information processing method as set forth in claim 1, wherein the identifying identifies, as registered paths, the number of paths whose bandwidth is ranked within the top among said plurality of paths.

8. The information processing method as set forth in claim 1, wherein said third domain is an adjacent domain of said specific domain.

9. An information processing method executed by a management server in a source side domain of inter-domain communication, comprising:

receiving a path setting request including data concerning a source of a packet and data concerning a destination of said packet;

referring to a path data storage storing data of a candidate path in association with a source address and a destination address, to identify candidate paths relating to said path setting request;

identifying a routing policy of said packet based on said data concerning said destination of said path setting request;

requesting a management server of another associated domain on the identified candidate path to transmit data concerning a dynamic transmission bandwidth of said identified candidate path in said another associated domain;

receiving said data concerning said dynamic transmission bandwidth of said identified candidate path in said another associated domain from said management server of said another associated domain on said identified candidate path;

calculating total dynamic transmission bandwidth of the entire identified candidate path based on data concerning dynamic transmission bandwidth of said identified candidate path in said source domain and the received data concerning said dynamic transmission bandwidth of said identified candidate path in said another associated domain, and storing data of the calculated total dynamic transmission bandwidth into a storage;

determining an optimum path from the identified candidate paths based on said routing policy and said calculated total dynamic transmission bandwidths of said entire candidate paths, which are stored in the storage; and

transmitting data to identify said optimum path to a requesting source of said path setting request.

10. The information processing method as set forth in claim 9, wherein said determining includes determining, for said identified routing policy that is an asymmetric routing in uplink and downlink, a path whose value of said dynamic transmission bandwidth in uplink is largest and a path whose value of said dynamic transmission bandwidth in downlink is largest from said identified candidate paths.

11. The information processing method as set forth in claim 9, wherein said determining includes determining, for said routing policy that is a symmetric routing in which it is presumed that difference between traffic amounts in uplink and in downlink or ratio thereof is within a range, a path whose values of said dynamic transmission bandwidths in uplink and in downlink satisfy a condition from said identified candidate paths.

12. The information processing method as set forth in claim 9, wherein said determining comprises determining, for said routing policy that is a symmetric routing in which it is presumed that difference between traffic amounts in uplink and in downlink or ratio thereof is out of a range, a path whose value of said dynamic transmission bandwidth in a direction whose traffic amount is presumed to be larger is the largest from said identified candidate paths.

13. A computer-readable storage medium storing executable instructions that, when executed by a management server that manages paths between arbitrary nodes in a specific domain, cause the management server to perform a method comprising:

detecting an event in which a path is constituted between a source address associated with said specific domain and a destination address associated with a second domain different from said specific domain;

constituting a plurality of paths between a first node associated with said source address and a second node associated with said second domain and included in said specific domain;

identifying, as registered paths, a number of paths whose bandwidth is ranked within the top among said plurality of paths;

storing said source address, said destination address and data concerning said registered path for each said registered path into a path data storage;

transmitting, to a management server in a third domain connected to said second node, a constitution request including said source address and said destination address, and including, for each said registered path, data concerning bandwidth of said registered path and data concerning said second node, wherein said third domain is an adjacent domain of said specific domain;

receiving constitution information including said source address and said destination address, and including, for each said registered path, data concerning a connection link between said second node and a connection node on the third domain side from said management server in said third domain;

storing said data concerning said connection link into said path data storage, in association with a combination of said source address, said destination address, and said registered path; and

carrying out setting for routing to nodes associated with said registered path in said specific domain by using data stored in said path data storage.

14. A computer-readable storage medium storing executable instructions that, when executed by a management server in a source side domain of inter-domain communication, cause the management server to perform a method comprising:

receiving a path setting request including data concerning a source of a packet and data concerning a destination of said packet;

referring to a path data storage storing data of a candidate path in association with a source address and a destination address, to identify candidate paths relating to said path setting request;

identifying a routing policy of said packet based on said data concerning said destination of said path setting request;

requesting a management server of another associated domain on the identified candidate path to transmit data concerning a dynamic transmission bandwidth of said identified candidate path in said another associated domain;

receiving said data concerning said dynamic transmission bandwidth of said identified candidate path in said another associated domain from said management server of said another associated domain on said identified candidate path;

calculating total dynamic transmission bandwidth of the entire identified candidate path based on data concerning dynamic transmission bandwidth of said identified candidate path in said source domain and the received data concerning said dynamic transmission bandwidth of said identified candidate path in said another associated domain, and storing data of the calculated total dynamic transmission bandwidth into a storage;

determining an optimum path from the identified candidate paths based on said routing policy and said calculated total dynamic transmission bandwidths of said entire candidate paths, which are stored in the storage; and

transmitting data to identify said optimum path to a requesting source of said path setting request.

15. A management server for managing paths between arbitrary nodes in a specific domain, comprising:

a unit that detects an event in which a path is constituted between a source address associated with said specific domain and a destination address associated with a second domain different from said specific domain;

a unit that constitutes a plurality of paths between a first node associated with said source address and a second node associated with said second domain and included in said specific domain, identifies, as registered paths, a number of paths whose bandwidth is ranked within the top among said plurality of paths, and stores said source address, said destination address and data concerning said registered path for each said registered path into a path data storage;

a unit that transmits, to a management server in a third domain connected to said second node, a constitution request including said source address and said destination address, and including, for each said registered path, data concerning bandwidth of said registered path and data concerning said second node, wherein said third domain is an adjacent domain of said specific domain;

a unit that receives constitution information including said source address and said destination address, and including, for each said registered path, data concerning a connection link between said second node and a connection node on the third domain side from said management server in said third domain, and stores said data concerning said connection link into said path data storage, in association with a combination of said source address, said destination address, and said registered path; and

a unit that carries out setting for routing to nodes associated with said registered path in said specific domain by using data stored in said path data storage.

16. A management server in a source side domain of inter-domain communication, comprising:

a unit that receives a path setting request including data concerning a source of a packet and data concerning a destination of said packet;

a unit that refers to a path data storage storing data of a candidate path in association with a source address and a destination address, to identify candidate paths relating to said path setting request;

a unit that identifies a routing policy of said packet based on said data concerning said destination of said path setting request;

a unit that requests a management server of another associated domain on the identified candidate path to transmit data concerning a dynamic transmission bandwidth of said identified candidate path in said another associated domain;

a unit that receives said data concerning said dynamic transmission bandwidth of said identified candidate path in said another associated domain from said management server of said another associated domain on said identified candidate path;

a unit that calculates total dynamic transmission bandwidth of the entire identified candidate path based on data concerning dynamic transmission bandwidth of said identified candidate path in said source domain and the received data concerning said dynamic transmission bandwidth of said identified candidate path in said another associated domain, and stores data of the calculated total dynamic transmission bandwidth into a storage;

a unit that determines an optimum path from the identified candidate paths based on said routing policy and said calculated total dynamic transmission bandwidths of said entire candidate paths, which are stored in the storage; and

a unit that transmits data to identify said optimum path to a requesting source of said path setting request.

17. A router for carrying out routing according to an instruction from a management server for managing paths between arbitrary nodes in a specific domain, comprising:

a data storage to store a pair of labels assigned to an input link and an output link that are directly connected to said router among links included in paths passing through said router, and relationships between labels and links; and

a routing unit that refers to said data storage to identify a link and an output label corresponding to an input label included in a received packet and carries out routing on said received packet, and

wherein an identical label is assigned to a shared link shared with a plurality of paths,

said data storage further stores data to identify a branch direction at a reverse routing and data to identify the entire path in association with said pair of labels, and

said routing unit refers to said data storage to identify a link and an output label corresponding to a combination of an input label, data to identify a branch direction at a reverse routing and data to identify the entire path, which are included in a received second packet being backwardly routed between domains and carries out routing on said received second packet.