Method and apparatus for assigning communication nodes to CMTS cards

• US 7,552,462 B2
• Filed: 02/26/2008
• Issued: 06/23/2009
• Est. Priority Date: 05/10/2002
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Segal, Moshe
• Primary Examiner(s): Kelley; Christopher
• Assistant Examiner(s): Newlin; Timothy R
• Application Number:
  US12/072,372
• Publication Number:
  US 20080159745A1
• Time in Patent Office: 483 Days
• Field of Search: 725/129, 725/119, 725/107, 725/127, 725/111, 370/468, 370/255, 370/437, 370/254
• US Class Current: 725/119
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04M 7/1215 where a cable TV network is used as an access to the PSTN/ISDN

Abstract

A method and apparatus for assigning nodes to CMTS cards in a communication system. In order to avoid bottlenecks and to efficiently use resources of the cards in a hybrid fiber-coax architecture, the nodes are assigned to the cards using linear programming techniques so as to distribute the traffic load and minimize the unused capacity of each card. The number of households, nodes and cards are determined and used to establish a model which is then implemented using linear programming techniques to determine an optimal solution.

Claims

1. A method of connecting a plurality of nodes to a plurality of cards in a communication system, the method comprising:

providing service to customers through cables connected to said nodes;

determining using a computer a minimum number of said cards for controlling service connections to said nodes by contemporaneously evaluating the whole communication system for infrastructural arrangement inclusive of all cards and all nodes;

modeling minimum margins for said cards using an optimization model that includes linear relationships among customer distribution data and a set of constraint conditions for said cards; and

mathematically solving the model using linear, integer, and binary programming techniques, to determine a solution, whereby the number of customers served by each said card is similar for a simultaneous assignment of all of said nodes to all of said cards, wherein the number of said nodes being assigned to said cards are distributed to allocate traffic as evenly as possible, wherein said optimization model is represented by

max [x*z]

where

x[i, c] is an assignment variable which equals 1 when a specific said node “

i”

is assigned to said card “

c”

or 0 otherwise;

v[c]≧

0, indicating the leftover capacity for households or margin present in said card c;

w is a weight of 1 when the search reaches an optimal solution and remains 0 when it is searching for a feasible solution;

Σ

x[i, c]=1;

for all “

i”

when every said node must be assigned to one of said cards;

Σ

x[i, c]≦

SMAX;

for all “

c”

so that said card can serve at most SMAX said nodes;

Σ

x[i, c]*H[i]+y[c]=HMAX;

for all “

c”

such that said card can serve at most HMAX households;

y[c]≧

z;

for all “

c”

such that all of said cards must have at least a margin or unused capacity of z households; and

z≧

YMAX such that the minimum margin must be at least YMAX.

2. The method according to claim 1, wherein the number of said cards needed is determined to be at least the total number of customers served divided by the maximum number of customers allowed to be served by a card.

3. The method according to claim 1, wherein said set of constraints includes at least one of:

Every said node must be assigned to at least one of said cards;

one of said cards serves a maximum number of said nodes;

one of said cards serves a maximum number of customers; and

all cards have a minimum margin of customers.

4. The method according to claim 1, wherein said service provided to said customers is broadband service including video, data and telephony.

5. The method according to claim 1, wherein said customers are provided with a broadband telephony interface which is connected to one of said nodes by a coaxial cable, one of said nodes being connected to one of said cards by a fiber optic cable.

6. The method according to claim 1, wherein the communication system is a voice-over-IP system providing telephony, data and video services to said customer using a hybrid fiber optic-coaxial cable architecture.

7. The method according to claim 1, wherein said optimization program is supplemented by a heuristic algorithm if x[i, c] comes out to he fractional in the solution.

8. The method according to claim 1, wherein said solution includes finding a connection pattern that maximizes said minimum margin among all said cards.

9. The method according to claim 1, wherein said solution includes finding a connection pattern that maximizes said minimum margin among all said cards instantaneously.

10. The method according to claim 1, wherein additional constraints are added to said model to indicate that certain specific said nodes must be served by certain specific said cards.

11. The method according to claim 1, wherein said solution avoids overload of any one card and increases the flow of traffic.

12. A communication apparatus comprising:

a plurality of interface boxes for providing a plurality of respective customers with service from at least one service provider;

a plurality of coaxial cables connected to said boxes;

a plurality of nodes connected to said coaxial cables;

a plurality of fiber optic cables connected to said nodes; and

a plurality of cards connected to said fiber optic cables,

all of said nodes being assigned to all of said cards in an all-inclusive contemporaneous evaluation so as to allocate traffic as evenly as possible among said cards;

a comprehensive model created by simultaneously evaluating the minimum margins for all said cards using the linear relationships among customer distribution data and a set of constraint conditions for said cards;

a model solving optimization program for mathematically solving the model using linear, integer, and binary programming techniques, to determine an infrastructural assignment arrangement of all said cards and all said nodes, wherein the number of said nodes being assigned to said cards are distributed to allocate traffic as evenly as possible, wherein said optimization program is represented by;

max [x*z]

where

x[i, c] is an assignment variable which equals 1 when a specific said node “

i”

is assigned to said card “

c”

or 0 otherwise;

y[c]≧

0, indicating the leftover capacity for households or margin present in said card c;

w is a weight of 1 when the search reaches an optimal solution and remains 0 when it is searching for a feasible solution;

Σ

x[i, c]=1;

for all “

i”

when every said node must be assigned to one of said cards;

Σ

x[i, c]≦

SMAX;

for all “

c”

so that each said card can serve at most SMAX said nodes;

Σ

x[i, c]*H[i]+y[c]=HMAX;

for all “

c”

such that each said card can serve at most HMAX households;

y[c]≧

z;

for all “

c”

such that all said cards must have at least a margin or unused capacity of z households; and

z≧

YMAX such that the minimum margin must be at least YMAX.

13. The communication apparatus according to claim 12, wherein said interface boxes are broadband telephony interface boxes providing connections to telephone, data and video services.

14. The communication apparatus according to claim 12, wherein the assignment of said nodes to said cards is determined by linear relationships having a set of constraints, including at least one of:

that every said node must be assigned to at least one of said cards;

that one of said cards serves at most a maximum number of said nodes;

that one of said cards serves a maximum number of customers; and

that one of said cards has a minimum margin of customers.

15. The communication apparatus of claim 12, wherein said optimization program is supplemented by a heuristic algorithm if x[i, c] comes out to be fractional in the solution.

16. The communication apparatus of claim 12, wherein said solution includes finding a connection pattern that maximizes said minimum margin among all said cards.

17. The communication apparatus of claim 12, wherein said solution includes finding a connection pattern that maximizes said minimum margin among all said cards instantaneously.

18. The communication apparatus of claim 12, wherein additional constraints are added to said model to indicate that certain specific said nodes must be served by certain specific said cards.

19. The communication apparatus of claim 12, wherein said solution avoids overload of any one card and increases the flow of traffic.