Browse Prior Art Database

Routing Algorithm

IP.com Disclosure Number: IPCOM000125361D
Original Publication Date: 2005-Jun-20
Included in the Prior Art Database: 2005-Jun-20
Document File: 2 page(s) / 38K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

A routing algorithm is a key asset to any provisioning system. The provisioning system must be able to route information across the network at a moments notice considering the entire picture of the network as it continually evolves. The routing algorithm must take into account current network traffic, current network outages, current network capacity, and current network alarms. All of these attributes contribute to where in the network a customer circuit can be routed, and all of these attributes change on a continual basis. A good routing algorithm will find all routes between the two endpoints and compare each to determine which the best route is. In fig. 1 a graphical representation of a small network is shown. Each circle represents a node in the network, and each node is labeled with a number, their node identifier. Each line between two nodes represents a node pair group, which may contain one to many IDTs. A node may only be routed to another node by following node pair groups through other nodes. Adjacency List Representation of a Small Network This is an adjacency list representation of the same small network from fig. 1. An adjacency list of a network consists of two basic parts. First, there is a list of all of the nodes in the network, which will be saved as a list of NodeFootprint's inside of the AdjacencyList entity. Second, each NodeFootprint will contain, among other information, a list of all adjacent nodes in the network, which will be saved as a list of NpgFootprint's inside of each NodeFootprint. Each NpgFootprint contains a node identifier, which is the destination node of the node pair group.

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 55% of the total text.

Page 1 of 2

S

Routing Algorithm

Idea: John Blackford, US-Dallas, Texas; Paul Arceneaux, US-Dallas, Texas

A routing algorithm is a key asset to any provisioning system. The provisioning syste route information across the network at a moments notice considering the entire picture of the as it continually evolves. The routing algorithm must take into account current network network outages, current network capacity, and current network alarms. All of the

m must be able to

         network traffic, current se attributes s change dpoints and

       wn. Each circle represents a node in the r, their node identifier. Each line between two nodes ly be routed to

                                     adjacency list of a ere is a list of all of the nodes in the network, which will be Footprint's inside of the AdjacencyList entity. Second, each NodeFootprint will ill be saved as a e identifier,

    h algorithm, which is used to search g used here performs an exhaustive search encountered.

pRoute).

the NodeFootprints and add it to the temporary route object.

.

as at least one NodeFootprint in its list

etter than bestRoute, then copy the tmpRoute

he tmpRoute list and continue looping.

                 d, then remove the NpgFootprints that caused the problem from priate NodeFootprints and restart the process from step 5.

8. Otherwise, an acceptable route could not be identified.

Recursive Function: accepts: last NodeFootprint, tmpRoute and AdjacencyList, returns completedRoute.

1. If the last NodeFootprint on the tmpRoute list is the NodeFootprint that was saved off as the last node in the route, then return the tmpRoute

2. Otherwise

2.1. If the last NodeFootprint on the tmpRoute list has at least one unencountered NpgFootprint, then

contribute to where in the network a customer circuit can be routed, and all of these attribute on a continual basis. A good routing algorithm will find all routes between the two en compare each to determine which the best route is.

In fig. 1 a graphical representation of a small network is sho network, and each node is labeled with a numbe represents a node pair group, which may contain one to many IDTs. A node may on another node by following node pair groups through other nodes.

Adjacency List Representation of a Small Network

This is an adjacency list representation of the same small network from fig. 1. An network consists of two basic parts. First, th saved as a list of Node contain, among other information, a list of all adjacent nodes in the network, which w list of NpgFootprint's inside of each NodeFootprint. Each NpgFootprint contains a nod which is the destination node of the node pair group.

Recursive Routing Algorithm

The routing algorithm is a version of the Depth First Se...