Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-18
2003-07-29
Ton, Dang (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S351000, C706S046000
Reexamination Certificate
active
06600749
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to communications networks, in particular, though not exclusively to planning of multi-service connections in a hierarchical broadband network.
BACKGROUND TO THE INVENTION
Broadband communications networks must deliver a variety of services, often in combination, over transport and access networks which differ geographically in their capabilities and quality of service parameters. Also, communications data is often subject to various forms of transformation, such as compression and translation, as part of its carriage between parties involved.
Broadband networks are likely to be heterogeneous for quite some time in the future, in terms of the connectivity types winch they offer and the available service gateways. There is therefore a problem when provisioning a service in matching the needs of an end user to the facilities which are available within a service provider.
Planning connections in hierarchical broadband communications networks involves similar planning a route of links and/or nodes in a simple network. However, due to the existence of the hierarchy in the broadband communications network, the routing problem can give rise to a hierarchy of routing sub-problems. A classical routing algorithm (eg Dijkstra's) could be applied to find a route between two nodes. However, the same routing problem could be applied recursively to sub-problems arising in the hierarchical network, but if a sub-problem has no solution then a higher level route must be modified.
Another complication in a heterogenous broadband network is the differing natures of links between nodes, for example a link between two nodes may only be capable of transferring a certain type of data between the two nodes. Traffic carrying and/or transport characteristics of such nodes constitute “behaviors” of the nodes. Therefore, a corresponding hierarchy of behavior rules need to be found to describe the traffic carrying transport characteristics of individual links and/or nodes in addition to the route of links and/or nodes itself in order to fully plan a connection which provisions a service to the end user.
In U.S. Pat No. 4,999,833 (Lee), there is described a system which applies a set of heuristic rules to a knowledge base to select connectivity paths through a network. However, the connectivity paths are selected from a routing sequence based upon a simple list of communications links and so is not capable of dealing with transformation of communications data as part of its carriage over the network. Furthermore, the system relates to radio networks only rather than heterogeneous networks and so does not overcome the problems associated with planning multi-service connections over transport and access networks which differ geographically in their capabilities and quality of service parameters.
SUMMARY OF THE INVENTION
A novel approach outlined herein supports the creation and management of broadband service connections in an integrated manner, using a combination of structured modeling and goal-based route finding.
According to a first aspect of the present invention, there is provided in a network comprising a plurality of nodes and links, each said node having at least one end point connecting it to a said link element, each said link between said end points having a type, a method of producing a connection plan representing at least one connection between said end points in said network, said connection plan comprising data describing a set of said end points and said types of said links between the end points said method comprising the steps of:
creating a data representation of at least part of said network;
creating a data representation of end points of said connection; and
applying an algorithm to said data representations to generate said connection plan.
Preferably, a said representation comprises a list of at least one clause, each said clause comprising at least one term.
Said clauses may comprise assertions and implications.
Preferably, said algorithm operates to select a said term of a said clause representing said connection as a sub-goal and recursively attempts to solve said sub-goal.
A said sub-goal may be assigned a priority, and said algorithm selects a said sub-goal with a highest said priority.
A said algorithm may select a said sub-goal which is a clause with fewest said terms.
Said algorithm may select a said sub-goal according to order of its said terms.
Said algorithm may select a sub-goal with a lowest position in said network hierarchy.
Said algorithm may select said sub-goal randomly.
Said algorithm may select a said clause with which to solve said sub-goal according to position of said clause in said list of clauses.
Said algorithm may select a said clause with which to solve said sub-goal by selecting a said clause having a term included in said connection plan.
Said algorithm may select a said clause with which to solve said sub-goal by selecting a clause which is lowest in said network hierarchy.
Said algorithm may select a said clause with which to solve said sub-goal by selecting a clause with a term having smallest capacity.
Said algorithm may randomly select a clause with which to solve said sub-goal.
Preferably, said clauses represent data describing features of said network, said features selected from the set:
classes of said network nodes;
end points of said network nodes;
links of said network;
schematic representations of said link types.
A said link typemay be selected from the set:
binding;
realization;
behavior;
containment.
A graphical representation of said connection plan may be described.
Said connection plan is preferably implemented as a set of connections in said network.
Said representation may comprise a substantially Prolog-like syntax.
According to a second aspect of the present invention there is provided in a network comprising a plurality of nodes and links, each said node having at least one end point connecting it to a said link element, each said link between said end points having a type, connection planning apparatus for planning at least one connection between said end points in said network by creating a connection plan comprising a set of said end points and said type of said link between the end point said connection planning apparatus comprising:
means of creating a representation of at least part of said network;
means of creating a representation of end points of said connection; and
an inference engine which uses said representation to generate said connection plan.
Said representation may comprise a list of at least one clause, each said use comprising at least one term.
Said clauses may comprise horn clauses.
Said inference engine may select a said term of a said clause representing said connection as a sub-goal and recursively attempts to solve said sub-goal.
A said sub-goal may be assigned a priority, and said inference engine elects a said sub-goal with a highest said priority.
Said inference engine may select a said sub-goal which is a clause with aid fewest said terms.
Said inference engine may select a sub-goal according to order of its said terms.
Said inference engine selects said sub-goal with a lowest position in said network hierarchy.
Said inference engine may select said sub-goal randomly.
Said inference engine may select a said clause with which to solve said sub-goal according to position of said clause in said list of clauses.
Said inference engine may select a said clause with which to solve said sub-goal by selecting said clause having a term included in said connection plan.
Said inference engine may select a said clause with which to solve said sub-goal by selecting a clause which is lowest in said network hierarchy.
Said inference engine may select a said clause with which to solve sub-goal by selecting a clause with a term having smallest capacity.
Said inference engine may randomly select a clause with which to solve said sub-goal.
Said clauses may represent data describing features of said network, said features selected from the set:
classes of said n
Bragg Nigel Lawrence
Hayball Clive Colin
Ross Niall Forbes
Tunnicliffe Andrew J
Barnes & Thornburg
Nortel Networks Limited
Ton Dang
Wilson Robert W.
LandOfFree
Planning system for broadband multi-service connections does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Planning system for broadband multi-service connections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Planning system for broadband multi-service connections will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3084162