Method for preempting connections in high speed packet switching networks
First Claim
1. For use in a multi-priority packet switching network having a plurality of nodes interconnected with links carrying multiple traffic connections wherein existing connections are each assigned a priority level and said priority levels are assigned to groups of consecutive priority levels, a method for determining whether to establish a connection on a given path through the network from an originating node to a destination node through at least one intermediate node, the given path being proposed in response to a requested connection, said method comprising the steps of:
- at each intermediate node in the network, for each group on each outgoing link from said intermediate node having at least two existing connections, assigning the priority levels of the existing connections in said group to one of two or more subgroups and communicating the subgroup definitions to other nodes in the network;
at the originating node,for each link on the given path, determining whether the bandwidth requirements for a requested connection can be satisfied, in sequence,from free bandwidth,from bandwidth already allocated for existing connections having priority levels assigned to lower priority groups than the group including the priority level of the requested connection, andwhere the subgroup including the priority level of the requested connection is not the lowest subgroup in its group as determined by subgroup definitions communicated from an intermediate node, from bandwidth already allocated to existing connections having priority levels assigned to lower subgroups in its group; and
where bandwidth requirements can be satisfied in accordance with the preceding step for every link on the given path, preempting existing connections as necessary to reassign bandwidth to the requested connection, otherwise rejecting the requested connection.
3 Assignments
0 Petitions
Accused Products
Abstract
High speed network nodes can establish new connections by preempting existing ones when insufficient bandwidth is available in the network. Numerous preemption priorities are arranged in a limited number of groups and a median priority level is defined within each group. This median, stored in the topology database of each node of the network, permits better bandwidth utilization per group while consuming very little memory space and generating very low traffic overhead.
354 Citations
8 Claims
-
1. For use in a multi-priority packet switching network having a plurality of nodes interconnected with links carrying multiple traffic connections wherein existing connections are each assigned a priority level and said priority levels are assigned to groups of consecutive priority levels, a method for determining whether to establish a connection on a given path through the network from an originating node to a destination node through at least one intermediate node, the given path being proposed in response to a requested connection, said method comprising the steps of:
-
at each intermediate node in the network, for each group on each outgoing link from said intermediate node having at least two existing connections, assigning the priority levels of the existing connections in said group to one of two or more subgroups and communicating the subgroup definitions to other nodes in the network; at the originating node, for each link on the given path, determining whether the bandwidth requirements for a requested connection can be satisfied, in sequence, from free bandwidth, from bandwidth already allocated for existing connections having priority levels assigned to lower priority groups than the group including the priority level of the requested connection, and where the subgroup including the priority level of the requested connection is not the lowest subgroup in its group as determined by subgroup definitions communicated from an intermediate node, from bandwidth already allocated to existing connections having priority levels assigned to lower subgroups in its group; and where bandwidth requirements can be satisfied in accordance with the preceding step for every link on the given path, preempting existing connections as necessary to reassign bandwidth to the requested connection, otherwise rejecting the requested connection. - View Dependent Claims (2, 3, 4, 5)
-
-
6. In a multi-priority packet switching network having a plurality of nodes interconnected with links carrying multiple traffic connections wherein each connection is assigned a priority level and said priority levels are assigned to groups of consecutive priority levels, a system for determining whether to set up a requested connection on a given path through the network from an originating node to a destination node through at least one intermediate node, said system including:
-
subgroup creating means at each intermediate node for assigning, for each priority group on each outgoing link having at least two existing connections on the link, the priority levels of the existing connections to one of two or more subgroups and for communicating the subgroup definitions to other nodes in the network; at the originating node, bandwidth allocation means for determining for each link on the given path, whether the bandwidth requirements for the requested connection can be satisfied, in sequence, from free bandwidth, from bandwidth already allocated for existing connections having priority levels assigned to lower priority groups than the group including the priority level of the requested connection, and where the subgroup including the priority level is not the lowest subgroup in its group as determined by subgroup definitions communicated from an intermediate node, from bandwidth already allocated to existing connections having priority levels already assigned to lower subgroups in its group; and connection control means responsive to a determination that bandwidth requirements can be satisfied for every link on the given path in accordance with the preceding step, to preempt existing connections as necessary to reassign bandwidth to the requested connection and then to establish the requested connection or, where bandwidth requirements cannot be satisified, to reject the requested connection. - View Dependent Claims (7)
-
-
8. In a multi-priority packet switching network having a plurality of nodes interconnected with links carrying multiple traffic connections wherein each connection is assigned a priority level and said priority levels am assigned to groups of consecutive priority levels, a system for determining whether to set up a requested connection on a given path through the network from an originating node to a destination node through at least one intermediate node, each intermediate nodes including means for assigning, for each priority group on each outgoing link from the intermediate node having at least two existing connections on the link, the priority levels of the existing connections to one of two or more subgroups and for communicating the subgroup definitions to other nodes in the networ, said system being implemented an an originating node and including:
-
bandwidth allocation means for determining for each link on the given path, whether the bandwidth requirements for the requested connection can be satisfied, in sequence, from free bandwidth, from bandwidth already allocated for existing connections having priority levels assigned to lower priority groups than the group including the priority level of the requested connection, and where the subgroup including the priority level is not the lowest subgroup in its group as determined by subgroup definitions communicated from an intermediate node, from bandwidth already allocated to existing connections having priority levels already assigned to lower subgroups in its group; and connection control means responsive to a determination that bandwidth requirements can be satisfied for every link on the given path in accordance with the preceding step, to preempt existing connections as necessary to reassign bandwidth to the requested connection and then to establish the requested connection or, where bandwidth requirements cannot be satisified, to reject the requested connection.
-
Specification