Network Feasibility Algorithm and Class of Service Generation in Advanced Peer-To-Peer Networks
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Described is an algorithm to provide network feasibility and to create class of service (COS) table in Advanced Peer-to-Peer Networks (APPNs). The concept provides a means whereby an APPN router can find a feasible routing for the traffic.
Network Feasibility Algorithm and Class of Service
Advanced Peer-To-Peer Networks
an algorithm to provide network feasibility
and to create class of service (COS) table in Advanced Peer-to-Peer
Networks (APPNs). The concept provides a means whereby an APPN router
can find a feasible routing for the traffic.
An APPN is
defined by a pair of tables. One table
weights to the links and the other table gives weights to the nodes.
When a session assigned to the COS is established, a randomized
shortest path algorithm is used to compute the shortest route from
source to destination. In the case of ties, it uses randomization to
spread the load. The tables use the characteristics of the links and
nodes to give them weights. However, incorrect routing choices can
be made. The concept described herein addresses the problem of
creating a COS for a given network design and how to change the
design if a COS cannot be found which routes the traffic.
network design algorithms consist of two steps:
finding a spanning tree; and adding links if justified, otherwise
flow the traffic onto the tree. As links are added, a routing is
computed implicitly. However, the routing may not be feasible for an
APPN network. As a result, APPN balancing is necessary and involves
two operations: a) giving each link a weight and b) adding capacity
to the network if the algorithm for giving weights cannot bring the
network into balance by bringing the link traffic under the design
balancing is complicated since the implementation of APPN
allows the COS function to give a link or transmission group (TG) one
of eight finite weights, or a weight of infinity. Thus, APPN
balancing becomes a complicated combinatorial problem. If each link
weight can be one of eight finite weights of infinity, then a network
with 2n transmission groups will have 92n possible weightings. In
APPN, links are unidirectional and a physical link can have different
weights in opposite directions. To see if a network can be balanced
with a set of eight weights, a search must be made through all 92n
values. The solution space for any choice of eight values will be
unreasonably large for even modest networks. Even if the optimum is
found by brute force, there could be another set of eight values
which give a better solution.
described herein centers on the good choices for
the eight weights and a good heuristic for changing the weights to
balance the flow and to add capacity to the network in the event it
is impossible to correct the balances by adjusting the weights.
weight assignment uses the fact that underlying the
design is a tree. Each tree link is given a weight "a", with a>0 and
for the purpose of this discussion will be assigned a=10. Each
additional link connects two nodes. The tree distance between the
two nodes is define...