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

• US 7,397,802 B2
• Filed: 07/18/2002
• Issued: 07/08/2008
• Est. Priority Date: 07/19/2001
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Maeno, Yoshiharu
• Primary Examiner(s): Kizou; Hassan
• Assistant Examiner(s): ZHU, BO HUI ALVIN
• Application Number:
  US10/196,985
• Publication Number:
  US 20030016678A1
• Time in Patent Office: 2,182 Days
• Field of Search: 370/395.31, 370/389, 370/390
• US Class Current: 370/395.31
• 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 a 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 an unavailability of 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, the routing table of each of the associated domains including a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through 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 by selecting one of said parallel routes having a smallest number of transit domains and discarding the parallel routes other than the selected route from the routing table.

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 5, wherein each of said inter-domain connectivity tables is provided in each of the network nodes.

32. The communication network of claim 1, wherein said domain connectivity tables indicate both an availability and an unavailability of said intra-domain connectivity of the associated domain.

8. A cross-connect node for a communications network in which said node comprises 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 a periphery of the network functioning as edge nodes to which user terminals are connected, said cross-connect node comprising:

a domain connectivity table for indicating an unavailability of an 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, the domain routing table including a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through the domain of the cross-connect node; 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 by selecting one of said parallel routes having a smallest number of transit domains and discarding the parallel routes other than the selected route from the routing table.

9. The cross-connect node of claim 8, 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.

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

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

12. The cross-connect node of claim 8, 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.

33. The cross-connect node of claim 8, wherein said domain connectivity table indicates both an availability and an unavailability of said intra-domain connectivity of the associated domain.

13. 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 a 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 an unavailability of an 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, the domain routing table including a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through the domain of the cross-connect node;

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 by selecting one of said parallel routes having a smallest number of transit domains and discarding the parallel routes other than the selected route from the domain routing table.

14. The method of claim 13, 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 an 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.

34. The operating method of claim 13, wherein said domain connectivity table indicates both an availability and an unavailability of said intra-domain connectivity of the associated domain.

15. 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 a 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, each of the domain routing tables including 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

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 by selecting one of said parallel routes having a smallest number of transit domains and discarding the parallel routes other than the selected route from the domain routing table.

16. The communications network of claim 15, 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.

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

18. The communications network of claim 15, 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.

19. The communications network of claim 15, 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.

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

21. A cross-connect node for a communications network in which said node comprises 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 a 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 a 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, the domain routing table including a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through the associated domain;

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 muting table for establishing a path between said edge nodes in response to a path setup request from said user terminals by selecting one of said parallel routes having a smallest number of transit domains and discarding the parallel routes other than the selected route from the domain routing table.

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

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

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

24. The cross-connect node of claim 21, 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.

25. The cross-connect node of claim 21, 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 slate 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.

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

27. 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 a 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 a 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, each of said domain routing tables including a plurality of parallel routes between said source and destination terminals, each of said plurality of parallel routes repeatedly passing through the associated domain;

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 link but containing no consecutively concatenated intra-domain virtual links; and

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 by selecting one of said parallel routes having a smallest number of transit domains, and discarding the parallel routes other than the selected route from the domain routing table.

28. The method of claim 27, further comprising:

creating a border connectivity table for indicating an intra-domain connectivity of said border nodes within each of said domains, additionally using said border connectivity table for establishing said path.

29. The method of claim 27, 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.

30. The method of claim 27, 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.

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