 |
Claims  |
|
|
We claim:
1. A line adapter for a packet switching node in a communication network,
including a programmable processing means (SPP) for receiving and
transmitting data packets of fixed or variable length to one or more
outputs, said line adapters comprising:
a first storing means for buffering each data packet in one or more
buffers;
means for identifying said buffers,
a second storing means including means for queuing said buffer identifiers
in buffer lists, each buffer list identifying a data packet;
means for identifying said buffer lists;
means for queuing, in said second storing means, buffer list identifiers in
packet lists, each packet list identifying a queue;
means for identifying said packet lists;
means for processing a routing header of each data packet;
means for associating with each output an output queue for stacking the
packet list identifiers of the data packets to transmit on said outputs;
means for routing the data packets to one or a plurality of outputs;
means for processing said routing header further comprising means for
determining and selecting the output queue corresponding to the
destination of each data packet;
said means for routing further comprising:
means for copying the buffer list identifier of the data packet to transmit
in the output queue corresponding to said selected output;
means for handling each data request for said outputs in real time;
means for releasing said buffers in said first storing means, and said
buffer identifiers and said buffer list identifiers from said second
storing means;
said means for handling data requests further comprising means for handling
independently the output queues, which further includes:
means for dequeuing in parallel the packet identifiers requested by the
outputs; and
means for dequeuing the buffer identifiers stacked in the buffer list
identified by said packet identifiers.
2. The line adapter according to claim 1 wherein:
said first storing means includes means for writing and reading said data
packets in buffers of fixed length independently of said programmable
processing means; and
said second storing means includes means for separately storing said buffer
lists and said packet lists under control of said programmable processing
means.
3. The line adapter according to claim 1 wherein said programmable
processing means (SPP) comprises:
a background procedure for processing the data packets,
a plurality of real time procedures triggered under control of each output
to request the contents of a new buffer, said real time procedures being
independent of the routing mode used.
4. The line adapter according to claim 3 wherein said means for releasing
in said means for routing is executed in said background procedure.
5. The line adapter according to claim 1 wherein:
said means for identifying said buffers includes buffer pointers (B.sub.--
PTR) identifying said buffers and stacked in one or more buffer lists
(B.sub.-- LIST);
said means for identifying said buffer lists includes packet pointers
(P.sub.-- PTR) identifying said buffer lists (B.sub.-- LIST) and stacked
in one or more packet lists (P.sub.-- LIST); and
said means for identifying said packet lists include queue pointers
(Q.sub.-- PTR) identifying said packet lists (P.sub.-- LIST) and stacked
in one or more queue lists (Q.sub.-- LIST); and
wherein each buffer list, packet list and queue list includes a prefix for
storing information related to the data contained in said each buffer
list, packet list and queue list.
6. The line adapter according to claim 5 wherein said buffer list prefix
includes control and routing information contained in the data packet
header.
7. The line adapter according to claim 6 wherein said buffer list prefix
further includes a multicast counter (MCC COUNTER) and a packet pointer
(P.sub.-- PTR).
8. The line adapter according to claim 7 wherein a status of each output
queue is stored in an output queue table located in said second storing
means, said status including:
the output queue pointer (Q.sub.-- PTR),
a current packet pointer (cur P.sub.-- PTR) for the last packet dequeued
from the output queue;
a current buffer pointer (cur B.sub.-- PTR) for the last buffer dequeued
from the current packet pointer; and
a state of the output queue depending on if the output queue is active, an
output queue being active during the time said data packet identified by
said current packet pointer is transmitted to said selected output.
9. The line adapter according to claim 8 wherein said background procedure
includes:
means for detecting a new buffer list;
means for reading the routing information in the buffer list prefix;
means for initializing the multicast counter in the buffer list prefix with
the number of outputs towards which the data packet must be transmitted;
means for copying the packet pointer of the buffer list in its own prefix;
means for selecting an output queue according to the destination of the
data packet, queuing in said output queue the packet pointer and testing
the state of said output queue, wherein:
if the state is active a new output queue is selected according to the
other destinations of the data packet;
if the state is not active:
a packet pointer is dequeued from said output queue and saved as the
current packet pointer in said output queue table;
a buffer pointer is dequeued from the buffer list identified by said
current packet pointer and saved as the current buffer pointer in said
output queue table;
a message is sent to the output;
the output queue is set in an active state; and
a new output queue is selected according to the other destinations of the
data packet;
when said packet pointer has been queued in all selected output queues the
background process returns to its waiting state.
10. The line adapter according to claim 9 wherein said plurality of real
time procedures comprise:
a first real time procedure triggered by the outputs on request for a new
buffer including:
means for getting the packet pointer corresponding to the last output queue
processed in the output queue table;
means for dequeing the next buffer pointer in the buffer list identified by
said packet pointer;
means for saving said packet pointer into the output queue table as the
current packet pointer;
means for saving said buffer pointer into the output queue table as the
current buffer pointer;
a second real time procedure triggered by the outputs on request for a new
packet including:
means for getting the packet pointer corresponding to the last output queue
processed in the output queue table;
means for queuing said packet pointer in a release queue for a delayed
release;
means for testing if the output queue is empty or not, wherein:
if said output queue is empty, said output queue is set in a non-active
state;
if said output queue is not empty:
a next packet pointer is dequeued from said output queue;
said next packet pointer is saved as the current packet pointer in the
output queue table;
a first buffer pointer of the buffer list identified by said packet pointer
is saved as the current buffer pointer in the output queue table; and
a message is sent to the output associated with said output queue.
11. The line adapter according to claim 1 wherein the management of the
buffers in said first storing means is realized by means of a first
permanent list (free buffer list) containing all of the buffer pointers.
12. The line adapter according to claim 1 wherein the management of the
buffer lists in said second storing means is realized by means of a second
permanent list (free packet list) containing all of the packet pointers.
13. The line adapter according to claim 1 wherein said releasing means in
said background procedure comprises:
means for testing the contents of the release queue:
if the release queue is empty, then terminating the release;
if the release queue is not empty:
dequeuing a packet pointer from the release queue;
decrementing the buffer list prefix counter by one;
testing if the multicast counter value is equal to zero,
if the multicast counter value is not zero, then testing the contents of
the release queue:
if the release queue is empty, then terminating the release;
if the release queue is not empty, then dequeuing the next packet pointer
from the release queue;
if the multicast counter value is zero:
retrieving the original packet pointer from the buffer list prefix
identified by said packet pointer;
releasing the buffer list and buffers identified by said packet pointer
from the free packet list and the free buffer list;
testing the contents of the release queue.
14. The line adapter according to claim 5 wherein each list pointer (packet
pointer (P.sub.-- PTR) or queue pointer (Q.sub.-- PTR)) comprises:
a first field (LID) for identifying the list;
a second field for identifying a next pointer (TAIL) to stack in said list;
a third field for identifying a first pointer (HEAD) stacked in said list.
15. The line adapter according to claim 14 wherein said means for queuing
comprises:
means for incrementing the TAIL field of the list pointer;
means for simultaneously storing the pointer identified by the TAIL field
in the list identified by the LID field;
means for generating a list full indicator.
16. The line adapter according to claim 14 wherein said means for dequeuing
comprises:
means for incrementing the HEAD field of the list pointer;
means for simultaneously reading the pointer identified by the HEAD field,
in the list identified by the LID field;
means for generating a list empty indicator.
17. The line adapter according to claim 15 wherein said means for queuing
further includes a means for testing said list full indicator, and said
means for dequeuing further includes a means for testing said list empty
indicator.
18. The line adapter according to claim 1 wherein said programmable
processing means includes:
an arithmetical and logical unit,
a register file,
a sequencer,
an instruction file,
a direct memory access controller module, and
a physical memory address generator.
19. A routing method in a line adapter for a packet switching node in a
communication network, including programmable processing means (SPP) for
receiving and transmitting data packets of fixed or variable length to one
or more outputs, said routing method comprising the steps of:
buffering each data packet in one or more buffers in a first storing means;
identifying said buffers;
queuing, in a second storing means, said buffer identifiers in buffer
lists, each buffer list identifying a data packet;
identifying said buffer lists;
queuing buffer list identifiers in packet lists in said second storing
means, each packet list identifying a queue;
identifying said packet lists;
processing a routing header of each data packet;
associating with each output an output queue for stacking the packet list
identifiers of the data packets to transmit on said outputs;
routing the data packets to one or a plurality of outputs;
said processing the routing header step further comprising the step of
determining and selecting the output queue corresponding to the
destination of each data packet;
said routing step further comprising the steps of:
copying the buffer list identifier of the data packet to transmit in the
output queue corresponding to said selected output;
handling each data request for said outputs in real time;
releasing said buffers in said first storing means, and said buffer
identifiers and buffer list identifiers from said second storing means;
said handling each data request step including the step of handling
independently the output queues by
dequeuing in parallel the packet identifiers requested by the outputs; and
dequeuing the buffer identifiers stacked in the buffer list identified by
said packet identifiers. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
TECHNICAL FIELD
The present invention relates to an efficient point-to-point and
multi-points routing system and method for programmable data communication
adapters in packet switching nodes of high speed networks.
BACKGROUND ART
The telecommunication environment is in full evolution and has changed
considerably this recent years. The principal reason has been the
spectacular progress realized in the communication technology:
the maturing of fiber optical transmission. High speed rates can now be
sustained with very low bit error rates.
the universal use of digital technologies within private and public
telecommunications networks.
In relation with these new emerging technologies, the offer of the
telecommunication companies, public or private, are evolving:
The emergence of high speed transmissions entails an explosion in the high
bandwidth connectivity.
the increase of the communication capacity generates more attractive
tariffs.
A higher flexibility is offered to the users to manage their growth through
a wide range of connectivity options, an efficient bandwidth management
and the support of new media.
Once sampled and digitally encoded, voice, video and image derived data can
be merged with pure data for a common and transparent transport.
Abundant, cheap communications means that many potential applications that
where not possible before because of cost are now becoming attractive. In
this environment, three generic requirements are expressed by the users:
Doing old applications better,
Optimizing communication networks,
Doing new applications.
High Performance Networks
In a first step, T1 backbone networks were primarily deployed with TDM
(Time Division Multiplexing) technology to achieve cost savings through
line aggregation. These systems easily supported the fixed bandwidth
requirements of host/terminal computing and 64 Kbps PCM (Pulse Code
Modulation) voice traffic.
The data transmission is now evolving with a specific focus on applications
and by integrating a fundamental shift in the customer traffic profile.
Driven by the growth of workstations, the local area networks (LAN)
interconnection, the distributed processing between workstations and super
computers, the new applications and the integration of various and often
conflicting structures--hierarchical versus peer to peer, wide (WAN)
versus local (LAN) area networks, voice versus data--the data profile has
become higher in bandwidth, bursting, non deterministic and requires more
connectivity. Based on the above, it is clear that there is strong
requirement to support distributed computing applications across high
speed backbones that may be carrying LAN traffic, voice, video, and
traffic among channel attached hosts, business workstations, engineering
workstations, terminals, and small to intermediate file servers. This
traffic reflects a heterogeneous mix of:
end user network protocols including Ethernet, Tocken Ring, APPN, FDDI,
OSI, ISDN, ATM . . . , and
real time (steady stream traffic such as voice and video) and non real time
(bursty nature traffic such as interactive data) transmissions.
This vision of a high speed protocol-agile backbone network is the driver
for the emergence of fast packet switching networks architectures in which
data, voice, and video information is digitally encoded, chopped into
small packets and transmitted through a common set of nodes and links.
Although low speed links may exist, the availability of fiber optic links
will make cost effective to have a few links of high speed rather that
many links of low speed. In addition to the high speed backbone, there
exists a peripheral network which essentially provides access to the
switching nodes. This peripheral network is composed of relatively low
speed links which may not use the same protocols or switching techniques
used in the backbone. In addition, the peripheral network performs the
task of multiplexing the relatively slow end users traffic to the high
speed backbone. Thus, backbone switching nodes are principally handling
high speed lines. The number of high speed links entering each switching
node is relatively small but the aggregate throughput very high in the
Giga-bits per second range.
Throughput
The key requirement of these new architectures is to reduce the end-to-end
delay in order to satisfy real time delivery constraints and to achieve
the necessary high nodal throughput for the transport of voice and video.
Increases in link speeds have not been matched by proportionate increases
in the processing speeds of communication nodes and the fundamental
challenge for high speed networks is to minimize the packet processing
time within each node. As example, for meeting a typical 100 ms delay to
deliver a voice packet between two end users:
A total of 36 ms might be needed for the packetization and play-out
functions at the end points.
About 20 ms is the unalterable propagation delay needed, say, to cross the
United States.
There remains 44 ms for all the intra-node processing time as the packet
moves through the network. In a 5 nodes network, each node would have
about 8 ms for all processing time including any queueing time. In a 10
nodes network, each node would have about 4 ms.
Another way of looking the same constraint is illustrated in FIG. 1: taking
a node with an effective processing rate of 1 MIPS (Millions of
Instructions Per Second), it is possible to fill a 9.6 kbps line with 1000
byte packets even if a network node must execute 833 000 instructions per
packet processed. For a 64 kbps line the node can afford 125 000
instructions per packet. In order to fill an OC24 link, however, our 1
MIPS node could only execute 7 instruction per packet! In the latter case
even an effective rate of 10-30 MIPS would allow only 70-200 instructions
per packet.
In order to minimize the processing time and to take full advantage of the
high speed/low error rate technologies, most of the transport functions
provided by the new high bandwidth network architectures are performed on
an end-to-end basis. This includes the flow control and error recovery for
data, the packetization and reassembly for voice and video. The protocol
is simplified:
First, there is no need for transit node to be aware of individual (end
user to end user) transport connections.
Secondly high performance and high quality links does not require any more
node to node error recovery or re-transmission. Congestion and and flow
control are managed at the access and end points of the network
connections reducing both the awareness and the function of the
intermediate nodes.
Packet size
Transmission of real time data, like voice or video packets, which must be
delivered to the receiver at a steady, uniform rate (isochronous mode)
requires the use of short packets. In another side, pure data does not
have any problem with transit delay. They are generated in a very bursty
and non deterministic manner. The longer packet are, the fewer packets per
second must be switched for a given data throughput. In order to take full
advantage of the different data packet transmission systems, the data
transfer across the network must be done with packets of nearly the same
size as the user packets without processing them into artificial lengths.
As opposed to solely data networks or solely voice or video networks, the
high speed network architectures have to support a plurality of
heterogeneous transmission protocols operating with variable length
packets.
Connectivity
In a high speed network, the nodes must provide a total connectivity. This
includes attachment of the customer's devices, regardless of vendor or
protocol, and the ability to have the end user communicate with any other
device. Traffic types include data, voice, video, fax, graphic, image. The
node must be able to take advantage of all common carrier facilities and
to be adaptable to a plurality of protocols: all needed conversions must
be automatic and transparent to the end user. For example, a high speed
node must not have any dependencies on the existence of SNA (System
Network Architecture) equipments on a user network. It has to be able to
offer a similar level of service in a SNA environment as in a non-SNA
environment made of routers, Private Branch eXchanges (PBXs), Local Area
Networks (LAN) . . . .
Key Requirements
The efficient transport of mixed traffic streams on very high speed lines
means for each communication node of the network a set of requirements in
term of performance and resource consumption which can be summarized as
follows:
a very short packet processing time,
a very high throughput,
an efficient queue and buffer management,
a limited number of instructions per packet,
a minimum impact of the control flow on the user traffic, and
a very large flexibility to support a wide range of connectivity options.
The high bandwidth dictates the need of specialized hardware to support
very fast packet handling and control protocols, and to satisfy the real
time transmission needs of the voice and video traffic. The processing
time being the main bottleneck in high speed networks, most of the
communication nodes today are built around high speed switching hardware
to off-load the routing packet handling and routing functions from the
processor.
However, on equal performances, a software approach represents the most
adequate solution for each node to meet the connectivity and flexibility
requirements and to optimize the manufacturing and adaptation costs. The
line adapters, are based on a common hardware design and are configured by
means of a specific programming to execute either the access point or
inter nodal transport functions. The adaptability of the adapters to
support different access protocols and data streams--Frame Relay, HDLC
(High level Data Link-Control), CBO (Continuous Bit Operations), ATM
(Asynchronous Transfer Mode), . . .--is provided by logical components
called Access Agents. Such logical associations Adapter/Access Agent are
specified by software, providing a very large flexibility at a reduced
cost. Each line adapter is automatically configured at system initiation
according to:
the adapter function, and
the access protocol.
Programmable High Performance Communication Nodes
The throughput of a communication adapter is defined as the total time
required to handle a data packet from the input to the output. However,
the packet size being application dependent, two measures are currently
used to evaluate the performances of adapters:
first, the number of packets of fixed length the adapter is able to handle
in a second (packet throughput),
second, the number of bits per second the adapter is able to transmit in
case of infinite packet length (data throughput).
The performances depend on the hardware and on the processor capabilities
but the main throughput limiting factor is the packet processing time and
this processing time is directly related to the number of instructions
required to handle a packet. The operations on the packets can be divided
in two categories:
the background process with the operations of packet routing,
assembling--disassembling, formatting, bandwidth management, priority, . .
. . This process is designed according to the adapter function, but in the
same application, the background process is identical for all packets
independently of their size.
the buffering process with the interrupt routines. This operation is
generic for all adapter types. The processing time required for this
operation is directly proportional to the packet length.
The interrupt routines are the way real time is supported by the processor.
They must be as short as possible to avoid the overrun on the input device
and the underrun on the output device. They commands the performance of
the adapter in term data throughput (bits per second). For packets of
infinite length, the background process disappears and the throughput
bottleneck is the interrupt response time which depends of the queuing and
dequeueing operations.
In another way, to maximize the packet throughput (number of packets per
seconds that the adapter is able to transmit), the number of instructions
required by the background process must be reduced to a minimum.
Non published European patent application 93480087.1 (IBM docket FR993027)
entitled Programmable High Performance Data Communication Adapter for
Packet Transmission Networks (prior art under Article 54(3) EPC), which
content is herein incorporated by simple reference, discloses a high
performance packet buffering method and system in a programmable data
communication adapter. The adapter includes a programmable processor, for
receiving and transmitting data packets of fixed or variable length. The
system is designed to optimize the queueing and dequeueing operations and
in particular to minimize the number of instructions to manipulate the
packets. It is characterized in that it comprises:
means for storing data packets in buffers,
means for identifying said data packets in the buffers
means for queueing in a local memory the packet identifiers in a single
instruction,
means for dequeueing from the local memory the packet identifiers in
another single instruction,
means for releasing the buffers.
Each instruction comprises up to three operations executed in parallel by
said processor:
an arithmetical and logical (ALU) operation on the packet identifiers,
a memory operation on the local memory, and
a sequence operation.
SUMMARY OF THE INVENTION
An efficient point-to-point and multi-points routing system and method for
data communication adapters in packet switching nodes of a high speed
network is disclosed. The general principles of the present invention can
be summarized as follows:
data packets are never copied during their routing through the adapter,
only packet pointers are copied for each destination,
each output is processed independently on a priority mode,
no overhead generated by the multi-points routing in the interrupt
procedures,
release of the resources on a non priority mode (background procedure).
DESCRIPTION OF THE DRAWINGS
FIG. 1 shows the processing times (or number of instructions per second)
required in function of the different line throughputs supported by the
present invention.
FIG. 2 shows a typical model of high speed packet switching network
including the access and transit nodes claimed in the present invention.
FIG. 3 describes a high speed Routing Point according to the present
invention.
FIG. 4 shows a programmable high performance adapter according to the
present invention.
FIG. 5 represents the receive and transmit data flows in a Trunk Adapter.
FIG. 6 illustrates the buffer, packet and queue structures according to the
present invention.
FIG. 7 illustrates the Control Point Spanning Tree.
FIG. 8a shows a graphical representation of a typical header for packets
transmitted in a network such as represented in FIG. 2.
FIG. 8b shows a graphical representation of a Multicast Tree Routing Field
in the header represented in FIG. 8a.
FIG. 9 represents the List Pointer structure according to the present
invention.
FIG. 10 shows an overview of the multicast mechanism as claimed in the
present invention.
FIG. 11 represents the Buffer List structure of a packet supporting the
multicasting routing according to the present invention.
FIG. 12 represents the Free Buffer List structure according to the present
invention.
FIG. 13 represents the Processor functional structure according to the
present invention.
FIG. 14 shows a general view of the packet processing in the programmable
adapter according to the present invention.
FIG. 15 shows the packet routing and multicasting process according to the
present invention.
FIG. 16 shows the interrupt procedure at packet level according to the
present invention.
FIG. 17 shows the interrupt procedure at buffer level according to the
present invention.
FIG. 18 illustrates the data flow between the Specific Purpose Processor
(SPP), the Direct Access Memory (DMA) and IO1 device according to the
present invention.
FIG. 19 is a flow chart illustrating the release mechanism of the memory
resources in the background procedure as claimed in the present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENT OF THE INVENTION
As illustrated in FIG. 2, a typical model of communication system is made
of several user networks (212) communicating through a high performance
network (200) using private lines, carrier provided services, or public
data networks. Each user network can be described as a set of
communication processors and links (211) interconnecting large computers
used as Enterprise Servers (213), user groups using workstations or
personnel computers attached on LAN (Local Area Networks 214),
applications servers (215), PBX (Private Branch eXchange 216) or video
servers (217). These user networks, dispersed in different establishments,
need to be interconnected through wide area transport facilities and
different approaches can be used for organizing the data transfer. Some
architectures involve the checking for data integrity at each network
node, thus slowing down the transmission. Others are essentially looking
for a high speed data transfer and to that end the transmission, routing
and switching techniques within the nodes are optimized to process the
flowing packets towards their final destination at the highest possible
rate. The present invention belongs essentially to the latter category and
more particularly to the fast packet switching network architecture
detailed in the following paragraphs.
High Speed Packet Switching Networks
The general view in FIG. 2 shows a fast packet switching transmission
system comprising eight nodes (201 to 208) each node being interconnected
by means of high speed communication lines called Trunks (209). The access
(210) to the high speed network by the users is realized through Access
Nodes (202 to 205) located at the periphery. These Access Nodes comprise
one or more Ports, each one providing an access point for attaching
external devices supporting standard interfaces to the network and
performing the conversions required to transport the users data flow
across the network from and to other external devices. As example, the
Access Node 202 interfaces respectively a Private Branch eXchange (PBX),
an application server and a hub through three Ports and communicates
through the network by means of the adjacent Transit Nodes 201, 208 and
205.
Switching Nodes
Each network node (201 to 208) includes a Routing Point where the incoming
data packets are selectively routed on the outgoing Trunks towards the
neighboring Transit Nodes. Such routing decisions are made according to
the information contained in the header of the data packets. In addition
to the basic packet routing function, the network nodes also provide
ancillary services such as:
the determination of routing paths for packets originated in the node,
directory services like retrieving and updating information about network
users and resources,
the maintaining of a consistent view of the physical network topology,
including link utilization information, and
the reservation of resources at access points of the network.
Each Port is connected to a plurality of user processing equipments, each
user equipment comprising either a source of digital data to be
transmitted to another user system, or a data sink for consuming digital
data received from another user system, or, typically, both. The
interpretation of the users protocols, the translation of the users data
into packets formatted appropriately for their transmission on the packet
network (200) and the generation of a header to route these packets are
executed by an Access Agent running in the Port. This network layer header
(800) shown in FIG. 8a is made of Control (801), Routing (802) and
Redundancy Check (803) Fields.
The Control Fields (801) include, among other things, an encoded
identification of the protocol to be used in interpreting the Routing
Field.
The Routing Fields (802) contain all the information necessary to route the
packet through the network (200) to the destination End Node to which it
is addressed. These fields can take several formats depending on the
routing mode specified
The Redundancy Check Fields (803) are used to check for errors in the
header itself. If an error is detected, the packet is discarded.
Routing Points
FIG. 3 shows a general block diagram of a typical Routing Point (300) such
as it can be found in the network Nodes (201 to 208) illustrated in FIG.
2. A Routing Point comprises a high speed packet Switch (302) onto which
packets arriving at the Routing Point are entered. Such packets are
received:
from other nodes over high speed transmission links (303) via Trunk
Adapters (304).
from users via application adapters called Ports (301).
Using information in the packet header, the adapters (304, 301) determine
which packets are to be routed by means of the Switch (302) towards a
local user network (307) or towards a transmission link (303) leaving the
Node. The adapters (301 and 304) include queuing circuits for queuing
packets prior to or subsequent to their launch on the Switch (302).
The Route Controller (305) calculates the optimum routes through the
network (200) so as to minimize the amount of network resources used to
complete a communication path and builds the header of the packets
generated in the Routing Point. The optimization criteria includes the
characteristics of the connection request, the capabilities and the
utilization of the Trunks in the path, the number of intermediate nodes .
. . . All the information necessary for the routing, about the nodes and
transmission links connected to the nodes, are contained in a Network
Topology Database (306). Under steady state conditions, every Routing
Point has the same view of the network. The network topology information
is updated when new links are activated or new nodes added to the network.
Such information is exchanged by means of control messages with all other
Route Controllers to provide the necessary up-to-date information needed
for route calculation (such database updates are carried on packets very
similar to the data packets between end users of the network). The fact
that the network topology is kept current in every node through continuous
updates allows dynamic network reconfigurations without disrupting end
users logical sessions
The incoming transmission links to the packet Routing Point may comprise
links from external devices in the local user networks (210) or links
(Trunks) from adjacent network nodes (209). In any case, the Routing Point
operates in the same manner to receive each data packet and forward it on
to another Routing Point as dictated by the information in the packet
header. The fast packet switching network operates to enable a
communication between any two end user applications without dedicating any
transmission or node facilities to that communication path except for the
duration of a single packet. In this way, the utilization of the
communication facilities of the packet network is optimized to carry
significantly more traffic than would be possible with dedicated
transmission links for each communication path.
Control Point Spanning Tree
Associated with networks are several network control functions: network
Spanning Tree maintenance, Topology Database, Directory, Path Selection,
Bandwidth Management and Reservation, and Congestion Control. Preferably,
every node has a set of the foregoing network control functions called its
Control Point (CP) that the node uses to facilitate the establishment of
connections between user applications.
The main purpose of the Control Point Spanning Tree is to ensure a
communication and distribution mechanism for all network control functions
in the nodes of a high speed network. It (logically) joins together the
Control Points (305) if the nodes are in a (physically) connected portion
of the network. As illustrated in FIG. 7 a tree is a pattern of
connections with no loop, the term "spanning" means that the tree spans
(connects) all of the nodes. Once formed, the Control Point Spanning Tree
is the principal system used to disseminate control information such as
Topology Database (306) updates. This mechanism is fundamental to minimize
delays due to intermediate node processing.
First, an intermediate node will get each control message exactly once on
the tree, and
second, the message can be forwarded along outgoing links of the tree
before the intermediate node has even looked at the packet contents.
A distributed algorithm creates and maintains the Control Point Spanning
Tree in presence of node and link failures and helps to minimize the
impact of the increased control flows that result when the network grows.
Routing Modes
The routing within the network presents two aspects:
1. Determining what the route for a given connection shall be.
2. Actually switching the packet within a switching node.
There are many methods of determining a route through a network. For very
high throughput, once the route selected, the critical item is that the
switching elements must be able to route an incoming packet in a very
short portion of time. Driven by the requirements to keep transit node
processing at a minimum, the transport services are designed to operate on
an end-to-end basis so there is no hop-by-hop error recovery or
retransmission envisioned for high speed, high performance (low error)
links. There is also no need for transit nodes to be aware of individual
transport connections.
Data packets are routed and queued in the transit nodes according to the
routing information contained in the header. Several routing modes can be
used in high speed networks (refer to an Introductory Survey (pages 116 to
129)--GG24-3816-01 ITSC Raleigh June 1993). However, in most of the case,
packets using different modes can share the same data transmission
facilities.
To classify the different transport type, we can consider on one side the
point-to-point transmissions on the other side the multi-pointss
transmissions. As illustrated by the following examples, each routing mode
has its particular indented use and includes advantages and disadvantages
that complement the other modes.:
Point-to-Point Transmission
Source Routing
The Source Routing is a particular implementation of the distributed
routing for connectionless networks. The The source node (or access node)
is responsible for calculating the route the packet must take through the
network.
Each packet includes in its routing field a list of the labels of all links
through which the packet will pass as it moves across the network. The
Source Routing requires no connection setup activity in intermediate nodes
and supports true datagram services.
Label Swapping
This routing mode is used in connection oriented networks. Each packet sent
on the link has a header which includes an arbitrary number identifying
which logical connection that this packet belongs to. Label Swapping
requires that connection tables be set up and maintained dynamically in
each node. Due to the low packet overhead, this technique is particularly
adapted to the transmission of very short packets (for example real-time
voice connections).
Multi-Points Transmission
Multicast allows one entity to communicate with multiple entities. An
efficient multicast mechanism provides packet delivery to a set of users
without having to broadcast to all users in the network or having to
"unicast" separate copies of packets to each user of a group.
Multicast Tree Routing
Multicast Tree Routing is supported by the ability of each node to
recognize that a particular label represents a pre-defined tree and to
forward the received packet along all the outbound links associated with
that tree. This is the basic routing mechanism that underlies both the
fundamental Control Point Spanning Tree and any individual trees that can
be established, pruned, and removed dynamically in a network. The Control
Point Spanning Tree greatly reduces the negative effect on performance
that network control flows could have in a high speed network. Tree
routing on other Multicast Trees can be fundamental to supporting, for
example, multi-attached LANs, or specific applications like video
conference.
Remote Access to a Multicast Tree
Remote Access to a Broadcast Tree is a straightforward combination of the
two routing modes: Source Routing and Multicast Tree Routing. The routing
field includes several Source Routing labels followed by a tree address
label. This allows a node that is not a member of a tree to route packets
to nodes that are tree members. This technique is described with more
details in European patent application 93480059.0 filed May 19th 1993
entitled Method and Apparatus for Routing Packets in Packet Transmission
Networks.
Multicast Mechanism
The Multicast Tree Routing provides a broadcast capability over a
preselected tree that can connect multiple nodes. Any member of a
multicast group can send a packet which will be forwarded to all other
member of the group. A Multicast Tree is simply identified, in the Routing
Point, by a reference in the Topology Database. Different trees can
coexist in the same network. One internal use of a Multicast Tree is to
join all the Control Points of a network (Control Point Spanning Tree) for
maintaining in each Topology Database a true image of the network
configuration. This broadcast mechanism can also be used to address subset
of network users (like a closer user group).
As illustrated in FIG. 8b, a Multicast Tree is identified by a tree address
(804) which is part of the routing field (802) of packets to be sent on
the tree. Unlike the Source Routing labels which are uniquely preassigned
to individual links within each node, the tree address is assigned to all
links that are to be part of a tree at the time that the tree is set up.
The tree address must be unique to one and only one tree across all nodes
over which the tree passes. When a packet addressed to a Multicast Tree
arrives at a node over a link, any links in that node that are configured
for that tree address will forward this packet. In this manner, copies of
the packet flow across the network, along each link configured as a branch
of the tree, with one and only one copy arriving at each node that is part
of the tree. A Hop Countdown Field (805) is included in the Multicast Tree
Routing Field (802) which is decremented at each retransmission of the
packet. When the hop countdown is equal to zero, no further retransmission
is permitted and an error condition is assumed. The routing field is
terminated by and End Of Field (EOF) flag (806).
Any node can be simultaneously be a member of a plurality of different
trees and hence the tree addresses assigned to overlapping multicast trees
must be unique. Nodes can be added or deleted from a Multicast Tree simply
by adding or remo | | |
