Route designing method

• US 20050154790A1
• Filed: 06/16/2004
• Published: 07/14/2005
• Est. Priority Date: 01/13/2004
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nagata, Akira, Ueno, Hitoshi, Miyazaki, Keiji
• Granted Patent: US 8,185,616 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4675 Dynamic sharing of VLAN information amongst network nodes configuration of the network or of network elements H04L41/08
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• 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/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

To provide a technology of easily conducting a route design for efficiently accommodating user traffic. On the occasion of designing a communication route between user sites in a network management device connecting to a relay node in a network that connects a plurality of user sites to each other through a plurality of relay nodes and links, there is accepted an input of user information containing information about bandwidth of an access link serving as a link for connecting each of the user sites to the relay node, and information showing the relay node connecting to the user site via the access link, topology information of the network for relaying the communications between the user sites is acquired, a communication relay port and a communication non-relay port are obtained based on the user information and the topology information, an upper limit of the communication bandwidth available for the user on the communication relay port is obtained, a route design so that the user sites are connected by a tree-shaped route is performed, and a result of the route design is outputted.

Claims

1. A route designing method of designing a communication route between user sites in a network management device connecting to a relay node in a network that connects a plurality of user sites to each other through a plurality of relay nodes and links,

the method comprising step of:

accepting an input of user information containing information about a bandwidth of an access link serving as a link for connecting each of the user sites to the relay node, and information showing the relay node connecting to the user site via the access link;

acquiring topology information of the network for relaying the communications between the user sites, wherein each of the user sites is a point through which traffic of a user flow into/out of a network;

obtaining a communication relay port and a communication non-relay port on the basis of the user information and the topology information, obtaining an upper limit of a communication bandwidth of the communication relay port, and performing a route design so that the user sites are connected by a tree-shaped route; and

outputting a result of the route design.

2. A route designing method according to claim 1, wherein the route design is performed by allocating the upper limit of the communication bandwidth of an arbitrary port in each of relay nodes existing among the user sites, so as to be equal to or smaller than a sum of upper limits of communication bandwidths of other ports in the node to which the arbitrary port belongs.

3. A route designing method according to claim 1, wherein performing the route design involves obtaining a tree-shaped route with each relay node serving as a root, defining a condition indicating the communication non-relay node, and obtaining a communication route by excluding the relay nodes applicable to the condition from the relay nodes configuring the tree-shaped route.

4. A route designing method according to claim 1, wherein performing the route design involves obtaining a tree-shaped route of which a root is a site accommodation node as the relay node connecting to the user site via the access link, obtaining evaluation values acquired from bands utilizable on the access link connecting each user site to the relay nodes and from the number of relay nodes needed for reaching from each user site with respect to all the relay nodes configuring the tree-shaped route, and obtaining a shortest hop-by-hop route built up by connecting the relay nodes selected based on the evaluation values to each site with a minimum hop count.

5. A route designing method according to claim 2, wherein performing the route design involves obtaining a tree-shaped route with each relay node serving as a root, defining a condition indicating the communication non-relay node, excluding the relay nodes applicable to the condition from the relay nodes configuring the tree-shaped route, and allocating bands so as to minimize a total sum of the bands allocated to the respective links with respect to the tree-shaped route after the exclusion thereof.

6. A route designing method according to claim 2, wherein performing the route design involves obtaining a tree-shaped route of which a root is a site accommodation node as the relay node connecting to the user site via the access link, obtaining evaluation values acquired from bands utilizable on the access link connecting each user site to the relay nodes and from the number of relay nodes needed for reaching from each user site with respect to all the relay nodes configuring the tree-shaped route, obtaining a shortest hop-by-hop route built up by connecting the relay nodes selected based on the evaluation values to each site with a minimum hop count, and allocating communication bands for the shortest hop-by-hop route.

7. A route designing method according to claim 4, wherein information about the tree-shaped route of which a root is the relay node capable of becoming the site accommodation node is previously acquired and stored, and is read out and thus utilized when conducting a route design.

8. A route designing method according to claim 3, wherein the route design is carried out after excluding, from a design object, the relay nodes that have a port count “

1” and

are not the user site accommodation nodes and all the links connected thereto.

9. A route designing method according to claim 3, wherein if the network is managed in a way that divides the network into sub-domains, the route design is carried out after excluding, from the design object, nodes belonging to the sub-domains including none of the relay nodes connecting to the user sites via the access link and also all the links connected thereto.

10. A route designing method according to claim 1, wherein if a different route reachable to the root node with the same relay count from an unspecified relay node is acquired on the occasion of obtaining the tree-shaped route, information about this different route is retained as information belonging to this node.

11. A route designing method according to claim 10, wherein after completing the route design, a result of the route design and the information about the different route are retained.

12. A route designing method according to claim 1, further comprising a step of transmitting, to the respective relay nodes, setting information containing information for specifying a port for relaying the communications between the user sites and information for indicating communication bands with respect to each relay node, and making the relay node set a route.

13. A recording medium recorded with a route designing program, operated on a network management device connecting to a relay node in a network that connects a plurality of user sites to each other through a plurality of relay nodes and links, for designing a communication route between user sites, the program making the network management device execute step of:

accepting an input of user information containing information about a bandwidth of an access link serving as a link for connecting each of the user sites to the relay node, and information showing the relay node connecting to the user site via the access link;

acquiring topology information of the network for relaying the communications between the user sites, wherein each of the user sites is a point through which traffic of a user flow into/out of a network;

obtaining a communication relay port and a communication non-relay port on the basis of the user information and the topology information, obtaining an upper limit of a communication bandwidth of the communication relay port, and performing a route design so that the user sites are connected by a tree-shaped route; and

outputting a result of the route design.

