Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-12-14
2002-05-14
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S360000
Reexamination Certificate
active
06389017
ABSTRACT:
BACKGROUND OF THE INVENTION
Multi-link routing algorithms are well known in the field of wide area networks (WANs) and are used to optimize performance.
A key distinction among multi-link routing algorithms is the amount of assumed knowledge about the state of the network. It is clear that making use of more information leads to better algorithms. Central concerns in devising a new scheduling scheme include: (i) deciding what information to use, (ii) determining the cost of collecting such information, and (iii) deciding when additional information will lead to improved performance sufficient to justify its inclusion.
In wide area networks, Shortest Path First (SPF) was proposed as a way to select among alternate paths. SPF performs well when the traffic is light and changing slowly, however under heavy and dynamic traffic the routing algorithm suffers from severe congestion and results in degradation of the network performance. Many of the problems are associated with the distance estimation procedure of the algorithm. SPF-EE4 (Shortest Path First with Emergency Exits) attempts to eliminate the problems associated with the SPF (Shortest Path First) algorithm by using alternate path only as emergency exit.
Multiple links between routers in a system area network may be configured as an adaptive sets or “fat pipes”. Multi-port routers are cascaded to create arbitrary network topologies. The presence of multiple ports allows for a wide variety of substantial connectivity. However, providing sustained network throughput can present some difficulties. Failure to consider the fan-in to the router-router links within the network can produce system topologies with substantial bottlenecks.
Configuring multiple links between routers to act as “fat pipes” allows the router hardware to dynamically select an output port based on recent message traffic. Multi-link routing algorithms used in switches arc similar to algorithms used in WANs, but there are significant differences. Most importantly, it is critical for high-speed switching to take arriving traffic and quickly send it out on the appropriate output link. This places major constraints on the computational complexity of the scheduling task, and thus excludes many of the multipath routing solutions based on expected response time.
SUMMARY OF THE INVENTION
According to one aspect of the invention, a Destination Based Scheduling (DBS) algorithm is utilized to schedule incoming packets between multiple links of a fat pipe. The DBS algorithm binds packets targeting the same destination to the same physical link in a multiple alternate link switch. Committing packets to a particular link is achieved by adding router caches. A destination register or a cache is associated with each of the alternate links of the network switch. Each of the caches holds the destination of the last packet that used the link. Upon arrival, a packet checks the content of all caches. If it hits, then it uses the corresponding link; otherwise, the packet is scheduled according to a round-robin policy or other default policy.
DBS has the following advantages:
It has higher throughput and lower message latency while requiring little hardware support;
It reduces the variance of message response time of competing requests; and
It significantly reduces the frequency to access the router table.
Other features and advantages of the invention will be apparent in view of the following detailed description and appended drawings.
REFERENCES:
patent: 5740346 (1998-04-01), Wicki et al.
patent: 6188686 (2001-02-01), Smith
Harzallah Karim
Patel Naresh
Compaq Computer Corporation
Olms Douglas
Oppenheimer Wolff & Donnelly LLP
Sam Phirin
Sherry Leah
LandOfFree
Resource scheduling algorithm in packet switched networks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Resource scheduling algorithm in packet switched networks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource scheduling algorithm in packet switched networks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2866018