# US 5,347,511 A · Traffic management in packet communications networks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 5,347,511 A - Document ID: US5347511A - Status: Granted - Kind: A - Application number: 08/073,232 - Filed: 1993-06-07 - Granted: 1994-09-13 - Earliest claimed: 1993-06-07 - Assignees: International Business Machines Corporation - Inventors: Levent Gun - Web page: https://patentgrep.com/patent/US5347511A ## CPC - H04L 12/5602: {Bandwidth control in ATM Networks, e.g. leaky bucket} - H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)} - H04L 45/26: {Route discovery packet} - H04L 45/302: Route determination based on requested QoS - H04L 45/3065: {for real time traffic} - H04Q 11/0478: {Provisions for broadband connections} - H04L 2012/5619: {Network Node Interface, e.g. tandem connections, transit switching} - H04L 2012/5632: {Bandwidth allocation} - H04L 2012/5638: {Services, e.g. multimedia, GOS, QOS} - H04L 2012/5651: {Priority, marking, classes} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - H04Q: SELECTING (switches, relays, selectors H01H; wireless communication networks H04W) ## Abstract 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. A new connection (or deletion) is represented by a compatible metric which allows updates in the link metric by simple vector addition or subtraction. Separate link metrics for a plurality of classes of service permit a much higher efficiency in the exploitation of the link bandwidth than is possible with a single link metric. A packet network using multiple link metrics and efficient metric updating techniques provides increased packet throughput while, at the same time, preserving all class of service guarantees. ## Claims ### Claim 1 A packet communications network including a plurality of switching nodes interconnected by transmission links, and in which data packets are transmitted over multilink paths between a source node and a destination node, said data packets each belonging to one of a plurality of classes of traffic, said packet communications network comprising means for storing, at each said node, a vector representation of the traffic load reserved for those connections in each of said plurality of classes of traffic to be transmitted on each of said transmission links terminating at said node, means for initiating a new connection in said network by propagating a connection request along the route selected for that connection, each said connection request including a vector representing the characteristics of said new connection including the class of service for said new connection, and means responsive to said connection request for updating said vector representation of traffic load for the class of traffic of said connection request and for all lower classes of traffic, said updating taking place by vector addition of said connection request vector to said vector representation of said traffic load at each of said nodes along said route. ### Claim 2 (depends on 1) The packet communications network according to claim 1 further comprising means responsive to said connection request for denying said connection request when the updated representation of the traffic load for any class of traffic on any of said transmission links exceeds the reservable capacity of said transmission link. ### Claim 3 (depends on 1) The packet communications network according to claim 1 wherein said classes of traffic comprise classes of priorities in forwarding said packets through said network. ### Claim 4 (depends on 3) The packet communications network according to claim 3 wherein said classes of priorities include real-time and non-real time information. ### Claim 5 (depends on 1) The packet communications network according to claim 1 wherein said means for updating said representations of link traffic load for a new connection i of traffic class l comprises means for determining the value t.sub.1 of a first variable given by t.sub.1 =R.sub.link -N.sub.l *m.sub.i where R.sub.link is the maximum reservable traffic capacity on the link, N.sub.l * is a constant for traffic class l representing the number of connection with metrics similar to the metrics of connection i which could be statistically multiplexed on the capacity R.sub.link, and m.sub.i is the mean of the bit rate for said new connection i, means for comparing the value of said first variable to zero and, if said value is greater than zero, determining the value t.sub.2 of a second variable given by t.sub.2 =.alpha.'.sub.l.sup.2 N.sub.l *.sigma..sub.i.sup.2 where .sigma..sub.i is the standard deviation of the mean bit rate m.sub.i, and .alpha.' is given by ##EQU9## where .epsilon..sub.l is the target buffer oveflow probability for the traffic class l, means for comparing the value of said second variable to the square of said first variable, means for determining an update vector r.sub.i.sup.(l) for connection i of traffic class l in which the variance of the bit rate is zero, means for updating said representation with said request vector when said first variable is greater than zero and said second variable is less than the square of said first variable, and means for updating said representation with said update vector r.sub.i.sup.(l) otherwise. ### Claim 6 A method of establishing new connections in a packet communications network including a plurality of switching nodes interconnected by transmission links, and in which data packets are transmitted over multilink paths between a source node and a destination node, said data packets each belonging to one of a plurality of classes of traffic, said method comprising the steps of storing, at each said node, a vector representation of the traffic load reserved for those connections in each of said plurality of classes of traffic to be transmitted on each transmission link terminating in said node, initiating a new connection in said network by propagating a connection request along the route selected for that connection, each said connection request including a vector representing the characteristics of said new connection including class of service for said new connection, and updating, in response to said connection request, said representation of traffic load for the class of traffic of said connection request and for all lower classes of traffic, said updating taking place by vector addition of said connection request vector to said vector representation of said traffic load at each of said nodes along said route. ### Claim 7 (depends on 6) The method according to claim 6 further comprising the step of denying, in request to said connection request, said connection request when the updated representation of the traffic load for any class of traffic on any of said transmission links exceeds the reservable capacity of said transmission link. ### Claim 8 (depends on 6) The method according to claim 6 wherein said classes of traffic comprise classes of priorities in forwarding said packets through said network. ### Claim 9 (depends on 8) The method according to claim 8 wherein said classes of priorities include real-time and non-real time information. ### Claim 10 (depends on 6) The method according to claim 6 wherein said step of updating said representations of link traffic for a new connection i of traffic class l comprises determining the value t.sub.1 of a first variable given by t.sub.1 =R.sub.link -N.sub.l *m.sub.i where R.sub.link is the maximum reservable traffic capacity on said link, N.sub.l * is a constant for traffic class l representing the number of connections with metrics similar to the metrics of connection i which could be statistically multiplexed on the capacity R.sub.link, and m.sub.i is the mean of the bit rate for said new connection i, comparing the value of said first variable to zero and, if said value is greater than zero, determining the value t.sub.2 of a second variable given by t.sub.2 =.alpha.'.sub.l.sup.2 N.sub.l *.sigma..sub.i.sup.2 where .sigma..sub.i is the standard deviation of the mean bit rate m.sub.i, and .alpha.'.sub.l is given by ##EQU10## where .epsilon..sub.l is the target buffer overflow probability for the traffic class l, comparing the value of said second variable to the square of said first variable, determining an update vector r.sub.i.sup.(l) for connection i of traffic class l in which the variance of the bit rate is zero, updating said representation with said request vector when said first variable is greater than zero and said second variable is less than the square of said first variable, and updating said representation with said update vector r.sub.i.sup.(l) otherwise. ### Claim 11 A node for a packet communications network including a plurality of switching nodes interconnected by transmission links, and in which data packets are transmitted over multilink paths between a source node and a destination node, said data packets belonging to one of a plurality of classes of traffic, said packet communications network node comprising means for storing at said node a vector representation of the traffic load reserved for those connections in each of said plurality of classes of traffic to be transmitted on each transmission link terminating in said node, means for initiating a new connection from said node into said network by propagating a connection request from said node along the route selected for that connection, each said connection request including a vector representing the characteristics of said new connection including the class of service for said new connection, and means in said node responsive to a connection request from other nodes in said network for updating said representation of traffic load for the class of traffic of said connection request and for all lower classes of traffic, said updating taking place by vector addition of said connection request vector to said vector representation of said traffic load at said node. ### Claim 12 (depends on 11) The packet communications network node according to claim 11 further comprising means responsive to said connection request for denying said connection request when the updated representation of the traffic load for any class of traffic on a transmission link in said route exceeds the capacity of said transmission link. ### Claim 13 (depends on 11) The packet communications network node according to claim 11 wherein said classes of traffic comprise classes of priorities in forwarding said packets through said network. ### Claim 14 (depends on 13) The packet communications network node according to claim 13 wherein said classes of priorities include real-time and non-real-time information. ### Claim 15 (depends on 11) The packet communications network node according to claim 11 wherein said means for updating said representations of traffic load for a new connection i of traffic class l comprises means for determining the value t.sub.1 of a first variable given by t.sub.1 =R.sub.link -N.sub.l *m.sub.i where R.sub.link is the maximum reservable traffic capacity on said link, N.sub.l * is a constant for traffic class l representing the number of connections with metrics similar to the metrics of connection i which could be statistically multiplexed on the capacity R.sub.link, and m.sub.i is the mean of the bit rate for said new connection, means for comparing the value of said first variable to zero and, if said value is greater than zero, determining the value t.sub.2 of a second variable given by t.sub.2 =.alpha.'.sub.l.sup.2 N.sub.l *.sigma..sub.i.sup.2 where .sigma..sub.i is the standard deviation of the mean bit rate m.sub.i, and .alpha.'.sub.l is given by ##EQU11## where .epsilon..sub.l is the target buffer overflow probability for the traffic class l, means for comparing the value of said second variable to the square of said first variable, means for determining an update vector r.sub.i.sup.(l) for connection i of traffic class l in which the variance of the bit rate is zero, means for updating said representation with said request vector when said first variable is greater than zero and said second variable is less than the square of said first variable, and means for updating said representation with said update vector r.sub.i.sup.(l) otherwise.