Methods, systems and computer program products for end-to-end route selection in compound wide/local area networks

• US 6,097,727 A
• Filed: 04/29/1997
• Issued: 08/01/2000
• Est. Priority Date: 04/29/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Peters, Marcia Lambert
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US08/841,212
• Time in Patent Office: 1,190 Days
• Field of Search: 370/238, 370/252, 370/400, 370/389, 370/392, 370/393, 370/401, 370/402, 370/403, 370/404, 370/405, 370/406, 370/408, 370/409, 370/231, 370/235, 370/411, 370/437, 370/475, 395/238, 395/242, 395/243, 395/244
• US Class Current: 370/400
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A route selection system, method and computer program provides a complete end-to-end communications path between an origin node and a destination node in a relatively large communications network having a number of branch networks and at least one backbone network operationally connectable to the branch network. The origin node, the destination node, or both nodes, are located in branch networks and operationally connect to standard network nodes in the backbone network by way of a branch network node. The branch network nodes may be cascaded or in parallel. The branch network node modifies the communications path selected by the standard network node. The branch network node conceals the hop between the node in the branch and itself, identifies the direction of the hop as either an uplink or a downlink, identifies itself as the control point of the resource located in the corresponding node in the branch, and includes the concealed hop information in its own tail vectors which it adds to the route. In serving the origin node, the branch network node completes the route prior to sending the route to the origin node. In serving the destination end node, the branch network node completes the route during connection setup. Connection setup may take the form of either BIND or Route Setup.

Claims

1. A method for establishing a communications path having a plurality of nodes between an origin node and a destination node in a communications network, the communications network having a first branch network and a first backbone network, said first branch network operationally connectable to the first backbone network, the first backbone network having a network node, and only one of the origin node or the destination node being in the first branch network, wherein each node has tail vectors associated therewith, said method comprising the steps of:

establishing a route between the origin node and the destination node, said route calculated by the network node

wherein said establishing step comprises the steps of;

selecting a route between the first branch network and the one of the origin node or the destination node not in the first branch network; and

modifying said selected route to expand said selected route to the one of the origin node or the destination node in the first branch network, wherein a modified selected route between said origin node and said destination node is established; and

wherein said modifying step comprises the steps of;

modifying tail vectors of the one of said origin node or said destination node in the first branch network to represent tail vectors of an intermediate node in said first branch network;

passing the modified tail vectors of the one of said origin node or said destination node in the first branch network to the network node;

receiving a selected route between the first branch network and the one of the origin node or the destination node not in the first branch network; and

adding a link to the received selected route, said added link connecting the intermediate node in the first branch network and the one of said origin node or said destination node in the first branch network.

2. A method for establishing a communications path according to claim 1 wherein the origin node is in the first branch network;

and wherein the network node is operationally connectable to an intermediate node in the first branch network and said intermediate node is operationally connectable to the origin node in the first branch network.

3. A method for establishing a communications path according to claim 1 wherein the destination node is in the first branch network;

and wherein the network node is operationally connectable to an intermediate node in the first branch network and said intermediate node is operationally connectable to the destination node in the first branch network.

4. A method for establishing a communications path according to claim 1 wherein said origin node is in a first branch network and said destination node is in a second branch network.

5. A method for establishing a communications path according to claim 1 wherein said selecting step is preceded by the origin node locating the destination node.

6. A method for establishing a communications path according to claim 1 wherein said establishing step further comprises the step of connecting the origin node and the destination node along the modified selected route.

7. A method for establishing a communications path according to claim 6 wherein said connecting step is a BIND process.

8. A method for establishing a communication path according to claim 6 wherein said connecting step is a ROUTE SETUP process.

9. A method for establishing a communications path according to claim 1 wherein said establishing step is followed by the step of transferring data between said origin node and said destination node.

10. A method for establishing a communications path according to claim 1 wherein the origin node is in the first branch network;

wherein the first branch network is operationally connectable to a second branch network and said second branch network is operationally connectable to the first backbone network; and

wherein the network node is operationally connectable to an intermediate node in the second branch network and said intermediate node is operationally connectable to the origin node in the first branch network.

