Routing in a communication network

Details Routing in a communication network Routing in a communication network

2002-01-15

2003-07-08

Yao, Kwang B. (Department: 2662)

Typewriting machines

Carriage or carriage-moving or movement-regulating mechanism

Margin-regulator mechanism

C370S237000

Reexamination Certificate

active

06588953

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to routing in a communication network. In particular, the invention concerns routing in telecommunication and cellular networks. Generally, the term routing describes choosing a data stream path between two endpoints. In this text routing also means a process to route the whole network, i.e. to route all data streams in a network.
BACKGROUND OF THE INVENTION
The routing process of a network is not a simple task. The network can be divided, for example, into three main levels: physical, path, and logical levels. The physical level describes a real physical network, where nodes and lines have been located. The path level makes it clear how channels (for example packets) have been routed via the nodes. This level is significant concerning choices for back-up routes as well. The logical level describes how a single node (for example a base station) sees the network, i.e. depicts transparent connections. All these layers have to be taken into account for making a working routing.
A network can be hundreds or even thousands of nodes in size. Taking into account the above-mentioned matters, the routing of the network can be very time-consuming. In general, routing methods are based on algorithms that calculate the best or near best routing alternative. Sophisticated algorithms typically yield good results, but they normally consume time. Alternatively coarse algorithms yield poor results, but they are fast. To achieve good results fast at present, very fast computers are used.
It is also possible to divide a routing problem into several small parts, which are solved separately. In this case, the division is based on entities which have as few common parameters as possible, i.e. there exist as few interfaces between entities as possible. Another way to solve a routing problem is hierarchical technique in which the most important parameters are solved and fixed first, and after that the next set of parameters is solved and fixed, and so on, until there are no parameters left. Usually both, the division and hierarchical technique need manual work, which is time-consuming.
Fast expensive computers are not always available. Spending more time with the good algorithms can be too time-consuming. Dividing the network into small subnetworks needs expensive and time-consuming manual work. However, to have a fast sophisticated routing method is especially important for new enlarging cellular networks, which are significantly larger than older networks. The objective of the invention is to alleviate the above-mentioned drawbacks of the known solutions and to increase effectiveness in the known solutions. This is achieved in a way described in the claims.
SUMMARY OF THE INVENTION
The idea of the invention is to preprocess the network in order to accelerate the routing process. The preprocessing comprises finding the difficult network portions, and removing trivial network portions from the network topology. As a result of these phases the network is divided into small subnetworks. After the preprocessing predetermined endpoints of a single route are added into the subnetworks for finding the route through the network. After that, traffic in each subnetwork is routed separately. Traffic in the network parts between the subnetworks, or between the endpoints and the subnetworks, may need additional routing, but they are simple to perform.


REFERENCES:
patent: 5444694 (1995-08-01), Millet et al.
patent: 5793765 (1998-08-01), Boer et al.
patent: 5872773 (1999-02-01), Katzela et al.
patent: 6324674 (2001-11-01), Andreev et al.
patent: 0637153 (1993-07-01), None
patent: 1009131 (1998-12-01), None
patent: 98/27695 (1997-12-01), None
L. Li and A. K. Somani, “Dynamic Wavelength Routing Using Congestion and Neighborhood Information”, IEEE/ACM Transactions on networking, vol. 7, No. 5, Oct. 1999, pp. 799-786.*
L. Szymanski and O. W. W. Yang, “Spanning Tree Algorithm for Spare Network Capacity”, IEEE, pp. 0447-0452.**
“Spanning Tree Method For Link State Aggregation in Large Communication Networks,” Whay Chiou Lee, vol. 1, pp. 297-302.

Affiliated with

Also associated with

Rating

Routing in a communication 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 Routing in a communication network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing in a communication network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3074327