EP0629065A2 - Verkehrsverwaltung in Paketkommunikationsnetzen - Google Patents

Verkehrsverwaltung in Paketkommunikationsnetzen Download PDF

Info

Publication number
EP0629065A2
EP0629065A2 EP94480039A EP94480039A EP0629065A2 EP 0629065 A2 EP0629065 A2 EP 0629065A2 EP 94480039 A EP94480039 A EP 94480039A EP 94480039 A EP94480039 A EP 94480039A EP 0629065 A2 EP0629065 A2 EP 0629065A2
Authority
EP
European Patent Office
Prior art keywords
traffic
link
connection
variable
node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP94480039A
Other languages
English (en)
French (fr)
Other versions
EP0629065A3 (de
Inventor
Levent Gun
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of EP0629065A2 publication Critical patent/EP0629065A2/de
Publication of EP0629065A3 publication Critical patent/EP0629065A3/de
Withdrawn legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L12/5602—Bandwidth control in ATM Networks, e.g. leaky bucket
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/123—Evaluation of link metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/26—Route discovery packet
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/302—Route determination based on requested QoS
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/302—Route determination based on requested QoS
    • H04L45/306—Route determination based on the nature of the carried application
    • H04L45/3065—Route determination based on the nature of the carried application for real time traffic
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
    • H04Q11/0478—Provisions for broadband connections
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5619—Network Node Interface, e.g. tandem connections, transit switching
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5629—Admission control
    • H04L2012/5631—Resource management and allocation
    • H04L2012/5632—Bandwidth allocation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5638—Services, e.g. multimedia, GOS, QOS
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5638—Services, e.g. multimedia, GOS, QOS
    • H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
    • H04L2012/5651—Priority, marking, classes

Definitions

  • This invention relates to packet communications networks and, more particularly, to rapid and efficient traffic control in such networks by accurately modeling traffic behavior and accounting for traffic loading in the network.
  • Bandwidth management in modern high speed packet communications networks utilizes connection level controls applied at the time the connection is set up based on the load characteristics of the transmission links in the connection route at the time that the connection is set up.
  • connection level controls include bandwidth allocation, path selection, admission control and call setup.
  • Bandwidth allocation is accomplished by noting, at the connection setup time, the "equivalent capacity" loading that the new connection will generate, based on the traffic characteristics of the source signal and the desired quality of service. Using this equivalent capacity as the bandwidth that must be available to carry the new connection, the originating node of the network computes a path to the destination node that is capable of carrying the new connection and providing the level of service required by the new connection.
  • This path selection process utilizes data describing the current state of the traffic in the entire network.
  • Such data can be stored in a topology database located at each entry point, and, indeed, at each node, of the network. If no suitable path can be found to meet these requirements, the connection is rejected. Once a suitable path has been selected at the entry node, a setup message is generated which traverses the selected route, updating the resource allocations for each link visited by the setup message. Due to race conditions, simultaneous requests for setup, or unknown changes in the link resource allocation, the attempt to set up the call may fail because of the lack of necessary resources at the time the call setup message reaches a node along the route.
  • each connection level control process i.e., initial bandwidth allocation, route selection and call setup, requires adequate network resources to carry the call. A failure at any point in any of these control processes results in the call being rejected, thus preventing the launching of packets likely to cause network overload.
  • connection level controls operate correctly at all times. Furthermore, in order to efficiently accommodate connections for data streams with widely different characteristics, it is important to allocate bandwidth for each connection with a metric which is readily computable, easily updated and capable of capturing all of the significant characteristics of the highly diversified traffic. Moreover, this metric must also be used to characterize the accumulated transmission link traffic load due to all of the individual connections on that link, determined by a simple additive process from the individual connection vectors. An easily calculated additive metric to characterize traffic on a network is a critical factor for efficient traffic control in the network.
  • the algorithm for computing link metrics disclosed in the above-identified patent application is computationally efficient, readily allowing for real-time updates of the link metric vectors while, at the same time, accounting reasonably well for the relationship between the link bandwidth and the connection characteristics. This algor ithm also preserves the incremental nature of the link metric updates so that information on the individual connections need not be maintained in the network topology database.
  • a different link metric is used for each different class of traffic, allowing each class of traffic to be more accurately modeled by its own link metric and, even more importantly, permitting the interplay of the different priority traffic to be occurately modeled.
  • This more accurate modeling of the interplay of different traffic classes significantly increases the possible throughput of the links of the network thereby significantly increasing the efficiency of the network.
  • the ability to model real-time and non-real-time traffic with different link metrics permits the optimization of the non-real-time traffic throughput by modifying the non-real-time metrics depending on the real-time traffic level. That is, the priority rules which guarantee the transmission of real-time traffic independent of the level of non-real-time traffic permits a much higher level of non-real-time traffic than would be possible with a single traffic metric which does not take the priority rules into account in controlling traffic levels.
  • the multiple link metrics of the present invention continue the advantage of the prior art copending application of permitting real-time incremental updates of all link metrics by simple vector addition and subtraction.
  • a connection request with the metrics for the new connection is propagated along the selected route for the connection.
  • the metric in the connection message is used to update the link metrics for the next link in the route.
  • both the real-time metric and the non-real-time metrics for the next link are updated.
  • new non-real-time connections only the non-real-time link metrics must be updated.
  • New real-time connections are accepted only if both the resulting real-time and non-real-time link occupancies are less than the effective maximum link capacity.
  • New non-real-time connections are accepted, however, if the resulting non-real-time link occupancy is less than the effective link capacity, regardless of the real-time occupancy.
  • the strategy of utilizing two or more different link metrics permits the low priority traffic to be increased sufficiently to absorb almost all of the idle time left due to the bursty nature of the high priority traffic, any yet be able to guarantee the prescribed class of service for such high priority traffic.
  • FIG. 1 there is shown a general block diagram of a packet transmission system 10 comprising eight network nodes 11 numbered 1 through 8.
  • Each of network nodes 11 is linked to others of the network nodes 11 by one or more communication links A through L.
  • Each such communication link may be either a permanent connection or a selectively enabled (dial-up) connection.
  • Any or all of network nodes 11 may be attached to end nodes, network node 2 being shown as attached to end nodes 1, 2 and 3, network node 7 being shown as attached to end nodes 4, 5 and 6, and network node 8 being shown as attached to end nodes 7, 8 and 9.
  • Network nodes 11 each comprise a data processing system which provides data communications services to all connected nodes, network nodes and end nodes, as well as providing decision points within the node.
  • the network nodes 11 each comprise one or more decision points within the node, at which point incoming data packets are selectively routed on one or more of the outgoing communication links terminated within that node or at another node. Such routing decisions are made in response to information in the header of the data packet.
  • the network node also provides ancillary services such as the calculation of new routes or paths between terminal nodes, the provision of access control to packets entering the network at that node, and the provision of directory services and topology database maintenance at that node.
  • Each of end nodes 12 comprises either a source of digital data to be transmitted to another end node, a utilization device for consuming digital data received from another end node, or both.
  • Users of the packet communications network 10 of FIG. 1 utilize an end node device 12 connected to the local network node 11 for access to the packet network 10.
  • the local network node 11 translates the user's data into packets formatted appropriately for transmission on the packet network of FIG. 1 and generates the header which is used to route the packets through the network 10.
  • connection request message to be launched from a source node in the network of FIG. 1 to a destination node in the network along a precalculated route.
  • the connection message of FIG.2 comprises a routing field 20 which includes the information necessary to transmit the connection message along the precalculated route.
  • a connection request vector 22 which characterizes the important statistical characteristics of the new packet source and which allows this new source to be statistically multiplexed with the previously existing signals on each link of the route.
  • the connection request vector 22 further includes a priority class (PC) subfield 24 containing a coded identification of the priority class associated with the new connection.
  • PC priority class
  • Priority subfield 24 may comprise a single bit if only two priority classes are used, or may comprise a larger field to accommodate a larger number of priority classes.
  • the connection request vector includes a relatively few parameters necessary to adequately characterize the packet source. As described in the copending application, EP Application No. 93480099.6 filed July 16, 1993, and assigned to applicant's assignee, these parameters might include the mean of the aggregate bit rate for the source, the variance of that bit rate from that mean, and the equivalent bandwidth required to carry the new connection. This copending application, however, required the same set of parameters to be used to characterize all packet sources connected to the network.
  • connection request vector 22 is customized for the class of packet source being represented, as identified by subfield 24.
  • Real-time signal sources for example, are represented by a set of parameters suitable for real-time signals while non-real-time signal sources are represented by a set of parameters more suitable for non-real-time signals.
  • the portion of the connection vector representing the estimated link bandwidth required to carry the connection can be tailored to reflect the relative priority of the particular signal source. As a result, the occupancy of the various links of the network of FIG. 1 can be increased significantly, and possibly even doubled, without sacrificing the quality of service for the higher priority packets.
  • connection request vector the values in the connection request vector are used to test each link of the route to determine if the new connection can actually be supported by that link, and to update, separately for each link, the link occupancy metric to reflect the addition of the new connection. If the link occupancy has changed since the route was calculated, the connection may be rejected at any node along the route, and the source node notified of the rejection.
  • the control fields 23 include additional information used in establishing the connection, but which are not pertinent to the present invention and will not be further discussed here. Note that, when a connection is to be taken down, a connection removal message having the same format as FIG. 2 is transmitted along the route of the connection to be removed. The link occupancy of each link is then updated to reflect the removal of this connection by subtracting the metrics for the removed connection.
  • FIG. 3 there is shown a general block diagram of a typical packet network decision point such as is found in the network nodes 11 of FIG. 1.
  • the decision point of FIG. 3 comprises a high speed packet switching fabric 33 onto which packets arriving at the decision point are entered. Such packets arrive over transmission links such as links A-L of FIG. 1 (or are originated locally), and are deposited in one of packet buffers 30, 31, ..., 32, depending on the priority classification of that particular packet. That is, it is assumed that the traffic handled by the packet communications system of FIG. 1 is divided into K different priority classifications. As previously noted, such classifications might include real time and non-real time traffic. System control packets might form another candidate for an even higher priority classification than user traffic.
  • Outgoing links 34 correspond to inter- node transmission links A-L of FIG. 1, extending to other nodes, or to local transmission facilities to one of the end nodes 12.
  • Each source of packets e.g., each incoming transmission link
  • one or more of the transmission links 34 can be connected to yet other packet decision points in the same node, thereby expanding the switching capacity of the node.
  • the decision point of FIG. 3 thus serves to connect the packets arriving at a decision point to a local user (for end nodes) or to a transmission link leaving the decision point (for network nodes and end nodes).
  • a route controller 37 is used to calculate optimum routes through the network for packets originating at a local end node. As previously noted, one technique for calculating optimum routes is disclosed in the copending application EP Application No. 93480030.1 filed March 23, 1993, and assigned to applicant's assignee.
  • Network access controllers 39 are used to regulate the launching of packets onto the network if the transient rate of any connection exceeds the values assumed in making the original connection, as disclosed in the afore-mentioned application EP Application No. 93480099.6 filed July 16,1993. Both route controller 37 and access controllers 39 utilize the link metric vectors in the connection request message of FIG.
  • Controller 37 utilizes link metric vectors representing the traffic on each link of the network, stored in topology data base 38, to calculate the connection route through the network.
  • Network topology data base 38 contains information about all of the nodes and transmission links of the network of FIG. 1, which information is necessary for controller 37 to operate properly.
  • the controllers 37 and 39 of FIG. 3 may comprise discrete digital circuitry or may preferably comprise properly programmed digital computer circuits. Such a programmed computer can be used to generate headers for packets originating at user inputs to the decision point of FIG. 3, or may modify headers of packets switched at the decision point to facilitate future routing. Similarly, the computer can also be used to calculate feasible routes for new connections and to calculate the necessary controls to regulate access to the network in order to prevent congestion.
  • the information in data base 38 is updated when each new link is activated, new nodes are added to the network, when links or nodes are dropped from the network or when link loads change due to the addition of new connections or the deletion of old connections.
  • Such information originates at the network node to which the resources are attached and is exchanged with all other nodes to assure up-to-date topological information needed for route and access control calculations.
  • Such data can be carried throughout the network on supervisory packets very similar to the information packets exchanged between end users of the network.
  • the incoming transmission links to the packet decision point of FIG. 3 may comprise links from local end nodes such as end nodes 12 of FIG. 1, or links from adjacent network nodes 11 of FIG. 1.
  • the decision point of FIG. 3 operates to receive each data packet and forward it on to another local or remote decision point as dictated by the information in the packet header.
  • the packet network of FIG. 1 thus operates to enable communication between any two end nodes of FIG. 1 without dedicating any transmission or node facilities to that communication path except for the duration of a single packet. In this way, the utilization of the communication facilities of the packet network is statistically optimized to carry significantly more traffic than would be possible with dedicated transmission facilities for each communication path.
  • FIG. 4 there is shown in tabular form a portion of the information stored in the data base 38 of FIG. 3.
  • a plurality of link metric vectors for each link of the network is stored in the data base, one link metric vector for each priority classification recognized in the network.
  • FIG. 4 shows two link metric priority classifications, real-time and non-real time. A larger number of priority classifications is, of course, possible, in which case separate link metrics for each classification must be stored in the topological data base of FIG. 4.
  • the link metric vectors are calculated as will be described below. As will also be described hereinafter, these link metric vectors are updated with the addition or deletion of each virtual connection through the network, and adjusted to reflect physical changes in the network. The use of the link metric vectors for call requests will be described in detail in connection with FIG. 5.
  • connections with possibly widely different characteristics e.g., peak rate, utilization, burst size
  • priority classification e.g., priority classification
  • the allocated bandwidth can be easily computed as new connections are added or removed.
  • the topology data base 38 of FIG. 3 maintains, for each link, a link vector in the form of equation (1). Furthermore, the bandwidth request vector for connection i is generated and transmitted in the form:
  • the link metric can now be updated by simple vector addition or subtraction, each time a network connection is added to or removed from that link. That is, in accordance with the prior patent application, a new link vector is obtained incrementally from the existing one by using L ⁇ L ⁇ r(i), where addition and subtraction are component-wise.
  • the present invention contemplates the substitution of multiple link metrics for the single linkmetric of the prior art copending application EP Application No. 93480099.6 filed Juiy 16, 1993. More specifically, the traffic is divided into a plurality of classes of signals having substantially different priorities. Two obviously different priority classifications are those ascribed to real-time and to non-real time traffic. Initially, only two classes of traffic priorities will be considered, corresponding to real-time and non-real-time traffic. Generalization to more than two classes of traffic will then be taken up.
  • D(k,pi,t) denotes the total workload of type k transmitted by time t
  • D(t) D(1, pi,t) + D(2, pi,t) holds for every in PI.
  • x(k, pi,t) denote the workload in the system at time t due to class k under any scheduling policy in PI.
  • the present invention utilizes separate link metrics, in the form given in equation (1), for each priority class be kept at each node, i.e., and
  • Equation (9) provides an upper bound to the required capacity to achieve the target loss probability from non-real-time buffers for any service policy.
  • the overflow probability from the non-real-time buffer is guaranteed to be within s(2). That is, the performance of the non-real-time traffic is guaranteed when its admission is based on the link vector L(2) of equation (8). This allows more non-real-time traffic to be placed on links even though the link is up to its reservable capacity R(link) according to the link vector L(1). Moreover, since the real-time packets have a higher transmission priority, their performance is always guaranteed as long as the condition is satisfied.
  • the call admission criterion for real-time traffic should also be based on L(2), i.e., the condition should also be satisfied.
  • the inequality (10) ensures that the loss probability from real-time buffer will stay within the target ⁇ (1).
  • the inequality (11) ensures that the loss probability for the non-real-time buffers will stay within the target s(2).
  • the function c(x,s) is monotonically decreasing in both chi and s.
  • the real-time buffer size ⁇ (1) is designed to be much smaller than the non-real-time buffer size X (2). Therefore, as long as the two overflow loss probabilities s(1) and s(2) are of the same order, the relation c(2) ⁇ c(1) holds. Therefore, both f(L(1)) and f(L(2)) are smaller than the total bandwidth allocated on a link as suggested in the prior art copending application, EP Application No 93480099.6, i.e., f(L).
  • the present invention permits the placement of both additional non-real-time connections on a link and more real-time connections on the link than would be placed on the link with the prior art algorithm.
  • the multiple link metrics of the present invention also fixes a potential problem in the prior art for very high speed links. If, on such high speed links, ⁇ (1) ⁇ (2), and if ⁇ (1) > s(2) , then L ⁇ L(2), where Land L(2) are as given in equations (1) and (7), respectively, and the vector inequality is componentwise. Therefore, if only one metric is kept for all of the traffic and the admission criterion f(L) ⁇ R(link) is used, then the overflow probability objective s(2) of the non-real time traffic may be violated when f(L) ⁇ R(link) ⁇ C Z f(L(2)).
  • the following algorithm is used to admit calls to a link in the packet communications system of FIG. 1.
  • This algorithm provides an efficient procedure to update link metric vectors. This efficiency allows for real-time updates while accounting for the difference between priorities of incoming traffic, the relationship between link bandwidth and connection characteristics, and preserving the incremental nature of link metric updates so that information on individual connections need not be maintained.
  • connection request message propagates along the computed connection path, it is received in each of the nodes and copied by the route controller 37 (FIG. 3) responsible for managing the bandwidth of the links connected to the node.
  • the route controller 37 must first determine whether the connection should be accepted or rejected. If accepted, route controller 37 must update the link metric vectors in topology data base 38 for the link to be used in the computed connection path and, if the connection is being added, derive the new link metric vector to be used to decide whether future connections should be accepted or rejected.
  • a computationally efficient algorithm for updating the link metric vectors from the connection request vector is described above.
  • a computationally efficient algorithm for deciding whether the connection should be accepted will now be described. This algorithm is a modified version of the accept-reject algorithm described in the afore-mentioned copending application EP Application No. 93480099.6 filed July 16, 1993.
  • the decision of whether or not to accept a new connection, based on the connection request vector requires that two operations be performed for each link, for one or more priority classes.
  • the number of connections with a request vector of r(i,k) that could be statistically multiplexed on the link is computed and compared to the number needed to satisfy the statistical multiplexing assumption.
  • the statistical multiplexing assumption used in equation (3) requires that the link be capable of supporting "many" connections similar to the one being added. For any given type of connection, this assumption depends on both the connection characteristics and the total link bandwidth since high bandwidth links can fit more connections, resulting in a greater accuracy of the statistical multiplexing assumption.
  • N(i,k) Upon receipt of the request vector r(i,k) over a link, the the maximum number of connections with the same request vector which could fit on the next link in the route is given by 30 where R(link) is the maximum reservable capacity on the link.
  • R(link) is the maximum reservable capacity on the link.
  • n and alpha are different for different priority classes.
  • N(i,k) is greater or smaller than a given minimum value N * (k)
  • the new link metric vector L' is computed. The value of N * (k) should be "large" to approximate the aggregate bit rate distribution necessary to validate the statistical multiplexing assumption.
  • the new link metric vector L'(k) is computed as follows: 20 where addition is component-wise and where (i) is modified request vector for those links where the statistical multiplexing assumption does not hold true, and is given by:
  • This algorithm provides an efficient procedure to update link metric vectors, requiring at most four additions, three multiplications and two comparisons. This efficiency allows for real-time updates while accounting for the relationship between link bandwidth and connection characteristics and preserving the incremental nature of link metric updates so that information on individual connections need not be maintained.
  • the procedure must, of course, be repeated for all lower priority link metric vectors in order to reflect the loss of bandwidth available to future lower priority connection requests. Higher priority link metric vectors need not be adjusted since the priority classification ensures adequate transmission of the higher priority packets.
  • FIG. 5 Aflow chart of the algorithm for implementing the multiple priority class link metrics of the present invention is shown in FIG. 5.
  • the procedure of FIG. 5 is used at each node in the path of a new connection which is visited by the connection request message of FIG. 2.
  • box 61 is entered to set the priority k to the value I found in the received connection vector.
  • Box 51 is then entered where the connection request message (FIG. 2) is copied at the local node included in the route.
  • decision box 56 the value of t2 is compared to the square of the value of t1. If t2 is less than t1 squared, box 57 is entered where the link metric incremental vector is set to be equal to the request vector r(i,k) received with the connection request message. If, however, t2 is equal to or greater than the square of t1, box 60 is entered where the incremental vector is set to be equal to r (i,k) using equation (8).
  • box 60 is also entered to set the link metric incremental vector to the value of r (i,k). In either case, the link metric incremental vector is used in box 58 to update the link metric vector for this link by simple component-wise vector addition.
  • Box 62 is then entered to calculate f(L(k)) from equation (3).
  • decision box 63 f(L(k)) is compared to R(link) and, if equal to or smaller, decision box 64 is entered.
  • box 67 is entered where all of the link metric vectors previously incremented or decremented by this connection vector are restored to the values they had prior to the arrival of this connection vector. This can be accomplished by either reversing the component- by-component alterations of the link metric values or by saving the original values and merely restoring these values to the topology database of FIG. 4. Box 68 is then entered to reject the call and the process terminated in terminal box 69.
  • priority class index k is not equal to the maximum priority class index value K, as determined by decision box 64, box 66 is entered where the priority class index k is incremented by one and box 53 is re-entered to repeat the link metric update computations for the next lower priority (next higher value of index k) class metric. This process is continued until all of the lower priority link metrics have been updated, or until the call is rejected because some link metric cannot be accommodated in the remaining bandwidth, as determined by decision box 63. Note that the new connection must be acceptable for all priority classes having a priority class equal to or lower than the priority class of the new connection. Afailure to meet any of these criteria results in a rejection of the call.
  • the link metrics defined above can also used in calculating the parameters of an admission stratagem to control access of the signal source for each connection to the network. That is, if the statistics of a signal source diverge significantly from the characteristics assumed when the connection was established, it becomes possible that congestion will occur in the network. To prevent such congestion, a stratagem such as the leaky bucket stratagem described in the above-noted prior application is used to limit the access of that signal source to the network while the signal source is outside of the assumed statistical values.
  • leaky bucket parameters are chosen to achieve transparency of the leaky bucket access controls to the users as long as the traffic remains within the negotiated values, and to control the maximum bandwidth taken by the traffic when that traffic exceeds the negotiated values.
  • the new connection metric vectors defined herein can be used as in the prior art, both to update the link metric vectors for all links along the path of a new connection and, at the same time, be used to calculate the leaky bucket parameters for controlling the access of the new connection to the network. Moreover, since different link metrics are used for each class of connection, the total traffic throughput that can be accommodated by the link can be increased significantly, possible even doubled, without increasing the likelihood of congestion.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Telephonic Communication Services (AREA)
EP94480039A 1993-06-07 1994-05-06 Verkehrsverwaltung in Paketkommunikationsnetzen Withdrawn EP0629065A3 (de)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/073,232 US5347511A (en) 1993-06-07 1993-06-07 Traffic management in packet communications networks
US73232 1993-06-07

Publications (2)

Publication Number Publication Date
EP0629065A2 true EP0629065A2 (de) 1994-12-14
EP0629065A3 EP0629065A3 (de) 2002-05-29

Family

ID=22112541

Family Applications (1)

Application Number Title Priority Date Filing Date
EP94480039A Withdrawn EP0629065A3 (de) 1993-06-07 1994-05-06 Verkehrsverwaltung in Paketkommunikationsnetzen

Country Status (4)

Country Link
US (1) US5347511A (de)
EP (1) EP0629065A3 (de)
JP (1) JP2620513B2 (de)
CA (1) CA2120559C (de)

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1996028920A3 (en) * 1995-03-13 1996-12-12 Intecom Inc Distributed interactive multimedia system architecture
WO1998024260A1 (de) * 1996-11-29 1998-06-04 Siemens Aktiengesellschaft Verfahren zum statistischen multiplexen von atm-verbindungen
WO1999022487A3 (de) * 1997-10-28 1999-07-15 Deutsche Telekom Ag Verfahren und vorrichtung zum aufbauen wenigstens einer verbindung mit niedriger priorität in einem telekommunikationsnetz
EP0847221A3 (de) * 1996-12-06 2000-03-08 Nec Corporation Steuerungsvorrichtung für ein ATM-Netzwerk
RU2166236C2 (ru) * 1995-11-09 2001-04-27 Нокиа Телекоммьюникейшнз Ой Управление трафиком в системе связи
GB2379355A (en) * 2001-08-31 2003-03-05 Roke Manor Research Method of deriving a metric for a link in a network
WO2006032615A1 (de) * 2004-09-22 2006-03-30 Siemens Aktiengesellschaft Automatische nachführung von netzparametern bei veränderungen der verkehrslast
US7058067B1 (en) 1995-03-13 2006-06-06 Cisco Technology, Inc. Distributed interactive multimedia system architecture
DE102006041058A1 (de) * 2006-09-01 2008-03-27 Nokia Siemens Networks Gmbh & Co.Kg Verfahren zur Nachführung von Netzparametern

Families Citing this family (78)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2701513B2 (ja) * 1990-03-29 1998-01-21 日本電気株式会社 回線切替制御方式
SE501272C2 (sv) * 1993-05-03 1994-12-19 Ellemtel Utvecklings Ab Sätt och anordning för att åt en påkallande förbindelse välja en ledig länk
CA2124974C (en) * 1993-06-28 1998-08-25 Kajamalai Gopalaswamy Ramakrishnan Method and apparatus for link metric assignment in shortest path networks
WO1995009501A1 (en) * 1993-09-29 1995-04-06 Fujitsu Limited Network element management system
JP3420621B2 (ja) * 1993-11-04 2003-06-30 富士通株式会社 通信網の分散型経路選択制御装置
EP0660569A1 (de) * 1993-12-22 1995-06-28 International Business Machines Corporation Verfahren und System zum Verbessern der Verarbeitungszeit der Wegeauswahl in einem Hochgeschwindigkeits-Paketvermittlungsnetz
US5497375A (en) * 1994-01-05 1996-03-05 Motorola, Inc. Device and method for ATM end system cell flow regulation
US5694546A (en) 1994-05-31 1997-12-02 Reisman; Richard R. System for automatic unattended electronic information transport between a server and a client by a vendor provided transport software with a manifest list
US5461611A (en) * 1994-06-07 1995-10-24 International Business Machines Corporation Quality of service management for source routing multimedia packet networks
US5452294A (en) * 1994-07-05 1995-09-19 Motorola, Inc. Method and apparatus for adaptive route selection in communication networks
US5434848A (en) * 1994-07-28 1995-07-18 International Business Machines Corporation Traffic management in packet communications networks
US5737547A (en) * 1995-06-07 1998-04-07 Microunity Systems Engineering, Inc. System for placing entries of an outstanding processor request into a free pool after the request is accepted by a corresponding peripheral device
EP0753979A1 (de) * 1995-07-13 1997-01-15 International Business Machines Corporation Methode und System für Wegesuche in einem schnellen Paketvermittlungsnetzwerk
US6097700A (en) * 1995-09-18 2000-08-01 Telefonaktiebolaget L M Ericsson (Publ) Packet switched radio channel congestion control
US5742588A (en) * 1995-09-18 1998-04-21 Telefonaktiebolaget Lm Ericsson Packet switched traffic management in a cellular telecommunications system
US5796719A (en) * 1995-11-01 1998-08-18 International Business Corporation Traffic flow regulation to guarantee end-to-end delay in packet switched networks
EP0781068A1 (de) * 1995-12-20 1997-06-25 International Business Machines Corporation Methode und System für adaptive Bandbreitenzuordnung in einem schnellen Datennetzwerk
US5625622A (en) * 1995-12-27 1997-04-29 Lucent Technologies Inc. Apparatus and method for a generalized leaky bucket
US5781624A (en) * 1996-02-16 1998-07-14 Lucent Technologies Inc. Method for sharing network resources by virtual partitioning
GB9612363D0 (en) * 1996-06-13 1996-08-14 British Telecomm ATM network management
US6400687B1 (en) 1996-06-13 2002-06-04 British Telecommunications Public Limited Company ATM network management
US6754712B1 (en) 2001-07-11 2004-06-22 Cisco Techonology, Inc. Virtual dial-up protocol for network communication
US6073176A (en) * 1996-07-29 2000-06-06 Cisco Technology, Inc. Dynamic bidding protocol for conducting multilink sessions through different physical termination points
US5918019A (en) * 1996-07-29 1999-06-29 Cisco Technology, Inc. Virtual dial-up protocol for network communication
US5963542A (en) * 1996-09-03 1999-10-05 The United States Of America As Represented By The Secretary Of The Navy Asynchronous transfer mode cell loss estimator
US5982748A (en) 1996-10-03 1999-11-09 Nortel Networks Corporation Method and apparatus for controlling admission of connection requests
FI103455B (fi) * 1996-10-08 1999-06-30 Nokia Telecommunications Oy Pakettiverkon reititin
US5884037A (en) * 1996-10-21 1999-03-16 International Business Machines Corporation System for allocation of network resources using an autoregressive integrated moving average method
US6122283A (en) * 1996-11-01 2000-09-19 Motorola Inc. Method for obtaining a lossless compressed aggregation of a communication network
US5848055A (en) * 1996-11-19 1998-12-08 Northern Telecom Limited Bandwidth correlation means for paths in connection-oriented packet switching networks
US6046980A (en) 1996-12-09 2000-04-04 Packeteer, Inc. System for managing flow bandwidth utilization at network, transport and application layers in store and forward network
US6046981A (en) * 1997-02-28 2000-04-04 Nec Usa, Inc. Multi-class connection admission control method for Asynchronous Transfer Mode (ATM) switches
US6195354B1 (en) * 1997-07-16 2001-02-27 Nortel Networks Limited Route selection for path balancing in connection-oriented packet switching networks
US6160818A (en) * 1997-07-17 2000-12-12 At &T Corp Traffic management in packet communication networks having service priorities and employing effective bandwidths
US6438110B1 (en) * 1997-11-12 2002-08-20 Nortel Networks Limited Reservation of connections in a communications network
US6647008B1 (en) 1997-12-19 2003-11-11 Ibm Corporation Method and system for sharing reserved bandwidth between several dependent connections in high speed packet switching networks
US6757247B1 (en) * 1998-02-20 2004-06-29 Adc Telecommunications, Inc. Circuit and method for controlling virtual connections in a ring network
US6633569B2 (en) * 1998-04-16 2003-10-14 Samsung Electronics Co., Ltd. System and method for routing data cells through an ATM architecture using quality of service data in a service control point
US6222824B1 (en) 1998-04-24 2001-04-24 International Business Machines Corporation Statistical call admission control
US6359879B1 (en) * 1998-04-24 2002-03-19 Avici Systems Composite trunking
EP1082843B1 (de) 1998-06-05 2006-08-30 Nokia Corporation Verfahren und anlage zur verbindungszulassungssteuerung
US6891797B1 (en) 1998-07-06 2005-05-10 Canon Kabushiki Kaisha Method and device for communicating information
US6275695B1 (en) * 1998-10-08 2001-08-14 Nortel Networks Limited Spectrum yield management in a wireless communication system
US6499061B1 (en) * 1998-12-11 2002-12-24 Cisco Technology, Inc. Method and system for assigning labels to data flows over a packet switched network
WO2000038378A1 (en) * 1998-12-21 2000-06-29 Siemens Information And Communication Networks S.P.A. Admission control of mixed vbr sources in broadband networks
US6442164B1 (en) 1999-06-03 2002-08-27 Fujitsu Network Communications, Inc. Method and system for allocating bandwidth and buffer resources to constant bit rate (CBR) traffic
US6477167B1 (en) 1999-06-03 2002-11-05 Fujitsu Network Communications, Inc. Method and system for allocating bandwith to real-time variable bit rate (rt-VBR) traffic
US6847609B1 (en) 1999-06-29 2005-01-25 Adc Telecommunications, Inc. Shared management of a network entity
US6959006B1 (en) 1999-06-29 2005-10-25 Adc Telecommunications, Inc. Service delivery unit for an enterprise network
JP3407696B2 (ja) * 1999-07-13 2003-05-19 日本電気株式会社 Ａｔｍ交換機および呼受付処理方法
US7173904B1 (en) * 1999-09-23 2007-02-06 Lucent Technologies Inc. System and method for reverse link overload control
US6816456B1 (en) * 2000-02-04 2004-11-09 At&T Corp. Methods and apparatus for network use optimization
EP1135000A1 (de) * 2000-03-17 2001-09-19 Telefonaktiebolaget Lm Ericsson Verbindung-aggregation
US6954429B2 (en) * 2000-04-05 2005-10-11 Dyband Corporation Bandwidth control system
US6658512B1 (en) * 2000-09-28 2003-12-02 Intel Corporation Admission control method for data communications over peripheral buses
US7325058B1 (en) 2000-11-13 2008-01-29 Cisco Technology, Inc. Method and system for controlling subscriber access in a network capable of establishing connections with a plurality of domain sites
US6874030B1 (en) 2000-11-13 2005-03-29 Cisco Technology, Inc. PPP domain name and L2TP tunnel selection configuration override
JP4511021B2 (ja) * 2000-12-28 2010-07-28 富士通株式会社 トラフィック情報収集装置およびトラフィック情報収集方法
US7139276B1 (en) 2001-02-27 2006-11-21 Cisco Technology, Inc. Load sharing between L2TP tunnels
US7023879B1 (en) 2001-03-09 2006-04-04 Cisco Technology, Inc. Dynamic multi-hop ingress to egress L2TP tunnel mapping
US7107344B2 (en) * 2001-08-16 2006-09-12 International Business Machines Corporation Connection allocation technology
KR100948317B1 (ko) * 2001-12-15 2010-03-17 톰슨 라이센싱 클라이언트 사이의 세션을 위한 ＱｏＳ 계약의 설정 능력을 제공하는 방법 및 시스템
US10489449B2 (en) 2002-05-23 2019-11-26 Gula Consulting Limited Liability Company Computer accepting voice input and/or generating audible output
US8611919B2 (en) 2002-05-23 2013-12-17 Wounder Gmbh., Llc System, method, and computer program product for providing location based services and mobile e-commerce
US7161904B2 (en) * 2002-06-04 2007-01-09 Fortinet, Inc. System and method for hierarchical metering in a virtual router based network switch
US7376121B2 (en) * 2003-06-06 2008-05-20 Microsoft Corporation Method and system for global routing and bandwidth sharing
US20040264472A1 (en) * 2003-06-27 2004-12-30 Oliver Neal C. Method and system for open-loop congestion control in a system fabric
US8631151B2 (en) * 2006-05-18 2014-01-14 Intel Corporation Techniques for guaranteeing bandwidth with aggregate traffic
ES2377157T3 (es) * 2003-12-30 2012-03-23 Intel Corporation Técnicas para garantizar el ancho de banda con un tr�?fico agregado.
US7925728B2 (en) * 2005-09-08 2011-04-12 International Business Machines Corporation Facilitating detection of hardware service actions
JP5068125B2 (ja) * 2007-09-25 2012-11-07 株式会社日立国際電気 通信装置
JP2013150152A (ja) * 2012-01-19 2013-08-01 Sony Corp 情報処理装置、情報処理方法、及び情報処理システム
EP2823664B1 (de) * 2012-03-07 2019-01-16 Telefonaktiebolaget LM Ericsson (publ) Knoten und verfahren zur handhabung von nicht-echtzeit daten in einem drahtlosen kommunikationsnetz
US8964953B2 (en) 2013-01-10 2015-02-24 Microsoft Corporation Incremental valuation based network capacity allocation
US9525638B2 (en) 2013-10-15 2016-12-20 Internap Corporation Routing system for internet traffic
US9367384B2 (en) * 2014-06-12 2016-06-14 International Business Machines Corporation Admission control based on the end-to-end availability
GB2556090B (en) * 2016-11-18 2019-07-17 Bluwireless Tech Ltd Apparatus and method for scheduling communications in a wireless communication system
US12149980B2 (en) * 2021-03-26 2024-11-19 T-Mobile Usa, Inc. System and method for dynamic allocation of resources

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0831876B2 (ja) * 1985-09-20 1996-03-27 株式会社日立製作所 パケツト交換網におけるル−チング制御方式
US4827411A (en) * 1987-06-15 1989-05-02 International Business Machines Corporation Method of maintaining a topology database
JPH01177743A (ja) * 1988-01-08 1989-07-14 Nec Corp ハイブリッド・リンク・システムのルーティング策定方式
JP2865675B2 (ja) * 1988-09-12 1999-03-08 株式会社日立製作所 通信ネットワーク制御方法
JPH02220531A (ja) * 1989-02-22 1990-09-03 Toshiba Corp 呼接続制御方式および流量監視方式
JP2837182B2 (ja) * 1989-08-04 1998-12-14 富士通株式会社 セルデータの伝送方法、送信要求処理方法及びスイッチ
US5243592A (en) * 1990-10-15 1993-09-07 Digital Equipment Corporation Method and apparatus for distance vector routing on datagram point-to-point links
US5233604A (en) * 1992-04-28 1993-08-03 International Business Machines Corporation Methods and apparatus for optimum path selection in packet transmission networks
US5262906A (en) * 1992-06-19 1993-11-16 Alcatel Network Systems, Inc. Message routing for SONET telecommunications maintenance network

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
SAITO H.: "Hybrid Connection Admission Control in ATM networks", ICC 92 PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, vol. 4, 14 June 1992 (1992-06-14), CHICAGO, pages 699 - 703, XP010062022, DOI: doi:10.1109/ICC.1992.268193 *

Cited By (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1996028920A3 (en) * 1995-03-13 1996-12-12 Intecom Inc Distributed interactive multimedia system architecture
US7058067B1 (en) 1995-03-13 2006-06-06 Cisco Technology, Inc. Distributed interactive multimedia system architecture
RU2166236C2 (ru) * 1995-11-09 2001-04-27 Нокиа Телекоммьюникейшнз Ой Управление трафиком в системе связи
US6970421B1 (en) 1996-11-29 2005-11-29 Siemens Aktiengesellschaft Statistic multiplexing of ATM-connections
WO1998024260A1 (de) * 1996-11-29 1998-06-04 Siemens Aktiengesellschaft Verfahren zum statistischen multiplexen von atm-verbindungen
EP0847221A3 (de) * 1996-12-06 2000-03-08 Nec Corporation Steuerungsvorrichtung für ein ATM-Netzwerk
US6226263B1 (en) 1996-12-06 2001-05-01 Nec Corporation ATM network externally controlled for network resource reservation of end-to-end switched virtual connection
WO1999022487A3 (de) * 1997-10-28 1999-07-15 Deutsche Telekom Ag Verfahren und vorrichtung zum aufbauen wenigstens einer verbindung mit niedriger priorität in einem telekommunikationsnetz
GB2379355A (en) * 2001-08-31 2003-03-05 Roke Manor Research Method of deriving a metric for a link in a network
GB2379355B (en) * 2001-08-31 2003-07-16 Roke Manor Research A method of deriving a metric for link in a network
WO2006032615A1 (de) * 2004-09-22 2006-03-30 Siemens Aktiengesellschaft Automatische nachführung von netzparametern bei veränderungen der verkehrslast
DE102006041058A1 (de) * 2006-09-01 2008-03-27 Nokia Siemens Networks Gmbh & Co.Kg Verfahren zur Nachführung von Netzparametern
DE102006041058B4 (de) * 2006-09-01 2008-09-11 Nokia Siemens Networks Gmbh & Co.Kg Verfahren zur Nachführung von Netzparametern
US8027261B2 (en) 2006-09-01 2011-09-27 Nokia Siemens Networks Gmbh & Co. Kg Method for tracking network parameters

Also Published As

Publication number Publication date
CA2120559A1 (en) 1994-12-08
CA2120559C (en) 1999-07-13
EP0629065A3 (de) 2002-05-29
JPH0758778A (ja) 1995-03-03
US5347511A (en) 1994-09-13
JP2620513B2 (ja) 1997-06-18

Similar Documents

Publication Publication Date Title
US5347511A (en) Traffic management in packet communications networks
US5289462A (en) Traffic management in packet communications networks
US6934249B1 (en) Method and system for minimizing the connection set up time in high speed packet switching networks
US5600638A (en) Method and system for improving the processing time of the path selection in a high speed packet switching network
US6400681B1 (en) Method and system for minimizing the connection set up time in high speed packet switching networks
US5402478A (en) System and method for call-by-call source routing with rule-based fallbacks
CA2181206C (en) A method for admission control and routing by allocating network resources in network nodes
Lee et al. Routing subject to quality of service constraints in integrated communication networks
CA2371194C (en) Device and method for routing streams at a node in a packet transmission network
JP3159927B2 (ja) 網動作方法、要求経路方法並びにルーティング及び承認制御する方法
US5581544A (en) Method and apparatus for evaluating QOS in ATM multiplexing apparatus in which priority control is performed and for controlling call admissions and optimizing priority control on the basis of the evaluation
US7593321B2 (en) Method and system for a local and fast non-disruptive path switching in high speed packet switching networks
US5917804A (en) Connection admission control for ATM networks handling CBR and VBR services
US6628670B1 (en) Method and system for sharing reserved bandwidth between several dependent connections in high speed packet switching networks
EP0957648A2 (de) Verfahren und Vorrichtung zur verteilten Steuerung eines Netzes mit mehreren Klassen
EP0897232B1 (de) Verkehrsverwaltung in Paketkommunikationsnetzwerken mit Dienstenprioritäten und effektiven
EP0814583A2 (de) Verfahren und System zur Verminderung der Verbindungsaufbauzeit in Hochgeschwindigkeits-Paketvermittlungsnetzen
Pillai A distributed overload control algorithm for delay-bounded call setup
Gawlick et al. Routing and admission control of virtual circuits in general topology networks
JP2004007230A (ja) 通信帯域制御方式
Ismail Bandwidth problems in high-speed networks
KR100226997B1 (ko) 트래픽 모니터링 기반 고속 호출허용 제어방법 및장치
Ansari et al. The performance evaluation of a new neural network-based traffic management scheme for a satellite communication network
Acampora Issues in Traffic Control and Performance Management
Atlasis et al. An adaptive routing algorithm for ATM networks using a learning automaton

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): DE FR GB

17P Request for examination filed

Effective date: 19950425

PUAL Search report despatched

Free format text: ORIGINAL CODE: 0009013

AK Designated contracting states

Kind code of ref document: A3

Designated state(s): DE FR GB

RIC1 Information provided on ipc code assigned before grant

Free format text: 7H 04L 12/56 A, 7H 04Q 11/04 B

17Q First examination report despatched

Effective date: 20040303

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20040914