1. Node S1 uses Dijkstra’s algorithm to calculate its minimum weight path to T. In an intermediate step, Node S1 finds that 2. This causes node S1 to prematurely discard 3. When S2 calculates its path to T, Dijkstra’s algorithm correctly computes that
2. This causes node S1 to prematurely discard 3. When S2 calculates its path to T, Dijkstra’s algorithm correctly computes that
3. When S2 calculates its path to T, Dijkstra’s algorithm correctly computes that
In their quest for performance gains, many wireless network engineers are proposing a cross-layer design approach that some researchers fear may prove disruptive and short-lived.
In traditional, wired network design, protocols with single goals — such as routing — are designed and optimized as separate modules, or layers in a stack. Each layer communicates with two others, typically pictured as those above and below. By breaking the layered architecture, cross-layer designs can actively exploit the dependence between protocol layers and solve the unique problems posed by wireless links, according to Yaling Yang, assistant professor of ECE. Cross-layer designs also enable engineers to explore opportunistic communications, and leverage new modes of wireless communications, she says.
Cross-layer designs are growing more popular, but their increasing numbers are creating serious coexistence problems amongst themselves and with other networking protocols, according to Yang. Problems can reach beyond poor decisions and can affect the very stability and reach of a network.
“For example, a cross-layer design that involves multiple iterative algorithms at different network entities may never be able to converge in a highly dynamic wireless network environment,” she says. “Or, a cross-layer design that has a too-aggressive power control scheme in the physical layer may affect a routing system’s ability to find a path.”
Researchers have published warnings about cross-layer design and unresolved coexistence problems could cause the approach to be prematurely abandoned, according to Yang. “Many cross-layer designs may not be accepted, due to the fear of the unknown impact of these problems.”
Yang wants to resolve these uncertainties. She is leading a new effort to investigate cross-layer coexistence issues, supported by a five-year, $450,000 National Science Foundation (NSF) Faculty Early Career Development (CAREER) award. The CAREER grant is the NSF’s most prestigious award, given to junior faculty members who are expected to become academic leaders in their fields.
“To the best of our knowledge, ours is the first systematic, rigorous analysis of cross-layer coexistence issues,” she acknowledges.
The research effort comprises three parts: modeling and analyzing coexistence restrictions of various cross-layer designs; investigating restriction-compliant design techniques; and developing an open-source testbed.
Yang has identified four types of coexistence restrictions that her team will model and analyze, including restrictions on optimality, distributed design, reachability and stability. While in each case, cross-layer designs could break underlying assumptions and conditions, the problems present different perils to network operation. Optimal decision-making is the core of many networking systems, including routing and traffic she says. “While existing optimization algorithms in these networking systems guarantee optimal solutions, they may not work if cross-layer designs break their assumptions about the structures of their target problems.”
Distributed design is often adopted for scalability, she says. “In these designs, while nodes need to make individual decisions, these decisions are consistent so that the overall system still functions correctly.” However, if cross-layer designs break the conditions that ensure consistent decision-making, routing loops and other problems can arise.
A cross-layer design can impact a network’s reachability in many ways, she says. For example, a network can be disconnected due to excessive physical-layer power control or a wrong selection of modulation schemes. Cross-layer designs can affect stability as well, according to Yang. “Many designs include multiple iterative algorithms that reside on different layers. The interactions among these algorithms can greatly slow down the convergence speed of the entire network,” she says. “This may cause route flapping, buffer overflow, high control message overhead, and slow responses to changes.”
Not only do the restrictions create different challenges, but they also affect networks differently, Yang says. “Optimality restrictions are critical for networks with stringent resources. Distributed design and stability restrictions are important for large networks, and reachability restrictions are especially important for networks that require reliable communications,” she explains.
Once the restrictions and the challenges of cross-layer design are analyzed, Yang’s team plans to investigate practical techniques for building restriction-compliant cross-layer systems. They plan to develop techniques that ensure that cross-layer components satisfy given coexistence restrictions, and techniques that relax coexistence restrictions. “These techniques can serve as design guidelines for cross-layer designs and help network engineers create more adaptable and flexible networking systems,” she says.
The third tier of her research effort will be building an open-source testbed to validate results, measure the impact of violating different coexistence restrictions, and serve as a proof-of-concept for the team’s restriction-compliant design techniques. The testbed will initially be implemented as a hybrid wireless/wired network system that takes advantage of many of Virginia Tech’s homegrown software and designs.
All CAREER awards have a strong educational component and the testbed will play a major role in Yang’s educational efforts. She plans to develop a discovery-based networking course for upper-level undergraduates and first-year graduate students that incorporates competition-based projects.
At the graduate level, Yang plans to develop a course named Theories for Network System Analysis.
Yang’s goal is the same in both her research and educational efforts: to develop the understanding and tools needed for flexible, robust wireless networks that enable engineers to enhance the flexibility and robustness of current and future network systems.