Browse Prior Art Database

Covering method for multicast destinations

IP.com Disclosure Number: IPCOM000014536D
Original Publication Date: 2001-Apr-28
Included in the Prior Art Database: 2003-Jun-19
Document File: 5 page(s) / 44K

Publishing Venue

IBM

Abstract

The multicast covering problem can be defined as follows. There are D 2 destinations possible, so D elements in a set S of all possible destinations across a switch. The destinations are labeled with the integers 1, 2, ..., D. There are N nonempty, distinct subsets {Si},i=1,2, ..., N 2^D of the D elements. The set of subsets {Si} includes all D subsets consisting of exactly one element. The set of all integer labels used to enumerate the subsets is A {1, 2, ..., N}. There is in addition a given subset G. G might be exactly the same as one of the subsets in {Si}, but in general it is not. The problem is to find a set of subsets among {Si} with indices in a set F such that F has two proproperties: 1. if i and j are distinct indices in F, then Si and Sj do not intersect; 2. the union of all subsets with indices in F is exactly G.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 5

Covering method for multicast destinations

The multicast covering problem can be
defined as follows. There are D >= 2
destinations possible, so D elements in a
set S of all possible destinations across
a switch. The destinations are labeled
with the integers 1, 2, ..., D.

There are N nonempty, distinct subsets
{Si},i=1,2, ..., N <= 2^D of the D
elements. The set of subsets {Si}
includes all D subsets consisting of
exactly one element. The set of all
integer labels used to enumerate the
subsets is A = {1, 2, ..., N}.

There is in addition a given subset G. G
might be exactly the same as one of the
subsets in {Si}, but in general it is
not. The problem is to find a set of
subsets among {Si} with indices in a set F
such that F has two proproperties:

1. if i and j are distinct indices in F,
then Si and Sj do not intersect;
2. the union of all subsets with indices
in F is exactly G.

Such a set of subsets with indices in F is
called a "correct cover." An "optimal
correct cover" has no more subsets than
any correct cover.

A related problem is discussed on pages
135-138 of

Kyle Loudon, Mastering Algorithms in C,
O'Reilly, Sebastopol CA, 1999

The related problem has G = {1, 2, ..., D}
and omits the intersection constraint. An
algorithm for generating a cover (not
necessarily optimal) is given that is
essentially D loops each of complexity
O(D^2), so the algorithm is O(D^3)
altogether.

Following is an algorithm that solves the
Multicast Covering Problem. It is not

1

Page 2 of 5

optimal, but the inventors feel it will be
well suited to real applications. This
optimism stems from two anticipated
characteristics of multicasting in real
networks:

1. The instances of the multicast problem
are likely to be highly repetitive or at
least contain many destinations in common.
Hence correct covers of two consectutive
instances have a greater than random
chance that they share some large common
subsets.

2. Correct covers will tend to contain
only a few subsets with several elements,
plus several subsets with single elements.

Our solution is biased toward large
subsets, hence tends to select a
relatively small number of subsets (number
of indices in F).

2

Page 3 of 5

The invention includes the following
algorithm.

Write every subset Si as a binary D-vector
in which component j is 1 if and only if
element j is in the subset.

The cardinality C(Si) of a subset Si is
the number of elements in Si, that is, the
sum of th...