Multiplex communications – Pathfinding or routing
Reexamination Certificate
1998-06-02
2001-11-06
Ton, Dang (Department: 2661)
Multiplex communications
Pathfinding or routing
C370S254000
Reexamination Certificate
active
06314093
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for finding routes for a plurality of connections in a communications network comprising a plurality of node elements connected by a plurality of link elements.
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. A set of shortest paths forms the basis for an initial string population of the genetic algorithm.
In WO 96/31969, 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 cannot deal with service requests for mixed traffic data types. Further, use of shortest path routing can lead to unbalanced use of some routes or links in a network, whilst other routes and links remain under utilized.
SUMMARY OF THE INVENTION
Users of services delivered over a communications network may make service requests for connections over the network, specifying a source node and one or more destination nodes for each connection. Such connection requests need not usually specify a route of nodes and links in the network which should be taken between the source and destination nodes. Routes across the network need to be assigned to connection requests in order to implement connections.
One object of the present invention is to route connection requests in a communication network in a manner which takes into account a plurality of connection requests simultaneously rather than one connection 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 connection requests in a communications network according to a type of traffic which is to be carried.
A further object of the present invention is to distribute traffic of a point to point service connection over a plurality of routes.
According to a first aspect of the present invention there is provided in a network comprising a plurality of nodes and links, a method of assigning a plurality of routes to a plurality of connections, each said connection having a source node and a destination node, said method comprising the steps of:
for each said connection:
generating a plurality of routes of links; and
selecting a route from said plurality of routes,
wherein, said process of selecting favors selection of a route comprising lightly utilized links over routes comprising heavily utilized links.
Said method preferably comprises applying an artificial intelligence technique. Suitably, the artificial intelligence technique is applied to select a set of routes to satisfy all connections, wherein the selection provides an optimized balancing of load across the network as a whole, or across selected parts of the network. Such an artificial intelligence technique preferably comprises a genetic algorithm, but may comprise simulated annealing, or a like technique.
Preferably, said method comprises the step of assigning a link cost at each said link of the network, wherein said process of selecting favors selection of routes having lower link costs over routes having higher link costs.
According to a second aspect of the present invention, there is provided in a network comprising a plurality of nodes and links, a method of assigning a plurality of routes to a plurality of connections comprising the steps:
for each connection, generating data describing a plurality of routes for said connections, each said route represented as a bit representation;
assembling a plurality of said bit representations into a bit string representing a respective route for each of a plurality of connections;
creating a population comprising a plurality of said bit strings;
modifying said population of bit strings to rearrange an order of bits within individual bit strings of said population;
for each bit string of said population, determining a utilization of each link in said network; and
selecting a said bit string having a relatively more even distribution of utilization across all said links.
Preferably, said method comprises the steps of:
for each connection to b
Mann Jason Warren
Turner John Ian
White Anthony Richard Phillip
Lee Mann Smith McWilliams Sweeney & Ohlson
Nortel Networks Limited
Ton Dang
LandOfFree
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.
Profile ID: LFUS-PAI-O-2568668