Virtual trees routing protocol for an ATM-based mobile network

• US 5,872,773 A
• Filed: 05/17/1996
• Issued: 02/16/1999
• Est. Priority Date: 05/17/1996
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Katzela, Irene, Veeraraghavan, Malathi
• Primary Examiner(s): VU, HUY DUY
• Application Number:
  US08/650,097
• Time in Patent Office: 1,005 Days
• Field of Search: 370/203, 370/254, 370/255, 370/256, 370/257, 370/258, 370/351, 370/389, 370/395, 370/392, 370/400, 370/401, 370/402, 370/403, 370/404, 370/405, 370/409, 370/410, 370/408 , 370/399, 370/252, 370/310, 370/315, 370/328, 370/338, 370/349, 370/398, 340/825.03, 340/826
• US Class Current: 370/256
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 40/34 Modification of an existing route

Abstract

The present invention is a system and method for routing cells in a wireless communications network, wherein the communications network includes a plurality of switching nodes and the cells are routed according to destination-rooted virtual path identifier (VPI) trees. The present invention includes a routing protocol for determining preestablished VPI trees rooted at each destination node. The routing protocol manages the routes of these trees, while ensuring that there are at least two VPI trees from each source to each destination for reliability reasons, and that each destination node has multiple VPI trees for load-balancing reasons. The routing protocol includes an off-line procedure for the determination of the initial VPI trees. In order to handle changes in network traffic and conditions, the routing protocol updates the routes of the VPI trees in a dynamic and distributed fashion. These update procedures are triggered by congestion, link/node failures and link/node additions.

Claims

1. A method for routing cells in a wireless communications network, said communications network including a plurality of switching nodes and said cells being routed according to destination-rooted virtual path identifier (VPI) trees, said method comprising the steps of:

forming a set of VPI primary trees by determining all-pairs shortest paths for said nodes within said network, said set of primary trees including one tree rooted at each node in said network; and

determining a set of secondary trees rooted at each node in said network for given destination nodes.

2. The method of claim 1, wherein said communications network is represented as a graph G(S,L), S being a set of nodes in said communications network and L a set of links coupling said nodes, said step of determining a set of secondary trees including the steps of:

updating link weights for links between said nodes in edges of said graph G(S,L), such that for each edge e_ij, a new assigned weight is (w+Σ

p_ij), where p_ij is the number of paths in all said primary trees that use edge e_ij ; and

defining all-pairs shortest paths for said graph G(S,L) using updated link weights from said step of updating.

3. The method of claim 1, wherein said communications network is represented as a graph G(S,L), S being a set of nodes in said communications network and L a set of links coupling said nodes, said step of determining a set of secondary trees including the steps of:

determining a set of edges E_n through which a primary VPI tree V_nl rooted at node n is routed;

updating link weights for links between said nodes of edges e_ij .di-elect cons.E_n in the graph G(S,L) by assigning new weights w'"'"'_ij =w_ij +p_ij, where p_ij is the number of paths in a primary VPI sink tree V_nl traversing the edge e_ij, and w_ij represent the weights used in computing said primary trees; and

defining all-pairs shortest paths on the new graph including updated weights to thereby determine shortest paths from all nodes to a destination node.

4. The method of claim 1, wherein said communications network is represented as a graph G(S,L), S being a set of nodes in said communications network and L a set of links coupling said nodes, said step of determining a set of secondary trees including the steps of:

determining a set of edges E_n through which a primary VPI tree V_nl rooted at node n is routed;

updating link weights for links between said nodes of edges e_ij .di-elect cons.E_n in the graph G(S,L) by assigning new weights w'"'"'_ij =w_ij +p_ij, where P_ij is the number of paths in a primary VPI sink tree V_nl traversing the edge e_ij and w_ij represent the weights used in computing said primary trees;

creating a graph G'"'"'(S, L-E_n) by eliminating from G(S,L) edges that are included in a primary sink tree rooted at n;

replacing each connected component of G'"'"'(S, L-E_n) by a new node, thereby creating an auxiliary graph G"(S'"'"', E'"'"');

marking each edge e in the graph G"(S'"'"', E'"'"'), with a two-tuple (i,j) denoting the nodes in G(S,L) that this edge represents;

