Link state routing techniques

• US 7,047,316 B2
• Filed: 03/23/2001
• Issued: 05/16/2006
• Est. Priority Date: 03/24/2000
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwata, Atsushi, Takatama, Hirokazu
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): Hu, Jinsong
• Application Number:
  US09/814,854
• Publication Number:
  US 20010029543A1
• Time in Patent Office: 1,880 Days
• Field of Search: 709/225, 709/240, 370/238, 370/351, 370/356, 370/357, 379/900
• US Class Current: 709/240
• CPC Class Codes: H04L 2012/562 Routing
• 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/302 Route determination based on requested QoS

Abstract

A link state routing communication device allowing path precalculation satisfying the required quality of a connection and reducing the call blocking probability is disclosed. A path satisfying a connection request can be selected from a plurality of precalculated paths which are stored for each destination in a memory. The precalculated paths reflect the latest link resource information using the feasibility check operation or precalculated path update operation. Therefore, a blocking probability of connection setup using precalculated paths can be decreased. In a border node, summarized information is calculated based on precalculated paths and therefore high-speed summarized information calculation is allowed, resulting in reduced computation load.

Claims

1. A link state routing device of a node in a network comprising a plurality of nodes and links, said link state routing device comprising:

a first memory for storing link resource information for each link in the network, wherein the link resource information is updated as an occasion to do so arises;

a path calculator for calculating a plurality of precalculated paths from a source node to at least one destination node based on link resource information stored in the first memory, independently of occurrence of a connection request;

a second memory for storing the precalculated paths and path resource information for each precalculated path;

a path selector for selecting a precalculated path from the precalculated paths stored in the second memory when a connection request occurs, wherein the precalculated path is selected so as to satisfy a quality requirement of the connection request;

a connection setup attempter for attempting connection setup of the precalculated path;

a first counter for counting the number of path selection occurrences in the path selector;

a second counter for counting the number of path blocking occurrences in the connection setup attempter;

a blocking rate calculator for calculating a blocking rate based on the counted number of path selection occurrences and the counted number of path blocking occurrences; and

a controller controlling the path calculator such that, when the blocking rate is not smaller than a predetermined threshold, the path calculator recalculates a plurality of precalculated paths for each destination node based on link resource information stored in the first memory.

2. The link state routing device according to claim 1, wherein the path selector comprises:

a precalculated path searcher for searching the second memory for a precalculated path candidate satisfying the quality requirement of the connection request; and

a feasibility checker for checking whether the precalculated path candidate comprises a feasible path, by referring to link resource information stored in the first memory,

wherein, when the precalculated path candidate comprises an infeasible path, the precalculated path searcher searches the second memory for another precalculated path candidate.

3. The link state routing device according to claim 2, wherein the path selector further comprises:

an on-demand path searcher for searching the first memory for a path candidate satisfying the quality requirement of the connection request,

wherein, when a precalculated path candidate satisfying the quality requirement of the connection request is not found, the on-demand path searcher is activated.

4. The link state routing device according to claim 2, wherein the blocking rate calculator calculates a blocking rate based on the counted number of feasibility check occurrences and the counted number of path blocking occurrences.

5. The link state routing device according to claim 1, further comprising:

an updater for updating the path resource information of a precalculated path stored in the second memory when link resource information of a link included in the precalculated path is updated.

6. The link state routing device according to claim 5, wherein the path selector further comprises:

an on-demand path searcher for searching the first memory for a path candidate satisfying the quality requirement of the connection request,

wherein, when a precalculated path candidate satisfying the quality requirement of the connection request is not found, the on-demand path searcher is activated.

7. The link state routing device according to claim 5, further comprising a controller controlling the path calculator such that, when the updated link resource information of the link is not smaller than a predetermined link quality threshold, the path calculator recalculates a plurality of precalculated paths for each destination node exclusive of the updated link resource information of the link.

8. The link state routing device according to claim 1, wherein the path calculator calculates a plurality of precalculated paths for each destination node based on a link-inherent parameter that is independent of link resource information.

9. The link state routing device according to claim 1, wherein the path calculator calculates a precalculated path based on a single parameter a plurality of times to produce a plurality of precalculated paths for each destination node.

10. The link state routing device according to claim 1, wherein the path calculator calculates a plurality of precalculated paths for each destination node based on an integrated parameter set having a plurality of parameters integrated therein.

11. The link state routing device according to claim 10, wherein the path selector sorts the precalculated paths stored in the second memory according to the integrated parameter set to search the second memory for a precalculated path satisfying the quality requirement of the connection request.

12. The link state routing device according to claim 11, wherein the path selector searches the second memory for a precalculated path satisfying the quality requirement of the connection request in a round robin fashion weighted by the integrated parameter set.

13. The link state routing device according to claim 12, wherein the path selector searches the second memory for a precalculated path satisfying the quality requirement of the connection request in a round robin fashion hierarchically weighted by the integrated parameter set.

14. The link state routing device according to claim 1, wherein the link resource information comprises delay information and available bandwidth information.

15. The link state routing device according to claim 1, wherein the path selector further comprises:

an on-demand path searcher for searching the first memory for a path candidate satisfying the quality requirement of the connection request,

wherein, when a precalculated path candidate satisfying the quality requirement of the connection request is not found, the on-demand searcher is activated.

16. A communication method in a link state routing device of a node in a network comprising a plurality of nodes and links, said method comprising:

storing link resource information for each link in the network in a first memory;

updating the link resource information as an occasion to do so arises;

calculating a plurality of precalculated paths from a source node to at least one destination node based on link resource information stored in the first memory, independently of occurrence of a connection request;

storing the precalculated paths and path resource information for each precalculated path in a second memory;

selecting a precalculated path from the precalculated paths stored in the second memory when a connection request occurs, wherein the precalculated path is selected so as to satisfy a quality requirement of the connection request;

attempting connection setup of the precalculated path;

counting the number of path selection occurrences in the path selector;

counting the number of path blocking occurrences during the attempting of the connection setup;

calculating a blocking rate based on the counted number of path selection occurrences and the counted number of path blocking occurrences; and

when the blocking rate is not smaller than a predetermined threshold, recalculating a plurality of the precalculated paths for each destination node based on link resource information stored in the first memory.

17. The method according to claim 16, wherein selecting the precalculated path comprises:

searching the second memory for a precalculated path candidate satisfying the quality requirement of the connection request; and

checking whether the precalculated path candidate comprises a feasible path, by referring to link resource information stored in the first memory,

wherein, when the precalculated path candidate comprises an infeasible path, the second memory is searched for another precalculated path candidate.

18. The method according to claim 16, further comprising:

updating the path resource information of a precalculated path stored in the second memory when link resource information of a link included in the precalculated path is updated.

19. The method according to claim 16, further comprising:

updating path resource information of a precalculated path stored in the second memory when link resource information of a link included in the precalculated path is updated; and

when the update link resource information of the link is not smaller than a predetermined link quality threshold, recalculating a plurality of precalculated paths for each destination node exclusive of the updated link resource information of the link.

20. The method according to claim 16, wherein the link resource information comprises delay information and available bandwidth information.