Method and apparatus for assigning communication nodes to CMTS cards

• US 7,353,530 B1
• Filed: 05/10/2002
• Issued: 04/01/2008
• 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; Chris
• Assistant Examiner(s): Newlin; Timothy R
• Application Number:
  US10/144,409
• Time in Patent Office: 2,153 Days
• Field of Search: 725/129, 725/119, 725/111, 370/468, 370/437, 370/254, 370/255
• 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 communication system comprising:

a plurality of broadband telephony interfaces for providing a plurality of respective customers with service from at least one service provider;

a plurality of nodes for relaying the service;

a plurality of cards for controlling the service;

a plurality of coaxial and/or fiber optic cables connecting said nodes to said interfaces and to 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 module 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 module optimization 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 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 node must be assigned to some card;

Σ

x[i, c]≦

SMAX;

for all “

c”

so that a card can serve at most SMAX nodes;

Σ

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

for all “

c”

such that a card can serve at most HMAX households;

y[c]≧

z;

for all “

c”

such that all 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. A communication system according to claim 1, wherein said module is supplemented by a heuristic algorithm if x[i, c] comes out to be fractional in the solution.

3. A communication system according to claim 1, wherein said model solving module maximizes the minimum margin across all cards instantaneously.

4. A communication system 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.

5. A communication system according to claim 1, wherein the number of 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.

6. A communication system 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 said cards have a minimum margin of customers.

7. A communication system according to claim 1, wherein said solution includes finding a connection pattern that maximizes said minimum margin among all cards.

8. A communication system according to claim 1, wherein said solution avoids overload of any one card and increases the traffic flow of said service.