defining all-pairs shortest paths for the auxiliary graph, G"(S'"'"', E'"'"') for a destination node n'"'"' such that connected component n'"'"' includes the node n, wherein a new tree from said all-pairs shortest paths is V_n ;

expanding the nodes n'"'"' in V_n ; and

defining all-pairs shortest paths for the destination node n, thereby providing a maximally disjoint tree from the primary tree.

5. The method of claim 1, wherein said cells are ATM cells.

6. The method of claim 1, wherein said all-pairs shortest-paths are determined using Floyd-Warshall algorithms.

7. The method of claim 3, wherein said all-pairs shortest-paths are determined using a Dijkstra algorithm.

8. The method of claim 1, further including the step of dynamically updating said VPI trees in response to triggering events in said network.

9. The method of claim 8, wherein said triggering events are selected from the group consisting of congestion on a physical link in said network, physical link failure, node failure, node removal, addition of a physical link and addition of node to said network.

10. The method of claim 8, wherein said step of updating is performed according to a virtual trees routing protocol.

11. A wireless communications network including a plurality of switching nodes adapted to route cells in said network according to destination-rooted virtual path identifier (VPI) trees, said network configured according to the steps of:

forming a set of VPI primary trees by computing all-pairs shortest paths for said nodes within said network, said set of primary trees including one tree rooted at each node in said network; and

including a set of secondary trees rooted at each node in said network for given destination nodes.

12. The network of claim 11, wherein said communications network is represented as a graph G(S,L), S being a set of nodes in said communications network and L a set of links coupling said nodes, said set of secondary trees being determined according to the steps of:

updating link weights for links between said nodes in edges of said graph G(S,L), such that for each edge e_ij, a new assigned weight is (w+Σ

p_ij), where P_ij is the number of paths in all said primary trees that use edge e_ij ; and

defining all-pairs shortest paths for said graph G(S,L) using updated link weights from said step of updating.

13. The network of claim 11, wherein said communications network is represented as a graph G(S,L), S being a set of nodes in said communications network and L a set of links coupling said nodes, said set of secondary trees being determined according to the steps of:

determining a set of edges E_n through which a primary VPI tree V_nl rooted at node n is routed;

updating link weights for links between said nodes of edges e_ij .di-elect cons.E_n in the graph G(S,L) by assigning new weights w'"'"'_ij =w_ij +p_ij, where p_ij is the number of paths in a primary VPI sink tree V_nl traversing the edge e_ij, and w_ij represent the weights used in computing said primary trees; and

defining all-pairs shortest paths on the new graph including updated weights to thereby determine shortest paths from all nodes to a destination node.

14. The network of claim 11, wherein said communications network is represented as a graph G(S,L), S being a set of nodes in said communications network and L a set of links coupling said nodes, said set of secondary trees being determined according to the steps of:

determining a set of edges E_n through which a primary VPI tree V_nl rooted at node n is routed;

updating link weights for links between said nodes of edges e_ij .di-elect cons.E_n in the graph G(S,L) by assigning new weights w_ij =w_ij +p_ij, where p_ij is the number of paths in a primary VPI sink tree V_nl traversing the edge e_ij and w_ij represent the weights used in computing said primary trees;

creating a graph G'"'"'(S, L-E_n) by eliminating from G(S,L) edges that are included in a primary sink tree rooted at n;

replacing each connected component of G'"'"'(S, L-E_n) by a new node, thereby creating an auxiliary graph G"(S'"'"', E'"'"');

marking each edge e in the graph G"(S'"'"', E'"'"'), with a two-tuple (i,j) denoting the nodes in G(S,L) that this edge represents;

defining all-pairs shortest paths for the auxiliary graph, G"(S'"'"', E'"'"') for a destination node n'"'"' such that connected component n'"'"' includes the node n, wherein a new tree from said shortest path algorithm is V_n ;

expanding the nodes n'"'"' in V_n ; and

defining all-pairs shortest paths for the destination node n, thereby providing a maximally disjoint tree from the primary tree.

15. The network of claim 11, wherein said cells are ATM cells.

16. The network of claim 11, wherein said all-pairs shortest-paths are determined using Floyd-Warshall algorithms.

