Communications network with routing tables for establishing a path without failure by avoiding unreachable nodes

• US 20030016678A1
• Filed: 07/18/2002
• Published: 01/23/2003
• Est. Priority Date: 07/19/2001
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Maeno, Yoshiharu
• Granted Patent: US 7,397,802 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/62 Wavelength based optical switching H04Q11/0062

Abstract

In a communications network where cross-connect nodes are organized according to geographic domains, a domain connectivity table indicates intra-domain connectivity of each domain and a domain routing table indicates a route specifying those nodes whose intra-domain connectivity is indicated in the domain connectivity table. Each node uses its domain routing table to establish a path between edge nodes. In another embodiment, the domain routing table indicates routes containing no intra-domain virtual link that terminates at an edge node and no consecutively concatenated intra-domain virtual links. A backbone routing table indicates inter-domain routes and unreachability indications between border nodes of each domain and border nodes of every other domain. The inter-domain routes contain at least one of the inter-domain physical links but contain no consecutively concatenated intra-domain virtual links.

Claims

1. A communications network comprising:

a plurality of network nodes interconnected by communication links, said network nodes being organized into a plurality of groups corresponding to geographic domains, ones of said network nodes located at periphery of the network functioning as edge nodes to which user terminals are connected;

a plurality of domain connectivity tables respectively associated with said domains, each of the domain connectivity tables indicating intra-domain connectivity of the associated domain; and

a plurality of domain routing tables respectively associated with said domains, each of the domain routing tables indicating a route specifying ones of said network nodes whose intra-domain connectivity is indicated in the domain connectivity table of the associated domain,

said network nodes using said plurality of routing tables for establishing a path between said edge nodes in response to a path setup request from said user terminals.

2. The communications network of claim 1, wherein the network nodes of each domain advertise contents of the domain routing table of the domain to the network nodes of a downstream neighbor domain and create the domain routing table of the domain in accordance with advertised contents of the domain routing table of an upstream neighbor domain.

3. The communications network of claim 2, wherein the network nodes of each of said domains update the domain routing table of the domain in accordance with the advertised contents of the domain routing table of said upstream neighbor domain.

4. The communications network of claim 1, wherein each of said network nodes comprises an optical cross-connect system for establishing transparent optical connections between neighboring network nodes.

5. The communications network of claim 1, wherein ones of said network nodes located at border points between neighbor domains of said plurality of domains function as border nodes, further comprising:

a plurality of inter-domain connectivity tables respectively associated with said domains, each of the inter-domain connectivity tables indicating inter-domain connectivity between the network nodes of the associated domain and the border nodes of a neighbor domain,

each of said domain routing tables indicating a route specifying ones of said network nodes whose inter-domain connectivity is indicated in the inter-domain connectivity table of the associated domain,

each of said network nodes additionally using the inter-domain connectivity table of the associated domain when creating the domain routing table of the associated domain.

6. The communications network of claim 1, wherein each of said domain connectivity tables and each of said routing tables are provided in each of the network nodes.

7. The communications network of claim 1, wherein each of said border connectivity tables is provided in each of the network nodes.

8. The communications network of claim 1, wherein the network nodes of each of said domains are arranged to:

determine whether the routing table of the domain includes a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through the associated domain, and

select one of said parallel routes having a smallest number of transit domains and discard said parallel routes other than the selected route from the routing table.

9. A cross-connect node for a communications network in which said node is one of a plurality of network nodes, said network nodes being organized into a plurality of groups corresponding to geographic domains, ones of said network nodes located at periphery of the network functioning as edge nodes to which user terminals are connected, comprising:

a domain connectivity table for indicating intra-domain connectivity of the domain of said cross-connect node;

a domain routing table for indicating a route specifying ones of said network nodes whose intra-domain connectivity is indicated in said domain connectivity table; and

a processor for using said domain routing table for establishing a path between said edge nodes in response to a path setup request from said user terminals.

10. The cross-connect node of claim 9, wherein said processor advertises contents of the domain routing table to the network nodes of a downstream neighbor domain and creates the routing table in accordance with advertised contents of the routing table of an upstream neighbor domain.

11. The cross-connect node of claim 10, wherein said processor updates the domain routing table in accordance with the advertised contents of the domain routing table of said upstream neighbor domain.

