US 5,495,479 AGranted

Method and apparatus for an automatic decomposition of a network topology into a backbone and subareas

AssigneeInternational Business Machines Corporation

InventorsClaude Galaand, Paolo Scotton

Life of this patent

Estimating the term…

Loading patent…

Abstract

The object of the invention is to perform an automatic decomposition of a packet switching network in backbone nodes and subareas nodes to speed up the routing path search without degrading the optimization criterion of the routing algorithm and without generating additional control messages on the network. Currently, routing algorithms compute all the available paths in the network, from the source node to the destination node before to select an optimal route. However, networks are rarely fully meshed. They are usually built around a hierarchical structure: a set of nodes, interconnected by high throughput lines, are used to build a backbone with a high degree of meshing and then, local nodes are grouped in geographical subareas themselves attached to the backbone. Routing algorithms can take advantage of this particular network topology to drastically reduce the complexity of paths computation. For a given connection, only a limited number of nodes are defined as usable and are taken in account by the algorithm in its path calculation.

Claims6

Dependent claims

A network access node (300) for a packet switching communication network (200) comprising a plurality of network nodes (201-208) interconnected with transmission links (209), said network nodes being connected to termination nodes, said access node including means for receiving and transmitting data packets (301, 302, 304), and data storage means (306) for storing data representing the network configuration, said network access node further including:

selecting means for selecting a set of links suitable for use as part of a path to each destination termination node located in the network, said selecting means further include clustering means for decomposing said network into a set of backbone nodes and a plurality of subarea nodes, said clustering means further comprising
data retrieval means for retrieving the network configuration data from said data storage means,
sorting means for ranking all nodes according to the number of links connected to the nodes,
tree forming means for constructing a connectivity tree in which each node in the network appears only once and in which the tree origin is the highest rank node found by said sorting means,
classifying means for classifying nodes into backbone nodes and subarea nodes, backbone nodes being all non-termination nodes and any termination node which is connected only to one other node and subarea nodes being any node that is not a backbone node, subarea nodes having the same parent being categorized in the same subarea,
means for defining a backbone path between two subareas, the backbone path including a link to each subarea interconnected through the highest ranked node from the set of nodes connecting the two links,
means for removing from the set of backbone to subarea links, any link in which the parent node in the subarea is not connected to the parent in the backbone and any link to a subarea having less than a predetermined number of nodes;
storage means for storing data representing the sets of links selected by said selecting means;
and
means responsive to a request for a connection between said access node and a destination node to establish a routing path including links from the set of links selected for the destination node.

7 more elements

A method performed in an access node (300) for selecting a routing path in a packet switching communication network (200) comprising a plurality of nodes (201-208) interconnected by transmission links (209), said method comprising the steps of:

a) storing data representing the network configuration in a network topology database;
b) selecting a set of links which may be used in a route to each destination node in the network, said selecting step including the further step of decomposing the network into a set of backbone nodes and a plurality of subarea nodes, said decomposing step including further steps of
retrieving data representing the network configuration from the network topology database,
ranking all network nodes in the network as a function of the number of links connected to the network nodes,
constructing a connectivity tree in which each node in the network appears only one and in which the tree origin is the highest raned node found in the ranking step,
classifying nodes in the network either as backbone nodes or termination nodes, backbone nodes being all non-termination nodes and any termination node which is connected only to one other node, subarea nodes being any node which is not a backbone node, subarea nodes having the same parent being grouped into the same subarea,
detecting all links between each pair of subareas,
defining a path through the backbone between the pair of subareas, the backbone path including a link to each subarea interconnected through the highest ranked node from the set of nodes connecting the two links,
removing from the set of backbone to subarea links, any link in which the parent node in the subarea is not connected to the parent in the backbone and any link to a subarea having less than a predetermined number of nodes;
storing data representing the sets of links selected by said selecting step;
and
responsive to a request for a connection between said access node and a destination node, establishing a routing pathing including links from the set of links selected for the destination node.

9 more elements

Dependencies are inferred from the claim text.