11. A method for establishing a communications path according to claim 1 wherein the destination node is in the first branch network;

wherein the first branch network is operationally connectable to a second branch network and said second branch network is operationally connectable to the first backbone network; and

wherein the network node is operationally connectable to an intermediate node in the second branch network and said intermediate node is operationally connectable to the destination node in the first branch network.

12. A method for establishing a communication path according to claim 1 wherein the origin node is in the first branch network;

wherein the origin node is operationally connectable to a first intermediate node in the first branch network and the origin node is operationally connectable to a second intermediate node in the first branch network; and

wherein the network node is operationally connectable to one of said first intermediate node or said second intermediate node.

13. A method for establishing a communications path according to claim 1 wherein the destination node is in the first branch network;

wherein the destination node is operationally connectable to a first intermediate node in the first branch network and the destination node is operationally connectable to a second intermediate node in the first branch network; and

wherein the network node is operationally connectable to one of said first intermediate node or said second intermediate node.

14. A method for establishing a communications path having a plurality of nodes between an origin node and a destination node in a communications network, the communications network having a first branch network and a first backbone network, said first branch network operationally connectable to the first backbone network, the first backbone network having a network node, and only one of the origin node or the destination node being in the first branch network, wherein each of said nodes has at least one tail vector associated therewith, said method comprising the steps of:

establishing a route between the origin node and the destination node, said route calculated by the network node; and

wherein said establishing step comprises the steps of;

receiving a selected route from the network node, the selected route identifying a communications path between the first branch network and the one of the origin node and the destination node not in the first branch network;

modifying said selected route to expand said received selected route to the one of the origin node or the destination node in the first branch network, wherein a modified selected route between said origin node and said destination node is established; and

transmitting the expanded selected route to the origin node; and

wherein said receiving step is preceded by the steps of;

receiving a request at a branch network node in the first branch network from one of the origin node or the destination node in the first branch network to establish a communications path between the origin node and the destination node;

modifying the at least one tail vector associated with the one of the origin node or the destination node in the first branch network to include the at least one tail vector associated with the branch network node, such that the modified tail vector hides the knowledge of the link between the branch network node and the origin node or the destination node in the first branch network from the network node; and

transmitting the request to establish a communications path between the origin node and the destination node, and the modified tail vector, to the network node.

15. A method for establishing a communications path according to claim 14 wherein the origin node is in the first branch network;

and wherein the network node is operationally connectable to an intermediate node in the first branch network and said intermediate node is operationally connectable to the origin node in the first branch network.

16. A method for establishing a communications path according to claim 14 wherein the destination node is in the first branch network;

and wherein the network node is operationally connectable to an intermediate node in the first branch network and said intermediate node is operationally connectable to the destination node in the first branch network.

17. A method for establishing a communications path according to claim 14 wherein said establishing step further comprises the step of connecting the origin node and the destination node along the modified selected route.

18. A method for establishing a communications path according to claim 17 wherein said connecting step is a BIND process.

19. A method for establishing a communications path according to claim 17 wherein said connecting step is a ROUTE SETUP process.

20. A method for establishing a communications path according to claim 14 wherein the origin node is on the first branch network;

wherein the first branch network is operationally connectable to a second branch network and said second branch network is operationally connectable to the first backbone network; and

wherein the network node is operationally connectable to an intermediate node in the second branch network and said intermediate node is operationally connectable to the origin node in the first branch network.

21. A method for establishing a communications path according to claim 14 wherein the destination node is in the first branch network;

wherein the first branch network is operationally connectable to a second branch network and said second branch network is operationally connectable to the first backbone network; and

wherein the network node is operationally connectable to an intermediate node in the second branch network and said intermediate node is operationally connectable to the destination node in the first branch network.

22. A method for establishing a communications path according to claim 14 wherein the origin node is in the first branch network;

wherein the origin node is operationally connectable to a first intermediate node in the first branch network and the origin node is operationally connectable to a second intermediate node in the first branch network; and

wherein the network node is operationally connectable to at least one of said first intermediate node and said second intermediate node.