12. The cross-connect node of claim 9, further comprising an optical cross-connect system for establishing transparent optical connections between neighboring network nodes.

13. The cross-connect node of claim 9, wherein ones of said network nodes located at border points between neighbor domains of said plurality of domains function as border nodes, further comprising:

an inter-domain connectivity table for indicating inter-domain connectivity between the network nodes of the associated domain and the border nodes of a neighbor domain,

said domain routing table indicating a route specifying ones of said network nodes whose inter-domain connectivity is indicated in the inter-domain connectivity table,

said processor using the inter-domain connectivity table when creating said domain routing table.

14. The cross-connect node of claim 9, wherein said processor is arranged to:

determine whether said routing table includes a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through the associated domain, and

select one of said parallel routes having a smallest number of transit domains and discard said parallel routes other than the selected route from the routing table.

16. The method of claim 15, wherein ones of said network nodes located at border points between neighbor domains of said plurality of domains function as border nodes, further comprising steps of:

creating an inter-domain connectivity table for indicating inter-domain connectivity between the network nodes of the associated domain and the border nodes of a neighbor domain; and

updating said domain routing table for indicating that said route specifies ones of said network nodes whose inter-domain connectivity is indicated in the inter-domain connectivity table.

17. The method of claim 15, further comprising steps of:

determining whether the domain routing table contains a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through the associated domain, and

selecting one of said parallel routes having a smallest number of transit domains; and

discarding said parallel routes other than the selected route from the routing table.

19. The communications network of claim 18, further comprising a border connectivity table for indicating intra-domain connectivity of said border nodes within each of said domains,

said network nodes additionally using said border connectivity table for establishing said path.

20. The communications network of claim 18, wherein each of said network nodes comprises an optical cross-connect system for establishing transparent optical connections between neighboring network nodes.

21. The communications network of claim 18, wherein said network nodes are responsive to a failure in establishing said path for using said domain routing tables and said backbone routing table again and reestablishing a path between said edge nodes by avoiding a previously selected route.

22. The communications network of claim 18, further comprising a backbone link state database for storing link state information mapping said intra-domain virtual links to ones of said border nodes and mapping said inter-domain physical links to ones of said border nodes,

wherein a border node of a domain advertises summary link state information of the domain to a neighbor domain, and

wherein the border node is responsive to summary link state information received from a neighbor domain for combining the advertised summary link state information with link state information stored in the backbone link state database, performing calculations on the combined information to formulate new summary link state information, updating said backbone link state database with the new summary link state information and advertising the new summary link state information to a neighbor domain.

23. The communications network of claim 22, wherein said summary link state information contains a maximum value of costs of links said domain.

25. The cross-connect node of claim 24, further comprising a border connectivity table for indicating intra-domain connectivity of said border nodes within each of said domains,

said processor additionally using said border connectivity table for establishing said path.

26. The cross-connect node of claim 24, further comprising an optical cross-connect system for establishing transparent optical connections between neighboring network nodes.

27. The cross-connect node of claim 24, wherein said processor responds to a failure in establishing said path for using said domain routing tables and said backbone routing table again and reestablishing a path between said edge nodes by avoiding a previously selected route.

28. The cross-connect node of claim 24, further comprising a backbone link state database for storing link state information mapping said intra-domain virtual links to ones of said border nodes and mapping said inter-domain physical links to ones of said border nodes,

wherein said processor advertises summary link state information of a domain to a neighbor domain, and

wherein said processor is responsive to summary link state information received from a neighbor domain for combining the advertised summary link state information with link state information stored in the backbone link state database, performing calculations on the combined information to formulate new summary link state information, updating said backbone link state database with the new summary link state information and advertising the new summary link state information to a neighbor domain.

29. The cross-connect node of claim 28, wherein said summary link state information contains a maximum value of costs of links said domain.

15. An operating method for a communications network, wherein the network comprises a plurality of network nodes being organized into a plurality of groups corresponding to geographic domains, ones of said network nodes located at periphery of the network functioning as edge nodes and a plurality of user terminals connected to said edge nodes, the method comprising:

creating a domain connectivity table for indicating intra-domain connectivity of an associated one of said plurality of domains;

