Multiplex communications – Pathfinding or routing
Reexamination Certificate
1999-05-27
2003-04-01
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
C370S389000
Reexamination Certificate
active
06542496
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to a packet switching method and apparatus in which information of a forwarding packet is used in routing, and particularly to a packet switching method and apparatus suitable for multicast communications.
The term “multicast communications” means that a packet addressed to a multicast group from one computer (node) is relayed and transmitted to a plurality of computers (nodes) belonging to the group.
FIG. 1
is a diagram showing the concept of the multicast communications. As illustrated, a packet from a computer
150
of source S is relayed and transmitted through routers (packet switching devices) R
1
-R
9
to all computers
151
-
157
associated with the same group G. Here, the group is the communication unit of the multicast communications. The router holds a plurality of relay interfaces for one group. Fundamentally, in the multicast communications, the same packet is not relayed to the same computer and router. Therefore, the receiving interface of a router is always a
1
-interface. However, the above fact is not true for the route solution stage in the routing protocol.
In the multicast communications shown in
FIG. 1
, each router received a packet addressed to a multicast group does not relay the packet to a link
158
between the routers R
1
and R
4
, a link
159
between the routers R
4
and R
3
, a link
160
between the routers R
2
and R
3
, a link
161
between the routers R
6
and R
9
, and a link
162
between the routers R
8
and R
9
all of which are the redundant routes of the multicast communications. In addition, when the source side of data is referred to as an upstream side and the destination side of data is referred to as a downstream side, the router R
7
, for example, does not need to relay the packet to a path
163
on the upstream side since the router R
2
located on the upstream side relays the packet to the computer
151
connected to the router R
2
, but it may relay the packet only to links
164
and
165
on the downstream side.
FIG. 2
is a diagram showing one example of a network system for the IP (Internet Protocol) multicast communications. Routers R
1
-R
6
are routers for IP multicast. That is, the routers R
1
-R
6
are packet repeaters for relaying IP datagram which is a communication unit packet of IP protocol. Computers
126
-
134
of sources S
1
-S
9
are computers for IP multicast protocol, and are sending and receiving terminals of the IP datagram. Groups G
1
-G
3
indicate the ranges of the IP multicast communications.
In this network system, the computes
126
,
128
and
134
of sources S
1
, S
3
and S
9
belong to the group G
1
, the computers
128
,
129
,
133
and
134
of sources S
3
, S
4
, S
8
and S
9
to the group G
2
, and the computes
127
,
130
,
131
,
132
and
133
of sources S
2
, S
5
, S
6
, S
7
and S
8
to the group G
3
. Therefore, the IP datagram transmitted to the group G
1
is relayed to the computers
126
,
128
and
134
of sources S
1
, S
3
and S
9
, the IP data gram transmitted to the group G
2
is relayed to the computers
128
,
129
,
133
and
134
of sources S
3
, S
4
, S
8
and S
9
, and the IP datagram transmitted to the group G
3
is relayed to the computers
127
,
130
,
131
,
132
and
133
of sources S
2
, S
5
, S
6
, S
7
and S
8
. The router R
1
at the center of the diagram has an interface “a” connected to the router R
2
, an interface “b” connected to the router R
6
, an interface “c” connected to the router R
4
, an interface “d” connected to the computer
128
of source S
3
, an interface “e” connected to the computer
129
of source S
4
, and an interface “f” connected to the router R
5
.
The multicast communications routing system includes a system in which the user previously sets the multicast communication routing information in each router, and a system in which the multicast communications routing information is transmitted and received between the routers according to the routing protocol to automatically calculate a multicast communications route. Here, as the multicast routing protocol, there are a routing protocol X and a routing protocol Y which will be described below. The routing protocol X is the routing protocol of the broadcast and prune system, and there is DVMRP (RFC1075) as a typical example. The routing protocol Y is the routing protocol of the explicit join system, and there is PIM-SM (RFC2117) as a typical example.
FIGS. 3A and 3B
are diagrams for explaining the operation of the routing protocol X. According to the routing protocol X, when a router R
10
receives IP datagram
170
from a computer
176
of source S
1
, it relays the IP datagram
170
to routers R
20
, R
30
, R
40
on the downstream side (see IP datagram
171
-
173
). The router R
20
received the IP datagram
171
relays it to a computer
177
since the router R
20
is connected to the computer
177
belonging to the destination group G
1
of the IP datagram
171
. The router R
30
received the IP datagram
172
also repays it to a computer
178
since the router R
30
is connected to the computer
178
belonging to the destination group G
1
of the IP datagram
172
. However, the router R
40
received the IP datagram
173
transmits a prune request
175
, which rejecting the relaying of IP datagram of the source address S
1
and the destination group G
1
, to the router R
10
which relayed the IP datagram
173
, since the connected computer
179
does not belong to the destination group G
1
of the IP datagram
173
. Then, as shown in
FIG. 3B
, the IP router R
10
received the prune request
175
receives IP datagram
180
having the rejected source address S
1
and destination group G
1
, but does not relay the IP datagram
180
to the router R
40
which transmitted the prune request
175
.
FIGS. 4A and 4B
are diagrams for explaining the operation of the routing protocol Y. According to the routing protocol Y, as illustrated in
FIG. 4A
, computers
190
and
191
which desire to relay IP datagram of a destination group G
1
issue join requests
194
and
195
, which include a group information (G
1
), to routers R
21
and R
31
on the upstream side, respectively. The routers R
21
and R
31
register interfaces
204
and
205
which received the join requests
194
and
195
, and the group information (G
1
) included in the join requests
194
and
197
. Also, the routers R
21
and R
31
issue the join requests
196
and
197
, which include the group information (G
1
), to the router R
11
on the upstream side. The router R
11
registers interfaces
201
and
202
which received the join requests
196
and
197
, and the group information (G
1
) included in the join requests
196
and
197
. Then, as shown in
FIG. 4B
, when the router R
11
receives IP datagram
200
of the destination group G
1
coincident with the registered group information (G
1
) from the computer
193
of source S, it relays the IP datagram
200
only to the routers R
21
and R
31
connected to the interfaces
201
and
202
which received the join requests
196
and
197
. The routers R
21
and R
31
operate as does the router R
11
. Thus, the IP datagram
200
is transmitted to the computers
190
and
191
which issued the join requests
194
and
195
, but is not transmitted to the computer
192
which did not issue the joint request.
FIG. 5
is a diagram showing one example of the header format of IP datagram. In the multicast communications, a source address (SX) is stored in a source address field
210
of the IP datagram header, and a multicast destination group address (GX) is stored in a destination address field
211
of the IP datagram header. The destination group address (GX) is of class D in order to coexist with or be distinguished from the existing IP destination address (of classes A-C).
FIG. 6
shows the class-D address format. The first four bits “1110” in
FIG. 6
means the class D. By the way, the class A is indicated by the first one bit of “0”, the class B by the second two bits of “10”, and the class C by the f
Fukuda Masashi
Hirota Nagayuki
Morimoto Shigeki
Sako Yoshihito
Sekino Hiroshi
Patel Ajit
Shah Chirag
LandOfFree
Packet switching method and apparatus thereof does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet switching method and apparatus thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet switching method and apparatus thereof will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3003014