17. The network of claim 13, wherein said all-pairs shortest-paths are determined using a Dijkstra algorithm.

18. The network of claim 11, wherein said switching nodes are portable base stations.

19. A method for dynamically updating routing paths for cells traveling in a wireless communications network, said communications network including a plurality of switching nodes and said cells being routed according to destination-rooted virtual path identifier (VPI) trees, said method comprising the steps of:

detecting a trigger condition at a node i in said communications network indicative of a requirement to update one or more of said VPI trees, said trigger condition being a congested link in said communications network;

updating route structures and route states of said VPI trees in said communications network in response to said trigger condition; and

determining a candidate set of said VPI trees for redirection, said candidate set including "empty" VPIs, wherein an empty VPI has no assigned virtual channel identifiers (VCIs) thereon, said step of determining further including the substeps of;

creating a set of all VPIs using said congested link;

referencing a record of connections at said node i having been admitted with quality of service (QoS) guarantees to thereby rule out any non-empty VPIs.;

communicating with a root node of each potentially empty VPI to determine if a best-effort connection without QoS guarantees has been admitted on said VPI.

20. The method of claim 19, further including the steps of:

sending an explore-route message from said node i to all adjacent nodes in said network requesting accommodation for redirection of a VPI, wherein each of said adjacent nodes checks a transit VPIs data table to determine if an entry exists for said VPI;

initiating a check-resources-and-cycles-process to determine if a certain path has sufficient resources on links along said path to permit said redirection, said check resources-and-cycles-process also ensuring that no cycles are caused in the tree structure of said VPI.

21. The method of claim 20, wherein said check-resources-and cycles-process includes the steps of:

checking a data table to determine available resources on a link along the root of said VPI;

checking for cycles in said tree structure by determining whether a neighboring node is node i, wherein a redirection-rejection message is sent to a root node of said VPI if no available resources exist on said link or no loop condition is created, otherwise said explore-route message being sent on to a next node along said root of said VPI wherein subsequent to said explore-route message traversing all nodes in said root, said root node selects one route through which redirection is possible.

22. The method of claim 19, wherein if said node i determines that a sufficient number of reroutes have not been accomplished, said node i determines to delete itself from a VPI tree by means of a deletion procedure to thereby reduce traffic on said VPI tree by eliminating data generated by end-users coupled node i.

23. The method of claim 22, wherein said deletion procedure includes the steps of:

obtaining permission from a root node of said VPI tree for said deletion procedure;

determining whether node i is a leaf node on said VPI tree, said node i dropping itself from said VPI tree if determined to be a leaf node, and

requesting downstream neighbor nodes from node i to perform redirection for said VPI tree if node i is not a leaf node.

24. The method of claim 20, wherein said node i determines that a sufficient number of reroutes have not been accomplished, further including the step of requesting inactivation of selected VPIs for said node i to thereby prevent new connections from being admitted to said selected VPIs.

25. The method of claim 22, wherein subsequent to said deletion procedure, said node i initiates an addition procedure to another VPI if node i has only two active VPIs to a given destination node in said network, said addition procedure including the steps of:

communicating with neighbor nodes to determine different VPIs to a given destination node;

adding node i as a leaf node to one or more of said different VPIs.

37. The method of claim 21, wherein one of said available resources is spare capacity, spare capacity being defined as C-A-T, where C represents bandwidth capacity of a connection, A represents allocated capacity and T represents a reserved capacity to absorb bursts when needed.

40. The method of claim 21, wherein said available resources are selected from the group consisting of spare capacity and hop count.

26. A method for dynamically updating routing paths for cells traveling in a wireless communications network, said communications network including a plurality of switching nodes and said cells being routed according to destination-rooted virtual path identifier (VPI) trees, said method comprising the steps of:

detecting a trigger condition at a node i in said communications network indicative of a requirement to update one or more of said VPI trees, wherein said trigger condition is a failed link, wherein all VPIs traversing said failed link are considered empty, an empty VPI having no assigned virtual channel identifiers (VCIs) thereon; and

updating route structures and route states of said VPI trees in said communications network in response to said trigger condition.

27. The method of claim 26, wherein said trigger condition is a failed node said redirection for said failed node being multiple conditions of said failed link occurring at said failed node.

