Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
2000-05-17
2004-04-06
Kizou, Hassan (Department: 2662)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S390000, C370S408000, C709S252000
Reexamination Certificate
active
06717921
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods for routing multicast data communications. More specifically, it relates to a method for configuring a close-to-optimal Steiner tree for routing data communications traffic associated with a multicast conference call subject to a predetermined end-to-end delay requirement.
BACKGROUND OF THE INVENTION
Multicasting presents a communications paradigm in which communications initiated by a sending party are broadcast to a plurality of receiving parties. Internet Protocol (IP) multicasting applications, for example, represent a significant segment for multicasting applications. Typical IP applications for multicasting include audio and video conferencing, streaming audio and video applications, and document and software distribution (see, e.g., Sanjoy Paul, Multicasting On The Internet And Its Applications, Kluwer Academic Publishers, Boston, 1998, pp.9-10). Real time applications such as audio and video conferencing present stringent delay requirements for multicast packets transmitted over IP networks. Typical sender-to-receiver latency, for example, may be required to be less than 100 milliseconds. Multicast network facilities costs consumed represent an additional concern for IP multicast network operators.
In conventional multicast networks, trees are often employed to facilitate multicast routing (see, e.g., V. P. Kompella et al., “Multicast Routing for Multimedia Communication,” IEEE/ACM Transactions On Networking, Vol. 1, No. 3, June 1993, pp. 286-292). Such trees are defined by a plurality of routers (“nodes”) for transmitting multicast conference packets over a plurality of data transmission links (“arcs”) that interconnect node pairs. Multicast conference participants (“senders” and “receivers”) are terminated on at least a subset of the plurality of routers (“terminating nodes”).
Multicast trees provide for efficient conference routing, as each packet that must be forwarded by a sender to a number of receivers need only be copied at each node that branches to at least two nodes or that serves at least two receivers. As a result, the sender's node is most often required to produce a number of copies that is fewer in number than the number of receivers. This may be contrasted, for example, with unicast methods that require the sender to produce individual packet copies for each intended receiver.
Several methods have been used-to configure multicast trees in a manner that reduces facilities costs (see, e.g., Sanjoy Paul, op cit. at pg. 21). Such methods can be characterized as shortest path tree (SPT) methods, minimum cost tree (MCT) methods and constrained tree (CT) methods.
SPT methods are used to produce a multicast tree such that the cost of facilities between a selected sender and each identified receiver is minimized. MCT methods focus on minimizing total facilities costs for the multicast tree. CT methods focus on minimizing overall facilities costs subject to additional constraints.
A representative CT method used for multicast routing is the constrained Steiner tree method (see Kompella, op cit. at pp. 286-289). A minimum Steiner tree may be defined as a network tree which is constructed such that the sum of a series of “penalties” (for example, such as network facilities costs) that can be associated with each arc in the tree are minimized. A constrained Steiner tree may be heuristically constructed as “close-to-optimal,” such that the tree approaches a theoretical minimum penalty subject to one or more constraints. For example, a typical constraint may require that the expected delay on each path between a sender and a receiver does not exceed a predetermined maximum.
Kompella discloses a constrained Steiner tree method directed to produce a multicast tree supporting one sender and a plurality of receivers. However, emerging conferencing applications in multicasting are requiring that each participant to be capable of acting either as a sender or a receiver. Therefore, it would be advantageous to develop a constrained Steiner tree method that produces a close-to-optimal Steiner tree for a multicast conference in which any participant may function as either a sender or a receiver.
SUMMARY OF THE INVENTION
The art is advanced by a novel and non-obvious method directed to configuring a close-to-optimal Steiner tree with low facilities cost constrained by a desired maximum end-to-end delay T between each pair of participants. The method begins by initializing the tree with a node that terminates at least one of the participants. While one or more nodes that terminate participants have not been added to the tree, additional nodes are incrementally selected from among nodes not yet selected or added to the tree such that each selected node adds a least additional penalty over its identified path to the current tree. When the selected node is a terminating node, the node is added to the tree along with any other selected nodes and arcs in its path to the tree.
The method further incorporates a penalty function that addresses the maximum delay constraint by using a Lagrangian-like relaxation technique to combine both cost and delay into a single incremental penalty function. In order to approach the maximum end-to-end delay constraint T between any pair of terminating nodes in the tree, a novel path delay metric (“delta diameter”) is introduced that provides a measure of impact on the maximum expected end-to-end delay &tgr; that would result from the addition of each incrementally selected node to the tree.
REFERENCES:
patent: 5291477 (1994-03-01), Liew
patent: 5541927 (1996-07-01), Kristol et al.
patent: 6088333 (2000-07-01), Yang et al.
patent: 6154463 (2000-11-01), Aggarwal et al.
patent: 6321271 (2001-11-01), Kodialam et al.
patent: 6363319 (2002-03-01), Hsu
patent: 6529498 (2003-03-01), Cheng
Ahn A multicast tree algorithm considering maximum delay bound for real-time applications. Local Computer Networks, 1996., Proceedings 21st IEEE Conference on, Oct. 13-16, 1996 Page(s): 172-181.*
Ravindran Cost-optimal multicast trees for multi-source data flows in multimedia distribution. INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol.: 2, 22-26 Apr. 2.*
Ahuja, Ravindra K., et al.,Network Flows: Theory, Algorithms and Applications,Prentice Hall, Englewood Cliffs, NJ, 1993, pp. 598-638.
Kompella, Vachaspathi P., et al.,“Multicast Routing for Multimedia Communication,”IEEE/ACM Transactions on Networking, Vol, 1, No. 3, Jun. 1993, pp. 286-292.
Maxemchuk, Nicholas F.,“Video Distribution on Multicast Networks,”IEEE Journal on Selected Areas in Communications, vol. 15, No. 3, Apr. 1997, pp. 357-372.
Paul, Sanjoy,Multicasting on the Internet and its Applications,Kluwer Academic Publishers, Boston, MA, 1998, pp. 21-28 and 397-415.
Aggarwal Sudhir
Netravali Arun N
Sabnani Krishan K
Hodulik Matthew J.
Kizou Hassan
Levitan Dmitry
Lucent Technologies - Inc.
LandOfFree
Method for configuring a shared tree for routing traffic in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for configuring a shared tree for routing traffic in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for configuring a shared tree for routing traffic in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3247128