Hop-by-hop routing with node-dependent topology information

Details Hop-by-hop routing with node-dependent topology information Hop-by-hop routing with node-dependent topology information

1999-03-20

2003-11-11

Hsu, Alpus H. (Department: 2665)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S238100, C370S254000, C370S400000, C709S241000, C709S238000, C709S243000

Reexamination Certificate

active

06646989

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to communication networks, and more particularly, to hop-by-hop routing in which different network nodes have different views of the network topology.
BACKGROUND OF THE INVENTION
Networks are the principal means of exchanging or transferring information, which may be in the form of data, voice, text, video and the like, among different communication devices connected to the network(s), including I/O devices such as computer terminals, multimedia workstations, fax machines, printers, servers, telephones, videophones, and the like. A network typically comprises switching nodes connected to each other and to communication devices by communication links. Each link is characterized by link capacity, available bandwidth, link propagation delay, processing delay at the associated node, delay variation, and loss probability, among other things. Such characteristics are referred to as “metrics,” with some remaining constant, and others varying over time. Information input from the communication devices to the network may be in any form, but is often formatted into packets of either fixed or variable length. When information is to be exchanged between two communication devices, a path is established within the network connecting the nodes (called a source node and destination node) with which those devices are associated.
In many networks, a given communications stream between a specified source and destination is carried over a set of physical paths (i.e., paths comprising the source and destination nodes, and possibly one or more intermediate nodes, and communication links connecting the included nodes) within the network. An important element of network design is the process of selecting a set of physical paths for routing information through the network. This process may take into account various factors, such as network topology, currently available network resources, and quality of service (QoS) commitments made to network users, e.g., guaranteed bandwidth or maximum packet delay, among others. To support path selection, different network nodes maintain information about the network, including node adjacency and link incidence, reachability of different nodes, as well as various other link metrics. This information is stored in a so-called “topology database” of the node and constitutes the node's view of the network.
The routing of information packets from a source node to any other node in the network or a segment of the network, in which all nodes have the same view of the network topology is well established. Two existing routing paradigms in such networks are source routing and hop-by-hop routing. In source routing, the entire route taken by a packet from source to destination may be pre-computed and placed on the packet. As the packet is passed from the first node to a second node, the second node strips its address from the pre-specified route and passes the packet to the next node indicated in the packet header. In the alternative routing technique of hop-by-hop routing, no pre-computed route is employed. Each packet contains only the destination address. Upon receiving a packet, each intermediate node refers to its routing table, computed on the basis of its topology database, to forward the packet along the next hop towards the destination node.
Well-known methods, such as Dijkstra's shortest path algorithm, have been developed, which given the single static view of the network, determine under fairly general conditions the shortest routing path between any two network nodes. However, if different network nodes have different views of the network topology, such algorithms cannot guarantee loop-free and effective routing.
Recently, the focus in network routing has shifted, however, toward dynamic or state-adaptive routing. Beside reducing configuration work, such routing adapts quickly to changes in the available resources of the network and link failures. Several design solutions exist for dynamic routing in computer networks and are still under development, with distance vector and link-state protocol approaches being the ones well-known.
The basic idea of link state routing protocols is that each node sends local network topology information to its neighbors. This information is then propagated through the network using sophisticated “flooding” mechanisms. As the result, every node accumulates the view of the entire network in its topology database. The generation and flooding of information is repeated each time a node sees a significant change in available local resources. The distributed pieces of topology information, link state up-dates (LSU) or link state elements (LSE), carry a unique identifier and a version number increasing when the information inside of such an LSU is changing. Additionally, to prevent this process from being triggered too often, a dampening function controls the thresholds holding back non-significant changes. The topology database resulting from the execution of this latter “flooding” mechanism between nodes is used to compute routes to the desired destinations. Such routes are used, for example, in hop-by-hop forwarding of packets. The distance vector approach is based on a significantly different idea. Each node continuously diffuses information about the distances to different network sites reachable via that node. At the same time, it uses data received from other nodes and metrics of its own links to recompute the set of best routes, thus updating the distance information it distributes.
Despite the simplicity of the latter protocols, they are plagued by problems, such as long convergence times, forming of loops and lack of scalability in terms of topology sizes supported. Research is being performed to alleviate some of the problems. It should be noted that these link-state protocols also suffer from excessive amount of information being flooded in larger topologies. Therefore, newer link-state routing protocols incorporate a concept of “hierarchy,” where a part of the network running a link-state protocol collapses into a logical node in the view of distant nodes, and between such logical nodes, sometimes called areas, where some form of distance vector protocol is being executed.
Modern routing protocols, such as PNNI, are following the trend toward extensibility for future requirements, which abandon fixed packet formats and use TLV (type, length, value)—encoded packet schemes. The “type” describes the fixed part of the TLV transmitted and the “length” indicates the offset in the packet where the next TLV starts. In cases where the length exceeds the length of the fixed part of the TLV, embedded TLVs are present. Generally, TLV encoded packets transferring topology information in modern routing protocols can be interpreted as representations of lists of arbitrary elements embedded themselves in a recursive fashion into lists at a higher level.
An additional property of many of the prior art routing protocols is their ability to flood information elements even if they are opaque to the receiver since their type is not known. This allows newer protocol versions to be introduced as well as experimental features in an existing network to be deployed without the necessity of bringing all the nodes synchronously to the same release. To operate properly, guaranteeing packet delivery to the destination without creating loops, the link-state and distance vector protocols require that the topology databases of different network nodes converge to the same view of the network. In the networks deployed so far, however, different versions of link-state protocols cannot interoperate when new metrics or novel link properties are introduced, unless a translation between them is performed. Furthermore, network topologies are traditionally partitioned into disjoint domains corresponding to different routing protocols due to the possibility of loop creation.
SUMMARY OF THE INVENTION
The present invention presents a method to effect hop-by-hop routing in a network segment where different nodes h

Affiliated with

Also associated with

Rating

Hop-by-hop routing with node-dependent topology information does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hop-by-hop routing with node-dependent topology information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hop-by-hop routing with node-dependent topology information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3159990