CURRENT_MEETING_REPORT_
Reported by Isidro Castineyra/Bolt Beranek and Newman
Minutes of the New Internet Routing and Addressing Architecture
Working Group (NIMROD)
Preface
The Nimrod Working Group met on Wednesday, 19 July, and on Thursday,
20 July. The agenda for the meeting was:
o Wednesday
- Agenda bashing/Announcements
- Overview of the Implementation Model (Isidro Castineyra)
- Neighbor Discovery Protocol (Ram Ramanathan)
- Agent Discovery Protocol (Ram Ramanathan)
o Thursday
- Path Set-up Protocol (Isidro Castineyra)
- Reliable Transaction Protocol (Ram Ramanathan)
- Query Response and Update Protocols (Ram Ramanathan)
- Open Issues and Work Plan
The discussion of the agent discovery protocol was eliminated from the
agenda. A demonstration of a configuration tool written by Mike Patton
was added at the end of the first session.
Overview of the Implementation Model
The following are the main points from that presentation:
o Network Components
- A Nimrod network is composed of Nimrod boxes: Nimrod routers
and Nimrod hosts.
- Nimrod forwarding agents live in Nimrod routers.
- Other agents, e.g., route agents, node representatives,
endpoint representatives, can live in either Nimrod routers or
in Nimrod hosts.
- A given Nimrod box can be the home of agents for multiple
nodes, e.g., for a node and its component nodes.
o Interfaces
- Nimrod routers and hosts have distinct interfaces to the
external world.
- Interfaces are not assigned locators.
- Interfaces are numbered for management purposes.
o Interconnectivity of Nimrod Boxes
- Two different boxes are directly connected if there are
interfaces in each one of them that can exchange data without
the aid of any other Nimrod Box and such that data exchange is
actually enabled.
- The connectivity between two interfaces can be realized in many
ways, for example: PPP, Ethernet, IP, IPv6, ATM, etc. The
underlying technology is not important.
- We say that a set of Nimrod boxes is connected if between any
two of them there exists a path consisting of other Nimrod
boxes in that set, such that consecutive boxes in the path are
directly connected.
o Agents
- Endpoint Representatives
- Node Representatives
- Forwarding Agents
- Route Agents
o Connectivity
- Any one agent is associated with a one and only one node. That
is, an agent for a component node is not associated with the
parent node.
- This is emphasized by the phrase ``associated in the narrow
sense.''
- An agent is associated ``in the wide sense'' with a node if it
is associated with the node or one of its component nodes
(recursively).
- Two agents are directly connected if either they
1. reside in the same box, or
2. reside in boxes that are directly connected.
- A set of agents is connected if the set of boxes they belong to
is connected.
o Boundaries
- A boundary between two nodes exists between any two directly
connected forwarding agents that belong to different nodes.
- Therefore, a boundary between two nodes can occur both inside a
Nimrod box and between two boxes.
- Existence of a boundary between two nodes does not necessarily
imply the existence at that point of an adjacency between those
two nodes.
o Tight Connectivity Restrictions
- Forwarding Agents: the set of forwarding agents associated
with a node (in the narrow sense) must be connected, i.e., the
node must have a backbone of forwarding agents.
- Node Representatives: each node representative must be
directly connected to a forwarding agent of the node it
represents.
- Endpoint Representatives: To communicate with agents to which
it is not directly connected, an endpoint representative must
be connected to a forwarding agent.
- For a node that has a parent, at least one of its forwarding
agents (narrow sense) must be connected to a forwarding agent
in the parent.
o Tight Flooding Rule
``Agent discovery messages are flooded only within the boundaries
of a node (strict sense).''
o Loose Connectivity Restrictions
- Forwarding Agents: The set of all forwarding agents associated
in the wide sense with a given node must be connected.
- Node Representatives: each node representative must be
connected to a forwarding agent associated in the wide sense
with the node it represents.
- Endpoint Representatives: To communicate with agents to which
it is not directly connected, an endpoint representative must
be connected to a forwarding agent of the same node.
- The set of forwarding agents of sibling nodes must be connected
to one agent of the parent node.
o Protocols
- Neighbor Discovery: implemented by all agents.
- Agent Discovery: implemented by all agents.
- Reliable Transaction Protocol: implemented by all agents.
- Query/Response: implemented by all agents.
- Update: implemented by all agents.
- Path Set-Up: requests sent by endpoint representatives (at top
level) and/or forwarding agents (at lower level paths) by
forwarding agents.
There was a discussion on the benefits of the ``tight'' against the
``loose'' model. The general consensus was that the loose model was
preferable.
Agent Discovery Protocol
Ram Ramanathan presented the agent discovery protocol. The slides of
this presentation will be posted to the mailing list.
Path Set Up Protocol
Isidro Castineyra presented the path set up protocol. Highlights of
that presentation follow:
o Agents and Path Management
- Path management is the responsibility of forwarding agents and
endpoint representatives.
- Forwarding agents establish state in routers, endpoint
representatives in hosts and in themselves.
- Forwarding agents and endpoint representatives are responsible
for forwarding Nimrod messages according to this state
information and according to forwarding directives carried
along in the messages.
- Each forwarding agent and endpoint representative maintains
forwarding information for those paths that originate,
terminate, or, in the case of forwarding agents, pass thorough
it.
- Forwarding agents try to build new forwarding paths by piecing
together existing paths.
o Paths
- Paths may be set up from source to destination or from
destination to source.
- Each path has an initiator and a target.
- Multiple traffic sessions may use the same path.
- A single traffic session may use multiple paths.
- A path may connect one or more source endpoints to one or more
destination endpoints. In the initial implementation of
Nimrod, each multicast path is either a source tree or a sink
tree.
o Path Labels
- Paths are identified by path labels, which are unique along the
path but not necessarily globally unique throughout the
internetwork.
- The labels for direction of a path are distinguished by a bit
that indicates whether the direction is toward the target or
toward the initiator.
- Labels are assigned randomly. There exists a label collision
resolution procedure.
o Multilevel Paths
- A single path comprises multiple lower level contiguous paths ,
one for each of the n segments of the route on which the
original path is based.
- Each component path itself comprises multiple contiguous paths
corresponding to each of its segments, and so on recursively.
- For each pij composing pi-1 k, the initiator and target of pij
maintain linkages from the path pi-1k to pi j , which helps to
guide forwarding along the successive segments of pi-1k.
- A flow mode data message, at any point along the end-to-end
path, contains one path label for each level, but only one path
label is used for forwarding at a given time. Path labels are
stacked in the message and manipulated by the forwarding agents
handling the message.
o Protocol Messages
- There are four types of message: setup, accept, teardown, and
management.
- These messages travel along the path to which they refer.
- The messages can be used to collect and return performance
monitoring information for a path---e.g., path delay and
throughput.
- Monitoring operates in two modes: collection and return.
o Setup Message
Generated by the path initiator and used to establish forwarding
state in forwarding agents. It contains:
1. End-to-end path label and label stack.
2. Route.
3. Path label collision indication.
4. Multicast group identifier (for multicast).
5. Indication of whether the path is source- or
destination-initiated.
6. Service requirements for the source and/or destination (TLV
format).
7. Monitored information for the path updated at each node in the
path (TLV format).
o Accept Message
This message is generated by the path target and is used to
indicate successful path establishment from initiator to target.
It contains:
1. The label of the accepted path.
2. Any monitored information for the path, collected during setup.
o Teardown Message
This message is generated by any forwarding agent on the path and
is used to remove forwarding state. It contains:
1. The label of the path being torn down.
2. Any monitored information for the path collected along the
path.
3. The reason for the teardown (TLV format). This may include
target service requirements. Teardown messages may travel in
both directions along paths and may result from any of the
following:
- Failure to meet source and/or destination's service
requirements.
- Loss of component lower-level path.
- Timeout.
- Change in service requirements.
- Insufficient available resource at the next hop.
- Change in connectivity specification for a node in the
route.
- Unresolvable label collision.
- Preemption.
o Initiator Finite State Machine
It has four states: idle, check, ready, and done. Transitions are
described below:
- idle ! check: initiator begins the setup
- check ! ready: occurs after the initiator has successfully
completed all of the resource availability checks for the path.
- check ! idle: occurs if the initiator fails to complete the
resource availability check for the path.
- ready ! done: initiator receives an accept message.
- ready ! idle, done ! idle: occurs when the initiator
receives a teardown message for the path. Forwarding
information for the path is removed.
o Forwarding Agent and Target State Machine
This machine has three states: idle, check, and ready. State
transitions are described below:
- idle ! check: occurs when one of the agents receives a setup
message.
- check ! ready: occurs after the agent has successfully
completed all the consistency and resource availability checks
for the path---including target service requirements check.
- check ! idle: occurs if the agent fails to complete the
consistency checks and resource availability checks for the
path.
- ready ! idle: occurs when the agent receives or generates a
teardown message for the path.
o Check State Actions
- General consistency checks:
1. setup not out of date;
2. setup not duplicate;
3. path label not in use (not generally fatal).
- Checks performed by intermediate forwarding agents:
1. The forwarding agents acts on behalf of the current node in
the route specification carried in the setup message.
2. The connectivity specification label for the node, carried
in the setup message, is a valid connectivity specification
for this node.
3. The node's service restrictions do not preclude carrying
traffic along the specified route.
- Checks performed by target:
1. The route specified carried in the setup message meets the
target endpoint's service requirement.
o Resource Availability Checks
These include the following:
1. The forwarding database can accommodate state for a new path.
2. There exists a feasible path to the next node on the specified
route. This is an extensive check performed by the initiator
and intermediate forwarding agents. The initiator or
intermediate forwarding agent may have to request a route and
set up this path, or there may be such a path already
established.
Reliable Transaction Protocol
Ram Ramanathan presented briefly the reliable transaction protocol used
by Nimrod: TTCP.
Query Response Protocol
Ram Ramanathan presented the query response protocol. The slides from
the presentation will be sent to the mailing list of the working group.