Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-04-20
2004-06-15
Vu, Huy D. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S406000
Reexamination Certificate
active
06751219
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to network systems, and more particularly to multicast of packets in a mesh-based packet switch.
BACKGROUND OF THE INVENTION
Ever-increasing demand for telephone and data communications has led to the development of higher-capacity media such as fiber optic cables. Standards have been developed to aggregate many separate telephone calls (DS0 lines) onto high-speed data backbones. One widely-used optical standard originally developed to aggregate phone calls is the Synchronous Optical NETwork (SONET) standard.
Traditional telephone switches for SONET have included Time-Division-Multiplexed (TDM) circuit switches. More recently, packet-based switches have been used to emulate such TDM switches. See the related application for “Adaptive Fault-Tolerant Switching Network With Random Initial Routing and Random Routing Around Faults”, U.S. Ser. No. 09/470,144, assigned to Corvia Networks of Sunnyvale, Calif., which solves the problem of packet blocking and localized congestion by initially routing packets to a randomly-selected node within the network fabric. SONET data received by a switch is divided into packets which are sent through the switch fabric to the output (egress) port. At the egress port, the packets are re-assembled in order to form the outgoing SONET data. The switch fabric consists of store-and-forward nodes that receive packets and send them toward their destination, the egress port. The nodes are connected together in a mesh to provide many alternate routes, ensuring that node failures can be routed around.
SONET data is arranged into frames that are sent every 125 micro-seconds (&mgr;sec). Since one SONET frame is divided into several packets that may be sent through the switch fabric over different routes, the latency through the switch can vary. Routing algorithms used by the nodes must be carefully selected to ensure that statistically such latencies do not exceed the frame latency of 125 &mgr;sec.
While most network traffic is point-to-point (unicast), some special applications require multicast functionality. For example, video distribution requires that the packets containing the video data be replicated and sent to several different users, often through different egress ports. Other applications that use multicast include port monitoring or mirroring, protection-path routing, in-service rollover, and drop-and-continue. Port mirroring/monitoring is used for diagnostic purposes, to observe the data at another port without interfering with its forwarding. Protection-path routing is used to send duplicate data over an alternative route for enhanced reliability. In-service rollover is temporarily routing data over a duplicate new path to its destination in preparation for a permanent switchover to the new path. Drop-and-continue is a method of multicasting over a continuing network interconnection such as a ring where the data is dropped off at an intermediate node but also continues to another destination.
Parallel Multicast Causes Congestion—FIG.
1
FIG. 1
shows multicast by replicating a packet at an ingress port. One simple approach to implement multicast is to replicate packets as they are inserted into the switch fabric at the input (ingress) port. Packet
12
is a packet received by the network switch and inserted into the switch fabric by ingress port
10
. Ingress port
10
formats packet
12
for transmission through switch fabric
28
, and makes several duplicate copies
14
of the re-formatted packet
12
.
Each of the duplicate copies
14
contains a destination address for a different egress port
20
-
25
. Thus the duplicate copies
14
are not exact duplicates, but do contain the same data payload as packet
12
. Of course, packet
12
can itself be a portion of a larger data group, such as a row in a SONET frame. Each of the duplicate copies
14
is routed toward its destination egress port
20
-
25
over a different path through switch fabric
28
. For example, one of the duplicate copies
14
is routed from ingress port
10
through nodes
30
,
31
,
32
to egress port
25
, while another of the duplicate copies
14
is routed from ingress port
10
through node
35
to egress port
24
. Other routes include node
33
to egress port
20
, node
34
to egress port
21
, and node
35
to egress ports
22
,
23
.
Egress ports
20
-
25
each receive one of the duplicate copies
14
and generate packet
16
containing the same data as packet
12
. One packet
12
input to ingress port
10
is used to generate six packets
16
to six egress ports
20
-
25
. This is known as parallel multicast, since the duplicate copies
14
pass through switch fabric
28
in parallel to each other, at about the same time.
While such parallel multicast is useful, replication of the packet at the ingress port causes a multiplication of packet traffic within switch fabric
28
. In this example, six times the traffic of a single packet is produced at node
10
and at neighboring nodes creating a routing “hot spot” of congestion. Such heavy traffic can slow the switch since several nodes must route the additional packet traffic. Other packets passing through switch fabric
28
from other ingress ports
18
can be slowed by the multicast traffic. Failures such as dropped packets can occur when packets are delayed.
Some nodes in switch fabric
28
can become congested from the multicast traffic. For example, node
35
receives three of the duplicate copies
14
from ingress port
10
. Node
35
can become congested by the sudden arrival of several multicast packets. Ingress port
10
may also be locally congested, having to transmit all the duplicate copies
14
.
Serial Multicast Increases Latency—FIG.
2
FIG. 2
shows serial multicast by packet duplication at egress ports. Traffic from multicast can be reduced by using a serial or drop-and-continue method. Packet
12
received by ingress port
10
is not duplicated. Instead, packet
12
is sent to egress port
20
through node
33
in switch fabric
28
. Once packet
12
arrives at its first destination, egress port
20
, packet
12
is replicated to form packet
16
in addition to packet
12
. Packet
16
is output from switch fabric
28
by egress port
20
, while packet
12
is re-injected into switch fabric
28
. Packet
12
then continues on to its second destination, egress port
21
. Another duplicate packet
16
is made by egress port
21
for output, while packet
12
continues to the third destination, egress port
22
.
A duplicate of packet
12
is made for output as packet
16
passes through each egress port
20
-
23
. Once packet
12
arrives at its final destination, egress port
24
, it is removed from switch fabric
28
and output as packet
16
by egress port
24
.
Such serial multicast results in five copies of packet
12
being transmitted from egress ports
20
-
24
with minimal traffic increase. Local congestion from many duplicate copies of the multicast packet are avoided.
Latency Delays Packets into Next SONET Frame—FIG.
3
One problem with the serial multicast of
FIG. 2
is latency.
FIG. 3
shows serial multicast packets in SONET time frames. A delay occurs for each packet as it travels through the switch fabric. Also, a delay occurs while each egress port replicates the packet and re-injects it into the switch fabric. Since delays are cumulative, the last egress ports
23
,
24
experience greater delays than do earlier egress ports
20
-
22
.
Packet
12
arrives at ingress port
10
of
FIG. 2
at arrival time TA shown on FIG.
3
. Arrival time TA occurs near the beginning of a first SONET frame. After a first propagation delay TP, the packet arrives at the first egress port. The first packet is output at time TA+TP. The packet is duplicated and sent from the first egress port to the second egress port
21
, which requires another propagation delay TP. Thus the second egress port outputs its packet at time TA+TP+TP. This is still within the first SONET frame.
The second egress port duplicates the packet and sends it to the third
Boura Younes
Lipp Robert J.
Auvinen Stuart T.
Aztech Partners, Inc.
Philpott Justin M
Vu Huy D.
LandOfFree
Multicast packet duplication at random node or at egress... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicast packet duplication at random node or at egress..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicast packet duplication at random node or at egress... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3314164