23. A method for establishing a communications path according to claim 14 wherein the destination node is in the first branch network;

wherein the destination node is operationally connectable to a first intermediate node in the first branch network and the destination node is operationally connectable to a second intermediate node in the first branch network; and

wherein the network node is operationally connectable to at least one of said first intermediate node and said second intermediate node.

24. A system for establishing a communications path having a plurality of nodes between an origin node and a destination node in a communications network, the communications network having a first branch network and a first backbone network, said first branch network operationally connectable to the first backbone network, the first backbone network having a network node, and only one of the origin node or the destination node being in the first branch network, wherein each node has tail vectors associated therewith, said system comprising:

means for establishing a route between the origin node and the destination node, said route calculated by the network node

wherein said means for establishing comprises;

means for selecting a route between the first branch network and the one of the origin node or the destination node not in the first branch network; and

means for modifying said selected route to expand said selected route to the one of the origin node or the destination node in the first branch network, wherein a modified selected route between said origin node and said destination node is established; and

wherein said means for modifying comprises;

means for modifying tail vectors of the one of said origin node or said destination node in the first branch network to represent tail vectors of an intermediate node in said first branch network;

means for passing the modified tail vectors of the one of said origin node or said destination node in the first branch network to the network node;

means for receiving a selected route between the first branch network and the one of the origin node or the destination node not in the first branch network; and

means for adding a link to the received selected route, said added link connecting the intermediate node in the first branch network and the one of said origin node or said destination node in the first branch network.

25. A computer program product for establishing a communications path having a plurality of nodes between an origin node and a destination node in a communications network, the communications network having a first branch network and a first backbone network, said first branch network operationally connectable to the first backbone network, the first backbone network having network node, and only one of the origin node or the destination node being in the first branch network, wherein each node has tail vectors associated therewith, said computer program product comprising:

a computer readable storage medium having computer readable code means embodied in said medium, said computer readable code means comprising;

computer instruction means for establishing a route between the origin node and the destination node, said route calculated by the network node

wherein said computer instruction means for establishing comprises;

computer instruction means for selecting a route between the first branch network and the one of the origin node or the destination node not in the first branch network; and

computer instruction means for modifying said selected route to expand said selected route to the one of the origin node or the destination node in the first branch network, wherein a modified selected route between said origin node and said destination node is established; and

wherein said computer instruction means for modifying comprises;

computer instruction means for modifying tail vectors of the one of said origin node or said destination node in the first branch network to represent tail vectors of an intermediate node in said first branch network;

computer instruction means for passing the modified tail vectors of the one of said origin node or said destination node in the first branch network to the network node;

computer instruction means for receiving a selected route between the first branch network and the one of the origin node or the destination node not in the first branch network; and

computer instruction means for adding a link to the received selected route, said added link connecting the intermediate node in the first branch network and the one of said origin node or said destination node in the first branch network.

26. A method of providing a connection path in a node where a first endpoint of the connection path is in a branch network which is hidden from a second endpoint of the connection path, the method comprising:

receiving at a branch network node associated with the branch network a connection communication from one of the first or the second endpoint;

incorporating revised endpoint information in the received connection communication to provide branch network node information associated with a hop between the first endpoint and the branch network node so as to provide a modified communication containing information about the connection path within the branch network and outside the branch network; and

forwarding the modified communication to a next node in the connection path.

27. A method according to claim 26, wherein connection communication is a locate find communication, wherein the first endpoint is an origin endpoint and the locate find communication is received by the branch network node from the origin endpoint node, and wherein the step of incorporating endpoint information comprises the step of replacing tail vectors in the locate find communication with tail vectors that reflect a one hop route from the origin node to the branch network node.

28. A method according to claim 26, wherein the connection communication is a resource control vector (RSVC) communication, wherein the first endpoint is an origin endpoint and wherein the step of incorporating comprises the step of inserting the one hop from the origin node to the branch network node as the first hop in the RSCV.

