Traffic route finder in communications network

Details Traffic route finder in communications network Traffic route finder in communications network

1998-03-20

2001-10-30

Vu, Huy D. (Department: 2733)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

Reexamination Certificate

active

06310883

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method of finding routes for connections across a communications networks comprising a plurality of node elements connected by a plurality of link elements, and particularly although not exclusively to a method of finding an optimized routing for a plurality of point to multipoint connections.
BACKGROUND TO THE INVENTION
A conventional broadband circuit switched communications network, for example a telephony network or a mobile phone network, comprises a plurality of nodes, at which are provided node equipment, the nodes connected by a plurality of communications links, the links comprising link equipment. The node equipment may comprise, for example a telecommunications switch apparatus, and the links may comprise a terrestrial link, eg an optical fiber link or coaxial cable or a wireless link.
An increasing range of services are delivered over such networks, including as examples, video on demand, video conferencing, distance learning, and internet services. Such services involve delivering different traffic data types, eg voice traffic, video or computer data traffic, having different characteristics, some types of traffic being more sensitive to delay than others and the different traffic types having different ranges of bitrate requirements. These services may involve delivery of data from a single source to a single destination (point to point) from a single source to many destinations (point to multipoint) or from a plurality of sources to a plurality of destinations (multipoint to multipoint). Such services place heavy requirements for routing of connections supporting these services over a network.
Conventional route finding methods, such as Dijkstra's shortest path algorithm, are capable of finding a single route for a single connection (E W Dijkstra, “A Note on Two Problems in Connection with Graphs”, Numerische
Mathematik 1, pg 269, 1959). However, using a shortest path routing algorithm on a connection-by-connection basis can lead to sub-optimal or even highly congested network routing solutions. Additionally, in a telecommunications network, there are constraints other than finding the shortest route to consider. For example, it may be useful to take into account traffic flowing through the network resulting from other connections, and link and node bandwidth capacities.
In WO 96/31969 there is disclosed a method of routing traffic from a communications network which uses a genetic algorithm search routine to find optimum sets of paths between nodes in a network for routing of traffic on a point to point connection basis with the object of minimizing a number of communications channels used, and to reduce a risk of a communications system being unable to handle a high volume of traffic.
In WO 96/31969, a set of shortest paths forms the basis for an initial string population of the genetic algorithm. Routes are selected according to a fitness criteria which includes a user specified weighting based on a number of channels required to support traffic, utilization of links represented as a number of links whose capacity could be exceeded, and a user specified “path cost” comprising a sum of costs of a plurality of links of a path between nodes. The user can vary the fitness criteria by altering the respective weighting given to the path cost, utilization, and number of channels in order to customize the genetic algorithm process to select for these criteria according to an importance as reflected in the user specified weightings.
However, shortest path routing, even as optimized by genetic algorithm technique, cannot provide solutions for point to multipoint routing. Further, shortest path routing cannot deal with service requests for mixed traffic data types.
SUMMARY OF THE INVENTION
Users of services delivered over such a communications network may make requests for services to be carried over the network, specifying a plurality of connections each between a source node and one or more destination nodes. Such service requests do not usually specify a route of nodes and links in the network which should be taken between the source and destination nodes.
One object of the present invention is to find routes for connections specified in a service request in a manner which takes into account a plurality of service requests simultaneously rather than one service request at a time.
Another object is to balance routing of connections across the network. For instance, if two connections would ideally include a same link in a shortest path, but this could result in either that link becoming overloaded or one of the connections needing to take a much longer route, then it may be beneficial for one or both of the connections to be routed over slightly longer routes in order to avoid network congestion, thereby resulting in a more even distribution of network link and node utilization.
Another object of the present invention is to provide a capability to include or exclude certain nodes or links from routes found for a particular connection, for example if it is known that a particular network node equipment is not working properly or for security reasons.
A further object is to provide a generic route finding means which is reusable for circuit switched communications networks using different transport protocol types.
Suitably, the generic route finder means takes a modularized embodiment capable of being installed in a network controller or network manager, and acting as a server for a plurality of other network management applications.
A further object of the present invention is to route connections in a communications network according to a type of traffic which is to be carded.
A further object of the present invention is to distribute traffic of a service connection over a plurality of routes.
A further object of the present invention is to distribute point to multi-point traffic over a network.
According to a first aspect of the present invention there is provided a method of finding routes of links for a plurality of communications connections over a network comprising a plurality of node elements and link elements, each said connection having a source node element and a plurality of destination node elements, said method comprising the machine executable steps of:
assigning at least one link cost to each said link element;
for each said connection to be routed:
selecting a set of node elements of said network which are not included in a source node element or a plurality of destination node elements of said connection;
determining which of said node elements in said set are Steiner Vertices;
evaluating a route cost of traversing a plurality of link elements between said source node elements and said plurality of destination node elements; and
for all said connections to be routed, evaluating a total cost of said route costs.
Preferably said set of node elements is represented by a string of bits,
a bit in said string having a value of 1 if said node element it represents is marked as a Steiner Vertex, and
a bit in said string having a value of 0 if said node element it represents is not marked as a Steiner Vertex.
Preferably, said step of evaluating a route cost comprises the steps of:
creating a Steiner tree including nodes in each said connection to be route and nodes in said set which are marked as Steiner Vertices; and
adding costs of traversing each link in said Steiner tree.
Preferably, said string of bits is manipulated using genetic algorithm operations, including reproduction, mutation, crossover and merging.
Said cost(s) assigned to said link element are associated with a data type, and said method may comprise the step of assigning a data type to all or some of said connections to be routed.
According to a second aspect of the present invention, there is provided a method of determining a plurality of routes for a plurality of connections across a network comprising a plurality of nodes and links, each said connection between a source node and a plurality of destination nodes, said method co

Affiliated with

Also associated with

Rating

Traffic route finder in communications network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Traffic route finder in communications network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Traffic route finder in communications network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2573066