Browse Prior Art Database

Establishing Virtual Circuits in Large Computer NETWORKS

IP.com Disclosure Number: IPCOM000059711D
Original Publication Date: 1986-Jan-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 4 page(s) / 59K

Publishing Venue

IBM

Related People

Baratz, AE: AUTHOR [+3]

Abstract

This article describes an approach to economically obtain shortest path communication even in very large computer networks. 1.INTRODUCTION One of the most fundamental decisions faced in designing a data communication network is the choice of a routing technique. While dynamic routing gives the best performance, the dynamic determination of optimal paths is costly, and unacceptably costly for large networks. This is because of large storage and bandwidth costs. There are several approaches that have been proposed to cope with or solve the apparent incompatibility between the goals of shortest path routing and the realities of large networks. The following describes an approach that economically provides shortest paths even in large networks. 2.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 27% of the total text.

Page 1 of 4

Establishing Virtual Circuits in Large Computer NETWORKS

This article describes an approach to economically obtain shortest path communication even in very large computer networks. 1.INTRODUCTION One of the most fundamental decisions faced in designing a data communication network is the choice of a routing technique. While dynamic routing gives the best performance, the dynamic determination of optimal paths is costly, and unacceptably costly for large networks. This is because of large storage and bandwidth costs. There are several approaches that have been proposed to cope with or solve the apparent incompatibility between the goals of shortest path routing and the realities of large networks. The following describes an approach that economically provides shortest paths even in large networks. 2.THE SHORTEST PATH TABLES The shortest path tables required by this new architecture are similar to those described in [1]. The nodes of a network are logically partitioned into clusters and each node maintains a shortest path table containing entries for every node in the same cluster as itself. In addition, each table contains some representation of every other cluster in the network. In [1], this representation takes the form of a single-table entry for each remote cluster. In this new scheme, however, there will be exactly one entry for each node on the boundary of a remote cluster. A more precise description of this table structure follows. A one-level clustering of a network is simply a partition of its node set into disjoint subsets with each such subset called a cluster. For the remainder of this description, each link connecting nodes in the same cluster will be called an intra-cluster link, and each link connecting nodes in different clusters will be called an inter-cluster link. Furthermore, any node to which an inter-cluster link is connected will be called a border node, and all other nodes will be called internal nodes (Fig. 1). Any path composed entirely of intra-cluster links will be called an intra-cluster path. It is now a fairly simple matter to formalize the structure of the shortest path tables required by the new routing scheme. Given a network and a one-level clustering of this network, each node must maintain a shortest path table containing one entry for every node in the same cluster as itself, and one entry for every node which is a border node under the given clustering. Each such entry will include the node name, the status (internal or border) of the node, the weight of the shortest path to this node, and the next node along this shortest path. Fig. 2 illustrates this table structure for node 3.5 in Fig. 1. Since each border node appears in the tables of every node in the network, the border node entries can be easily maintained by any of the well known distributed shortest path algorithms !2,3,41. The result will be shortest path tables containing the weight and the next node along the current shortest path...