29. A method according to claim 26, wherein connection communication is a locate found communication, wherein the first endpoint is a destination endpoint and the locate found communication is received by the branch network node from the destination endpoint node, and wherein the step of incorporating endpoint information comprises the step of replacing tail vectors in the locate found communication with tail vectors that reflect a one hop route from the branch network node to the destination node.

30. A method according to claim 26, wherein the connection communication is a resource control vector (RSVC) communication, wherein the first endpoint is a destination endpoint and wherein the step of incorporating comprises the step of inserting the one hop from the branch network node to the destination network node as the last hop in the RSCV.

31. A system for providing a connection path in a node where a first endpoint of the connection path is in a branch network which is hidden from a second endpoint of the connection path, comprising:

means for receiving at a branch network node associated with the branch network a connection communication from one of the first or the second endpoint;

means for incorporating revised endpoint information in the received connection communication to provide branch network node information associated with a hop between the first endpoint and the branch network node so as to provide a modified communication containing information about the connection path within the branch network and outside the branch network; and

means for forwarding the modified communication to a next node in the connection path.

32. A system according to claim 31, wherein connection communication is a locate find communication, wherein the first endpoint is an origin endpoint and the locate find communication is received by the branch network node from the origin endpoint node, and wherein the means for incorporating endpoint information comprises means for replacing tail vectors in the locate find communication with tail vectors that reflect a one hop route from the origin node to the branch network node.

33. A system according to claim 31, wherein the connection communication is a resource control vector (RSVC) communication, wherein the first endpoint is an origin endpoint and wherein the means for incorporating comprises means for inserting the one hop from the origin node to the branch network node as the first hop in the RSCV.

34. A system according to claim 31, wherein connection communication is a locate found communication, wherein the first endpoint is a destination endpoint and the locate found communication is received by the branch network node from the destination endpoint node, and wherein the means for incorporating endpoint information comprises means for replacing tail vectors in the locate found communication with tail vectors that reflect a one hop route from the branch network node to the destination node.

35. A system according to claim 31, wherein the connection communication is a resource control vector (RSVC) communication, wherein the first endpoint is a destination endpoint and wherein the means for incorporating comprises means for inserting the one hop from the branch network node to the destination network node as the last hop in the RSCV.

36. A computer program product for providing a connection path in a node where a first endpoint of the connection path is in a branch network which is hidden from a second endpoint of the connection path, comprising:

a computer readable storage medium having computer readable program code means embodied in said medium, said computer readable program code means comprising;

computer readable program code means for receiving at a branch network node associated with the branch network a connection communication from one of the first or the second endpoint;

computer readable program code means for incorporating revised endpoint information in the received connection communication to provide branch network node information associated with a hop between the first endpoint and the branch network node so as to provide a modified communication containing information about the connection path within the branch network and outside the branch network; and

computer readable program code means for forwarding the modified communication to a next node in the connection path.

37. A computer program product according to claim 36, wherein connection communication is a locate find communication, wherein the first endpoint is an origin endpoint and the locate find communication is received by the branch network node from the origin endpoint node, and wherein the computer readable program code means for incorporating endpoint information comprises computer readable program code means for replacing tail vectors in the locate find communication with tail vectors that reflect a one hop route from the origin node to the branch network node.

38. A computer program product according to claim 36, wherein the connection communication is a resource control vector (RSVC) communication, wherein the first endpoint is an origin endpoint and wherein the computer readable program code means for incorporating comprises computer readable program code means for inserting the one hop from the origin node to the branch network node as the first hop in the RSCV.

39. A computer program product according to claim 36, wherein connection communication is a locate found communication, wherein the first endpoint is a destination endpoint and the locate found communication is received by the branch network node from the destination endpoint node, and wherein the computer readable program code means for incorporating endpoint information comprises computer readable program code means for replacing tail vectors in the locate found communication with tail vectors that reflect a one hop route from the branch network node to the destination node.

40. A computer program product according to claim 36, wherein the connection communication is a resource control vector (RSVC) communication, wherein the first endpoint is a destination endpoint and wherein the computer readable program code means for incorporating comprises computer readable program code means for inserting the one hop from the branch network node to the destination network node as the last hop in the RSCV.