Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
1999-07-26
2003-07-22
Kizou, Hassan (Department: 2662)
Multiplex communications
Diagnostic testing
Determination of communication parameters
C370S238000, C370S389000, C709S238000
Reexamination Certificate
active
06597663
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer networks and, more particularly, to the detection of routing transients in a computer network.
BACKGROUND OF THE INVENTION
Communication in a computer network involves the exchange of data between two or more entities interconnected by communication links and subnetworks. These entities are typically software programs executing on hardware computer platforms, such as end stations and intermediate stations. An example of an intermediate station may be a switch or router which interconnects the communication links and subnetworks to enable transmission of data between the end stations. The stations typically communicate by exchanging discrete packets or frames of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the stations interact with each other.
Most networks are typically organized as a series of hardware and software levels or “layers” within each station. These layers interact to format data for transfer between, e.g., a source station and a destination station communicating over the network. Specifically, predetermined services are performed on the data as it passes through each layer and the layers communicate with each other by means of the predefined protocols. This layered design permits each layer to offer selected services to other layers using a standardized interface that shields those layers from the details of actual implementation of the services.
Modern communications architectures are organized as such layered designs. The Internet communications architecture is an example of a layered architecture represented by four layers which are termed, in ascending interfacing order, the network interface, internetwork, transport and application layers. These layers are arranged to form a protocol stack in each communicating node of the network.
FIG. 1
illustrates a schematic block diagram of prior art Internet protocol stacks
125
and
175
used to transmit data between a source station
110
and a destination station
150
, respectively, of a network
100
. As can be seen, the stacks
125
and
175
are physically connected through a communications channel
180
at the network interface layers
120
and
160
. For ease of description, the protocol stack
125
will be described.
In general, the lower layers of the communications stack provide internetworking services and the upper layers, which are the users of these services, collectively provide common network application services. The transport layer
114
serves as the boundary between the network-specific elements and the application-specific elements. The transport layer's fundamental service is to move a user's data from its source to its destination over a communication path using the internetwork subsystem. The application layer
112
provides services suitable for the different types of applications using the network.
The lower network interface layer
120
of the Internet architecture addresses protocols that occupy physical and datalink sublayers of layer
120
. The physical layer
126
is concerned with the actual transmission of signals across the communication channel and the datalink layer is responsible for transmission of data from one station to another. The primary network layer protocol of the Internet architecture is the Internet protocol (IP) contained within the internetwork layer
116
. IP is primarily a connectionless network protocol that relies on transport protocols for end-to-end reliability. An example of such a reliable transport mechanism is the transmission control protocol (TCP) contained within the transport layer
114
.
Data transmission over the network
100
therefore consists of generating data in, e.g., sending process
104
executing on the source station
110
, passing that data to the application layer
112
and down through the layers of the protocol stack
125
, where the data are sequentially formatted as a frame for delivery onto the channel
180
as bits. Those frame bits are then transmitted over an established connection of channel
180
to the protocol stack
175
of the destination station
150
where they are passed up that stack to a receiving process
174
. Data flow is schematically illustrated by solid arrows.
Although actual data transmission occurs vertically through the stacks, each layer is programmed as though such transmission were horizontal. That is, each layer in the source station
110
is programmed to transmit data to its corresponding layer in the destination station
150
, as schematically shown by dotted arrows. To achieve this effect, each layer of the protocol stack
125
in the source station
110
typically adds information (in the form of a header field) to the data frame generated by the sending process as the frame descends the stack. At the destination station
150
, the various encapsulated headers are stripped off one-by-one as the frame propagates up the layers of the stack
175
until it arrives at the receiving process.
As noted, each layer of the protocol stack offers selected services to other layers; one such service is a connectionless service. This network service is generally implemented by a network layer protocol, an aspect of which involves the routing of packets from the source station to the destination station. In particular, this aspect of the internetwork layer concerns the algorithms and protocols used by routers when cooperating to calculate paths through a network topology. A routing algorithm is that portion of the network layer software responsible for determining an output communication link (i.e., an egress) over which an incoming packet should be transmitted. An example of a conventional routing algorithm is the Dijkstra algorithm and an example of a conventional network layer routing protocol is a link state routing protocol.
According to this latter protocol, each router constructs a link state packet (LSP) comprising information, such as a list of neighboring nodes adjacent to the router, sufficient to generate a complete map of the topology of the network. As defined herein, the term “neighbor” denotes a neighboring router. The LSP is then forwarded to all other routers of the network over, e.g., a plurality of interconnected local area networks (LANs). Each of these other routers stores only the most recently received LSP from the forwarding router in its LSP database. Armed with updated maps, the routers may compute shortest paths to destination stations using a conventional routing algorithm; the computed paths are then stored in forwarding tables of the routers. Examples of link state routing protocols are the intermediate system to intermediate system (IS-IS) protocol defined by the International Standards Organization (ISO), the open shortest path first (OSPF) protocol defined by the Internet protocol (IP) community and the NetWare link services protocol (NLSP) defined by Novell, Inc.
Use of link state routing in conjunction with hop-by-hop forwarding may result in formation of transient (i.e., temporary) forwarding loops. Routing transients typically arise when there is a change in the topology of a network. For example in response to a network topology change, each router updates its routing information and re-calculates shortest paths between the router and a destination station. This newly updated information is then transmitted to the other routers in the network. While the other routers propagate the updated information throughout the network and re-calculate their forwarding tables, there is a possibility that routers possessing inconsistent routing information may forward packets back to a previous sender of the packets, thus creating forwarding loops. The present invention is directed to an approach that enables detection of the occurrence of forwarding loops.
Conventional link state routing protocols, such as OSPF and IS-IS, generally do not provide mechanisms for suppressing such forwarding loops during routing transients. In order to limit the amount
Cesari and McKenna LLP
Cisco Technology Inc.
Pezzlo John
LandOfFree
Technique for handling forwarding transients with link state... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Technique for handling forwarding transients with link state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for handling forwarding transients with link state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3087757