Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-09-30
2001-02-06
Olms, Douglas W. (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S397000
Reexamination Certificate
active
06185210
ABSTRACT:
BACKGROUND
A computer network typically comprises a collection of interconnection nodes such as computer systems and switches. These may in turn be connected through an irregular configuration of transmission lines, i.e., links. The switches are specialized computers used to connect two or more links. Data is exchanged among nodes of such an arbitrary topology network by passing packets and messages from switch to switch over the links. Specifically, when a packet or message arrives on an incoming link, the switch decides onto which of the outgoing links that packet will be forwarded.
In a connection-oriented network, a virtual circuit (VC) is commonly established when exchanging packets between nodes of the network. The virtual circuit is a temporary logical path connection that requires a set up procedure to open the virtual circuit prior to transferring the data packets, and a release procedure to close the circuit once the data transfer is complete. This obviates the need for effecting routing decisions for each data packet that is transferred between the nodes once the circuit is opened. For point-to-point communication, the set up procedure creates a virtual circuit by allocating certain switches and links in the network to establish the “best” route, according to conventional route configuration techniques, between a source node and a destination node. However, opening and closing virtual circuits is a time and resource consuming task. Further, there are limits as to how many virtual circuits can be opened and supported simultaneously.
Virtual circuits can also perform point-to-multipoint connections, where one source node connects to several destination nodes. This allows several techniques, including multicasting, which involves transmitting a single multicast packet from a source node and having it received by a group of destination nodes.
One use for multicasting is Distributed Interactive Simulation (DIS) applications. An example of DIS is military training, although DIS technology can be used for training non-military personnel and to construct distributed virtual-reality games. A simulation involving a multitude of actors or objects is set up and maintained in near-real time. Typical objects are tanks, trucks, planes, helicopters, ships, and dismounted infantry (soldiers). In a simulation, a computer is responsible for modeling some number (typically between 1 and 100) entities. Each machine sends packets containing the current state of locally modeled entities, and receives packets containing the current state of remote entities within the region of interest of local entities.
DIS can benefit from IP multicasting in that simulation packets are delivered to only those simulators that need them. Typically, each entity transmits to one multicast group and joins a number of multicast groups. One can imagine a grid in latitude and longitude and sending to a group corresponding to one's location and joining all nearby groups.
One technique for providing multicast is called bilevel multicast. The central idea of bilevel multicast is the construction of a private virtual multicast network using an existing multipoint delivery service. All bilevel multicast routers (BMRS) are peers connected to the multipoint delivery service. More features of bilevel multicast will be discussed below.
There is a need to use more and more multicast groups for DIS and other applications to obtain finer-grained control over data delivery and deliver less unneeded data. There are also constraints which prevent the use of as many multicast groups as are desired. Routers cannot support a very large number of groups. Multicast routing protocols that can handle a very large number of concurrent multicast groups have not yet been developed. Some problems that must be addressed include routing traffic caused by transient joining of groups, the requirement of sufficient router memory to hold multicast routing tables.
Another constraint is the inability of hosts to support a large number of subscribed multicast groups efficiently. There are two common problems: a shortage of hardware filtering slots, so that the network interface delivers all multicast packets to the operating system; and the lack of efficiency of networking code to deal with one hundred or more subscribed groups. Accordingly, efficient delivery of packets to the proper destinations with a minimum of oversent data is very important. Oversent data is data sent to more destinations than it is needed. Further, the efficient use of bandwidth to deliver as many packets as possible, while observing packet requirements including priority levels. Obtaining a proper balance of high packet throughput while guaranteeing high-priority packets are not delayed (often referred to as Quality of Service (QoS)) is extremely problematic.
Accordingly, what is needed is a system and method for optimizing a network's virtual circuits (VCs), including minimizing oversent data, and utilizing VC bandwidth for optimum delivery while still maintaining quality of service. Further, the optimizations should perform well with the transient nature of nodes joining and leaving multicast groups, and VCs opening and closing in response to the multicast membership changes.
SUMMARY
The present invention is directed towards a system and method for optimizing flow control through a node in a network system, where messages forwarded to the node have one of at least two priorities, a normal priority and a high priority. It includes a token counter associated with a flow into the node, the token counter holding a numeric value representing a number of tokens. The token counter is incremented at a predetermined rate of tokens per second, and has a maximum value.
The token counter is decremented by a number of tokens as required for passing an arriving message in that flow through the node. The number of tokens required for passing the arriving message is determined by attributes of the arriving message, for example one token for each byte of message size.
A normal priority threshold value is associated with the token counter. If a message with a high priority arrives at the node, the message is marked non-conforming if the token counter is below the number of tokens required for passing said message. If a message with a normal priority arrives at node, the message is marked non-conforming if the token counter is below the number of tokens required for passing said message plus the normal priority threshold value.
Messages marked non-conforming in the first stage may be dropped, or passed on the more policing processing, or sent out of the node with appropriate standard tagging for network messages over a flow.
The system and method also includes a second stage, which includes an aggregate token counter, for holding a numeric value representing a number of tokens, the aggregate token counter is incremented at a predetermined rate of tokens per second, and is decremented by a number of tokens as required for passing the arriving message through the node, the number of tokens required for passing said arriving message is determined by attributes of the arriving message. This aggregate token counter also includes a maximum limit value.
An aggregate normal priority threshold value is associated with the aggregate token counter. If a message with a high priority was not marked non-conforming in the first stage, the message is marked non-conforming in the second stage if the aggregate token counter is below the number of tokens required for passing the message. If a message with a low priority was not marked non-conforming in the first stage, the message is marked non-conforming in the second stage if the aggregate token counter is below the number of tokens required for passing said message plus the normal priority threshold value.
Messages marked non-conforming in said second stage may be dropped or sent out appropriately tagged for the network flow.
The system and method also includes an aggregate headroom threshold value associated with the aggregate token counter,
BBN Corporation
Olms Douglas W.
Pizarro Ricardo M.
Suchyta Leonard Charles
Weixel James K.
LandOfFree
Virtual circuit management for multi-point delivery in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Virtual circuit management for multi-point delivery in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual circuit management for multi-point delivery in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2559934