creating a domain routing table for indicating a route specifying ones of said network nodes whose intra-domain connectivity is indicated in said domain connectivity table;

advertising contents of the domain routing table to the network nodes of a downstream neighbor domain;

updating the domain routing table in accordance with advertised contents of the routing table of an upstream neighbor domain; and

using said domain routing table for establishing a path between said edge nodes in response to a path setup request from said user terminals.

18. A communications network comprising:

a plurality of network nodes organized into a plurality of groups corresponding to geographic domains, ones of said network nodes located at periphery of the network functioning as edge nodes to which user terminals are connected, and ones of said network nodes located at border points between neighbor domains of said plurality of domains functioning as border nodes, the border nodes of same domain being interconnected by intra-domain virtual links and the border nodes of different domains being interconnected by inter-domain physical links;

a plurality of domain routing tables respectively associated with said domains, each of the domain routing tables indicating a plurality of routes containing no intra-domain virtual link terminating at said edge nodes and no consecutively concatenated intra-domain virtual links; and

a backbone routing table for indicating a plurality of inter-domain routes and unreachability indications between the border nodes of each domain and the border nodes of every other domain, said inter-domain routes containing at least one of said inter-domain physical links but containing no consecutively concatenated intra-domain virtual links,

said network nodes using said domain routing tables and said backbone routing table for establishing a path between said edge nodes in response to a path setup request from said user terminals.

24. A cross-connect node for a communications network in which said node is one of a plurality of network nodes, said network nodes being organized into a plurality of groups corresponding to geographic domains, ones of said network nodes located at periphery of the network functioning as edge nodes to which user terminals are connected, and ones of said network nodes located at border points between neighbor domains of said plurality of domains functioning as border nodes, the border nodes of same domain being interconnected by intra-domain virtual links and the border nodes of different domains being interconnected by inter-domain physical links;

a domain routing table for indicating a plurality of routes containing no intra-domain virtual link terminating at said edge nodes and no consecutively concatenated intra-domain virtual links; and

a backbone routing table for indicating a plurality of inter-domain routes and unreachability indications between the border nodes of each domain and the border nodes of every other domain, said inter-domain routes containing at least one of the inter-domain physical links but containing no consecutively concatenated intra-domain virtual links; and

a processor for using said domain routing table and said backbone routing table for establishing a path between said edge nodes in response to a path setup request from said user terminals.

30. An operating method for a communications network which comprises a plurality of network nodes organized into a plurality of groups corresponding to geographic domains, ones of said network nodes located at periphery of the network functioning as edge nodes to which user terminals are connected, and ones of said network nodes located at border points between neighbor domains of said plurality of domains functioning as border nodes, the border nodes of same domain being interconnected by intra-domain virtual links and the border nodes of different domains being interconnected by inter-domain physical links, the method comprising:

creating a plurality of domain routing tables respectively associated with said domains, each of the domain routing tables indicating a plurality of routes containing no intra-domain virtual link terminating at said edge nodes and no consecutively concatenated intra-domain virtual links; and

creating a backbone routing table for indicating a plurality of inter-domain routes and unreachability indications between the border nodes of each domain and the border nodes of every other domain, said inter-domain routes containing at least one inter-domain physical links but containing no consecutively concatenated intra-domain virtual links,

using said domain routing tables and said backbone routing table for establishing a path between said edge nodes in response to a path setup request from said user terminals.

31. The method of claim 30, further comprising:

creating a border connectivity table for indicating intra-domain connectivity of said border nodes within each of said domains,

additionally using said border connectivity table for establishing said path.

32. The method of claim 30, further comprising:

responsive to a failure in establishing said path, using said domain routing tables and said backbone routing table again; and

reestablishing a path between said edge nodes by avoiding a previously selected route.

33. The method of claim 30, further comprising:

advertising summary link state information of a domain to a neighbor domain;

combining summary link state information advertised from a neighbor domain with link state information which maps, in a backbone link state database, said intra-domain virtual links to ones of said border nodes and said inter-domain physical links to ones of said border nodes,

performing calculation on the combined information to formulate new summary link state information;

updating said backbone link state database with the new summary link state information; and

advertising the new summary link state information to a neighbor domain.

34. The method of claim 33, wherein said summary link state information contains a maximum value of costs of links of said domain.