Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-11-17
2001-06-12
Ngo, Ricky (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S257000, C370S400000
Reexamination Certificate
active
06246669
ABSTRACT:
FIELD OF INVENTION
The present invention deals with high speed packet switching networks and more particularly with a method and system for improving said network operation by enabling efficient path selection and connection set-up operations.
BACKGROUND OF THE INVENTION
A data communications network can generally be defined as a collection of network nodes and access nodes interconnected through communication links. A network node is generally a high cost data processing system that provides certain functions within the network, such as routing of messages (generally in the form of data packets) between itself and neighboring nodes, selection and optimization of routes for messages to be transmitted within the network and furnishing directory services to locate resources. Comparatively, access nodes are low cost data processing systems, offering to attached users a high level of access services but providing a limited set of routing, path selection and directory services. The links between nodes may be permanent communications links such as conventional cable connections or links that are enabled only when needed, such as dial-up connections through public or private telephone systems.
The number of access nodes in a network is expected to be much greater than the number of network nodes. Collectively, the network nodes, the access nodes and the links between the nodes are referred to as network resources. The physical configuration and characteristics of the network resources are said to be the topology of the network.
Route management is the network layer protocol that guides packets to their correct destination. Two aspects have to be considered:
1. determining what the route for a given connection shall be;
2. actually switching (routing) the packet within a node. This aspect is particularly critical in high speed packet switching networks since the switching element must be able to decide where to route an incoming packet in a very short portion of time.
There are many methods to route a packet through a network. A first method can be called “dynamic node by node routing”. With this method there is no route determined when the connection is set up. This is due to the fact that there is no connection. Each packet is sent into the network with its full destination address imbedded in the header. Each node knows the current network topology and loading and is able to decide where and on which path the packet should be directed. This process, even if it can be very fast is a software based technique. It is very difficult to see how it could be efficiently implemented in hardware. Packet rates of millions per second are not likely to be achieved by this method very soon.
This is the reason why, for high speed packet switching networks, another method named “source routing” is chosen preferably. In the source routing method the originating node is responsible for calculating the route the packet must take through the network. A routing field is appended to every packet sent and that field is used by the intermediate nodes to direct the packet towards its destination. The sending node must either know the network topology or it must use some method (such as broadcasting) to find the optimal route. But once the route is determined, intermediate switches do not need to refer to any system tables or parameters to make the routing decision. Depending on whether the network is “connection oriented” or “connectionless”, two techniques are used. The first one, used in connectionless networks, consists in appending a routing vector to every packet sent and that vector is used by intermediate nodes to route the packet towards its destination. A drawback of this technique is that the routing vector requires some storage and so constitutes an overhead. This overhead may become unacceptable for a high speed real time network. This is the reason why another technique named “label swapping” is regarded by many as an appropriate technique for supporting source routing in high speed networks. The label swapping is a particular implementation of the source routing method for connection oriented networks. Each packet sent on the link has a header which includes an arbitrary number (called label) identifying which logical connection this packet belongs to. In such networks the call setup and the resource reservation process requires first that a connection be requested from a calling source to a target destination, then a route should be defined and finally reserved. The connection request is specified by the user via a set of parameters including origin and destination address and data flow characteristics. The route determination is realized by the source node using its local routing topology database. And finally the route reservation is sent out in a special message along the nodes specified during the route determination process. That message signals the intermediate nodes to set up their connection tables and to reserve their resources to provide the service level required by the connection request. The connection is then said to be set up.
It shall be noticed that a good source routing mechanism in large and high speed packet switching networks supporting connection oriented routing mode implies some requirements in terms of performance and resource consumption which can be summarized as follows:
The source node (or the node providing calculation for the source node) must be able to decide where to route an incoming connection in a very short period of time (the computation must be rapid enough to compute an optimum path for each connection request); this is a major requirement.
The switching time in the intermediate nodes must be minimized (minimum processing time).
The network resources along the selected path must be optimized according to user criteria.
Control messages must be limited as much as possible to avoid overloading the network.
Route determination and topology maintenance within a network typically involve a rather complex collection of algorithms that work more or less independently and yet support each other by exchanging services or information. The complexity is due to a number of reasons. First, it requires coordination between all the nodes rather than just a pair of nodes. Second, the routing algorithm must cope with link and node failures, requiring redirection of traffic and updates of the databases maintained by the system. Third, to achieve performance, it may need to modify its routes when some areas within the network become congested.
The subject invention focuses on the way to generate and maintain routing-related information even in case of link and node failures to all access nodes within a network, while minimizing processing time and software and hardware required.
Different methods including the so-called flooding mechanism and spanning tree mechanism are used to broadcast and maintain routing information within a network. Let's examine first the flooding mechanism, then the use of a spanning tree. Then we shall take a look at the way IBM Advance Peer-to-Peer Networking architecture (APPN) has solved the route determination issue in a network composed of network nodes and access nodes.
As shown in
FIG. 1A
the flooding method operates as follows. The origin node (e.g. node A) sends its information in the form of a packet to its neighbors (the nodes to which it is directly connected with a link). The neighbors relay it to their neighbors, and so on, until the packet reaches all nodes in the network. Two additional rules are also observed, which limit the number of packet transmissions. First, a node will not relay the packet back to the node from which the packet was obtained. Second, a node will transmit the packet to its neighbors at most once. This can be ensured by including in the packet the identification(ID) number of the origin node, a sequence number, which is incremented with each new packet issued by the origin node. By storing the highest sequence number received for each origin node, and by not relaying packets with sequence numbers tha
Bazot Philippe Michel
Bertin Olivier
Chevalier Denis Jean Albert
Chobert Jean-Paul
Levy-Abegnoli Eric
Cesari and McKenna LLP
Cisco Technology Inc.
Johnston A. Sidney
Ngo Ricky
LandOfFree
Method and system for optimizing connection set-up... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for optimizing connection set-up..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for optimizing connection set-up... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2507925