Telephonic communications – Plural exchange network or interconnection – With interexchange network routing
Reexamination Certificate
2001-12-14
2004-12-07
Bui, Bing Q. (Department: 2642)
Telephonic communications
Plural exchange network or interconnection
With interexchange network routing
C379S114020, C379S221010, C379S221060, C379S221070
Reexamination Certificate
active
06829347
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a constraint based routing scheme for a network, particularly but not exclusive to a routing scheme which adopts various constraint profiles which can be selected by a user and implemented by a network operator for a communications network.
BACKGROUND TO THE INVENTION
Within the physical resources of a network, for example, within a network element, circuit switched traffic can follow paths and trails at various multiplex levels. A trail, for example, may be a circuit, line, path or section into which, at a first end, is inserted a data stream, and at a second end, is output the data stream.
Routing traffic across a network is becoming an increasingly complex task often requiring both manual and computational techniques to be combined. Computed routes may include network elements paths which are suitable for a variety of reasons. For example, whilst a network may support a variety of traffic types, however not all network elements may support a specific traffic type. If this route is to be used, then a container is needed to carry such traffic over the route between those network elements. Alternatively, those network elements must be avoided and another route needs to be selected.
For example, within a communications network, there may be a restricted number of network elements which are capable of processing voice data. Operations on voice data at a voice level may be performed within those particular network elements. However, to transport traffic data between those network elements, there must be further transmission, such as provided by a synchronous digital hierarchy (SDH) virtual container system.
As an example, if a voice connection is to be made between two geographically disparate network elements, the connection may be routed via intermediate network elements in the VC-12 layer. However, the VC-12 layer itself, to connect between intermediate network elements, may need to be multiplexed into a higher bit rate layer, e.g. the VC-4 layer.
Conventional trail routing schemes compute a number of potential routes and return these as potential routes to the network operator. The network operator must then select from the returned routes a suitable route bearing in mind any requests made by a user and the type of traffic to be routed. Trails computed conventionally will often include connections which are either physically and/or logically unsuitable. Conventional trail routing programs do not efficiently incorporate user preferences and/or desired routing profiles into the computation of the routes to eliminate the majority of unsuitable routes unless they are based on complex, for example genetic, algorithms. Such complex algorithms can incur extensive coding and, despite their complexity, often demonstrate a lack of versatility which creates implementation problems.
Conventional routing programs often implement Dijkstra algorithm based route selection scheme(s). These are more simple to implement in code than a genetic algorithm based route selection scheme. However, a problem associated with use of the Dijkstra algorithm is the high number of potential routes it returns from analysis at the abstract level which must then be confirmed as acceptable at the physical level either automatically or by a human operator intervening in the process.
The number of unsuitable routes selected in conventional Dijkstra based selection schemes can be extremely high, for example, in an optical network, Dijkstra based routing schemes often require subsequent verification of over a hundred possible routes. The elimination of redundant routes is often a time consuming process.
Users of a communications network providing routing services often request that a routing policy be used when a trail is being established. For example, when routing a trail consideration is often paid to criteria such as whether the trail will carry voice, data, video or graphics services, and the extent to which the trail maximises network asset utilization and minimises blocking. Accordingly, there is a demand for a network management system which can mediate between a required class of service requested by a user and the available quality of service which can be supported.
OBJECT OF THE INVENTION
One object of the invention seeks to mitigate and/or obviate the above problems by providing a method of selecting a trail route which is able to support and enforce user selected policies independently of the treatment of each class of traffic within different networking scenarios.
Another object of the invention is to provide an route advising application which provides routing policy management, i.e., routing management which can be selectively based on one or more predetermined routing profiles or equivalently routing principles. Such routing profiles may be based on criteria such as, for example, a balancing mode criteria for balancing traffic across the network, a threshold level for link usage criteria, a cumulative path threshold level criteria, a diverse routing criteria, an exclusion profile criteria for excluding some network sector/traffic type, a Quality of Service criteria, a Class of Service criteria, and/or a User Information criteria. A profile formed from an appropriate combination of these criteria can then be used in route computation requests.
Another object of the invention thus seeks to provide a method of optimising a routing scheme for a network.
Another object of the invention seeks to provide a routing scheme for a network which enables a suitable route to be determined automatically by pre-weighting certain routes according to their likely appropriateness.
The routing scheme according to the invention enables a route to be preselected using the routing algorithm which reflects additional selection criteria than simply the shortest-path across a network, for example, a route can be preselected to balance load on the network more evenly. Moreover, only routes which are physically able to support a particular connection request can be selected. Other selection criteria such as the cost of a route may be incorporated into the routing scheme to influence route selection by the Dijkstra algorithm.
The pre-weighting is provided by modifying the weight given to a network link in a conventional routing algorithm such as a Dijkstra algorithm. This biasing of a conventional routing algorithm enables factors beyond simple topology to be taken into account.
SUMMARY OF THE INVENTION
A first aspect of the invention seeks to provide a method of selecting a trail route across a communications network using a routing engine, the method comprising the steps of: selecting a routing policy profile having at least one route biasing parameter; inputting information from said routing policy profile to said routing engine, in which said information includes information derived from said selected at least one route biasing parameter which biases the computation of trail routes; and computing a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy.
Preferably, the method is used to select trail routes for different classes of traffic within a network. The routing policy may bias the output of the routing engine independently of the manner in which said different classes of traffic are individually routed.
The step of selecting a routing policy profile may be performed by a user of the communications network, or by a network operator, or be performed automatically.
Preferably, at least one of said parameters is taken from the group consisting of:
a balancing mode criteria; a threshold level for link usage criteria; a cumulative path threshold level criteria; a diverse routing criteria; an exclusion profile criteria for excluding some network sector/traffic type; a Quality of Service criteria; a Class of Service criteria; and a User Information criteria.
Preferably, the routing engine comprises a Dijkstra algorithm.
The trail route selected may provide protection fo
Barnes & Thornburg
Bui Bing Q.
Nortel Networks Limited
LandOfFree
Constraint based routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Constraint based routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraint based routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3299914