Frederick W Shepard

US Patent:

20070121510, May 31, 2007

Filed:

Nov 28, 2005

Appl. No.:

11/287890

Inventors:

Chandra Chekuri - Chatham NJ, US
Sanjeev Khanna - Philadelphia PA, US
Frederick Shepard - Summit NJ, US

International Classification:

H04J 1/16
H04L 12/56

US Classification:

370235000, 370400000

Abstract:

Methods and apparatus are provided for designing traffic distribution in a multiple-service packetized network using such multicommodity flows and well-linked terminals. Arbitrary multicommodity flows are transformed to sets of well-linked terminals. The multicommodity flows are represented in a graph G having a set of k node-pairs st, . . . ,st, each having a positive integer demand dand a positive weight w. The graph G is partitioned into a collection of node-disjoint subgraphs wherein each sub-graph H contains a set of terminals, where {right arrow over (π)} is a non-negative weight function on a set X of nodes in the graph G; and then the set of terminals are clustered to a subset of terminals that is at least -flow-linked or -cut-linked.