28. The method of claim 26, further including the steps of:

creating a set of VPIs using said failed link for each destination node l;

determining if more than two functional VPIs exist to destination node l;

performing a selective freeze of VPIs at nodes downstream from node i, thereby preventing said nodes from sending cells to node i, if more than two functional VPIs exist to destination node l, and

redirecting VPIs in said set of VPIs using said failed link to thereby create multiple routes to said to destination node l, if two or fewer functional VPIs exist to destination node l.

29. A method for dynamically updating routing paths for cells traveling in a wireless communications network, said communications network including a plurality of switching nodes and said cells being routed according to destination-rooted virtual path identifier (VPI) trees, said method comprising the steps of:

detecting a trigger condition at a node i in said communications network indicative of a requirement to update one or more of said VPI trees wherein said trigger condition is the addition of a link in said network to replace a previously failed link;

updating route structures and route states of said VPI trees in said communications network in response to said trigger condition;

determining a set of VPIs that were inactivated by a selective freeze procedure when said the link failure occurred;

activating said set of VPIs previously inactivated;

updating a data table at node i to indicate that a VPI from said set of VPIs previously inactivated is active;

sending selective unfreeze messages in a chained fashion to neighbor nodes downstream of a selected VPI in said communications network, wherein each node informs a root node of its activation; and

updating a data table at said root node to reflect new activation of said set of VPIs and thereby incorporate the restored link in said network.

30. A method for dynamically updating routing paths for cells traveling in a wireless communications network, said communications network including a plurality of switching nodes and said cells being routed according to destination-rooted virtual path identifier (VPI) trees, said method comprising the steps of:

detecting a trigger condition at a node i in said communications network indicative of a requirement to update one or more of said VPI trees, wherein said trigger condition is the addition of a link in said network between two ports not previously connected;

updating route structures and route states of said VPI trees in said communications network in response to said trigger condition;

selecting a set of empty VPIs that pass through other links in said network; and

redirecting said other links onto the new link being added.

31. A method for dynamically updating routing paths for cells traveling in a wireless communications network, said communications network including a plurality of switching nodes and said cells being routed according to destination-rooted virtual path identifier (VPI) trees, said method comprising the steps of:

detecting a trigger condition at a node i in said communications network indicative of a requirement to update one or more of said VPI trees, wherein said trigger condition is the addition of said node i into said network;

updating route structures and route states of said VPI trees in said communications network in response to said trigger condition;

communicating with neighbor nodes in said network to determine a set of VPI trees to join as a leaf node; and

joining said set of VPI trees as a leaf node.

32. The method of claim 31, wherein an additional resource check procedure is used to select neighbor nodes through which node i should join a given VPI tree if multiple neighbor nodes exist as potential candidates through which to join said given VPI tree, further including the step of performing said additional resource check through said multiple neighbor nodes.

33. The method of claim 32, further including the step of creating VPI sink trees at said node i using a given sink tree creation procedure.

34. The method of claim 33, wherein said sink tree creation procedure is executed using a distributed version of the Bellman-Ford algorithm for a primary tree, further including the step of determining a set of secondary trees from topology and loading conditions of said network.

35. the method of claim 33, wherein said given sink tree creation procedure includes the steps of:

communicating with neighbor nodes to obtain a list of VPIs routed at said neighbor nodes;

selecting a set of least-loaded trees from said list of VPIs such that all other nodes in said network are enabled to reach said node i; and

updating data tables at said other nodes to thereby include said set of least-loaded trees.

36. A method for dynamically updating routing paths for cells traveling in a wireless communications network, said communications network including a plurality of switching nodes and said cells being routed according to destination-rooted virtual path identifier (VPI) trees, said method comprising the steps of:

detecting a trigger condition at a node i in said communications network indicative of a requirement to update one or more of said VPI trees, wherein said trigger condition is a congestion incident, said congestion incident being defined as C-U<

T for a period of τ

, where C represents bandwidth capacity of a connection, U represents usage and T represents a reserved capacity to absorb bursts when needed; and

updating route structures and route states of said VPI trees in said communications network in response to said trigger condition.

38. The method of claim 36, wherein said cells are ATM cells.

39. The method of claim 36, wherein said nodes are portable base station switching devices.