Abstract Network Model and
J-Sim
January 29, 2003
In this document, we present a
generalized packet switched network model. This model is composed
of basic, abstract components extracted from the Internet, and
hence the name Internetworking Simulation Platform (INET). Although
the model is derived from the Internet, it is general enough to
serve as a base model for other network architectures, such as
the IETF Integrated/Differentiated Services architecture, the
mobile wireless network architecture, and the WDM-based optical
network architecture. We first present the core service
layer, and discuss how we decompose the core service layer
based on the ``arbitrary and complex protocol graphs with
simple protocols'' concept for better module reuse. Then, we describe the
implementation of INET in J-Sim, an implementation of the autonomous
component architecture in Java.
Table of Contents
We design the core service
layer in compliance with the thin waist model of the protocol
hour-glass, and include in the core service layer the most
fundamental core services that should be provided to clients ---
protocol modules in the protocol module layer. Services provided by the core service layer
include
- the data forwarding/delivery service,
- the identity service,
- the routing service;
- the interface/neighbor service; and
- the packet filter configuration service.
These services are
defined in terms of contracts. A protocol module that uses the
core services may own a port that is bound to the specific
service contract. The protocol module is actually connected to the
core service layer by wiring its port to the corresponding port
of the core service layer only at system integration time.
As shown in Figure 1, a
typical INET node is composed of the core service layer and one
or more application and transport layer protocols. Note that
applications and transport protocols are part of an end host but
not part of routers inside the network.
Figure 1: The internal
structure of an INET node.
The data sending/delivery service
consists of two contracts, one for each direction of data flows (upward
or downward).
- The downward contract:
defines the packet sending service provided by the core
service layer to upper layer protocols. To send a packet,
an upper layer protocol must provide the destination
address (in terms of the address of the destination node
and the upper layer protocol identification), TTL (the
maximum number of hops before the packet is discarded),
the router alert flag (that indicates whether or not the
packet should be intercepted by intermediate routers),
and the type of service (ToS) the packet will receive. In
the current implementation, INET only uses the first bit
of the ToS field to distinguish data packets (from
applications) from control packets (from routing or
signaling protocols). It may be extended to provide more
options to upper layer protocols.
The core service layer provides three data sending
options: default forwarding, explicit multicast, and exclusive
broadcast. For the default forwarding option, the core
service layer looks up the routing table based on the
destination address specified to determine on which
outgoing interface(s) the packet should be sent.
For the explicit multicast option, the core service layer
sends the packet on the interfaces specified by the
upper layer protocol. For the exclusive broadcast
option, the core service layer sends the packet on all
interfaces except the ones specified by the upper layer
protocol.
- The upward contract:
defines the service to deliver a packet to an upper layer
protocol. Along with the packet, the core service layer provides the sender address, the incoming interface on which the
packet arrives, and the type of service (ToS).
In addition to the packet forwarding and delivery services, the core service layer also exports a
packet arrival event (see Exporting Information at Run
Time) whenever a packet arrives at an upper or
lower data port.
The core service layer maintains a
list of identities, or addresses, of the node known by other
nodes in the network. In INET, a unicast address is an identity
owned by at most one node in the network, while a multicast
address is an identity by which more than one node may be
identified in the network. An upper layer protocol may look up
and/or configure the identities of the node through the following
two service contracts:
- Identity Lookup:
This contract defines the service which an upper layer
protocol uses to look up the identities of the node.
Three types of lookup service are available: default identity lookup,
identity inquiry, and all identities inquiry. One identity is set to be the default identity
for each node. In the default identity lookup service,
the core service layer returns the default identity of the node. In
the identity inquiry service, the initiator specifies an
identity for query and the core service layer returns a Boolean value of
true if the identity is indeed
owned by the node, or false otherwise. In the all identities inquiry service, the core service layer returns
a list of identities of the node.
- Identify Configuration:
This contract defines the service for configuring the
identities of a node, e.g., adding/removing an identity.
In addition, each identity can be associated with a timer.
When the timer expires, the associated identity is
removed. The service also allows one to adjust or query
the expiration time of an
identity.
In addition to the lookup and
configuration services, the core service layer exports an event (see Exporting Information at
Run Time) whenever the set of identities changes.
The changes include addition or removal of an identity, or
modification of the timer associated with an identity.
The core service layer at each
node maintains a routing table and, for each packet to be
forwarded, looks up appropriate interfaces in the table, based on
the source address, the destination address, and the incoming interface on which the packet arrived. An
upper layer protocol may look up and/or configure the routing
table through the following routing service contracts:
- Route Lookup:
In this contract, the initiator specifies the source
address, the destination address,
and the incoming interface on which the packet arrived.
The core service layer then responds with the interface(s)
on which the packet should be sent.
- Route Configuration:
This contract defines services for configuring the
routing table. In addition to adding and removing a
routing table entry, one can also retrieve or modify an entry. Moreover, each entry is associated
with a timer, and the entry is removed when its timer
expires. One may adjust these timers through one of the
services provided in this category.
- Route Request:
The core service layer also defines a Route Request
contract when the route does not exist for a packet.
This contract has the same format as the Route Lookup
service defined above, but is initiated by the core
service layer. This allows the node to set up
routing table entries on demand, or to set up temporary
entries to monitor the routing process during certain
transitional periods.
In addition, the core service
layer exports an event (see Exporting Information at Run
Time) whenever the routing table changes. The
change includes addition, removal or modification, of an entry.
The core service layer maintains a database to keep the information of all
the interfaces of the node. The information for an interface includes the local
address , the addresses of the neighbors that can be reached on the interface,
the size of the outgoing buffer, the bandwidth, the maximum transmission unit (MTU)
and so on. The core service layer provides the services for upper layer
protocols to retrieve the information, and to be notified of neighboring events,
such as the neighbor-up event (the event that a new neighbor is discovered) and
the neighbor-down event (the event that an existing neighbor is gone).
The neighboring information may be manually, statically configured into the core service layer.
In this case, the core service layer exports all the neighbor-up events at node
boot-up time. Alternatively, the core service layer may be instrumented to build
the neighbor information and export the neighbor events dynamically (by running
some generic Hello protocol).
Packet filters are conceptually the extensible part of the core service
layer. Each interface of a node may contain a bank of packet filters.
When the core service layer forwards a packet on an outgoing interface, the
packet may go through a subset of packet filters in the bank before being placed
in the outgoing buffer of the interface. When a packet arrives on an interface
of a node, it may also traverse a (possibly different) subset of packet filters
in the bank before being handed to the dispatching function of the core service layer.
While different implementations of core service layer may have different sets of
packet filters installed, all implementations should provide this configuration
service for upper layer protocols to configure the installed packet filters.
In compliance with the four
categories of services provided by the core service layer, we
decompose the core service layer into five components (Figure 2): PacketDispatcher, Identify,
RoutingTable, Hello, and PacketFilterSwitch (along
with one or more extensible packet filter banks). The decomposition is grounded on the philosophy
of the ``complex protocol graph
and simple protocols''1,2
for better component reuse.
1 S. W. O'Malley and L. L. Peterson, "A
dynamic network architecture," ACM Trans. on Computer
Systems, Vol. 10, No. 2, pages 110-143, May 1992.
2 R. Morris, E. Kohler, J. Jannotti, and M.
F. Kaashoek, "The Click modular router," Proc. of 17th
ACM Symposium on Operating Systems Principles (SOSP'99),
December 1999.
Figure 2: The decomposition of the core service layer.
In what follows, we discuss
each of the components:
- The Identity
component keeps the identities of the node and provides
the identity services to both the upper layer protocols
and other components in the core service layer.
- The RoutingTable
component keeps the routing table entries and provides
the routing services to the upper layer protocols,
especially the routing protocols, as well as other
components in the core service layer.
- The PacketDispatcher
component provides the data sending/delivery services to
the upper layer protocols. Specifically, it forwards
incoming packets to an appropriate set of output ports
connected either to an upper layer protocol or a lower
layer component in one of the packet filter banks. The PacketDispatcher
component invokes the Identity Lookup and Route
Lookup services as an initiator, by binding two ports
to those contracts respectively. When a packet arrives, PacketDispatcher
first checks if the TTL field in the packet header has
been reduced to zero. If so, the packet is discarded.
Otherwise, PacketDispatcher proceeds to determine
where to deliver the packet (an upper layer protocol
module and/or one or more outgoing interfaces). If
the packet should be forwarded, PacketDispatcher
uses the Route Lookup service to obtain the
outgoing interface(s) on which the packet should be sent.
- The Hello component keeps the interface and neighbor information of the
node and provides the interface/neighbor services to both the upper layer
protocols and other components in the core service layer. It may be
configured statically or running a generic hello protocol to discover and
maintain neighboring information.
- The PacketFilterSwitch
component acts between an upper layer protocol (usually a
signaling protocol) and the components in the packet
filter banks. As the name suggests, it ``switches'' configuration requests
to appropriate packet filter components.
A packet filter bank is a set of packet filters connected
in serial and constitutes an ``interface'' of the node. (An
end host is a node that is equipped with exactly one
packet filter bank, while a router or a multi-homed host
is a node with two or more packet filter banks.) A packet
filter may perform certain operations on packets, may
drop packets according to pre-specified policies, or may
pass packets to the lower layer filters. The lowest
packet filter in a packet filter bank is a network
interface that models the physical device and injects
packets into the network. If a network interface
processes packets at a slower pace than the other
components in a node, a buffer component is located
right above the network interface.
Packet filters can be accessed, and configured, by an upper-layer signaling protocol
through
the packet filter configuration service. The PacketFilterSwitch component is designed to support more
efficient access and configuration. Each packet filter is
indexed by a packet filter bank ID and a packet filter ID
within the bank. A signaling protocol then sends a
request with the indices to indicate the packet filter to which the
request should be dispatched.
Note that the way in which the packet filter bank is
arranged does not necessarily mirror the way in which the
Internet protocol stack is layered. That is, there
is no clear boundary between the network layer, the data
link layer and the physical layer in the packet filter
bank. This allows creation of simulation scenarios
at desirable levels of abstraction. At one extreme, one
may model the packet transmission delay in a packet
filter bank so as not model the actual queuing behavior and all the physical
layer characteristics. At the other extreme, one may
model and implement MAC protocols, error detection and
recovery strategies, and address resolution protocols in great details.
We lay out the generalized packet
switched network model on top of ACA.
This is done by defining generic network components and their
contracts, with the intent to capture their fundamental features
and yet allow flexibility to accommodate other technology
advances. By virtue of the layered, component-based
architecture with well-defined contracts, it is easy to extend
the abstract network model to accommodate other network
architectures, e.g., wireless LANs, optical networks with WDM
technology, networks with satellite communication links, and/or
ad hoc networks consisting primarily of mobile sensors.
Specifically, to model a network
architecture, one need only to sub-class an appropriate generic
component, and re-defines its attributes and/or methods for
manipulating these attributes. For example, one needs only
to modify the link and network interface card (NIC) components to
incorporate the error characteristics of wireless links and the
mobility characteristics of mobile subscribers in order to model
a wireless mobile network. One possible module stack that
can be derived from the abstract network model is depicted
in Figure 3.
Figure 3: A possible module
stack using the abstract network model.
Based on the INET abstract network model, we have implemented a network simulation
environment on top of J-Sim/ACA. Building INET in such
a component-based software architecture is a natural task. The concepts of
service contracts and component decomposition in INET directly follow those in
the software architecture.
We implement every component in INET as a class, and
organized classes into layers. Figure 4 depicts the five-layer
class organization in J-Sim.
Figure 4: The class pyramid in J-Sim.
- The ACA layer contains the
component and port classes in the autonomous component
architecture (ACA).
- The NET layer contains
network simulation primitives and tools such as Packet, Module, Address,
traffic
models (such as CBR and token buckets) and tools such as traffic monitor
and NAM trace generator.
- The INET layer contains the
INET components. Specifically, it defines
- the basic components (Network, Node, and Link)
for construction of hierarchical networks,
- the Protocol component that serves as the base
class for implementing protocol modules, and
- contract classes, one for each contract defined
in INET (see Core Service Layer), and components that constitute
the core service layer.
- Specific network
architectures are further derived from the INET layer. We
have implemented three different network
architectures: the current Internet (best effort)
architecture, the integrated services architecture,
and the differentiated services architecture.
- Protocol modules and/or
algorithms specific to a network architecture are
implemented on top of that architecture layer. For
example, the unicast routing protocols specific to the
best effort services architecture are RIP (distance
vector) and OSPF (link state), and are implemented on top
of the architecture layer.
The following table gives the algorithms/models
currently supported or under development in J-Sim.
| Network
Architecture |
|
Application |
Socket Layer |
Transport |
Routing |
Traffic Model |
Tagger Marker |
Buffer
Management |
NI Scheduling |
| Best Effect
Services |
|
FTP, FSP
WWW |
Java Socket |
TCP-Reno
TCP-Tahoe
TCP-Vegas
TCP Sack
UDP |
RIP (DV)
OSPFv2
Multicast shortest path tree
DVMRP
CBT |
|
|
Drop-Tail |
FIFO |
| Differentiated
Services |
|
|
|
|
|
|
Token Bucket
TSW
ETSW |
FIFO
RED
FRED
SRED
BRED |
Priority Queue, Weighted Round-robin,
3ColorQueue |
| Integrated
Services |
|
|
|
RSVP |
Unicast QoS routing
QoS-enhanced OSPFv2
QoS-enhanced CBT |
Periodic message (CBR)
Peak rate model
Leaky bucket model
Token bucket model
IETF/Intserv Flowspec
(r,t)-smooth model
(C,D)-smooth model |
|
|
RM
EDF
Stop-and-go
DCTS
VirtualClock
LFVC
SCFQ
PGPS
STQ
WF2Q |
| FTP: file
transfer protocol |
FSP: file
service protocol |
| TCP:
transmission control protocol |
RIP:
routing information protocol |
| OSPF: open
shortest path first |
DVMRP:
distance vector multicast routing protocol |
| CBT: core
based tree protocol |
FIFO:
first in first out |
| TSW: time
sliding window |
ETSW:
enhanced time sliding window |
| RED:
random early drop |
FRED: fair
random early drop |
| SRED:
stable random early drop |
BRED:
balanced random early drop |
| RSVP:
Resource reservation protocol |
CBR:
constant bit rate |
| RM: rate
monotonic |
EDF:
earliest deadline first |
| DCTS:
distance constrained task system |
LFVC: leap
forward virtual clock |
| SCFQ: self-clocked
fair queueing |
PGPS:
packet-by-packet generalized processing sharing |
| STQ:
start time fair queueing |
WF2Q:
worst-case fair weighted fair queueing |
By virtue of the autonomous
component architecture, INET supports hierarchical networks of
arbitrary depth. Specifically, an internetwork consists of
networks, nodes and (backbone) links. A network, in turn,
contains nodes, links and networks of smaller sizes. The
internetworking system itself is a network entity, and the
ancestor of all entities contained in it.
To address nodes at different
levels of the network hierarchy, INET uses the address allocation
mechanism, called Classless Inter- Domain Routing (CIDR, or supernetting)3,4,
to allocate numerical addresses to networks and nodes in the
system. Succinctly speaking, CIDR uses variable length subnet masks
to assign addresses in unbalanced hierarchical
networks, where by an unbalanced network, we mean a network that
contains at least two networks with unequal number of nodes. Due to the use of variable
length subnet masks, we can achieve more efficient address assignment, meaning
that the number of un-used addresses can be reduced, as compared to the traditional
class-based address assignment.
3 Y. Rekhter and T. Li, "An
architecture for IP address allocation with CIDR," RFC 1518,
September 1993.
4 V. Fuller, T. Li, J. Y. Yu and K. Varadhan,
"Classless inter-domain routing (CIDR): an address
assignment and aggregation strategy," RFC 1519, September
1993.
In CIDR, a network is represented
by an address with a network mask in the format of <address>/<mask>,
where a network mask is an address that starts, in the binary form, with contiguous 1's
and followed by 0's thereafter. For
example, the network address 10xy/1100 with x, y in
[0,1] is equivalent to 1000/1100, and contains only the nodes
with addresses in the format of 10xy with x, y in
[0,1]. A network address can also be represented in the format of <address>/<number
of 1's>. For example, the above network address can also
be represented as 1000/2.
Example: Figure 5 (a)
depicts a network system of 3 levels and totally 10 nodes. The
system is unbalanced because net0 and net1 contain 6 and 3 nodes,
respectively. If a straightforward address allocation method is
used to allocate sufficient bits to each level of the network
hierarchy, start from the first level, totally 6 bits are needed.
This is done by (i) assigning 2 bits to the three immediate
children node0, net0, and net1 of the system; (ii) going down one
level and assigning 2 bits to the three immediate children of net0
and net1; and (iii) going down to one level further and assigning
2 bits to the two immediate children of net2 and the three
immediate children of net3. A more efficient CIDR-based address assignment
assigns a unique 4-bit address to each network and
node for the same system. One such solution is given in Figure 5 (b).
| Figure 5: An example network under CIDR-based address assignment. |
 |
 |
| (a) The example hierarchical network. |
(b) One possible CIDR address assignment. |
|
Note that in the above example
addresses are associated with node instead of with interfaces of
a node. As a matter of fact, INET supports both per-node
addressing and per-interface addressing. The way in which INET
supports per-interface addressing is to allow assignment of
multiple addresses to a node (see Node
Identity Service).
~ END ~