Multiplex communications – Pathfinding or routing
Patent
1996-08-13
2000-03-28
Horabik, Michael
Multiplex communications
Pathfinding or routing
370351, 370354, 370234, 370235, 39520068, 39520069, 39520071, G01R 3108, G06F 1100, H04L 1266
Patent
active
060440759
DESCRIPTION:
BRIEF SUMMARY
FIELD OF THE INVENTION
The invention relates to the transfer of information within a network, e.g. a digital broadband telecommunication or computer network. More specifically, the invention concerns an apparatus and method for routing information from one node in an information network to another node in the network.
The invention is preferably applicable to Asynchronous Transfer Mode networks. An Asynchronous Transfer Mode (henceforth "ATM") network permits the transfer of digital information from any one access point within it to any other access point. These access points are referred to as the nodes of the network.
ATM networks have been used widely in the prior art for traditional telecommunications and computer-computer communication. It is expected that ATM networks which support broadband communication will be chosen increasingly in the future for interactive communication and for the dissemination of information. Examples of these uses which already exist are video-on-demand, interactive games, home-banking, home-shopping, remote study, PC/PC- and client/server links. ATM networks are ideally suited to data transfer tasks lying within the fields of "multi-media" and "information super-highway" communication.
BACKGROUND OF THE INVENTION
The section of a network which directly connects two nodes without including any other node is termed the link between those nodes. In most networks a node is connected by such direct links to only a few other nodes, these often being nodes which are spatially or geographically close to it.
When communication must be provided between any two nodes in a network to facilitate the transfer of data between them, a "route" must be provided between them. A request for a communication is usually made by a user located at one of the network's nodes who requests immediate provision of a route to one other single node in the network. The route assigned will consist of one or more links. There are usually very many possible routes between any two nodes, each of these routes passing through different sets of intermediate nodes and each therefore consisting of a different combination of links.
The problem which the present invention solves concerns selecting and assigning the optimum route for communication between any two nodes in a network. One aspect of this problem concerns exploiting the network's carrying capacity efficiently in the assignment of routes. Another aspect of this problem is the provision of the optimum route sufficiently quickly after a request is made that the user making the request does not have to wait and delay the planned communication significantly.
ATM networks which are presently used must respond to a request for the assignment of a route between any two nodes. This is done in some prior art networks by the following steps, or a variation thereof, performed in the order a)-c): present, e.g. what is the bandwidth which the route must have. constraints in the request should be assigned. This calculation usually seeks to minimize one parameter, e.g. the financial cost of the route, or the delay in the route. The result of this calculation is the optimum route for the particular request which was made.
The calculations in step c) must be made for a very large number of possible routes.
Methods such as that given above are only usable for small networks where very few constraints can be made in the request. Typically only one constraint can be specified. If these conditions are not met then the calculation of which route to assign takes too much time for "real time" assignment of routes and is too expensive. For networks with very many links the calculation can become intractable, i.e. could not be completed within many years on even a very fast computer.
At least one prior art document has attempted to overcome these difficulties by performing the calculation mentioned above before the request for a route has been received. See the document "SNA Networks of Small Systems" from the IEEE Journal on Selected Areas in Communications discussed below. Ho
REFERENCES:
patent: 4905233 (1990-02-01), Cain et al.
patent: 5142531 (1992-08-01), Kirby
patent: 5233604 (1993-08-01), Ahmadi et al.
patent: 5491690 (1996-02-01), Alfonsi et al.
patent: 5615254 (1997-03-01), Qiu et al.
Le Boudec Jean-Yves
Przygienda Antoni B
Horabik Michael
International Business Machines - Corporation
Phan Man
Woods Gerald R.
LandOfFree
Apparatus and method for routing a communication in a 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 Apparatus and method for routing a communication in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for routing a communication in a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1332220