Each network node in a communications network maintains its own copy of the network topology database defining network resources. Each resource record contains a "timer" field which is initially set to a maximum value but which may be decremented on a daily basis. If the timer field is decremented to zero without being reset, the node unilaterally removes the resource record from its copy of the database. The timer field will normally reach zero only for obsolete resource records since each network node responsible for a resource broadcasts a timer-resetting message for the resource (1) each time the resource status changes, (2) when the node first joins or rejoins the network, and (3) on a periodic (weekly) basis regardless of whether conditions (1) or (2) have occurred.
In a packet communications network, the addition or deletion of a connection to the network by a user is governed by a link traffic metric which represents the effective capacity of each link in the network which participates in the packet connection route. The link metric is calculated in real-time and updated by simple vector addition or subtraction. Moreover, this link metric is also used to calculate leaky bucket parameters which govern the access of packets to the network once the connection is set up. A packet network using these link metrics and metric generation techniques provides maximum packet throughput while, at the same time, preserving grade of service guarantees.
A congestion control system for packet communications networks in which access to the network is controlled to prevent such congestion. Packets within the prespecified statistical description of each packet source are marked as high priority ("green" packets) while packets exceeding the pre-specified characteristics are marked with a lower priority ("red" packets). The overall red packet rate is limited to prevent red packet saturation of the network. Packets are marked red for a continuous train of successive red packets. The introduction of red packets into the network is subjected to a degree of hysteresis to provide better interaction with higher layer error recovery protocols. The amount of hysteresis introduced into the red packet marking can be fixed or varied, depending on the statistics of the incoming data packets at the entry point to the network.
A packet communications system provides for point-to-point packet routing and multicast packet routing to limited subsets of nodes in the network, using a routing field in the packet header which is processed according to two different protocols. A third protocol is provided in which a packet can be multicast to the limited subset even when launched from a node which is not a member of the subset. The routing field includes a first portion which contains the route labels necessary to deliver the packet to the multicast subset. A second portion of the routing field contains the multicast subset identifier which can then be used to deliver the packet to all of the members of the multicast subset. Provision is made to backtrack deliver the packet to the last node identified before the multicast subset if that last node is itself a member of the subset.
A packet communications system utilizes a route determining mechanism by identifying principal paths between the source and the destination in the system. Principal paths are minimum hop count paths with a transmission delay less than a specified threshold. Principal path links are accepted as legs of the optimum path, if feasible, i.e., if the resulting load on the link is less than a specified principal threshold. Secondary links are accepted only if the resulting load on the link is less than a specified secondary threshold, where the secondary threshold is less than the principal threshold. All paths must also have a transmission delay less than a specified threshold. Each request for a route includes the source node, the destination node, the load required, the maximum transmission delay and, if desired, the quality of service parameters which all of the legs of the route must satisfy. A modified Bellman-Ford breadth-first search algorithm is used to identify the principal links and, using these principal link identifications, determining the optimum path.
A network database. The network database is arranged in a plurality of domains in a logical hierarchy. Each domain of the hierarchy represents a body of information associated with a logically related group of users or related group of computers. A relative naming scheme is implemented in which a domain stores the names of only its parent domain and child domains. This permits reconfiguration of the network to be accomplished without changing the database structure. Each domain stores information in a hierarchical structure known as a "directory." Each directory consists of a list of zero or more "properties," each having an associated name and ordered list of values.
