Modern digital networks are made to operate in a multimedia environment and interconnect, upon request, a tremendous number of users and applications through fairly large and complex digital communication networks.
Due to the variety of users' profiles and distributed applications, the corresponding traffic is becoming more and more bandwidth consuming, non-deterministic and requiring more connectivity. This has been the driver for the emergence of fast packet switching network architectures in which data, voice, and video information are digitally encoded, chopped into small packets and transmitted through a common set of nodes and links interconnected to constitute the network communication facilities.
An efficient transport of mixed traffic streams on very high speed lines (herein also designated as links or trunks) means for these new network architectures a set of requirements in terms of performance and resource consumption including a very high throughput and a very short packet processing time, a very large flexibility to support a wide range of connectivity options, an efficient flow and congestion control.
One of the key requirements of high speed packet switching networks is to reduce the end to end delay in order to satisfy real time delivery constraints and to achieve the necessary high nodal throughput for the transport of voice and video. Increases in link speeds have not been matched by proportionate increases in the processing speeds of communication nodes. The fundamental challenge for high speed networks is to minimize the processing time and to take full advantage of the high speed/low error rate technologies. Most of the transport and control functions provided by the new high bandwidth network architectures are performed on an end to end basis. The flow control and particularly the path selection and bandwidth management processes are managed by access points of the network which reduces both the awareness and the function of the intermediate nodes.
In high speed networks, the nodes must provide a total connectivity. This includes attachment of the user's devices regardless of vendor or protocol, and the ability to have the end user communicate with any other device. The network must support any type of traffic mix including data, voice, video, fax, graphic or image. The nodes must be able to take advantage of all common carrier facilities and to be adaptable to a plurality of protocols. All needed conversions must be automatic and transparent to the end user.
Communication networks have at their disposal limited resources to ensure efficient transmission. An efficient bandwidth management is essential to take full advantage of a high speed network. While transmission costs per byte continue to drop year after year, said transmission costs are still likely to continue to represent the major expense of operating future telecommunication networks as the demand for bandwidth increases. Thus considerable efforts have been spent on designing flow and congestion control processes, bandwidth reservation mechanisms, routing algorithms to manage the network bandwidth.
An ideal network should be able to transmit useful traffic directly proportional to the traffic offered to the network and this until the maximum transmission capacity is reached. Beyond this limit, the network should operate at its maximum capacity whatever the demand is.
A general problem in the communication networks is to find a path between a source and a destination node. For virtual circuits operation, the path decision is done once only at the time of the connection (or session) establishment, or, and this is particularly important for this invention, upon any network failure like in case of link or node failure for rerouting the disrupted connections. The choice of a routing algorithm is not easy because it must satisfy a large number of often conflicting requirements. The routing or rerouting algorithm must allow the network to operate in an optimal way, according to a criterion which can vary with the utilization type. In most of the cases, the network is realized so as to minimize the packet transit time and to transfer the maximum number of packets. In other cases, the objective is to decrease the communication cost, or to develop a reliable network able to operate correctly either in case of catastrophic line or node failure or in case of peaks of traffic.
Because of the variety of the constraints, there is a large number of different routing types like flooding routing, random or stochastic routing, deterministic routing. This last routing technique can be implemented according to particular modes such as fixed or adaptive routing, centralized or distributed routing, node by node or end to end routing, connection oriented or connectionless routing.
Contrary to the Fixed Routing, where the routing rules are established once for all, the purpose of the Adaptive Routing is to satisfy at any time the optimization criteria. Routing Tables are permanently updated according to the instantaneous state of the traffic on the links.
When the characteristics of the network fluctuate, it is possible to adapt the routing by assigning to one node the responsibility to update periodically the routing tables according to the traffic and the topology. The principal disadvantage of this method called Centralized Routing is to generate an important auxiliary traffic and to subordinate the good functioning of the network to only one node. On the other hand, the Centralized Routing can generate some problems at the time the tables are refreshed because corresponding updatings cannot be performed at the same time by all the nodes.
The solution is to decentralize the tables at the level of each node. The corresponding Distributed Routing is a method in which neighboring nodes are exchanging messages concerning the traffic and the network conditions to update their own routing tables.
In order to minimize the processing time and to take full advantage of the high speed/low error rate technologies, the transport and control functions provided by the high bandwidth networks may be performed on an end to end basis. No hop by hop error recovery or retransmission is envisioned in high speed, high performance (low error) links and thus, there is no need for transit nodes to be aware of all individual transport connections. The originating node (access node) is responsible for calculating the route that a packet must take through the network. The routing of the packets presents two aspects for which a wide range of implementing methods exist. Said routing includes determining what the route for a given connection shall be, and actually switching the packet within a switching node.
We shall consider herein that the high speed connections between end users are established on a reserved path to guarantee the bandwidth and the quality of service requested by the user. The path across the network is computed in response to each connection request by the originating node. The computed path is based on the parameters characterizing the network connection requirements and on link capacity and load information maintained within each network node. The originating node sends a reservation request to the end node. As the bandwidth request packet flows along the network, each transit node determines whether it has enough capacity to accept the new connection. If the connection is accepted, the requested bandwidth is reserved. Changes are reflected in every node of the network by means of control messages broadcasted through so-called spanning tree arrangement of the network. Once a connection is established, there is no need to place a destination address in the packet header every time a packet is sent. All that is needed is an identifier to be used to specify which connection is to be used for this packet. Due to the low packet overhead, the connection oriented routing technique is particularly adapted to the transmission of very short packets (for example for real-time voice connections). This technique requires that connection tables be set up and maintained dynamically in each node. The implementation of flow and congestion control in a connection oriented network is easier than in a connectionless one, because network nodes can regulate the flow on individual connections. However, when a link or a node becomes inoperative (i.e. goes down), connections that were passing through the affected link or node are typically lost. A new connection must be established through a different route. This rerouting takes time and may disrupt the connection at the end user level.
A Path Selection process is used to determine optimum paths for users across the network each time a connection is requested either at call set-up or upon link or node failure. This implies the allocation of network resources to users in order to guarantee their quality-of-service requirements while optimizing the overall throughput within the network. This function takes place entirely within the origin node. Various quality of service parameters may be specified by the users, some of them in order to satisfy realtime delivery constraints, others related to non real time data traffic transfer. Accordingly, so-called priority classes are defined that specify the corresponding quality of service guaranteed.
In order to establish a connection, the origin node computes a path to the destination node that is capable of carrying the new connection and providing the quality level of service required by the new connection. The Path Selection algorithm uses data describing the current traffic load in the entire network (nodes and links). Such data are stored in a topology database located in each node of the network. If no suitable path can be found to meet all requirements, the connection is rejected. Once, the origin node has found a suitable path, a connection set-up message is generated which traverses the selected route, reserving the required resources and updating the resource allocations for each link visited by the set up message.
To meet high throughput requirements, paths are selected and resources reserved once only at the time of the connection establishment and upon specific events, including link failure. The Path Selection algorithm takes into account various constraints which come both from the user (quality of service requirements, user's traffic characteristics . . . ) and from the current network topology and bandwidth allocation. In addition, the algorithm maximizes the network throughput by choosing a path with the least number of hops and which tends to achieve an even distribution of the traffic among the links. Once an appropriate path has been selected, the network connection establishment process takes place, and only then are the resources along the path reserved.
Therefore selecting a path and setting up a connection can take considerable processing overhead in network nodes and can generate a significant delay. For end nodes supporting multiple connection set-up requests simultaneously, the time for establishing a connection may be huge. The origin node must compute the path to the destination node that is capable of carrying the new connection and provide the level of service required by the new connection. The path selection algorithm uses data describing the current traffic load in the entire network (nodes and links). Such data are stored in the topology database located in each node of the network.
For connections service in real-time, the delays are a very important parameter, especially since some connections terminate in equipment that runs time-outs.
Those delays are also important from the point of view of path switching requirement upon link/node failure within the network. The rerouting of a lot of connections that were using a failing link or node may lead to a high number of simultaneous new path set-ups. The establishment in parallel of multiple new connections through alternate routes takes time and usually disrupt the connections at the end user level.
In view of the above, it appears that while optimizing the network traffic capacity is a must from a cost efficiency viewpoint, any link or node failure may generate an important control traffic load by itself, that may paralyze the network. Some facilities such as the so-called spanning tree organization have been provided to optimize control traffic operation under such critical situations.
For more information on the Spanning tree operation, one may refer to the European Application 94480046.1, published Nov. 29, 1995 with the Number 0684716 and title "A Data Communication Network and Method for Operating said Network".
While control traffic flow has been improved with the above described arrangements, it may still suffer a major drawback from the fact that the number of simultaneous rerouting requests in case of link or node failure are undefined and may be very large. In the worst case, all these requests may use the same link and therefore require processing in the same node. The node may be unable to process such large amounts of requests and beyond a certain number of reroutings per second the node queue, devoted to the buffering of rerouting requests becomes overloaded, resulting into loosing requests messages, starting retry procedures and possibly leading to unacceptable delays on rerouting if not completely jamming the network.
In addition, when several links fail simultaneously (typically on node failure case) local topology database(s) may be unupdated. Some data used for rerouting connections are thus invalid. The rerouting mechanism shall then reconsider rerouting through links actually invalid, which contributes to further jamming the network with unnecessary control traffic.