14. A network management device connecting to a relay node in a network that connects a plurality of user sites to each other through a plurality of relay nodes and links, comprising:

an input unit accepting an input of user information containing information about a bandwidth of an access link serving as a link for connecting each of the user sites to the relay node, and information showing the relay node connecting to the user site via the access link;

a topology acquiring unit acquiring topology information of the network for relaying the communications between the user sites, wherein each of the user sites is a point through which traffic of a user flow into/out of a network;

a route designing unit obtaining a communication relay port and a communication non-relay port on the basis of the user information and the topology information, obtaining an upper limit of a communication bandwidth of the communication relay port, and performing a route design so that the user sites are connected by a tree-shaped route; and

a route output unit outputting a result of the route design.

15. A network management device according to claim 14, wherein the route designing unit allocates the upper limit of the communication bandwidth of an arbitrary port in each of relay nodes existing among the user sites, so as to be equal to or smaller than a sum of upper limits of communication bandwidths of other ports in the node to which the arbitrary port belongs.

16. A network management device according to claim 14, wherein the route designing unit obtains a tree-shaped route with each relay node serving as a root, defines a condition indicating the communication non-relay node, and obtains a communication route by excluding the relay nodes applicable to the condition from the relay nodes configuring the tree-shaped route.

17. A network management device according to claim 14, wherein the route designing unit obtains a tree-shaped route of which a root is a site accommodation node as the relay node connecting to the user site via the access link, obtains evaluation values acquired from bands utilizable on the access link connecting each user site to the relay nodes and from the number of relay nodes needed for reaching from each user site with respect to all the relay nodes configuring the tree-shaped route, and obtains a shortest hop-by-hop route built up by connecting the relay nodes selected based on the evaluation values to each site with a minimum hop count.

18. A network management device according to claim 15, wherein the route designing unit obtains a tree-shaped route with each relay node serving as a root, defines a condition indicating the communication non-relay node, excludes the relay nodes applicable to the condition from the relay nodes configuring the tree-shaped route, and allocates bands so as to minimize a total sum of the bands allocated to the respective links with respect to the tree-shaped route after the exclusion thereof.

19. A network management device according to claim 15, wherein the route designing unit obtains a tree-shaped route of which a root is a site accommodation node as the relay node connecting to the user site via the access link, obtains evaluation values acquired from bands utilizable on the access link connecting each user site to the relay nodes and from the number of relay nodes needed for reaching from each user site with respect to all the relay nodes configuring the tree-shaped route, obtains a shortest hop-by-hop route built up by connecting the relay nodes selected based on the evaluation values to each site with a minimum hop count, and allocates communication bands for the shortest hop-by-hop route.

20. A network management device according to claim 17, wherein the route designing unit previously obtains and stores information about the tree-shaped route of which a root is the relay node capable of becoming the site accommodation node, and reads and thus utilizes the information about the tree-shaped route when conducting a route design.

21. A network management device according to claim 16 wherein the route designing unit carries out the route design after excluding, from a design object, the relay nodes that have a port count “

1” and

are not the user site accommodation nodes and all the links connected thereto.

22. A network management device according to claim 16, wherein the route designing unit, if the network is managed in a way that divides the network into sub-domains, carries out the route design after excluding, from the design object, nodes belonging to the sub-domains including none of the relay nodes connecting to the user sites via the access link and also all the links connected thereto.

23. A network management device according to claim 14, wherein the route designing unit, if a different route reachable to the root node with the same relay count from an unspecified relay node is acquired on the occasion of obtaining the tree-shaped route, retains information about this different route as information belonging to this node.

24. A network management device according to claim 23, wherein the route designing unit, after completing the route design, retains a result of the route design and the information about the different route.

25. A network management device according to claim 14, further comprising a network setting unit transmitting, to the respective relay nodes, setting information containing information for specifying a port for relaying the communications between the user sites and information for indicating communication bands with respect to each relay node, and making the relay node set a route.

26. A network system comprising:

a network for connecting a plurality of user sites to each other through a plurality of relay nodes and links; and

a network management device connecting to the relay node,

the network management device including;

an input unit accepting an input of user information containing information about a bandwidth of an access link serving as a link for connecting each of the user sites to the relay node, and information showing the relay node connecting to the user site via the access link;

a topology acquiring unit acquiring topology information of the network for relaying the communications between the user sites, wherein each of the user sites is a point through which traffic of a user flow into/out of a network;

a route designing unit obtaining a communication relay port and a communication non-relay port on the basis of the user information and the topology information, obtaining an upper limit of a communication bandwidth of the communication relay port, and performing a route design so that the user sites are connected by a tree-shaped route; and

a route output unit outputting a result of the route design,

the relay node including;

an input unit accepting a traffic of the communication;

an output unit outputting the traffic to a next node via the port;

a setting acquisition unit receiving setting information from the network management device; and

a setting unit setting a port of the output unit on the basis of the setting information.

27. A network management method operated in a network system comprising a network for connecting a plurality of user sites to each other through a plurality of relay nodes and links, and a network management device connecting to the relay node,

the network management device executing step of:

accepting an input of user information containing information about a bandwidth of an access link serving as a link for connecting each of the user sites to the relay node, and information showing the relay node connecting to the user site via the access link;

acquiring topology information of the network for relaying the communications between the user sites, wherein each of the user sites is a point through which traffic of a user flow into/out of a network;

obtaining a communication relay port and a communication non-relay port on the basis of the user information and the topology information, obtaining an upper limit of a communication bandwidth of the communication relay port, and performing a route design so that the user sites are connected by a tree-shaped route; and

outputting a result of the route design,

the relay node executing step of;

receiving setting information from the network management device; and

setting a port of the output unit on the basis of the setting information.