Browse Prior Art Database

Efficient Systems Network Architecture Routing Table Contention Graph Computation

IP.com Disclosure Number: IPCOM000115646D
Original Publication Date: 1995-Jun-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 71K

Publishing Venue

IBM

Related People

Hantler, S: AUTHOR [+2]

Abstract

In Systems Network Architecture (SNA) networks, communication controllers and other switching hardware elements use routing tables to direct network traffic. Each element must switch arriving traffic based only on an Explicit Route Number (ERN) and destination number contained in the message header, plus the information in the routing table. In order to build these tables, an ERN must be assigned to each direction of each route. Any high-quality procedure for determining these assignments must construct one graph for each destination, where each directed route to that destination is represented by a distinct node, and two nodes are connected by an undirected edge iff the routes they represent cannot be assigned the same ERN.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Efficient Systems Network Architecture Routing Table Contention Graph
Computation

      In Systems Network Architecture (SNA) networks, communication
controllers and other switching hardware elements use routing tables
to direct network traffic.  Each element must switch arriving traffic
based only on an Explicit Route Number (ERN) and destination number
contained in the message header, plus the information in the routing
table.  In order to build these tables, an ERN must be assigned to
each direction of each route.  Any high-quality procedure for
determining these assignments must construct one graph for each
destination, where each directed route to that destination is
represented by a distinct node, and two nodes are connected by an
undirected edge iff the routes they represent cannot be assigned the
same ERN.  Straightforward procedures for constructing this graph are
known, but their complexity is quadratic in the number of routes to a
destination.  This disclosure describes a graph construction process
whose complexity is max( E, K log K ), where E is the number of edges
in the graph, and K is the number of routes to a destination.

      For the set of all routes to a given destination, create the
route adjacency graph G as follows:
  1.  Construct matrix M(i)(j) whose rows M(1) M(2) M(3)... represent
       all the routes to a common destination D. M(i) is a list of
the
       indices of the directed links contained in route i to
destination
       D.  Associated with each link index is a link origin and link
       destination.  The link indices M(i)(1) M(i)(2) M(i)(3)... are
       ordered from destination to origin as the links appear in the
       route, i.e. if route i contains k links then the origin of
link
       M(i)(k) is the route origin, and the destination of link
M(i)(1)
       is the route destination.
  2.  Make all the rows of M the same length by appending null
indices,
       as needed,...