SYSTEM FOR COMMUNICATING LABELED ROUTING TREES TO ESTABLISH PREFERRED PATHS AND SOURCE ROUTES WITH LOCAL IDENTIFIERS IN WIRELESS COMPUTER NETWORKS

• US 20030165117A1
• Filed: 10/15/1999
• Published: 09/04/2003
• Est. Priority Date: 10/15/1999
• Status: Active Grant

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: SPOHN, MARCELO, GARCIA-LUNA-ACEVES, J. JOAQUIN, BEYER, DAVID A.
• Granted Patent: US 6,836,463 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 8/24 Transfer of terminal data
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support

Abstract

One or more labeled routing trees (LRTS) are produced at a router of a computer network according to a shortest path determination made over a partial topology graph of the network, which graph is produced according to knowledge of adjacent links of the router and one or more LRTs of neighboring routers. The LRTs of the router may be updated in response to receipt of routing state update messages, and such messages may include local link identifiers assigned by a head of a link to which the identifiers pertain, and node parameters of a tail of the link to which the local link identifiers pertain. The routing state update messages may be transmitted within the network: (i) in response to a new destination node being detected by an existing node within the network, (ii) in response to a destination becoming unreachable by a collection of the existing nodes, (iii) in response to the change in the cost of a path to at least one destination exceeding a threshold and/or (iv) in situations where a routing loop may be encountered among two or more of the nodes of the network (e.g., at times when a path implied in the LRT of the router leads to a loop).

Claims

1. A method, comprising producing one or more labeled routing trees (LRTs) at a router of a computer network according to a shortest path determination made over a partial topology graph of the network, which graph is produced according to knowledge of adjacent links of the router and one or more LRTs of neighboring routers.

2. The method of claim 1 wherein the LRTs of the router are updated in response to receipt of routing state update messages.

3. The method of claim 2 wherein the routing state update messages include local link identifiers assigned by a head of a link to which the identifiers pertain.

4. The method of claim 3 wherein the routing state update messages further include node parameters of a tail of the link to which the local link identifiers pertain.

5. The method of claim 3 wherein the routing state update messages are transmitted within the network:

(i) in response to a new destination node being detected by an existing node within the network, (ii) in response to a destination becoming unreachable by a collection of the existing nodes, and/or (iii) in response to the change in the cost of a path to at least one destination exceeding a threshold delta, (iv) in situations where a routing loop may be encountered among two or more of the nodes of the network.

6. The method of claim 5 wherein situations where a routing loop may be encountered include times when a path implied in the LRT of the router leads to a loop.

7. A routing protocol, comprising distributing local link identifiers among nodes of a computer network within routing state update messages.

8. The routing protocol of claim 7 wherein the local link identifiers are each assigned by a head of a link to which the identifiers pertain.

9. The routing protocol of claim 7 wherein the routing state update messages include state parameters for nodes at tails of links to which the identifiers pertain.

10. The routing protocol of claim 7, further comprising distributing labeled routing trees of the nodes of the computer network among the nodes.

11. The routing protocol of claim 10 wherein each node of the computers network distributes its labeled routing trees to its neighboring nodes.

12. The routing protocol of claim 11 wherein each node of the computer network maintains one labeled routing tree per type of service offered in the network.

13. The routing protocol of claim 11 wherein each node generates its labeled routing trees according to a partial topology graph derived from the node'"'"'s adjacent links and labeled routing trees of neighboring nodes.

14. The routing protocol of claim 13 wherein the labeled routing trees of a node are generated by applying a path selection algorithm to the partial topology graph.

15. The routing protocol of claim 14 wherein each node of the computer network maintains one labeled routing tree per type of service offered in the network.

16. The routing protocol of claim 15 wherein labeled routing trees of nodes in the computer network are updated in response to receipt of the routing state update messages.

17. The routing protocol of claim 16 wherein labeled routing trees are updated according to whether an optimum routing approach or a least overhead routing approach is used within the computer network.

18. The routing protocol of claim 17 wherein in the optimum routing approach, routing state update messages are transmitted:

(i) when a routing state update message which causes a link to be added to a subject node'"'"'s labeled routing trees is received, (ii) when a more recent routing state update message regarding an existing link in the subject node'"'"'s labeled routing trees is received, and/or (iii) when a destination becomes unreachable by the subject node.

19. The routing protocol of claim 17 wherein in the least overhead routing approach, routing state update messages are transmitted:

(i) when a subject node finds a new destination or any neighbors of the subject node report same, (ii) when a destination becomes unreachable by the subject node or any of its neighbors, (iii) when the subject node finds that the change in the cost of path to at least one destination exceeds a threshold delta, (iv) when a path implied in any of the labeled routing trees of the subject node leads to a loop, and/or a new successor chosen to a given destination has an address larger than an address of the subject node and a reported distance from the new successor to a particular destination is larger than a reported distance from a previous successor to that particular destination.

20. A routing update message, comprising information regarding performance characteristics and addressing information for a link of a computer network and a node of the network at a tail end of the link.

21. The routing update message of claim 20 wherein the routing update message further comprises a time stamp assigned by a node at a head end of the link.

22. The routing update message of claim 21 wherein the performance characteristics include link state parameters of the link.

23. The routing update message of claim 21 wherein the routing update message further comprises a type of service vector.

24. The routing update message of claim 21 wherein the routing update message further comprises addressing information for a node at a head end of the link.

25. The routing update message of claim 23 wherein the type of service vector specifies a type of service routing tree in which the link is being used by a node transmitting the routing update message.

26. The routing update message of claim 20 wherein the performance characteristics of the link comprise link delay, link cost, available bandwidth, and/or reliability.

27. The routing update message of claim 20 wherein the addressing information of the link comprises a local link identifier assigned to the link by a node at a head end of the link.